-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();
-}
-
-// 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(std::priority_queue<std::pair<float, unsigned> > &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(std::make_pair(getPriority(&VirtReg), RegNum));
- }
-}
-
-// 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.
- std::priority_queue<std::pair<float, unsigned> > VirtRegQ;
- seedLiveVirtRegs(VirtRegQ);
-
- // Continue assigning vregs one at a time to available physical registers.
- while (!VirtRegQ.empty()) {
- // Pop the highest priority vreg.
- LiveInterval &VirtReg = LIS->getInterval(VirtRegQ.top().second);
- VirtRegQ.pop();
-
- // selectOrSplit requests the allocator to return an available physical
- // register if possible and populate a list of new live intervals that
- // result from splitting.
- DEBUG(dbgs() << "\nselectOrSplit " << MRI->getRegClass(VirtReg.reg)->getName()
- << ':' << VirtReg << '\n');
- typedef SmallVector<LiveInterval*, 4> VirtRegVec;
- VirtRegVec SplitVRegs;
- unsigned AvailablePhysReg = selectOrSplit(VirtReg, SplitVRegs);
-
- if (AvailablePhysReg) {
- DEBUG(dbgs() << "allocating: " << TRI->getName(AvailablePhysReg)
- << " for " << 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(std::make_pair(getPriority(SplitVirtReg),
- SplitVirtReg->reg));
- }
- }
-}
-
-// 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();
-}