RegAllocBase.h revision 8ce8b809ef4aec7f09f2d55e37f317fb3623fd25
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 48namespace llvm { 49 50class 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. 59class RegAllocBase { 60protected: 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 113private: 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. 121struct 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. 131template<typename PQ> 132void 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. 148template<typename LICompare> 149void 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) 180