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 <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 {
  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   PhyRegAlloc(const PhyRegAlloc&);     // DO NOT IMPLEMENT
  76   void operator=(const PhyRegAlloc&);  // DO NOT IMPLEMENT
  77 public:
  78   PhyRegAlloc(Function *F, const TargetMachine& TM, FunctionLiveVarInfo *Lvi,
  79               LoopInfo *LoopDepthCalc);
  80   ~PhyRegAlloc();
  81
  82   // main method called for allocating registers
  83   //
  84   void allocateRegisters();
  85
  86   // access to register classes by class ID
  87   //
  88   const RegClass* getRegClassByID(unsigned id) const {
  89     return RegClassList[id];
  90   }
  91   RegClass* getRegClassByID(unsigned id) {
  92     return RegClassList[id];
  93   }
  94
  95 private:
  96   void addInterference(const Value *Def, const ValueSet *LVSet,
  97                        bool isCallInst);
  98
  99   void addInterferencesForArgs();
 100   void createIGNodeListsAndIGs();
 101   void buildInterferenceGraphs();
 102
 103   void setCallInterferences(const MachineInstr *MI,
 104                             const ValueSet *LVSetAft);
 105
 106   void move2DelayedInstr(const MachineInstr *OrigMI,
 107                          const MachineInstr *DelayedMI);
 108
 109   void markUnusableSugColors();
 110   void allocateStackSpace4SpilledLRs();
 111
 112   void insertCode4SpilledLR(const LiveRange *LR,
 113                             MachineBasicBlock::iterator& MII,
 114                             MachineBasicBlock &MBB, 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 *Val);
 132   void printMachineCode();
 133
 134
 135   int getUsableUniRegAtMI(int RegType, const ValueSet *LVSetBef,
 136                           MachineInstr *MI,
 137                           std::vector<MachineInstr*>& MIBef,
 138                           std::vector<MachineInstr*>& MIAft);
 139
 140   // Callback method used to find unused registers.
 141   // LVSetBef is the live variable set to search for an unused register.
 142   // If it is not specified, the LV set before the current MI is used.
 143   // This is sufficient as long as no new copy instructions are generated
 144   // to copy the free register to memory.
 145   //
 146   int getUnusedUniRegAtMI(RegClass *RC, int RegType,
 147                           const MachineInstr *MI,
 148                           const ValueSet *LVSetBef = 0);
 149
 150   void setRelRegsUsedByThisInst(RegClass *RC, int RegType,
 151                                 const MachineInstr *MI);
 152
 153   int getUniRegNotUsedByThisInst(RegClass *RC, int RegType,
 154                                  const MachineInstr *MI);
 155
 156   void addInterf4PseudoInstr(const MachineInstr *MI);
 157 };
 158
 159
 160 #endif
 161