Line data Source code
1 : //===- SpillPlacement.h - Optimal Spill Code Placement ---------*- C++ -*--===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This analysis computes the optimal spill code placement between basic blocks.
11 : //
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.
15 : //
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.
20 : //
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
23 : // considered.
24 : //
25 : //===----------------------------------------------------------------------===//
26 :
27 : #ifndef LLVM_LIB_CODEGEN_SPILLPLACEMENT_H
28 : #define LLVM_LIB_CODEGEN_SPILLPLACEMENT_H
29 :
30 : #include "llvm/ADT/ArrayRef.h"
31 : #include "llvm/ADT/SmallVector.h"
32 : #include "llvm/ADT/SparseSet.h"
33 : #include "llvm/CodeGen/MachineFunctionPass.h"
34 : #include "llvm/Support/BlockFrequency.h"
35 :
36 : namespace llvm {
37 :
38 : class BitVector;
39 : class EdgeBundles;
40 : class MachineBlockFrequencyInfo;
41 : class MachineFunction;
42 : class MachineLoopInfo;
43 :
44 : class SpillPlacement : public MachineFunctionPass {
45 : struct Node;
46 : const MachineFunction *MF;
47 : const EdgeBundles *bundles;
48 : const MachineLoopInfo *loops;
49 : const MachineBlockFrequencyInfo *MBFI;
50 : Node *nodes = nullptr;
51 :
52 : // Nodes that are active in the current computation. Owned by the prepare()
53 : // caller.
54 : BitVector *ActiveNodes;
55 :
56 : // Nodes with active links. Populated by scanActiveBundles.
57 : SmallVector<unsigned, 8> Linked;
58 :
59 : // Nodes that went positive during the last call to scanActiveBundles or
60 : // iterate.
61 : SmallVector<unsigned, 8> RecentPositive;
62 :
63 : // Block frequencies are computed once. Indexed by block number.
64 : SmallVector<BlockFrequency, 8> BlockFrequencies;
65 :
66 : /// Decision threshold. A node gets the output value 0 if the weighted sum of
67 : /// its inputs falls in the open interval (-Threshold;Threshold).
68 : BlockFrequency Threshold;
69 :
70 : /// List of nodes that need to be updated in ::iterate.
71 : SparseSet<unsigned> TodoList;
72 :
73 : public:
74 : static char ID; // Pass identification, replacement for typeid.
75 :
76 19488 : SpillPlacement() : MachineFunctionPass(ID) {}
77 58083 : ~SpillPlacement() override { releaseMemory(); }
78 :
79 : /// BorderConstraint - A basic block has separate constraints for entry and
80 : /// exit.
81 : enum BorderConstraint {
82 : DontCare, ///< Block doesn't care / variable not live.
83 : PrefReg, ///< Block entry/exit prefers a register.
84 : PrefSpill, ///< Block entry/exit prefers a stack slot.
85 : PrefBoth, ///< Block entry prefers both register and stack.
86 : MustSpill ///< A register is impossible, variable must be spilled.
87 : };
88 :
89 : /// BlockConstraint - Entry and exit constraints for a basic block.
90 : struct BlockConstraint {
91 : unsigned Number; ///< Basic block number (from MBB::getNumber()).
92 : BorderConstraint Entry : 8; ///< Constraint on block entry.
93 : BorderConstraint Exit : 8; ///< Constraint on block exit.
94 :
95 : /// True when this block changes the value of the live range. This means
96 : /// the block has a non-PHI def. When this is false, a live-in value on
97 : /// the stack can be live-out on the stack without inserting a spill.
98 : bool ChangesValue;
99 : };
100 :
101 : /// prepare - Reset state and prepare for a new spill placement computation.
102 : /// @param RegBundles Bit vector to receive the edge bundles where the
103 : /// variable should be kept in a register. Each bit
104 : /// corresponds to an edge bundle, a set bit means the
105 : /// variable should be kept in a register through the
106 : /// bundle. A clear bit means the variable should be
107 : /// spilled. This vector is retained.
108 : void prepare(BitVector &RegBundles);
109 :
110 : /// addConstraints - Add constraints and biases. This method may be called
111 : /// more than once to accumulate constraints.
112 : /// @param LiveBlocks Constraints for blocks that have the variable live in or
113 : /// live out.
114 : void addConstraints(ArrayRef<BlockConstraint> LiveBlocks);
115 :
116 : /// addPrefSpill - Add PrefSpill constraints to all blocks listed. This is
117 : /// equivalent to calling addConstraint with identical BlockConstraints with
118 : /// Entry = Exit = PrefSpill, and ChangesValue = false.
119 : ///
120 : /// @param Blocks Array of block numbers that prefer to spill in and out.
121 : /// @param Strong When true, double the negative bias for these blocks.
122 : void addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong);
123 :
124 : /// addLinks - Add transparent blocks with the given numbers.
125 : void addLinks(ArrayRef<unsigned> Links);
126 :
127 : /// scanActiveBundles - Perform an initial scan of all bundles activated by
128 : /// addConstraints and addLinks, updating their state. Add all the bundles
129 : /// that now prefer a register to RecentPositive.
130 : /// Prepare internal data structures for iterate.
131 : /// Return true is there are any positive nodes.
132 : bool scanActiveBundles();
133 :
134 : /// iterate - Update the network iteratively until convergence, or new bundles
135 : /// are found.
136 : void iterate();
137 :
138 : /// getRecentPositive - Return an array of bundles that became positive during
139 : /// the previous call to scanActiveBundles or iterate.
140 : ArrayRef<unsigned> getRecentPositive() { return RecentPositive; }
141 :
142 : /// finish - Compute the optimal spill code placement given the
143 : /// constraints. No MustSpill constraints will be violated, and the smallest
144 : /// possible number of PrefX constraints will be violated, weighted by
145 : /// expected execution frequencies.
146 : /// The selected bundles are returned in the bitvector passed to prepare().
147 : /// @return True if a perfect solution was found, allowing the variable to be
148 : /// in a register through all relevant bundles.
149 : bool finish();
150 :
151 : /// getBlockFrequency - Return the estimated block execution frequency per
152 : /// function invocation.
153 : BlockFrequency getBlockFrequency(unsigned Number) const {
154 1279200 : return BlockFrequencies[Number];
155 : }
156 :
157 : private:
158 : bool runOnMachineFunction(MachineFunction &mf) override;
159 : void getAnalysisUsage(AnalysisUsage &AU) const override;
160 : void releaseMemory() override;
161 :
162 : void activate(unsigned n);
163 : void setThreshold(const BlockFrequency &Entry);
164 :
165 : bool update(unsigned n);
166 : };
167 :
168 : } // end namespace llvm
169 :
170 : #endif // LLVM_LIB_CODEGEN_SPILLPLACEMENT_H
|
