Track IR ordering of SelectionDAG nodes 3/4.
[oota-llvm.git] / lib / CodeGen / SpillPlacement.cpp
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 #define DEBUG_TYPE "spillplacement"
31 #include "SpillPlacement.h"
32 #include "llvm/ADT/BitVector.h"
33 #include "llvm/CodeGen/EdgeBundles.h"
34 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
35 #include "llvm/CodeGen/MachineBasicBlock.h"
36 #include "llvm/CodeGen/MachineFunction.h"
37 #include "llvm/CodeGen/MachineLoopInfo.h"
38 #include "llvm/CodeGen/Passes.h"
39 #include "llvm/Support/Debug.h"
40 #include "llvm/Support/Format.h"
41
42 using namespace llvm;
43
44 char SpillPlacement::ID = 0;
45 INITIALIZE_PASS_BEGIN(SpillPlacement, "spill-code-placement",
46                       "Spill Code Placement Analysis", true, true)
47 INITIALIZE_PASS_DEPENDENCY(EdgeBundles)
48 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
49 INITIALIZE_PASS_END(SpillPlacement, "spill-code-placement",
50                     "Spill Code Placement Analysis", true, true)
51
52 char &llvm::SpillPlacementID = SpillPlacement::ID;
53
54 void SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const {
55   AU.setPreservesAll();
56   AU.addRequiredTransitive<EdgeBundles>();
57   AU.addRequiredTransitive<MachineLoopInfo>();
58   MachineFunctionPass::getAnalysisUsage(AU);
59 }
60
61 /// Node - Each edge bundle corresponds to a Hopfield node.
62 ///
63 /// The node contains precomputed frequency data that only depends on the CFG,
64 /// but Bias and Links are computed each time placeSpills is called.
65 ///
66 /// The node Value is positive when the variable should be in a register. The
67 /// value can change when linked nodes change, but convergence is very fast
68 /// because all weights are positive.
69 ///
70 struct SpillPlacement::Node {
71   /// Scale - Inverse block frequency feeding into[0] or out of[1] the bundle.
72   /// Ideally, these two numbers should be identical, but inaccuracies in the
73   /// block frequency estimates means that we need to normalize ingoing and
74   /// outgoing frequencies separately so they are commensurate.
75   float Scale[2];
76
77   /// Bias - Normalized contributions from non-transparent blocks.
78   /// A bundle connected to a MustSpill block has a huge negative bias,
79   /// otherwise it is a number in the range [-2;2].
80   float Bias;
81
82   /// Value - Output value of this node computed from the Bias and links.
83   /// This is always in the range [-1;1]. A positive number means the variable
84   /// should go in a register through this bundle.
85   float Value;
86
87   typedef SmallVector<std::pair<float, unsigned>, 4> LinkVector;
88
89   /// Links - (Weight, BundleNo) for all transparent blocks connecting to other
90   /// bundles. The weights are all positive and add up to at most 2, weights
91   /// from ingoing and outgoing nodes separately add up to a most 1. The weight
92   /// sum can be less than 2 when the variable is not live into / out of some
93   /// connected basic blocks.
94   LinkVector Links;
95
96   /// preferReg - Return true when this node prefers to be in a register.
97   bool preferReg() const {
98     // Undecided nodes (Value==0) go on the stack.
99     return Value > 0;
100   }
101
102   /// mustSpill - Return True if this node is so biased that it must spill.
103   bool mustSpill() const {
104     // Actually, we must spill if Bias < sum(weights).
105     // It may be worth it to compute the weight sum here?
106     return Bias < -2.0f;
107   }
108
109   /// Node - Create a blank Node.
110   Node() {
111     Scale[0] = Scale[1] = 0;
112   }
113
114   /// clear - Reset per-query data, but preserve frequencies that only depend on
115   // the CFG.
116   void clear() {
117     Bias = Value = 0;
118     Links.clear();
119   }
120
121   /// addLink - Add a link to bundle b with weight w.
122   /// out=0 for an ingoing link, and 1 for an outgoing link.
123   void addLink(unsigned b, float w, bool out) {
124     // Normalize w relative to all connected blocks from that direction.
125     w *= Scale[out];
126
127     // There can be multiple links to the same bundle, add them up.
128     for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I)
129       if (I->second == b) {
130         I->first += w;
131         return;
132       }
133     // This must be the first link to b.
134     Links.push_back(std::make_pair(w, b));
135   }
136
137   /// addBias - Bias this node from an ingoing[0] or outgoing[1] link.
138   /// Return the change to the total number of positive biases.
139   void addBias(float w, bool out) {
140     // Normalize w relative to all connected blocks from that direction.
141     w *= Scale[out];
142     Bias += w;
143   }
144
145   /// update - Recompute Value from Bias and Links. Return true when node
146   /// preference changes.
147   bool update(const Node nodes[]) {
148     // Compute the weighted sum of inputs.
149     float Sum = Bias;
150     for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I)
151       Sum += I->first * nodes[I->second].Value;
152
153     // The weighted sum is going to be in the range [-2;2]. Ideally, we should
154     // simply set Value = sign(Sum), but we will add a dead zone around 0 for
155     // two reasons:
156     //  1. It avoids arbitrary bias when all links are 0 as is possible during
157     //     initial iterations.
158     //  2. It helps tame rounding errors when the links nominally sum to 0.
159     const float Thres = 1e-4f;
160     bool Before = preferReg();
161     if (Sum < -Thres)
162       Value = -1;
163     else if (Sum > Thres)
164       Value = 1;
165     else
166       Value = 0;
167     return Before != preferReg();
168   }
169 };
170
171 bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) {
172   MF = &mf;
173   bundles = &getAnalysis<EdgeBundles>();
174   loops = &getAnalysis<MachineLoopInfo>();
175
176   assert(!nodes && "Leaking node array");
177   nodes = new Node[bundles->getNumBundles()];
178
179   // Compute total ingoing and outgoing block frequencies for all bundles.
180   BlockFrequency.resize(mf.getNumBlockIDs());
181   for (MachineFunction::iterator I = mf.begin(), E = mf.end(); I != E; ++I) {
182     float Freq = LiveIntervals::getSpillWeight(true, false,
183                                                loops->getLoopDepth(I));
184     unsigned Num = I->getNumber();
185     BlockFrequency[Num] = Freq;
186     nodes[bundles->getBundle(Num, 1)].Scale[0] += Freq;
187     nodes[bundles->getBundle(Num, 0)].Scale[1] += Freq;
188   }
189
190   // Scales are reciprocal frequencies.
191   for (unsigned i = 0, e = bundles->getNumBundles(); i != e; ++i)
192     for (unsigned d = 0; d != 2; ++d)
193       if (nodes[i].Scale[d] > 0)
194         nodes[i].Scale[d] = 1 / nodes[i].Scale[d];
195
196   // We never change the function.
197   return false;
198 }
199
200 void SpillPlacement::releaseMemory() {
201   delete[] nodes;
202   nodes = 0;
203 }
204
205 /// activate - mark node n as active if it wasn't already.
206 void SpillPlacement::activate(unsigned n) {
207   if (ActiveNodes->test(n))
208     return;
209   ActiveNodes->set(n);
210   nodes[n].clear();
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 1/32 of the
217   // connected blocks need to be interested before we consider expanding the
218   // region through the bundle. This helps compile time by limiting the number
219   // of blocks visited and the number of links in the Hopfield network.
220   if (bundles->getBlocks(n).size() > 100)
221     nodes[n].Bias = -0.0625f;
222 }
223
224
225 /// addConstraints - Compute node biases and weights from a set of constraints.
226 /// Set a bit in NodeMask for each active node.
227 void SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) {
228   for (ArrayRef<BlockConstraint>::iterator I = LiveBlocks.begin(),
229        E = LiveBlocks.end(); I != E; ++I) {
230     float Freq = getBlockFrequency(I->Number);
231     const float Bias[] = {
232       0,           // DontCare,
233       1,           // PrefReg,
234       -1,          // PrefSpill
235       0,           // PrefBoth
236       -HUGE_VALF   // MustSpill
237     };
238
239     // Live-in to block?
240     if (I->Entry != DontCare) {
241       unsigned ib = bundles->getBundle(I->Number, 0);
242       activate(ib);
243       nodes[ib].addBias(Freq * Bias[I->Entry], 1);
244     }
245
246     // Live-out from block?
247     if (I->Exit != DontCare) {
248       unsigned ob = bundles->getBundle(I->Number, 1);
249       activate(ob);
250       nodes[ob].addBias(Freq * Bias[I->Exit], 0);
251     }
252   }
253 }
254
255 /// addPrefSpill - Same as addConstraints(PrefSpill)
256 void SpillPlacement::addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong) {
257   for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
258        I != E; ++I) {
259     float Freq = getBlockFrequency(*I);
260     if (Strong)
261       Freq += Freq;
262     unsigned ib = bundles->getBundle(*I, 0);
263     unsigned ob = bundles->getBundle(*I, 1);
264     activate(ib);
265     activate(ob);
266     nodes[ib].addBias(-Freq, 1);
267     nodes[ob].addBias(-Freq, 0);
268   }
269 }
270
271 void SpillPlacement::addLinks(ArrayRef<unsigned> Links) {
272   for (ArrayRef<unsigned>::iterator I = Links.begin(), E = Links.end(); I != E;
273        ++I) {
274     unsigned Number = *I;
275     unsigned ib = bundles->getBundle(Number, 0);
276     unsigned ob = bundles->getBundle(Number, 1);
277
278     // Ignore self-loops.
279     if (ib == ob)
280       continue;
281     activate(ib);
282     activate(ob);
283     if (nodes[ib].Links.empty() && !nodes[ib].mustSpill())
284       Linked.push_back(ib);
285     if (nodes[ob].Links.empty() && !nodes[ob].mustSpill())
286       Linked.push_back(ob);
287     float Freq = getBlockFrequency(Number);
288     nodes[ib].addLink(ob, Freq, 1);
289     nodes[ob].addLink(ib, Freq, 0);
290   }
291 }
292
293 bool SpillPlacement::scanActiveBundles() {
294   Linked.clear();
295   RecentPositive.clear();
296   for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) {
297     nodes[n].update(nodes);
298     // A node that must spill, or a node without any links is not going to
299     // change its value ever again, so exclude it from iterations.
300     if (nodes[n].mustSpill())
301       continue;
302     if (!nodes[n].Links.empty())
303       Linked.push_back(n);
304     if (nodes[n].preferReg())
305       RecentPositive.push_back(n);
306   }
307   return !RecentPositive.empty();
308 }
309
310 /// iterate - Repeatedly update the Hopfield nodes until stability or the
311 /// maximum number of iterations is reached.
312 /// @param Linked - Numbers of linked nodes that need updating.
313 void SpillPlacement::iterate() {
314   // First update the recently positive nodes. They have likely received new
315   // negative bias that will turn them off.
316   while (!RecentPositive.empty())
317     nodes[RecentPositive.pop_back_val()].update(nodes);
318
319   if (Linked.empty())
320     return;
321
322   // Run up to 10 iterations. The edge bundle numbering is closely related to
323   // basic block numbering, so there is a strong tendency towards chains of
324   // linked nodes with sequential numbers. By scanning the linked nodes
325   // backwards and forwards, we make it very likely that a single node can
326   // affect the entire network in a single iteration. That means very fast
327   // convergence, usually in a single iteration.
328   for (unsigned iteration = 0; iteration != 10; ++iteration) {
329     // Scan backwards, skipping the last node which was just updated.
330     bool Changed = false;
331     for (SmallVectorImpl<unsigned>::const_reverse_iterator I =
332            llvm::next(Linked.rbegin()), E = Linked.rend(); I != E; ++I) {
333       unsigned n = *I;
334       if (nodes[n].update(nodes)) {
335         Changed = true;
336         if (nodes[n].preferReg())
337           RecentPositive.push_back(n);
338       }
339     }
340     if (!Changed || !RecentPositive.empty())
341       return;
342
343     // Scan forwards, skipping the first node which was just updated.
344     Changed = false;
345     for (SmallVectorImpl<unsigned>::const_iterator I =
346            llvm::next(Linked.begin()), E = Linked.end(); I != E; ++I) {
347       unsigned n = *I;
348       if (nodes[n].update(nodes)) {
349         Changed = true;
350         if (nodes[n].preferReg())
351           RecentPositive.push_back(n);
352       }
353     }
354     if (!Changed || !RecentPositive.empty())
355       return;
356   }
357 }
358
359 void SpillPlacement::prepare(BitVector &RegBundles) {
360   Linked.clear();
361   RecentPositive.clear();
362   // Reuse RegBundles as our ActiveNodes vector.
363   ActiveNodes = &RegBundles;
364   ActiveNodes->clear();
365   ActiveNodes->resize(bundles->getNumBundles());
366 }
367
368 bool
369 SpillPlacement::finish() {
370   assert(ActiveNodes && "Call prepare() first");
371
372   // Write preferences back to ActiveNodes.
373   bool Perfect = true;
374   for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n))
375     if (!nodes[n].preferReg()) {
376       ActiveNodes->reset(n);
377       Perfect = false;
378     }
379   ActiveNodes = 0;
380   return Perfect;
381 }