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();
30 #ifndef PHY_REG_ALLOC_H
31 #define PHY_REG_ALLOC_H
33 #include "llvm/CodeGen/RegClass.h"
34 #include "llvm/CodeGen/LiveRangeInfo.h"
35 #include "llvm/Analysis/LoopDepth.h"
37 class MachineCodeForMethod;
39 class MethodLiveVarInfo;
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 //----------------------------------------------------------------------------
54 std::deque<MachineInstr*> InstrnsBefore;// Added insts BEFORE an existing inst
55 std::deque<MachineInstr*> InstrnsAfter; // Added insts AFTER an existing inst
58 typedef std::hash_map<const MachineInstr *, AddedInstrns *> AddedInstrMapType;
62 //----------------------------------------------------------------------------
64 // Main class the register allocator. Call allocateRegisters() to allocate
65 // registers for a Method.
66 //----------------------------------------------------------------------------
69 class PhyRegAlloc: public NonCopyable
72 std::vector<RegClass *> RegClassList; // vector of register classes
73 const TargetMachine &TM; // target machine
74 const Method* Meth; // name of the method we work on
75 MachineCodeForMethod &mcInfo; // descriptor for method's native code
76 MethodLiveVarInfo *const LVI; // LV information for this method
77 // (already computed for BBs)
78 LiveRangeInfo LRI; // LR info (will be computed)
79 const MachineRegInfo &MRI; // Machine Register information
80 const unsigned NumOfRegClasses; // recorded here for efficiency
83 AddedInstrMapType AddedInstrMap; // to store instrns added in this phase
84 cfg::LoopDepthCalculator LoopDepthCalc; // to calculate loop depths
85 ReservedColorListType ResColList; // A set of reserved regs if desired.
90 //------- ------------------ private methods---------------------------------
92 void addInterference(const Value *const Def, const LiveVarSet *const LVSet,
93 const bool isCallInst);
95 void addInterferencesForArgs();
96 void createIGNodeListsAndIGs();
97 void buildInterferenceGraphs();
99 void setCallInterferences(const MachineInstr *MInst,
100 const LiveVarSet *const LVSetAft );
102 void move2DelayedInstr(const MachineInstr *OrigMI,
103 const MachineInstr *DelayedMI );
105 void markUnusableSugColors();
106 void allocateStackSpace4SpilledLRs();
108 void insertCode4SpilledLR (const LiveRange *LR,
110 const BasicBlock *BB,
111 const unsigned OpNum);
113 inline void constructLiveRanges() { LRI.constructLiveRanges(); }
115 void colorIncomingArgs();
116 void colorCallRetArgs();
117 void updateMachineCode();
119 void printLabel(const Value *const Val);
120 void printMachineCode();
122 friend class UltraSparcRegInfo;
125 int getUsableUniRegAtMI(RegClass *RC, const int RegType,
126 const MachineInstr *MInst,
127 const LiveVarSet *LVSetBef, MachineInstr *MIBef,
128 MachineInstr *MIAft );
130 int getUnusedUniRegAtMI(RegClass *RC, const MachineInstr *MInst,
131 const LiveVarSet *LVSetBef);
133 void setRelRegsUsedByThisInst(RegClass *RC, const MachineInstr *MInst );
134 int getUniRegNotUsedByThisInst(RegClass *RC, const MachineInstr *MInst);
136 void addInterf4PseudoInstr(const MachineInstr *MInst);
139 PhyRegAlloc(Method *const M, const TargetMachine& TM,
140 MethodLiveVarInfo *const Lvi);
143 // main method called for allocating registers
145 void allocateRegisters();