1 /* Title: PhyRegAlloc.h -*- C++ -*-
2 Author: Ruchira Sasanka
4 Purpose: This is the main entry point for register allocation.
9 * RegisterClasses: Each RegClass accepts a
10 MachineRegClass 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 MachineRegClass object passed into it to get
13 machine specific info.
15 * Machine dependent work: All parts of the register coloring algorithm
16 except coloring of an individual node are machine independent.
18 Register allocation must be done as:
20 MethodLiveVarInfo LVI(*MethodI ); // compute LV info
23 TargetMachine &target = ....
26 PhyRegAlloc PRA(*MethodI, target, &LVI); // allocate regs
27 PRA.allocateRegisters();
30 #ifndef PHY_REG_ALLOC_H
31 #define PHY_REG_ALLOC_H
33 #include "llvm/CodeGen/RegClass.h"
34 #include "llvm/CodeGen/LiveRangeInfo.h"
36 class MachineCodeForMethod;
38 class MethodLiveVarInfo;
40 namespace cfg { class LoopInfo; }
42 //----------------------------------------------------------------------------
43 // Class AddedInstrns:
44 // When register allocator inserts new instructions in to the existing
45 // instruction stream, it does NOT directly modify the instruction stream.
46 // Rather, it creates an object of AddedInstrns and stick it in the
47 // AddedInstrMap for an existing instruction. This class contains two vectors
48 // to store such instructions added before and after an existing instruction.
49 //----------------------------------------------------------------------------
52 std::deque<MachineInstr*> InstrnsBefore;// Added insts BEFORE an existing inst
53 std::deque<MachineInstr*> InstrnsAfter; // Added insts AFTER an existing inst
56 typedef std::map<const MachineInstr *, AddedInstrns> AddedInstrMapType;
60 //----------------------------------------------------------------------------
62 // Main class the register allocator. Call allocateRegisters() to allocate
63 // registers for a Function.
64 //----------------------------------------------------------------------------
67 class PhyRegAlloc: public NonCopyable {
69 std::vector<RegClass *> RegClassList; // vector of register classes
70 const TargetMachine &TM; // target machine
71 const Function *Meth; // name of the function we work on
72 MachineCodeForMethod &mcInfo; // descriptor for method's native code
73 MethodLiveVarInfo *const LVI; // LV information for this method
74 // (already computed for BBs)
75 LiveRangeInfo LRI; // LR info (will be computed)
76 const MachineRegInfo &MRI; // Machine Register information
77 const unsigned NumOfRegClasses; // recorded here for efficiency
80 AddedInstrMapType AddedInstrMap; // to store instrns added in this phase
81 cfg::LoopInfo *LoopDepthCalc; // to calculate loop depths
82 ReservedColorListType ResColList; // A set of reserved regs if desired.
86 PhyRegAlloc(Function *F, const TargetMachine& TM, MethodLiveVarInfo *Lvi,
87 cfg::LoopInfo *LoopDepthCalc);
90 // main method called for allocating registers
92 void allocateRegisters();
95 // access to register classes by class ID
97 const RegClass* getRegClassByID(unsigned int id) const {
98 return RegClassList[id];
100 RegClass* getRegClassByID(unsigned int id) {
101 return RegClassList[id]; }
108 //------- ------------------ private methods---------------------------------
110 void addInterference(const Value *Def, const ValueSet *LVSet,
113 void addInterferencesForArgs();
114 void createIGNodeListsAndIGs();
115 void buildInterferenceGraphs();
117 void setCallInterferences(const MachineInstr *MInst,
118 const ValueSet *LVSetAft );
120 void move2DelayedInstr(const MachineInstr *OrigMI,
121 const MachineInstr *DelayedMI );
123 void markUnusableSugColors();
124 void allocateStackSpace4SpilledLRs();
126 void insertCode4SpilledLR (const LiveRange *LR,
128 const BasicBlock *BB,
129 const unsigned OpNum);
131 inline void constructLiveRanges() { LRI.constructLiveRanges(); }
133 void colorIncomingArgs();
134 void colorCallRetArgs();
135 void updateMachineCode();
137 void printLabel(const Value *const Val);
138 void printMachineCode();
140 friend class UltraSparcRegInfo;
143 int getUsableUniRegAtMI(RegClass *RC, int RegType,
144 const MachineInstr *MInst,
145 const ValueSet *LVSetBef, MachineInstr *&MIBef,
146 MachineInstr *&MIAft );
148 int getUnusedUniRegAtMI(RegClass *RC, const MachineInstr *MInst,
149 const ValueSet *LVSetBef);
151 void setRelRegsUsedByThisInst(RegClass *RC, const MachineInstr *MInst );
152 int getUniRegNotUsedByThisInst(RegClass *RC, const MachineInstr *MInst);
154 void addInterf4PseudoInstr(const MachineInstr *MInst);