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