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/TargetRegInfo.h"
  31 #include "llvm/Target/TargetMachine.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   std::map<const Function *, Constant *> FnAllocState;
  89
  90   PhyRegAlloc(const PhyRegAlloc&);     // DO NOT IMPLEMENT
  91   void operator=(const PhyRegAlloc&);  // DO NOT IMPLEMENT
  92 public:
  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   void addInterference(const Value *Def, const ValueSet *LVSet,
 117                        bool isCallInst);
 118   bool markAllocatedRegs(MachineInstr* MInst);
 119
 120   void addInterferencesForArgs();
 121   void createIGNodeListsAndIGs();
 122   void buildInterferenceGraphs();
 123   void saveState();
 124
 125   void setCallInterferences(const MachineInstr *MI,
 126                             const ValueSet *LVSetAft);
 127
 128   void move2DelayedInstr(const MachineInstr *OrigMI,
 129                          const MachineInstr *DelayedMI);
 130
 131   void markUnusableSugColors();
 132   void allocateStackSpace4SpilledLRs();
 133
 134   void insertCode4SpilledLR(const LiveRange *LR,
 135                             MachineBasicBlock::iterator& MII,
 136                             MachineBasicBlock &MBB, unsigned OpNum);
 137
 138   // Method for inserting caller saving code. The caller must save all the
 139   // volatile registers live across a call.
 140   void insertCallerSavingCode(std::vector<MachineInstr*>& instrnsBefore,
 141                               std::vector<MachineInstr*>& instrnsAfter,
 142                               MachineInstr *CallMI,
 143                               const BasicBlock *BB);
 144
 145   void colorIncomingArgs();
 146   void colorCallRetArgs();
 147   void updateMachineCode();
 148   void updateInstruction(MachineBasicBlock::iterator& MII,
 149                          MachineBasicBlock &MBB);
 150
 151   int getUsableUniRegAtMI(int RegType, const ValueSet *LVSetBef,
 152                           MachineInstr *MI,
 153                           std::vector<MachineInstr*>& MIBef,
 154                           std::vector<MachineInstr*>& MIAft);
 155
 156   // Callback method used to find unused registers.
 157   // LVSetBef is the live variable set to search for an unused register.
 158   // If it is not specified, the LV set before the current MI is used.
 159   // This is sufficient as long as no new copy instructions are generated
 160   // to copy the free register to memory.
 161   //
 162   int getUnusedUniRegAtMI(RegClass *RC, int RegType,
 163                           const MachineInstr *MI,
 164                           const ValueSet *LVSetBef = 0);
 165
 166   void setRelRegsUsedByThisInst(RegClass *RC, int RegType,
 167                                 const MachineInstr *MI);
 168
 169   int getUniRegNotUsedByThisInst(RegClass *RC, int RegType,
 170                                  const MachineInstr *MI);
 171
 172   void addInterf4PseudoInstr(const MachineInstr *MI);
 173 };
 174
 175 #endif