lib/Target/SparcV9/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 PHYREGALLOC_H
  20 #define PHYREGALLOC_H
  21
  22 #include "LiveRangeInfo.h"
  23 #include "llvm/Pass.h"
  24 #include "llvm/CodeGen/MachineBasicBlock.h"
  25 #include "llvm/Target/TargetRegInfo.h"
  26 #include "llvm/Target/TargetMachine.h"
  27 #include <map>
  28
  29 class MachineFunction;
  30 class FunctionLiveVarInfo;
  31 class MachineInstr;
  32 class LoopInfo;
  33 class RegClass;
  34
  35 //----------------------------------------------------------------------------
  36 // Class AddedInstrns:
  37 // When register allocator inserts new instructions in to the existing
  38 // instruction stream, it does NOT directly modify the instruction stream.
  39 // Rather, it creates an object of AddedInstrns and stick it in the
  40 // AddedInstrMap for an existing instruction. This class contains two vectors
  41 // to store such instructions added before and after an existing instruction.
  42 //----------------------------------------------------------------------------
  43
  44 struct AddedInstrns {
  45   std::vector<MachineInstr*> InstrnsBefore;//Insts added BEFORE an existing inst
  46   std::vector<MachineInstr*> InstrnsAfter; //Insts added AFTER an existing inst
  47   inline void clear () { InstrnsBefore.clear (); InstrnsAfter.clear (); }
  48 };
  49
  50 //----------------------------------------------------------------------------
  51 // class PhyRegAlloc:
  52 // Main class the register allocator. Call runOnFunction() to allocate
  53 // registers for a Function.
  54 //----------------------------------------------------------------------------
  55
  56 class PhyRegAlloc : public FunctionPass {
  57   std::vector<RegClass *> RegClassList; // vector of register classes
  58   const TargetMachine &TM;              // target machine
  59   const Function *Fn;                   // name of the function we work on
  60   MachineFunction *MF;                  // descriptor for method's native code
  61   FunctionLiveVarInfo *LVI;             // LV information for this method
  62                                         // (already computed for BBs)
  63   LiveRangeInfo *LRI;                   // LR info  (will be computed)
  64   const TargetRegInfo &MRI;             // Machine Register information
  65   const unsigned NumOfRegClasses;       // recorded here for efficiency
  66
  67   // Map to indicate whether operands of each MachineInstr have been
  68   // updated according to their assigned colors.  This is only used in
  69   // assertion checking (debug builds).
  70   std::map<const MachineInstr *, bool> OperandsColoredMap;
  71
  72   // AddedInstrMap - Used to store instrns added in this phase
  73   std::map<const MachineInstr *, AddedInstrns> AddedInstrMap;
  74
  75   // ScratchRegsUsed - Contains scratch register uses for a particular MI.
  76   typedef std::multimap<const MachineInstr*, int> ScratchRegsUsedTy;
  77   ScratchRegsUsedTy ScratchRegsUsed;
  78
  79   AddedInstrns AddedInstrAtEntry;       // to store instrns added at entry
  80   const LoopInfo *LoopDepthCalc;        // to calculate loop depths
  81
  82   PhyRegAlloc(const PhyRegAlloc&);     // DO NOT IMPLEMENT
  83   void operator=(const PhyRegAlloc&);  // DO NOT IMPLEMENT
  84 public:
  85   inline PhyRegAlloc (const TargetMachine &TM_) :
  86     TM (TM_), MRI (TM.getRegInfo ()),
  87     NumOfRegClasses (MRI.getNumOfRegClasses ()) { }
  88   virtual ~PhyRegAlloc() { }
  89
  90   /// runOnFunction - Main method called for allocating registers.
  91   ///
  92   virtual bool runOnFunction (Function &F);
  93
  94   virtual void getAnalysisUsage (AnalysisUsage &AU) const {
  95     AU.addRequired<LoopInfo> ();
  96     AU.addRequired<FunctionLiveVarInfo> ();
  97   }
  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
 117   void setCallInterferences(const MachineInstr *MI,
 118                             const ValueSet *LVSetAft);
 119
 120   void move2DelayedInstr(const MachineInstr *OrigMI,
 121                          const MachineInstr *DelayedMI);
 122
 123   void markUnusableSugColors();
 124   void allocateStackSpace4SpilledLRs();
 125
 126   void insertCode4SpilledLR(const LiveRange *LR,
 127                             MachineBasicBlock::iterator& MII,
 128                             MachineBasicBlock &MBB, unsigned OpNum);
 129
 130   // Method for inserting caller saving code. The caller must save all the
 131   // volatile registers live across a call.
 132   void insertCallerSavingCode(std::vector<MachineInstr*>& instrnsBefore,
 133                               std::vector<MachineInstr*>& instrnsAfter,
 134                               MachineInstr *CallMI,
 135                               const BasicBlock *BB);
 136
 137   void colorIncomingArgs();
 138   void colorCallRetArgs();
 139   void updateMachineCode();
 140   void updateInstruction(MachineBasicBlock::iterator& MII,
 141                          MachineBasicBlock &MBB);
 142
 143   int getUsableUniRegAtMI(int RegType, const ValueSet *LVSetBef,
 144                           MachineInstr *MI,
 145                           std::vector<MachineInstr*>& MIBef,
 146                           std::vector<MachineInstr*>& MIAft);
 147
 148   // Callback method used to find unused registers.
 149   // LVSetBef is the live variable set to search for an unused register.
 150   // If it is not specified, the LV set before the current MI is used.
 151   // This is sufficient as long as no new copy instructions are generated
 152   // to copy the free register to memory.
 153   //
 154   int getUnusedUniRegAtMI(RegClass *RC, int RegType,
 155                           const MachineInstr *MI,
 156                           const ValueSet *LVSetBef = 0);
 157
 158   void setRelRegsUsedByThisInst(RegClass *RC, int RegType,
 159                                 const MachineInstr *MI);
 160
 161   int getUniRegNotUsedByThisInst(RegClass *RC, int RegType,
 162                                  const MachineInstr *MI);
 163
 164   void addInterf4PseudoInstr(const MachineInstr *MI);
 165 };
 166
 167 #endif