Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/SpillPlacement.cpp
Line
Count
Source (jump to first uncovered line)
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"
34
#include "llvm/CodeGen/EdgeBundles.h"
35
#include "llvm/CodeGen/MachineBasicBlock.h"
36
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
37
#include "llvm/CodeGen/MachineFunction.h"
38
#include "llvm/CodeGen/MachineLoopInfo.h"
39
#include "llvm/CodeGen/Passes.h"
40
#include "llvm/Pass.h"
41
#include "llvm/Support/BlockFrequency.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
53
char &llvm::SpillPlacementID = SpillPlacement::ID;
54
55
42.3k
INITIALIZE_PASS_BEGIN(SpillPlacement, DEBUG_TYPE,
56
42.3k
                      "Spill Code Placement Analysis", true, true)
57
42.3k
INITIALIZE_PASS_DEPENDENCY(EdgeBundles)
58
42.3k
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
59
42.3k
INITIALIZE_PASS_END(SpillPlacement, DEBUG_TYPE,
60
                    "Spill Code Placement Analysis", true, true)
61
62
33.5k
void SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const {
63
33.5k
  AU.setPreservesAll();
64
33.5k
  AU.addRequired<MachineBlockFrequencyInfo>();
65
33.5k
  AU.addRequiredTransitive<EdgeBundles>();
66
33.5k
  AU.addRequiredTransitive<MachineLoopInfo>();
67
33.5k
  MachineFunctionPass::getAnalysisUsage(AU);
68
33.5k
}
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.
78
struct SpillPlacement::Node {
79
  /// BiasN - Sum of blocks that prefer a spill.
80
  BlockFrequency BiasN;
81
82
  /// BiasP - Sum of blocks that prefer a register.
83
  BlockFrequency BiasP;
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
90
  using LinkVector = SmallVector<std::pair<BlockFrequency, unsigned>, 4>;
91
92
  /// Links - (Weight, BundleNo) for all transparent blocks connecting to other
93
  /// bundles. The weights are all positive block frequencies.
94
  LinkVector Links;
95
96
  /// SumLinkWeights - Cached sum of the weights of all links + ThresHold.
97
  BlockFrequency SumLinkWeights;
98
99
  /// preferReg - Return true when this node prefers to be in a register.
100
360M
  bool preferReg() const {
101
360M
    // Undecided nodes (Value==0) go on the stack.
102
360M
    return Value > 0;
103
360M
  }
104
105
  /// mustSpill - Return True if this node is so biased that it must spill.
106
31.2M
  bool mustSpill() const {
107
31.2M
    // We must spill if Bias < -sum(weights) or the MustSpill flag was set.
108
31.2M
    // BiasN is saturated when MustSpill is set, make sure this still returns
109
31.2M
    // true when the RHS saturates. Note that SumLinkWeights includes Threshold.
110
31.2M
    return BiasN >= BiasP + SumLinkWeights;
111
31.2M
  }
112
113
  /// clear - Reset per-query data, but preserve frequencies that only depend on
114
  /// the CFG.
115
70.6M
  void clear(const BlockFrequency &Threshold) {
116
70.6M
    BiasN = BiasP = Value = 0;
117
70.6M
    SumLinkWeights = Threshold;
118
70.6M
    Links.clear();
119
70.6M
  }
120
121
  /// addLink - Add a link to bundle b with weight w.
122
111M
  void addLink(unsigned b, BlockFrequency w) {
123
111M
    // Update cached sum.
124
111M
    SumLinkWeights += w;
125
111M
126
111M
    // There can be multiple links to the same bundle, add them up.
127
300M
    for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; 
++I189M
)
128
208M
      if (I->second == b) {
129
19.5M
        I->first += w;
130
19.5M
        return;
131
19.5M
      }
132
111M
    // This must be the first link to b.
133
111M
    Links.push_back(std::make_pair(w, b));
134
91.5M
  }
135
136
  /// addBias - Bias this node.
137
87.8M
  void addBias(BlockFrequency freq, BorderConstraint direction) {
138
87.8M
    switch (direction) {
139
87.8M
    default:
140
0
      break;
141
87.8M
    case PrefReg:
142
23.6M
      BiasP += freq;
143
23.6M
      break;
144
87.8M
    case PrefSpill:
145
46.3M
      BiasN += freq;
146
46.3M
      break;
147
87.8M
    case MustSpill:
148
17.9M
      BiasN = BlockFrequency::getMaxFrequency();
149
17.9M
      break;
150
87.8M
    }
151
87.8M
  }
152
153
  /// update - Recompute Value from Bias and Links. Return true when node
154
  /// preference changes.
155
125M
  bool update(const Node nodes[], const BlockFrequency &Threshold) {
156
125M
    // Compute the weighted sum of inputs.
157
125M
    BlockFrequency SumN = BiasN;
158
125M
    BlockFrequency SumP = BiasP;
159
278M
    for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; 
++I153M
) {
160
153M
      if (nodes[I->second].Value == -1)
161
17.1M
        SumN += I->first;
162
136M
      else if (nodes[I->second].Value == 1)
163
117M
        SumP += I->first;
164
153M
    }
165
125M
166
125M
    // Each weighted sum is going to be less than the total frequency of the
167
125M
    // bundle. Ideally, we should simply set Value = sign(SumP - SumN), but we
168
125M
    // will add a dead zone around 0 for two reasons:
169
125M
    //
170
125M
    //  1. It avoids arbitrary bias when all links are 0 as is possible during
171
125M
    //     initial iterations.
172
125M
    //  2. It helps tame rounding errors when the links nominally sum to 0.
173
125M
    //
174
125M
    bool Before = preferReg();
175
125M
    if (SumN >= SumP + Threshold)
176
40.7M
      Value = -1;
177
84.5M
    else if (SumP >= SumN + Threshold)
178
73.4M
      Value = 1;
179
11.1M
    else
180
11.1M
      Value = 0;
181
125M
    return Before != preferReg();
182
125M
  }
183
184
  void getDissentingNeighbors(SparseSet<unsigned> &List,
185
52.1M
                              const Node nodes[]) const {
186
52.1M
    for (const auto &Elt : Links) {
187
45.0M
      unsigned n = Elt.second;
188
45.0M
      // Neighbors that already have the same value are not going to
189
45.0M
      // change because of this node changing.
190
45.0M
      if (Value != nodes[n].Value)
191
10.3M
        List.insert(n);
192
45.0M
    }
193
52.1M
  }
194
};
195
196
484k
bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) {
197
484k
  MF = &mf;
198
484k
  bundles = &getAnalysis<EdgeBundles>();
199
484k
  loops = &getAnalysis<MachineLoopInfo>();
200
484k
201
484k
  assert(!nodes && "Leaking node array");
202
484k
  nodes = new Node[bundles->getNumBundles()];
203
484k
  TodoList.clear();
204
484k
  TodoList.setUniverse(bundles->getNumBundles());
205
484k
206
484k
  // Compute total ingoing and outgoing block frequencies for all bundles.
207
484k
  BlockFrequencies.resize(mf.getNumBlockIDs());
208
484k
  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
209
484k
  setThreshold(MBFI->getEntryFreq());
210
2.82M
  for (auto &I : mf) {
211
2.82M
    unsigned Num = I.getNumber();
212
2.82M
    BlockFrequencies[Num] = MBFI->getBlockFreq(&I);
213
2.82M
  }
214
484k
215
484k
  // We never change the function.
216
484k
  return false;
217
484k
}
218
219
517k
void SpillPlacement::releaseMemory() {
220
517k
  delete[] nodes;
221
517k
  nodes = nullptr;
222
517k
  TodoList.clear();
223
517k
}
224
225
/// activate - mark node n as active if it wasn't already.
226
198M
void SpillPlacement::activate(unsigned n) {
227
198M
  TodoList.insert(n);
228
198M
  if (ActiveNodes->test(n))
229
128M
    return;
230
70.6M
  ActiveNodes->set(n);
231
70.6M
  nodes[n].clear(Threshold);
232
70.6M
233
70.6M
  // Very large bundles usually come from big switches, indirect branches,
234
70.6M
  // landing pads, or loops with many 'continue' statements. It is difficult to
235
70.6M
  // allocate registers when so many different blocks are involved.
236
70.6M
  //
237
70.6M
  // Give a small negative bias to large bundles such that a substantial
238
70.6M
  // fraction of the connected blocks need to be interested before we consider
239
70.6M
  // expanding the region through the bundle. This helps compile time by
240
70.6M
  // limiting the number of blocks visited and the number of links in the
241
70.6M
  // Hopfield network.
242
70.6M
  if (bundles->getBlocks(n).size() > 100) {
243
24.1k
    nodes[n].BiasP = 0;
244
24.1k
    nodes[n].BiasN = (MBFI->getEntryFreq() / 16);
245
24.1k
  }
246
70.6M
}
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
484k
void SpillPlacement::setThreshold(const BlockFrequency &Entry) {
254
484k
  // Apparently 2 is a good threshold when Entry==2^14, but we need to scale
255
484k
  // it.  Divide by 2^13, rounding as appropriate.
256
484k
  uint64_t Freq = Entry.getFrequency();
257
484k
  uint64_t Scaled = (Freq >> 13) + bool(Freq & (1 << 12));
258
484k
  Threshold = std::max(UINT64_C(1), Scaled);
259
484k
}
260
261
/// addConstraints - Compute node biases and weights from a set of constraints.
262
/// Set a bit in NodeMask for each active node.
263
20.9M
void SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) {
264
20.9M
  for (ArrayRef<BlockConstraint>::iterator I = LiveBlocks.begin(),
265
70.2M
       E = LiveBlocks.end(); I != E; 
++I49.3M
) {
266
49.3M
    BlockFrequency Freq = BlockFrequencies[I->Number];
267
49.3M
268
49.3M
    // Live-in to block?
269
49.3M
    if (I->Entry != DontCare) {
270
39.6M
      unsigned ib = bundles->getBundle(I->Number, false);
271
39.6M
      activate(ib);
272
39.6M
      nodes[ib].addBias(Freq, I->Entry);
273
39.6M
    }
274
49.3M
275
49.3M
    // Live-out from block?
276
49.3M
    if (I->Exit != DontCare) {
277
44.0M
      unsigned ob = bundles->getBundle(I->Number, true);
278
44.0M
      activate(ob);
279
44.0M
      nodes[ob].addBias(Freq, I->Exit);
280
44.0M
    }
281
49.3M
  }
282
20.9M
}
283
284
/// addPrefSpill - Same as addConstraints(PrefSpill)
285
219k
void SpillPlacement::addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong) {
286
219k
  for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
287
2.30M
       I != E; 
++I2.08M
) {
288
2.08M
    BlockFrequency Freq = BlockFrequencies[*I];
289
2.08M
    if (Strong)
290
2.08M
      Freq += Freq;
291
2.08M
    unsigned ib = bundles->getBundle(*I, false);
292
2.08M
    unsigned ob = bundles->getBundle(*I, true);
293
2.08M
    activate(ib);
294
2.08M
    activate(ob);
295
2.08M
    nodes[ib].addBias(Freq, PrefSpill);
296
2.08M
    nodes[ob].addBias(Freq, PrefSpill);
297
2.08M
  }
298
219k
}
299
300
16.9M
void SpillPlacement::addLinks(ArrayRef<unsigned> Links) {
301
84.5M
  for (ArrayRef<unsigned>::iterator I = Links.begin(), E = Links.end(); I != E;
302
67.5M
       ++I) {
303
67.5M
    unsigned Number = *I;
304
67.5M
    unsigned ib = bundles->getBundle(Number, false);
305
67.5M
    unsigned ob = bundles->getBundle(Number, true);
306
67.5M
307
67.5M
    // Ignore self-loops.
308
67.5M
    if (ib == ob)
309
12.0M
      continue;
310
55.5M
    activate(ib);
311
55.5M
    activate(ob);
312
55.5M
    BlockFrequency Freq = BlockFrequencies[Number];
313
55.5M
    nodes[ib].addLink(ob, Freq);
314
55.5M
    nodes[ob].addLink(ib, Freq);
315
55.5M
  }
316
16.9M
}
317
318
7.95M
bool SpillPlacement::scanActiveBundles() {
319
7.95M
  RecentPositive.clear();
320
31.2M
  for (unsigned n : ActiveNodes->set_bits()) {
321
31.2M
    update(n);
322
31.2M
    // A node that must spill, or a node without any links is not going to
323
31.2M
    // change its value ever again, so exclude it from iterations.
324
31.2M
    if (nodes[n].mustSpill())
325
13.8M
      continue;
326
17.3M
    if (nodes[n].preferReg())
327
14.8M
      RecentPositive.push_back(n);
328
17.3M
  }
329
7.95M
  return !RecentPositive.empty();
330
7.95M
}
331
332
125M
bool SpillPlacement::update(unsigned n) {
333
125M
  if (!nodes[n].update(nodes, Threshold))
334
73.1M
    return false;
335
52.1M
  nodes[n].getDissentingNeighbors(TodoList, nodes);
336
52.1M
  return true;
337
52.1M
}
338
339
/// iterate - Repeatedly update the Hopfield nodes until stability or the
340
/// maximum number of iterations is reached.
341
12.6M
void SpillPlacement::iterate() {
342
12.6M
  // We do not need to push those node in the todolist.
343
12.6M
  // They are already been proceeded as part of the previous iteration.
344
12.6M
  RecentPositive.clear();
345
12.6M
346
12.6M
  // Since the last iteration, the todolist have been augmented by calls
347
12.6M
  // to addConstraints, addLinks, and co.
348
12.6M
  // Update the network energy starting at this new frontier.
349
12.6M
  // The call to ::update will add the nodes that changed into the todolist.
350
12.6M
  unsigned Limit = bundles->getNumBundles() * 10;
351
106M
  while(Limit-- > 0 && !TodoList.empty()) {
352
94.0M
    unsigned n = TodoList.pop_back_val();
353
94.0M
    if (!update(n))
354
56.8M
      continue;
355
37.2M
    if (nodes[n].preferReg())
356
27.1M
      RecentPositive.push_back(n);
357
37.2M
  }
358
12.6M
}
359
360
7.95M
void SpillPlacement::prepare(BitVector &RegBundles) {
361
7.95M
  RecentPositive.clear();
362
7.95M
  TodoList.clear();
363
7.95M
  // Reuse RegBundles as our ActiveNodes vector.
364
7.95M
  ActiveNodes = &RegBundles;
365
7.95M
  ActiveNodes->clear();
366
7.95M
  ActiveNodes->resize(bundles->getNumBundles());
367
7.95M
}
368
369
bool
370
4.17M
SpillPlacement::finish() {
371
4.17M
  assert(ActiveNodes && "Call prepare() first");
372
4.17M
373
4.17M
  // Write preferences back to ActiveNodes.
374
4.17M
  bool Perfect = true;
375
4.17M
  for (unsigned n : ActiveNodes->set_bits())
376
54.8M
    if (!nodes[n].preferReg()) {
377
27.8M
      ActiveNodes->reset(n);
378
27.8M
      Perfect = false;
379
27.8M
    }
380
4.17M
  ActiveNodes = nullptr;
381
4.17M
  return Perfect;
382
4.17M
}