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