Break the spill placement algorithm into three parts: prepare, addConstraints, and...

This will allow us to abort the algorithm early if it is determined to be futile.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129020 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp
index 4339a81b8f4789ff7d43eec46ad228510356716b..4e8891f66f300a1646f9b28a3809b8e3bb21d358 100644 (file)
--- a/lib/CodeGen/RegAllocGreedy.cpp
+++ b/lib/CodeGen/RegAllocGreedy.cpp
@@ -770,7 +770,10 @@ unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
       continue;
     }
 
-    SpillPlacer->placeSpills(SplitConstraints, LiveBundles);
+    SpillPlacer->prepare(LiveBundles);
+    SpillPlacer->addConstraints(SplitConstraints);
+    SpillPlacer->finish();
+
     // No live bundles, defer to splitSingleBlocks().
     if (!LiveBundles.any()) {
       DEBUG(dbgs() << " no bundles.\n");

diff --git a/lib/CodeGen/SpillPlacement.cpp b/lib/CodeGen/SpillPlacement.cpp
index 57951ed80689c2a1fd51d7b9aa028cbdf07f28b6..d648d5a9e15393d45627e8fea68eb5142c0f63ad 100644 (file)
--- a/lib/CodeGen/SpillPlacement.cpp
+++ b/lib/CodeGen/SpillPlacement.cpp
@@ -203,11 +203,10 @@ void SpillPlacement::activate(unsigned n) {
 }
 
 
-/// prepareNodes - Compute node biases and weights from a set of constraints.
+/// addConstraints - Compute node biases and weights from a set of constraints.
 /// Set a bit in NodeMask for each active node.
-void SpillPlacement::
-prepareNodes(const SmallVectorImpl<BlockConstraint> &LiveBlocks) {
-  for (SmallVectorImpl<BlockConstraint>::const_iterator I = LiveBlocks.begin(),
+void SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) {
+  for (ArrayRef<BlockConstraint>::iterator I = LiveBlocks.begin(),
        E = LiveBlocks.end(); I != E; ++I) {
     float Freq = getBlockFrequency(I->Number);
 
@@ -288,21 +287,20 @@ void SpillPlacement::iterate(const SmallVectorImpl<unsigned> &Linked) {
   }
 }
 
-bool
-SpillPlacement::placeSpills(const SmallVectorImpl<BlockConstraint> &LiveBlocks,
-                            BitVector &RegBundles) {
+void SpillPlacement::prepare(BitVector &RegBundles) {
   // Reuse RegBundles as our ActiveNodes vector.
   ActiveNodes = &RegBundles;
   ActiveNodes->clear();
   ActiveNodes->resize(bundles->getNumBundles());
+}
 
-  // Compute active nodes, links and biases.
-  prepareNodes(LiveBlocks);
-
+bool
+SpillPlacement::finish() {
+  assert(ActiveNodes && "Call prepare() first");
   // Update all active nodes, and find the ones that are actually linked to
   // something so their value may change when iterating.
   SmallVector<unsigned, 8> Linked;
-  for (int n = RegBundles.find_first(); n>=0; n = RegBundles.find_next(n)) {
+  for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) {
     nodes[n].update(nodes);
     // A node that must spill, or a node without any links is not going to
     // change its value ever again, so exclude it from iterations.
@@ -313,12 +311,13 @@ SpillPlacement::placeSpills(const SmallVectorImpl<BlockConstraint> &LiveBlocks,
   // Iterate the network to convergence.
   iterate(Linked);
 
-  // Write preferences back to RegBundles.
+  // Write preferences back to ActiveNodes.
   bool Perfect = true;
-  for (int n = RegBundles.find_first(); n>=0; n = RegBundles.find_next(n))
+  for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n))
     if (!nodes[n].preferReg()) {
-      RegBundles.reset(n);
+      ActiveNodes->reset(n);
       Perfect = false;
     }
+  ActiveNodes = 0;
   return Perfect;
 }

diff --git a/lib/CodeGen/SpillPlacement.h b/lib/CodeGen/SpillPlacement.h
index b0135cbc36599e81f223f555ea8fffd9dff7287b..d1c6ceb78575ec39c6ac3c5134c957165a00ccfc 100644 (file)
--- a/lib/CodeGen/SpillPlacement.h
+++ b/lib/CodeGen/SpillPlacement.h
@@ -10,8 +10,8 @@
 // This analysis computes the optimal spill code placement between basic blocks.
 //
 // The runOnMachineFunction() method only precomputes some profiling information
-// about the CFG. The real work is done by placeSpills() which is called by the
-// register allocator.
+// about the CFG. The real work is done by prepare(), addConstraints(), and
+// finish() which are called by the register allocator.
 //
 // Given a variable that is live across multiple basic blocks, and given
 // constraints on the basic blocks where the variable is live, determine which
@@ -27,6 +27,7 @@
 #ifndef LLVM_CODEGEN_SPILLPLACEMENT_H
 #define LLVM_CODEGEN_SPILLPLACEMENT_H
 
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 
@@ -44,7 +45,7 @@ class SpillPlacement  : public MachineFunctionPass {
   const MachineLoopInfo *loops;
   Node *nodes;
 
-  // Nodes that are active in the current computation. Owned by the placeSpills
+  // Nodes that are active in the current computation. Owned by the prepare()
   // caller.
   BitVector *ActiveNodes;
 
@@ -73,24 +74,31 @@ public:
     BorderConstraint Exit : 8;  ///< Constraint on block exit.
   };
 
-  /// placeSpills - 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
-  /// expected execution frequencies.
-  /// @param LiveBlocks Constraints for blocks that have the variable live in or
-  ///                   live out. DontCare/DontCare means the variable is live
-  ///                   through the block. DontCare/X means the variable is live
-  ///                   out, but not live in.
+  /// prepare - Reset state and prepare for a new spill placement computation.
   /// @param RegBundles Bit vector to receive the edge bundles where the
   ///                   variable should be kept in a register. Each bit
   ///                   corresponds to an edge bundle, a set bit means the
   ///                   variable should be kept in a register through the
   ///                   bundle. A clear bit means the variable should be
-  ///                   spilled.
+  ///                   spilled. This vector is retained.
+  void prepare(BitVector &RegBundles);
+
+  /// addConstraints - Add constraints and biases. This method may be called
+  /// more than once to accumulate constraints.
+  /// @param LiveBlocks Constraints for blocks that have the variable live in or
+  ///                   live out. DontCare/DontCare means the variable is live
+  ///                   through the block. DontCare/X means the variable is live
+  ///                   out, but not live in.
+  void addConstraints(ArrayRef<BlockConstraint> LiveBlocks);
+
+  /// 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
+  /// expected execution frequencies.
+  /// The selected bundles are returned in the bitvector passed to prepare().
   /// @return True if a perfect solution was found, allowing the variable to be
   ///         in a register through all relevant bundles.
-  bool placeSpills(const SmallVectorImpl<BlockConstraint> &LiveBlocks,
-                   BitVector &RegBundles);
+  bool finish();
 
   /// getBlockFrequency - Return the estimated block execution frequency per
   /// function invocation.
@@ -104,7 +112,6 @@ private:
   virtual void releaseMemory();
 
   void activate(unsigned);
-  void prepareNodes(const SmallVectorImpl<BlockConstraint>&);
   void iterate(const SmallVectorImpl<unsigned>&);
 };