1 //===-- PhyRegAlloc.h - Graph Coloring Register Allocator -------*- c++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This is the main entry point for register allocation.
13 // * RegisterClasses: Each RegClass accepts a
14 // TargetRegClass which contains machine specific info about that register
15 // class. The code in the RegClass is machine independent and they use
16 // access functions in the TargetRegClass object passed into it to get
17 // machine specific info.
19 // * Machine dependent work: All parts of the register coloring algorithm
20 // except coloring of an individual node are machine independent.
22 //===----------------------------------------------------------------------===//
27 #include "LiveRangeInfo.h"
28 #include "llvm/Pass.h"
29 #include "llvm/CodeGen/MachineBasicBlock.h"
30 #include "llvm/Target/TargetMachine.h"
31 #include "../SparcV9RegInfo.h"
36 class MachineFunction;
37 class FunctionLiveVarInfo;
43 //----------------------------------------------------------------------------
44 // Class AddedInstrns:
45 // When register allocator inserts new instructions in to the existing
46 // instruction stream, it does NOT directly modify the instruction stream.
47 // Rather, it creates an object of AddedInstrns and stick it in the
48 // AddedInstrMap for an existing instruction. This class contains two vectors
49 // to store such instructions added before and after an existing instruction.
50 //----------------------------------------------------------------------------
53 std::vector<MachineInstr*> InstrnsBefore;//Insts added BEFORE an existing inst
54 std::vector<MachineInstr*> InstrnsAfter; //Insts added AFTER an existing inst
55 inline void clear () { InstrnsBefore.clear (); InstrnsAfter.clear (); }
58 //----------------------------------------------------------------------------
60 // Main class the register allocator. Call runOnFunction() to allocate
61 // registers for a Function.
62 //----------------------------------------------------------------------------
64 class PhyRegAlloc : public FunctionPass {
65 std::vector<RegClass *> RegClassList; // vector of register classes
66 const TargetMachine &TM; // target machine
67 const Function *Fn; // name of the function we work on
68 MachineFunction *MF; // descriptor for method's native code
69 FunctionLiveVarInfo *LVI; // LV information for this method
70 // (already computed for BBs)
71 LiveRangeInfo *LRI; // LR info (will be computed)
72 const TargetRegInfo &MRI; // Machine Register information
73 const unsigned NumOfRegClasses; // recorded here for efficiency
75 // Map to indicate whether operands of each MachineInstr have been
76 // updated according to their assigned colors. This is only used in
77 // assertion checking (debug builds).
78 std::map<const MachineInstr *, bool> OperandsColoredMap;
80 // AddedInstrMap - Used to store instrns added in this phase
81 std::map<const MachineInstr *, AddedInstrns> AddedInstrMap;
83 // ScratchRegsUsed - Contains scratch register uses for a particular MI.
84 typedef std::multimap<const MachineInstr*, int> ScratchRegsUsedTy;
85 ScratchRegsUsedTy ScratchRegsUsed;
87 AddedInstrns AddedInstrAtEntry; // to store instrns added at entry
88 const LoopInfo *LoopDepthCalc; // to calculate loop depths
90 PhyRegAlloc(const PhyRegAlloc&); // DO NOT IMPLEMENT
91 void operator=(const PhyRegAlloc&); // DO NOT IMPLEMENT
93 typedef std::map<const Function *, std::vector<AllocInfo> > SavedStateMapTy;
95 inline PhyRegAlloc (const TargetMachine &TM_) :
96 TM (TM_), MRI (TM.getRegInfo ()),
97 NumOfRegClasses (MRI.getNumOfRegClasses ()) { }
98 virtual ~PhyRegAlloc() { }
100 /// runOnFunction - Main method called for allocating registers.
102 virtual bool runOnFunction (Function &F);
104 virtual bool doFinalization (Module &M);
106 virtual void getAnalysisUsage (AnalysisUsage &AU) const;
108 const char *getPassName () const {
109 return "Traditional graph-coloring reg. allocator";
112 inline const RegClass* getRegClassByID(unsigned id) const {
113 return RegClassList[id];
115 inline RegClass *getRegClassByID(unsigned id) { return RegClassList[id]; }
118 SavedStateMapTy FnAllocState;
120 void addInterference(const Value *Def, const ValueSet *LVSet,
122 bool markAllocatedRegs(MachineInstr* MInst);
124 void addInterferencesForArgs();
125 void createIGNodeListsAndIGs();
126 void buildInterferenceGraphs();
128 void saveStateForValue (std::vector<AllocInfo> &state,
129 const Value *V, int Insn, int Opnd);
131 void verifySavedState();
132 void finishSavingState(Module &M);
134 void setCallInterferences(const MachineInstr *MI,
135 const ValueSet *LVSetAft);
137 void move2DelayedInstr(const MachineInstr *OrigMI,
138 const MachineInstr *DelayedMI);
140 void markUnusableSugColors();
141 void allocateStackSpace4SpilledLRs();
143 void insertCode4SpilledLR(const LiveRange *LR,
144 MachineBasicBlock::iterator& MII,
145 MachineBasicBlock &MBB, unsigned OpNum);
147 /// Method for inserting caller saving code. The caller must save all the
148 /// volatile registers live across a call.
150 void insertCallerSavingCode(std::vector<MachineInstr*>& instrnsBefore,
151 std::vector<MachineInstr*>& instrnsAfter,
152 MachineInstr *CallMI,
153 const BasicBlock *BB);
155 void colorIncomingArgs();
156 void colorCallRetArgs();
157 void updateMachineCode();
158 void updateInstruction(MachineBasicBlock::iterator& MII,
159 MachineBasicBlock &MBB);
161 int getUsableUniRegAtMI(int RegType, const ValueSet *LVSetBef,
163 std::vector<MachineInstr*>& MIBef,
164 std::vector<MachineInstr*>& MIAft);
166 /// Callback method used to find unused registers.
167 /// LVSetBef is the live variable set to search for an unused register.
168 /// If it is not specified, the LV set before the current MI is used.
169 /// This is sufficient as long as no new copy instructions are generated
170 /// to copy the free register to memory.
172 int getUnusedUniRegAtMI(RegClass *RC, int RegType,
173 const MachineInstr *MI,
174 const ValueSet *LVSetBef = 0);
176 void setRelRegsUsedByThisInst(RegClass *RC, int RegType,
177 const MachineInstr *MI);
179 int getUniRegNotUsedByThisInst(RegClass *RC, int RegType,
180 const MachineInstr *MI);
182 void addInterf4PseudoInstr(const MachineInstr *MI);
185 } // End llvm namespace