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();
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 std::deque<MachineInstr*> InstrnsBefore;// Added insts BEFORE an existing inst
58 std::deque<MachineInstr*> InstrnsAfter; // Added insts AFTER an existing inst
61 typedef std::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 std::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
86 AddedInstrMapType AddedInstrMap; // to store instrns added in this phase
87 cfg::LoopDepthCalculator LoopDepthCalc; // to calculate loop depths
88 ReservedColorListType ResColList; // A set of reserved regs if desired.
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();
102 void setCallInterferences(const MachineInstr *MInst,
103 const LiveVarSet *const LVSetAft );
105 void move2DelayedInstr(const MachineInstr *OrigMI,
106 const MachineInstr *DelayedMI );
108 void markUnusableSugColors();
109 void allocateStackSpace4SpilledLRs();
111 void insertCode4SpilledLR (const LiveRange *LR,
113 const BasicBlock *BB,
114 const unsigned OpNum);
116 inline void constructLiveRanges() { LRI.constructLiveRanges(); }
118 void colorIncomingArgs();
119 void colorCallRetArgs();
120 void updateMachineCode();
122 void printLabel(const Value *const Val);
123 void printMachineCode();
125 friend class UltraSparcRegInfo;
128 int getUsableUniRegAtMI(RegClass *RC, const int RegType,
129 const MachineInstr *MInst,
130 const LiveVarSet *LVSetBef, MachineInstr *MIBef,
131 MachineInstr *MIAft );
133 int getUnusedUniRegAtMI(RegClass *RC, const MachineInstr *MInst,
134 const LiveVarSet *LVSetBef);
136 void setRelRegsUsedByThisInst(RegClass *RC, const MachineInstr *MInst );
137 int getUniRegNotUsedByThisInst(RegClass *RC, const MachineInstr *MInst);
139 void addInterf4PseudoInstr(const MachineInstr *MInst);
142 PhyRegAlloc(Method *const M, const TargetMachine& TM,
143 MethodLiveVarInfo *const Lvi);
146 // main method called for allocating registers
148 void allocateRegisters();