1 /* Title: PhyRegAlloc.h
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();
33 #ifndef PHY_REG_ALLOC_H
34 #define PHY_REG_ALLOC_H
36 #include "llvm/CodeGen/MachineInstr.h"
37 #include "llvm/CodeGen/RegClass.h"
38 #include "llvm/CodeGen/LiveRangeInfo.h"
39 #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
40 #include "llvm/Analysis/LoopDepth.h"
45 //----------------------------------------------------------------------------
46 // Class AddedInstrns:
47 // When register allocator inserts new instructions in to the existing
48 // instruction stream, it does NOT directly modify the instruction stream.
49 // Rather, it creates an object of AddedInstrns and stick it in the
50 // AddedInstrMap for an existing instruction. This class contains two vectors
51 // to store such instructions added before and after an existing instruction.
52 //----------------------------------------------------------------------------
57 deque<MachineInstr *> InstrnsBefore; // Added insts BEFORE an existing inst
58 deque<MachineInstr *> InstrnsAfter; // Added insts AFTER an existing inst
60 AddedInstrns() : InstrnsBefore(), InstrnsAfter() { }
63 typedef hash_map<const MachineInstr *, AddedInstrns *> AddedInstrMapType;
67 //----------------------------------------------------------------------------
69 // Main class the register allocator. Call allocateRegisters() to allocate
70 // registers for a Method.
71 //----------------------------------------------------------------------------
74 class PhyRegAlloc: public NonCopyable
77 vector<RegClass *> RegClassList ; // vector of register classes
78 const TargetMachine &TM; // target machine
79 const Method* Meth; // name of the method we work on
80 MachineCodeForMethod& mcInfo; // descriptor for method's native code
81 MethodLiveVarInfo *const LVI; // LV information for this method
82 // (already computed for BBs)
83 LiveRangeInfo LRI; // LR info (will be computed)
84 const MachineRegInfo &MRI; // Machine Register information
85 const unsigned NumOfRegClasses; // recorded here for efficiency
88 AddedInstrMapType AddedInstrMap; // to store instrns added in this phase
89 LoopDepthCalculator LoopDepthCalc; // to calculate loop depths
90 ReservedColorListType ResColList; // A set of reserved regs if desired.
95 //------- ------------------ private methods---------------------------------
97 void addInterference(const Value *const Def, const LiveVarSet *const LVSet,
98 const bool isCallInst);
100 void addInterferencesForArgs();
101 void createIGNodeListsAndIGs();
102 void buildInterferenceGraphs();
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();
113 void insertCode4SpilledLR (const LiveRange *LR,
115 const BasicBlock *BB,
116 const unsigned OpNum);
118 inline void constructLiveRanges()
119 { LRI.constructLiveRanges(); }
121 void colorIncomingArgs();
122 void colorCallRetArgs();
123 void updateMachineCode();
125 void printLabel(const Value *const Val);
126 void printMachineCode();
128 friend class UltraSparcRegInfo;
131 int getUsableUniRegAtMI(RegClass *RC, const int RegType,
132 const MachineInstr *MInst,
133 const LiveVarSet *LVSetBef, MachineInstr *MIBef,
134 MachineInstr *MIAft );
136 int getUnusedUniRegAtMI(RegClass *RC, const MachineInstr *MInst,
137 const LiveVarSet *LVSetBef);
139 void setRelRegsUsedByThisInst(RegClass *RC, const MachineInstr *MInst );
140 int getUniRegNotUsedByThisInst(RegClass *RC, const MachineInstr *MInst);
142 void addInterf4PseudoInstr(const MachineInstr *MInst);
147 PhyRegAlloc(Method *const M, const TargetMachine& TM,
148 MethodLiveVarInfo *const Lvi);
152 // main method called for allocating registers
154 void allocateRegisters();