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   // ScratchRegsUsed - Contains scratch register uses for a particular MI.
  73   typedef std::multimap<const MachineInstr*, int> ScratchRegsUsedTy;
  74   ScratchRegsUsedTy ScratchRegsUsed;
  75
  76   AddedInstrns AddedInstrAtEntry;       // to store instrns added at entry
  77   LoopInfo *LoopDepthCalc;              // to calculate loop depths
  78
  79   PhyRegAlloc(const PhyRegAlloc&);     // DO NOT IMPLEMENT
  80   void operator=(const PhyRegAlloc&);  // DO NOT IMPLEMENT
  81 public:
  82   PhyRegAlloc(Function *F, const TargetMachine& TM, FunctionLiveVarInfo *Lvi,
  83               LoopInfo *LoopDepthCalc);
  84   ~PhyRegAlloc();
  85
  86   // main method called for allocating registers
  87   //
  88   void allocateRegisters();
  89
  90   // access to register classes by class ID
  91   //
  92   const RegClass* getRegClassByID(unsigned id) const {
  93     return RegClassList[id];
  94   }
  95   RegClass* getRegClassByID(unsigned id) {
  96     return RegClassList[id];
  97   }
  98
  99 private:
 100   void addInterference(const Value *Def, const ValueSet *LVSet,
 101                        bool isCallInst);
 102
 103   void addInterferencesForArgs();
 104   void createIGNodeListsAndIGs();
 105   void buildInterferenceGraphs();
 106
 107   void setCallInterferences(const MachineInstr *MI,
 108                             const ValueSet *LVSetAft);
 109
 110   void move2DelayedInstr(const MachineInstr *OrigMI,
 111                          const MachineInstr *DelayedMI);
 112
 113   void markUnusableSugColors();
 114   void allocateStackSpace4SpilledLRs();
 115
 116   void insertCode4SpilledLR(const LiveRange *LR,
 117                             MachineBasicBlock::iterator& MII,
 118                             MachineBasicBlock &MBB, unsigned OpNum);
 119
 120   // Method for inserting caller saving code. The caller must save all the
 121   // volatile registers live across a call.
 122   void insertCallerSavingCode(std::vector<MachineInstr*>& instrnsBefore,
 123                               std::vector<MachineInstr*>& instrnsAfter,
 124                               MachineInstr *CallMI,
 125                               const BasicBlock *BB);
 126
 127   inline void constructLiveRanges() { LRI.constructLiveRanges(); }
 128
 129   void colorIncomingArgs();
 130   void colorCallRetArgs();
 131   void updateMachineCode();
 132   void updateInstruction(MachineBasicBlock::iterator& MII,
 133                          MachineBasicBlock &MBB);
 134
 135   void printLabel(const Value *Val);
 136   void printMachineCode();
 137
 138
 139   int getUsableUniRegAtMI(int RegType, const ValueSet *LVSetBef,
 140                           MachineInstr *MI,
 141                           std::vector<MachineInstr*>& MIBef,
 142                           std::vector<MachineInstr*>& MIAft);
 143
 144   // Callback method used to find unused registers.
 145   // LVSetBef is the live variable set to search for an unused register.
 146   // If it is not specified, the LV set before the current MI is used.
 147   // This is sufficient as long as no new copy instructions are generated
 148   // to copy the free register to memory.
 149   //
 150   int getUnusedUniRegAtMI(RegClass *RC, int RegType,
 151                           const MachineInstr *MI,
 152                           const ValueSet *LVSetBef = 0);
 153
 154   void setRelRegsUsedByThisInst(RegClass *RC, int RegType,
 155                                 const MachineInstr *MI);
 156
 157   int getUniRegNotUsedByThisInst(RegClass *RC, int RegType,
 158                                  const MachineInstr *MI);
 159
 160   void addInterf4PseudoInstr(const MachineInstr *MI);
 161 };
 162
 163
 164 #endif
 165