LLVM  9.0.0svn
SpillPlacement.cpp
Go to the documentation of this file.
1 //===- SpillPlacement.cpp - Optimal Spill Code Placement ------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the spill code placement analysis.
10 //
11 // Each edge bundle corresponds to a node in a Hopfield network. Constraints on
12 // basic blocks are weighted by the block frequency and added to become the node
13 // bias.
14 //
15 // Transparent basic blocks have the variable live through, but don't care if it
16 // is spilled or in a register. These blocks become connections in the Hopfield
17 // network, again weighted by block frequency.
18 //
19 // The Hopfield network minimizes (possibly locally) its energy function:
20 //
21 // E = -sum_n V_n * ( B_n + sum_{n, m linked by b} V_m * F_b )
22 //
23 // The energy function represents the expected spill code execution frequency,
24 // or the cost of spilling. This is a Lyapunov function which never increases
25 // when a node is updated. It is guaranteed to converge to a local minimum.
26 //
27 //===----------------------------------------------------------------------===//
28 
29 #include "SpillPlacement.h"
30 #include "llvm/ADT/ArrayRef.h"
31 #include "llvm/ADT/BitVector.h"
32 #include "llvm/ADT/SmallVector.h"
33 #include "llvm/ADT/SparseSet.h"
39 #include "llvm/CodeGen/Passes.h"
40 #include "llvm/Pass.h"
42 #include <algorithm>
43 #include <cassert>
44 #include <cstdint>
45 #include <utility>
46 
47 using namespace llvm;
48 
49 #define DEBUG_TYPE "spill-code-placement"
50 
51 char SpillPlacement::ID = 0;
52 
54 
56  "Spill Code Placement Analysis", true, true)
60  "Spill Code Placement Analysis", true, true)
61 
62 void SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const {
63  AU.setPreservesAll();
64  AU.addRequired<MachineBlockFrequencyInfo>();
65  AU.addRequiredTransitive<EdgeBundles>();
66  AU.addRequiredTransitive<MachineLoopInfo>();
68 }
69 
70 /// Node - Each edge bundle corresponds to a Hopfield node.
71 ///
72 /// The node contains precomputed frequency data that only depends on the CFG,
73 /// but Bias and Links are computed each time placeSpills is called.
74 ///
75 /// The node Value is positive when the variable should be in a register. The
76 /// value can change when linked nodes change, but convergence is very fast
77 /// because all weights are positive.
79  /// BiasN - Sum of blocks that prefer a spill.
81 
82  /// BiasP - Sum of blocks that prefer a register.
84 
85  /// Value - Output value of this node computed from the Bias and links.
86  /// This is always on of the values {-1, 0, 1}. A positive number means the
87  /// variable should go in a register through this bundle.
88  int Value;
89 
91 
92  /// Links - (Weight, BundleNo) for all transparent blocks connecting to other
93  /// bundles. The weights are all positive block frequencies.
95 
96  /// SumLinkWeights - Cached sum of the weights of all links + ThresHold.
98 
99  /// preferReg - Return true when this node prefers to be in a register.
100  bool preferReg() const {
101  // Undecided nodes (Value==0) go on the stack.
102  return Value > 0;
103  }
104 
105  /// mustSpill - Return True if this node is so biased that it must spill.
106  bool mustSpill() const {
107  // We must spill if Bias < -sum(weights) or the MustSpill flag was set.
108  // BiasN is saturated when MustSpill is set, make sure this still returns
109  // true when the RHS saturates. Note that SumLinkWeights includes Threshold.
110  return BiasN >= BiasP + SumLinkWeights;
111  }
112 
113  /// clear - Reset per-query data, but preserve frequencies that only depend on
114  /// the CFG.
115  void clear(const BlockFrequency &Threshold) {
116  BiasN = BiasP = Value = 0;
117  SumLinkWeights = Threshold;
118  Links.clear();
119  }
120 
121  /// addLink - Add a link to bundle b with weight w.
122  void addLink(unsigned b, BlockFrequency w) {
123  // Update cached sum.
124  SumLinkWeights += w;
125 
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) {
129  I->first += w;
130  return;
131  }
132  // This must be the first link to b.
133  Links.push_back(std::make_pair(w, b));
134  }
135 
136  /// addBias - Bias this node.
138  switch (direction) {
139  default:
140  break;
141  case PrefReg:
142  BiasP += freq;
143  break;
144  case PrefSpill:
145  BiasN += freq;
146  break;
147  case MustSpill:
149  break;
150  }
151  }
152 
153  /// update - Recompute Value from Bias and Links. Return true when node
154  /// preference changes.
155  bool update(const Node nodes[], const BlockFrequency &Threshold) {
156  // Compute the weighted sum of inputs.
157  BlockFrequency SumN = BiasN;
158  BlockFrequency SumP = BiasP;
159  for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) {
160  if (nodes[I->second].Value == -1)
161  SumN += I->first;
162  else if (nodes[I->second].Value == 1)
163  SumP += I->first;
164  }
165 
166  // Each weighted sum is going to be less than the total frequency of the
167  // bundle. Ideally, we should simply set Value = sign(SumP - SumN), but we
168  // will add a dead zone around 0 for two reasons:
169  //
170  // 1. It avoids arbitrary bias when all links are 0 as is possible during
171  // initial iterations.
172  // 2. It helps tame rounding errors when the links nominally sum to 0.
173  //
174  bool Before = preferReg();
175  if (SumN >= SumP + Threshold)
176  Value = -1;
177  else if (SumP >= SumN + Threshold)
178  Value = 1;
179  else
180  Value = 0;
181  return Before != preferReg();
182  }
183 
185  const Node nodes[]) const {
186  for (const auto &Elt : Links) {
187  unsigned n = Elt.second;
188  // Neighbors that already have the same value are not going to
189  // change because of this node changing.
190  if (Value != nodes[n].Value)
191  List.insert(n);
192  }
193  }
194 };
195 
196 bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) {
197  MF = &mf;
198  bundles = &getAnalysis<EdgeBundles>();
199  loops = &getAnalysis<MachineLoopInfo>();
200 
201  assert(!nodes && "Leaking node array");
202  nodes = new Node[bundles->getNumBundles()];
203  TodoList.clear();
204  TodoList.setUniverse(bundles->getNumBundles());
205 
206  // Compute total ingoing and outgoing block frequencies for all bundles.
207  BlockFrequencies.resize(mf.getNumBlockIDs());
208  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
209  setThreshold(MBFI->getEntryFreq());
210  for (auto &I : mf) {
211  unsigned Num = I.getNumber();
212  BlockFrequencies[Num] = MBFI->getBlockFreq(&I);
213  }
214 
215  // We never change the function.
216  return false;
217 }
218 
219 void SpillPlacement::releaseMemory() {
220  delete[] nodes;
221  nodes = nullptr;
222  TodoList.clear();
223 }
224 
225 /// activate - mark node n as active if it wasn't already.
226 void SpillPlacement::activate(unsigned n) {
227  TodoList.insert(n);
228  if (ActiveNodes->test(n))
229  return;
230  ActiveNodes->set(n);
231  nodes[n].clear(Threshold);
232 
233  // Very large bundles usually come from big switches, indirect branches,
234  // landing pads, or loops with many 'continue' statements. It is difficult to
235  // allocate registers when so many different blocks are involved.
236  //
237  // Give a small negative bias to large bundles such that a substantial
238  // fraction of the connected blocks need to be interested before we consider
239  // expanding the region through the bundle. This helps compile time by
240  // limiting the number of blocks visited and the number of links in the
241  // Hopfield network.
242  if (bundles->getBlocks(n).size() > 100) {
243  nodes[n].BiasP = 0;
244  nodes[n].BiasN = (MBFI->getEntryFreq() / 16);
245  }
246 }
247 
248 /// Set the threshold for a given entry frequency.
249 ///
250 /// Set the threshold relative to \c Entry. Since the threshold is used as a
251 /// bound on the open interval (-Threshold;Threshold), 1 is the minimum
252 /// threshold.
253 void SpillPlacement::setThreshold(const BlockFrequency &Entry) {
254  // Apparently 2 is a good threshold when Entry==2^14, but we need to scale
255  // it. Divide by 2^13, rounding as appropriate.
256  uint64_t Freq = Entry.getFrequency();
257  uint64_t Scaled = (Freq >> 13) + bool(Freq & (1 << 12));
258  Threshold = std::max(UINT64_C(1), Scaled);
259 }
260 
261 /// addConstraints - Compute node biases and weights from a set of constraints.
262 /// Set a bit in NodeMask for each active node.
264  for (ArrayRef<BlockConstraint>::iterator I = LiveBlocks.begin(),
265  E = LiveBlocks.end(); I != E; ++I) {
266  BlockFrequency Freq = BlockFrequencies[I->Number];
267 
268  // Live-in to block?
269  if (I->Entry != DontCare) {
270  unsigned ib = bundles->getBundle(I->Number, false);
271  activate(ib);
272  nodes[ib].addBias(Freq, I->Entry);
273  }
274 
275  // Live-out from block?
276  if (I->Exit != DontCare) {
277  unsigned ob = bundles->getBundle(I->Number, true);
278  activate(ob);
279  nodes[ob].addBias(Freq, I->Exit);
280  }
281  }
282 }
283 
284 /// addPrefSpill - Same as addConstraints(PrefSpill)
286  for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
287  I != E; ++I) {
288  BlockFrequency Freq = BlockFrequencies[*I];
289  if (Strong)
290  Freq += Freq;
291  unsigned ib = bundles->getBundle(*I, false);
292  unsigned ob = bundles->getBundle(*I, true);
293  activate(ib);
294  activate(ob);
295  nodes[ib].addBias(Freq, PrefSpill);
296  nodes[ob].addBias(Freq, PrefSpill);
297  }
298 }
299 
301  for (ArrayRef<unsigned>::iterator I = Links.begin(), E = Links.end(); I != E;
302  ++I) {
303  unsigned Number = *I;
304  unsigned ib = bundles->getBundle(Number, false);
305  unsigned ob = bundles->getBundle(Number, true);
306 
307  // Ignore self-loops.
308  if (ib == ob)
309  continue;
310  activate(ib);
311  activate(ob);
312  BlockFrequency Freq = BlockFrequencies[Number];
313  nodes[ib].addLink(ob, Freq);
314  nodes[ob].addLink(ib, Freq);
315  }
316 }
317 
319  RecentPositive.clear();
320  for (unsigned n : ActiveNodes->set_bits()) {
321  update(n);
322  // A node that must spill, or a node without any links is not going to
323  // change its value ever again, so exclude it from iterations.
324  if (nodes[n].mustSpill())
325  continue;
326  if (nodes[n].preferReg())
327  RecentPositive.push_back(n);
328  }
329  return !RecentPositive.empty();
330 }
331 
332 bool SpillPlacement::update(unsigned n) {
333  if (!nodes[n].update(nodes, Threshold))
334  return false;
335  nodes[n].getDissentingNeighbors(TodoList, nodes);
336  return true;
337 }
338 
339 /// iterate - Repeatedly update the Hopfield nodes until stability or the
340 /// maximum number of iterations is reached.
342  // We do not need to push those node in the todolist.
343  // They are already been proceeded as part of the previous iteration.
344  RecentPositive.clear();
345 
346  // Since the last iteration, the todolist have been augmented by calls
347  // to addConstraints, addLinks, and co.
348  // Update the network energy starting at this new frontier.
349  // The call to ::update will add the nodes that changed into the todolist.
350  unsigned Limit = bundles->getNumBundles() * 10;
351  while(Limit-- > 0 && !TodoList.empty()) {
352  unsigned n = TodoList.pop_back_val();
353  if (!update(n))
354  continue;
355  if (nodes[n].preferReg())
356  RecentPositive.push_back(n);
357  }
358 }
359 
361  RecentPositive.clear();
362  TodoList.clear();
363  // Reuse RegBundles as our ActiveNodes vector.
364  ActiveNodes = &RegBundles;
365  ActiveNodes->clear();
366  ActiveNodes->resize(bundles->getNumBundles());
367 }
368 
369 bool
371  assert(ActiveNodes && "Call prepare() first");
372 
373  // Write preferences back to ActiveNodes.
374  bool Perfect = true;
375  for (unsigned n : ActiveNodes->set_bits())
376  if (!nodes[n].preferReg()) {
377  ActiveNodes->reset(n);
378  Perfect = false;
379  }
380  ActiveNodes = nullptr;
381  return Perfect;
382 }
int Value
Value - Output value of this node computed from the Bias and links.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
iterator begin() const
Definition: ArrayRef.h:136
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.
void push_back(const T &Elt)
Definition: SmallVector.h:211
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:50
void clear()
clear - Removes all bits from the bitvector. Does not change capacity.
Definition: BitVector.h:366
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:32
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")
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:137
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.
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:201
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
BlockFrequency BiasN
BiasN - Sum of blocks that prefer a spill.
loops
Definition: LoopInfo.cpp:802