LLVM  9.0.0svn
PlaceSafepoints.cpp
Go to the documentation of this file.
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"
58 #include "llvm/IR/Dominators.h"
59 #include "llvm/IR/IntrinsicInst.h"
61 #include "llvm/IR/Statepoint.h"
63 #include "llvm/Support/Debug.h"
64 #include "llvm/Transforms/Scalar.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  : FunctionPass(ID), CallSafepointsEnabled(CallSafepoints) {
120  }
121 
122  bool runOnLoop(Loop *);
123  void runOnLoopAndSubLoops(Loop *L) {
124  // Visit all the subloops
125  for (Loop *I : *L)
126  runOnLoopAndSubLoops(I);
127  runOnLoop(L);
128  }
129 
130  bool runOnFunction(Function &F) override {
131  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
132  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
133  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
134  TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
135  for (Loop *I : *LI) {
136  runOnLoopAndSubLoops(I);
137  }
138  return false;
139  }
140 
141  void getAnalysisUsage(AnalysisUsage &AU) const override {
146  // We no longer modify the IR at all in this pass. Thus all
147  // analysis are preserved.
148  AU.setPreservesAll();
149  }
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  PlaceSafepoints() : FunctionPass(ID) {
163  }
164  bool runOnFunction(Function &F) override;
165 
166  void getAnalysisUsage(AnalysisUsage &AU) const override {
167  // We modify the graph wholesale (inlining, block insertion, etc). We
168  // preserve nothing at the moment. We could potentially preserve dom tree
169  // if that was worth doing
171  }
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 static bool needsStatepoint(CallBase *Call, const TargetLibraryInfo &TLI) {
184  if (callsGCLeafFunction(Call, TLI))
185  return false;
186  if (auto *CI = dyn_cast<CallInst>(Call)) {
187  if (CI->isInlineAsm())
188  return false;
189  }
190 
191  return !(isStatepoint(Call) || isGCRelocate(Call) || isGCResult(Call));
192 }
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.
199  BasicBlock *Pred,
200  DominatorTree &DT,
201  const TargetLibraryInfo &TLI) {
202  // In general, we're looking for any cut of the graph which ensures
203  // there's a call safepoint along every edge between Header and Pred.
204  // For the moment, we look only for the 'cuts' that consist of a single call
205  // instruction in a block which is dominated by the Header and dominates the
206  // loop latch (Pred) block. Somewhat surprisingly, walking the entire chain
207  // of such dominating blocks gets substantially more occurrences than just
208  // checking the Pred and Header blocks themselves. This may be due to the
209  // density of loop exit conditions caused by range and null checks.
210  // TODO: structure this as an analysis pass, cache the result for subloops,
211  // avoid dom tree recalculations
212  assert(DT.dominates(Header, Pred) && "loop latch not dominated by header?");
213 
214  BasicBlock *Current = Pred;
215  while (true) {
216  for (Instruction &I : *Current) {
217  if (auto *Call = dyn_cast<CallBase>(&I))
218  // Note: Technically, needing a safepoint isn't quite the right
219  // condition here. We should instead be checking if the target method
220  // has an
221  // unconditional poll. In practice, this is only a theoretical concern
222  // since we don't have any methods with conditional-only safepoint
223  // polls.
224  if (needsStatepoint(Call, TLI))
225  return true;
226  }
227 
228  if (Current == Header)
229  break;
230  Current = DT.getNode(Current)->getIDom()->getBlock();
231  }
232 
233  return false;
234 }
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.
241  BasicBlock *Pred) {
242  // A conservative bound on the loop as a whole.
243  const SCEV *MaxTrips = SE->getMaxBackedgeTakenCount(L);
244  if (MaxTrips != SE->getCouldNotCompute() &&
245  SE->getUnsignedRange(MaxTrips).getUnsignedMax().isIntN(
247  return true;
248 
249  // If this is a conditional branch to the header with the alternate path
250  // being outside the loop, we can ask questions about the execution frequency
251  // of the exit block.
252  if (L->isLoopExiting(Pred)) {
253  // This returns an exact expression only. TODO: We really only need an
254  // upper bound here, but SE doesn't expose that.
255  const SCEV *MaxExec = SE->getExitCount(L, Pred);
256  if (MaxExec != SE->getCouldNotCompute() &&
257  SE->getUnsignedRange(MaxExec).getUnsignedMax().isIntN(
259  return true;
260  }
261 
262  return /* not finite */ false;
263 }
264 
265 static void scanOneBB(Instruction *Start, Instruction *End,
266  std::vector<CallInst *> &Calls,
268  std::vector<BasicBlock *> &Worklist) {
269  for (BasicBlock::iterator BBI(Start), BBE0 = Start->getParent()->end(),
270  BBE1 = BasicBlock::iterator(End);
271  BBI != BBE0 && BBI != BBE1; BBI++) {
272  if (CallInst *CI = dyn_cast<CallInst>(&*BBI))
273  Calls.push_back(CI);
274 
275  // FIXME: This code does not handle invokes
276  assert(!isa<InvokeInst>(&*BBI) &&
277  "support for invokes in poll code needed");
278 
279  // Only add the successor blocks if we reach the terminator instruction
280  // without encountering end first
281  if (BBI->isTerminator()) {
282  BasicBlock *BB = BBI->getParent();
283  for (BasicBlock *Succ : successors(BB)) {
284  if (Seen.insert(Succ).second) {
285  Worklist.push_back(Succ);
286  }
287  }
288  }
289  }
290 }
291 
292 static void scanInlinedCode(Instruction *Start, Instruction *End,
293  std::vector<CallInst *> &Calls,
294  DenseSet<BasicBlock *> &Seen) {
295  Calls.clear();
296  std::vector<BasicBlock *> Worklist;
297  Seen.insert(Start->getParent());
298  scanOneBB(Start, End, Calls, Seen, Worklist);
299  while (!Worklist.empty()) {
300  BasicBlock *BB = Worklist.back();
301  Worklist.pop_back();
302  scanOneBB(&*BB->begin(), End, Calls, Seen, Worklist);
303  }
304 }
305 
306 bool PlaceBackedgeSafepointsImpl::runOnLoop(Loop *L) {
307  // Loop through all loop latches (branches controlling backedges). We need
308  // to place a safepoint on every backedge (potentially).
309  // Note: In common usage, there will be only one edge due to LoopSimplify
310  // having run sometime earlier in the pipeline, but this code must be correct
311  // w.r.t. loops with multiple backedges.
312  BasicBlock *Header = L->getHeader();
313  SmallVector<BasicBlock*, 16> LoopLatches;
314  L->getLoopLatches(LoopLatches);
315  for (BasicBlock *Pred : LoopLatches) {
316  assert(L->contains(Pred));
317 
318  // Make a policy decision about whether this loop needs a safepoint or
319  // not. Note that this is about unburdening the optimizer in loops, not
320  // avoiding the runtime cost of the actual safepoint.
321  if (!AllBackedges) {
322  if (mustBeFiniteCountedLoop(L, SE, Pred)) {
323  LLVM_DEBUG(dbgs() << "skipping safepoint placement in finite loop\n");
324  FiniteExecution++;
325  continue;
326  }
327  if (CallSafepointsEnabled &&
328  containsUnconditionalCallSafepoint(L, Header, Pred, *DT, *TLI)) {
329  // Note: This is only semantically legal since we won't do any further
330  // IPO or inlining before the actual call insertion.. If we hadn't, we
331  // might latter loose this call safepoint.
332  LLVM_DEBUG(
333  dbgs()
334  << "skipping safepoint placement due to unconditional call\n");
335  CallInLoop++;
336  continue;
337  }
338  }
339 
340  // TODO: We can create an inner loop which runs a finite number of
341  // iterations with an outer loop which contains a safepoint. This would
342  // not help runtime performance that much, but it might help our ability to
343  // optimize the inner loop.
344 
345  // Safepoint insertion would involve creating a new basic block (as the
346  // target of the current backedge) which does the safepoint (of all live
347  // variables) and branches to the true header
348  Instruction *Term = Pred->getTerminator();
349 
350  LLVM_DEBUG(dbgs() << "[LSP] terminator instruction: " << *Term);
351 
352  PollLocations.push_back(Term);
353  }
354 
355  return false;
356 }
357 
358 /// Returns true if an entry safepoint is not required before this callsite in
359 /// the caller function.
361  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Call)) {
362  switch (II->getIntrinsicID()) {
363  case Intrinsic::experimental_gc_statepoint:
364  case Intrinsic::experimental_patchpoint_void:
365  case Intrinsic::experimental_patchpoint_i64:
366  // The can wrap an actual call which may grow the stack by an unbounded
367  // amount or run forever.
368  return false;
369  default:
370  // Most LLVM intrinsics are things which do not expand to actual calls, or
371  // at least if they do, are leaf functions that cause only finite stack
372  // growth. In particular, the optimizer likes to form things like memsets
373  // out of stores in the original IR. Another important example is
374  // llvm.localescape which must occur in the entry block. Inserting a
375  // safepoint before it is not legal since it could push the localescape
376  // out of the entry block.
377  return true;
378  }
379  }
380  return false;
381 }
382 
384  DominatorTree &DT) {
385 
386  // Conceptually, this poll needs to be on method entry, but in
387  // practice, we place it as late in the entry block as possible. We
388  // can place it as late as we want as long as it dominates all calls
389  // that can grow the stack. This, combined with backedge polls,
390  // give us all the progress guarantees we need.
391 
392  // hasNextInstruction and nextInstruction are used to iterate
393  // through a "straight line" execution sequence.
394 
395  auto HasNextInstruction = [](Instruction *I) {
396  if (!I->isTerminator())
397  return true;
398 
399  BasicBlock *nextBB = I->getParent()->getUniqueSuccessor();
400  return nextBB && (nextBB->getUniquePredecessor() != nullptr);
401  };
402 
403  auto NextInstruction = [&](Instruction *I) {
404  assert(HasNextInstruction(I) &&
405  "first check if there is a next instruction!");
406 
407  if (I->isTerminator())
408  return &I->getParent()->getUniqueSuccessor()->front();
409  return &*++I->getIterator();
410  };
411 
412  Instruction *Cursor = nullptr;
413  for (Cursor = &F.getEntryBlock().front(); HasNextInstruction(Cursor);
414  Cursor = NextInstruction(Cursor)) {
415 
416  // We need to ensure a safepoint poll occurs before any 'real' call. The
417  // easiest way to ensure finite execution between safepoints in the face of
418  // recursive and mutually recursive functions is to enforce that each take
419  // a safepoint. Additionally, we need to ensure a poll before any call
420  // which can grow the stack by an unbounded amount. This isn't required
421  // for GC semantics per se, but is a common requirement for languages
422  // which detect stack overflow via guard pages and then throw exceptions.
423  if (auto *Call = dyn_cast<CallBase>(Cursor)) {
425  continue;
426  break;
427  }
428  }
429 
430  assert((HasNextInstruction(Cursor) || Cursor->isTerminator()) &&
431  "either we stopped because of a call, or because of terminator");
432 
433  return Cursor;
434 }
435 
436 static const char *const GCSafepointPollName = "gc.safepoint_poll";
437 
438 static bool isGCSafepointPoll(Function &F) {
439  return F.getName().equals(GCSafepointPollName);
440 }
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.
446  // TODO: This should check the GCStrategy
447  if (F.hasGC()) {
448  const auto &FunctionGCName = F.getGC();
449  const StringRef StatepointExampleName("statepoint-example");
450  const StringRef CoreCLRName("coreclr");
451  return (StatepointExampleName == FunctionGCName) ||
452  (CoreCLRName == FunctionGCName);
453  } else
454  return false;
455 }
456 
457 // TODO: These should become properties of the GCStrategy, possibly with
458 // command line overrides.
459 static bool enableEntrySafepoints(Function &F) { return !NoEntry; }
460 static bool enableBackedgeSafepoints(Function &F) { return !NoBackedge; }
461 static bool enableCallSafepoints(Function &F) { return !NoCall; }
462 
464  if (F.isDeclaration() || F.empty()) {
465  // This is a declaration, nothing to do. Must exit early to avoid crash in
466  // dom tree calculation
467  return false;
468  }
469 
470  if (isGCSafepointPoll(F)) {
471  // Given we're inlining this inside of safepoint poll insertion, this
472  // doesn't make any sense. Note that we do make any contained calls
473  // parseable after we inline a poll.
474  return false;
475  }
476 
477  if (!shouldRewriteFunction(F))
478  return false;
479 
480  const TargetLibraryInfo &TLI =
481  getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
482 
483  bool Modified = false;
484 
485  // In various bits below, we rely on the fact that uses are reachable from
486  // defs. When there are basic blocks unreachable from the entry, dominance
487  // and reachablity queries return non-sensical results. Thus, we preprocess
488  // the function to ensure these properties hold.
489  Modified |= removeUnreachableBlocks(F);
490 
491  // STEP 1 - Insert the safepoint polling locations. We do not need to
492  // actually insert parse points yet. That will be done for all polls and
493  // calls in a single pass.
494 
495  DominatorTree DT;
496  DT.recalculate(F);
497 
498  SmallVector<Instruction *, 16> PollsNeeded;
499  std::vector<CallBase *> ParsePointNeeded;
500 
501  if (enableBackedgeSafepoints(F)) {
502  // Construct a pass manager to run the LoopPass backedge logic. We
503  // need the pass manager to handle scheduling all the loop passes
504  // appropriately. Doing this by hand is painful and just not worth messing
505  // with for the moment.
507  bool CanAssumeCallSafepoints = enableCallSafepoints(F);
508  auto *PBS = new PlaceBackedgeSafepointsImpl(CanAssumeCallSafepoints);
509  FPM.add(PBS);
510  FPM.run(F);
511 
512  // We preserve dominance information when inserting the poll, otherwise
513  // we'd have to recalculate this on every insert
514  DT.recalculate(F);
515 
516  auto &PollLocations = PBS->PollLocations;
517 
518  auto OrderByBBName = [](Instruction *a, Instruction *b) {
519  return a->getParent()->getName() < b->getParent()->getName();
520  };
521  // We need the order of list to be stable so that naming ends up stable
522  // when we split edges. This makes test cases much easier to write.
523  llvm::sort(PollLocations, OrderByBBName);
524 
525  // We can sometimes end up with duplicate poll locations. This happens if
526  // a single loop is visited more than once. The fact this happens seems
527  // wrong, but it does happen for the split-backedge.ll test case.
528  PollLocations.erase(std::unique(PollLocations.begin(),
529  PollLocations.end()),
530  PollLocations.end());
531 
532  // Insert a poll at each point the analysis pass identified
533  // The poll location must be the terminator of a loop latch block.
534  for (Instruction *Term : PollLocations) {
535  // We are inserting a poll, the function is modified
536  Modified = true;
537 
538  if (SplitBackedge) {
539  // Split the backedge of the loop and insert the poll within that new
540  // basic block. This creates a loop with two latches per original
541  // latch (which is non-ideal), but this appears to be easier to
542  // optimize in practice than inserting the poll immediately before the
543  // latch test.
544 
545  // Since this is a latch, at least one of the successors must dominate
546  // it. Its possible that we have a) duplicate edges to the same header
547  // and b) edges to distinct loop headers. We need to insert pools on
548  // each.
549  SetVector<BasicBlock *> Headers;
550  for (unsigned i = 0; i < Term->getNumSuccessors(); i++) {
551  BasicBlock *Succ = Term->getSuccessor(i);
552  if (DT.dominates(Succ, Term->getParent())) {
553  Headers.insert(Succ);
554  }
555  }
556  assert(!Headers.empty() && "poll location is not a loop latch?");
557 
558  // The split loop structure here is so that we only need to recalculate
559  // the dominator tree once. Alternatively, we could just keep it up to
560  // date and use a more natural merged loop.
561  SetVector<BasicBlock *> SplitBackedges;
562  for (BasicBlock *Header : Headers) {
563  BasicBlock *NewBB = SplitEdge(Term->getParent(), Header, &DT);
564  PollsNeeded.push_back(NewBB->getTerminator());
565  NumBackedgeSafepoints++;
566  }
567  } else {
568  // Split the latch block itself, right before the terminator.
569  PollsNeeded.push_back(Term);
570  NumBackedgeSafepoints++;
571  }
572  }
573  }
574 
575  if (enableEntrySafepoints(F)) {
576  if (Instruction *Location = findLocationForEntrySafepoint(F, DT)) {
577  PollsNeeded.push_back(Location);
578  Modified = true;
579  NumEntrySafepoints++;
580  }
581  // TODO: else we should assert that there was, in fact, a policy choice to
582  // not insert a entry safepoint poll.
583  }
584 
585  // Now that we've identified all the needed safepoint poll locations, insert
586  // safepoint polls themselves.
587  for (Instruction *PollLocation : PollsNeeded) {
588  std::vector<CallBase *> RuntimeCalls;
589  InsertSafepointPoll(PollLocation, RuntimeCalls, TLI);
590  ParsePointNeeded.insert(ParsePointNeeded.end(), RuntimeCalls.begin(),
591  RuntimeCalls.end());
592  }
593 
594  return Modified;
595 }
596 
598 char PlaceSafepoints::ID = 0;
599 
601  return new PlaceSafepoints();
602 }
603 
604 INITIALIZE_PASS_BEGIN(PlaceBackedgeSafepointsImpl,
605  "place-backedge-safepoints-impl",
606  "Place Backedge Safepoints", false, false)
610 INITIALIZE_PASS_END(PlaceBackedgeSafepointsImpl,
611  "place-backedge-safepoints-impl",
612  "Place Backedge Safepoints", false, false)
613 
614 INITIALIZE_PASS_BEGIN(PlaceSafepoints, "place-safepoints", "Place Safepoints",
615  false, false)
616 INITIALIZE_PASS_END(PlaceSafepoints, "place-safepoints", "Place Safepoints",
617  false, false)
618 
619 static void
621  std::vector<CallBase *> &ParsePointsNeeded /*rval*/,
622  const TargetLibraryInfo &TLI) {
623  BasicBlock *OrigBB = InsertBefore->getParent();
624  Module *M = InsertBefore->getModule();
625  assert(M && "must be part of a module");
626 
627  // Inline the safepoint poll implementation - this will get all the branch,
628  // control flow, etc.. Most importantly, it will introduce the actual slow
629  // path call - where we need to insert a safepoint (parsepoint).
630 
631  auto *F = M->getFunction(GCSafepointPollName);
632  assert(F && "gc.safepoint_poll function is missing");
633  assert(F->getValueType() ==
635  "gc.safepoint_poll declared with wrong type");
636  assert(!F->empty() && "gc.safepoint_poll must be a non-empty function");
637  CallInst *PollCall = CallInst::Create(F, "", InsertBefore);
638 
639  // Record some information about the call site we're replacing
640  BasicBlock::iterator Before(PollCall), After(PollCall);
641  bool IsBegin = false;
642  if (Before == OrigBB->begin())
643  IsBegin = true;
644  else
645  Before--;
646 
647  After++;
648  assert(After != OrigBB->end() && "must have successor");
649 
650  // Do the actual inlining
651  InlineFunctionInfo IFI;
652  bool InlineStatus = InlineFunction(PollCall, IFI);
653  assert(InlineStatus && "inline must succeed");
654  (void)InlineStatus; // suppress warning in release-asserts
655 
656  // Check post-conditions
657  assert(IFI.StaticAllocas.empty() && "can't have allocs");
658 
659  std::vector<CallInst *> Calls; // new calls
660  DenseSet<BasicBlock *> BBs; // new BBs + insertee
661 
662  // Include only the newly inserted instructions, Note: begin may not be valid
663  // if we inserted to the beginning of the basic block
664  BasicBlock::iterator Start = IsBegin ? OrigBB->begin() : std::next(Before);
665 
666  // If your poll function includes an unreachable at the end, that's not
667  // valid. Bugpoint likes to create this, so check for it.
668  assert(isPotentiallyReachable(&*Start, &*After) &&
669  "malformed poll function");
670 
671  scanInlinedCode(&*Start, &*After, Calls, BBs);
672  assert(!Calls.empty() && "slow path not found for safepoint poll");
673 
674  // Record the fact we need a parsable state at the runtime call contained in
675  // the poll function. This is required so that the runtime knows how to
676  // parse the last frame when we actually take the safepoint (i.e. execute
677  // the slow path)
678  assert(ParsePointsNeeded.empty());
679  for (auto *CI : Calls) {
680  // No safepoint needed or wanted
681  if (!needsStatepoint(CI, TLI))
682  continue;
683 
684  // These are likely runtime calls. Should we assert that via calling
685  // convention or something?
686  ParsePointsNeeded.push_back(CI);
687  }
688  assert(ParsePointsNeeded.size() <= Calls.size());
689 }
static bool mustBeFiniteCountedLoop(Loop *L, ScalarEvolution *SE, BasicBlock *Pred)
Returns true if this loop is known to terminate in a finite number of iterations. ...
STATISTIC(NumEntrySafepoints, "Number of entry safepoints inserted")
bool empty() const
Definition: Function.h:678
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static bool shouldRewriteFunction(Function &F)
Returns true if this function should be rewritten to include safepoint polls and parseable call sites...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock *> *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction &#39;To&#39; is reachable from &#39;From&#39;, without passing through any blocks in Ex...
Definition: CFG.cpp:211
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
void push_back(const T &Elt)
Definition: SmallVector.h:211
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
The main scalar evolution driver.
bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI=nullptr, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function&#39;s entry.
Definition: Local.cpp:2228
This class represents a function call, abstracting a target machine&#39;s calling convention.
bool isTerminator() const
Definition: Instruction.h:128
void initializePlaceSafepointsPass(PassRegistry &)
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
F(f)
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
This class captures the data input to the InlineFunction call, and records the auxiliary results prod...
Definition: Cloning.h:173
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Split the edge connecting specified block.
static void scanOneBB(Instruction *Start, Instruction *End, std::vector< CallInst *> &Calls, DenseSet< BasicBlock *> &Seen, std::vector< BasicBlock *> &Worklist)
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Definition: BitVector.h:937
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:244
void getLoopLatches(SmallVectorImpl< BlockT *> &LoopLatches) const
Return all loop latch blocks of this loop.
Definition: LoopInfo.h:306
static cl::opt< bool > NoBackedge("spp-no-backedge", cl::Hidden, cl::init(false))
BlockT * getHeader() const
Definition: LoopInfo.h:102
static bool doesNotRequireEntrySafepointBefore(CallBase *Call)
Returns true if an entry safepoint is not required before this callsite in the caller function...
static bool enableCallSafepoints(Function &F)
INITIALIZE_PASS_BEGIN(PlaceBackedgeSafepointsImpl, "place-backedge-safepoints-impl", "Place Backedge Safepoints", false, false) INITIALIZE_PASS_END(PlaceBackedgeSafepointsImpl
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
bool isStatepoint(const CallBase *Call)
Definition: Statepoint.cpp:20
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:246
const std::string & getGC() const
Definition: Function.cpp:477
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
void initializePlaceBackedgeSafepointsImplPass(PassRegistry &)
static void scanInlinedCode(Instruction *Start, Instruction *End, std::vector< CallInst *> &Calls, DenseSet< BasicBlock *> &Seen)
static const char *const GCSafepointPollName
static cl::opt< bool > SplitBackedge("spp-split-backedge", cl::Hidden, cl::init(false))
const BasicBlock & getEntryBlock() const
Definition: Function.h:656
static Instruction * findLocationForEntrySafepoint(Function &F, DominatorTree &DT)
const SCEV * getCouldNotCompute()
NodeT * getBlock() const
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static bool enableEntrySafepoints(Function &F)
FunctionPass * createPlaceSafepointsPass()
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop...
Definition: LoopInfo.h:205
DomTreeNodeBase * getIDom() const
const Instruction & front() const
Definition: BasicBlock.h:280
static void InsertSafepointPoll(Instruction *InsertBefore, std::vector< CallBase *> &ParsePointsNeeded, const TargetLibraryInfo &TLI)
static cl::opt< bool > NoCall("spp-no-call", cl::Hidden, cl::init(false))
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
Represent the analysis usage information of a pass.
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:160
static cl::opt< bool > AllBackedges("spp-all-backedges", cl::Hidden, cl::init(false))
const Instruction & back() const
Definition: BasicBlock.h:282
const SCEV * getMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
static FunctionType * get(Type *Result, ArrayRef< Type *> Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:296
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
Definition: APInt.h:449
place backedge safepoints Place Backedge Safepoints
InlineResult InlineFunction(CallBase *CB, InlineFunctionInfo &IFI, AAResults *CalleeAAR=nullptr, bool InsertLifetime=true)
This function inlines the called function into the basic block of the caller.
FunctionPassManager manages FunctionPasses and BasicBlockPassManagers.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
static bool isGCSafepointPoll(Function &F)
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1122
bool isGCRelocate(const CallBase *Call)
Definition: Statepoint.cpp:36
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:112
Iterator for intrusive lists based on ilist_node.
iterator end()
Definition: BasicBlock.h:270
bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI)
Return true if this call calls a gc leaf function.
Definition: Local.cpp:2480
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:248
Provides information about what library functions are available for the current target.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Definition: Module.cpp:174
void setPreservesAll()
Set by analyses that do not transform their input at all.
static cl::opt< bool > NoEntry("spp-no-entry", cl::Hidden, cl::init(false))
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:89
static cl::opt< int > CountedLoopTripWidth("spp-counted-loop-trip-width", cl::Hidden, cl::init(32))
How narrow does the trip count of a loop have to be to have to be considered "counted"? Counted loops do not get safepoints at backedges.
LLVM_NODISCARD bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
Definition: StringRef.h:160
bool hasGC() const
hasGC/getGC/setGC/clearGC - The name of the garbage collection algorithm to use during code generatio...
Definition: Function.h:351
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:467
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
Type * getValueType() const
Definition: GlobalValue.h:279
place backedge safepoints Place Backedge false place safepoints
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:227
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
static bool enableBackedgeSafepoints(Function &F)
static bool needsStatepoint(CallBase *Call, const TargetLibraryInfo &TLI)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
aarch64 promote const
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
A vector that has set insertion semantics.
Definition: SetVector.h:40
succ_range successors(Instruction *I)
Definition: CFG.h:259
static bool containsUnconditionalCallSafepoint(Loop *L, BasicBlock *Header, BasicBlock *Pred, DominatorTree &DT, const TargetLibraryInfo &TLI)
Returns true if this loop is known to contain a call safepoint which must unconditionally execute on ...
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:1138
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
const SCEV * getExitCount(const Loop *L, BasicBlock *ExitingBlock)
Get the expression for the number of loop iterations for which this loop is guaranteed not to exit vi...
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
#define LLVM_DEBUG(X)
Definition: Debug.h:122
bool isGCResult(const CallBase *Call)
Definition: Statepoint.cpp:46
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43
const BasicBlock * getParent() const
Definition: Instruction.h:66