1 //===-- SpillPlacement.h - Optimal Spill Code Placement --------*- C++ -*--===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This analysis computes the optimal spill code placement between basic blocks.
12 // The runOnMachineFunction() method only precomputes some profiling information
13 // about the CFG. The real work is done by prepare(), addConstraints(), and
14 // finish() which are called by the register allocator.
16 // Given a variable that is live across multiple basic blocks, and given
17 // constraints on the basic blocks where the variable is live, determine which
18 // edge bundles should have the variable in a register and which edge bundles
19 // should have the variable in a stack slot.
21 // The returned bit vector can be used to place optimal spill code at basic
22 // block entries and exits. Spill code placement inside a basic block is not
25 //===----------------------------------------------------------------------===//
27 #ifndef LLVM_CODEGEN_SPILLPLACEMENT_H
28 #define LLVM_CODEGEN_SPILLPLACEMENT_H
30 #include "llvm/ADT/ArrayRef.h"
31 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/CodeGen/MachineFunctionPass.h"
38 class MachineBasicBlock;
39 class MachineLoopInfo;
41 class SpillPlacement : public MachineFunctionPass {
43 const MachineFunction *MF;
44 const EdgeBundles *bundles;
45 const MachineLoopInfo *loops;
48 // Nodes that are active in the current computation. Owned by the prepare()
50 BitVector *ActiveNodes;
52 // Nodes with active links. Populated by scanActiveBundles.
53 SmallVector<unsigned, 8> Linked;
55 // Nodes that went positive during the last call to scanActiveBundles or
57 SmallVector<unsigned, 8> RecentPositive;
59 // Block frequencies are computed once. Indexed by block number.
60 SmallVector<float, 4> BlockFrequency;
63 static char ID; // Pass identification, replacement for typeid.
65 SpillPlacement() : MachineFunctionPass(ID), nodes(0) {}
66 ~SpillPlacement() { releaseMemory(); }
68 /// BorderConstraint - A basic block has separate constraints for entry and
70 enum BorderConstraint {
71 DontCare, ///< Block doesn't care / variable not live.
72 PrefReg, ///< Block entry/exit prefers a register.
73 PrefSpill, ///< Block entry/exit prefers a stack slot.
74 PrefBoth, ///< Block entry prefers both register and stack.
75 MustSpill ///< A register is impossible, variable must be spilled.
78 /// BlockConstraint - Entry and exit constraints for a basic block.
79 struct BlockConstraint {
80 unsigned Number; ///< Basic block number (from MBB::getNumber()).
81 BorderConstraint Entry : 8; ///< Constraint on block entry.
82 BorderConstraint Exit : 8; ///< Constraint on block exit.
84 /// True when this block changes the value of the live range. This means
85 /// the block has a non-PHI def. When this is false, a live-in value on
86 /// the stack can be live-out on the stack without inserting a spill.
90 /// prepare - Reset state and prepare for a new spill placement computation.
91 /// @param RegBundles Bit vector to receive the edge bundles where the
92 /// variable should be kept in a register. Each bit
93 /// corresponds to an edge bundle, a set bit means the
94 /// variable should be kept in a register through the
95 /// bundle. A clear bit means the variable should be
96 /// spilled. This vector is retained.
97 void prepare(BitVector &RegBundles);
99 /// addConstraints - Add constraints and biases. This method may be called
100 /// more than once to accumulate constraints.
101 /// @param LiveBlocks Constraints for blocks that have the variable live in or
103 void addConstraints(ArrayRef<BlockConstraint> LiveBlocks);
105 /// addPrefSpill - Add PrefSpill constraints to all blocks listed. This is
106 /// equivalent to calling addConstraint with identical BlockConstraints with
107 /// Entry = Exit = PrefSpill, and ChangesValue = false.
109 /// @param Blocks Array of block numbers that prefer to spill in and out.
110 /// @param Strong When true, double the negative bias for these blocks.
111 void addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong);
113 /// addLinks - Add transparent blocks with the given numbers.
114 void addLinks(ArrayRef<unsigned> Links);
116 /// scanActiveBundles - Perform an initial scan of all bundles activated by
117 /// addConstraints and addLinks, updating their state. Add all the bundles
118 /// that now prefer a register to RecentPositive.
119 /// Prepare internal data structures for iterate.
120 /// Return true is there are any positive nodes.
121 bool scanActiveBundles();
123 /// iterate - Update the network iteratively until convergence, or new bundles
127 /// getRecentPositive - Return an array of bundles that became positive during
128 /// the previous call to scanActiveBundles or iterate.
129 ArrayRef<unsigned> getRecentPositive() { return RecentPositive; }
131 /// finish - Compute the optimal spill code placement given the
132 /// constraints. No MustSpill constraints will be violated, and the smallest
133 /// possible number of PrefX constraints will be violated, weighted by
134 /// expected execution frequencies.
135 /// The selected bundles are returned in the bitvector passed to prepare().
136 /// @return True if a perfect solution was found, allowing the variable to be
137 /// in a register through all relevant bundles.
140 /// getBlockFrequency - Return the estimated block execution frequency per
141 /// function invocation.
142 float getBlockFrequency(unsigned Number) const {
143 return BlockFrequency[Number];
147 virtual bool runOnMachineFunction(MachineFunction&);
148 virtual void getAnalysisUsage(AnalysisUsage&) const;
149 virtual void releaseMemory();
151 void activate(unsigned);
154 } // end namespace llvm