X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocBase.h;h=659b8f505a229fd277a69726cd519a64e7f9852b;hb=6dc4b28cd41d6708d6b5c6cfe14355b99ce0e1ed;hp=a972fbf11082647039827eed650e5b31d918a7c4;hpb=14e8d71cc945034d4ee6e76be00e00f14efac62f;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocBase.h b/lib/CodeGen/RegAllocBase.h index a972fbf1108..659b8f505a2 100644 --- a/lib/CodeGen/RegAllocBase.h +++ b/lib/CodeGen/RegAllocBase.h @@ -11,11 +11,11 @@ // register allocation algorithm and interface for extending it. It provides the // building blocks on which to construct other experimental allocators and test // the validity of two principles: -// +// // - If virtual and physical register liveness is modeled using intervals, then // on-the-fly interference checking is cheap. Furthermore, interferences can be // lazily cached and reused. -// +// // - Register allocation complexity, and generated code performance is // determined by the effectiveness of live range splitting rather than optimal // coloring. @@ -30,150 +30,83 @@ // of registers, if a more sophisticated allocator chooses to do that. // // This framework provides a way to engineer the compile time vs. code -// quality trade-off without relying a particular theoretical solver. +// quality trade-off without relying on a particular theoretical solver. // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_REGALLOCBASE -#define LLVM_CODEGEN_REGALLOCBASE +#ifndef LLVM_LIB_CODEGEN_REGALLOCBASE_H +#define LLVM_LIB_CODEGEN_REGALLOCBASE_H -#include "LiveIntervalUnion.h" -#include "VirtRegMap.h" -#include "llvm/CodeGen/LiveIntervalAnalysis.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/ADT/OwningPtr.h" -#include -#include +#include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/RegisterClassInfo.h" namespace llvm { +template class SmallVectorImpl; +class TargetRegisterInfo; class VirtRegMap; +class LiveIntervals; +class LiveRegMatrix; +class Spiller; /// RegAllocBase provides the register allocation driver and interface that can /// be extended to add interesting heuristics. /// -/// More sophisticated allocators must override the selectOrSplit() method to -/// implement live range splitting and must specify a comparator to determine -/// register assignment priority. LessSpillWeightPriority is provided as a -/// standard comparator. +/// Register allocators must override the selectOrSplit() method to implement +/// live range splitting. They must also override enqueue/dequeue to provide an +/// assignment order. class RegAllocBase { + virtual void anchor(); protected: - typedef SmallVector LiveVirtRegs; - typedef LiveVirtRegs::iterator LVRIter; - - // Array of LiveIntervalUnions indexed by physical register. - class LIUArray { - unsigned nRegs_; - OwningArrayPtr array_; - public: - LIUArray(): nRegs_(0) {} - - unsigned numRegs() const { return nRegs_; } - - void init(unsigned nRegs); - - void clear(); - - LiveIntervalUnion& operator[](unsigned physReg) { - assert(physReg < nRegs_ && "physReg out of bounds"); - return array_[physReg]; - } - }; - - const TargetRegisterInfo *tri_; - VirtRegMap *vrm_; - LiveIntervals *lis_; - LIUArray physReg2liu_; - - RegAllocBase(): tri_(0), vrm_(0), lis_(0) {} + const TargetRegisterInfo *TRI; + MachineRegisterInfo *MRI; + VirtRegMap *VRM; + LiveIntervals *LIS; + LiveRegMatrix *Matrix; + RegisterClassInfo RegClassInfo; + + RegAllocBase() + : TRI(nullptr), MRI(nullptr), VRM(nullptr), LIS(nullptr), Matrix(nullptr) {} + + virtual ~RegAllocBase() {} // A RegAlloc pass should call this before allocatePhysRegs. - void init(const TargetRegisterInfo &tri, VirtRegMap &vrm, LiveIntervals &lis); + void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat); + + // The top-level driver. The output is a VirtRegMap that us updated with + // physical register assignments. + void allocatePhysRegs(); + + // Get a temporary reference to a Spiller instance. + virtual Spiller &spiller() = 0; - // The top-level driver. Specialize with the comparator that determines the - // priority of assigning live virtual registers. The output is a VirtRegMap - // that us updated with physical register assignments. - template - void allocatePhysRegs(LICompare liCompare); + /// enqueue - Add VirtReg to the priority queue of unassigned registers. + virtual void enqueue(LiveInterval *LI) = 0; + + /// dequeue - Return the next unassigned register, or NULL. + virtual LiveInterval *dequeue() = 0; // A RegAlloc pass should override this to provide the allocation heuristics. - // Each call must guarantee forward progess by returning an available - // PhysReg or new set of split LiveVirtRegs. It is up to the splitter to + // Each call must guarantee forward progess by returning an available PhysReg + // or new set of split live virtual registers. It is up to the splitter to // converge quickly toward fully spilled live ranges. - virtual unsigned selectOrSplit(LiveInterval &lvr, - LiveVirtRegs &splitLVRs) = 0; + virtual unsigned selectOrSplit(LiveInterval &VirtReg, + SmallVectorImpl &splitLVRs) = 0; - // A RegAlloc pass should call this when PassManager releases its memory. - virtual void releaseMemory(); + // Use this group name for NamedRegionTimer. + static const char TimerGroupName[]; - // Helper for checking interference between a live virtual register and a - // physical register, including all its register aliases. - bool checkPhysRegInterference(LiveIntervalUnion::Query &query, unsigned preg); - -private: - template - void seedLiveVirtRegs(PQ &lvrQ); -}; + /// Method called when the allocator is about to remove a LiveInterval. + virtual void aboutToRemoveInterval(LiveInterval &LI) {} -// Heuristic that determines the priority of assigning virtual to physical -// registers. The main impact of the heuristic is expected to be compile time. -// The default is to simply compare spill weights. -struct LessSpillWeightPriority - : public std::binary_function { - bool operator()(const LiveInterval *left, const LiveInterval *right) const { - return left->weight < right->weight; - } -}; +public: + /// VerifyEnabled - True when -verify-regalloc is given. + static bool VerifyEnabled; -// Visit all the live virtual registers. If they are already assigned to a -// physical register, unify them with the corresponding LiveIntervalUnion, -// otherwise push them on the priority queue for later assignment. -template -void RegAllocBase::seedLiveVirtRegs(PQ &lvrQ) { - for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end(); - liItr != liEnd; ++liItr) { - unsigned reg = liItr->first; - LiveInterval &li = *liItr->second; - if (TargetRegisterInfo::isPhysicalRegister(reg)) { - physReg2liu_[reg].unify(li); - } - else { - lvrQ.push(&li); - } - } -} - -// Top-level driver to manage the queue of unassigned LiveVirtRegs and call the -// selectOrSplit implementation. -template -void RegAllocBase::allocatePhysRegs(LICompare liCompare) { - typedef std::priority_queue - , LICompare> LiveVirtRegQueue; - - LiveVirtRegQueue lvrQ(liCompare); - seedLiveVirtRegs(lvrQ); - while (!lvrQ.empty()) { - LiveInterval *lvr = lvrQ.top(); - lvrQ.pop(); - LiveVirtRegs splitLVRs; - unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs); - if (availablePhysReg) { - assert(splitLVRs.empty() && "inconsistent splitting"); - assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions"); - vrm_->assignVirt2Phys(lvr->reg, availablePhysReg); - physReg2liu_[availablePhysReg].unify(*lvr); - } - else { - for (LVRIter lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end(); - lvrI != lvrEnd; ++lvrI ) { - assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) && - "expect split value in virtual register"); - lvrQ.push(*lvrI); - } - } - } -} +private: + void seedLiveRegs(); +}; } // end namespace llvm -#endif // !defined(LLVM_CODEGEN_REGALLOCBASE) +#endif