-void RegAllocBase::init(const TargetRegisterInfo &tri, VirtRegMap &vrm,
- LiveIntervals &lis) {
- TRI = &tri;
- VRM = &vrm;
- LIS = &lis;
- PhysReg2LiveUnion.init(TRI->getNumRegs());
- // Cache an interferece query for each physical reg
- Queries.reset(new LiveIntervalUnion::Query[PhysReg2LiveUnion.numRegs()]);
-}
-
-void RegAllocBase::LiveUnionArray::clear() {
- NumRegs = 0;
- Array.reset(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);
- }
- }
-}
-
-// Check if this live virtual register interferes with a physical register. If
-// not, then check for interference on each register that aliases with the
-// physical register. Return the interfering register.
-unsigned RegAllocBase::checkPhysRegInterference(LiveInterval &VirtReg,
- unsigned PhysReg) {
- if (query(VirtReg, PhysReg).checkInterference())
- return PhysReg;
- for (const unsigned *AliasI = TRI->getAliasSet(PhysReg); *AliasI; ++AliasI) {
- if (query(VirtReg, *AliasI).checkInterference())
- return *AliasI;
- }
- return 0;
-}
-
-// Helper for spillInteferences() that spills all interfering vregs currently
-// assigned to this physical register.
-void RegAllocBase::spillReg(LiveInterval& VirtReg, unsigned PhysReg,
- SmallVectorImpl<LiveInterval*> &SplitVRegs) {
- LiveIntervalUnion::Query &Q = query(VirtReg, PhysReg);
- assert(Q.seenAllInterferences() && "need collectInterferences()");
- const SmallVectorImpl<LiveInterval*> &PendingSpills = Q.interferingVRegs();
-
- for (SmallVectorImpl<LiveInterval*>::const_iterator I = PendingSpills.begin(),
- E = PendingSpills.end(); I != E; ++I) {
- LiveInterval &SpilledVReg = **I;
- DEBUG(dbgs() << "extracting from " <<
- TRI->getName(PhysReg) << " " << SpilledVReg << '\n');
-
- // Deallocate the interfering vreg by removing it from the union.
- // A LiveInterval instance may not be in a union during modification!
- PhysReg2LiveUnion[PhysReg].extract(SpilledVReg);
-
- // Clear the vreg assignment.
- VRM->clearVirt(SpilledVReg.reg);
-
- // Spill the extracted interval.
- spiller().spill(&SpilledVReg, SplitVRegs, PendingSpills);
- }
- // After extracting segments, the query's results are invalid. But keep the
- // contents valid until we're done accessing pendingSpills.
- Q.clear();
-}