X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocBase.h;h=659b8f505a229fd277a69726cd519a64e7f9852b;hb=5fc0e47e6b56d8236d2095efa3f3af4bd442f961;hp=8c7e5f53b824ce46d01b28e13333d5ce2e8cb474;hpb=2710638db2eb84cd7eefb8bb9a1b7e5c49413d45;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocBase.h b/lib/CodeGen/RegAllocBase.h index 8c7e5f53b82..659b8f505a2 100644 --- a/lib/CodeGen/RegAllocBase.h +++ b/lib/CodeGen/RegAllocBase.h @@ -34,12 +34,11 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_REGALLOCBASE -#define LLVM_CODEGEN_REGALLOCBASE +#ifndef LLVM_LIB_CODEGEN_REGALLOCBASE_H +#define LLVM_LIB_CODEGEN_REGALLOCBASE_H -#include "llvm/ADT/OwningPtr.h" -#include "LiveIntervalUnion.h" -#include +#include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/RegisterClassInfo.h" namespace llvm { @@ -47,135 +46,67 @@ template class SmallVectorImpl; class TargetRegisterInfo; class VirtRegMap; class LiveIntervals; +class LiveRegMatrix; class Spiller; -// Forward declare a priority queue of live virtual registers. If an -// implementation needs to prioritize by anything other than spill weight, then -// this will become an abstract base class with virtual calls to push/get. -class LiveVirtRegQueue; - /// RegAllocBase provides the register allocation driver and interface that can /// be extended to add interesting heuristics. /// /// Register allocators must override the selectOrSplit() method to implement -/// live range splitting. They may also override getPriority() which otherwise -/// defaults to the spill weight computed by CalculateSpillWeights. +/// live range splitting. They must also override enqueue/dequeue to provide an +/// assignment order. class RegAllocBase { - LiveIntervalUnion::Allocator UnionAllocator; + virtual void anchor(); protected: - // Array of LiveIntervalUnions indexed by physical register. - class LiveUnionArray { - unsigned NumRegs; - LiveIntervalUnion *Array; - public: - LiveUnionArray(): NumRegs(0), Array(0) {} - ~LiveUnionArray() { clear(); } - - unsigned numRegs() const { return NumRegs; } - - void init(LiveIntervalUnion::Allocator &, unsigned NRegs); - - void clear(); - - LiveIntervalUnion& operator[](unsigned PhysReg) { - assert(PhysReg < NumRegs && "physReg out of bounds"); - return Array[PhysReg]; - } - }; - const TargetRegisterInfo *TRI; MachineRegisterInfo *MRI; VirtRegMap *VRM; LiveIntervals *LIS; - LiveUnionArray PhysReg2LiveUnion; - - // Current queries, one per physreg. They must be reinitialized each time we - // query on a new live virtual register. - OwningArrayPtr Queries; + LiveRegMatrix *Matrix; + RegisterClassInfo RegClassInfo; - RegAllocBase(): TRI(0), MRI(0), VRM(0), LIS(0) {} + RegAllocBase() + : TRI(nullptr), MRI(nullptr), VRM(nullptr), LIS(nullptr), Matrix(nullptr) {} virtual ~RegAllocBase() {} // A RegAlloc pass should call this before allocatePhysRegs. - void init(VirtRegMap &vrm, LiveIntervals &lis); - - // Get an initialized query to check interferences between lvr and preg. Note - // that Query::init must be called at least once for each physical register - // before querying a new live virtual register. This ties Queries and - // PhysReg2LiveUnion together. - LiveIntervalUnion::Query &query(LiveInterval &VirtReg, unsigned PhysReg) { - Queries[PhysReg].init(&VirtReg, &PhysReg2LiveUnion[PhysReg]); - return Queries[PhysReg]; - } + void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat); // The top-level driver. The output is a VirtRegMap that us updated with // physical register assignments. - // - // If an implementation wants to override the LiveInterval comparator, we - // should modify this interface to allow passing in an instance derived from - // LiveVirtRegQueue. void allocatePhysRegs(); // Get a temporary reference to a Spiller instance. virtual Spiller &spiller() = 0; - // getPriority - Calculate the allocation priority for VirtReg. - // Virtual registers with higher priorities are allocated first. - virtual float getPriority(LiveInterval *LI) = 0; + /// 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 live virtual registers. It is up to the splitter to // converge quickly toward fully spilled live ranges. virtual unsigned selectOrSplit(LiveInterval &VirtReg, - SmallVectorImpl &splitLVRs) = 0; - - // A RegAlloc pass should call this when PassManager releases its memory. - virtual void releaseMemory(); - - // Helper for checking interference between a live virtual register and a - // physical register, including all its register aliases. If an interference - // exists, return the interfering register, which may be preg or an alias. - unsigned checkPhysRegInterference(LiveInterval& VirtReg, unsigned PhysReg); - - /// assign - Assign VirtReg to PhysReg. - /// This should not be called from selectOrSplit for the current register. - void assign(LiveInterval &VirtReg, unsigned PhysReg); - - /// unassign - Undo a previous assignment of VirtReg to PhysReg. - /// This can be invoked from selectOrSplit, but be careful to guarantee that - /// allocation is making progress. - void unassign(LiveInterval &VirtReg, unsigned PhysReg); - - // Helper for spilling all live virtual registers currently unified under preg - // that interfere with the most recently queried lvr. Return true if spilling - // was successful, and append any new spilled/split intervals to splitLVRs. - bool spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, - SmallVectorImpl &SplitVRegs); - - /// addMBBLiveIns - Add physreg liveins to basic blocks. - void addMBBLiveIns(MachineFunction *); - -#ifndef NDEBUG - // Verify each LiveIntervalUnion. - void verify(); -#endif + SmallVectorImpl &splitLVRs) = 0; // Use this group name for NamedRegionTimer. - static const char *TimerGroupName; + static const char TimerGroupName[]; + + /// Method called when the allocator is about to remove a LiveInterval. + virtual void aboutToRemoveInterval(LiveInterval &LI) {} public: /// VerifyEnabled - True when -verify-regalloc is given. static bool VerifyEnabled; private: - void seedLiveVirtRegs(std::priority_queue >&); - - void spillReg(LiveInterval &VirtReg, unsigned PhysReg, - SmallVectorImpl &SplitVRegs); + void seedLiveRegs(); }; } // end namespace llvm -#endif // !defined(LLVM_CODEGEN_REGALLOCBASE) +#endif