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