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 //----------------------------------------------------------------------------
54 std::deque<MachineInstr*> InstrnsBefore;// Added insts BEFORE an existing inst
55 std::deque<MachineInstr*> InstrnsAfter; // Added insts AFTER an existing inst
58 typedef std::hash_map<const MachineInstr *, AddedInstrns *> AddedInstrMapType;
62 //----------------------------------------------------------------------------
64 // Main class the register allocator. Call allocateRegisters() to allocate
65 // registers for a Method.
66 //----------------------------------------------------------------------------
69 class PhyRegAlloc: public NonCopyable {
71 std::vector<RegClass *> RegClassList; // vector of register classes
72 const TargetMachine &TM; // target machine
73 const Method* Meth; // name of the method we work on
74 MachineCodeForMethod &mcInfo; // descriptor for method's native code
75 MethodLiveVarInfo *const LVI; // LV information for this method
76 // (already computed for BBs)
77 LiveRangeInfo LRI; // LR info (will be computed)
78 const MachineRegInfo &MRI; // Machine Register information
79 const unsigned NumOfRegClasses; // recorded here for efficiency
82 AddedInstrMapType AddedInstrMap; // to store instrns added in this phase
83 cfg::LoopInfo *LoopDepthCalc; // to calculate loop depths
84 ReservedColorListType ResColList; // A set of reserved regs if desired.
88 PhyRegAlloc(Method *M, const TargetMachine& TM, MethodLiveVarInfo *Lvi,
89 cfg::LoopInfo *LoopDepthCalc);
92 // main method called for allocating registers
94 void allocateRegisters();
97 // access to register classes by class ID
99 const RegClass* getRegClassByID(unsigned int id) const {
100 return RegClassList[id];
102 RegClass* getRegClassByID(unsigned int id) {
103 return RegClassList[id]; }
110 //------- ------------------ private methods---------------------------------
112 void addInterference(const Value *Def, const ValueSet *LVSet,
115 void addInterferencesForArgs();
116 void createIGNodeListsAndIGs();
117 void buildInterferenceGraphs();
119 void setCallInterferences(const MachineInstr *MInst,
120 const ValueSet *LVSetAft );
122 void move2DelayedInstr(const MachineInstr *OrigMI,
123 const MachineInstr *DelayedMI );
125 void markUnusableSugColors();
126 void allocateStackSpace4SpilledLRs();
128 void insertCode4SpilledLR (const LiveRange *LR,
130 const BasicBlock *BB,
131 const unsigned OpNum);
133 inline void constructLiveRanges() { LRI.constructLiveRanges(); }
135 void colorIncomingArgs();
136 void colorCallRetArgs();
137 void updateMachineCode();
139 void printLabel(const Value *const Val);
140 void printMachineCode();
142 friend class UltraSparcRegInfo;
145 int getUsableUniRegAtMI(RegClass *RC, int RegType,
146 const MachineInstr *MInst,
147 const ValueSet *LVSetBef, MachineInstr *&MIBef,
148 MachineInstr *&MIAft );
150 int getUnusedUniRegAtMI(RegClass *RC, const MachineInstr *MInst,
151 const ValueSet *LVSetBef);
153 void setRelRegsUsedByThisInst(RegClass *RC, const MachineInstr *MInst );
154 int getUniRegNotUsedByThisInst(RegClass *RC, const MachineInstr *MInst);
156 void addInterf4PseudoInstr(const MachineInstr *MInst);