Add isIdentityCopy to check for identity copy (or extract_subreg, etc.)
[oota-llvm.git] / include / llvm / Target / TargetInstrInfo.h
1 //===-- llvm/Target/TargetInstrInfo.h - Instruction Info --------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file describes the target machine instruction set to the code generator.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #ifndef LLVM_TARGET_TARGETINSTRINFO_H
15 #define LLVM_TARGET_TARGETINSTRINFO_H
16
17 #include "llvm/Target/TargetInstrDesc.h"
18 #include "llvm/CodeGen/MachineFunction.h"
19
20 namespace llvm {
21
22 class MCAsmInfo;
23 class TargetRegisterClass;
24 class TargetRegisterInfo;
25 class LiveVariables;
26 class CalleeSavedInfo;
27 class SDNode;
28 class SelectionDAG;
29
30 template<class T> class SmallVectorImpl;
31
32
33 //---------------------------------------------------------------------------
34 ///
35 /// TargetInstrInfo - Interface to description of machine instruction set
36 ///
37 class TargetInstrInfo {
38   const TargetInstrDesc *Descriptors; // Raw array to allow static init'n
39   unsigned NumOpcodes;                // Number of entries in the desc array
40
41   TargetInstrInfo(const TargetInstrInfo &);  // DO NOT IMPLEMENT
42   void operator=(const TargetInstrInfo &);   // DO NOT IMPLEMENT
43 public:
44   TargetInstrInfo(const TargetInstrDesc *desc, unsigned NumOpcodes);
45   virtual ~TargetInstrInfo();
46
47   // Invariant opcodes: All instruction sets have these as their low opcodes.
48   enum { 
49     PHI = 0,
50     INLINEASM = 1,
51     DBG_LABEL = 2,
52     EH_LABEL = 3,
53     GC_LABEL = 4,
54
55     /// KILL - This instruction is a noop that is used only to adjust the liveness
56     /// of registers. This can be useful when dealing with sub-registers.
57     KILL = 5,
58
59     /// EXTRACT_SUBREG - This instruction takes two operands: a register
60     /// that has subregisters, and a subregister index. It returns the
61     /// extracted subregister value. This is commonly used to implement
62     /// truncation operations on target architectures which support it.
63     EXTRACT_SUBREG = 6,
64
65     /// INSERT_SUBREG - This instruction takes three operands: a register
66     /// that has subregisters, a register providing an insert value, and a
67     /// subregister index. It returns the value of the first register with
68     /// the value of the second register inserted. The first register is
69     /// often defined by an IMPLICIT_DEF, as is commonly used to implement
70     /// anyext operations on target architectures which support it.
71     INSERT_SUBREG = 7,
72
73     /// IMPLICIT_DEF - This is the MachineInstr-level equivalent of undef.
74     IMPLICIT_DEF = 8,
75
76     /// SUBREG_TO_REG - This instruction is similar to INSERT_SUBREG except
77     /// that the first operand is an immediate integer constant. This constant
78     /// is often zero, as is commonly used to implement zext operations on
79     /// target architectures which support it, such as with x86-64 (with
80     /// zext from i32 to i64 via implicit zero-extension).
81     SUBREG_TO_REG = 9,
82
83     /// COPY_TO_REGCLASS - This instruction is a placeholder for a plain
84     /// register-to-register copy into a specific register class. This is only
85     /// used between instruction selection and MachineInstr creation, before
86     /// virtual registers have been created for all the instructions, and it's
87     /// only needed in cases where the register classes implied by the
88     /// instructions are insufficient. The actual MachineInstrs to perform
89     /// the copy are emitted with the TargetInstrInfo::copyRegToReg hook.
90     COPY_TO_REGCLASS = 10
91   };
92
93   unsigned getNumOpcodes() const { return NumOpcodes; }
94
95   /// get - Return the machine instruction descriptor that corresponds to the
96   /// specified instruction opcode.
97   ///
98   const TargetInstrDesc &get(unsigned Opcode) const {
99     assert(Opcode < NumOpcodes && "Invalid opcode!");
100     return Descriptors[Opcode];
101   }
102
103   /// isTriviallyReMaterializable - Return true if the instruction is trivially
104   /// rematerializable, meaning it has no side effects and requires no operands
105   /// that aren't always available.
106   bool isTriviallyReMaterializable(const MachineInstr *MI,
107                                    AliasAnalysis *AA = 0) const {
108     return MI->getOpcode() == IMPLICIT_DEF ||
109            (MI->getDesc().isRematerializable() &&
110             (isReallyTriviallyReMaterializable(MI, AA) ||
111              isReallyTriviallyReMaterializableGeneric(MI, AA)));
112   }
113
114 protected:
115   /// isReallyTriviallyReMaterializable - For instructions with opcodes for
116   /// which the M_REMATERIALIZABLE flag is set, this hook lets the target
117   /// specify whether the instruction is actually trivially rematerializable,
118   /// taking into consideration its operands. This predicate must return false
119   /// if the instruction has any side effects other than producing a value, or
120   /// if it requres any address registers that are not always available.
121   virtual bool isReallyTriviallyReMaterializable(const MachineInstr *MI,
122                                                  AliasAnalysis *AA) const {
123     return false;
124   }
125
126 private:
127   /// isReallyTriviallyReMaterializableGeneric - For instructions with opcodes
128   /// for which the M_REMATERIALIZABLE flag is set and the target hook
129   /// isReallyTriviallyReMaterializable returns false, this function does
130   /// target-independent tests to determine if the instruction is really
131   /// trivially rematerializable.
132   bool isReallyTriviallyReMaterializableGeneric(const MachineInstr *MI,
133                                                 AliasAnalysis *AA) const;
134
135 public:
136   /// isMoveInstr - Return true if the instruction is a register to register
137   /// move and return the source and dest operands and their sub-register
138   /// indices by reference.
139   virtual bool isMoveInstr(const MachineInstr& MI,
140                            unsigned& SrcReg, unsigned& DstReg,
141                            unsigned& SrcSubIdx, unsigned& DstSubIdx) const {
142     return false;
143   }
144
145   /// isIdentityCopy - Return true if the instruction is a copy (or
146   /// extract_subreg, insert_subreg, subreg_to_reg) where the source and
147   /// destination registers are the same.
148   bool isIdentityCopy(const MachineInstr &MI,
149                       unsigned &SrcReg, unsigned &DstReg,
150                       unsigned &SrcSubIdx, unsigned &DstSubIdx) const {
151     if (isMoveInstr(MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
152         SrcReg == DstReg)
153       return true;
154
155     if (MI.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) {
156       DstReg = MI.getOperand(0).getReg();
157       DstSubIdx = MI.getOperand(0).getSubReg();
158       SrcReg = MI.getOperand(1).getReg();
159       SrcSubIdx = MI.getOperand(1).getSubReg();
160       return DstReg == SrcReg;
161     }
162
163     if (MI.getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
164         MI.getOpcode() == TargetInstrInfo::SUBREG_TO_REG) {
165       DstReg = MI.getOperand(0).getReg();
166       DstSubIdx = MI.getOperand(0).getSubReg();
167       SrcReg = MI.getOperand(2).getReg();
168       SrcSubIdx = MI.getOperand(2).getSubReg();
169       return DstReg == SrcReg;
170     }
171
172     return false;
173   }
174   
175   /// isLoadFromStackSlot - If the specified machine instruction is a direct
176   /// load from a stack slot, return the virtual or physical register number of
177   /// the destination along with the FrameIndex of the loaded stack slot.  If
178   /// not, return 0.  This predicate must return 0 if the instruction has
179   /// any side effects other than loading from the stack slot.
180   virtual unsigned isLoadFromStackSlot(const MachineInstr *MI,
181                                        int &FrameIndex) const {
182     return 0;
183   }
184   
185   /// isStoreToStackSlot - If the specified machine instruction is a direct
186   /// store to a stack slot, return the virtual or physical register number of
187   /// the source reg along with the FrameIndex of the loaded stack slot.  If
188   /// not, return 0.  This predicate must return 0 if the instruction has
189   /// any side effects other than storing to the stack slot.
190   virtual unsigned isStoreToStackSlot(const MachineInstr *MI,
191                                       int &FrameIndex) const {
192     return 0;
193   }
194
195   /// reMaterialize - Re-issue the specified 'original' instruction at the
196   /// specific location targeting a new destination register.
197   virtual void reMaterialize(MachineBasicBlock &MBB,
198                              MachineBasicBlock::iterator MI,
199                              unsigned DestReg, unsigned SubIdx,
200                              const MachineInstr *Orig) const = 0;
201
202   /// convertToThreeAddress - This method must be implemented by targets that
203   /// set the M_CONVERTIBLE_TO_3_ADDR flag.  When this flag is set, the target
204   /// may be able to convert a two-address instruction into one or more true
205   /// three-address instructions on demand.  This allows the X86 target (for
206   /// example) to convert ADD and SHL instructions into LEA instructions if they
207   /// would require register copies due to two-addressness.
208   ///
209   /// This method returns a null pointer if the transformation cannot be
210   /// performed, otherwise it returns the last new instruction.
211   ///
212   virtual MachineInstr *
213   convertToThreeAddress(MachineFunction::iterator &MFI,
214                    MachineBasicBlock::iterator &MBBI, LiveVariables *LV) const {
215     return 0;
216   }
217
218   /// commuteInstruction - If a target has any instructions that are commutable,
219   /// but require converting to a different instruction or making non-trivial
220   /// changes to commute them, this method can overloaded to do this.  The
221   /// default implementation of this method simply swaps the first two operands
222   /// of MI and returns it.
223   ///
224   /// If a target wants to make more aggressive changes, they can construct and
225   /// return a new machine instruction.  If an instruction cannot commute, it
226   /// can also return null.
227   ///
228   /// If NewMI is true, then a new machine instruction must be created.
229   ///
230   virtual MachineInstr *commuteInstruction(MachineInstr *MI,
231                                            bool NewMI = false) const = 0;
232
233   /// findCommutedOpIndices - If specified MI is commutable, return the two
234   /// operand indices that would swap value. Return true if the instruction
235   /// is not in a form which this routine understands.
236   virtual bool findCommutedOpIndices(MachineInstr *MI, unsigned &SrcOpIdx1,
237                                      unsigned &SrcOpIdx2) const = 0;
238
239   /// AnalyzeBranch - Analyze the branching code at the end of MBB, returning
240   /// true if it cannot be understood (e.g. it's a switch dispatch or isn't
241   /// implemented for a target).  Upon success, this returns false and returns
242   /// with the following information in various cases:
243   ///
244   /// 1. If this block ends with no branches (it just falls through to its succ)
245   ///    just return false, leaving TBB/FBB null.
246   /// 2. If this block ends with only an unconditional branch, it sets TBB to be
247   ///    the destination block.
248   /// 3. If this block ends with an conditional branch and it falls through to
249   ///    a successor block, it sets TBB to be the branch destination block and
250   ///    a list of operands that evaluate the condition. These
251   ///    operands can be passed to other TargetInstrInfo methods to create new
252   ///    branches.
253   /// 4. If this block ends with a conditional branch followed by an
254   ///    unconditional branch, it returns the 'true' destination in TBB, the
255   ///    'false' destination in FBB, and a list of operands that evaluate the
256   ///    condition.  These operands can be passed to other TargetInstrInfo
257   ///    methods to create new branches.
258   ///
259   /// Note that RemoveBranch and InsertBranch must be implemented to support
260   /// cases where this method returns success.
261   ///
262   /// If AllowModify is true, then this routine is allowed to modify the basic
263   /// block (e.g. delete instructions after the unconditional branch).
264   ///
265   virtual bool AnalyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
266                              MachineBasicBlock *&FBB,
267                              SmallVectorImpl<MachineOperand> &Cond,
268                              bool AllowModify = false) const {
269     return true;
270   }
271
272   /// RemoveBranch - Remove the branching code at the end of the specific MBB.
273   /// This is only invoked in cases where AnalyzeBranch returns success. It
274   /// returns the number of instructions that were removed.
275   virtual unsigned RemoveBranch(MachineBasicBlock &MBB) const {
276     assert(0 && "Target didn't implement TargetInstrInfo::RemoveBranch!"); 
277     return 0;
278   }
279
280   /// InsertBranch - Insert branch code into the end of the specified
281   /// MachineBasicBlock.  The operands to this method are the same as those
282   /// returned by AnalyzeBranch.  This is only invoked in cases where
283   /// AnalyzeBranch returns success. It returns the number of instructions
284   /// inserted.
285   ///
286   /// It is also invoked by tail merging to add unconditional branches in
287   /// cases where AnalyzeBranch doesn't apply because there was no original
288   /// branch to analyze.  At least this much must be implemented, else tail
289   /// merging needs to be disabled.
290   virtual unsigned InsertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
291                             MachineBasicBlock *FBB,
292                             const SmallVectorImpl<MachineOperand> &Cond) const {
293     assert(0 && "Target didn't implement TargetInstrInfo::InsertBranch!"); 
294     return 0;
295   }
296   
297   /// copyRegToReg - Emit instructions to copy between a pair of registers. It
298   /// returns false if the target does not how to copy between the specified
299   /// registers.
300   virtual bool copyRegToReg(MachineBasicBlock &MBB,
301                             MachineBasicBlock::iterator MI,
302                             unsigned DestReg, unsigned SrcReg,
303                             const TargetRegisterClass *DestRC,
304                             const TargetRegisterClass *SrcRC) const {
305     assert(0 && "Target didn't implement TargetInstrInfo::copyRegToReg!");
306     return false;
307   }
308   
309   /// storeRegToStackSlot - Store the specified register of the given register
310   /// class to the specified stack frame index. The store instruction is to be
311   /// added to the given machine basic block before the specified machine
312   /// instruction. If isKill is true, the register operand is the last use and
313   /// must be marked kill.
314   virtual void storeRegToStackSlot(MachineBasicBlock &MBB,
315                                    MachineBasicBlock::iterator MI,
316                                    unsigned SrcReg, bool isKill, int FrameIndex,
317                                    const TargetRegisterClass *RC) const {
318     assert(0 && "Target didn't implement TargetInstrInfo::storeRegToStackSlot!");
319   }
320
321   /// loadRegFromStackSlot - Load the specified register of the given register
322   /// class from the specified stack frame index. The load instruction is to be
323   /// added to the given machine basic block before the specified machine
324   /// instruction.
325   virtual void loadRegFromStackSlot(MachineBasicBlock &MBB,
326                                     MachineBasicBlock::iterator MI,
327                                     unsigned DestReg, int FrameIndex,
328                                     const TargetRegisterClass *RC) const {
329     assert(0 && "Target didn't implement TargetInstrInfo::loadRegFromStackSlot!");
330   }
331   
332   /// spillCalleeSavedRegisters - Issues instruction(s) to spill all callee
333   /// saved registers and returns true if it isn't possible / profitable to do
334   /// so by issuing a series of store instructions via
335   /// storeRegToStackSlot(). Returns false otherwise.
336   virtual bool spillCalleeSavedRegisters(MachineBasicBlock &MBB,
337                                          MachineBasicBlock::iterator MI,
338                                 const std::vector<CalleeSavedInfo> &CSI) const {
339     return false;
340   }
341
342   /// restoreCalleeSavedRegisters - Issues instruction(s) to restore all callee
343   /// saved registers and returns true if it isn't possible / profitable to do
344   /// so by issuing a series of load instructions via loadRegToStackSlot().
345   /// Returns false otherwise.
346   virtual bool restoreCalleeSavedRegisters(MachineBasicBlock &MBB,
347                                            MachineBasicBlock::iterator MI,
348                                 const std::vector<CalleeSavedInfo> &CSI) const {
349     return false;
350   }
351   
352   /// foldMemoryOperand - Attempt to fold a load or store of the specified stack
353   /// slot into the specified machine instruction for the specified operand(s).
354   /// If this is possible, a new instruction is returned with the specified
355   /// operand folded, otherwise NULL is returned. The client is responsible for
356   /// removing the old instruction and adding the new one in the instruction
357   /// stream.
358   MachineInstr* foldMemoryOperand(MachineFunction &MF,
359                                   MachineInstr* MI,
360                                   const SmallVectorImpl<unsigned> &Ops,
361                                   int FrameIndex) const;
362
363   /// foldMemoryOperand - Same as the previous version except it allows folding
364   /// of any load and store from / to any address, not just from a specific
365   /// stack slot.
366   MachineInstr* foldMemoryOperand(MachineFunction &MF,
367                                   MachineInstr* MI,
368                                   const SmallVectorImpl<unsigned> &Ops,
369                                   MachineInstr* LoadMI) const;
370
371 protected:
372   /// foldMemoryOperandImpl - Target-dependent implementation for
373   /// foldMemoryOperand. Target-independent code in foldMemoryOperand will
374   /// take care of adding a MachineMemOperand to the newly created instruction.
375   virtual MachineInstr* foldMemoryOperandImpl(MachineFunction &MF,
376                                           MachineInstr* MI,
377                                           const SmallVectorImpl<unsigned> &Ops,
378                                           int FrameIndex) const {
379     return 0;
380   }
381
382   /// foldMemoryOperandImpl - Target-dependent implementation for
383   /// foldMemoryOperand. Target-independent code in foldMemoryOperand will
384   /// take care of adding a MachineMemOperand to the newly created instruction.
385   virtual MachineInstr* foldMemoryOperandImpl(MachineFunction &MF,
386                                               MachineInstr* MI,
387                                               const SmallVectorImpl<unsigned> &Ops,
388                                               MachineInstr* LoadMI) const {
389     return 0;
390   }
391
392 public:
393   /// canFoldMemoryOperand - Returns true for the specified load / store if
394   /// folding is possible.
395   virtual
396   bool canFoldMemoryOperand(const MachineInstr *MI,
397                             const SmallVectorImpl<unsigned> &Ops) const {
398     return false;
399   }
400
401   /// unfoldMemoryOperand - Separate a single instruction which folded a load or
402   /// a store or a load and a store into two or more instruction. If this is
403   /// possible, returns true as well as the new instructions by reference.
404   virtual bool unfoldMemoryOperand(MachineFunction &MF, MachineInstr *MI,
405                                 unsigned Reg, bool UnfoldLoad, bool UnfoldStore,
406                                  SmallVectorImpl<MachineInstr*> &NewMIs) const{
407     return false;
408   }
409
410   virtual bool unfoldMemoryOperand(SelectionDAG &DAG, SDNode *N,
411                                    SmallVectorImpl<SDNode*> &NewNodes) const {
412     return false;
413   }
414
415   /// getOpcodeAfterMemoryUnfold - Returns the opcode of the would be new
416   /// instruction after load / store are unfolded from an instruction of the
417   /// specified opcode. It returns zero if the specified unfolding is not
418   /// possible.
419   virtual unsigned getOpcodeAfterMemoryUnfold(unsigned Opc,
420                                       bool UnfoldLoad, bool UnfoldStore) const {
421     return 0;
422   }
423   
424   /// BlockHasNoFallThrough - Return true if the specified block does not
425   /// fall-through into its successor block.  This is primarily used when a
426   /// branch is unanalyzable.  It is useful for things like unconditional
427   /// indirect branches (jump tables).
428   virtual bool BlockHasNoFallThrough(const MachineBasicBlock &MBB) const {
429     return false;
430   }
431   
432   /// ReverseBranchCondition - Reverses the branch condition of the specified
433   /// condition list, returning false on success and true if it cannot be
434   /// reversed.
435   virtual
436   bool ReverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const {
437     return true;
438   }
439   
440   /// insertNoop - Insert a noop into the instruction stream at the specified
441   /// point.
442   virtual void insertNoop(MachineBasicBlock &MBB, 
443                           MachineBasicBlock::iterator MI) const;
444   
445   /// isPredicated - Returns true if the instruction is already predicated.
446   ///
447   virtual bool isPredicated(const MachineInstr *MI) const {
448     return false;
449   }
450
451   /// isUnpredicatedTerminator - Returns true if the instruction is a
452   /// terminator instruction that has not been predicated.
453   virtual bool isUnpredicatedTerminator(const MachineInstr *MI) const;
454
455   /// PredicateInstruction - Convert the instruction into a predicated
456   /// instruction. It returns true if the operation was successful.
457   virtual
458   bool PredicateInstruction(MachineInstr *MI,
459                         const SmallVectorImpl<MachineOperand> &Pred) const = 0;
460
461   /// SubsumesPredicate - Returns true if the first specified predicate
462   /// subsumes the second, e.g. GE subsumes GT.
463   virtual
464   bool SubsumesPredicate(const SmallVectorImpl<MachineOperand> &Pred1,
465                          const SmallVectorImpl<MachineOperand> &Pred2) const {
466     return false;
467   }
468
469   /// DefinesPredicate - If the specified instruction defines any predicate
470   /// or condition code register(s) used for predication, returns true as well
471   /// as the definition predicate(s) by reference.
472   virtual bool DefinesPredicate(MachineInstr *MI,
473                                 std::vector<MachineOperand> &Pred) const {
474     return false;
475   }
476
477   /// isSafeToMoveRegClassDefs - Return true if it's safe to move a machine
478   /// instruction that defines the specified register class.
479   virtual bool isSafeToMoveRegClassDefs(const TargetRegisterClass *RC) const {
480     return true;
481   }
482
483   /// GetInstSize - Returns the size of the specified Instruction.
484   /// 
485   virtual unsigned GetInstSizeInBytes(const MachineInstr *MI) const {
486     assert(0 && "Target didn't implement TargetInstrInfo::GetInstSize!");
487     return 0;
488   }
489
490   /// GetFunctionSizeInBytes - Returns the size of the specified
491   /// MachineFunction.
492   /// 
493   virtual unsigned GetFunctionSizeInBytes(const MachineFunction &MF) const = 0;
494   
495   /// Measure the specified inline asm to determine an approximation of its
496   /// length.
497   virtual unsigned getInlineAsmLength(const char *Str,
498                                       const MCAsmInfo &MAI) const;
499 };
500
501 /// TargetInstrInfoImpl - This is the default implementation of
502 /// TargetInstrInfo, which just provides a couple of default implementations
503 /// for various methods.  This separated out because it is implemented in
504 /// libcodegen, not in libtarget.
505 class TargetInstrInfoImpl : public TargetInstrInfo {
506 protected:
507   TargetInstrInfoImpl(const TargetInstrDesc *desc, unsigned NumOpcodes)
508   : TargetInstrInfo(desc, NumOpcodes) {}
509 public:
510   virtual MachineInstr *commuteInstruction(MachineInstr *MI,
511                                            bool NewMI = false) const;
512   virtual bool findCommutedOpIndices(MachineInstr *MI, unsigned &SrcOpIdx1,
513                                      unsigned &SrcOpIdx2) const;
514   virtual bool PredicateInstruction(MachineInstr *MI,
515                             const SmallVectorImpl<MachineOperand> &Pred) const;
516   virtual void reMaterialize(MachineBasicBlock &MBB,
517                              MachineBasicBlock::iterator MI,
518                              unsigned DestReg, unsigned SubReg,
519                              const MachineInstr *Orig) const;
520   virtual unsigned GetFunctionSizeInBytes(const MachineFunction &MF) const;
521 };
522
523 } // End llvm namespace
524
525 #endif