RegAllocBase.h revision 14e8d71cc945034d4ee6e76be00e00f14efac62f
114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick//===-- RegAllocBase.h - basic regalloc interface and driver --*- C++ -*---===// 214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// The LLVM Compiler Infrastructure 414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// This file is distributed under the University of Illinois Open Source 614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// License. See LICENSE.TXT for details. 714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick//===----------------------------------------------------------------------===// 914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 1014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// This file defines the RegAllocBase class, which is the skeleton of a basic 1114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// register allocation algorithm and interface for extending it. It provides the 1214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// building blocks on which to construct other experimental allocators and test 1314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// the validity of two principles: 1414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 1514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// - If virtual and physical register liveness is modeled using intervals, then 1614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// on-the-fly interference checking is cheap. Furthermore, interferences can be 1714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// lazily cached and reused. 1814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 1914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// - Register allocation complexity, and generated code performance is 2014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// determined by the effectiveness of live range splitting rather than optimal 2114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// coloring. 2214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 2314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// Following the first principle, interfering checking revolves around the 2414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// LiveIntervalUnion data structure. 2514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 2614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// To fulfill the second principle, the basic allocator provides a driver for 2714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// incremental splitting. It essentially punts on the problem of register 2814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// coloring, instead driving the assignment of virtual to physical registers by 2914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// the cost of splitting. The basic allocator allows for heuristic reassignment 3014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// of registers, if a more sophisticated allocator chooses to do that. 3114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 3214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// This framework provides a way to engineer the compile time vs. code 3314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// quality trade-off without relying a particular theoretical solver. 3414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// 3514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick//===----------------------------------------------------------------------===// 3614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 3714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick#ifndef LLVM_CODEGEN_REGALLOCBASE 3814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick#define LLVM_CODEGEN_REGALLOCBASE 3914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 4014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick#include "LiveIntervalUnion.h" 4114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick#include "VirtRegMap.h" 4214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick#include "llvm/CodeGen/LiveIntervalAnalysis.h" 4314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick#include "llvm/Target/TargetRegisterInfo.h" 4414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick#include "llvm/ADT/OwningPtr.h" 4514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick#include <vector> 4614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick#include <queue> 4714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 4814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Tricknamespace llvm { 4914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 5014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trickclass VirtRegMap; 5114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 5214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick/// RegAllocBase provides the register allocation driver and interface that can 5314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick/// be extended to add interesting heuristics. 5414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick/// 5514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick/// More sophisticated allocators must override the selectOrSplit() method to 5614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick/// implement live range splitting and must specify a comparator to determine 5714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick/// register assignment priority. LessSpillWeightPriority is provided as a 5814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick/// standard comparator. 5914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trickclass RegAllocBase { 6014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trickprotected: 6114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick typedef SmallVector<LiveInterval*, 4> LiveVirtRegs; 6214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick typedef LiveVirtRegs::iterator LVRIter; 6314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 6414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // Array of LiveIntervalUnions indexed by physical register. 6514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick class LIUArray { 6614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick unsigned nRegs_; 6714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick OwningArrayPtr<LiveIntervalUnion> array_; 6814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick public: 6914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick LIUArray(): nRegs_(0) {} 7014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 7114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick unsigned numRegs() const { return nRegs_; } 7214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 7314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick void init(unsigned nRegs); 7414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 7514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick void clear(); 7614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 7714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick LiveIntervalUnion& operator[](unsigned physReg) { 7814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick assert(physReg < nRegs_ && "physReg out of bounds"); 7914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick return array_[physReg]; 8014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick } 8114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick }; 8214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 8314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick const TargetRegisterInfo *tri_; 8414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick VirtRegMap *vrm_; 8514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick LiveIntervals *lis_; 8614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick LIUArray physReg2liu_; 8714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 8814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick RegAllocBase(): tri_(0), vrm_(0), lis_(0) {} 8914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 9014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // A RegAlloc pass should call this before allocatePhysRegs. 9114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick void init(const TargetRegisterInfo &tri, VirtRegMap &vrm, LiveIntervals &lis); 9214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 9314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // The top-level driver. Specialize with the comparator that determines the 9414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // priority of assigning live virtual registers. The output is a VirtRegMap 9514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // that us updated with physical register assignments. 9614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick template<typename LICompare> 9714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick void allocatePhysRegs(LICompare liCompare); 9814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 9914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // A RegAlloc pass should override this to provide the allocation heuristics. 10014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // Each call must guarantee forward progess by returning an available 10114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // PhysReg or new set of split LiveVirtRegs. It is up to the splitter to 10214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // converge quickly toward fully spilled live ranges. 10314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick virtual unsigned selectOrSplit(LiveInterval &lvr, 10414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick LiveVirtRegs &splitLVRs) = 0; 10514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 10614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // A RegAlloc pass should call this when PassManager releases its memory. 10714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick virtual void releaseMemory(); 10814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 10914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // Helper for checking interference between a live virtual register and a 11014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick // physical register, including all its register aliases. 11114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick bool checkPhysRegInterference(LiveIntervalUnion::Query &query, unsigned preg); 11214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 11314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trickprivate: 11414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick template<typename PQ> 11514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick void seedLiveVirtRegs(PQ &lvrQ); 11614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick}; 11714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 11814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// Heuristic that determines the priority of assigning virtual to physical 11914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// registers. The main impact of the heuristic is expected to be compile time. 12014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// The default is to simply compare spill weights. 12114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trickstruct LessSpillWeightPriority 12214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick : public std::binary_function<LiveInterval,LiveInterval, bool> { 12314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick bool operator()(const LiveInterval *left, const LiveInterval *right) const { 12414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick return left->weight < right->weight; 12514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick } 12614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick}; 12714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 12814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// Visit all the live virtual registers. If they are already assigned to a 12914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// physical register, unify them with the corresponding LiveIntervalUnion, 13014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// otherwise push them on the priority queue for later assignment. 13114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Tricktemplate<typename PQ> 13214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trickvoid RegAllocBase::seedLiveVirtRegs(PQ &lvrQ) { 13314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end(); 13414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick liItr != liEnd; ++liItr) { 13514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick unsigned reg = liItr->first; 13614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick LiveInterval &li = *liItr->second; 13714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick if (TargetRegisterInfo::isPhysicalRegister(reg)) { 13814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick physReg2liu_[reg].unify(li); 13914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick } 14014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick else { 14114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick lvrQ.push(&li); 14214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick } 14314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick } 14414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick} 14514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 14614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// Top-level driver to manage the queue of unassigned LiveVirtRegs and call the 14714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick// selectOrSplit implementation. 14814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Tricktemplate<typename LICompare> 14914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trickvoid RegAllocBase::allocatePhysRegs(LICompare liCompare) { 15014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick typedef std::priority_queue 15114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick <LiveInterval*, std::vector<LiveInterval*>, LICompare> LiveVirtRegQueue; 15214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 15314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick LiveVirtRegQueue lvrQ(liCompare); 15414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick seedLiveVirtRegs(lvrQ); 15514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick while (!lvrQ.empty()) { 15614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick LiveInterval *lvr = lvrQ.top(); 15714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick lvrQ.pop(); 15814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick LiveVirtRegs splitLVRs; 15914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs); 16014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick if (availablePhysReg) { 16114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick assert(splitLVRs.empty() && "inconsistent splitting"); 16214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions"); 16314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick vrm_->assignVirt2Phys(lvr->reg, availablePhysReg); 16414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick physReg2liu_[availablePhysReg].unify(*lvr); 16514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick } 16614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick else { 16714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick for (LVRIter lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end(); 16814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick lvrI != lvrEnd; ++lvrI ) { 16914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) && 17014e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick "expect split value in virtual register"); 17114e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick lvrQ.push(*lvrI); 17214e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick } 17314e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick } 17414e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick } 17514e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick} 17614e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 17714e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick} // end namespace llvm 17814e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick 17914e8d71cc945034d4ee6e76be00e00f14efac62fAndrew Trick#endif // !defined(LLVM_CODEGEN_REGALLOCBASE) 180