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
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 <queue>
#include <memory>
#include <cmath>
+#include <iostream>
+
using namespace llvm;
STATISTIC(NumIters , "Number of iterations performed");
@@ -310,6 +312,93 @@
static RegisterPass<RALinScan>
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 @@
if (!rewriter_.get()) rewriter_.reset(createVirtRegRewriter());
if (NewSpillFramework) {
- spiller_.reset(createSpiller(mf_, li_, vrm_));
+ spiller_.reset(createSpiller(mf_, li_, ls_, vrm_));
}
- else {
- spiller_.reset(0);
- }
-
+
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 @@
NextReloadMap.clear();
DowngradedRegs.clear();
DowngradeMap.clear();
+ spiller_.reset(0);
return true;
}
@@ -1127,8 +1218,7 @@
if (!NewSpillFramework) {
added = li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_);
- }
- else {
+ } else {
added = spiller_->spill(cur);
}
@@ -1192,7 +1282,9 @@
// 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 @@
// mark our rollback point.
std::vector<LiveInterval*> 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<LiveInterval*> 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<LiveInterval*> 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