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"
42 class MachineCodeForMethod;
44 //----------------------------------------------------------------------------
45 // Class AddedInstrns:
46 // When register allocator inserts new instructions in to the existing
47 // instruction stream, it does NOT directly modify the instruction stream.
48 // Rather, it creates an object of AddedInstrns and stick it in the
49 // AddedInstrMap for an existing instruction. This class contains two vectors
50 // to store such instructions added before and after an existing instruction.
51 //----------------------------------------------------------------------------
56 std::deque<MachineInstr*> InstrnsBefore;// Added insts BEFORE an existing inst
57 std::deque<MachineInstr*> InstrnsAfter; // Added insts AFTER an existing inst
60 typedef std::hash_map<const MachineInstr *, AddedInstrns *> AddedInstrMapType;
64 //----------------------------------------------------------------------------
66 // Main class the register allocator. Call allocateRegisters() to allocate
67 // registers for a Method.
68 //----------------------------------------------------------------------------
71 class PhyRegAlloc: public NonCopyable
74 std::vector<RegClass *> RegClassList; // vector of register classes
75 const TargetMachine &TM; // target machine
76 const Method* Meth; // name of the method we work on
77 MachineCodeForMethod &mcInfo; // descriptor for method's native code
78 MethodLiveVarInfo *const LVI; // LV information for this method
79 // (already computed for BBs)
80 LiveRangeInfo LRI; // LR info (will be computed)
81 const MachineRegInfo &MRI; // Machine Register information
82 const unsigned NumOfRegClasses; // recorded here for efficiency
85 AddedInstrMapType AddedInstrMap; // to store instrns added in this phase
86 cfg::LoopDepthCalculator LoopDepthCalc; // to calculate loop depths
87 ReservedColorListType ResColList; // A set of reserved regs if desired.
92 //------- ------------------ private methods---------------------------------
94 void addInterference(const Value *const Def, const LiveVarSet *const LVSet,
95 const bool isCallInst);
97 void addInterferencesForArgs();
98 void createIGNodeListsAndIGs();
99 void buildInterferenceGraphs();
101 void setCallInterferences(const MachineInstr *MInst,
102 const LiveVarSet *const LVSetAft );
104 void move2DelayedInstr(const MachineInstr *OrigMI,
105 const MachineInstr *DelayedMI );
107 void markUnusableSugColors();
108 void allocateStackSpace4SpilledLRs();
110 void insertCode4SpilledLR (const LiveRange *LR,
112 const BasicBlock *BB,
113 const unsigned OpNum);
115 inline void constructLiveRanges() { 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 getUsableUniRegAtMI(RegClass *RC, const int RegType,
128 const MachineInstr *MInst,
129 const LiveVarSet *LVSetBef, MachineInstr *MIBef,
130 MachineInstr *MIAft );
132 int getUnusedUniRegAtMI(RegClass *RC, const MachineInstr *MInst,
133 const LiveVarSet *LVSetBef);
135 void setRelRegsUsedByThisInst(RegClass *RC, const MachineInstr *MInst );
136 int getUniRegNotUsedByThisInst(RegClass *RC, const MachineInstr *MInst);
138 void addInterf4PseudoInstr(const MachineInstr *MInst);
141 PhyRegAlloc(Method *const M, const TargetMachine& TM,
142 MethodLiveVarInfo *const Lvi);
145 // main method called for allocating registers
147 void allocateRegisters();