Keep track of the number of positively biased nodes when adding constraints.
If there are no positive nodes, the algorithm can be aborted early.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129021 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp
index 4e8891f..31729ec 100644
--- a/lib/CodeGen/RegAllocGreedy.cpp
+++ b/lib/CodeGen/RegAllocGreedy.cpp
@@ -772,6 +772,7 @@
SpillPlacer->prepare(LiveBundles);
SpillPlacer->addConstraints(SplitConstraints);
+ DEBUG(dbgs() << ", " << SpillPlacer->getPositiveNodes() << " biased nodes");
SpillPlacer->finish();
// No live bundles, defer to splitSingleBlocks().
diff --git a/lib/CodeGen/SpillPlacement.cpp b/lib/CodeGen/SpillPlacement.cpp
index d648d5a..0ccb93f 100644
--- a/lib/CodeGen/SpillPlacement.cpp
+++ b/lib/CodeGen/SpillPlacement.cpp
@@ -134,10 +134,14 @@
}
/// addBias - Bias this node from an ingoing[0] or outgoing[1] link.
- void addBias(float w, bool out) {
+ /// Return the change to the total number of positive biases.
+ int addBias(float w, bool out) {
// Normalize w relative to all connected blocks from that direction.
w /= Frequency[out];
+ int Before = Bias > 0;
Bias += w;
+ int After = Bias > 0;
+ return After - Before;
}
/// update - Recompute Value from Bias and Links. Return true when node
@@ -237,14 +241,14 @@
if (I->Entry != DontCare) {
unsigned ib = bundles->getBundle(I->Number, 0);
activate(ib);
- nodes[ib].addBias(Freq * Bias[I->Entry], 1);
+ PositiveNodes += nodes[ib].addBias(Freq * Bias[I->Entry], 1);
}
// Live-out from block?
if (I->Exit != DontCare) {
unsigned ob = bundles->getBundle(I->Number, 1);
activate(ob);
- nodes[ob].addBias(Freq * Bias[I->Exit], 0);
+ PositiveNodes += nodes[ob].addBias(Freq * Bias[I->Exit], 0);
}
}
}
@@ -292,6 +296,7 @@
ActiveNodes = &RegBundles;
ActiveNodes->clear();
ActiveNodes->resize(bundles->getNumBundles());
+ PositiveNodes = 0;
}
bool
diff --git a/lib/CodeGen/SpillPlacement.h b/lib/CodeGen/SpillPlacement.h
index d1c6ceb..a67785d 100644
--- a/lib/CodeGen/SpillPlacement.h
+++ b/lib/CodeGen/SpillPlacement.h
@@ -49,6 +49,9 @@
// caller.
BitVector *ActiveNodes;
+ // The number of active nodes with a positive bias.
+ unsigned PositiveNodes;
+
// Block frequencies are computed once. Indexed by block number.
SmallVector<float, 4> BlockFrequency;
@@ -91,6 +94,10 @@
/// out, but not live in.
void addConstraints(ArrayRef<BlockConstraint> LiveBlocks);
+ /// getPositiveNodes - Return the total number of graph nodes with a positive
+ /// bias after adding constraints.
+ unsigned getPositiveNodes() const { return PositiveNodes; }
+
/// finish - Compute the optimal spill code placement given the
/// constraints. No MustSpill constraints will be violated, and the smallest
/// possible number of PrefX constraints will be violated, weighted by