From ed47ed4e80d9add78932bafff99701a87d54923c Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Sat, 9 Apr 2011 02:59:09 +0000 Subject: Build the Hopfield network incrementally when splitting global live ranges. It is common for large live ranges to have few basic blocks with register uses and many live-through blocks without any uses. This approach grows the Hopfield network incrementally around the use blocks, completely avoiding checking interference for some through blocks. llvm-svn: 129188 --- llvm/lib/CodeGen/SpillPlacement.h | 26 ++++++++++++++++++++------ 1 file changed, 20 insertions(+), 6 deletions(-) (limited to 'llvm/lib/CodeGen/SpillPlacement.h') diff --git a/llvm/lib/CodeGen/SpillPlacement.h b/llvm/lib/CodeGen/SpillPlacement.h index 46e64e6fcbf..6952ad80096 100644 --- a/llvm/lib/CodeGen/SpillPlacement.h +++ b/llvm/lib/CodeGen/SpillPlacement.h @@ -49,8 +49,12 @@ class SpillPlacement : public MachineFunctionPass { // caller. BitVector *ActiveNodes; - // The number of active nodes with a positive bias. - unsigned PositiveNodes; + // Nodes with active links. Populated by scanActiveBundles. + SmallVector Linked; + + // Nodes that went positive during the last call to scanActiveBundles or + // iterate. + SmallVector RecentPositive; // Block frequencies are computed once. Indexed by block number. SmallVector BlockFrequency; @@ -95,9 +99,20 @@ public: /// addLinks - Add transparent blocks with the given numbers. void addLinks(ArrayRef Links); - /// getPositiveNodes - Return the total number of graph nodes with a positive - /// bias after adding constraints. - unsigned getPositiveNodes() const { return PositiveNodes; } + /// scanActiveBundles - Perform an initial scan of all bundles activated by + /// addConstraints and addLinks, updating their state. Add all the bundles + /// that now prefer a register to RecentPositive. + /// Prepare internal data structures for iterate. + /// Return true is there are any positive nodes. + bool scanActiveBundles(); + + /// iterate - Update the network iteratively until convergence, or new bundles + /// are found. + void iterate(); + + /// getRecentPositive - Return an array of bundles that became positive during + /// the previous call to scanActiveBundles or iterate. + ArrayRef getRecentPositive() { return RecentPositive; } /// finish - Compute the optimal spill code placement given the /// constraints. No MustSpill constraints will be violated, and the smallest @@ -120,7 +135,6 @@ private: virtual void releaseMemory(); void activate(unsigned); - void iterate(const SmallVectorImpl&); }; } // end namespace llvm -- cgit v1.2.3