lib/Target/SparcV9/RegAlloc/PhyRegAlloc.h

   1 //===-- PhyRegAlloc.h - Graph Coloring Register Allocator -------*- c++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   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.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This is the main entry point for register allocation.
  11 //
  12 // Notes:
  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.
  18 //
  19 // * Machine dependent work: All parts of the register coloring algorithm
  20 //   except coloring of an individual node are machine independent.
  21 //
  22 //===----------------------------------------------------------------------===//
  23
  24 #ifndef PHYREGALLOC_H
  25 #define PHYREGALLOC_H
  26
  27 #include "LiveRangeInfo.h"
  28 #include "llvm/Pass.h"
  29 #include "llvm/CodeGen/MachineBasicBlock.h"
  30 #include "llvm/Target/TargetMachine.h"
  31 #include "llvm/Target/TargetRegInfo.h"
  32 #include <map>
  33
  34 class MachineFunction;
  35 class FunctionLiveVarInfo;
  36 class MachineInstr;
  37 class LoopInfo;
  38 class RegClass;
  39 class Constant;
  40
  41 //----------------------------------------------------------------------------
  42 // Class AddedInstrns:
  43 // When register allocator inserts new instructions in to the existing
  44 // instruction stream, it does NOT directly modify the instruction stream.
  45 // Rather, it creates an object of AddedInstrns and stick it in the
  46 // AddedInstrMap for an existing instruction. This class contains two vectors
  47 // to store such instructions added before and after an existing instruction.
  48 //----------------------------------------------------------------------------
  49
  50 struct AddedInstrns {
  51   std::vector<MachineInstr*> InstrnsBefore;//Insts added BEFORE an existing inst
  52   std::vector<MachineInstr*> InstrnsAfter; //Insts added AFTER an existing inst
  53   inline void clear () { InstrnsBefore.clear (); InstrnsAfter.clear (); }
  54 };
  55
  56 //----------------------------------------------------------------------------
  57 // class PhyRegAlloc:
  58 // Main class the register allocator. Call runOnFunction() to allocate
  59 // registers for a Function.
  60 //----------------------------------------------------------------------------
  61
  62 class PhyRegAlloc : public FunctionPass {
  63   std::vector<RegClass *> RegClassList; // vector of register classes
  64   const TargetMachine &TM;              // target machine
  65   const Function *Fn;                   // name of the function we work on
  66   MachineFunction *MF;                  // descriptor for method's native code
  67   FunctionLiveVarInfo *LVI;             // LV information for this method
  68                                         // (already computed for BBs)
  69   LiveRangeInfo *LRI;                   // LR info  (will be computed)
  70   const TargetRegInfo &MRI;             // Machine Register information
  71   const unsigned NumOfRegClasses;       // recorded here for efficiency
  72
  73   // Map to indicate whether operands of each MachineInstr have been
  74   // updated according to their assigned colors.  This is only used in
  75   // assertion checking (debug builds).
  76   std::map<const MachineInstr *, bool> OperandsColoredMap;
  77
  78   // AddedInstrMap - Used to store instrns added in this phase
  79   std::map<const MachineInstr *, AddedInstrns> AddedInstrMap;
  80
  81   // ScratchRegsUsed - Contains scratch register uses for a particular MI.
  82   typedef std::multimap<const MachineInstr*, int> ScratchRegsUsedTy;
  83   ScratchRegsUsedTy ScratchRegsUsed;
  84
  85   AddedInstrns AddedInstrAtEntry;       // to store instrns added at entry
  86   const LoopInfo *LoopDepthCalc;        // to calculate loop depths
  87
  88   PhyRegAlloc(const PhyRegAlloc&);     // DO NOT IMPLEMENT
  89   void operator=(const PhyRegAlloc&);  // DO NOT IMPLEMENT
  90 public:
  91   typedef std::map<const Function *, std::vector<AllocInfo> > SavedStateMapTy;
  92
  93   inline PhyRegAlloc (const TargetMachine &TM_) :
  94     TM (TM_), MRI (TM.getRegInfo ()),
  95     NumOfRegClasses (MRI.getNumOfRegClasses ()) { }
  96   virtual ~PhyRegAlloc() { }
  97
  98   /// runOnFunction - Main method called for allocating registers.
  99   ///
 100   virtual bool runOnFunction (Function &F);
 101
 102   virtual bool doFinalization (Module &M);
 103
 104   virtual void getAnalysisUsage (AnalysisUsage &AU) const;
 105
 106   const char *getPassName () const {
 107     return "Traditional graph-coloring reg. allocator";
 108   }
 109
 110   inline const RegClass* getRegClassByID(unsigned id) const {
 111     return RegClassList[id];
 112   }
 113   inline RegClass *getRegClassByID(unsigned id) { return RegClassList[id]; }
 114
 115 private:
 116   SavedStateMapTy FnAllocState;
 117
 118   void addInterference(const Value *Def, const ValueSet *LVSet,
 119                        bool isCallInst);
 120   bool markAllocatedRegs(MachineInstr* MInst);
 121
 122   void addInterferencesForArgs();
 123   void createIGNodeListsAndIGs();
 124   void buildInterferenceGraphs();
 125   void saveState();
 126   void verifySavedState();
 127
 128   void setCallInterferences(const MachineInstr *MI,
 129                             const ValueSet *LVSetAft);
 130
 131   void move2DelayedInstr(const MachineInstr *OrigMI,
 132                          const MachineInstr *DelayedMI);
 133
 134   void markUnusableSugColors();
 135   void allocateStackSpace4SpilledLRs();
 136
 137   void insertCode4SpilledLR(const LiveRange *LR,
 138                             MachineBasicBlock::iterator& MII,
 139                             MachineBasicBlock &MBB, unsigned OpNum);
 140
 141   /// Method for inserting caller saving code. The caller must save all the
 142   /// volatile registers live across a call.
 143   ///
 144   void insertCallerSavingCode(std::vector<MachineInstr*>& instrnsBefore,
 145                               std::vector<MachineInstr*>& instrnsAfter,
 146                               MachineInstr *CallMI,
 147                               const BasicBlock *BB);
 148
 149   void colorIncomingArgs();
 150   void colorCallRetArgs();
 151   void updateMachineCode();
 152   void updateInstruction(MachineBasicBlock::iterator& MII,
 153                          MachineBasicBlock &MBB);
 154
 155   int getUsableUniRegAtMI(int RegType, const ValueSet *LVSetBef,
 156                           MachineInstr *MI,
 157                           std::vector<MachineInstr*>& MIBef,
 158                           std::vector<MachineInstr*>& MIAft);
 159
 160   /// Callback method used to find unused registers.
 161   /// LVSetBef is the live variable set to search for an unused register.
 162   /// If it is not specified, the LV set before the current MI is used.
 163   /// This is sufficient as long as no new copy instructions are generated
 164   /// to copy the free register to memory.
 165   ///
 166   int getUnusedUniRegAtMI(RegClass *RC, int RegType,
 167                           const MachineInstr *MI,
 168                           const ValueSet *LVSetBef = 0);
 169
 170   void setRelRegsUsedByThisInst(RegClass *RC, int RegType,
 171                                 const MachineInstr *MI);
 172
 173   int getUniRegNotUsedByThisInst(RegClass *RC, int RegType,
 174                                  const MachineInstr *MI);
 175
 176   void addInterf4PseudoInstr(const MachineInstr *MI);
 177 };
 178
 179 #endif