From 9efa2a263ea470caacef1c85f6ca45e32bf516d3 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Wed, 6 Apr 2011 19:13:57 +0000 Subject: Break the spill placement algorithm into three parts: prepare, addConstraints, and finish. 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 --- lib/CodeGen/RegAllocGreedy.cpp | 5 ++++- lib/CodeGen/SpillPlacement.cpp | 27 +++++++++++++-------------- lib/CodeGen/SpillPlacement.h | 37 ++++++++++++++++++++++--------------- 3 files changed, 39 insertions(+), 30 deletions(-) (limited to 'lib') diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp index 4339a81b8f..4e8891f66f 100644 --- 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 57951ed806..d648d5a9e1 100644 --- 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 &LiveBlocks) { - for (SmallVectorImpl::const_iterator I = LiveBlocks.begin(), +void SpillPlacement::addConstraints(ArrayRef LiveBlocks) { + for (ArrayRef::iterator I = LiveBlocks.begin(), E = LiveBlocks.end(); I != E; ++I) { float Freq = getBlockFrequency(I->Number); @@ -288,21 +287,20 @@ void SpillPlacement::iterate(const SmallVectorImpl &Linked) { } } -bool -SpillPlacement::placeSpills(const SmallVectorImpl &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 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 &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 b0135cbc36..d1c6ceb785 100644 --- 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 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 &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&); void iterate(const SmallVectorImpl&); }; -- cgit v1.2.3