lib/Target/SparcV9/RegAlloc/PhyRegAlloc.h

   1 //===-- PhyRegAlloc.h - Graph Coloring Register Allocator -------*- c++ -*-===//
   2 //
   3 // This is the main entry point for register allocation.
   4 //
   5 // Notes:
   6 // * RegisterClasses: Each RegClass accepts a
   7 //   TargetRegClass which contains machine specific info about that register
   8 //   class. The code in the RegClass is machine independent and they use
   9 //   access functions in the TargetRegClass object passed into it to get
  10 //   machine specific info.
  11 //
  12 // * Machine dependent work: All parts of the register coloring algorithm
  13 //   except coloring of an individual node are machine independent.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #ifndef PHYREGALLOC_H
  18 #define PHYREGALLOC_H
  19
  20 #include "LiveRangeInfo.h"
  21 #include "llvm/Pass.h"
  22 #include "llvm/CodeGen/MachineBasicBlock.h"
  23 #include "llvm/Target/TargetRegInfo.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include <map>
  26
  27 class MachineFunction;
  28 class FunctionLiveVarInfo;
  29 class MachineInstr;
  30 class LoopInfo;
  31 class RegClass;
  32 class Constant;
  33
  34 //----------------------------------------------------------------------------
  35 // Class AddedInstrns:
  36 // When register allocator inserts new instructions in to the existing
  37 // instruction stream, it does NOT directly modify the instruction stream.
  38 // Rather, it creates an object of AddedInstrns and stick it in the
  39 // AddedInstrMap for an existing instruction. This class contains two vectors
  40 // to store such instructions added before and after an existing instruction.
  41 //----------------------------------------------------------------------------
  42
  43 struct AddedInstrns {
  44   std::vector<MachineInstr*> InstrnsBefore;//Insts added BEFORE an existing inst
  45   std::vector<MachineInstr*> InstrnsAfter; //Insts added AFTER an existing inst
  46   inline void clear () { InstrnsBefore.clear (); InstrnsAfter.clear (); }
  47 };
  48
  49 //----------------------------------------------------------------------------
  50 // class PhyRegAlloc:
  51 // Main class the register allocator. Call runOnFunction() to allocate
  52 // registers for a Function.
  53 //----------------------------------------------------------------------------
  54
  55 class PhyRegAlloc : public FunctionPass {
  56   std::vector<RegClass *> RegClassList; // vector of register classes
  57   const TargetMachine &TM;              // target machine
  58   const Function *Fn;                   // name of the function we work on
  59   MachineFunction *MF;                  // descriptor for method's native code
  60   FunctionLiveVarInfo *LVI;             // LV information for this method
  61                                         // (already computed for BBs)
  62   LiveRangeInfo *LRI;                   // LR info  (will be computed)
  63   const TargetRegInfo &MRI;             // Machine Register information
  64   const unsigned NumOfRegClasses;       // recorded here for efficiency
  65
  66   // Map to indicate whether operands of each MachineInstr have been
  67   // updated according to their assigned colors.  This is only used in
  68   // assertion checking (debug builds).
  69   std::map<const MachineInstr *, bool> OperandsColoredMap;
  70
  71   // AddedInstrMap - Used to store instrns added in this phase
  72   std::map<const MachineInstr *, AddedInstrns> AddedInstrMap;
  73
  74   // ScratchRegsUsed - Contains scratch register uses for a particular MI.
  75   typedef std::multimap<const MachineInstr*, int> ScratchRegsUsedTy;
  76   ScratchRegsUsedTy ScratchRegsUsed;
  77
  78   AddedInstrns AddedInstrAtEntry;       // to store instrns added at entry
  79   const LoopInfo *LoopDepthCalc;        // to calculate loop depths
  80
  81   std::map<const Function *, Constant *> FnAllocState;
  82
  83   PhyRegAlloc(const PhyRegAlloc&);     // DO NOT IMPLEMENT
  84   void operator=(const PhyRegAlloc&);  // DO NOT IMPLEMENT
  85 public:
  86   inline PhyRegAlloc (const TargetMachine &TM_) :
  87     TM (TM_), MRI (TM.getRegInfo ()),
  88     NumOfRegClasses (MRI.getNumOfRegClasses ()) { }
  89   virtual ~PhyRegAlloc() { }
  90
  91   /// runOnFunction - Main method called for allocating registers.
  92   ///
  93   virtual bool runOnFunction (Function &F);
  94
  95   virtual bool doFinalization (Module &M);
  96
  97   virtual void getAnalysisUsage (AnalysisUsage &AU) const;
  98
  99   const char *getPassName () const {
 100     return "Traditional graph-coloring reg. allocator";
 101   }
 102
 103   inline const RegClass* getRegClassByID(unsigned id) const {
 104     return RegClassList[id];
 105   }
 106   inline RegClass *getRegClassByID(unsigned id) { return RegClassList[id]; }
 107
 108 private:
 109   void addInterference(const Value *Def, const ValueSet *LVSet,
 110                        bool isCallInst);
 111   bool markAllocatedRegs(MachineInstr* MInst);
 112
 113   void addInterferencesForArgs();
 114   void createIGNodeListsAndIGs();
 115   void buildInterferenceGraphs();
 116   void saveState();
 117
 118   void setCallInterferences(const MachineInstr *MI,
 119                             const ValueSet *LVSetAft);
 120
 121   void move2DelayedInstr(const MachineInstr *OrigMI,
 122                          const MachineInstr *DelayedMI);
 123
 124   void markUnusableSugColors();
 125   void allocateStackSpace4SpilledLRs();
 126
 127   void insertCode4SpilledLR(const LiveRange *LR,
 128                             MachineBasicBlock::iterator& MII,
 129                             MachineBasicBlock &MBB, unsigned OpNum);
 130
 131   // Method for inserting caller saving code. The caller must save all the
 132   // volatile registers live across a call.
 133   void insertCallerSavingCode(std::vector<MachineInstr*>& instrnsBefore,
 134                               std::vector<MachineInstr*>& instrnsAfter,
 135                               MachineInstr *CallMI,
 136                               const BasicBlock *BB);
 137
 138   void colorIncomingArgs();
 139   void colorCallRetArgs();
 140   void updateMachineCode();
 141   void updateInstruction(MachineBasicBlock::iterator& MII,
 142                          MachineBasicBlock &MBB);
 143
 144   int getUsableUniRegAtMI(int RegType, const ValueSet *LVSetBef,
 145                           MachineInstr *MI,
 146                           std::vector<MachineInstr*>& MIBef,
 147                           std::vector<MachineInstr*>& MIAft);
 148
 149   // Callback method used to find unused registers.
 150   // LVSetBef is the live variable set to search for an unused register.
 151   // If it is not specified, the LV set before the current MI is used.
 152   // This is sufficient as long as no new copy instructions are generated
 153   // to copy the free register to memory.
 154   //
 155   int getUnusedUniRegAtMI(RegClass *RC, int RegType,
 156                           const MachineInstr *MI,
 157                           const ValueSet *LVSetBef = 0);
 158
 159   void setRelRegsUsedByThisInst(RegClass *RC, int RegType,
 160                                 const MachineInstr *MI);
 161
 162   int getUniRegNotUsedByThisInst(RegClass *RC, int RegType,
 163                                  const MachineInstr *MI);
 164
 165   void addInterf4PseudoInstr(const MachineInstr *MI);
 166 };
 167
 168 #endif