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