1 /* Title: PhyRegAlloc.h
2 Author: Ruchira Sasanka
4 Purpose: This is the main entry point for register allocation.
8 * RegisterClasses: Each RegClass accepts a
9 MachineRegClass which contains machine specific info about that register
10 class. The code in the RegClass is machine independent and they use
11 access functions in the MachineRegClass object passed into it to get
12 machine specific info.
14 * Machine dependent work: All parts of the register coloring algorithm
15 except coloring of an individual node are machine independent.
17 Register allocation must be done as:
19 static const MachineRegInfo MRI = MachineRegInfo(); // machine reg info
21 MethodLiveVarInfo LVI(*MethodI ); // compute LV info
24 PhyRegAlloc PRA(*MethodI, &MRI, &LVI); // allocate regs
25 PRA.allocateRegisters();
28 All values in a live range will be of the same physical reg class.
32 #ifndef PHY_REG_ALLOC_H
33 #define PHY_REG_ALLOC_H
35 #include "llvm/CodeGen/MachineInstr.h"
36 #include "llvm/CodeGen/RegClass.h"
37 #include "llvm/CodeGen/LiveRangeInfo.h"
38 #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
43 //----------------------------------------------------------------------------
44 // Class AddedInstrns:
45 // When register allocator inserts new instructions in to the existing
46 // instruction stream, it does NOT directly modify the instruction stream.
47 // Rather, it creates an object of AddedInstrns and stick it in the
48 // AddedInstrMap for an existing instruction. This class contains two vectors
49 // to store such instructions added before and after an existing instruction.
50 //----------------------------------------------------------------------------
55 deque<MachineInstr *> InstrnsBefore; // Added insts BEFORE an existing inst
56 deque<MachineInstr *> InstrnsAfter; // Added insts AFTER an existing inst
58 AddedInstrns() : InstrnsBefore(), InstrnsAfter() { }
61 typedef hash_map<const MachineInstr *, AddedInstrns *> AddedInstrMapType;
65 //----------------------------------------------------------------------------
66 // Class RegStackOffsets:
67 // This class is responsible for managing stack frame of the method for
68 // register allocation.
70 //----------------------------------------------------------------------------
72 class RegStackOffsets {
75 int curSpilledVarOff; // cur pos of spilled LRs
76 int curNewTmpPosOffset; // cur pos of tmp values on stack
77 bool isTmpRegionUsable; // can we call getNewTmpPosOffFromFP
79 const int SizeOfStackItem; // size of an item on stack
80 const int StackSpillStartFromFP; // start position of spill region
81 int StartOfTmpRegion; // start of the tmp var region
87 RegStackOffsets(int SEnSize=8, int StartSpill=176 ) :
88 SizeOfStackItem(SEnSize), StackSpillStartFromFP(StartSpill) {
90 curSpilledVarOff = StartSpill;
91 isTmpRegionUsable = false;
95 int getNewSpillOffFromFP() {
96 int tmp = curSpilledVarOff;
97 curSpilledVarOff += SizeOfStackItem;
98 return tmp; // **TODO: Is sending un-incremented value correct?
102 // The following method must be called only after allocating space
103 // for spilled LRs and calling setEndOfSpillRegion()
104 int getNewTmpPosOffFromFP() {
105 assert( isTmpRegionUsable && "Spill region still open");
106 int tmp = curNewTmpPosOffset;
107 curNewTmpPosOffset += SizeOfStackItem;
108 return tmp; //**TODO: Is sending un-incremented val correct?
112 // This method is called when we have allocated space for all spilled
113 // LRs. The tmp region can be used only after a call to this method.
115 void setEndOfSpillRegion() {
116 assert(( ! isTmpRegionUsable) && "setEndOfSpillRegion called again");
117 isTmpRegionUsable = true;
118 StartOfTmpRegion = curSpilledVarOff;
122 // called when temporary values allocated on stack are no longer needed
124 curNewTmpPosOffset = StartOfTmpRegion;
132 //----------------------------------------------------------------------------
133 // class PhyRegAlloc:
134 // Main class the register allocator. Call allocateRegisters() to allocate
135 // registers for a Method.
136 //----------------------------------------------------------------------------
142 vector<RegClass *> RegClassList ; // vector of register classes
143 const Method *const Meth; // name of the method we work on
144 const TargetMachine &TM; // target machine
145 MethodLiveVarInfo *const LVI; // LV information for this method
146 // (already computed for BBs)
147 LiveRangeInfo LRI; // LR info (will be computed)
148 const MachineRegInfo &MRI; // Machine Register information
149 const unsigned NumOfRegClasses; // recorded here for efficiency
151 //vector<const Instruction *> CallInstrList; // a list of all call instrs
152 //vector<const Instruction *> RetInstrList; // a list of all return instrs
155 AddedInstrMapType AddedInstrMap; // to store instrns added in this phase
157 RegStackOffsets StackOffsets;
159 //vector<const MachineInstr *> PhiInstList; // a list of all phi instrs
161 //------- private methods ---------------------------------------------------
163 void addInterference(const Value *const Def, const LiveVarSet *const LVSet,
164 const bool isCallInst);
166 void addInterferencesForArgs();
167 void createIGNodeListsAndIGs();
168 void buildInterferenceGraphs();
169 //void insertCallerSavingCode(const MachineInstr *MInst,
170 // const BasicBlock *BB );
172 void setCallInterferences(const MachineInstr *MInst,
173 const LiveVarSet *const LVSetAft );
175 void move2DelayedInstr(const MachineInstr *OrigMI,
176 const MachineInstr *DelayedMI );
178 void markUnusableSugColors();
179 void allocateStackSpace4SpilledLRs();
181 RegStackOffsets & getStackOffsets() {
186 inline void constructLiveRanges()
187 { LRI.constructLiveRanges(); }
189 void colorIncomingArgs();
190 void colorCallRetArgs();
191 void updateMachineCode();
193 void printLabel(const Value *const Val);
194 void printMachineCode();
196 friend class UltraSparcRegInfo;
199 int getUsableRegAtMI(RegClass *RC, const int RegType, const MachineInstr *MInst,
200 const LiveVarSet *LVSetBef, MachineInstr *MIBef,
201 MachineInstr *MIAft );
203 int getUnusedRegAtMI(RegClass *RC, const MachineInstr *MInst,
204 const LiveVarSet *LVSetBef);
206 void setRegsUsedByThisInst(RegClass *RC, const MachineInstr *MInst );
207 int getRegNotUsedByThisInst(RegClass *RC, const MachineInstr *MInst);
211 void PhyRegAlloc::insertPhiEleminateInstrns();
215 PhyRegAlloc(const Method *const M, const TargetMachine& TM,
216 MethodLiveVarInfo *const Lvi);
218 void allocateRegisters(); // main method called for allocatin
229 * Insert IntCCReg checking code to insertCallerSaving
230 * add methods like cpCCReg2Mem & cpMem2CCReg (these will accept an array
231 and push back or push_front the instr according to PUSH_BACK, PUSH_FRONT