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/BitVector.h"
32 #include "llvm/CodeGen/EdgeBundles.h"
33 #include "llvm/CodeGen/MachineBasicBlock.h"
34 #include "llvm/CodeGen/MachineBlockFrequencyInfo.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"
40 #include "llvm/Support/ManagedStatic.h"
41 
42 using namespace llvm;
43 
44 #define DEBUG_TYPE "spillplacement"
45 
46 char SpillPlacement::ID = 0;
47 INITIALIZE_PASS_BEGIN(SpillPlacement, "spill-code-placement",
48                       "Spill Code Placement Analysis", true, true)
49 INITIALIZE_PASS_DEPENDENCY(EdgeBundles)
50 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
51 INITIALIZE_PASS_END(SpillPlacement, "spill-code-placement",
52                     "Spill Code Placement Analysis", true, true)
53 
54 char &llvm::SpillPlacementID = SpillPlacement::ID;
55 
getAnalysisUsage(AnalysisUsage & AU) const56 void SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const {
57   AU.setPreservesAll();
58   AU.addRequired<MachineBlockFrequencyInfo>();
59   AU.addRequiredTransitive<EdgeBundles>();
60   AU.addRequiredTransitive<MachineLoopInfo>();
61   MachineFunctionPass::getAnalysisUsage(AU);
62 }
63 
64 /// Node - Each edge bundle corresponds to a Hopfield node.
65 ///
66 /// The node contains precomputed frequency data that only depends on the CFG,
67 /// but Bias and Links are computed each time placeSpills is called.
68 ///
69 /// The node Value is positive when the variable should be in a register. The
70 /// value can change when linked nodes change, but convergence is very fast
71 /// because all weights are positive.
72 ///
73 struct SpillPlacement::Node {
74   /// BiasN - Sum of blocks that prefer a spill.
75   BlockFrequency BiasN;
76   /// BiasP - Sum of blocks that prefer a register.
77   BlockFrequency BiasP;
78 
79   /// Value - Output value of this node computed from the Bias and links.
80   /// This is always on of the values {-1, 0, 1}. A positive number means the
81   /// variable should go in a register through this bundle.
82   int Value;
83 
84   typedef SmallVector<std::pair<BlockFrequency, unsigned>, 4> LinkVector;
85 
86   /// Links - (Weight, BundleNo) for all transparent blocks connecting to other
87   /// bundles. The weights are all positive block frequencies.
88   LinkVector Links;
89 
90   /// SumLinkWeights - Cached sum of the weights of all links + ThresHold.
91   BlockFrequency SumLinkWeights;
92 
93   /// preferReg - Return true when this node prefers to be in a register.
preferRegSpillPlacement::Node94   bool preferReg() const {
95     // Undecided nodes (Value==0) go on the stack.
96     return Value > 0;
97   }
98 
99   /// mustSpill - Return True if this node is so biased that it must spill.
mustSpillSpillPlacement::Node100   bool mustSpill() const {
101     // We must spill if Bias < -sum(weights) or the MustSpill flag was set.
102     // BiasN is saturated when MustSpill is set, make sure this still returns
103     // true when the RHS saturates. Note that SumLinkWeights includes Threshold.
104     return BiasN >= BiasP + SumLinkWeights;
105   }
106 
107   /// clear - Reset per-query data, but preserve frequencies that only depend on
108   // the CFG.
clearSpillPlacement::Node109   void clear(const BlockFrequency &Threshold) {
110     BiasN = BiasP = Value = 0;
111     SumLinkWeights = Threshold;
112     Links.clear();
113   }
114 
115   /// addLink - Add a link to bundle b with weight w.
addLinkSpillPlacement::Node116   void addLink(unsigned b, BlockFrequency w) {
117     // Update cached sum.
118     SumLinkWeights += w;
119 
120     // There can be multiple links to the same bundle, add them up.
121     for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I)
122       if (I->second == b) {
123         I->first += w;
124         return;
125       }
126     // This must be the first link to b.
127     Links.push_back(std::make_pair(w, b));
128   }
129 
130   /// addBias - Bias this node.
addBiasSpillPlacement::Node131   void addBias(BlockFrequency freq, BorderConstraint direction) {
132     switch (direction) {
133     default:
134       break;
135     case PrefReg:
136       BiasP += freq;
137       break;
138     case PrefSpill:
139       BiasN += freq;
140       break;
141     case MustSpill:
142       BiasN = BlockFrequency::getMaxFrequency();
143       break;
144     }
145   }
146 
147   /// update - Recompute Value from Bias and Links. Return true when node
148   /// preference changes.
updateSpillPlacement::Node149   bool update(const Node nodes[], const BlockFrequency &Threshold) {
150     // Compute the weighted sum of inputs.
151     BlockFrequency SumN = BiasN;
152     BlockFrequency SumP = BiasP;
153     for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) {
154       if (nodes[I->second].Value == -1)
155         SumN += I->first;
156       else if (nodes[I->second].Value == 1)
157         SumP += I->first;
158     }
159 
160     // Each weighted sum is going to be less than the total frequency of the
161     // bundle. Ideally, we should simply set Value = sign(SumP - SumN), but we
162     // will add a dead zone around 0 for two reasons:
163     //
164     //  1. It avoids arbitrary bias when all links are 0 as is possible during
165     //     initial iterations.
166     //  2. It helps tame rounding errors when the links nominally sum to 0.
167     //
168     bool Before = preferReg();
169     if (SumN >= SumP + Threshold)
170       Value = -1;
171     else if (SumP >= SumN + Threshold)
172       Value = 1;
173     else
174       Value = 0;
175     return Before != preferReg();
176   }
177 };
178 
runOnMachineFunction(MachineFunction & mf)179 bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) {
180   MF = &mf;
181   bundles = &getAnalysis<EdgeBundles>();
182   loops = &getAnalysis<MachineLoopInfo>();
183 
184   assert(!nodes && "Leaking node array");
185   nodes = new Node[bundles->getNumBundles()];
186 
187   // Compute total ingoing and outgoing block frequencies for all bundles.
188   BlockFrequencies.resize(mf.getNumBlockIDs());
189   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
190   setThreshold(MBFI->getEntryFreq());
191   for (MachineFunction::iterator I = mf.begin(), E = mf.end(); I != E; ++I) {
192     unsigned Num = I->getNumber();
193     BlockFrequencies[Num] = MBFI->getBlockFreq(I);
194   }
195 
196   // We never change the function.
197   return false;
198 }
199 
releaseMemory()200 void SpillPlacement::releaseMemory() {
201   delete[] nodes;
202   nodes = nullptr;
203 }
204 
205 /// activate - mark node n as active if it wasn't already.
activate(unsigned n)206 void SpillPlacement::activate(unsigned n) {
207   if (ActiveNodes->test(n))
208     return;
209   ActiveNodes->set(n);
210   nodes[n].clear(Threshold);
211 
212   // Very large bundles usually come from big switches, indirect branches,
213   // landing pads, or loops with many 'continue' statements. It is difficult to
214   // allocate registers when so many different blocks are involved.
215   //
216   // Give a small negative bias to large bundles such that a substantial
217   // fraction of the connected blocks need to be interested before we consider
218   // expanding the region through the bundle. This helps compile time by
219   // limiting the number of blocks visited and the number of links in the
220   // Hopfield network.
221   if (bundles->getBlocks(n).size() > 100) {
222     nodes[n].BiasP = 0;
223     nodes[n].BiasN = (MBFI->getEntryFreq() / 16);
224   }
225 }
226 
227 /// \brief Set the threshold for a given entry frequency.
228 ///
229 /// Set the threshold relative to \c Entry.  Since the threshold is used as a
230 /// bound on the open interval (-Threshold;Threshold), 1 is the minimum
231 /// threshold.
setThreshold(const BlockFrequency & Entry)232 void SpillPlacement::setThreshold(const BlockFrequency &Entry) {
233   // Apparently 2 is a good threshold when Entry==2^14, but we need to scale
234   // it.  Divide by 2^13, rounding as appropriate.
235   uint64_t Freq = Entry.getFrequency();
236   uint64_t Scaled = (Freq >> 13) + bool(Freq & (1 << 12));
237   Threshold = std::max(UINT64_C(1), Scaled);
238 }
239 
240 /// addConstraints - Compute node biases and weights from a set of constraints.
241 /// Set a bit in NodeMask for each active node.
addConstraints(ArrayRef<BlockConstraint> LiveBlocks)242 void SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) {
243   for (ArrayRef<BlockConstraint>::iterator I = LiveBlocks.begin(),
244        E = LiveBlocks.end(); I != E; ++I) {
245     BlockFrequency Freq = BlockFrequencies[I->Number];
246 
247     // Live-in to block?
248     if (I->Entry != DontCare) {
249       unsigned ib = bundles->getBundle(I->Number, 0);
250       activate(ib);
251       nodes[ib].addBias(Freq, I->Entry);
252     }
253 
254     // Live-out from block?
255     if (I->Exit != DontCare) {
256       unsigned ob = bundles->getBundle(I->Number, 1);
257       activate(ob);
258       nodes[ob].addBias(Freq, I->Exit);
259     }
260   }
261 }
262 
263 /// addPrefSpill - Same as addConstraints(PrefSpill)
addPrefSpill(ArrayRef<unsigned> Blocks,bool Strong)264 void SpillPlacement::addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong) {
265   for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
266        I != E; ++I) {
267     BlockFrequency Freq = BlockFrequencies[*I];
268     if (Strong)
269       Freq += Freq;
270     unsigned ib = bundles->getBundle(*I, 0);
271     unsigned ob = bundles->getBundle(*I, 1);
272     activate(ib);
273     activate(ob);
274     nodes[ib].addBias(Freq, PrefSpill);
275     nodes[ob].addBias(Freq, PrefSpill);
276   }
277 }
278 
addLinks(ArrayRef<unsigned> Links)279 void SpillPlacement::addLinks(ArrayRef<unsigned> Links) {
280   for (ArrayRef<unsigned>::iterator I = Links.begin(), E = Links.end(); I != E;
281        ++I) {
282     unsigned Number = *I;
283     unsigned ib = bundles->getBundle(Number, 0);
284     unsigned ob = bundles->getBundle(Number, 1);
285 
286     // Ignore self-loops.
287     if (ib == ob)
288       continue;
289     activate(ib);
290     activate(ob);
291     if (nodes[ib].Links.empty() && !nodes[ib].mustSpill())
292       Linked.push_back(ib);
293     if (nodes[ob].Links.empty() && !nodes[ob].mustSpill())
294       Linked.push_back(ob);
295     BlockFrequency Freq = BlockFrequencies[Number];
296     nodes[ib].addLink(ob, Freq);
297     nodes[ob].addLink(ib, Freq);
298   }
299 }
300 
scanActiveBundles()301 bool SpillPlacement::scanActiveBundles() {
302   Linked.clear();
303   RecentPositive.clear();
304   for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) {
305     nodes[n].update(nodes, Threshold);
306     // A node that must spill, or a node without any links is not going to
307     // change its value ever again, so exclude it from iterations.
308     if (nodes[n].mustSpill())
309       continue;
310     if (!nodes[n].Links.empty())
311       Linked.push_back(n);
312     if (nodes[n].preferReg())
313       RecentPositive.push_back(n);
314   }
315   return !RecentPositive.empty();
316 }
317 
318 /// iterate - Repeatedly update the Hopfield nodes until stability or the
319 /// maximum number of iterations is reached.
320 /// @param Linked - Numbers of linked nodes that need updating.
iterate()321 void SpillPlacement::iterate() {
322   // First update the recently positive nodes. They have likely received new
323   // negative bias that will turn them off.
324   while (!RecentPositive.empty())
325     nodes[RecentPositive.pop_back_val()].update(nodes, Threshold);
326 
327   if (Linked.empty())
328     return;
329 
330   // Run up to 10 iterations. The edge bundle numbering is closely related to
331   // basic block numbering, so there is a strong tendency towards chains of
332   // linked nodes with sequential numbers. By scanning the linked nodes
333   // backwards and forwards, we make it very likely that a single node can
334   // affect the entire network in a single iteration. That means very fast
335   // convergence, usually in a single iteration.
336   for (unsigned iteration = 0; iteration != 10; ++iteration) {
337     // Scan backwards, skipping the last node when iteration is not zero. When
338     // iteration is not zero, the last node was just updated.
339     bool Changed = false;
340     for (SmallVectorImpl<unsigned>::const_reverse_iterator I =
341            iteration == 0 ? Linked.rbegin() : std::next(Linked.rbegin()),
342            E = Linked.rend(); I != E; ++I) {
343       unsigned n = *I;
344       if (nodes[n].update(nodes, Threshold)) {
345         Changed = true;
346         if (nodes[n].preferReg())
347           RecentPositive.push_back(n);
348       }
349     }
350     if (!Changed || !RecentPositive.empty())
351       return;
352 
353     // Scan forwards, skipping the first node which was just updated.
354     Changed = false;
355     for (SmallVectorImpl<unsigned>::const_iterator I =
356            std::next(Linked.begin()), E = Linked.end(); I != E; ++I) {
357       unsigned n = *I;
358       if (nodes[n].update(nodes, Threshold)) {
359         Changed = true;
360         if (nodes[n].preferReg())
361           RecentPositive.push_back(n);
362       }
363     }
364     if (!Changed || !RecentPositive.empty())
365       return;
366   }
367 }
368 
prepare(BitVector & RegBundles)369 void SpillPlacement::prepare(BitVector &RegBundles) {
370   Linked.clear();
371   RecentPositive.clear();
372   // Reuse RegBundles as our ActiveNodes vector.
373   ActiveNodes = &RegBundles;
374   ActiveNodes->clear();
375   ActiveNodes->resize(bundles->getNumBundles());
376 }
377 
378 bool
finish()379 SpillPlacement::finish() {
380   assert(ActiveNodes && "Call prepare() first");
381 
382   // Write preferences back to ActiveNodes.
383   bool Perfect = true;
384   for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n))
385     if (!nodes[n].preferReg()) {
386       ActiveNodes->reset(n);
387       Perfect = false;
388     }
389   ActiveNodes = nullptr;
390   return Perfect;
391 }
392