Line data Source code
1 : //===- SpillPlacement.cpp - Optimal Spill Code Placement ------------------===//
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 file implements the spill code placement analysis.
11 : //
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
14 : // bias.
15 : //
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.
19 : //
20 : // The Hopfield network minimizes (possibly locally) its energy function:
21 : //
22 : // E = -sum_n V_n * ( B_n + sum_{n, m linked by b} V_m * F_b )
23 : //
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.
27 : //
28 : //===----------------------------------------------------------------------===//
29 :
30 : #include "SpillPlacement.h"
31 : #include "llvm/ADT/ArrayRef.h"
32 : #include "llvm/ADT/BitVector.h"
33 : #include "llvm/ADT/SmallVector.h"
34 : #include "llvm/ADT/SparseSet.h"
35 : #include "llvm/CodeGen/EdgeBundles.h"
36 : #include "llvm/CodeGen/MachineBasicBlock.h"
37 : #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
38 : #include "llvm/CodeGen/MachineFunction.h"
39 : #include "llvm/CodeGen/MachineLoopInfo.h"
40 : #include "llvm/CodeGen/Passes.h"
41 : #include "llvm/Pass.h"
42 : #include "llvm/Support/BlockFrequency.h"
43 : #include <algorithm>
44 : #include <cassert>
45 : #include <cstdint>
46 : #include <utility>
47 :
48 : using namespace llvm;
49 :
50 : #define DEBUG_TYPE "spill-code-placement"
51 :
52 : char SpillPlacement::ID = 0;
53 :
54 : char &llvm::SpillPlacementID = SpillPlacement::ID;
55 :
56 31780 : INITIALIZE_PASS_BEGIN(SpillPlacement, DEBUG_TYPE,
57 : "Spill Code Placement Analysis", true, true)
58 31780 : INITIALIZE_PASS_DEPENDENCY(EdgeBundles)
59 31780 : INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
60 63560 : INITIALIZE_PASS_END(SpillPlacement, DEBUG_TYPE,
61 : "Spill Code Placement Analysis", true, true)
62 :
63 19488 : void SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const {
64 : AU.setPreservesAll();
65 : AU.addRequired<MachineBlockFrequencyInfo>();
66 : AU.addRequiredTransitive<EdgeBundles>();
67 : AU.addRequiredTransitive<MachineLoopInfo>();
68 19488 : MachineFunctionPass::getAnalysisUsage(AU);
69 19488 : }
70 :
71 : /// Node - Each edge bundle corresponds to a Hopfield node.
72 : ///
73 : /// The node contains precomputed frequency data that only depends on the CFG,
74 : /// but Bias and Links are computed each time placeSpills is called.
75 : ///
76 : /// The node Value is positive when the variable should be in a register. The
77 : /// value can change when linked nodes change, but convergence is very fast
78 : /// because all weights are positive.
79 563940 : struct SpillPlacement::Node {
80 : /// BiasN - Sum of blocks that prefer a spill.
81 : BlockFrequency BiasN;
82 :
83 : /// BiasP - Sum of blocks that prefer a register.
84 : BlockFrequency BiasP;
85 :
86 : /// Value - Output value of this node computed from the Bias and links.
87 : /// This is always on of the values {-1, 0, 1}. A positive number means the
88 : /// variable should go in a register through this bundle.
89 : int Value;
90 :
91 : using LinkVector = SmallVector<std::pair<BlockFrequency, unsigned>, 4>;
92 :
93 : /// Links - (Weight, BundleNo) for all transparent blocks connecting to other
94 : /// bundles. The weights are all positive block frequencies.
95 : LinkVector Links;
96 :
97 : /// SumLinkWeights - Cached sum of the weights of all links + ThresHold.
98 : BlockFrequency SumLinkWeights;
99 :
100 : /// preferReg - Return true when this node prefers to be in a register.
101 0 : bool preferReg() const {
102 : // Undecided nodes (Value==0) go on the stack.
103 9140564 : return Value > 0;
104 : }
105 :
106 : /// mustSpill - Return True if this node is so biased that it must spill.
107 : bool mustSpill() const {
108 : // We must spill if Bias < -sum(weights) or the MustSpill flag was set.
109 : // BiasN is saturated when MustSpill is set, make sure this still returns
110 : // true when the RHS saturates. Note that SumLinkWeights includes Threshold.
111 2448496 : return BiasN >= BiasP + SumLinkWeights;
112 : }
113 :
114 : /// clear - Reset per-query data, but preserve frequencies that only depend on
115 : /// the CFG.
116 0 : void clear(const BlockFrequency &Threshold) {
117 2551055 : BiasN = BiasP = Value = 0;
118 2551055 : SumLinkWeights = Threshold;
119 : Links.clear();
120 0 : }
121 :
122 : /// addLink - Add a link to bundle b with weight w.
123 2674622 : void addLink(unsigned b, BlockFrequency w) {
124 : // Update cached sum.
125 2674622 : SumLinkWeights += w;
126 :
127 : // There can be multiple links to the same bundle, add them up.
128 4624099 : for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I)
129 2167539 : if (I->second == b) {
130 218062 : I->first += w;
131 218062 : return;
132 : }
133 : // This must be the first link to b.
134 4913120 : Links.push_back(std::make_pair(w, b));
135 : }
136 :
137 : /// addBias - Bias this node.
138 2965425 : void addBias(BlockFrequency freq, BorderConstraint direction) {
139 2965425 : switch (direction) {
140 : default:
141 : break;
142 926208 : case PrefReg:
143 926208 : BiasP += freq;
144 926208 : break;
145 1391403 : case PrefSpill:
146 1391403 : BiasN += freq;
147 1391403 : break;
148 : case MustSpill:
149 647814 : BiasN = BlockFrequency::getMaxFrequency();
150 647814 : break;
151 : }
152 2965425 : }
153 :
154 : /// update - Recompute Value from Bias and Links. Return true when node
155 : /// preference changes.
156 4570282 : bool update(const Node nodes[], const BlockFrequency &Threshold) {
157 : // Compute the weighted sum of inputs.
158 4570282 : BlockFrequency SumN = BiasN;
159 4570282 : BlockFrequency SumP = BiasP;
160 8913582 : for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) {
161 4343300 : if (nodes[I->second].Value == -1)
162 570370 : SumN += I->first;
163 3772930 : else if (nodes[I->second].Value == 1)
164 3098964 : SumP += I->first;
165 : }
166 :
167 : // Each weighted sum is going to be less than the total frequency of the
168 : // bundle. Ideally, we should simply set Value = sign(SumP - SumN), but we
169 : // will add a dead zone around 0 for two reasons:
170 : //
171 : // 1. It avoids arbitrary bias when all links are 0 as is possible during
172 : // initial iterations.
173 : // 2. It helps tame rounding errors when the links nominally sum to 0.
174 : //
175 4570282 : bool Before = preferReg();
176 4570282 : if (SumN >= SumP + Threshold)
177 1702568 : Value = -1;
178 2867714 : else if (SumP >= SumN + Threshold)
179 2367685 : Value = 1;
180 : else
181 500029 : Value = 0;
182 9140564 : return Before != preferReg();
183 : }
184 :
185 1930286 : void getDissentingNeighbors(SparseSet<unsigned> &List,
186 : const Node nodes[]) const {
187 3477467 : for (const auto &Elt : Links) {
188 1547181 : unsigned n = Elt.second;
189 : // Neighbors that already have the same value are not going to
190 : // change because of this node changing.
191 1547181 : if (Value != nodes[n].Value)
192 557438 : List.insert(n);
193 : }
194 1930286 : }
195 : };
196 :
197 193768 : bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) {
198 193768 : MF = &mf;
199 193768 : bundles = &getAnalysis<EdgeBundles>();
200 193768 : loops = &getAnalysis<MachineLoopInfo>();
201 :
202 : assert(!nodes && "Leaking node array");
203 951482 : nodes = new Node[bundles->getNumBundles()];
204 : TodoList.clear();
205 387536 : TodoList.setUniverse(bundles->getNumBundles());
206 :
207 : // Compute total ingoing and outgoing block frequencies for all bundles.
208 387536 : BlockFrequencies.resize(mf.getNumBlockIDs());
209 193768 : MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
210 193768 : setThreshold(MBFI->getEntryFreq());
211 651473 : for (auto &I : mf) {
212 457706 : unsigned Num = I.getNumber();
213 915412 : BlockFrequencies[Num] = MBFI->getBlockFreq(&I);
214 : }
215 :
216 : // We never change the function.
217 193767 : return false;
218 : }
219 :
220 213142 : void SpillPlacement::releaseMemory() {
221 777082 : delete[] nodes;
222 213142 : nodes = nullptr;
223 : TodoList.clear();
224 213142 : }
225 :
226 : /// activate - mark node n as active if it wasn't already.
227 5913723 : void SpillPlacement::activate(unsigned n) {
228 5913723 : TodoList.insert(n);
229 11827446 : if (ActiveNodes->test(n))
230 : return;
231 : ActiveNodes->set(n);
232 2551055 : nodes[n].clear(Threshold);
233 :
234 : // Very large bundles usually come from big switches, indirect branches,
235 : // landing pads, or loops with many 'continue' statements. It is difficult to
236 : // allocate registers when so many different blocks are involved.
237 : //
238 : // Give a small negative bias to large bundles such that a substantial
239 : // fraction of the connected blocks need to be interested before we consider
240 : // expanding the region through the bundle. This helps compile time by
241 : // limiting the number of blocks visited and the number of links in the
242 : // Hopfield network.
243 5102110 : if (bundles->getBlocks(n).size() > 100) {
244 0 : nodes[n].BiasP = 0;
245 0 : nodes[n].BiasN = (MBFI->getEntryFreq() / 16);
246 : }
247 : }
248 :
249 : /// Set the threshold for a given entry frequency.
250 : ///
251 : /// Set the threshold relative to \c Entry. Since the threshold is used as a
252 : /// bound on the open interval (-Threshold;Threshold), 1 is the minimum
253 : /// threshold.
254 193768 : void SpillPlacement::setThreshold(const BlockFrequency &Entry) {
255 : // Apparently 2 is a good threshold when Entry==2^14, but we need to scale
256 : // it. Divide by 2^13, rounding as appropriate.
257 193768 : uint64_t Freq = Entry.getFrequency();
258 193768 : uint64_t Scaled = (Freq >> 13) + bool(Freq & (1 << 12));
259 193768 : Threshold = std::max(UINT64_C(1), Scaled);
260 193768 : }
261 :
262 : /// addConstraints - Compute node biases and weights from a set of constraints.
263 : /// Set a bit in NodeMask for each active node.
264 756121 : void SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) {
265 1801264 : for (ArrayRef<BlockConstraint>::iterator I = LiveBlocks.begin(),
266 2557385 : E = LiveBlocks.end(); I != E; ++I) {
267 1801264 : BlockFrequency Freq = BlockFrequencies[I->Number];
268 :
269 : // Live-in to block?
270 1801264 : if (I->Entry != DontCare) {
271 1410037 : unsigned ib = bundles->getBundle(I->Number, false);
272 1410037 : activate(ib);
273 1410037 : nodes[ib].addBias(Freq, I->Entry);
274 : }
275 :
276 : // Live-out from block?
277 1801264 : if (I->Exit != DontCare) {
278 1555388 : unsigned ob = bundles->getBundle(I->Number, true);
279 1555388 : activate(ob);
280 1555388 : nodes[ob].addBias(Freq, I->Exit);
281 : }
282 : }
283 756121 : }
284 :
285 : /// addPrefSpill - Same as addConstraints(PrefSpill)
286 18563 : void SpillPlacement::addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong) {
287 18563 : for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
288 155401 : I != E; ++I) {
289 136838 : BlockFrequency Freq = BlockFrequencies[*I];
290 136838 : if (Strong)
291 136838 : Freq += Freq;
292 136838 : unsigned ib = bundles->getBundle(*I, false);
293 : unsigned ob = bundles->getBundle(*I, true);
294 136838 : activate(ib);
295 136838 : activate(ob);
296 136838 : nodes[ib].addBias(Freq, PrefSpill);
297 136838 : nodes[ob].addBias(Freq, PrefSpill);
298 : }
299 18563 : }
300 :
301 466079 : void SpillPlacement::addLinks(ArrayRef<unsigned> Links) {
302 1912471 : for (ArrayRef<unsigned>::iterator I = Links.begin(), E = Links.end(); I != E;
303 : ++I) {
304 1446392 : unsigned Number = *I;
305 1446392 : unsigned ib = bundles->getBundle(Number, false);
306 : unsigned ob = bundles->getBundle(Number, true);
307 :
308 : // Ignore self-loops.
309 1446392 : if (ib == ob)
310 109081 : continue;
311 1337311 : activate(ib);
312 1337311 : activate(ob);
313 1337311 : BlockFrequency Freq = BlockFrequencies[Number];
314 1337311 : nodes[ib].addLink(ob, Freq);
315 1337311 : nodes[ob].addLink(ib, Freq);
316 : }
317 466079 : }
318 :
319 338763 : bool SpillPlacement::scanActiveBundles() {
320 : RecentPositive.clear();
321 1563011 : for (unsigned n : ActiveNodes->set_bits()) {
322 1224248 : update(n);
323 : // A node that must spill, or a node without any links is not going to
324 : // change its value ever again, so exclude it from iterations.
325 1224248 : if (nodes[n].mustSpill())
326 : continue;
327 690061 : if (nodes[n].preferReg())
328 582894 : RecentPositive.push_back(n);
329 : }
330 338763 : return !RecentPositive.empty();
331 : }
332 :
333 4570282 : bool SpillPlacement::update(unsigned n) {
334 4570282 : if (!nodes[n].update(nodes, Threshold))
335 : return false;
336 1930286 : nodes[n].getDissentingNeighbors(TodoList, nodes);
337 1930286 : return true;
338 : }
339 :
340 : /// iterate - Repeatedly update the Hopfield nodes until stability or the
341 : /// maximum number of iterations is reached.
342 421462 : void SpillPlacement::iterate() {
343 : // We do not need to push those node in the todolist.
344 : // They are already been proceeded as part of the previous iteration.
345 : RecentPositive.clear();
346 :
347 : // Since the last iteration, the todolist have been augmented by calls
348 : // to addConstraints, addLinks, and co.
349 : // Update the network energy starting at this new frontier.
350 : // The call to ::update will add the nodes that changed into the todolist.
351 842924 : unsigned Limit = bundles->getNumBundles() * 10;
352 3767496 : while(Limit-- > 0 && !TodoList.empty()) {
353 3346034 : unsigned n = TodoList.pop_back_val();
354 3346034 : if (!update(n))
355 1998642 : continue;
356 1347392 : if (nodes[n].preferReg())
357 807523 : RecentPositive.push_back(n);
358 : }
359 421462 : }
360 :
361 338763 : void SpillPlacement::prepare(BitVector &RegBundles) {
362 : RecentPositive.clear();
363 : TodoList.clear();
364 : // Reuse RegBundles as our ActiveNodes vector.
365 338763 : ActiveNodes = &RegBundles;
366 : ActiveNodes->clear();
367 677526 : ActiveNodes->resize(bundles->getNumBundles());
368 338763 : }
369 :
370 : bool
371 149270 : SpillPlacement::finish() {
372 : assert(ActiveNodes && "Call prepare() first");
373 :
374 : // Write preferences back to ActiveNodes.
375 : bool Perfect = true;
376 2098326 : for (unsigned n : ActiveNodes->set_bits())
377 1949056 : if (!nodes[n].preferReg()) {
378 1221704 : ActiveNodes->reset(n);
379 : Perfect = false;
380 : }
381 149270 : ActiveNodes = nullptr;
382 149270 : return Perfect;
383 : }
|
