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 FunctionLiveVarInfo LVI(*FunctionI ); // compute LV info
23 TargetMachine &target = ....
26 PhyRegAlloc PRA(*FunctionI, 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 FunctionLiveVarInfo;
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 FunctionLiveVarInfo *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 AddedInstrns AddedInstrAtEntry; // to store instrns added at entry
82 cfg::LoopInfo *LoopDepthCalc; // to calculate loop depths
83 ReservedColorListType ResColList; // A set of reserved regs if desired.
87 PhyRegAlloc(Function *F, const TargetMachine& TM, FunctionLiveVarInfo *Lvi,
88 cfg::LoopInfo *LoopDepthCalc);
91 // main method called for allocating registers
93 void allocateRegisters();
96 // access to register classes by class ID
98 const RegClass* getRegClassByID(unsigned int id) const {
99 return RegClassList[id];
101 RegClass* getRegClassByID(unsigned int id) {
102 return RegClassList[id]; }
109 //------- ------------------ private methods---------------------------------
111 void addInterference(const Value *Def, const ValueSet *LVSet,
114 void addInterferencesForArgs();
115 void createIGNodeListsAndIGs();
116 void buildInterferenceGraphs();
118 void setCallInterferences(const MachineInstr *MInst,
119 const ValueSet *LVSetAft );
121 void move2DelayedInstr(const MachineInstr *OrigMI,
122 const MachineInstr *DelayedMI );
124 void markUnusableSugColors();
125 void allocateStackSpace4SpilledLRs();
127 void insertCode4SpilledLR (const LiveRange *LR,
129 const BasicBlock *BB,
130 const unsigned OpNum);
132 inline void constructLiveRanges() { LRI.constructLiveRanges(); }
134 void colorIncomingArgs();
135 void colorCallRetArgs();
136 void updateMachineCode();
138 void printLabel(const Value *const Val);
139 void printMachineCode();
141 friend class UltraSparcRegInfo;
144 int getUsableUniRegAtMI(RegClass *RC, int RegType,
145 const MachineInstr *MInst,
146 const ValueSet *LVSetBef, MachineInstr *&MIBef,
147 MachineInstr *&MIAft );
149 int getUnusedUniRegAtMI(RegClass *RC, const MachineInstr *MInst,
150 const ValueSet *LVSetBef);
152 void setRelRegsUsedByThisInst(RegClass *RC, const MachineInstr *MInst );
153 int getUniRegNotUsedByThisInst(RegClass *RC, const MachineInstr *MInst);
155 void addInterf4PseudoInstr(const MachineInstr *MInst);