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 PHY_REG_ALLOC_H
  20 #define PHY_REG_ALLOC_H
  21
  22 #include "llvm/CodeGen/LiveRangeInfo.h"
  23 #include "llvm/CodeGen/MachineBasicBlock.h"
  24 #include "Support/NonCopyable.h"
  25 #include <map>
  26
  27 class MachineFunction;
  28 class TargetRegInfo;
  29 class FunctionLiveVarInfo;
  30 class MachineInstr;
  31 class LoopInfo;
  32 class RegClass;
  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 };
  47
  48 //----------------------------------------------------------------------------
  49 // class PhyRegAlloc:
  50 // Main class the register allocator. Call allocateRegisters() to allocate
  51 // registers for a Function.
  52 //----------------------------------------------------------------------------
  53
  54 class PhyRegAlloc : public NonCopyable {
  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 *const 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 updated
  66   // according to their assigned colors.  This is primarily for debugging and
  67   // could be removed in the long run.
  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   AddedInstrns AddedInstrAtEntry;       // to store instrns added at entry
  74   LoopInfo *LoopDepthCalc;              // to calculate loop depths
  75
  76 public:
  77   PhyRegAlloc(Function *F, const TargetMachine& TM, FunctionLiveVarInfo *Lvi,
  78               LoopInfo *LoopDepthCalc);
  79   ~PhyRegAlloc();
  80
  81   // main method called for allocating registers
  82   //
  83   void allocateRegisters();
  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                                  MachineBasicBlock::iterator& MII,
 113                                  MachineBasicBlock &MBB,
 114                                  const unsigned OpNum);
 115
 116   // Method for inserting caller saving code. The caller must save all the
 117   // volatile registers live across a call.
 118   void insertCallerSavingCode(std::vector<MachineInstr*>& instrnsBefore,
 119                               std::vector<MachineInstr*>& instrnsAfter,
 120                               MachineInstr *CallMI,
 121                               const BasicBlock *BB);
 122
 123   inline void constructLiveRanges() { LRI.constructLiveRanges(); }
 124
 125   void colorIncomingArgs();
 126   void colorCallRetArgs();
 127   void updateMachineCode();
 128   void updateInstruction(MachineBasicBlock::iterator& MII,
 129                          MachineBasicBlock &MBB);
 130
 131   void printLabel(const Value *const Val);
 132   void printMachineCode();
 133
 134
 135   int getUsableUniRegAtMI(int RegType,
 136                           const ValueSet *LVSetBef,
 137                           MachineInstr *MInst,
 138                           std::vector<MachineInstr*>& MIBef,
 139                           std::vector<MachineInstr*>& MIAft);
 140
 141   // Callback method used to find unused registers.
 142   // LVSetBef is the live variable set to search for an unused register.
 143   // If it is not specified, the LV set before the current MInst is used.
 144   // This is sufficient as long as no new copy instructions are generated
 145   // to copy the free register to memory.
 146   //
 147   int getUnusedUniRegAtMI(RegClass *RC, const int RegType,
 148                           const MachineInstr *MInst,
 149                           const ValueSet *LVSetBef = 0);
 150
 151   void setRelRegsUsedByThisInst(RegClass *RC, const int RegType,
 152                                 const MachineInstr *MInst );
 153
 154   int getUniRegNotUsedByThisInst(RegClass *RC, const int RegType,
 155                                  const MachineInstr *MInst);
 156
 157   void addInterf4PseudoInstr(const MachineInstr *MInst);
 158 };
 159
 160
 161 #endif
 162