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 //----------------------------------------------------------------------------
67 // Main class the register allocator. Call allocateRegisters() to allocate
68 // registers for a Method.
69 //----------------------------------------------------------------------------
72 class PhyRegAlloc: public NonCopyable
75 vector<RegClass *> RegClassList ; // vector of register classes
76 const TargetMachine &TM; // target machine
77 const Method* Meth; // name of the method we work on
78 MachineCodeForMethod& mcInfo; // descriptor for method's native code
79 MethodLiveVarInfo *const LVI; // LV information for this method
80 // (already computed for BBs)
81 LiveRangeInfo LRI; // LR info (will be computed)
82 const MachineRegInfo &MRI; // Machine Register information
83 const unsigned NumOfRegClasses; // recorded here for efficiency
85 //vector<const Instruction *> CallInstrList; // a list of all call instrs
86 //vector<const Instruction *> RetInstrList; // a list of all return instrs
89 AddedInstrMapType AddedInstrMap; // to store instrns added in this phase
91 //vector<const MachineInstr *> PhiInstList; // a list of all phi instrs
93 //------- private methods ---------------------------------------------------
95 void addInterference(const Value *const Def, const LiveVarSet *const LVSet,
96 const bool isCallInst);
98 void addInterferencesForArgs();
99 void createIGNodeListsAndIGs();
100 void buildInterferenceGraphs();
101 //void insertCallerSavingCode(const MachineInstr *MInst,
102 // const BasicBlock *BB );
104 void setCallInterferences(const MachineInstr *MInst,
105 const LiveVarSet *const LVSetAft );
107 void move2DelayedInstr(const MachineInstr *OrigMI,
108 const MachineInstr *DelayedMI );
110 void markUnusableSugColors();
111 void allocateStackSpace4SpilledLRs();
114 inline void constructLiveRanges()
115 { LRI.constructLiveRanges(); }
117 void colorIncomingArgs();
118 void colorCallRetArgs();
119 void updateMachineCode();
121 void printLabel(const Value *const Val);
122 void printMachineCode();
124 friend class UltraSparcRegInfo;
127 int getUsableRegAtMI(RegClass *RC, const int RegType, const MachineInstr *MInst,
128 const LiveVarSet *LVSetBef, MachineInstr *MIBef,
129 MachineInstr *MIAft );
131 int getUnusedRegAtMI(RegClass *RC, const MachineInstr *MInst,
132 const LiveVarSet *LVSetBef);
134 void setRegsUsedByThisInst(RegClass *RC, const MachineInstr *MInst );
135 int getRegNotUsedByThisInst(RegClass *RC, const MachineInstr *MInst);
139 void PhyRegAlloc::insertPhiEleminateInstrns();
143 PhyRegAlloc(Method *const M, const TargetMachine& TM,
144 MethodLiveVarInfo *const Lvi);
146 void allocateRegisters(); // main method called for allocatin
157 * Insert IntCCReg checking code to insertCallerSaving
158 * add methods like cpCCReg2Mem & cpMem2CCReg (these will accept an array
159 and push back or push_front the instr according to PUSH_BACK, PUSH_FRONT