X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSpillPlacement.h;h=03cf5cd74246e5fb4299a3ef81284c8cd3cb2d67;hb=f8da7e552cdc7d369397db12dbb3169332d658f5;hp=ef2d516cdce7c3eaa75e68f09c91002749635e76;hpb=b5fa9333431673aac2ced8dea80152349a85cf6f;p=oota-llvm.git diff --git a/lib/CodeGen/SpillPlacement.h b/lib/CodeGen/SpillPlacement.h index ef2d516cdce..03cf5cd7424 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 @@ -24,10 +24,13 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_SPILLPLACEMENT_H -#define LLVM_CODEGEN_SPILLPLACEMENT_H +#ifndef LLVM_LIB_CODEGEN_SPILLPLACEMENT_H +#define LLVM_LIB_CODEGEN_SPILLPLACEMENT_H +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/Support/BlockFrequency.h" namespace llvm { @@ -35,23 +38,34 @@ class BitVector; class EdgeBundles; class MachineBasicBlock; class MachineLoopInfo; -template class SmallVectorImpl; +class MachineBlockFrequencyInfo; -class SpillPlacement : public MachineFunctionPass { +class SpillPlacement : public MachineFunctionPass { struct Node; const MachineFunction *MF; const EdgeBundles *bundles; const MachineLoopInfo *loops; + const MachineBlockFrequencyInfo *MBFI; 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; + // 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 BlockFrequencies; + public: static char ID; // Pass identification, replacement for typeid. - SpillPlacement() : MachineFunctionPass(ID), nodes(0) {} + SpillPlacement() : MachineFunctionPass(ID), nodes(nullptr) {} ~SpillPlacement() { releaseMemory(); } /// BorderConstraint - A basic block has separate constraints for entry and @@ -60,6 +74,7 @@ public: DontCare, ///< Block doesn't care / variable not live. PrefReg, ///< Block entry/exit prefers a register. PrefSpill, ///< Block entry/exit prefers a stack slot. + PrefBoth, ///< Block entry prefers both register and stack. MustSpill ///< A register is impossible, variable must be spilled. }; @@ -68,39 +83,75 @@ public: unsigned Number; ///< Basic block number (from MBB::getNumber()). BorderConstraint Entry : 8; ///< Constraint on block entry. BorderConstraint Exit : 8; ///< Constraint on block exit. + + /// True when this block changes the value of the live range. This means + /// the block has a non-PHI def. When this is false, a live-in value on + /// the stack can be live-out on the stack without inserting a spill. + bool ChangesValue; }; - /// 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. + void addConstraints(ArrayRef LiveBlocks); + + /// addPrefSpill - Add PrefSpill constraints to all blocks listed. This is + /// equivalent to calling addConstraint with identical BlockConstraints with + /// Entry = Exit = PrefSpill, and ChangesValue = false. + /// + /// @param Blocks Array of block numbers that prefer to spill in and out. + /// @param Strong When true, double the negative bias for these blocks. + void addPrefSpill(ArrayRef Blocks, bool Strong); + + /// addLinks - Add transparent blocks with the given numbers. + void addLinks(ArrayRef Links); + + /// 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 + /// 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. - float getBlockFrequency(const MachineBasicBlock*); + BlockFrequency getBlockFrequency(unsigned Number) const { + return BlockFrequencies[Number]; + } private: - virtual bool runOnMachineFunction(MachineFunction&); - virtual void getAnalysisUsage(AnalysisUsage&) const; - virtual void releaseMemory(); + bool runOnMachineFunction(MachineFunction&) override; + void getAnalysisUsage(AnalysisUsage&) const override; + void releaseMemory() override; void activate(unsigned); - void prepareNodes(const SmallVectorImpl&); - void iterate(const SmallVectorImpl&); }; } // end namespace llvm