Fix typo in a comment.
[oota-llvm.git] / include / llvm / Target / TargetRegisterInfo.h
1 //=== Target/TargetRegisterInfo.h - Target Register Information -*- 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 an abstract interface used to get information about a
11 // target machines register file.  This information is used for a variety of
12 // purposed, especially register allocation.
13 //
14 //===----------------------------------------------------------------------===//
15
16 #ifndef LLVM_TARGET_TARGETREGISTERINFO_H
17 #define LLVM_TARGET_TARGETREGISTERINFO_H
18
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/CodeGen/MachineBasicBlock.h"
21 #include "llvm/CodeGen/ValueTypes.h"
22 #include <cassert>
23 #include <functional>
24
25 namespace llvm {
26
27 class BitVector;
28 class MachineFunction;
29 class MachineInstr;
30 class MachineMove;
31 class RegScavenger;
32 class SDNode;
33 class SelectionDAG;
34 class TargetRegisterClass;
35 class Type;
36
37 /// TargetRegisterDesc - This record contains all of the information known about
38 /// a particular register.  The AliasSet field (if not null) contains a pointer
39 /// to a Zero terminated array of registers that this register aliases.  This is
40 /// needed for architectures like X86 which have AL alias AX alias EAX.
41 /// Registers that this does not apply to simply should set this to null.
42 /// The SubRegs field is a zero terminated array of registers that are
43 /// sub-registers of the specific register, e.g. AL, AH are sub-registers of AX.
44 /// The SuperRegs field is a zero terminated array of registers that are
45 /// super-registers of the specific register, e.g. RAX, EAX, are super-registers
46 /// of AX.
47 ///
48 struct TargetRegisterDesc {
49   const char     *AsmName;      // Assembly language name for the register
50   const char     *Name;         // Printable name for the reg (for debugging)
51   const unsigned *AliasSet;     // Register Alias Set, described above
52   const unsigned *SubRegs;      // Sub-register set, described above
53   const unsigned *SuperRegs;    // Super-register set, described above
54 };
55
56 class TargetRegisterClass {
57 public:
58   typedef const unsigned* iterator;
59   typedef const unsigned* const_iterator;
60
61   typedef const MVT* vt_iterator;
62   typedef const TargetRegisterClass* const * sc_iterator;
63 private:
64   unsigned ID;
65   bool  isSubClass;
66   const vt_iterator VTs;
67   const sc_iterator SubClasses;
68   const sc_iterator SuperClasses;
69   const sc_iterator SubRegClasses;
70   const sc_iterator SuperRegClasses;
71   const unsigned RegSize, Alignment;    // Size & Alignment of register in bytes
72   const int CopyCost;
73   const iterator RegsBegin, RegsEnd;
74 public:
75   TargetRegisterClass(unsigned id,
76                       const MVT *vts,
77                       const TargetRegisterClass * const *subcs,
78                       const TargetRegisterClass * const *supcs,
79                       const TargetRegisterClass * const *subregcs,
80                       const TargetRegisterClass * const *superregcs,
81                       unsigned RS, unsigned Al, int CC,
82                       iterator RB, iterator RE)
83     : ID(id), VTs(vts), SubClasses(subcs), SuperClasses(supcs),
84     SubRegClasses(subregcs), SuperRegClasses(superregcs),
85     RegSize(RS), Alignment(Al), CopyCost(CC), RegsBegin(RB), RegsEnd(RE) {}
86   virtual ~TargetRegisterClass() {}     // Allow subclasses
87   
88   /// getID() - Return the register class ID number.
89   ///
90   unsigned getID() const { return ID; }
91   
92   /// begin/end - Return all of the registers in this class.
93   ///
94   iterator       begin() const { return RegsBegin; }
95   iterator         end() const { return RegsEnd; }
96
97   /// getNumRegs - Return the number of registers in this class.
98   ///
99   unsigned getNumRegs() const { return (unsigned)(RegsEnd-RegsBegin); }
100
101   /// getRegister - Return the specified register in the class.
102   ///
103   unsigned getRegister(unsigned i) const {
104     assert(i < getNumRegs() && "Register number out of range!");
105     return RegsBegin[i];
106   }
107
108   /// contains - Return true if the specified register is included in this
109   /// register class.
110   bool contains(unsigned Reg) const {
111     for (iterator I = begin(), E = end(); I != E; ++I)
112       if (*I == Reg) return true;
113     return false;
114   }
115
116   /// hasType - return true if this TargetRegisterClass has the ValueType vt.
117   ///
118   bool hasType(MVT vt) const {
119     for(int i = 0; VTs[i] != MVT::Other; ++i)
120       if (VTs[i] == vt)
121         return true;
122     return false;
123   }
124   
125   /// vt_begin / vt_end - Loop over all of the value types that can be
126   /// represented by values in this register class.
127   vt_iterator vt_begin() const {
128     return VTs;
129   }
130
131   vt_iterator vt_end() const {
132     vt_iterator I = VTs;
133     while (*I != MVT::Other) ++I;
134     return I;
135   }
136
137   /// hasSubClass - return true if the specified TargetRegisterClass is a
138   /// sub-register class of this TargetRegisterClass.
139   bool hasSubClass(const TargetRegisterClass *cs) const {
140     for (int i = 0; SubClasses[i] != NULL; ++i) 
141       if (SubClasses[i] == cs)
142         return true;
143     return false;
144   }
145
146   /// subclasses_begin / subclasses_end - Loop over all of the sub-classes of
147   /// this register class.
148   sc_iterator subclasses_begin() const {
149     return SubClasses;
150   }
151   
152   sc_iterator subclasses_end() const {
153     sc_iterator I = SubClasses;
154     while (*I != NULL) ++I;
155     return I;
156   }
157   
158   /// hasSuperClass - return true if the specified TargetRegisterClass is a
159   /// super-register class of this TargetRegisterClass.
160   bool hasSuperClass(const TargetRegisterClass *cs) const {
161     for (int i = 0; SuperClasses[i] != NULL; ++i) 
162       if (SuperClasses[i] == cs)
163         return true;
164     return false;
165   }
166
167   /// superclasses_begin / superclasses_end - Loop over all of the super-classes
168   /// of this register class.
169   sc_iterator superclasses_begin() const {
170     return SuperClasses;
171   }
172   
173   sc_iterator superclasses_end() const {
174     sc_iterator I = SuperClasses;
175     while (*I != NULL) ++I;
176     return I;
177   }
178   
179   /// subregclasses_begin / subregclasses_end - Loop over all of
180   /// the subregister classes of this register class.
181   sc_iterator subregclasses_begin() const {
182     return SubRegClasses;
183   }
184   
185   sc_iterator subregclasses_end() const {
186     sc_iterator I = SubRegClasses;
187     while (*I != NULL) ++I;
188     return I;
189   }
190   
191   /// superregclasses_begin / superregclasses_end - Loop over all of
192   /// the superregister classes of this register class.
193   sc_iterator superregclasses_begin() const {
194     return SuperRegClasses;
195   }
196   
197   sc_iterator superregclasses_end() const {
198     sc_iterator I = SuperRegClasses;
199     while (*I != NULL) ++I;
200     return I;
201   }
202   
203   /// allocation_order_begin/end - These methods define a range of registers
204   /// which specify the registers in this class that are valid to register
205   /// allocate, and the preferred order to allocate them in.  For example,
206   /// callee saved registers should be at the end of the list, because it is
207   /// cheaper to allocate caller saved registers.
208   ///
209   /// These methods take a MachineFunction argument, which can be used to tune
210   /// the allocatable registers based on the characteristics of the function.
211   /// One simple example is that the frame pointer register can be used if
212   /// frame-pointer-elimination is performed.
213   ///
214   /// By default, these methods return all registers in the class.
215   ///
216   virtual iterator allocation_order_begin(const MachineFunction &MF) const {
217     return begin();
218   }
219   virtual iterator allocation_order_end(const MachineFunction &MF)   const {
220     return end();
221   }
222
223
224
225   /// getSize - Return the size of the register in bytes, which is also the size
226   /// of a stack slot allocated to hold a spilled copy of this register.
227   unsigned getSize() const { return RegSize; }
228
229   /// getAlignment - Return the minimum required alignment for a register of
230   /// this class.
231   unsigned getAlignment() const { return Alignment; }
232
233   /// getCopyCost - Return the cost of copying a value between two registers in
234   /// this class.
235   int getCopyCost() const { return CopyCost; }
236 };
237
238
239 /// TargetRegisterInfo base class - We assume that the target defines a static
240 /// array of TargetRegisterDesc objects that represent all of the machine
241 /// registers that the target has.  As such, we simply have to track a pointer
242 /// to this array so that we can turn register number into a register
243 /// descriptor.
244 ///
245 class TargetRegisterInfo {
246 protected:
247   const unsigned* SubregHash;
248   const unsigned SubregHashSize;
249 public:
250   typedef const TargetRegisterClass * const * regclass_iterator;
251 private:
252   const TargetRegisterDesc *Desc;             // Pointer to the descriptor array
253   unsigned NumRegs;                           // Number of entries in the array
254
255   regclass_iterator RegClassBegin, RegClassEnd;   // List of regclasses
256
257   int CallFrameSetupOpcode, CallFrameDestroyOpcode;
258 protected:
259   TargetRegisterInfo(const TargetRegisterDesc *D, unsigned NR,
260                      regclass_iterator RegClassBegin,
261                      regclass_iterator RegClassEnd,
262                      int CallFrameSetupOpcode = -1,
263                      int CallFrameDestroyOpcode = -1,
264                      const unsigned* subregs = 0,
265                      const unsigned subregsize = 0);
266   virtual ~TargetRegisterInfo();
267 public:
268
269   enum {                        // Define some target independent constants
270     /// NoRegister - This physical register is not a real target register.  It
271     /// is useful as a sentinal.
272     NoRegister = 0,
273
274     /// FirstVirtualRegister - This is the first register number that is
275     /// considered to be a 'virtual' register, which is part of the SSA
276     /// namespace.  This must be the same for all targets, which means that each
277     /// target is limited to 1024 registers.
278     FirstVirtualRegister = 1024
279   };
280
281   /// isPhysicalRegister - Return true if the specified register number is in
282   /// the physical register namespace.
283   static bool isPhysicalRegister(unsigned Reg) {
284     assert(Reg && "this is not a register!");
285     return Reg < FirstVirtualRegister;
286   }
287
288   /// isVirtualRegister - Return true if the specified register number is in
289   /// the virtual register namespace.
290   static bool isVirtualRegister(unsigned Reg) {
291     assert(Reg && "this is not a register!");
292     return Reg >= FirstVirtualRegister;
293   }
294
295   /// getPhysicalRegisterRegClass - Returns the Register Class of a physical
296   /// register of the given type. If type is MVT::Other, then just return any
297   /// register class the register belongs to.
298   const TargetRegisterClass *getPhysicalRegisterRegClass(unsigned Reg,
299                                           MVT VT = MVT::Other) const;
300
301   /// getAllocatableSet - Returns a bitset indexed by register number
302   /// indicating if a register is allocatable or not. If a register class is
303   /// specified, returns the subset for the class.
304   BitVector getAllocatableSet(MachineFunction &MF,
305                               const TargetRegisterClass *RC = NULL) const;
306
307   const TargetRegisterDesc &operator[](unsigned RegNo) const {
308     assert(RegNo < NumRegs &&
309            "Attempting to access record for invalid register number!");
310     return Desc[RegNo];
311   }
312
313   /// Provide a get method, equivalent to [], but more useful if we have a
314   /// pointer to this object.
315   ///
316   const TargetRegisterDesc &get(unsigned RegNo) const {
317     return operator[](RegNo);
318   }
319
320   /// getAliasSet - Return the set of registers aliased by the specified
321   /// register, or a null list of there are none.  The list returned is zero
322   /// terminated.
323   ///
324   const unsigned *getAliasSet(unsigned RegNo) const {
325     return get(RegNo).AliasSet;
326   }
327
328   /// getSubRegisters - Return the list of registers that are sub-registers of
329   /// the specified register, or a null list of there are none. The list
330   /// returned is zero terminated and sorted according to super-sub register
331   /// relations. e.g. X86::RAX's sub-register list is EAX, AX, AL, AH.
332   ///
333   const unsigned *getSubRegisters(unsigned RegNo) const {
334     return get(RegNo).SubRegs;
335   }
336
337   /// getSuperRegisters - Return the list of registers that are super-registers
338   /// of the specified register, or a null list of there are none. The list
339   /// returned is zero terminated and sorted according to super-sub register
340   /// relations. e.g. X86::AL's super-register list is RAX, EAX, AX.
341   ///
342   const unsigned *getSuperRegisters(unsigned RegNo) const {
343     return get(RegNo).SuperRegs;
344   }
345
346   /// getAsmName - Return the symbolic target-specific name for the
347   /// specified physical register.
348   const char *getAsmName(unsigned RegNo) const {
349     return get(RegNo).AsmName;
350   }
351
352   /// getName - Return the human-readable symbolic target-specific name for the
353   /// specified physical register.
354   const char *getName(unsigned RegNo) const {
355     return get(RegNo).Name;
356   }
357
358   /// getNumRegs - Return the number of registers this target has (useful for
359   /// sizing arrays holding per register information)
360   unsigned getNumRegs() const {
361     return NumRegs;
362   }
363
364   /// areAliases - Returns true if the two registers alias each other, false
365   /// otherwise
366   bool areAliases(unsigned regA, unsigned regB) const {
367     for (const unsigned *Alias = getAliasSet(regA); *Alias; ++Alias)
368       if (*Alias == regB) return true;
369     return false;
370   }
371
372   /// regsOverlap - Returns true if the two registers are equal or alias each
373   /// other. The registers may be virtual register.
374   bool regsOverlap(unsigned regA, unsigned regB) const {
375     if (regA == regB)
376       return true;
377
378     if (isVirtualRegister(regA) || isVirtualRegister(regB))
379       return false;
380     return areAliases(regA, regB);
381   }
382
383   /// isSubRegister - Returns true if regB is a sub-register of regA.
384   ///
385   bool isSubRegister(unsigned regA, unsigned regB) const {
386     // SubregHash is a simple quadratically probed hash table.
387     size_t index = (regA + regB * 37) & (SubregHashSize-1);
388     unsigned ProbeAmt = 2;
389     while (SubregHash[index*2] != 0 &&
390            SubregHash[index*2+1] != 0) {
391       if (SubregHash[index*2] == regA && SubregHash[index*2+1] == regB)
392         return true;
393       
394       index = (index + ProbeAmt) & (SubregHashSize-1);
395       ProbeAmt += 2;
396     }
397     
398     return false;
399   }
400
401   /// isSuperRegister - Returns true if regB is a super-register of regA.
402   ///
403   bool isSuperRegister(unsigned regA, unsigned regB) const {
404     for (const unsigned *SR = getSuperRegisters(regA); *SR; ++SR)
405       if (*SR == regB) return true;
406     return false;
407   }
408
409   /// getCalleeSavedRegs - Return a null-terminated list of all of the
410   /// callee saved registers on this target. The register should be in the
411   /// order of desired callee-save stack frame offset. The first register is
412   /// closed to the incoming stack pointer if stack grows down, and vice versa.
413   virtual const unsigned* getCalleeSavedRegs(const MachineFunction *MF = 0)
414                                                                       const = 0;
415
416   /// getCalleeSavedRegClasses - Return a null-terminated list of the preferred
417   /// register classes to spill each callee saved register with.  The order and
418   /// length of this list match the getCalleeSaveRegs() list.
419   virtual const TargetRegisterClass* const *getCalleeSavedRegClasses(
420                                             const MachineFunction *MF) const =0;
421
422   /// getReservedRegs - Returns a bitset indexed by physical register number
423   /// indicating if a register is a special register that has particular uses
424   /// and should be considered unavailable at all times, e.g. SP, RA. This is
425   /// used by register scavenger to determine what registers are free.
426   virtual BitVector getReservedRegs(const MachineFunction &MF) const = 0;
427
428   /// getSubReg - Returns the physical register number of sub-register "Index"
429   /// for physical register RegNo. Return zero if the sub-register does not
430   /// exist.
431   virtual unsigned getSubReg(unsigned RegNo, unsigned Index) const = 0;
432
433   //===--------------------------------------------------------------------===//
434   // Register Class Information
435   //
436
437   /// Register class iterators
438   ///
439   regclass_iterator regclass_begin() const { return RegClassBegin; }
440   regclass_iterator regclass_end() const { return RegClassEnd; }
441
442   unsigned getNumRegClasses() const {
443     return (unsigned)(regclass_end()-regclass_begin());
444   }
445   
446   /// getRegClass - Returns the register class associated with the enumeration
447   /// value.  See class TargetOperandInfo.
448   const TargetRegisterClass *getRegClass(unsigned i) const {
449     assert(i <= getNumRegClasses() && "Register Class ID out of range");
450     return i ? RegClassBegin[i - 1] : NULL;
451   }
452
453   //===--------------------------------------------------------------------===//
454   // Interfaces used by the register allocator and stack frame
455   // manipulation passes to move data around between registers,
456   // immediates and memory.  FIXME: Move these to TargetInstrInfo.h.
457   //
458
459   /// getCrossCopyRegClass - Returns a legal register class to copy a register
460   /// in the specified class to or from. Returns NULL if it is possible to copy
461   /// between a two registers of the specified class.
462   virtual const TargetRegisterClass *
463   getCrossCopyRegClass(const TargetRegisterClass *RC) const {
464     return NULL;
465   }
466
467   /// targetHandlesStackFrameRounding - Returns true if the target is
468   /// responsible for rounding up the stack frame (probably at emitPrologue
469   /// time).
470   virtual bool targetHandlesStackFrameRounding() const {
471     return false;
472   }
473
474   /// requiresRegisterScavenging - returns true if the target requires (and can
475   /// make use of) the register scavenger.
476   virtual bool requiresRegisterScavenging(const MachineFunction &MF) const {
477     return false;
478   }
479   
480   /// hasFP - Return true if the specified function should have a dedicated
481   /// frame pointer register. For most targets this is true only if the function
482   /// has variable sized allocas or if frame pointer elimination is disabled.
483   virtual bool hasFP(const MachineFunction &MF) const = 0;
484
485   // hasReservedCallFrame - Under normal circumstances, when a frame pointer is
486   // not required, we reserve argument space for call sites in the function
487   // immediately on entry to the current function. This eliminates the need for
488   // add/sub sp brackets around call sites. Returns true if the call frame is
489   // included as part of the stack frame.
490   virtual bool hasReservedCallFrame(MachineFunction &MF) const {
491     return !hasFP(MF);
492   }
493
494   // needsStackRealignment - true if storage within the function requires the
495   // stack pointer to be aligned more than the normal calling convention calls
496   // for.
497   virtual bool needsStackRealignment(const MachineFunction &MF) const {
498     return false;
499   }
500
501   /// getCallFrameSetup/DestroyOpcode - These methods return the opcode of the
502   /// frame setup/destroy instructions if they exist (-1 otherwise).  Some
503   /// targets use pseudo instructions in order to abstract away the difference
504   /// between operating with a frame pointer and operating without, through the
505   /// use of these two instructions.
506   ///
507   int getCallFrameSetupOpcode() const { return CallFrameSetupOpcode; }
508   int getCallFrameDestroyOpcode() const { return CallFrameDestroyOpcode; }
509
510
511   /// eliminateCallFramePseudoInstr - This method is called during prolog/epilog
512   /// code insertion to eliminate call frame setup and destroy pseudo
513   /// instructions (but only if the Target is using them).  It is responsible
514   /// for eliminating these instructions, replacing them with concrete
515   /// instructions.  This method need only be implemented if using call frame
516   /// setup/destroy pseudo instructions.
517   ///
518   virtual void
519   eliminateCallFramePseudoInstr(MachineFunction &MF,
520                                 MachineBasicBlock &MBB,
521                                 MachineBasicBlock::iterator MI) const {
522     assert(getCallFrameSetupOpcode()== -1 && getCallFrameDestroyOpcode()== -1 &&
523            "eliminateCallFramePseudoInstr must be implemented if using"
524            " call frame setup/destroy pseudo instructions!");
525     assert(0 && "Call Frame Pseudo Instructions do not exist on this target!");
526   }
527
528   /// processFunctionBeforeCalleeSavedScan - This method is called immediately
529   /// before PrologEpilogInserter scans the physical registers used to determine
530   /// what callee saved registers should be spilled. This method is optional.
531   virtual void processFunctionBeforeCalleeSavedScan(MachineFunction &MF,
532                                                 RegScavenger *RS = NULL) const {
533
534   }
535
536   /// processFunctionBeforeFrameFinalized - This method is called immediately
537   /// before the specified functions frame layout (MF.getFrameInfo()) is
538   /// finalized.  Once the frame is finalized, MO_FrameIndex operands are
539   /// replaced with direct constants.  This method is optional.
540   ///
541   virtual void processFunctionBeforeFrameFinalized(MachineFunction &MF) const {
542   }
543
544   /// eliminateFrameIndex - This method must be overriden to eliminate abstract
545   /// frame indices from instructions which may use them.  The instruction
546   /// referenced by the iterator contains an MO_FrameIndex operand which must be
547   /// eliminated by this method.  This method may modify or replace the
548   /// specified instruction, as long as it keeps the iterator pointing the the
549   /// finished product. SPAdj is the SP adjustment due to call frame setup
550   /// instruction.
551   virtual void eliminateFrameIndex(MachineBasicBlock::iterator MI,
552                                    int SPAdj, RegScavenger *RS=NULL) const = 0;
553
554   /// emitProlog/emitEpilog - These methods insert prolog and epilog code into
555   /// the function.
556   virtual void emitPrologue(MachineFunction &MF) const = 0;
557   virtual void emitEpilogue(MachineFunction &MF,
558                             MachineBasicBlock &MBB) const = 0;
559                             
560   //===--------------------------------------------------------------------===//
561   /// Debug information queries.
562   
563   /// getDwarfRegNum - Map a target register to an equivalent dwarf register
564   /// number.  Returns -1 if there is no equivalent value.  The second
565   /// parameter allows targets to use different numberings for EH info and
566   /// debugging info.
567   virtual int getDwarfRegNum(unsigned RegNum, bool isEH) const = 0;
568
569   /// getFrameRegister - This method should return the register used as a base
570   /// for values allocated in the current stack frame.
571   virtual unsigned getFrameRegister(MachineFunction &MF) const = 0;
572
573   /// getFrameIndexOffset - Returns the displacement from the frame register to
574   /// the stack frame of the specified index.
575   virtual int getFrameIndexOffset(MachineFunction &MF, int FI) const;
576                            
577   /// getRARegister - This method should return the register where the return
578   /// address can be found.
579   virtual unsigned getRARegister() const = 0;
580   
581   /// getInitialFrameState - Returns a list of machine moves that are assumed
582   /// on entry to all functions.  Note that LabelID is ignored (assumed to be
583   /// the beginning of the function.)
584   virtual void getInitialFrameState(std::vector<MachineMove> &Moves) const;
585 };
586
587 // This is useful when building IndexedMaps keyed on virtual registers
588 struct VirtReg2IndexFunctor : std::unary_function<unsigned, unsigned> {
589   unsigned operator()(unsigned Reg) const {
590     return Reg - TargetRegisterInfo::FirstVirtualRegister;
591   }
592 };
593
594 } // End llvm namespace
595
596 #endif