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 "../SparcV9RegInfo.h"
  32 #include <map>
  33
  34 namespace llvm {
  35
  36 class MachineFunction;
  37 class FunctionLiveVarInfo;
  38 class MachineInstr;
  39 class LoopInfo;
  40 class RegClass;
  41 class Constant;
  42
  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 //----------------------------------------------------------------------------
  51
  52 struct AddedInstrns {
  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 (); }
  56 };
  57
  58 //----------------------------------------------------------------------------
  59 // class PhyRegAlloc:
  60 // Main class the register allocator. Call runOnFunction() to allocate
  61 // registers for a Function.
  62 //----------------------------------------------------------------------------
  63
  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
  74
  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;
  79
  80   // AddedInstrMap - Used to store instrns added in this phase
  81   std::map<const MachineInstr *, AddedInstrns> AddedInstrMap;
  82
  83   // ScratchRegsUsed - Contains scratch register uses for a particular MI.
  84   typedef std::multimap<const MachineInstr*, int> ScratchRegsUsedTy;
  85   ScratchRegsUsedTy ScratchRegsUsed;
  86
  87   AddedInstrns AddedInstrAtEntry;       // to store instrns added at entry
  88   const LoopInfo *LoopDepthCalc;        // to calculate loop depths
  89
  90   PhyRegAlloc(const PhyRegAlloc&);     // DO NOT IMPLEMENT
  91   void operator=(const PhyRegAlloc&);  // DO NOT IMPLEMENT
  92 public:
  93   typedef std::map<const Function *, std::vector<AllocInfo> > SavedStateMapTy;
  94
  95   inline PhyRegAlloc (const TargetMachine &TM_) :
  96     TM (TM_), MRI (TM.getRegInfo ()),
  97     NumOfRegClasses (MRI.getNumOfRegClasses ()) { }
  98   virtual ~PhyRegAlloc() { }
  99
 100   /// runOnFunction - Main method called for allocating registers.
 101   ///
 102   virtual bool runOnFunction (Function &F);
 103
 104   virtual bool doFinalization (Module &M);
 105
 106   virtual void getAnalysisUsage (AnalysisUsage &AU) const;
 107
 108   const char *getPassName () const {
 109     return "Traditional graph-coloring reg. allocator";
 110   }
 111
 112   inline const RegClass* getRegClassByID(unsigned id) const {
 113     return RegClassList[id];
 114   }
 115   inline RegClass *getRegClassByID(unsigned id) { return RegClassList[id]; }
 116
 117 private:
 118   SavedStateMapTy FnAllocState;
 119
 120   void addInterference(const Value *Def, const ValueSet *LVSet,
 121                        bool isCallInst);
 122   bool markAllocatedRegs(MachineInstr* MInst);
 123
 124   void addInterferencesForArgs();
 125   void createIGNodeListsAndIGs();
 126   void buildInterferenceGraphs();
 127
 128   void saveStateForValue (std::vector<AllocInfo> &state,
 129                           const Value *V, int Insn, int Opnd);
 130   void saveState();
 131   void verifySavedState();
 132   void finishSavingState(Module &M);
 133
 134   void setCallInterferences(const MachineInstr *MI,
 135                             const ValueSet *LVSetAft);
 136
 137   void move2DelayedInstr(const MachineInstr *OrigMI,
 138                          const MachineInstr *DelayedMI);
 139
 140   void markUnusableSugColors();
 141   void allocateStackSpace4SpilledLRs();
 142
 143   void insertCode4SpilledLR(const LiveRange *LR,
 144                             MachineBasicBlock::iterator& MII,
 145                             MachineBasicBlock &MBB, unsigned OpNum);
 146
 147   /// Method for inserting caller saving code. The caller must save all the
 148   /// volatile registers live across a call.
 149   ///
 150   void insertCallerSavingCode(std::vector<MachineInstr*>& instrnsBefore,
 151                               std::vector<MachineInstr*>& instrnsAfter,
 152                               MachineInstr *CallMI,
 153                               const BasicBlock *BB);
 154
 155   void colorIncomingArgs();
 156   void colorCallRetArgs();
 157   void updateMachineCode();
 158   void updateInstruction(MachineBasicBlock::iterator& MII,
 159                          MachineBasicBlock &MBB);
 160
 161   int getUsableUniRegAtMI(int RegType, const ValueSet *LVSetBef,
 162                           MachineInstr *MI,
 163                           std::vector<MachineInstr*>& MIBef,
 164                           std::vector<MachineInstr*>& MIAft);
 165
 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.
 171   ///
 172   int getUnusedUniRegAtMI(RegClass *RC, int RegType,
 173                           const MachineInstr *MI,
 174                           const ValueSet *LVSetBef = 0);
 175
 176   void setRelRegsUsedByThisInst(RegClass *RC, int RegType,
 177                                 const MachineInstr *MI);
 178
 179   int getUniRegNotUsedByThisInst(RegClass *RC, int RegType,
 180                                  const MachineInstr *MI);
 181
 182   void addInterf4PseudoInstr(const MachineInstr *MI);
 183 };
 184
 185 } // End llvm namespace
 186
 187 #endif