Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/PlaceSafepoints.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- PlaceSafepoints.cpp - Place GC Safepoints --------------------------===//
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
// Place garbage collection safepoints at appropriate locations in the IR. This
10
// does not make relocation semantics or variable liveness explicit.  That's
11
// done by RewriteStatepointsForGC.
12
//
13
// Terminology:
14
// - A call is said to be "parseable" if there is a stack map generated for the
15
// return PC of the call.  A runtime can determine where values listed in the
16
// deopt arguments and (after RewriteStatepointsForGC) gc arguments are located
17
// on the stack when the code is suspended inside such a call.  Every parse
18
// point is represented by a call wrapped in an gc.statepoint intrinsic.
19
// - A "poll" is an explicit check in the generated code to determine if the
20
// runtime needs the generated code to cooperate by calling a helper routine
21
// and thus suspending its execution at a known state. The call to the helper
22
// routine will be parseable.  The (gc & runtime specific) logic of a poll is
23
// assumed to be provided in a function of the name "gc.safepoint_poll".
24
//
25
// We aim to insert polls such that running code can quickly be brought to a
26
// well defined state for inspection by the collector.  In the current
27
// implementation, this is done via the insertion of poll sites at method entry
28
// and the backedge of most loops.  We try to avoid inserting more polls than
29
// are necessary to ensure a finite period between poll sites.  This is not
30
// because the poll itself is expensive in the generated code; it's not.  Polls
31
// do tend to impact the optimizer itself in negative ways; we'd like to avoid
32
// perturbing the optimization of the method as much as we can.
33
//
34
// We also need to make most call sites parseable.  The callee might execute a
35
// poll (or otherwise be inspected by the GC).  If so, the entire stack
36
// (including the suspended frame of the current method) must be parseable.
37
//
38
// This pass will insert:
39
// - Call parse points ("call safepoints") for any call which may need to
40
// reach a safepoint during the execution of the callee function.
41
// - Backedge safepoint polls and entry safepoint polls to ensure that
42
// executing code reaches a safepoint poll in a finite amount of time.
43
//
44
// We do not currently support return statepoints, but adding them would not
45
// be hard.  They are not required for correctness - entry safepoints are an
46
// alternative - but some GCs may prefer them.  Patches welcome.
47
//
48
//===----------------------------------------------------------------------===//
49
50
#include "llvm/Pass.h"
51
52
#include "llvm/ADT/SetVector.h"
53
#include "llvm/ADT/Statistic.h"
54
#include "llvm/Analysis/CFG.h"
55
#include "llvm/Analysis/ScalarEvolution.h"
56
#include "llvm/Analysis/TargetLibraryInfo.h"
57
#include "llvm/Transforms/Utils/Local.h"
58
#include "llvm/IR/Dominators.h"
59
#include "llvm/IR/IntrinsicInst.h"
60
#include "llvm/IR/LegacyPassManager.h"
61
#include "llvm/IR/Statepoint.h"
62
#include "llvm/Support/CommandLine.h"
63
#include "llvm/Support/Debug.h"
64
#include "llvm/Transforms/Scalar.h"
65
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
66
#include "llvm/Transforms/Utils/Cloning.h"
67
68
#define DEBUG_TYPE "safepoint-placement"
69
70
STATISTIC(NumEntrySafepoints, "Number of entry safepoints inserted");
71
STATISTIC(NumBackedgeSafepoints, "Number of backedge safepoints inserted");
72
73
STATISTIC(CallInLoop,
74
          "Number of loops without safepoints due to calls in loop");
75
STATISTIC(FiniteExecution,
76
          "Number of loops without safepoints finite execution");
77
78
using namespace llvm;
79
80
// Ignore opportunities to avoid placing safepoints on backedges, useful for
81
// validation
82
static cl::opt<bool> AllBackedges("spp-all-backedges", cl::Hidden,
83
                                  cl::init(false));
84
85
/// How narrow does the trip count of a loop have to be to have to be considered
86
/// "counted"?  Counted loops do not get safepoints at backedges.
87
static cl::opt<int> CountedLoopTripWidth("spp-counted-loop-trip-width",
88
                                         cl::Hidden, cl::init(32));
89
90
// If true, split the backedge of a loop when placing the safepoint, otherwise
91
// split the latch block itself.  Both are useful to support for
92
// experimentation, but in practice, it looks like splitting the backedge
93
// optimizes better.
94
static cl::opt<bool> SplitBackedge("spp-split-backedge", cl::Hidden,
95
                                   cl::init(false));
96
97
namespace {
98
99
/// An analysis pass whose purpose is to identify each of the backedges in
100
/// the function which require a safepoint poll to be inserted.
101
struct PlaceBackedgeSafepointsImpl : public FunctionPass {
102
  static char ID;
103
104
  /// The output of the pass - gives a list of each backedge (described by
105
  /// pointing at the branch) which need a poll inserted.
106
  std::vector<Instruction *> PollLocations;
107
108
  /// True unless we're running spp-no-calls in which case we need to disable
109
  /// the call-dependent placement opts.
110
  bool CallSafepointsEnabled;
111
112
  ScalarEvolution *SE = nullptr;
113
  DominatorTree *DT = nullptr;
114
  LoopInfo *LI = nullptr;
115
  TargetLibraryInfo *TLI = nullptr;
116
117
  PlaceBackedgeSafepointsImpl(bool CallSafepoints = false)
118
22
      : FunctionPass(ID), CallSafepointsEnabled(CallSafepoints) {
119
22
    initializePlaceBackedgeSafepointsImplPass(*PassRegistry::getPassRegistry());
120
22
  }
121
122
  bool runOnLoop(Loop *);
123
17
  void runOnLoopAndSubLoops(Loop *L) {
124
17
    // Visit all the subloops
125
17
    for (Loop *I : *L)
126
1
      runOnLoopAndSubLoops(I);
127
17
    runOnLoop(L);
128
17
  }
129
130
22
  bool runOnFunction(Function &F) override {
131
22
    SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
132
22
    DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
133
22
    LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
134
22
    TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
135
22
    for (Loop *I : *LI) {
136
16
      runOnLoopAndSubLoops(I);
137
16
    }
138
22
    return false;
139
22
  }
140
141
22
  void getAnalysisUsage(AnalysisUsage &AU) const override {
142
22
    AU.addRequired<DominatorTreeWrapperPass>();
143
22
    AU.addRequired<ScalarEvolutionWrapperPass>();
144
22
    AU.addRequired<LoopInfoWrapperPass>();
145
22
    AU.addRequired<TargetLibraryInfoWrapperPass>();
146
22
    // We no longer modify the IR at all in this pass.  Thus all
147
22
    // analysis are preserved.
148
22
    AU.setPreservesAll();
149
22
  }
150
};
151
}
152
153
static cl::opt<bool> NoEntry("spp-no-entry", cl::Hidden, cl::init(false));
154
static cl::opt<bool> NoCall("spp-no-call", cl::Hidden, cl::init(false));
155
static cl::opt<bool> NoBackedge("spp-no-backedge", cl::Hidden, cl::init(false));
156
157
namespace {
158
struct PlaceSafepoints : public FunctionPass {
159
  static char ID; // Pass identification, replacement for typeid
160
161
10
  PlaceSafepoints() : FunctionPass(ID) {
162
10
    initializePlaceSafepointsPass(*PassRegistry::getPassRegistry());
163
10
  }
164
  bool runOnFunction(Function &F) override;
165
166
10
  void getAnalysisUsage(AnalysisUsage &AU) const override {
167
10
    // We modify the graph wholesale (inlining, block insertion, etc).  We
168
10
    // preserve nothing at the moment.  We could potentially preserve dom tree
169
10
    // if that was worth doing
170
10
    AU.addRequired<TargetLibraryInfoWrapperPass>();
171
10
  }
172
};
173
}
174
175
// Insert a safepoint poll immediately before the given instruction.  Does
176
// not handle the parsability of state at the runtime call, that's the
177
// callers job.
178
static void
179
InsertSafepointPoll(Instruction *InsertBefore,
180
                    std::vector<CallBase *> &ParsePointsNeeded /*rval*/,
181
                    const TargetLibraryInfo &TLI);
182
183
34
static bool needsStatepoint(CallBase *Call, const TargetLibraryInfo &TLI) {
184
34
  if (callsGCLeafFunction(Call, TLI))
185
2
    return false;
186
32
  if (auto *CI = dyn_cast<CallInst>(Call)) {
187
32
    if (CI->isInlineAsm())
188
0
      return false;
189
32
  }
190
32
191
32
  return !(isStatepoint(Call) || isGCRelocate(Call) || isGCResult(Call));
192
32
}
193
194
/// Returns true if this loop is known to contain a call safepoint which
195
/// must unconditionally execute on any iteration of the loop which returns
196
/// to the loop header via an edge from Pred.  Returns a conservative correct
197
/// answer; i.e. false is always valid.
198
static bool containsUnconditionalCallSafepoint(Loop *L, BasicBlock *Header,
199
                                               BasicBlock *Pred,
200
                                               DominatorTree &DT,
201
10
                                               const TargetLibraryInfo &TLI) {
202
10
  // In general, we're looking for any cut of the graph which ensures
203
10
  // there's a call safepoint along every edge between Header and Pred.
204
10
  // For the moment, we look only for the 'cuts' that consist of a single call
205
10
  // instruction in a block which is dominated by the Header and dominates the
206
10
  // loop latch (Pred) block.  Somewhat surprisingly, walking the entire chain
207
10
  // of such dominating blocks gets substantially more occurrences than just
208
10
  // checking the Pred and Header blocks themselves.  This may be due to the
209
10
  // density of loop exit conditions caused by range and null checks.
210
10
  // TODO: structure this as an analysis pass, cache the result for subloops,
211
10
  // avoid dom tree recalculations
212
10
  assert(DT.dominates(Header, Pred) && "loop latch not dominated by header?");
213
10
214
10
  BasicBlock *Current = Pred;
215
11
  while (true) {
216
24
    for (Instruction &I : *Current) {
217
24
      if (auto *Call = dyn_cast<CallBase>(&I))
218
3
        // Note: Technically, needing a safepoint isn't quite the right
219
3
        // condition here.  We should instead be checking if the target method
220
3
        // has an
221
3
        // unconditional poll. In practice, this is only a theoretical concern
222
3
        // since we don't have any methods with conditional-only safepoint
223
3
        // polls.
224
3
        if (needsStatepoint(Call, TLI))
225
1
          return true;
226
24
    }
227
11
228
11
    
if (10
Current == Header10
)
229
9
      break;
230
1
    Current = DT.getNode(Current)->getIDom()->getBlock();
231
1
  }
232
10
233
10
  
return false9
;
234
10
}
235
236
/// Returns true if this loop is known to terminate in a finite number of
237
/// iterations.  Note that this function may return false for a loop which
238
/// does actual terminate in a finite constant number of iterations due to
239
/// conservatism in the analysis.
240
static bool mustBeFiniteCountedLoop(Loop *L, ScalarEvolution *SE,
241
17
                                    BasicBlock *Pred) {
242
17
  // A conservative bound on the loop as a whole.
243
17
  const SCEV *MaxTrips = SE->getMaxBackedgeTakenCount(L);
244
17
  if (MaxTrips != SE->getCouldNotCompute() &&
245
17
      SE->getUnsignedRange(MaxTrips).getUnsignedMax().isIntN(
246
8
          CountedLoopTripWidth))
247
7
    return true;
248
10
249
10
  // If this is a conditional branch to the header with the alternate path
250
10
  // being outside the loop, we can ask questions about the execution frequency
251
10
  // of the exit block.
252
10
  if (L->isLoopExiting(Pred)) {
253
6
    // This returns an exact expression only.  TODO: We really only need an
254
6
    // upper bound here, but SE doesn't expose that.
255
6
    const SCEV *MaxExec = SE->getExitCount(L, Pred);
256
6
    if (MaxExec != SE->getCouldNotCompute() &&
257
6
        SE->getUnsignedRange(MaxExec).getUnsignedMax().isIntN(
258
1
            CountedLoopTripWidth))
259
0
        return true;
260
10
  }
261
10
262
10
  return /* not finite */ false;
263
10
}
264
265
static void scanOneBB(Instruction *Start, Instruction *End,
266
                      std::vector<CallInst *> &Calls,
267
                      DenseSet<BasicBlock *> &Seen,
268
31
                      std::vector<BasicBlock *> &Worklist) {
269
31
  for (BasicBlock::iterator BBI(Start), BBE0 = Start->getParent()->end(),
270
31
                                        BBE1 = BasicBlock::iterator(End);
271
62
       BBI != BBE0 && BBI != BBE1; 
BBI++31
) {
272
31
    if (CallInst *CI = dyn_cast<CallInst>(&*BBI))
273
31
      Calls.push_back(CI);
274
31
275
31
    // FIXME: This code does not handle invokes
276
31
    assert(!isa<InvokeInst>(&*BBI) &&
277
31
           "support for invokes in poll code needed");
278
31
279
31
    // Only add the successor blocks if we reach the terminator instruction
280
31
    // without encountering end first
281
31
    if (BBI->isTerminator()) {
282
0
      BasicBlock *BB = BBI->getParent();
283
0
      for (BasicBlock *Succ : successors(BB)) {
284
0
        if (Seen.insert(Succ).second) {
285
0
          Worklist.push_back(Succ);
286
0
        }
287
0
      }
288
0
    }
289
31
  }
290
31
}
291
292
static void scanInlinedCode(Instruction *Start, Instruction *End,
293
                            std::vector<CallInst *> &Calls,
294
31
                            DenseSet<BasicBlock *> &Seen) {
295
31
  Calls.clear();
296
31
  std::vector<BasicBlock *> Worklist;
297
31
  Seen.insert(Start->getParent());
298
31
  scanOneBB(Start, End, Calls, Seen, Worklist);
299
31
  while (!Worklist.empty()) {
300
0
    BasicBlock *BB = Worklist.back();
301
0
    Worklist.pop_back();
302
0
    scanOneBB(&*BB->begin(), End, Calls, Seen, Worklist);
303
0
  }
304
31
}
305
306
17
bool PlaceBackedgeSafepointsImpl::runOnLoop(Loop *L) {
307
17
  // Loop through all loop latches (branches controlling backedges).  We need
308
17
  // to place a safepoint on every backedge (potentially).
309
17
  // Note: In common usage, there will be only one edge due to LoopSimplify
310
17
  // having run sometime earlier in the pipeline, but this code must be correct
311
17
  // w.r.t. loops with multiple backedges.
312
17
  BasicBlock *Header = L->getHeader();
313
17
  SmallVector<BasicBlock*, 16> LoopLatches;
314
17
  L->getLoopLatches(LoopLatches);
315
17
  for (BasicBlock *Pred : LoopLatches) {
316
17
    assert(L->contains(Pred));
317
17
318
17
    // Make a policy decision about whether this loop needs a safepoint or
319
17
    // not.  Note that this is about unburdening the optimizer in loops, not
320
17
    // avoiding the runtime cost of the actual safepoint.
321
17
    if (!AllBackedges) {
322
17
      if (mustBeFiniteCountedLoop(L, SE, Pred)) {
323
7
        LLVM_DEBUG(dbgs() << "skipping safepoint placement in finite loop\n");
324
7
        FiniteExecution++;
325
7
        continue;
326
7
      }
327
10
      if (CallSafepointsEnabled &&
328
10
          containsUnconditionalCallSafepoint(L, Header, Pred, *DT, *TLI)) {
329
1
        // Note: This is only semantically legal since we won't do any further
330
1
        // IPO or inlining before the actual call insertion..  If we hadn't, we
331
1
        // might latter loose this call safepoint.
332
1
        LLVM_DEBUG(
333
1
            dbgs()
334
1
            << "skipping safepoint placement due to unconditional call\n");
335
1
        CallInLoop++;
336
1
        continue;
337
1
      }
338
9
    }
339
9
340
9
    // TODO: We can create an inner loop which runs a finite number of
341
9
    // iterations with an outer loop which contains a safepoint.  This would
342
9
    // not help runtime performance that much, but it might help our ability to
343
9
    // optimize the inner loop.
344
9
345
9
    // Safepoint insertion would involve creating a new basic block (as the
346
9
    // target of the current backedge) which does the safepoint (of all live
347
9
    // variables) and branches to the true header
348
9
    Instruction *Term = Pred->getTerminator();
349
9
350
9
    LLVM_DEBUG(dbgs() << "[LSP] terminator instruction: " << *Term);
351
9
352
9
    PollLocations.push_back(Term);
353
9
  }
354
17
355
17
  return false;
356
17
}
357
358
/// Returns true if an entry safepoint is not required before this callsite in
359
/// the caller function.
360
5
static bool doesNotRequireEntrySafepointBefore(CallBase *Call) {
361
5
  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Call)) {
362
2
    switch (II->getIntrinsicID()) {
363
2
    case Intrinsic::experimental_gc_statepoint:
364
0
    case Intrinsic::experimental_patchpoint_void:
365
0
    case Intrinsic::experimental_patchpoint_i64:
366
0
      // The can wrap an actual call which may grow the stack by an unbounded
367
0
      // amount or run forever.
368
0
      return false;
369
2
    default:
370
2
      // Most LLVM intrinsics are things which do not expand to actual calls, or
371
2
      // at least if they do, are leaf functions that cause only finite stack
372
2
      // growth.  In particular, the optimizer likes to form things like memsets
373
2
      // out of stores in the original IR.  Another important example is
374
2
      // llvm.localescape which must occur in the entry block.  Inserting a
375
2
      // safepoint before it is not legal since it could push the localescape
376
2
      // out of the entry block.
377
2
      return true;
378
3
    }
379
3
  }
380
3
  return false;
381
3
}
382
383
static Instruction *findLocationForEntrySafepoint(Function &F,
384
22
                                                  DominatorTree &DT) {
385
22
386
22
  // Conceptually, this poll needs to be on method entry, but in
387
22
  // practice, we place it as late in the entry block as possible.  We
388
22
  // can place it as late as we want as long as it dominates all calls
389
22
  // that can grow the stack.  This, combined with backedge polls,
390
22
  // give us all the progress guarantees we need.
391
22
392
22
  // hasNextInstruction and nextInstruction are used to iterate
393
22
  // through a "straight line" execution sequence.
394
22
395
26
  auto HasNextInstruction = [](Instruction *I) {
396
26
    if (!I->isTerminator())
397
6
      return true;
398
20
399
20
    BasicBlock *nextBB = I->getParent()->getUniqueSuccessor();
400
20
    return nextBB && 
(nextBB->getUniquePredecessor() != nullptr)17
;
401
20
  };
402
22
403
22
  auto NextInstruction = [&](Instruction *I) {
404
4
    assert(HasNextInstruction(I) &&
405
4
           "first check if there is a next instruction!");
406
4
407
4
    if (I->isTerminator())
408
1
      return &I->getParent()->getUniqueSuccessor()->front();
409
3
    return &*++I->getIterator();
410
3
  };
411
22
412
22
  Instruction *Cursor = nullptr;
413
26
  for (Cursor = &F.getEntryBlock().front(); HasNextInstruction(Cursor);
414
22
       
Cursor = NextInstruction(Cursor)4
) {
415
7
416
7
    // We need to ensure a safepoint poll occurs before any 'real' call.  The
417
7
    // easiest way to ensure finite execution between safepoints in the face of
418
7
    // recursive and mutually recursive functions is to enforce that each take
419
7
    // a safepoint.  Additionally, we need to ensure a poll before any call
420
7
    // which can grow the stack by an unbounded amount.  This isn't required
421
7
    // for GC semantics per se, but is a common requirement for languages
422
7
    // which detect stack overflow via guard pages and then throw exceptions.
423
7
    if (auto *Call = dyn_cast<CallBase>(Cursor)) {
424
5
      if (doesNotRequireEntrySafepointBefore(Call))
425
2
        continue;
426
3
      break;
427
3
    }
428
7
  }
429
22
430
22
  assert((HasNextInstruction(Cursor) || Cursor->isTerminator()) &&
431
22
         "either we stopped because of a call, or because of terminator");
432
22
433
22
  return Cursor;
434
22
}
435
436
static const char *const GCSafepointPollName = "gc.safepoint_poll";
437
438
33
static bool isGCSafepointPoll(Function &F) {
439
33
  return F.getName().equals(GCSafepointPollName);
440
33
}
441
442
/// Returns true if this function should be rewritten to include safepoint
443
/// polls and parseable call sites.  The main point of this function is to be
444
/// an extension point for custom logic.
445
23
static bool shouldRewriteFunction(Function &F) {
446
23
  // TODO: This should check the GCStrategy
447
23
  if (F.hasGC()) {
448
22
    const auto &FunctionGCName = F.getGC();
449
22
    const StringRef StatepointExampleName("statepoint-example");
450
22
    const StringRef CoreCLRName("coreclr");
451
22
    return (StatepointExampleName == FunctionGCName) ||
452
22
           
(CoreCLRName == FunctionGCName)1
;
453
22
  } else
454
1
    return false;
455
23
}
456
457
// TODO: These should become properties of the GCStrategy, possibly with
458
// command line overrides.
459
22
static bool enableEntrySafepoints(Function &F) { return !NoEntry; }
460
22
static bool enableBackedgeSafepoints(Function &F) { return !NoBackedge; }
461
22
static bool enableCallSafepoints(Function &F) { return !NoCall; }
462
463
33
bool PlaceSafepoints::runOnFunction(Function &F) {
464
33
  if (F.isDeclaration() || F.empty()) {
465
0
    // This is a declaration, nothing to do.  Must exit early to avoid crash in
466
0
    // dom tree calculation
467
0
    return false;
468
0
  }
469
33
470
33
  if (isGCSafepointPoll(F)) {
471
10
    // Given we're inlining this inside of safepoint poll insertion, this
472
10
    // doesn't make any sense.  Note that we do make any contained calls
473
10
    // parseable after we inline a poll.
474
10
    return false;
475
10
  }
476
23
477
23
  if (!shouldRewriteFunction(F))
478
1
    return false;
479
22
480
22
  const TargetLibraryInfo &TLI =
481
22
      getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
482
22
483
22
  bool Modified = false;
484
22
485
22
  // In various bits below, we rely on the fact that uses are reachable from
486
22
  // defs.  When there are basic blocks unreachable from the entry, dominance
487
22
  // and reachablity queries return non-sensical results.  Thus, we preprocess
488
22
  // the function to ensure these properties hold.
489
22
  Modified |= removeUnreachableBlocks(F);
490
22
491
22
  // STEP 1 - Insert the safepoint polling locations.  We do not need to
492
22
  // actually insert parse points yet.  That will be done for all polls and
493
22
  // calls in a single pass.
494
22
495
22
  DominatorTree DT;
496
22
  DT.recalculate(F);
497
22
498
22
  SmallVector<Instruction *, 16> PollsNeeded;
499
22
  std::vector<CallBase *> ParsePointNeeded;
500
22
501
22
  if (enableBackedgeSafepoints(F)) {
502
22
    // Construct a pass manager to run the LoopPass backedge logic.  We
503
22
    // need the pass manager to handle scheduling all the loop passes
504
22
    // appropriately.  Doing this by hand is painful and just not worth messing
505
22
    // with for the moment.
506
22
    legacy::FunctionPassManager FPM(F.getParent());
507
22
    bool CanAssumeCallSafepoints = enableCallSafepoints(F);
508
22
    auto *PBS = new PlaceBackedgeSafepointsImpl(CanAssumeCallSafepoints);
509
22
    FPM.add(PBS);
510
22
    FPM.run(F);
511
22
512
22
    // We preserve dominance information when inserting the poll, otherwise
513
22
    // we'd have to recalculate this on every insert
514
22
    DT.recalculate(F);
515
22
516
22
    auto &PollLocations = PBS->PollLocations;
517
22
518
22
    auto OrderByBBName = [](Instruction *a, Instruction *b) {
519
1
      return a->getParent()->getName() < b->getParent()->getName();
520
1
    };
521
22
    // We need the order of list to be stable so that naming ends up stable
522
22
    // when we split edges.  This makes test cases much easier to write.
523
22
    llvm::sort(PollLocations, OrderByBBName);
524
22
525
22
    // We can sometimes end up with duplicate poll locations.  This happens if
526
22
    // a single loop is visited more than once.   The fact this happens seems
527
22
    // wrong, but it does happen for the split-backedge.ll test case.
528
22
    PollLocations.erase(std::unique(PollLocations.begin(),
529
22
                                    PollLocations.end()),
530
22
                        PollLocations.end());
531
22
532
22
    // Insert a poll at each point the analysis pass identified
533
22
    // The poll location must be the terminator of a loop latch block.
534
22
    for (Instruction *Term : PollLocations) {
535
8
      // We are inserting a poll, the function is modified
536
8
      Modified = true;
537
8
538
8
      if (SplitBackedge) {
539
2
        // Split the backedge of the loop and insert the poll within that new
540
2
        // basic block.  This creates a loop with two latches per original
541
2
        // latch (which is non-ideal), but this appears to be easier to
542
2
        // optimize in practice than inserting the poll immediately before the
543
2
        // latch test.
544
2
545
2
        // Since this is a latch, at least one of the successors must dominate
546
2
        // it. Its possible that we have a) duplicate edges to the same header
547
2
        // and b) edges to distinct loop headers.  We need to insert pools on
548
2
        // each.
549
2
        SetVector<BasicBlock *> Headers;
550
6
        for (unsigned i = 0; i < Term->getNumSuccessors(); 
i++4
) {
551
4
          BasicBlock *Succ = Term->getSuccessor(i);
552
4
          if (DT.dominates(Succ, Term->getParent())) {
553
3
            Headers.insert(Succ);
554
3
          }
555
4
        }
556
2
        assert(!Headers.empty() && "poll location is not a loop latch?");
557
2
558
2
        // The split loop structure here is so that we only need to recalculate
559
2
        // the dominator tree once.  Alternatively, we could just keep it up to
560
2
        // date and use a more natural merged loop.
561
2
        SetVector<BasicBlock *> SplitBackedges;
562
3
        for (BasicBlock *Header : Headers) {
563
3
          BasicBlock *NewBB = SplitEdge(Term->getParent(), Header, &DT);
564
3
          PollsNeeded.push_back(NewBB->getTerminator());
565
3
          NumBackedgeSafepoints++;
566
3
        }
567
6
      } else {
568
6
        // Split the latch block itself, right before the terminator.
569
6
        PollsNeeded.push_back(Term);
570
6
        NumBackedgeSafepoints++;
571
6
      }
572
8
    }
573
22
  }
574
22
575
22
  if (enableEntrySafepoints(F)) {
576
22
    if (Instruction *Location = findLocationForEntrySafepoint(F, DT)) {
577
22
      PollsNeeded.push_back(Location);
578
22
      Modified = true;
579
22
      NumEntrySafepoints++;
580
22
    }
581
22
    // TODO: else we should assert that there was, in fact, a policy choice to
582
22
    // not insert a entry safepoint poll.
583
22
  }
584
22
585
22
  // Now that we've identified all the needed safepoint poll locations, insert
586
22
  // safepoint polls themselves.
587
31
  for (Instruction *PollLocation : PollsNeeded) {
588
31
    std::vector<CallBase *> RuntimeCalls;
589
31
    InsertSafepointPoll(PollLocation, RuntimeCalls, TLI);
590
31
    ParsePointNeeded.insert(ParsePointNeeded.end(), RuntimeCalls.begin(),
591
31
                            RuntimeCalls.end());
592
31
  }
593
22
594
22
  return Modified;
595
22
}
596
597
char PlaceBackedgeSafepointsImpl::ID = 0;
598
char PlaceSafepoints::ID = 0;
599
600
0
FunctionPass *llvm::createPlaceSafepointsPass() {
601
0
  return new PlaceSafepoints();
602
0
}
603
604
36.0k
INITIALIZE_PASS_BEGIN(PlaceBackedgeSafepointsImpl,
605
36.0k
                      "place-backedge-safepoints-impl",
606
36.0k
                      "Place Backedge Safepoints", false, false)
607
36.0k
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
608
36.0k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
609
36.0k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
610
36.0k
INITIALIZE_PASS_END(PlaceBackedgeSafepointsImpl,
611
                    "place-backedge-safepoints-impl",
612
                    "Place Backedge Safepoints", false, false)
613
614
36.0k
INITIALIZE_PASS_BEGIN(PlaceSafepoints, "place-safepoints", "Place Safepoints",
615
36.0k
                      false, false)
616
36.0k
INITIALIZE_PASS_END(PlaceSafepoints, "place-safepoints", "Place Safepoints",
617
                    false, false)
618
619
static void
620
InsertSafepointPoll(Instruction *InsertBefore,
621
                    std::vector<CallBase *> &ParsePointsNeeded /*rval*/,
622
31
                    const TargetLibraryInfo &TLI) {
623
31
  BasicBlock *OrigBB = InsertBefore->getParent();
624
31
  Module *M = InsertBefore->getModule();
625
31
  assert(M && "must be part of a module");
626
31
627
31
  // Inline the safepoint poll implementation - this will get all the branch,
628
31
  // control flow, etc..  Most importantly, it will introduce the actual slow
629
31
  // path call - where we need to insert a safepoint (parsepoint).
630
31
631
31
  auto *F = M->getFunction(GCSafepointPollName);
632
31
  assert(F && "gc.safepoint_poll function is missing");
633
31
  assert(F->getValueType() ==
634
31
         FunctionType::get(Type::getVoidTy(M->getContext()), false) &&
635
31
         "gc.safepoint_poll declared with wrong type");
636
31
  assert(!F->empty() && "gc.safepoint_poll must be a non-empty function");
637
31
  CallInst *PollCall = CallInst::Create(F, "", InsertBefore);
638
31
639
31
  // Record some information about the call site we're replacing
640
31
  BasicBlock::iterator Before(PollCall), After(PollCall);
641
31
  bool IsBegin = false;
642
31
  if (Before == OrigBB->begin())
643
24
    IsBegin = true;
644
7
  else
645
7
    Before--;
646
31
647
31
  After++;
648
31
  assert(After != OrigBB->end() && "must have successor");
649
31
650
31
  // Do the actual inlining
651
31
  InlineFunctionInfo IFI;
652
31
  bool InlineStatus = InlineFunction(PollCall, IFI);
653
31
  assert(InlineStatus && "inline must succeed");
654
31
  (void)InlineStatus; // suppress warning in release-asserts
655
31
656
31
  // Check post-conditions
657
31
  assert(IFI.StaticAllocas.empty() && "can't have allocs");
658
31
659
31
  std::vector<CallInst *> Calls; // new calls
660
31
  DenseSet<BasicBlock *> BBs;    // new BBs + insertee
661
31
662
31
  // Include only the newly inserted instructions, Note: begin may not be valid
663
31
  // if we inserted to the beginning of the basic block
664
31
  BasicBlock::iterator Start = IsBegin ? 
OrigBB->begin()24
:
std::next(Before)7
;
665
31
666
31
  // If your poll function includes an unreachable at the end, that's not
667
31
  // valid.  Bugpoint likes to create this, so check for it.
668
31
  assert(isPotentiallyReachable(&*Start, &*After) &&
669
31
         "malformed poll function");
670
31
671
31
  scanInlinedCode(&*Start, &*After, Calls, BBs);
672
31
  assert(!Calls.empty() && "slow path not found for safepoint poll");
673
31
674
31
  // Record the fact we need a parsable state at the runtime call contained in
675
31
  // the poll function.  This is required so that the runtime knows how to
676
31
  // parse the last frame when we actually take  the safepoint (i.e. execute
677
31
  // the slow path)
678
31
  assert(ParsePointsNeeded.empty());
679
31
  for (auto *CI : Calls) {
680
31
    // No safepoint needed or wanted
681
31
    if (!needsStatepoint(CI, TLI))
682
0
      continue;
683
31
684
31
    // These are likely runtime calls.  Should we assert that via calling
685
31
    // convention or something?
686
31
    ParsePointsNeeded.push_back(CI);
687
31
  }
688
31
  assert(ParsePointsNeeded.size() <= Calls.size());
689
31
}