LLVM API Documentation

PhyRegAlloc.h

Go to the documentation of this file.
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 V9LiveRange *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