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 "llvm/ADT/OwningPtr.h"
  41
  42 namespace llvm {
  43
  44 template<typename T> class SmallVectorImpl;
  45 class TargetRegisterInfo;
  46 class VirtRegMap;
  47 class LiveIntervals;
  48 class Spiller;
  49
  50 // Heuristic that determines the priority of assigning virtual to physical
  51 // registers. The main impact of the heuristic is expected to be compile time.
  52 // The default is to simply compare spill weights.
  53 struct LessSpillWeightPriority
  54   : public std::binary_function<LiveInterval,LiveInterval, bool> {
  55   bool operator()(const LiveInterval *left, const LiveInterval *right) const {
  56     return left->weight < right->weight;
  57   }
  58 };
  59
  60 // Forward declare a priority queue of live virtual registers. If an
  61 // implementation needs to prioritize by anything other than spill weight, then
  62 // this will become an abstract base class with virtual calls to push/get.
  63 class LiveVirtRegQueue;
  64
  65 /// RegAllocBase provides the register allocation driver and interface that can
  66 /// be extended to add interesting heuristics.
  67 ///
  68 /// More sophisticated allocators must override the selectOrSplit() method to
  69 /// implement live range splitting and must specify a comparator to determine
  70 /// register assignment priority. LessSpillWeightPriority is provided as a
  71 /// standard comparator.
  72 class RegAllocBase {
  73 protected:
  74   // Array of LiveIntervalUnions indexed by physical register.
  75   class LIUArray {
  76     unsigned nRegs_;
  77     OwningArrayPtr<LiveIntervalUnion> array_;
  78   public:
  79     LIUArray(): nRegs_(0) {}
  80
  81     unsigned numRegs() const { return nRegs_; }
  82
  83     void init(unsigned nRegs);
  84
  85     void clear();
  86
  87     LiveIntervalUnion& operator[](unsigned physReg) {
  88       assert(physReg <  nRegs_ && "physReg out of bounds");
  89       return array_[physReg];
  90     }
  91   };
  92
  93   const TargetRegisterInfo *tri_;
  94   VirtRegMap *vrm_;
  95   LiveIntervals *lis_;
  96   LIUArray physReg2liu_;
  97
  98   // Current queries, one per physreg. They must be reinitialized each time we
  99   // query on a new live virtual register.
 100   OwningArrayPtr<LiveIntervalUnion::Query> queries_;
 101
 102   RegAllocBase(): tri_(0), vrm_(0), lis_(0) {}
 103
 104   virtual ~RegAllocBase() {}
 105
 106   // A RegAlloc pass should call this before allocatePhysRegs.
 107   void init(const TargetRegisterInfo &tri, VirtRegMap &vrm, LiveIntervals &lis);
 108
 109   // Get an initialized query to check interferences between lvr and preg.  Note
 110   // that Query::init must be called at least once for each physical register
 111   // before querying a new live virtual register. This ties queries_ and
 112   // physReg2liu_ together.
 113   LiveIntervalUnion::Query &query(LiveInterval &lvr, unsigned preg) {
 114     queries_[preg].init(&lvr, &physReg2liu_[preg]);
 115     return queries_[preg];
 116   }
 117
 118   // The top-level driver. The output is a VirtRegMap that us updated with
 119   // physical register assignments.
 120   //
 121   // If an implementation wants to override the LiveInterval comparator, we
 122   // should modify this interface to allow passing in an instance derived from
 123   // LiveVirtRegQueue.
 124   void allocatePhysRegs();
 125
 126   // Get a temporary reference to a Spiller instance.
 127   virtual Spiller &spiller() = 0;
 128
 129   // A RegAlloc pass should override this to provide the allocation heuristics.
 130   // Each call must guarantee forward progess by returning an available PhysReg
 131   // or new set of split live virtual registers. It is up to the splitter to
 132   // converge quickly toward fully spilled live ranges.
 133   virtual unsigned selectOrSplit(LiveInterval &lvr,
 134                                  SmallVectorImpl<LiveInterval*> &splitLVRs) = 0;
 135
 136   // A RegAlloc pass should call this when PassManager releases its memory.
 137   virtual void releaseMemory();
 138
 139   // Helper for checking interference between a live virtual register and a
 140   // physical register, including all its register aliases. If an interference
 141   // exists, return the interfering register, which may be preg or an alias.
 142   unsigned checkPhysRegInterference(LiveInterval& lvr, unsigned preg);
 143
 144   // Helper for spilling all live virtual registers currently unified under preg
 145   // that interfere with the most recently queried lvr.  Return true if spilling
 146   // was successful, and append any new spilled/split intervals to splitLVRs.
 147   bool spillInterferences(LiveInterval &lvr, unsigned preg,
 148                           SmallVectorImpl<LiveInterval*> &splitLVRs);
 149
 150 #ifndef NDEBUG
 151   // Verify each LiveIntervalUnion.
 152   void verify();
 153 #endif
 154
 155 private:
 156   void seedLiveVirtRegs(LiveVirtRegQueue &lvrQ);
 157
 158   void spillReg(LiveInterval &lvr, unsigned reg,
 159                 SmallVectorImpl<LiveInterval*> &splitLVRs);
 160 };
 161
 162 } // end namespace llvm
 163
 164 #endif // !defined(LLVM_CODEGEN_REGALLOCBASE)