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