diff options
author | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2011-04-06 19:14:00 +0000 |
---|---|---|
committer | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2011-04-06 19:14:00 +0000 |
commit | 70d4370b47cdd375bbea98e50452789fe4f1af04 (patch) | |
tree | add9c7e773a47c8ff88ca8840dd657c7614db4da | |
parent | 9efa2a263ea470caacef1c85f6ca45e32bf516d3 (diff) |
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
-rw-r--r-- | lib/CodeGen/RegAllocGreedy.cpp | 1 | ||||
-rw-r--r-- | lib/CodeGen/SpillPlacement.cpp | 11 | ||||
-rw-r--r-- | 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 |