LLVM  6.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"
58 #include "llvm/IR/CallSite.h"
59 #include "llvm/IR/Dominators.h"
60 #include "llvm/IR/IntrinsicInst.h"
62 #include "llvm/IR/Statepoint.h"
64 #include "llvm/Support/Debug.h"
65 #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 
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  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  DEBUG(dbgs() << "skipping safepoint placement due to unconditional call\n");
336  CallInLoop++;
337  continue;
338  }
339  }
340 
341  // TODO: We can create an inner loop which runs a finite number of
342  // iterations with an outer loop which contains a safepoint. This would
343  // not help runtime performance that much, but it might help our ability to
344  // optimize the inner loop.
345 
346  // Safepoint insertion would involve creating a new basic block (as the
347  // target of the current backedge) which does the safepoint (of all live
348  // variables) and branches to the true header
349  TerminatorInst *Term = Pred->getTerminator();
350 
351  DEBUG(dbgs() << "[LSP] terminator instruction: " << *Term);
352 
353  PollLocations.push_back(Term);
354  }
355 
356  return false;
357 }
358 
359 /// Returns true if an entry safepoint is not required before this callsite in
360 /// the caller function.
362  Instruction *Inst = CS.getInstruction();
363  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
364  switch (II->getIntrinsicID()) {
365  case Intrinsic::experimental_gc_statepoint:
366  case Intrinsic::experimental_patchpoint_void:
367  case Intrinsic::experimental_patchpoint_i64:
368  // The can wrap an actual call which may grow the stack by an unbounded
369  // amount or run forever.
370  return false;
371  default:
372  // Most LLVM intrinsics are things which do not expand to actual calls, or
373  // at least if they do, are leaf functions that cause only finite stack
374  // growth. In particular, the optimizer likes to form things like memsets
375  // out of stores in the original IR. Another important example is
376  // llvm.localescape which must occur in the entry block. Inserting a
377  // safepoint before it is not legal since it could push the localescape
378  // out of the entry block.
379  return true;
380  }
381  }
382  return false;
383 }
384 
386  DominatorTree &DT) {
387 
388  // Conceptually, this poll needs to be on method entry, but in
389  // practice, we place it as late in the entry block as possible. We
390  // can place it as late as we want as long as it dominates all calls
391  // that can grow the stack. This, combined with backedge polls,
392  // give us all the progress guarantees we need.
393 
394  // hasNextInstruction and nextInstruction are used to iterate
395  // through a "straight line" execution sequence.
396 
397  auto HasNextInstruction = [](Instruction *I) {
398  if (!I->isTerminator())
399  return true;
400 
401  BasicBlock *nextBB = I->getParent()->getUniqueSuccessor();
402  return nextBB && (nextBB->getUniquePredecessor() != nullptr);
403  };
404 
405  auto NextInstruction = [&](Instruction *I) {
406  assert(HasNextInstruction(I) &&
407  "first check if there is a next instruction!");
408 
409  if (I->isTerminator())
410  return &I->getParent()->getUniqueSuccessor()->front();
411  return &*++I->getIterator();
412  };
413 
414  Instruction *Cursor = nullptr;
415  for (Cursor = &F.getEntryBlock().front(); HasNextInstruction(Cursor);
416  Cursor = NextInstruction(Cursor)) {
417 
418  // We need to ensure a safepoint poll occurs before any 'real' call. The
419  // easiest way to ensure finite execution between safepoints in the face of
420  // recursive and mutually recursive functions is to enforce that each take
421  // a safepoint. Additionally, we need to ensure a poll before any call
422  // which can grow the stack by an unbounded amount. This isn't required
423  // for GC semantics per se, but is a common requirement for languages
424  // which detect stack overflow via guard pages and then throw exceptions.
425  if (auto CS = CallSite(Cursor)) {
427  continue;
428  break;
429  }
430  }
431 
432  assert((HasNextInstruction(Cursor) || Cursor->isTerminator()) &&
433  "either we stopped because of a call, or because of terminator");
434 
435  return Cursor;
436 }
437 
438 static const char *const GCSafepointPollName = "gc.safepoint_poll";
439 
440 static bool isGCSafepointPoll(Function &F) {
441  return F.getName().equals(GCSafepointPollName);
442 }
443 
444 /// Returns true if this function should be rewritten to include safepoint
445 /// polls and parseable call sites. The main point of this function is to be
446 /// an extension point for custom logic.
448  // TODO: This should check the GCStrategy
449  if (F.hasGC()) {
450  const auto &FunctionGCName = F.getGC();
451  const StringRef StatepointExampleName("statepoint-example");
452  const StringRef CoreCLRName("coreclr");
453  return (StatepointExampleName == FunctionGCName) ||
454  (CoreCLRName == FunctionGCName);
455  } else
456  return false;
457 }
458 
459 // TODO: These should become properties of the GCStrategy, possibly with
460 // command line overrides.
461 static bool enableEntrySafepoints(Function &F) { return !NoEntry; }
462 static bool enableBackedgeSafepoints(Function &F) { return !NoBackedge; }
463 static bool enableCallSafepoints(Function &F) { return !NoCall; }
464 
466  if (F.isDeclaration() || F.empty()) {
467  // This is a declaration, nothing to do. Must exit early to avoid crash in
468  // dom tree calculation
469  return false;
470  }
471 
472  if (isGCSafepointPoll(F)) {
473  // Given we're inlining this inside of safepoint poll insertion, this
474  // doesn't make any sense. Note that we do make any contained calls
475  // parseable after we inline a poll.
476  return false;
477  }
478 
479  if (!shouldRewriteFunction(F))
480  return false;
481 
482  const TargetLibraryInfo &TLI =
483  getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
484 
485  bool Modified = false;
486 
487  // In various bits below, we rely on the fact that uses are reachable from
488  // defs. When there are basic blocks unreachable from the entry, dominance
489  // and reachablity queries return non-sensical results. Thus, we preprocess
490  // the function to ensure these properties hold.
491  Modified |= removeUnreachableBlocks(F);
492 
493  // STEP 1 - Insert the safepoint polling locations. We do not need to
494  // actually insert parse points yet. That will be done for all polls and
495  // calls in a single pass.
496 
497  DominatorTree DT;
498  DT.recalculate(F);
499 
500  SmallVector<Instruction *, 16> PollsNeeded;
501  std::vector<CallSite> ParsePointNeeded;
502 
503  if (enableBackedgeSafepoints(F)) {
504  // Construct a pass manager to run the LoopPass backedge logic. We
505  // need the pass manager to handle scheduling all the loop passes
506  // appropriately. Doing this by hand is painful and just not worth messing
507  // with for the moment.
509  bool CanAssumeCallSafepoints = enableCallSafepoints(F);
510  auto *PBS = new PlaceBackedgeSafepointsImpl(CanAssumeCallSafepoints);
511  FPM.add(PBS);
512  FPM.run(F);
513 
514  // We preserve dominance information when inserting the poll, otherwise
515  // we'd have to recalculate this on every insert
516  DT.recalculate(F);
517 
518  auto &PollLocations = PBS->PollLocations;
519 
520  auto OrderByBBName = [](Instruction *a, Instruction *b) {
521  return a->getParent()->getName() < b->getParent()->getName();
522  };
523  // We need the order of list to be stable so that naming ends up stable
524  // when we split edges. This makes test cases much easier to write.
525  std::sort(PollLocations.begin(), PollLocations.end(), OrderByBBName);
526 
527  // We can sometimes end up with duplicate poll locations. This happens if
528  // a single loop is visited more than once. The fact this happens seems
529  // wrong, but it does happen for the split-backedge.ll test case.
530  PollLocations.erase(std::unique(PollLocations.begin(),
531  PollLocations.end()),
532  PollLocations.end());
533 
534  // Insert a poll at each point the analysis pass identified
535  // The poll location must be the terminator of a loop latch block.
536  for (TerminatorInst *Term : PollLocations) {
537  // We are inserting a poll, the function is modified
538  Modified = true;
539 
540  if (SplitBackedge) {
541  // Split the backedge of the loop and insert the poll within that new
542  // basic block. This creates a loop with two latches per original
543  // latch (which is non-ideal), but this appears to be easier to
544  // optimize in practice than inserting the poll immediately before the
545  // latch test.
546 
547  // Since this is a latch, at least one of the successors must dominate
548  // it. Its possible that we have a) duplicate edges to the same header
549  // and b) edges to distinct loop headers. We need to insert pools on
550  // each.
551  SetVector<BasicBlock *> Headers;
552  for (unsigned i = 0; i < Term->getNumSuccessors(); i++) {
553  BasicBlock *Succ = Term->getSuccessor(i);
554  if (DT.dominates(Succ, Term->getParent())) {
555  Headers.insert(Succ);
556  }
557  }
558  assert(!Headers.empty() && "poll location is not a loop latch?");
559 
560  // The split loop structure here is so that we only need to recalculate
561  // the dominator tree once. Alternatively, we could just keep it up to
562  // date and use a more natural merged loop.
563  SetVector<BasicBlock *> SplitBackedges;
564  for (BasicBlock *Header : Headers) {
565  BasicBlock *NewBB = SplitEdge(Term->getParent(), Header, &DT);
566  PollsNeeded.push_back(NewBB->getTerminator());
567  NumBackedgeSafepoints++;
568  }
569  } else {
570  // Split the latch block itself, right before the terminator.
571  PollsNeeded.push_back(Term);
572  NumBackedgeSafepoints++;
573  }
574  }
575  }
576 
577  if (enableEntrySafepoints(F)) {
578  if (Instruction *Location = findLocationForEntrySafepoint(F, DT)) {
579  PollsNeeded.push_back(Location);
580  Modified = true;
581  NumEntrySafepoints++;
582  }
583  // TODO: else we should assert that there was, in fact, a policy choice to
584  // not insert a entry safepoint poll.
585  }
586 
587  // Now that we've identified all the needed safepoint poll locations, insert
588  // safepoint polls themselves.
589  for (Instruction *PollLocation : PollsNeeded) {
590  std::vector<CallSite> RuntimeCalls;
591  InsertSafepointPoll(PollLocation, RuntimeCalls, TLI);
592  ParsePointNeeded.insert(ParsePointNeeded.end(), RuntimeCalls.begin(),
593  RuntimeCalls.end());
594  }
595 
596  return Modified;
597 }
598 
600 char PlaceSafepoints::ID = 0;
601 
603  return new PlaceSafepoints();
604 }
605 
606 INITIALIZE_PASS_BEGIN(PlaceBackedgeSafepointsImpl,
607  "place-backedge-safepoints-impl",
608  "Place Backedge Safepoints", false, false)
612 INITIALIZE_PASS_END(PlaceBackedgeSafepointsImpl,
613  "place-backedge-safepoints-impl",
614  "Place Backedge Safepoints", false, false)
615 
616 INITIALIZE_PASS_BEGIN(PlaceSafepoints, "place-safepoints", "Place Safepoints",
617  false, false)
618 INITIALIZE_PASS_END(PlaceSafepoints, "place-safepoints", "Place Safepoints",
619  false, false)
620 
621 static void
623  std::vector<CallSite> &ParsePointsNeeded /*rval*/,
624  const TargetLibraryInfo &TLI) {
625  BasicBlock *OrigBB = InsertBefore->getParent();
626  Module *M = InsertBefore->getModule();
627  assert(M && "must be part of a module");
628 
629  // Inline the safepoint poll implementation - this will get all the branch,
630  // control flow, etc.. Most importantly, it will introduce the actual slow
631  // path call - where we need to insert a safepoint (parsepoint).
632 
633  auto *F = M->getFunction(GCSafepointPollName);
634  assert(F && "gc.safepoint_poll function is missing");
635  assert(F->getValueType() ==
637  "gc.safepoint_poll declared with wrong type");
638  assert(!F->empty() && "gc.safepoint_poll must be a non-empty function");
639  CallInst *PollCall = CallInst::Create(F, "", InsertBefore);
640 
641  // Record some information about the call site we're replacing
642  BasicBlock::iterator Before(PollCall), After(PollCall);
643  bool IsBegin = false;
644  if (Before == OrigBB->begin())
645  IsBegin = true;
646  else
647  Before--;
648 
649  After++;
650  assert(After != OrigBB->end() && "must have successor");
651 
652  // Do the actual inlining
653  InlineFunctionInfo IFI;
654  bool InlineStatus = InlineFunction(PollCall, IFI);
655  assert(InlineStatus && "inline must succeed");
656  (void)InlineStatus; // suppress warning in release-asserts
657 
658  // Check post-conditions
659  assert(IFI.StaticAllocas.empty() && "can't have allocs");
660 
661  std::vector<CallInst *> Calls; // new calls
662  DenseSet<BasicBlock *> BBs; // new BBs + insertee
663 
664  // Include only the newly inserted instructions, Note: begin may not be valid
665  // if we inserted to the beginning of the basic block
666  BasicBlock::iterator Start = IsBegin ? OrigBB->begin() : std::next(Before);
667 
668  // If your poll function includes an unreachable at the end, that's not
669  // valid. Bugpoint likes to create this, so check for it.
670  assert(isPotentiallyReachable(&*Start, &*After) &&
671  "malformed poll function");
672 
673  scanInlinedCode(&*Start, &*After, Calls, BBs);
674  assert(!Calls.empty() && "slow path not found for safepoint poll");
675 
676  // Record the fact we need a parsable state at the runtime call contained in
677  // the poll function. This is required so that the runtime knows how to
678  // parse the last frame when we actually take the safepoint (i.e. execute
679  // the slow path)
680  assert(ParsePointsNeeded.empty());
681  for (auto *CI : Calls) {
682  // No safepoint needed or wanted
683  if (!needsStatepoint(CI, TLI))
684  continue;
685 
686  // These are likely runtime calls. Should we assert that via calling
687  // convention or something?
688  ParsePointsNeeded.push_back(CallSite(CI));
689  }
690  assert(ParsePointsNeeded.size() <= Calls.size());
691 }
DomTreeNodeBase< NodeT > * getNode(NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
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:594
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:128
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:252
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:920
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:237
void getLoopLatches(SmallVectorImpl< BlockT *> &LoopLatches) const
Return all loop latch blocks of this loop.
Definition: LoopInfo.h:284
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:230
const std::string & getGC() const
Definition: Function.cpp:444
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
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:572
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:406
static bool enableEntrySafepoints(Function &F)
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:54
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:197
DomTreeNodeBase * getIDom() const
const Instruction & front() const
Definition: BasicBlock.h:264
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:266
const SCEV * getMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
static const unsigned End
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:1896
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:443
place backedge safepoints Place Backedge Safepoints
FunctionPassManager manages FunctionPasses and BasicBlockPassManagers.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
static bool isGCSafepointPoll(Function &F)
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:254
bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI=nullptr)
Remove all blocks that can not be reached from the function&#39;s entry.
Definition: Local.cpp:1730
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:239
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: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:286
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:439
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:220
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:267
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:556
succ_range successors(BasicBlock *BB)
Definition: CFG.h:143
A vector that has set insertion semantics.
Definition: SetVector.h:41
#define DEBUG(X)
Definition: Debug.h:118
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:958
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:267
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition: Parallel.h:199
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:120
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:66