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   // A RegAlloc pass should call this before allocatePhysRegs.
  91   void init(const TargetRegisterInfo &tri, VirtRegMap &vrm, LiveIntervals &lis);
  92
  93   // The top-level driver. Specialize with the comparator that determines the
  94   // priority of assigning live virtual registers. The output is a VirtRegMap
  95   // that us updated with physical register assignments.
  96   template<typename LICompare>
  97   void allocatePhysRegs(LICompare liCompare);
  98
  99   // A RegAlloc pass should override this to provide the allocation heuristics.
 100   // Each call must guarantee forward progess by returning an available
 101   // PhysReg or new set of split LiveVirtRegs. It is up to the splitter to
 102   // converge quickly toward fully spilled live ranges.
 103   virtual unsigned selectOrSplit(LiveInterval &lvr,
 104                                  LiveVirtRegs &splitLVRs) = 0;
 105
 106   // A RegAlloc pass should call this when PassManager releases its memory.
 107   virtual void releaseMemory();
 108
 109   // Helper for checking interference between a live virtual register and a
 110   // physical register, including all its register aliases.
 111   bool checkPhysRegInterference(LiveIntervalUnion::Query &query, unsigned preg);
 112
 113 private:
 114   template<typename PQ>
 115   void seedLiveVirtRegs(PQ &lvrQ);
 116 };
 117
 118 // Heuristic that determines the priority of assigning virtual to physical
 119 // registers. The main impact of the heuristic is expected to be compile time.
 120 // The default is to simply compare spill weights.
 121 struct LessSpillWeightPriority
 122   : public std::binary_function<LiveInterval,LiveInterval, bool> {
 123   bool operator()(const LiveInterval *left, const LiveInterval *right) const {
 124     return left->weight < right->weight;
 125   }
 126 };
 127
 128 // Visit all the live virtual registers. If they are already assigned to a
 129 // physical register, unify them with the corresponding LiveIntervalUnion,
 130 // otherwise push them on the priority queue for later assignment.
 131 template<typename PQ>
 132 void RegAllocBase::seedLiveVirtRegs(PQ &lvrQ) {
 133   for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end();
 134        liItr != liEnd; ++liItr) {
 135     unsigned reg = liItr->first;
 136     LiveInterval &li = *liItr->second;
 137     if (TargetRegisterInfo::isPhysicalRegister(reg)) {
 138       physReg2liu_[reg].unify(li);
 139     }
 140     else {
 141       lvrQ.push(&li);
 142     }
 143   }
 144 }
 145
 146 // Top-level driver to manage the queue of unassigned LiveVirtRegs and call the
 147 // selectOrSplit implementation.
 148 template<typename LICompare>
 149 void RegAllocBase::allocatePhysRegs(LICompare liCompare) {
 150   typedef std::priority_queue
 151     <LiveInterval*, std::vector<LiveInterval*>, LICompare> LiveVirtRegQueue;
 152
 153   LiveVirtRegQueue lvrQ(liCompare);
 154   seedLiveVirtRegs(lvrQ);
 155   while (!lvrQ.empty()) {
 156     LiveInterval *lvr = lvrQ.top();
 157     lvrQ.pop();
 158     LiveVirtRegs splitLVRs;
 159     unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs);
 160     if (availablePhysReg) {
 161       assert(splitLVRs.empty() && "inconsistent splitting");
 162       assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions");
 163       vrm_->assignVirt2Phys(lvr->reg, availablePhysReg);
 164       physReg2liu_[availablePhysReg].unify(*lvr);
 165     }
 166     else {
 167       for (LVRIter lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end();
 168            lvrI != lvrEnd; ++lvrI ) {
 169         assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) &&
 170                "expect split value in virtual register");
 171         lvrQ.push(*lvrI);
 172       }
 173     }
 174   }
 175 }
 176
 177 } // end namespace llvm
 178
 179 #endif // !defined(LLVM_CODEGEN_REGALLOCBASE)