lib/CodeGen/RegAlloc/PhyRegAlloc.h

   1 /* Title:   PhyRegAlloc.h   -*- C++ -*-
   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
   9  * RegisterClasses: Each RegClass accepts a
  10    TargetRegClass which contains machine specific info about that register
  11    class. The code in the RegClass is machine independent and they use
  12    access functions in the TargetRegClass object passed into it to get
  13    machine specific info.
  14
  15  * Machine dependent work: All parts of the register coloring algorithm
  16    except coloring of an individual node are machine independent.
  17 */
  18
  19 #ifndef PHY_REG_ALLOC_H
  20 #define PHY_REG_ALLOC_H
  21
  22 #include "llvm/CodeGen/LiveRangeInfo.h"
  23 #include "Support/NonCopyable.h"
  24 #include <map>
  25
  26 class MachineFunction;
  27 class TargetRegInfo;
  28 class FunctionLiveVarInfo;
  29 class MachineInstr;
  30 class LoopInfo;
  31 class RegClass;
  32
  33 //----------------------------------------------------------------------------
  34 // Class AddedInstrns:
  35 // When register allocator inserts new instructions in to the existing
  36 // instruction stream, it does NOT directly modify the instruction stream.
  37 // Rather, it creates an object of AddedInstrns and stick it in the
  38 // AddedInstrMap for an existing instruction. This class contains two vectors
  39 // to store such instructions added before and after an existing instruction.
  40 //----------------------------------------------------------------------------
  41
  42 struct AddedInstrns {
  43   std::vector<MachineInstr*> InstrnsBefore;//Insts added BEFORE an existing inst
  44   std::vector<MachineInstr*> InstrnsAfter; //Insts added AFTER an existing inst
  45 };
  46
  47 //----------------------------------------------------------------------------
  48 // class PhyRegAlloc:
  49 // Main class the register allocator. Call allocateRegisters() to allocate
  50 // registers for a Function.
  51 //----------------------------------------------------------------------------
  52
  53 class PhyRegAlloc : public NonCopyable {
  54   std::vector<RegClass *> RegClassList; // vector of register classes
  55   const TargetMachine &TM;              // target machine
  56   const Function *Fn;                   // name of the function we work on
  57   MachineFunction &MF;                  // descriptor for method's native code
  58   FunctionLiveVarInfo *const LVI;       // LV information for this method
  59                                         // (already computed for BBs)
  60   LiveRangeInfo LRI;                    // LR info  (will be computed)
  61   const TargetRegInfo &MRI;             // Machine Register information
  62   const unsigned NumOfRegClasses;       // recorded here for efficiency
  63
  64   // Map to indicate whether operands of each MachineInstr have been updated
  65   // according to their assigned colors.  This is primarily for debugging and
  66   // could be removed in the long run.
  67   std::map<const MachineInstr *, bool> OperandsColoredMap;
  68
  69   // AddedInstrMap - Used to store instrns added in this phase
  70   std::map<const MachineInstr *, AddedInstrns> AddedInstrMap;
  71
  72   AddedInstrns AddedInstrAtEntry;       // to store instrns added at entry
  73   LoopInfo *LoopDepthCalc;              // to calculate loop depths
  74
  75 public:
  76   PhyRegAlloc(Function *F, const TargetMachine& TM, FunctionLiveVarInfo *Lvi,
  77               LoopInfo *LoopDepthCalc);
  78   ~PhyRegAlloc();
  79
  80   // main method called for allocating registers
  81   //
  82   void allocateRegisters();
  83
  84
  85   // access to register classes by class ID
  86   //
  87   const RegClass*  getRegClassByID(unsigned int id) const {
  88     return RegClassList[id];
  89   }
  90   RegClass*  getRegClassByID(unsigned int id) {
  91     return RegClassList[id];
  92   }
  93
  94 private:
  95   void addInterference(const Value *Def, const ValueSet *LVSet,
  96                        bool isCallInst);
  97
  98   void addInterferencesForArgs();
  99   void createIGNodeListsAndIGs();
 100   void buildInterferenceGraphs();
 101
 102   void setCallInterferences(const MachineInstr *MInst,
 103                             const ValueSet *LVSetAft );
 104
 105   void move2DelayedInstr(const MachineInstr *OrigMI,
 106                          const MachineInstr *DelayedMI );
 107
 108   void markUnusableSugColors();
 109   void allocateStackSpace4SpilledLRs();
 110
 111   void insertCode4SpilledLR     (const LiveRange *LR,
 112                                  MachineInstr *MInst,
 113                                  const BasicBlock *BB,
 114                                  const unsigned OpNum);
 115
 116   inline void constructLiveRanges() { LRI.constructLiveRanges(); }
 117
 118   void colorIncomingArgs();
 119   void colorCallRetArgs();
 120   void updateMachineCode();
 121   void updateInstruction(MachineInstr* MInst, BasicBlock* BB);
 122
 123   void printLabel(const Value *const Val);
 124   void printMachineCode();
 125
 126
 127   friend class UltraSparcRegInfo;  // FIXME: remove this
 128
 129   int getUsableUniRegAtMI(int RegType,
 130                           const ValueSet *LVSetBef,
 131                           MachineInstr *MInst,
 132                           std::vector<MachineInstr*>& MIBef,
 133                           std::vector<MachineInstr*>& MIAft);
 134
 135   int getUnusedUniRegAtMI(RegClass *RC, const int RegType,
 136                           const MachineInstr *MInst, const ValueSet *LVSetBef);
 137
 138   void setRelRegsUsedByThisInst(RegClass *RC, const int RegType,
 139                                 const MachineInstr *MInst );
 140
 141   int getUniRegNotUsedByThisInst(RegClass *RC, const int RegType,
 142                                  const MachineInstr *MInst);
 143
 144   void addInterf4PseudoInstr(const MachineInstr *MInst);
 145 };
 146
 147
 148 #endif
 149