1 //===-- SpillPlacement.cpp - Optimal Spill Code Placement -----------------===//
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 file implements the spill code placement analysis.
12 // Each edge bundle corresponds to a node in a Hopfield network. Constraints on
13 // basic blocks are weighted by the block frequency and added to become the node
16 // Transparent basic blocks have the variable live through, but don't care if it
17 // is spilled or in a register. These blocks become connections in the Hopfield
18 // network, again weighted by block frequency.
20 // The Hopfield network minimizes (possibly locally) its energy function:
22 // E = -sum_n V_n * ( B_n + sum_{n, m linked by b} V_m * F_b )
24 // The energy function represents the expected spill code execution frequency,
25 // or the cost of spilling. This is a Lyapunov function which never increases
26 // when a node is updated. It is guaranteed to converge to a local minimum.
28 //===----------------------------------------------------------------------===//
30 #define DEBUG_TYPE "spillplacement"
31 #include "SpillPlacement.h"
32 #include "llvm/CodeGen/EdgeBundles.h"
33 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
34 #include "llvm/CodeGen/MachineBasicBlock.h"
35 #include "llvm/CodeGen/MachineFunction.h"
36 #include "llvm/CodeGen/MachineLoopInfo.h"
37 #include "llvm/CodeGen/Passes.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/Format.h"
43 char SpillPlacement::ID
= 0;
44 INITIALIZE_PASS_BEGIN(SpillPlacement
, "spill-code-placement",
45 "Spill Code Placement Analysis", true, true)
46 INITIALIZE_PASS_DEPENDENCY(EdgeBundles
)
47 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo
)
48 INITIALIZE_PASS_END(SpillPlacement
, "spill-code-placement",
49 "Spill Code Placement Analysis", true, true)
51 char &llvm::SpillPlacementID
= SpillPlacement::ID
;
53 void SpillPlacement::getAnalysisUsage(AnalysisUsage
&AU
) const {
55 AU
.addRequiredTransitive
<EdgeBundles
>();
56 AU
.addRequiredTransitive
<MachineLoopInfo
>();
57 MachineFunctionPass::getAnalysisUsage(AU
);
60 /// Node - Each edge bundle corresponds to a Hopfield node.
62 /// The node contains precomputed frequency data that only depends on the CFG,
63 /// but Bias and Links are computed each time placeSpills is called.
65 /// The node Value is positive when the variable should be in a register. The
66 /// value can change when linked nodes change, but convergence is very fast
67 /// because all weights are positive.
69 struct SpillPlacement::Node
{
70 /// Frequency - Total block frequency feeding into[0] or out of[1] the bundle.
71 /// Ideally, these two numbers should be identical, but inaccuracies in the
72 /// block frequency estimates means that we need to normalize ingoing and
73 /// outgoing frequencies separately so they are commensurate.
76 /// Bias - Normalized contributions from non-transparent blocks.
77 /// A bundle connected to a MustSpill block has a huge negative bias,
78 /// otherwise it is a number in the range [-2;2].
81 /// Value - Output value of this node computed from the Bias and links.
82 /// This is always in the range [-1;1]. A positive number means the variable
83 /// should go in a register through this bundle.
86 typedef SmallVector
<std::pair
<float, unsigned>, 4> LinkVector
;
88 /// Links - (Weight, BundleNo) for all transparent blocks connecting to other
89 /// bundles. The weights are all positive and add up to at most 2, weights
90 /// from ingoing and outgoing nodes separately add up to a most 1. The weight
91 /// sum can be less than 2 when the variable is not live into / out of some
92 /// connected basic blocks.
95 /// preferReg - Return true when this node prefers to be in a register.
96 bool preferReg() const {
97 // Undecided nodes (Value==0) go on the stack.
101 /// mustSpill - Return True if this node is so biased that it must spill.
102 bool mustSpill() const {
103 // Actually, we must spill if Bias < sum(weights).
104 // It may be worth it to compute the weight sum here?
108 /// Node - Create a blank Node.
110 Frequency
[0] = Frequency
[1] = 0;
113 /// clear - Reset per-query data, but preserve frequencies that only depend on
120 /// addLink - Add a link to bundle b with weight w.
121 /// out=0 for an ingoing link, and 1 for an outgoing link.
122 void addLink(unsigned b
, float w
, bool out
) {
123 // Normalize w relative to all connected blocks from that direction.
126 // There can be multiple links to the same bundle, add them up.
127 for (LinkVector::iterator I
= Links
.begin(), E
= Links
.end(); I
!= E
; ++I
)
128 if (I
->second
== b
) {
132 // This must be the first link to b.
133 Links
.push_back(std::make_pair(w
, b
));
136 /// addBias - Bias this node from an ingoing[0] or outgoing[1] link.
137 void addBias(float w
, bool out
) {
138 // Normalize w relative to all connected blocks from that direction.
143 /// update - Recompute Value from Bias and Links. Return true when node
144 /// preference changes.
145 bool update(const Node nodes
[]) {
146 // Compute the weighted sum of inputs.
148 for (LinkVector::iterator I
= Links
.begin(), E
= Links
.end(); I
!= E
; ++I
)
149 Sum
+= I
->first
* nodes
[I
->second
].Value
;
151 // The weighted sum is going to be in the range [-2;2]. Ideally, we should
152 // simply set Value = sign(Sum), but we will add a dead zone around 0 for
154 // 1. It avoids arbitrary bias when all links are 0 as is possible during
155 // initial iterations.
156 // 2. It helps tame rounding errors when the links nominally sum to 0.
157 const float Thres
= 1e-4f
;
158 bool Before
= preferReg();
161 else if (Sum
> Thres
)
165 return Before
!= preferReg();
169 bool SpillPlacement::runOnMachineFunction(MachineFunction
&mf
) {
171 bundles
= &getAnalysis
<EdgeBundles
>();
172 loops
= &getAnalysis
<MachineLoopInfo
>();
174 assert(!nodes
&& "Leaking node array");
175 nodes
= new Node
[bundles
->getNumBundles()];
177 // Compute total ingoing and outgoing block frequencies for all bundles.
178 for (MachineFunction::iterator I
= mf
.begin(), E
= mf
.end(); I
!= E
; ++I
) {
179 float Freq
= getBlockFrequency(I
);
180 unsigned Num
= I
->getNumber();
181 nodes
[bundles
->getBundle(Num
, 1)].Frequency
[0] += Freq
;
182 nodes
[bundles
->getBundle(Num
, 0)].Frequency
[1] += Freq
;
185 // We never change the function.
189 void SpillPlacement::releaseMemory() {
194 /// activate - mark node n as active if it wasn't already.
195 void SpillPlacement::activate(unsigned n
) {
196 if (ActiveNodes
->test(n
))
203 /// prepareNodes - Compute node biases and weights from a set of constraints.
204 /// Set a bit in NodeMask for each active node.
205 void SpillPlacement::
206 prepareNodes(const SmallVectorImpl
<BlockConstraint
> &LiveBlocks
) {
207 DEBUG(dbgs() << "Building Hopfield network from " << LiveBlocks
.size()
208 << " constraint blocks:\n");
209 for (SmallVectorImpl
<BlockConstraint
>::const_iterator I
= LiveBlocks
.begin(),
210 E
= LiveBlocks
.end(); I
!= E
; ++I
) {
211 MachineBasicBlock
*MBB
= MF
->getBlockNumbered(I
->Number
);
212 float Freq
= getBlockFrequency(MBB
);
213 DEBUG(dbgs() << " BB#" << I
->Number
<< format(", Freq = %.1f", Freq
));
215 // Is this a transparent block? Link ingoing and outgoing bundles.
216 if (I
->Entry
== DontCare
&& I
->Exit
== DontCare
) {
217 unsigned ib
= bundles
->getBundle(I
->Number
, 0);
218 unsigned ob
= bundles
->getBundle(I
->Number
, 1);
219 DEBUG(dbgs() << ", transparent EB#" << ib
<< " -> EB#" << ob
<< '\n');
221 // Ignore self-loops.
226 nodes
[ib
].addLink(ob
, Freq
, 1);
227 nodes
[ob
].addLink(ib
, Freq
, 0);
231 // This block is not transparent, but it can still add bias.
232 const float Bias
[] = {
236 -HUGE_VALF
// MustSpill
240 if (I
->Entry
!= DontCare
) {
241 unsigned ib
= bundles
->getBundle(I
->Number
, 0);
243 nodes
[ib
].addBias(Freq
* Bias
[I
->Entry
], 1);
244 DEBUG(dbgs() << format(", entry EB#%u %+.1f", ib
, Freq
* Bias
[I
->Entry
]));
247 // Live-out from block?
248 if (I
->Exit
!= DontCare
) {
249 unsigned ob
= bundles
->getBundle(I
->Number
, 1);
251 nodes
[ob
].addBias(Freq
* Bias
[I
->Exit
], 0);
252 DEBUG(dbgs() << format(", exit EB#%u %+.1f", ob
, Freq
* Bias
[I
->Exit
]));
255 DEBUG(dbgs() << '\n');
259 /// iterate - Repeatedly update the Hopfield nodes until stability or the
260 /// maximum number of iterations is reached.
261 /// @param Linked - Numbers of linked nodes that need updating.
262 void SpillPlacement::iterate(const SmallVectorImpl
<unsigned> &Linked
) {
263 DEBUG(dbgs() << "Iterating over " << Linked
.size() << " linked nodes:\n");
267 // Run up to 10 iterations. The edge bundle numbering is closely related to
268 // basic block numbering, so there is a strong tendency towards chains of
269 // linked nodes with sequential numbers. By scanning the linked nodes
270 // backwards and forwards, we make it very likely that a single node can
271 // affect the entire network in a single iteration. That means very fast
272 // convergence, usually in a single iteration.
273 for (unsigned iteration
= 0; iteration
!= 10; ++iteration
) {
274 // Scan backwards, skipping the last node which was just updated.
275 bool Changed
= false;
276 for (SmallVectorImpl
<unsigned>::const_reverse_iterator I
=
277 llvm::next(Linked
.rbegin()), E
= Linked
.rend(); I
!= E
; ++I
) {
279 bool C
= nodes
[n
].update(nodes
);
281 DEBUG(dbgs() << " \\EB#" << n
<< format(" = %+2.0f", nodes
[n
].Value
)
282 << (C
? " *\n" : "\n"));
287 // Scan forwards, skipping the first node which was just updated.
289 for (SmallVectorImpl
<unsigned>::const_iterator I
=
290 llvm::next(Linked
.begin()), E
= Linked
.end(); I
!= E
; ++I
) {
292 bool C
= nodes
[n
].update(nodes
);
294 DEBUG(dbgs() << " /EB#" << n
<< format(" = %+2.0f", nodes
[n
].Value
)
295 << (C
? " *\n" : "\n"));
303 SpillPlacement::placeSpills(const SmallVectorImpl
<BlockConstraint
> &LiveBlocks
,
304 BitVector
&RegBundles
) {
305 // Reuse RegBundles as our ActiveNodes vector.
306 ActiveNodes
= &RegBundles
;
307 ActiveNodes
->clear();
308 ActiveNodes
->resize(bundles
->getNumBundles());
310 // Compute active nodes, links and biases.
311 prepareNodes(LiveBlocks
);
313 // Update all active nodes, and find the ones that are actually linked to
314 // something so their value may change when iterating.
315 DEBUG(dbgs() << "Network has " << RegBundles
.count() << " active nodes:\n");
316 SmallVector
<unsigned, 8> Linked
;
317 for (int n
= RegBundles
.find_first(); n
>=0; n
= RegBundles
.find_next(n
)) {
318 nodes
[n
].update(nodes
);
319 // A node that must spill, or a node without any links is not going to
320 // change its value ever again, so exclude it from iterations.
321 if (!nodes
[n
].Links
.empty() && !nodes
[n
].mustSpill())
325 dbgs() << " EB#" << n
<< format(" = %+2.0f", nodes
[n
].Value
)
326 << format(", Bias %+.2f", nodes
[n
].Bias
)
327 << format(", Freq %.1f/%.1f", nodes
[n
].Frequency
[0],
328 nodes
[n
].Frequency
[1]);
329 for (unsigned i
= 0, e
= nodes
[n
].Links
.size(); i
!= e
; ++i
)
330 dbgs() << format(", %.2f -> EB#%u", nodes
[n
].Links
[i
].first
,
331 nodes
[n
].Links
[i
].second
);
336 // Iterate the network to convergence.
339 // Write preferences back to RegBundles.
341 for (int n
= RegBundles
.find_first(); n
>=0; n
= RegBundles
.find_next(n
))
342 if (!nodes
[n
].preferReg()) {
349 /// getBlockFrequency - Return our best estimate of the block frequency which is
350 /// the expected number of block executions per function invocation.
351 float SpillPlacement::getBlockFrequency(const MachineBasicBlock
*MBB
) {
352 // Use the unnormalized spill weight for real block frequencies.
353 return LiveIntervals::getSpillWeight(true, false, loops
->getLoopDepth(MBB
));