From 70d4370b47cdd375bbea98e50452789fe4f1af04 Mon Sep 17 00:00:00 2001
From: Jakob Stoklund Olesen <stoklund@2pi.dk>
Date: Wed, 6 Apr 2011 19:14:00 +0000
Subject: [PATCH] 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
---
 lib/CodeGen/RegAllocGreedy.cpp |  1 +
 lib/CodeGen/SpillPlacement.cpp | 11 ++++++++---
 lib/CodeGen/SpillPlacement.h   |  7 +++++++
 3 files changed, 16 insertions(+), 3 deletions(-)

diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp
index 4e8891f66f3..31729ec441e 100644
--- a/lib/CodeGen/RegAllocGreedy.cpp
+++ b/lib/CodeGen/RegAllocGreedy.cpp
@@ -772,6 +772,7 @@ unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
 
     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 d648d5a9e15..0ccb93f871d 100644
--- a/lib/CodeGen/SpillPlacement.cpp
+++ b/lib/CodeGen/SpillPlacement.cpp
@@ -134,10 +134,14 @@ struct SpillPlacement::Node {
   }
 
   /// 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 @@ void SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) {
     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 @@ void SpillPlacement::prepare(BitVector &RegBundles) {
   ActiveNodes = &RegBundles;
   ActiveNodes->clear();
   ActiveNodes->resize(bundles->getNumBundles());
+  PositiveNodes = 0;
 }
 
 bool
diff --git a/lib/CodeGen/SpillPlacement.h b/lib/CodeGen/SpillPlacement.h
index d1c6ceb7857..a67785ddf9b 100644
--- a/lib/CodeGen/SpillPlacement.h
+++ b/lib/CodeGen/SpillPlacement.h
@@ -49,6 +49,9 @@ class SpillPlacement  : public MachineFunctionPass {
   // 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 @@ public:
   ///                   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
-- 
2.34.1