lib/CodeGen/RegAllocBase.h

   1 //===-- RegAllocBase.h - basic regalloc interface and driver --*- C++ -*---===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the RegAllocBase class, which is the skeleton of a basic
  11 // register allocation algorithm and interface for extending it. It provides the
  12 // building blocks on which to construct other experimental allocators and test
  13 // the validity of two principles:
  14 //
  15 // - If virtual and physical register liveness is modeled using intervals, then
  16 // on-the-fly interference checking is cheap. Furthermore, interferences can be
  17 // lazily cached and reused.
  18 //
  19 // - Register allocation complexity, and generated code performance is
  20 // determined by the effectiveness of live range splitting rather than optimal
  21 // coloring.
  22 //
  23 // Following the first principle, interfering checking revolves around the
  24 // LiveIntervalUnion data structure.
  25 //
  26 // To fulfill the second principle, the basic allocator provides a driver for
  27 // incremental splitting. It essentially punts on the problem of register
  28 // coloring, instead driving the assignment of virtual to physical registers by
  29 // the cost of splitting. The basic allocator allows for heuristic reassignment
  30 // of registers, if a more sophisticated allocator chooses to do that.
  31 //
  32 // This framework provides a way to engineer the compile time vs. code
  33 // quality trade-off without relying a particular theoretical solver.
  34 //
  35 //===----------------------------------------------------------------------===//
  36
  37 #ifndef LLVM_CODEGEN_REGALLOCBASE
  38 #define LLVM_CODEGEN_REGALLOCBASE
  39
  40 #include "LiveIntervalUnion.h"
  41 #include "VirtRegMap.h"
  42 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  43 #include "llvm/Target/TargetRegisterInfo.h"
  44 #include "llvm/ADT/OwningPtr.h"
  45 #include <vector>
  46 #include <queue>
  47
  48 namespace llvm {
  49
  50 class VirtRegMap;
  51
  52 /// RegAllocBase provides the register allocation driver and interface that can
  53 /// be extended to add interesting heuristics.
  54 ///
  55 /// More sophisticated allocators must override the selectOrSplit() method to
  56 /// implement live range splitting and must specify a comparator to determine
  57 /// register assignment priority. LessSpillWeightPriority is provided as a
  58 /// standard comparator.
  59 class RegAllocBase {
  60 protected:
  61   typedef SmallVector<LiveInterval*, 4> LiveVirtRegs;
  62   typedef LiveVirtRegs::iterator LVRIter;
  63
  64   // Array of LiveIntervalUnions indexed by physical register.
  65   class LIUArray {
  66     unsigned nRegs_;
  67     OwningArrayPtr<LiveIntervalUnion> array_;
  68   public:
  69     LIUArray(): nRegs_(0) {}
  70
  71     unsigned numRegs() const { return nRegs_; }
  72
  73     void init(unsigned nRegs);
  74
  75     void clear();
  76
  77     LiveIntervalUnion& operator[](unsigned physReg) {
  78       assert(physReg <  nRegs_ && "physReg out of bounds");
  79       return array_[physReg];
  80     }
  81   };
  82
  83   const TargetRegisterInfo *tri_;
  84   VirtRegMap *vrm_;
  85   LiveIntervals *lis_;
  86   LIUArray physReg2liu_;
  87
  88   RegAllocBase(): tri_(0), vrm_(0), lis_(0) {}
  89
  90   virtual ~RegAllocBase() {}
  91
  92   // A RegAlloc pass should call this before allocatePhysRegs.
  93   void init(const TargetRegisterInfo &tri, VirtRegMap &vrm, LiveIntervals &lis);
  94
  95   // The top-level driver. Specialize with the comparator that determines the
  96   // priority of assigning live virtual registers. The output is a VirtRegMap
  97   // that us updated with physical register assignments.
  98   template<typename LICompare>
  99   void allocatePhysRegs(LICompare liCompare);
 100
 101   // A RegAlloc pass should override this to provide the allocation heuristics.
 102   // Each call must guarantee forward progess by returning an available
 103   // PhysReg or new set of split LiveVirtRegs. It is up to the splitter to
 104   // converge quickly toward fully spilled live ranges.
 105   virtual unsigned selectOrSplit(LiveInterval &lvr,
 106                                  LiveVirtRegs &splitLVRs) = 0;
 107
 108   // A RegAlloc pass should call this when PassManager releases its memory.
 109   virtual void releaseMemory();
 110
 111   // Helper for checking interference between a live virtual register and a
 112   // physical register, including all its register aliases.
 113   bool checkPhysRegInterference(LiveIntervalUnion::Query &query, unsigned preg);
 114
 115 private:
 116   template<typename PQ>
 117   void seedLiveVirtRegs(PQ &lvrQ);
 118 };
 119
 120 // Heuristic that determines the priority of assigning virtual to physical
 121 // registers. The main impact of the heuristic is expected to be compile time.
 122 // The default is to simply compare spill weights.
 123 struct LessSpillWeightPriority
 124   : public std::binary_function<LiveInterval,LiveInterval, bool> {
 125   bool operator()(const LiveInterval *left, const LiveInterval *right) const {
 126     return left->weight < right->weight;
 127   }
 128 };
 129
 130 // Visit all the live virtual registers. If they are already assigned to a
 131 // physical register, unify them with the corresponding LiveIntervalUnion,
 132 // otherwise push them on the priority queue for later assignment.
 133 template<typename PQ>
 134 void RegAllocBase::seedLiveVirtRegs(PQ &lvrQ) {
 135   for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end();
 136        liItr != liEnd; ++liItr) {
 137     unsigned reg = liItr->first;
 138     LiveInterval &li = *liItr->second;
 139     if (TargetRegisterInfo::isPhysicalRegister(reg)) {
 140       physReg2liu_[reg].unify(li);
 141     }
 142     else {
 143       lvrQ.push(&li);
 144     }
 145   }
 146 }
 147
 148 // Top-level driver to manage the queue of unassigned LiveVirtRegs and call the
 149 // selectOrSplit implementation.
 150 template<typename LICompare>
 151 void RegAllocBase::allocatePhysRegs(LICompare liCompare) {
 152   typedef std::priority_queue
 153     <LiveInterval*, std::vector<LiveInterval*>, LICompare> LiveVirtRegQueue;
 154
 155   LiveVirtRegQueue lvrQ(liCompare);
 156   seedLiveVirtRegs(lvrQ);
 157   while (!lvrQ.empty()) {
 158     LiveInterval *lvr = lvrQ.top();
 159     lvrQ.pop();
 160     LiveVirtRegs splitLVRs;
 161     unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs);
 162     if (availablePhysReg) {
 163       assert(splitLVRs.empty() && "inconsistent splitting");
 164       assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions");
 165       vrm_->assignVirt2Phys(lvr->reg, availablePhysReg);
 166       physReg2liu_[availablePhysReg].unify(*lvr);
 167     }
 168     else {
 169       for (LVRIter lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end();
 170            lvrI != lvrEnd; ++lvrI ) {
 171         assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) &&
 172                "expect split value in virtual register");
 173         lvrQ.push(*lvrI);
 174       }
 175     }
 176   }
 177 }
 178
 179 } // end namespace llvm
 180
 181 #endif // !defined(LLVM_CODEGEN_REGALLOCBASE)