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
  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   inline void clear () { InstrnsBefore.clear (); InstrnsAfter.clear (); }
  46 };
  47
  48 //----------------------------------------------------------------------------
  49 // class PhyRegAlloc:
  50 // Main class the register allocator. Call runOnFunction() to allocate
  51 // registers for a Function.
  52 //----------------------------------------------------------------------------
  53
  54 class PhyRegAlloc : public FunctionPass {
  55   std::vector<RegClass *> RegClassList; // vector of register classes
  56   const TargetMachine &TM;              // target machine
  57   const Function *Fn;                   // name of the function we work on
  58   MachineFunction *MF;                  // descriptor for method's native code
  59   FunctionLiveVarInfo *LVI;             // LV information for this method
  60                                         // (already computed for BBs)
  61   LiveRangeInfo *LRI;                   // LR info  (will be computed)
  62   const TargetRegInfo &MRI;             // Machine Register information
  63   const unsigned NumOfRegClasses;       // recorded here for efficiency
  64
  65   // Map to indicate whether operands of each MachineInstr have been
  66   // updated according to their assigned colors.  This is only used in
  67   // assertion checking (debug builds).
  68   std::map<const MachineInstr *, bool> OperandsColoredMap;
  69
  70   // AddedInstrMap - Used to store instrns added in this phase
  71   std::map<const MachineInstr *, AddedInstrns> AddedInstrMap;
  72
  73   // ScratchRegsUsed - Contains scratch register uses for a particular MI.
  74   typedef std::multimap<const MachineInstr*, int> ScratchRegsUsedTy;
  75   ScratchRegsUsedTy ScratchRegsUsed;
  76
  77   AddedInstrns AddedInstrAtEntry;       // to store instrns added at entry
  78   const LoopInfo *LoopDepthCalc;        // to calculate loop depths
  79
  80   PhyRegAlloc(const PhyRegAlloc&);     // DO NOT IMPLEMENT
  81   void operator=(const PhyRegAlloc&);  // DO NOT IMPLEMENT
  82 public:
  83   inline PhyRegAlloc (const TargetMachine &TM_) :
  84     TM (TM_), MRI (TM.getRegInfo ()),
  85     NumOfRegClasses (MRI.getNumOfRegClasses ()) { }
  86   virtual ~PhyRegAlloc() { }
  87
  88   /// runOnFunction - Main method called for allocating registers.
  89   ///
  90   virtual bool runOnFunction (Function &F);
  91
  92   virtual void getAnalysisUsage (AnalysisUsage &AU) const;
  93
  94   const char *getPassName () const {
  95     return "Traditional graph-coloring reg. allocator";
  96   }
  97
  98   inline const RegClass* getRegClassByID(unsigned id) const {
  99     return RegClassList[id];
 100   }
 101   inline RegClass *getRegClassByID(unsigned id) { return RegClassList[id]; }
 102
 103 private:
 104   void addInterference(const Value *Def, const ValueSet *LVSet,
 105                        bool isCallInst);
 106   bool markAllocatedRegs(MachineInstr* MInst);
 107
 108   void addInterferencesForArgs();
 109   void createIGNodeListsAndIGs();
 110   void buildInterferenceGraphs();
 111
 112   void setCallInterferences(const MachineInstr *MI,
 113                             const ValueSet *LVSetAft);
 114
 115   void move2DelayedInstr(const MachineInstr *OrigMI,
 116                          const MachineInstr *DelayedMI);
 117
 118   void markUnusableSugColors();
 119   void allocateStackSpace4SpilledLRs();
 120
 121   void insertCode4SpilledLR(const LiveRange *LR,
 122                             MachineBasicBlock::iterator& MII,
 123                             MachineBasicBlock &MBB, unsigned OpNum);
 124
 125   // Method for inserting caller saving code. The caller must save all the
 126   // volatile registers live across a call.
 127   void insertCallerSavingCode(std::vector<MachineInstr*>& instrnsBefore,
 128                               std::vector<MachineInstr*>& instrnsAfter,
 129                               MachineInstr *CallMI,
 130                               const BasicBlock *BB);
 131
 132   void colorIncomingArgs();
 133   void colorCallRetArgs();
 134   void updateMachineCode();
 135   void updateInstruction(MachineBasicBlock::iterator& MII,
 136                          MachineBasicBlock &MBB);
 137
 138   int getUsableUniRegAtMI(int RegType, const ValueSet *LVSetBef,
 139                           MachineInstr *MI,
 140                           std::vector<MachineInstr*>& MIBef,
 141                           std::vector<MachineInstr*>& MIAft);
 142
 143   // Callback method used to find unused registers.
 144   // LVSetBef is the live variable set to search for an unused register.
 145   // If it is not specified, the LV set before the current MI is used.
 146   // This is sufficient as long as no new copy instructions are generated
 147   // to copy the free register to memory.
 148   //
 149   int getUnusedUniRegAtMI(RegClass *RC, int RegType,
 150                           const MachineInstr *MI,
 151                           const ValueSet *LVSetBef = 0);
 152
 153   void setRelRegsUsedByThisInst(RegClass *RC, int RegType,
 154                                 const MachineInstr *MI);
 155
 156   int getUniRegNotUsedByThisInst(RegClass *RC, int RegType,
 157                                  const MachineInstr *MI);
 158
 159   void addInterf4PseudoInstr(const MachineInstr *MI);
 160 };
 161
 162 #endif