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 TargetRegClass 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 TargetRegClass 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.
19 #ifndef PHY_REG_ALLOC_H
20 #define PHY_REG_ALLOC_H
22 #include "LiveRangeInfo.h"
23 #include "llvm/CodeGen/MachineBasicBlock.h"
26 class MachineFunction;
28 class FunctionLiveVarInfo;
33 //----------------------------------------------------------------------------
34 // Class AddedInstrns:
35 // When register allocator inserts new instructions in to the existing
36 // instruction stream, it does NOT directly modify the instruction stream.
37 // Rather, it creates an object of AddedInstrns and stick it in the
38 // AddedInstrMap for an existing instruction. This class contains two vectors
39 // to store such instructions added before and after an existing instruction.
40 //----------------------------------------------------------------------------
43 std::vector<MachineInstr*> InstrnsBefore;//Insts added BEFORE an existing inst
44 std::vector<MachineInstr*> InstrnsAfter; //Insts added AFTER an existing inst
47 //----------------------------------------------------------------------------
49 // Main class the register allocator. Call allocateRegisters() to allocate
50 // registers for a Function.
51 //----------------------------------------------------------------------------
54 std::vector<RegClass *> RegClassList; // vector of register classes
55 const TargetMachine &TM; // target machine
56 const Function *Fn; // name of the function we work on
57 MachineFunction &MF; // descriptor for method's native code
58 FunctionLiveVarInfo *const LVI; // LV information for this method
59 // (already computed for BBs)
60 LiveRangeInfo LRI; // LR info (will be computed)
61 const TargetRegInfo &MRI; // Machine Register information
62 const unsigned NumOfRegClasses; // recorded here for efficiency
64 // Map to indicate whether operands of each MachineInstr have been updated
65 // according to their assigned colors. This is primarily for debugging and
66 // could be removed in the long run.
67 std::map<const MachineInstr *, bool> OperandsColoredMap;
69 // AddedInstrMap - Used to store instrns added in this phase
70 std::map<const MachineInstr *, AddedInstrns> AddedInstrMap;
72 // ScratchRegsUsed - Contains scratch register uses for a particular MI.
73 typedef std::multimap<const MachineInstr*, int> ScratchRegsUsedTy;
74 ScratchRegsUsedTy ScratchRegsUsed;
76 AddedInstrns AddedInstrAtEntry; // to store instrns added at entry
77 LoopInfo *LoopDepthCalc; // to calculate loop depths
79 PhyRegAlloc(const PhyRegAlloc&); // DO NOT IMPLEMENT
80 void operator=(const PhyRegAlloc&); // DO NOT IMPLEMENT
82 PhyRegAlloc(Function *F, const TargetMachine& TM, FunctionLiveVarInfo *Lvi,
83 LoopInfo *LoopDepthCalc);
86 // main method called for allocating registers
88 void allocateRegisters();
90 // access to register classes by class ID
92 const RegClass* getRegClassByID(unsigned id) const {
93 return RegClassList[id];
95 RegClass* getRegClassByID(unsigned id) {
96 return RegClassList[id];
100 void addInterference(const Value *Def, const ValueSet *LVSet,
103 void addInterferencesForArgs();
104 void createIGNodeListsAndIGs();
105 void buildInterferenceGraphs();
107 void setCallInterferences(const MachineInstr *MI,
108 const ValueSet *LVSetAft);
110 void move2DelayedInstr(const MachineInstr *OrigMI,
111 const MachineInstr *DelayedMI);
113 void markUnusableSugColors();
114 void allocateStackSpace4SpilledLRs();
116 void insertCode4SpilledLR(const LiveRange *LR,
117 MachineBasicBlock::iterator& MII,
118 MachineBasicBlock &MBB, unsigned OpNum);
120 // Method for inserting caller saving code. The caller must save all the
121 // volatile registers live across a call.
122 void insertCallerSavingCode(std::vector<MachineInstr*>& instrnsBefore,
123 std::vector<MachineInstr*>& instrnsAfter,
124 MachineInstr *CallMI,
125 const BasicBlock *BB);
127 inline void constructLiveRanges() { LRI.constructLiveRanges(); }
129 void colorIncomingArgs();
130 void colorCallRetArgs();
131 void updateMachineCode();
132 void updateInstruction(MachineBasicBlock::iterator& MII,
133 MachineBasicBlock &MBB);
135 void printLabel(const Value *Val);
136 void printMachineCode();
139 int getUsableUniRegAtMI(int RegType, const ValueSet *LVSetBef,
141 std::vector<MachineInstr*>& MIBef,
142 std::vector<MachineInstr*>& MIAft);
144 // Callback method used to find unused registers.
145 // LVSetBef is the live variable set to search for an unused register.
146 // If it is not specified, the LV set before the current MI is used.
147 // This is sufficient as long as no new copy instructions are generated
148 // to copy the free register to memory.
150 int getUnusedUniRegAtMI(RegClass *RC, int RegType,
151 const MachineInstr *MI,
152 const ValueSet *LVSetBef = 0);
154 void setRelRegsUsedByThisInst(RegClass *RC, int RegType,
155 const MachineInstr *MI);
157 int getUniRegNotUsedByThisInst(RegClass *RC, int RegType,
158 const MachineInstr *MI);
160 void addInterf4PseudoInstr(const MachineInstr *MI);