From f41538d1b54f55e8900394929b50f7ce3e61125f Mon Sep 17 00:00:00 2001 From: Lang Hames Date: Tue, 2 Jun 2009 16:53:25 +0000 Subject: Update to in-place spilling framework. Includes live interval scaling and trivial rewriter. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72729 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/RegAllocLinearScan.cpp | 141 ++++++++++++++++++++++++++++++++++--- 1 file changed, 132 insertions(+), 9 deletions(-) (limited to 'lib/CodeGen/RegAllocLinearScan.cpp') diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index ac6ab32..ee118de 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -40,6 +40,8 @@ #include #include #include +#include + using namespace llvm; STATISTIC(NumIters , "Number of iterations performed"); @@ -310,6 +312,93 @@ namespace { static RegisterPass X("linearscan-regalloc", "Linear Scan Register Allocator"); +bool validateRegAlloc(MachineFunction *mf, LiveIntervals *lis, + VirtRegMap *vrm) { + + MachineRegisterInfo *mri = &mf->getRegInfo(); + const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo(); + bool allocationValid = true; + + + for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); + itr != end; ++itr) { + + LiveInterval *li = itr->second; + + if (TargetRegisterInfo::isPhysicalRegister(li->reg)) { + continue; + } + + if (vrm->hasPhys(li->reg)) { + const TargetRegisterClass *trc = mri->getRegClass(li->reg); + + if (lis->hasInterval(vrm->getPhys(li->reg))) { + if (li->overlaps(lis->getInterval(vrm->getPhys(li->reg)))) { + std::cerr << "vreg " << li->reg << " overlaps its assigned preg " + << vrm->getPhys(li->reg) << "(" << tri->getName(vrm->getPhys(li->reg)) << ")\n"; + } + } + + TargetRegisterClass::iterator fReg = + std::find(trc->allocation_order_begin(*mf), trc->allocation_order_end(*mf), + vrm->getPhys(li->reg)); + + if (fReg == trc->allocation_order_end(*mf)) { + std::cerr << "preg " << vrm->getPhys(li->reg) + << "(" << tri->getName(vrm->getPhys(li->reg)) << ") is not in the allocation set for vreg " + << li->reg << "\n"; + allocationValid &= false; + } + } + else { + std::cerr << "No preg for vreg " << li->reg << "\n"; + // What about conflicting loads/stores? + continue; + } + + for (LiveIntervals::iterator itr2 = next(itr); itr2 != end; ++itr2) { + + LiveInterval *li2 = itr2->second; + + if (li2->empty()) + continue; + + if (TargetRegisterInfo::isPhysicalRegister(li2->reg)) { + if (li->overlaps(*li2)) { + if (vrm->getPhys(li->reg) == li2->reg || + tri->areAliases(vrm->getPhys(li->reg), li2->reg)) { + std::cerr << "vreg " << li->reg << " overlaps preg " + << li2->reg << "(" << tri->getName(li2->reg) << ") which aliases " + << vrm->getPhys(li->reg) << "(" << tri->getName(vrm->getPhys(li->reg)) << ")\n"; + allocationValid &= false; + } + } + } + else { + + if (!vrm->hasPhys(li2->reg)) { + continue; + } + + if (li->overlaps(*li2)) { + if (vrm->getPhys(li->reg) == vrm->getPhys(li2->reg) || + tri->areAliases(vrm->getPhys(li->reg), vrm->getPhys(li2->reg))) { + std::cerr << "vreg " << li->reg << " (preg " << vrm->getPhys(li->reg) + << ") overlaps vreg " << li2->reg << " (preg " << vrm->getPhys(li2->reg) + << ") and " << vrm->getPhys(li->reg) << " aliases " << vrm->getPhys(li2->reg) << "\n"; + allocationValid &= false; + } + } + } + } + + } + + return allocationValid; + +} + + void RALinScan::ComputeRelatedRegClasses() { // First pass, add all reg classes to the union, and determine at least one // reg class that each register is in. @@ -430,16 +519,17 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) { if (!rewriter_.get()) rewriter_.reset(createVirtRegRewriter()); if (NewSpillFramework) { - spiller_.reset(createSpiller(mf_, li_, vrm_)); - } - else { - spiller_.reset(0); + spiller_.reset(createSpiller(mf_, li_, ls_, vrm_)); } - + initIntervalSets(); linearScan(); + if (NewSpillFramework) { + bool allocValid = validateRegAlloc(mf_, li_, vrm_); + } + // Rewrite spill code and update the PhysRegsUsed set. rewriter_->runOnMachineFunction(*mf_, *vrm_, li_); @@ -454,6 +544,7 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) { NextReloadMap.clear(); DowngradedRegs.clear(); DowngradeMap.clear(); + spiller_.reset(0); return true; } @@ -1127,8 +1218,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) if (!NewSpillFramework) { added = li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_); - } - else { + } else { added = spiller_->spill(cur); } @@ -1192,7 +1282,9 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // The earliest start of a Spilled interval indicates up to where // in handled we need to roll back + unsigned earliestStart = cur->beginNumber(); + LiveInterval *earliestStartInterval = cur; // Spill live intervals of virtual regs mapped to the physical register we // want to clear (and its aliases). We only spill those that overlap with the @@ -1201,17 +1293,48 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // mark our rollback point. std::vector added; while (!spillIs.empty()) { + bool epicFail = false; LiveInterval *sli = spillIs.back(); spillIs.pop_back(); DOUT << "\t\t\tspilling(a): " << *sli << '\n'; earliestStart = std::min(earliestStart, sli->beginNumber()); - std::vector newIs = - li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_); + earliestStartInterval = + (earliestStartInterval->beginNumber() < sli->beginNumber()) ? + earliestStartInterval : sli; + + if (earliestStartInterval->beginNumber()!=earliestStart) { + epicFail |= true; + std::cerr << "What the 1 - " + << "earliestStart = " << earliestStart + << "earliestStartInterval = " << earliestStartInterval->beginNumber() + << "\n"; + } + + std::vector newIs; + if (!NewSpillFramework) { + newIs = li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_); + } else { + newIs = spiller_->spill(sli); + } addStackInterval(sli, ls_, li_, mri_, *vrm_); std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); spilled.insert(sli->reg); + + if (earliestStartInterval->beginNumber()!=earliestStart) { + epicFail |= true; + std::cerr << "What the 2 - " + << "earliestStart = " << earliestStart + << "earliestStartInterval = " << earliestStartInterval->beginNumber() + << "\n"; + } + + if (epicFail) { + //abort(); + } } + earliestStart = earliestStartInterval->beginNumber(); + DOUT << "\t\trolling back to: " << earliestStart << '\n'; // Scan handled in reverse order up to the earliest start of a -- cgit v1.1