lib/Target/SparcV9/RegAlloc/PhyRegAlloc.h

   1 /* Title:   PhyRegAlloc.h
   2    Author:  Ruchira Sasanka
   3    Date:    Aug 20, 01
   4    Purpose: This is the main entry point for register allocation.
   5
   6    Notes:
   7
   8  * RegisterClasses: Each RegClass accepts a
   9    MachineRegClass which contains machine specific info about that register
  10    class. The code in the RegClass is machine independent and they use
  11    access functions in the MachineRegClass object passed into it to get
  12    machine specific info.
  13
  14  * Machine dependent work: All parts of the register coloring algorithm
  15    except coloring of an individual node are machine independent.
  16
  17    Register allocation must be done  as:
  18
  19      static const MachineRegInfo MRI = MachineRegInfo();  // machine reg info
  20
  21      MethodLiveVarInfo LVI(*MethodI );                    // compute LV info
  22      LVI.analyze();
  23
  24      PhyRegAlloc PRA(*MethodI, &MRI, &LVI);               // allocate regs
  25      PRA.allocateRegisters();
  26
  27    Assumptions:
  28      All values in a live range will be of the same physical reg class.
  29
  30 */
  31
  32 #ifndef PHY_REG_ALLOC_H
  33 #define PHY_REG_ALLOC_H
  34
  35 #include "llvm/CodeGen/MachineInstr.h"
  36 #include "llvm/CodeGen/RegClass.h"
  37 #include "llvm/CodeGen/LiveRangeInfo.h"
  38 #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
  39
  40 #include <deque>
  41
  42
  43 //----------------------------------------------------------------------------
  44 // Class AddedInstrns:
  45 // When register allocator inserts new instructions in to the existing
  46 // instruction stream, it does NOT directly modify the instruction stream.
  47 // Rather, it creates an object of AddedInstrns and stick it in the
  48 // AddedInstrMap for an existing instruction. This class contains two vectors
  49 // to store such instructions added before and after an existing instruction.
  50 //----------------------------------------------------------------------------
  51
  52 class AddedInstrns
  53 {
  54  public:
  55   deque<MachineInstr *> InstrnsBefore;  // Added insts BEFORE an existing inst
  56   deque<MachineInstr *> InstrnsAfter;   // Added insts AFTER an existing inst
  57
  58   AddedInstrns() : InstrnsBefore(), InstrnsAfter() { }
  59 };
  60
  61 typedef hash_map<const MachineInstr *, AddedInstrns *> AddedInstrMapType;
  62
  63
  64
  65 //----------------------------------------------------------------------------
  66 // Class RegStackOffsets:
  67 // This class is responsible for managing stack frame of the method for
  68 // register allocation.
  69 //
  70 //----------------------------------------------------------------------------
  71
  72 class RegStackOffsets {
  73
  74  private:
  75   int curSpilledVarOff;                 // cur pos of spilled LRs
  76   int curNewTmpPosOffset;               // cur pos of tmp values on stack
  77   bool isTmpRegionUsable;               // can we call getNewTmpPosOffFromFP
  78
  79   const int SizeOfStackItem;            // size of an item on stack
  80   const int StackSpillStartFromFP;      // start position of spill region
  81   int StartOfTmpRegion;                 // start of the tmp var region
  82
  83  public:
  84
  85   // constructor
  86
  87   RegStackOffsets(int SEnSize=8, int StartSpill=176 ) :
  88     SizeOfStackItem(SEnSize),  StackSpillStartFromFP(StartSpill) {
  89
  90     curSpilledVarOff = StartSpill;
  91     isTmpRegionUsable = false;
  92   };
  93
  94
  95   int getNewSpillOffFromFP() {
  96     int tmp =  curSpilledVarOff;
  97     curSpilledVarOff += SizeOfStackItem;
  98     return tmp;   // **TODO: Is sending un-incremented value correct?
  99   };
 100
 101
 102   // The following method must be called only after allocating space
 103   // for spilled LRs and calling setEndOfSpillRegion()
 104   int getNewTmpPosOffFromFP() {
 105     assert( isTmpRegionUsable && "Spill region still open");
 106     int tmp = curNewTmpPosOffset;
 107     curNewTmpPosOffset += SizeOfStackItem;
 108     return tmp; //**TODO: Is sending un-incremented val correct?
 109   };
 110
 111
 112   // This method is called when we have allocated space for all spilled
 113   // LRs. The tmp region can be used only after a call to this method.
 114
 115   void setEndOfSpillRegion() {
 116     assert(( ! isTmpRegionUsable) && "setEndOfSpillRegion called again");
 117     isTmpRegionUsable = true;
 118     StartOfTmpRegion = curSpilledVarOff;
 119   }
 120
 121
 122   // called when temporary values allocated on stack are no longer needed
 123   void resetTmpPos() {
 124     curNewTmpPosOffset = StartOfTmpRegion;
 125   }
 126
 127
 128 };
 129
 130
 131
 132 //----------------------------------------------------------------------------
 133 // class PhyRegAlloc:
 134 // Main class the register allocator. Call allocateRegisters() to allocate
 135 // registers for a Method.
 136 //----------------------------------------------------------------------------
 137
 138
 139 class PhyRegAlloc
 140 {
 141
 142   vector<RegClass *> RegClassList  ;    // vector of register classes
 143   const Method *const Meth;             // name of the method we work on
 144   const TargetMachine &TM;              // target machine
 145   MethodLiveVarInfo *const LVI;         // LV information for this method
 146                                         // (already computed for BBs)
 147   LiveRangeInfo LRI;                    // LR info  (will be computed)
 148   const MachineRegInfo &MRI;            // Machine Register information
 149   const unsigned NumOfRegClasses;       // recorded here for efficiency
 150
 151   //vector<const Instruction *> CallInstrList;  // a list of all call instrs
 152   //vector<const Instruction *> RetInstrList;   // a list of all return instrs
 153
 154   AddedInstrMapType AddedInstrMap;      // to store instrns added in this phase
 155
 156   RegStackOffsets StackOffsets;
 157
 158   //------- private methods ---------------------------------------------------
 159
 160   void addInterference(const Value *const Def, const LiveVarSet *const LVSet,
 161                        const bool isCallInst);
 162
 163   void addInterferencesForArgs();
 164   void createIGNodeListsAndIGs();
 165   void buildInterferenceGraphs();
 166   //void insertCallerSavingCode(const MachineInstr *MInst,
 167   //                          const BasicBlock *BB );
 168
 169   void setCallInterferences(const MachineInstr *MInst,
 170                             const LiveVarSet *const LVSetAft );
 171
 172   void move2DelayedInstr(const MachineInstr *OrigMI,
 173                          const MachineInstr *DelayedMI );
 174
 175   void markUnusableSugColors();
 176   void allocateStackSpace4SpilledLRs();
 177
 178   RegStackOffsets & getStackOffsets() {
 179     return  StackOffsets;
 180   }
 181
 182
 183   inline void constructLiveRanges()
 184     { LRI.constructLiveRanges(); }
 185
 186   void colorIncomingArgs();
 187   void colorCallRetArgs();
 188   void updateMachineCode();
 189
 190   void printLabel(const Value *const Val);
 191   void printMachineCode();
 192
 193   friend class UltraSparcRegInfo;
 194   void setRegsUsedByThisInst(RegClass *RC, const MachineInstr *MInst );
 195   int getRegNotUsedByThisInst(RegClass *RC, const MachineInstr *MInst);
 196
 197
 198  public:
 199
 200   PhyRegAlloc(const Method *const M, const TargetMachine& TM,
 201               MethodLiveVarInfo *const Lvi);
 202
 203   void allocateRegisters();             // main method called for allocatin
 204
 205 };
 206
 207
 208
 209
 210
 211
 212
 213
 214
 215
 216
 217 #endif
 218