LLVM  6.0.0svn
SpillPlacement.cpp
Go to the documentation of this file.
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"
40 #include "llvm/CodeGen/Passes.h"
41 #include "llvm/Pass.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 
55 
57  "Spill Code Placement Analysis", true, true)
61  "Spill Code Placement Analysis", true, true)
62 
63 void SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const {
64  AU.setPreservesAll();
65  AU.addRequired<MachineBlockFrequencyInfo>();
66  AU.addRequiredTransitive<EdgeBundles>();
67  AU.addRequiredTransitive<MachineLoopInfo>();
69 }
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.
80  /// BiasN - Sum of blocks that prefer a spill.
82 
83  /// BiasP - Sum of blocks that prefer a register.
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 
92 
93  /// Links - (Weight, BundleNo) for all transparent blocks connecting to other
94  /// bundles. The weights are all positive block frequencies.
96 
97  /// SumLinkWeights - Cached sum of the weights of all links + ThresHold.
99 
100  /// preferReg - Return true when this node prefers to be in a register.
101  bool preferReg() const {
102  // Undecided nodes (Value==0) go on the stack.
103  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  return BiasN >= BiasP + SumLinkWeights;
112  }
113 
114  /// clear - Reset per-query data, but preserve frequencies that only depend on
115  /// the CFG.
116  void clear(const BlockFrequency &Threshold) {
117  BiasN = BiasP = Value = 0;
118  SumLinkWeights = Threshold;
119  Links.clear();
120  }
121 
122  /// addLink - Add a link to bundle b with weight w.
123  void addLink(unsigned b, BlockFrequency w) {
124  // Update cached sum.
125  SumLinkWeights += w;
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.
139  switch (direction) {
140  default:
141  break;
142  case PrefReg:
143  BiasP += freq;
144  break;
145  case PrefSpill:
146  BiasN += freq;
147  break;
148  case MustSpill:
150  break;
151  }
152  }
153 
154  /// update - Recompute Value from Bias and Links. Return true when node
155  /// preference changes.
156  bool update(const Node nodes[], const BlockFrequency &Threshold) {
157  // Compute the weighted sum of inputs.
158  BlockFrequency SumN = BiasN;
159  BlockFrequency SumP = BiasP;
160  for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) {
161  if (nodes[I->second].Value == -1)
162  SumN += I->first;
163  else if (nodes[I->second].Value == 1)
164  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  bool Before = preferReg();
176  if (SumN >= SumP + Threshold)
177  Value = -1;
178  else if (SumP >= SumN + Threshold)
179  Value = 1;
180  else
181  Value = 0;
182  return Before != preferReg();
183  }
184 
186  const Node nodes[]) const {
187  for (const auto &Elt : Links) {
188  unsigned n = Elt.second;
189  // Neighbors that already have the same value are not going to
190  // change because of this node changing.
191  if (Value != nodes[n].Value)
192  List.insert(n);
193  }
194  }
195 };
196 
197 bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) {
198  MF = &mf;
199  bundles = &getAnalysis<EdgeBundles>();
200  loops = &getAnalysis<MachineLoopInfo>();
201 
202  assert(!nodes && "Leaking node array");
203  nodes = new Node[bundles->getNumBundles()];
204  TodoList.clear();
205  TodoList.setUniverse(bundles->getNumBundles());
206 
207  // Compute total ingoing and outgoing block frequencies for all bundles.
208  BlockFrequencies.resize(mf.getNumBlockIDs());
209  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
210  setThreshold(MBFI->getEntryFreq());
211  for (auto &I : mf) {
212  unsigned Num = I.getNumber();
213  BlockFrequencies[Num] = MBFI->getBlockFreq(&I);
214  }
215 
216  // We never change the function.
217  return false;
218 }
219 
220 void SpillPlacement::releaseMemory() {
221  delete[] nodes;
222  nodes = nullptr;
223  TodoList.clear();
224 }
225 
226 /// activate - mark node n as active if it wasn't already.
227 void SpillPlacement::activate(unsigned n) {
228  TodoList.insert(n);
229  if (ActiveNodes->test(n))
230  return;
231  ActiveNodes->set(n);
232  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  if (bundles->getBlocks(n).size() > 100) {
244  nodes[n].BiasP = 0;
245  nodes[n].BiasN = (MBFI->getEntryFreq() / 16);
246  }
247 }
248 
249 /// \brief 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 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  uint64_t Freq = Entry.getFrequency();
258  uint64_t Scaled = (Freq >> 13) + bool(Freq & (1 << 12));
259  Threshold = std::max(UINT64_C(1), Scaled);
260 }
261 
262 /// addConstraints - Compute node biases and weights from a set of constraints.
263 /// Set a bit in NodeMask for each active node.
265  for (ArrayRef<BlockConstraint>::iterator I = LiveBlocks.begin(),
266  E = LiveBlocks.end(); I != E; ++I) {
267  BlockFrequency Freq = BlockFrequencies[I->Number];
268 
269  // Live-in to block?
270  if (I->Entry != DontCare) {
271  unsigned ib = bundles->getBundle(I->Number, false);
272  activate(ib);
273  nodes[ib].addBias(Freq, I->Entry);
274  }
275 
276  // Live-out from block?
277  if (I->Exit != DontCare) {
278  unsigned ob = bundles->getBundle(I->Number, true);
279  activate(ob);
280  nodes[ob].addBias(Freq, I->Exit);
281  }
282  }
283 }
284 
285 /// addPrefSpill - Same as addConstraints(PrefSpill)
287  for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
288  I != E; ++I) {
289  BlockFrequency Freq = BlockFrequencies[*I];
290  if (Strong)
291  Freq += Freq;
292  unsigned ib = bundles->getBundle(*I, false);
293  unsigned ob = bundles->getBundle(*I, true);
294  activate(ib);
295  activate(ob);
296  nodes[ib].addBias(Freq, PrefSpill);
297  nodes[ob].addBias(Freq, PrefSpill);
298  }
299 }
300 
302  for (ArrayRef<unsigned>::iterator I = Links.begin(), E = Links.end(); I != E;
303  ++I) {
304  unsigned Number = *I;
305  unsigned ib = bundles->getBundle(Number, false);
306  unsigned ob = bundles->getBundle(Number, true);
307 
308  // Ignore self-loops.
309  if (ib == ob)
310  continue;
311  activate(ib);
312  activate(ob);
313  BlockFrequency Freq = BlockFrequencies[Number];
314  nodes[ib].addLink(ob, Freq);
315  nodes[ob].addLink(ib, Freq);
316  }
317 }
318 
320  RecentPositive.clear();
321  for (unsigned n : ActiveNodes->set_bits()) {
322  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  if (nodes[n].mustSpill())
326  continue;
327  if (nodes[n].preferReg())
328  RecentPositive.push_back(n);
329  }
330  return !RecentPositive.empty();
331 }
332 
333 bool SpillPlacement::update(unsigned n) {
334  if (!nodes[n].update(nodes, Threshold))
335  return false;
336  nodes[n].getDissentingNeighbors(TodoList, nodes);
337  return true;
338 }
339 
340 /// iterate - Repeatedly update the Hopfield nodes until stability or the
341 /// maximum number of iterations is reached.
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  unsigned Limit = bundles->getNumBundles() * 10;
352  while(Limit-- > 0 && !TodoList.empty()) {
353  unsigned n = TodoList.pop_back_val();
354  if (!update(n))
355  continue;
356  if (nodes[n].preferReg())
357  RecentPositive.push_back(n);
358  }
359 }
360 
362  RecentPositive.clear();
363  TodoList.clear();
364  // Reuse RegBundles as our ActiveNodes vector.
365  ActiveNodes = &RegBundles;
366  ActiveNodes->clear();
367  ActiveNodes->resize(bundles->getNumBundles());
368 }
369 
370 bool
372  assert(ActiveNodes && "Call prepare() first");
373 
374  // Write preferences back to ActiveNodes.
375  bool Perfect = true;
376  for (unsigned n : ActiveNodes->set_bits())
377  if (!nodes[n].preferReg()) {
378  ActiveNodes->reset(n);
379  Perfect = false;
380  }
381  ActiveNodes = nullptr;
382  return Perfect;
383 }
int Value
Value - Output value of this node computed from the Bias and links.
void push_back(const T &Elt)
Definition: SmallVector.h:212
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
iterator begin() const
Definition: ArrayRef.h:137
std::pair< iterator, bool > insert(const ValueT &Val)
insert - Attempts to insert a new element.
Definition: SparseSet.h:249
A register is impossible, variable must be spilled.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID&#39;s allocated.
Spill Code Placement true
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
BlockFrequency BiasP
BiasP - Sum of blocks that prefer a register.
bool preferReg() const
preferReg - Return true when this node prefers to be in a register.
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
void clear()
clear - Removes all bits from the bitvector. Does not change capacity.
Definition: BitVector.h:367
void addPrefSpill(ArrayRef< unsigned > Blocks, bool Strong)
addPrefSpill - Add PrefSpill constraints to all blocks listed.
bool scanActiveBundles()
scanActiveBundles - Perform an initial scan of all bundles activated by addConstraints and addLinks...
LinkVector Links
Links - (Weight, BundleNo) for all transparent blocks connecting to other bundles.
void iterate()
iterate - Update the network iteratively until convergence, or new bundles are found.
void getDissentingNeighbors(SparseSet< unsigned > &List, const Node nodes[]) const
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
BlockFrequency SumLinkWeights
SumLinkWeights - Cached sum of the weights of all links + ThresHold.
void addBias(BlockFrequency freq, BorderConstraint direction)
addBias - Bias this node.
char & SpillPlacementID
SpillPlacement analysis.
void addLinks(ArrayRef< unsigned > Links)
addLinks - Add transparent blocks with the given numbers.
Unify divergent function exit nodes
Block doesn&#39;t care / variable not live.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
block freq
void clear(const BlockFrequency &Threshold)
clear - Reset per-query data, but preserve frequencies that only depend on the CFG.
Represent the analysis usage information of a pass.
bool update(const Node nodes[], const BlockFrequency &Threshold)
update - Recompute Value from Bias and Links.
bool finish()
finish - Compute the optimal spill code placement given the constraints.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Block entry/exit prefers a register.
Branch Probability Basic Block Placement
void addConstraints(ArrayRef< BlockConstraint > LiveBlocks)
addConstraints - Add constraints and biases.
Block entry/exit prefers a stack slot.
bool mustSpill() const
mustSpill - Return True if this node is so biased that it must spill.
INITIALIZE_PASS_BEGIN(SpillPlacement, DEBUG_TYPE, "Spill Code Placement Analysis", true, true) INITIALIZE_PASS_END(SpillPlacement
iterator end() const
Definition: ArrayRef.h:138
void prepare(BitVector &RegBundles)
prepare - Reset state and prepare for a new spill placement computation.
void addLink(unsigned b, BlockFrequency w)
addLink - Add a link to bundle b with weight w.
#define DEBUG_TYPE
Node - Each edge bundle corresponds to a Hopfield node.
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
static uint64_t getMaxFrequency()
Returns the maximum possible frequency, the saturation value.
BorderConstraint
BorderConstraint - A basic block has separate constraints for entry and exit.
const NodeList & List
Definition: RDFGraph.cpp:210
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Spill Code Placement Analysis
BlockFrequency BiasN
BiasN - Sum of blocks that prefer a spill.
loops
Definition: LoopInfo.cpp:769