lib/CodeGen/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
 155   AddedInstrMapType AddedInstrMap;      // to store instrns added in this phase
 156
 157   RegStackOffsets StackOffsets;
 158
 159   //vector<const MachineInstr *> PhiInstList;   // a list of all phi instrs
 160
 161   //------- private methods ---------------------------------------------------
 162
 163   void addInterference(const Value *const Def, const LiveVarSet *const LVSet,
 164                        const bool isCallInst);
 165
 166   void addInterferencesForArgs();
 167   void createIGNodeListsAndIGs();
 168   void buildInterferenceGraphs();
 169   //void insertCallerSavingCode(const MachineInstr *MInst,
 170   //                          const BasicBlock *BB );
 171
 172   void setCallInterferences(const MachineInstr *MInst,
 173                             const LiveVarSet *const LVSetAft );
 174
 175   void move2DelayedInstr(const MachineInstr *OrigMI,
 176                          const MachineInstr *DelayedMI );
 177
 178   void markUnusableSugColors();
 179   void allocateStackSpace4SpilledLRs();
 180
 181   RegStackOffsets & getStackOffsets() {
 182     return  StackOffsets;
 183   }
 184
 185
 186   inline void constructLiveRanges()
 187     { LRI.constructLiveRanges(); }
 188
 189   void colorIncomingArgs();
 190   void colorCallRetArgs();
 191   void updateMachineCode();
 192
 193   void printLabel(const Value *const Val);
 194   void printMachineCode();
 195
 196   friend class UltraSparcRegInfo;
 197
 198
 199   int getUsableRegAtMI(RegClass *RC,  const int RegType, const MachineInstr *MInst,
 200                        const LiveVarSet *LVSetBef, MachineInstr *MIBef,
 201                        MachineInstr *MIAft );
 202
 203   int getUnusedRegAtMI(RegClass *RC,  const MachineInstr *MInst,
 204                        const LiveVarSet *LVSetBef);
 205
 206   void setRegsUsedByThisInst(RegClass *RC, const MachineInstr *MInst );
 207   int getRegNotUsedByThisInst(RegClass *RC, const MachineInstr *MInst);
 208
 209
 210
 211   void PhyRegAlloc::insertPhiEleminateInstrns();
 212
 213  public:
 214
 215   PhyRegAlloc(const Method *const M, const TargetMachine& TM,
 216               MethodLiveVarInfo *const Lvi);
 217
 218   void allocateRegisters();             // main method called for allocatin
 219
 220 };
 221
 222
 223
 224 /*
 225
 226
 227 What to do:
 228
 229   * Insert IntCCReg checking code to insertCallerSaving
 230   * add methods like cpCCReg2Mem & cpMem2CCReg (these will accept an array
 231   and push back or push_front the instr according to PUSH_BACK, PUSH_FRONT
 232   flags
 233
 234 */
 235
 236
 237
 238
 239
 240
 241
 242
 243
 244
 245
 246 #endif
 247