LLVM API Documentation
00001 //===-- PhyRegAlloc.h - Graph Coloring Register Allocator -------*- c++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This is the main entry point for register allocation. 00011 // 00012 // Notes: 00013 // * RegisterClasses: Each RegClass accepts a 00014 // TargetRegClass which contains machine specific info about that register 00015 // class. The code in the RegClass is machine independent and they use 00016 // access functions in the TargetRegClass object passed into it to get 00017 // machine specific info. 00018 // 00019 // * Machine dependent work: All parts of the register coloring algorithm 00020 // except coloring of an individual node are machine independent. 00021 // 00022 //===----------------------------------------------------------------------===// 00023 00024 #ifndef PHYREGALLOC_H 00025 #define PHYREGALLOC_H 00026 00027 #include "LiveRangeInfo.h" 00028 #include "llvm/Pass.h" 00029 #include "llvm/CodeGen/MachineBasicBlock.h" 00030 #include "llvm/Target/TargetMachine.h" 00031 #include "../SparcV9RegInfo.h" 00032 #include <map> 00033 00034 namespace llvm { 00035 00036 class MachineFunction; 00037 class FunctionLiveVarInfo; 00038 class MachineInstr; 00039 class LoopInfo; 00040 class RegClass; 00041 class Constant; 00042 00043 //---------------------------------------------------------------------------- 00044 // Class AddedInstrns: 00045 // When register allocator inserts new instructions in to the existing 00046 // instruction stream, it does NOT directly modify the instruction stream. 00047 // Rather, it creates an object of AddedInstrns and stick it in the 00048 // AddedInstrMap for an existing instruction. This class contains two vectors 00049 // to store such instructions added before and after an existing instruction. 00050 //---------------------------------------------------------------------------- 00051 00052 struct AddedInstrns { 00053 std::vector<MachineInstr*> InstrnsBefore;//Insts added BEFORE an existing inst 00054 std::vector<MachineInstr*> InstrnsAfter; //Insts added AFTER an existing inst 00055 inline void clear () { InstrnsBefore.clear (); InstrnsAfter.clear (); } 00056 }; 00057 00058 //---------------------------------------------------------------------------- 00059 // class PhyRegAlloc: 00060 // Main class the register allocator. Call runOnFunction() to allocate 00061 // registers for a Function. 00062 //---------------------------------------------------------------------------- 00063 00064 class PhyRegAlloc : public FunctionPass { 00065 std::vector<RegClass *> RegClassList; // vector of register classes 00066 const TargetMachine &TM; // target machine 00067 const Function *Fn; // name of the function we work on 00068 MachineFunction *MF; // descriptor for method's native code 00069 FunctionLiveVarInfo *LVI; // LV information for this method 00070 // (already computed for BBs) 00071 LiveRangeInfo *LRI; // LR info (will be computed) 00072 const SparcV9RegInfo &MRI; // Machine Register information 00073 const unsigned NumOfRegClasses; // recorded here for efficiency 00074 00075 // Map to indicate whether operands of each MachineInstr have been 00076 // updated according to their assigned colors. This is only used in 00077 // assertion checking (debug builds). 00078 std::map<const MachineInstr *, bool> OperandsColoredMap; 00079 00080 // AddedInstrMap - Used to store instrns added in this phase 00081 std::map<const MachineInstr *, AddedInstrns> AddedInstrMap; 00082 00083 // ScratchRegsUsed - Contains scratch register uses for a particular MI. 00084 typedef std::multimap<const MachineInstr*, int> ScratchRegsUsedTy; 00085 ScratchRegsUsedTy ScratchRegsUsed; 00086 00087 AddedInstrns AddedInstrAtEntry; // to store instrns added at entry 00088 const LoopInfo *LoopDepthCalc; // to calculate loop depths 00089 00090 PhyRegAlloc(const PhyRegAlloc&); // DO NOT IMPLEMENT 00091 void operator=(const PhyRegAlloc&); // DO NOT IMPLEMENT 00092 public: 00093 typedef std::map<const Function *, std::vector<AllocInfo> > SavedStateMapTy; 00094 00095 inline PhyRegAlloc (const TargetMachine &TM_) : 00096 TM (TM_), MRI (*TM.getRegInfo ()), 00097 NumOfRegClasses (MRI.getNumOfRegClasses ()) { } 00098 virtual ~PhyRegAlloc() { } 00099 00100 /// runOnFunction - Main method called for allocating registers. 00101 /// 00102 virtual bool runOnFunction (Function &F); 00103 00104 virtual bool doFinalization (Module &M); 00105 00106 virtual void getAnalysisUsage (AnalysisUsage &AU) const; 00107 00108 const char *getPassName () const { 00109 return "Traditional graph-coloring reg. allocator"; 00110 } 00111 00112 inline const RegClass* getRegClassByID(unsigned id) const { 00113 return RegClassList[id]; 00114 } 00115 inline RegClass *getRegClassByID(unsigned id) { return RegClassList[id]; } 00116 00117 private: 00118 SavedStateMapTy FnAllocState; 00119 00120 void addInterference(const Value *Def, const ValueSet *LVSet, 00121 bool isCallInst); 00122 bool markAllocatedRegs(MachineInstr* MInst); 00123 00124 void addInterferencesForArgs(); 00125 void createIGNodeListsAndIGs(); 00126 void buildInterferenceGraphs(); 00127 00128 void saveStateForValue (std::vector<AllocInfo> &state, 00129 const Value *V, int Insn, int Opnd); 00130 void saveState(); 00131 void finishSavingState(Module &M); 00132 00133 void setCallInterferences(const MachineInstr *MI, 00134 const ValueSet *LVSetAft); 00135 00136 void move2DelayedInstr(const MachineInstr *OrigMI, 00137 const MachineInstr *DelayedMI); 00138 00139 void markUnusableSugColors(); 00140 void allocateStackSpace4SpilledLRs(); 00141 00142 void insertCode4SpilledLR(const LiveRange *LR, 00143 MachineBasicBlock::iterator& MII, 00144 MachineBasicBlock &MBB, unsigned OpNum); 00145 00146 /// Method for inserting caller saving code. The caller must save all the 00147 /// volatile registers live across a call. 00148 /// 00149 void insertCallerSavingCode(std::vector<MachineInstr*>& instrnsBefore, 00150 std::vector<MachineInstr*>& instrnsAfter, 00151 MachineInstr *CallMI, 00152 const BasicBlock *BB); 00153 00154 void colorIncomingArgs(); 00155 void colorCallRetArgs(); 00156 void updateMachineCode(); 00157 void updateInstruction(MachineBasicBlock::iterator& MII, 00158 MachineBasicBlock &MBB); 00159 00160 int getUsableUniRegAtMI(int RegType, const ValueSet *LVSetBef, 00161 MachineInstr *MI, 00162 std::vector<MachineInstr*>& MIBef, 00163 std::vector<MachineInstr*>& MIAft); 00164 00165 /// Callback method used to find unused registers. 00166 /// LVSetBef is the live variable set to search for an unused register. 00167 /// If it is not specified, the LV set before the current MI is used. 00168 /// This is sufficient as long as no new copy instructions are generated 00169 /// to copy the free register to memory. 00170 /// 00171 int getUnusedUniRegAtMI(RegClass *RC, int RegType, 00172 const MachineInstr *MI, 00173 const ValueSet *LVSetBef = 0); 00174 00175 void setRelRegsUsedByThisInst(RegClass *RC, int RegType, 00176 const MachineInstr *MI); 00177 00178 int getUniRegNotUsedByThisInst(RegClass *RC, int RegType, 00179 const MachineInstr *MI); 00180 00181 void addInterf4PseudoInstr(const MachineInstr *MI); 00182 }; 00183 00184 } // End llvm namespace 00185 00186 #endif