1 //===-- PhyRegAlloc.h - Graph Coloring Register Allocator -------*- c++ -*-===//
3 // This is the main entry point for register allocation.
6 // * RegisterClasses: Each RegClass accepts a
7 // TargetRegClass which contains machine specific info about that register
8 // class. The code in the RegClass is machine independent and they use
9 // access functions in the TargetRegClass object passed into it to get
10 // machine specific info.
12 // * Machine dependent work: All parts of the register coloring algorithm
13 // except coloring of an individual node are machine independent.
15 //===----------------------------------------------------------------------===//
20 #include "LiveRangeInfo.h"
21 #include "llvm/Pass.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/Target/TargetRegInfo.h"
24 #include "llvm/Target/TargetMachine.h"
27 class MachineFunction;
28 class FunctionLiveVarInfo;
34 //----------------------------------------------------------------------------
35 // Class AddedInstrns:
36 // When register allocator inserts new instructions in to the existing
37 // instruction stream, it does NOT directly modify the instruction stream.
38 // Rather, it creates an object of AddedInstrns and stick it in the
39 // AddedInstrMap for an existing instruction. This class contains two vectors
40 // to store such instructions added before and after an existing instruction.
41 //----------------------------------------------------------------------------
44 std::vector<MachineInstr*> InstrnsBefore;//Insts added BEFORE an existing inst
45 std::vector<MachineInstr*> InstrnsAfter; //Insts added AFTER an existing inst
46 inline void clear () { InstrnsBefore.clear (); InstrnsAfter.clear (); }
49 //----------------------------------------------------------------------------
51 // Main class the register allocator. Call runOnFunction() to allocate
52 // registers for a Function.
53 //----------------------------------------------------------------------------
55 class PhyRegAlloc : public FunctionPass {
56 std::vector<RegClass *> RegClassList; // vector of register classes
57 const TargetMachine &TM; // target machine
58 const Function *Fn; // name of the function we work on
59 MachineFunction *MF; // descriptor for method's native code
60 FunctionLiveVarInfo *LVI; // LV information for this method
61 // (already computed for BBs)
62 LiveRangeInfo *LRI; // LR info (will be computed)
63 const TargetRegInfo &MRI; // Machine Register information
64 const unsigned NumOfRegClasses; // recorded here for efficiency
66 // Map to indicate whether operands of each MachineInstr have been
67 // updated according to their assigned colors. This is only used in
68 // assertion checking (debug builds).
69 std::map<const MachineInstr *, bool> OperandsColoredMap;
71 // AddedInstrMap - Used to store instrns added in this phase
72 std::map<const MachineInstr *, AddedInstrns> AddedInstrMap;
74 // ScratchRegsUsed - Contains scratch register uses for a particular MI.
75 typedef std::multimap<const MachineInstr*, int> ScratchRegsUsedTy;
76 ScratchRegsUsedTy ScratchRegsUsed;
78 AddedInstrns AddedInstrAtEntry; // to store instrns added at entry
79 const LoopInfo *LoopDepthCalc; // to calculate loop depths
81 std::map<const Function *, Constant *> FnAllocState;
83 PhyRegAlloc(const PhyRegAlloc&); // DO NOT IMPLEMENT
84 void operator=(const PhyRegAlloc&); // DO NOT IMPLEMENT
86 inline PhyRegAlloc (const TargetMachine &TM_) :
87 TM (TM_), MRI (TM.getRegInfo ()),
88 NumOfRegClasses (MRI.getNumOfRegClasses ()) { }
89 virtual ~PhyRegAlloc() { }
91 /// runOnFunction - Main method called for allocating registers.
93 virtual bool runOnFunction (Function &F);
95 virtual bool doFinalization (Module &M);
97 virtual void getAnalysisUsage (AnalysisUsage &AU) const;
99 const char *getPassName () const {
100 return "Traditional graph-coloring reg. allocator";
103 inline const RegClass* getRegClassByID(unsigned id) const {
104 return RegClassList[id];
106 inline RegClass *getRegClassByID(unsigned id) { return RegClassList[id]; }
109 void addInterference(const Value *Def, const ValueSet *LVSet,
111 bool markAllocatedRegs(MachineInstr* MInst);
113 void addInterferencesForArgs();
114 void createIGNodeListsAndIGs();
115 void buildInterferenceGraphs();
118 void setCallInterferences(const MachineInstr *MI,
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,
128 MachineBasicBlock::iterator& MII,
129 MachineBasicBlock &MBB, unsigned OpNum);
131 // Method for inserting caller saving code. The caller must save all the
132 // volatile registers live across a call.
133 void insertCallerSavingCode(std::vector<MachineInstr*>& instrnsBefore,
134 std::vector<MachineInstr*>& instrnsAfter,
135 MachineInstr *CallMI,
136 const BasicBlock *BB);
138 void colorIncomingArgs();
139 void colorCallRetArgs();
140 void updateMachineCode();
141 void updateInstruction(MachineBasicBlock::iterator& MII,
142 MachineBasicBlock &MBB);
144 int getUsableUniRegAtMI(int RegType, const ValueSet *LVSetBef,
146 std::vector<MachineInstr*>& MIBef,
147 std::vector<MachineInstr*>& MIAft);
149 // Callback method used to find unused registers.
150 // LVSetBef is the live variable set to search for an unused register.
151 // If it is not specified, the LV set before the current MI is used.
152 // This is sufficient as long as no new copy instructions are generated
153 // to copy the free register to memory.
155 int getUnusedUniRegAtMI(RegClass *RC, int RegType,
156 const MachineInstr *MI,
157 const ValueSet *LVSetBef = 0);
159 void setRelRegsUsedByThisInst(RegClass *RC, int RegType,
160 const MachineInstr *MI);
162 int getUniRegNotUsedByThisInst(RegClass *RC, int RegType,
163 const MachineInstr *MI);
165 void addInterf4PseudoInstr(const MachineInstr *MI);