- SpillerInstance.reset(0);
- RegAllocBase::releaseMemory();
-}
-
-#ifndef NDEBUG
-// Verify each LiveIntervalUnion.
-void RegAllocBase::verify() {
- LiveVirtRegBitSet VisitedVRegs;
- OwningArrayPtr<LiveVirtRegBitSet>
- unionVRegs(new LiveVirtRegBitSet[PhysReg2LiveUnion.numRegs()]);
-
- // Verify disjoint unions.
- for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) {
- DEBUG(PhysicalRegisterDescription PRD(TRI);
- PhysReg2LiveUnion[PhysReg].dump(&PRD));
- LiveVirtRegBitSet &VRegs = unionVRegs[PhysReg];
- PhysReg2LiveUnion[PhysReg].verify(VRegs);
- // Union + intersection test could be done efficiently in one pass, but
- // don't add a method to SparseBitVector unless we really need it.
- assert(!VisitedVRegs.intersects(VRegs) && "vreg in multiple unions");
- VisitedVRegs |= VRegs;
- }
-
- // Verify vreg coverage.
- for (LiveIntervals::iterator liItr = LIS->begin(), liEnd = LIS->end();
- liItr != liEnd; ++liItr) {
- unsigned reg = liItr->first;
- if (TargetRegisterInfo::isPhysicalRegister(reg)) continue;
- if (!VRM->hasPhys(reg)) continue; // spilled?
- unsigned PhysReg = VRM->getPhys(reg);
- if (!unionVRegs[PhysReg].test(reg)) {
- dbgs() << "LiveVirtReg " << reg << " not in union " <<
- TRI->getName(PhysReg) << "\n";
- llvm_unreachable("unallocated live vreg");
- }
- }
- // FIXME: I'm not sure how to verify spilled intervals.
-}
-#endif //!NDEBUG
-
-//===----------------------------------------------------------------------===//
-// RegAllocBase Implementation
-//===----------------------------------------------------------------------===//
-
-// Instantiate a LiveIntervalUnion for each physical register.
-void RegAllocBase::LiveUnionArray::init(LiveIntervalUnion::Allocator &allocator,
- unsigned NRegs) {
- NumRegs = NRegs;
- Array =
- static_cast<LiveIntervalUnion*>(malloc(sizeof(LiveIntervalUnion)*NRegs));
- for (unsigned r = 0; r != NRegs; ++r)
- new(Array + r) LiveIntervalUnion(r, allocator);
-}
-
-void RegAllocBase::init(const TargetRegisterInfo &tri, VirtRegMap &vrm,
- LiveIntervals &lis) {
- TRI = &tri;
- VRM = &vrm;
- LIS = &lis;
- PhysReg2LiveUnion.init(UnionAllocator, TRI->getNumRegs());
- // Cache an interferece query for each physical reg
- Queries.reset(new LiveIntervalUnion::Query[PhysReg2LiveUnion.numRegs()]);
-}
-
-void RegAllocBase::LiveUnionArray::clear() {
- if (!Array)
- return;
- for (unsigned r = 0; r != NumRegs; ++r)
- Array[r].~LiveIntervalUnion();
- free(Array);
- NumRegs = 0;
- Array = 0;
-}
-
-void RegAllocBase::releaseMemory() {
- PhysReg2LiveUnion.clear();
-}
-
-namespace llvm {
-/// This class defines a queue of live virtual registers prioritized by spill
-/// weight. The heaviest vreg is popped first.
-///
-/// Currently, this is trivial wrapper that gives us an opaque type in the
-/// header, but we may later give it a virtual interface for register allocators
-/// to override the priority queue comparator.
-class LiveVirtRegQueue {
- typedef std::priority_queue
- <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority>
- PriorityQ;
- PriorityQ PQ;
-
-public:
- // Is the queue empty?
- bool empty() { return PQ.empty(); }
-
- // Get the highest priority lvr (top + pop)
- LiveInterval *get() {
- LiveInterval *VirtReg = PQ.top();
- PQ.pop();
- return VirtReg;
- }
- // Add this lvr to the queue
- void push(LiveInterval *VirtReg) {
- PQ.push(VirtReg);
- }
-};
-} // end namespace llvm
-
-// 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.
-void RegAllocBase::seedLiveVirtRegs(LiveVirtRegQueue &VirtRegQ) {
- for (LiveIntervals::iterator I = LIS->begin(), E = LIS->end(); I != E; ++I) {
- unsigned RegNum = I->first;
- LiveInterval &VirtReg = *I->second;
- if (TargetRegisterInfo::isPhysicalRegister(RegNum)) {
- PhysReg2LiveUnion[RegNum].unify(VirtReg);
- }
- else {
- VirtRegQ.push(&VirtReg);
- }
- }
-}
-
-// Top-level driver to manage the queue of unassigned VirtRegs and call the
-// selectOrSplit implementation.
-void RegAllocBase::allocatePhysRegs() {
-
- // Push each vreg onto a queue or "precolor" by adding it to a physreg union.
- LiveVirtRegQueue VirtRegQ;
- seedLiveVirtRegs(VirtRegQ);
-
- // Continue assigning vregs one at a time to available physical registers.
- while (!VirtRegQ.empty()) {
- // Pop the highest priority vreg.
- LiveInterval *VirtReg = VirtRegQ.get();
-
- // selectOrSplit requests the allocator to return an available physical
- // register if possible and populate a list of new live intervals that
- // result from splitting.
- typedef SmallVector<LiveInterval*, 4> VirtRegVec;
- VirtRegVec SplitVRegs;
- unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs);
-
- if (AvailablePhysReg) {
- DEBUG(dbgs() << "allocating: " << TRI->getName(AvailablePhysReg) <<
- " " << *VirtReg << '\n');
- assert(!VRM->hasPhys(VirtReg->reg) && "duplicate vreg in union");
- VRM->assignVirt2Phys(VirtReg->reg, AvailablePhysReg);
- PhysReg2LiveUnion[AvailablePhysReg].unify(*VirtReg);
- }
- for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end();
- I != E; ++I) {
- LiveInterval* SplitVirtReg = *I;
- if (SplitVirtReg->empty()) continue;
- DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");
- assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) &&
- "expect split value in virtual register");
- VirtRegQ.push(SplitVirtReg);
- }
- }