1 //===- PlaceSafepoints.cpp - Place GC Safepoints --------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
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".
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.
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.
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.
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.
49 //===----------------------------------------------------------------------===//
51 #include "llvm/Pass.h"
52 #include "llvm/IR/LegacyPassManager.h"
53 #include "llvm/ADT/SetOperations.h"
54 #include "llvm/ADT/SetVector.h"
55 #include "llvm/ADT/Statistic.h"
56 #include "llvm/ADT/StringRef.h"
57 #include "llvm/Analysis/LoopPass.h"
58 #include "llvm/Analysis/LoopInfo.h"
59 #include "llvm/Analysis/ScalarEvolution.h"
60 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
61 #include "llvm/Analysis/CFG.h"
62 #include "llvm/Analysis/InstructionSimplify.h"
63 #include "llvm/IR/BasicBlock.h"
64 #include "llvm/IR/CallSite.h"
65 #include "llvm/IR/Dominators.h"
66 #include "llvm/IR/Function.h"
67 #include "llvm/IR/IRBuilder.h"
68 #include "llvm/IR/InstIterator.h"
69 #include "llvm/IR/Instructions.h"
70 #include "llvm/IR/Intrinsics.h"
71 #include "llvm/IR/IntrinsicInst.h"
72 #include "llvm/IR/Module.h"
73 #include "llvm/IR/Statepoint.h"
74 #include "llvm/IR/Value.h"
75 #include "llvm/IR/Verifier.h"
76 #include "llvm/Support/Debug.h"
77 #include "llvm/Support/CommandLine.h"
78 #include "llvm/Support/raw_ostream.h"
79 #include "llvm/Transforms/Scalar.h"
80 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
81 #include "llvm/Transforms/Utils/Cloning.h"
82 #include "llvm/Transforms/Utils/Local.h"
84 #define DEBUG_TYPE "safepoint-placement"
85 STATISTIC(NumEntrySafepoints, "Number of entry safepoints inserted");
86 STATISTIC(NumCallSafepoints, "Number of call safepoints inserted");
87 STATISTIC(NumBackedgeSafepoints, "Number of backedge safepoints inserted");
89 STATISTIC(CallInLoop, "Number of loops w/o safepoints due to calls in loop");
90 STATISTIC(FiniteExecution, "Number of loops w/o safepoints finite execution");
94 // Ignore opportunities to avoid placing safepoints on backedges, useful for
96 static cl::opt<bool> AllBackedges("spp-all-backedges", cl::Hidden,
99 /// How narrow does the trip count of a loop have to be to have to be considered
100 /// "counted"? Counted loops do not get safepoints at backedges.
101 static cl::opt<int> CountedLoopTripWidth("spp-counted-loop-trip-width",
102 cl::Hidden, cl::init(32));
104 // If true, split the backedge of a loop when placing the safepoint, otherwise
105 // split the latch block itself. Both are useful to support for
106 // experimentation, but in practice, it looks like splitting the backedge
108 static cl::opt<bool> SplitBackedge("spp-split-backedge", cl::Hidden,
111 // Print tracing output
112 static cl::opt<bool> TraceLSP("spp-trace", cl::Hidden, cl::init(false));
116 /// An analysis pass whose purpose is to identify each of the backedges in
117 /// the function which require a safepoint poll to be inserted.
118 struct PlaceBackedgeSafepointsImpl : public FunctionPass {
121 /// The output of the pass - gives a list of each backedge (described by
122 /// pointing at the branch) which need a poll inserted.
123 std::vector<TerminatorInst *> PollLocations;
125 /// True unless we're running spp-no-calls in which case we need to disable
126 /// the call-dependent placement opts.
127 bool CallSafepointsEnabled;
129 ScalarEvolution *SE = nullptr;
130 DominatorTree *DT = nullptr;
131 LoopInfo *LI = nullptr;
133 PlaceBackedgeSafepointsImpl(bool CallSafepoints = false)
134 : FunctionPass(ID), CallSafepointsEnabled(CallSafepoints) {
135 initializePlaceBackedgeSafepointsImplPass(*PassRegistry::getPassRegistry());
138 bool runOnLoop(Loop *);
139 void runOnLoopAndSubLoops(Loop *L) {
140 // Visit all the subloops
141 for (auto I = L->begin(), E = L->end(); I != E; I++)
142 runOnLoopAndSubLoops(*I);
146 bool runOnFunction(Function &F) override {
147 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
148 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
149 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
150 for (auto I = LI->begin(), E = LI->end(); I != E; I++) {
151 runOnLoopAndSubLoops(*I);
156 void getAnalysisUsage(AnalysisUsage &AU) const override {
157 AU.addRequired<DominatorTreeWrapperPass>();
158 AU.addRequired<ScalarEvolutionWrapperPass>();
159 AU.addRequired<LoopInfoWrapperPass>();
160 // We no longer modify the IR at all in this pass. Thus all
161 // analysis are preserved.
162 AU.setPreservesAll();
167 static cl::opt<bool> NoEntry("spp-no-entry", cl::Hidden, cl::init(false));
168 static cl::opt<bool> NoCall("spp-no-call", cl::Hidden, cl::init(false));
169 static cl::opt<bool> NoBackedge("spp-no-backedge", cl::Hidden, cl::init(false));
172 struct PlaceSafepoints : public FunctionPass {
173 static char ID; // Pass identification, replacement for typeid
175 PlaceSafepoints() : FunctionPass(ID) {
176 initializePlaceSafepointsPass(*PassRegistry::getPassRegistry());
178 bool runOnFunction(Function &F) override;
180 void getAnalysisUsage(AnalysisUsage &AU) const override {
181 // We modify the graph wholesale (inlining, block insertion, etc). We
182 // preserve nothing at the moment. We could potentially preserve dom tree
183 // if that was worth doing
188 // Insert a safepoint poll immediately before the given instruction. Does
189 // not handle the parsability of state at the runtime call, that's the
192 InsertSafepointPoll(Instruction *InsertBefore,
193 std::vector<CallSite> &ParsePointsNeeded /*rval*/);
195 static bool isGCLeafFunction(const CallSite &CS);
197 static bool needsStatepoint(const CallSite &CS) {
198 if (isGCLeafFunction(CS))
201 CallInst *call = cast<CallInst>(CS.getInstruction());
202 if (call->isInlineAsm())
205 if (isStatepoint(CS) || isGCRelocate(CS) || isGCResult(CS)) {
211 static Value *ReplaceWithStatepoint(const CallSite &CS, Pass *P);
213 /// Returns true if this loop is known to contain a call safepoint which
214 /// must unconditionally execute on any iteration of the loop which returns
215 /// to the loop header via an edge from Pred. Returns a conservative correct
216 /// answer; i.e. false is always valid.
217 static bool containsUnconditionalCallSafepoint(Loop *L, BasicBlock *Header,
220 // In general, we're looking for any cut of the graph which ensures
221 // there's a call safepoint along every edge between Header and Pred.
222 // For the moment, we look only for the 'cuts' that consist of a single call
223 // instruction in a block which is dominated by the Header and dominates the
224 // loop latch (Pred) block. Somewhat surprisingly, walking the entire chain
225 // of such dominating blocks gets substantially more occurrences than just
226 // checking the Pred and Header blocks themselves. This may be due to the
227 // density of loop exit conditions caused by range and null checks.
228 // TODO: structure this as an analysis pass, cache the result for subloops,
229 // avoid dom tree recalculations
230 assert(DT.dominates(Header, Pred) && "loop latch not dominated by header?");
232 BasicBlock *Current = Pred;
234 for (Instruction &I : *Current) {
235 if (auto CS = CallSite(&I))
236 // Note: Technically, needing a safepoint isn't quite the right
237 // condition here. We should instead be checking if the target method
239 // unconditional poll. In practice, this is only a theoretical concern
240 // since we don't have any methods with conditional-only safepoint
242 if (needsStatepoint(CS))
246 if (Current == Header)
248 Current = DT.getNode(Current)->getIDom()->getBlock();
254 /// Returns true if this loop is known to terminate in a finite number of
255 /// iterations. Note that this function may return false for a loop which
256 /// does actual terminate in a finite constant number of iterations due to
257 /// conservatism in the analysis.
258 static bool mustBeFiniteCountedLoop(Loop *L, ScalarEvolution *SE,
260 // A conservative bound on the loop as a whole.
261 const SCEV *MaxTrips = SE->getMaxBackedgeTakenCount(L);
262 if (MaxTrips != SE->getCouldNotCompute() &&
263 SE->getUnsignedRange(MaxTrips).getUnsignedMax().isIntN(
264 CountedLoopTripWidth))
267 // If this is a conditional branch to the header with the alternate path
268 // being outside the loop, we can ask questions about the execution frequency
269 // of the exit block.
270 if (L->isLoopExiting(Pred)) {
271 // This returns an exact expression only. TODO: We really only need an
272 // upper bound here, but SE doesn't expose that.
273 const SCEV *MaxExec = SE->getExitCount(L, Pred);
274 if (MaxExec != SE->getCouldNotCompute() &&
275 SE->getUnsignedRange(MaxExec).getUnsignedMax().isIntN(
276 CountedLoopTripWidth))
280 return /* not finite */ false;
283 static void scanOneBB(Instruction *start, Instruction *end,
284 std::vector<CallInst *> &calls,
285 std::set<BasicBlock *> &seen,
286 std::vector<BasicBlock *> &worklist) {
287 for (BasicBlock::iterator itr(start);
288 itr != start->getParent()->end() && itr != BasicBlock::iterator(end);
290 if (CallInst *CI = dyn_cast<CallInst>(&*itr)) {
293 // FIXME: This code does not handle invokes
294 assert(!dyn_cast<InvokeInst>(&*itr) &&
295 "support for invokes in poll code needed");
296 // Only add the successor blocks if we reach the terminator instruction
297 // without encountering end first
298 if (itr->isTerminator()) {
299 BasicBlock *BB = itr->getParent();
300 for (BasicBlock *Succ : successors(BB)) {
301 if (seen.count(Succ) == 0) {
302 worklist.push_back(Succ);
309 static void scanInlinedCode(Instruction *start, Instruction *end,
310 std::vector<CallInst *> &calls,
311 std::set<BasicBlock *> &seen) {
313 std::vector<BasicBlock *> worklist;
314 seen.insert(start->getParent());
315 scanOneBB(start, end, calls, seen, worklist);
316 while (!worklist.empty()) {
317 BasicBlock *BB = worklist.back();
319 scanOneBB(&*BB->begin(), end, calls, seen, worklist);
323 bool PlaceBackedgeSafepointsImpl::runOnLoop(Loop *L) {
324 // Loop through all loop latches (branches controlling backedges). We need
325 // to place a safepoint on every backedge (potentially).
326 // Note: In common usage, there will be only one edge due to LoopSimplify
327 // having run sometime earlier in the pipeline, but this code must be correct
328 // w.r.t. loops with multiple backedges.
329 BasicBlock *header = L->getHeader();
330 SmallVector<BasicBlock*, 16> LoopLatches;
331 L->getLoopLatches(LoopLatches);
332 for (BasicBlock *pred : LoopLatches) {
333 assert(L->contains(pred));
335 // Make a policy decision about whether this loop needs a safepoint or
336 // not. Note that this is about unburdening the optimizer in loops, not
337 // avoiding the runtime cost of the actual safepoint.
339 if (mustBeFiniteCountedLoop(L, SE, pred)) {
341 errs() << "skipping safepoint placement in finite loop\n";
345 if (CallSafepointsEnabled &&
346 containsUnconditionalCallSafepoint(L, header, pred, *DT)) {
347 // Note: This is only semantically legal since we won't do any further
348 // IPO or inlining before the actual call insertion.. If we hadn't, we
349 // might latter loose this call safepoint.
351 errs() << "skipping safepoint placement due to unconditional call\n";
357 // TODO: We can create an inner loop which runs a finite number of
358 // iterations with an outer loop which contains a safepoint. This would
359 // not help runtime performance that much, but it might help our ability to
360 // optimize the inner loop.
362 // Safepoint insertion would involve creating a new basic block (as the
363 // target of the current backedge) which does the safepoint (of all live
364 // variables) and branches to the true header
365 TerminatorInst *term = pred->getTerminator();
368 errs() << "[LSP] terminator instruction: ";
372 PollLocations.push_back(term);
378 /// Returns true if an entry safepoint is not required before this callsite in
379 /// the caller function.
380 static bool doesNotRequireEntrySafepointBefore(const CallSite &CS) {
381 Instruction *Inst = CS.getInstruction();
382 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
383 switch (II->getIntrinsicID()) {
384 case Intrinsic::experimental_gc_statepoint:
385 case Intrinsic::experimental_patchpoint_void:
386 case Intrinsic::experimental_patchpoint_i64:
387 // The can wrap an actual call which may grow the stack by an unbounded
388 // amount or run forever.
391 // Most LLVM intrinsics are things which do not expand to actual calls, or
392 // at least if they do, are leaf functions that cause only finite stack
393 // growth. In particular, the optimizer likes to form things like memsets
394 // out of stores in the original IR. Another important example is
395 // llvm.localescape which must occur in the entry block. Inserting a
396 // safepoint before it is not legal since it could push the localescape
397 // out of the entry block.
404 static Instruction *findLocationForEntrySafepoint(Function &F,
407 // Conceptually, this poll needs to be on method entry, but in
408 // practice, we place it as late in the entry block as possible. We
409 // can place it as late as we want as long as it dominates all calls
410 // that can grow the stack. This, combined with backedge polls,
411 // give us all the progress guarantees we need.
413 // hasNextInstruction and nextInstruction are used to iterate
414 // through a "straight line" execution sequence.
416 auto hasNextInstruction = [](Instruction *I) {
417 if (!I->isTerminator()) {
420 BasicBlock *nextBB = I->getParent()->getUniqueSuccessor();
421 return nextBB && (nextBB->getUniquePredecessor() != nullptr);
424 auto nextInstruction = [&hasNextInstruction](Instruction *I) {
425 assert(hasNextInstruction(I) &&
426 "first check if there is a next instruction!");
427 if (I->isTerminator()) {
428 return I->getParent()->getUniqueSuccessor()->begin();
430 return std::next(BasicBlock::iterator(I));
434 Instruction *cursor = nullptr;
435 for (cursor = F.getEntryBlock().begin(); hasNextInstruction(cursor);
436 cursor = nextInstruction(cursor)) {
438 // We need to ensure a safepoint poll occurs before any 'real' call. The
439 // easiest way to ensure finite execution between safepoints in the face of
440 // recursive and mutually recursive functions is to enforce that each take
441 // a safepoint. Additionally, we need to ensure a poll before any call
442 // which can grow the stack by an unbounded amount. This isn't required
443 // for GC semantics per se, but is a common requirement for languages
444 // which detect stack overflow via guard pages and then throw exceptions.
445 if (auto CS = CallSite(cursor)) {
446 if (doesNotRequireEntrySafepointBefore(CS))
452 assert((hasNextInstruction(cursor) || cursor->isTerminator()) &&
453 "either we stopped because of a call, or because of terminator");
458 /// Identify the list of call sites which need to be have parseable state
459 static void findCallSafepoints(Function &F,
460 std::vector<CallSite> &Found /*rval*/) {
461 assert(Found.empty() && "must be empty!");
462 for (Instruction &I : instructions(F)) {
463 Instruction *inst = &I;
464 if (isa<CallInst>(inst) || isa<InvokeInst>(inst)) {
467 // No safepoint needed or wanted
468 if (!needsStatepoint(CS)) {
477 /// Implement a unique function which doesn't require we sort the input
478 /// vector. Doing so has the effect of changing the output of a couple of
479 /// tests in ways which make them less useful in testing fused safepoints.
480 template <typename T> static void unique_unsorted(std::vector<T> &vec) {
483 vec.reserve(vec.size());
486 if (seen.insert(V).second) {
492 static const char *const GCSafepointPollName = "gc.safepoint_poll";
494 static bool isGCSafepointPoll(Function &F) {
495 return F.getName().equals(GCSafepointPollName);
498 /// Returns true if this function should be rewritten to include safepoint
499 /// polls and parseable call sites. The main point of this function is to be
500 /// an extension point for custom logic.
501 static bool shouldRewriteFunction(Function &F) {
502 // TODO: This should check the GCStrategy
504 const char *FunctionGCName = F.getGC();
505 const StringRef StatepointExampleName("statepoint-example");
506 const StringRef CoreCLRName("coreclr");
507 return (StatepointExampleName == FunctionGCName) ||
508 (CoreCLRName == FunctionGCName);
513 // TODO: These should become properties of the GCStrategy, possibly with
514 // command line overrides.
515 static bool enableEntrySafepoints(Function &F) { return !NoEntry; }
516 static bool enableBackedgeSafepoints(Function &F) { return !NoBackedge; }
517 static bool enableCallSafepoints(Function &F) { return !NoCall; }
519 // Normalize basic block to make it ready to be target of invoke statepoint.
520 // Ensure that 'BB' does not have phi nodes. It may require spliting it.
521 static BasicBlock *normalizeForInvokeSafepoint(BasicBlock *BB,
522 BasicBlock *InvokeParent) {
523 BasicBlock *ret = BB;
525 if (!BB->getUniquePredecessor()) {
526 ret = SplitBlockPredecessors(BB, InvokeParent, "");
529 // Now that 'ret' has unique predecessor we can safely remove all phi nodes
531 FoldSingleEntryPHINodes(ret);
532 assert(!isa<PHINode>(ret->begin()));
537 bool PlaceSafepoints::runOnFunction(Function &F) {
538 if (F.isDeclaration() || F.empty()) {
539 // This is a declaration, nothing to do. Must exit early to avoid crash in
540 // dom tree calculation
544 if (isGCSafepointPoll(F)) {
545 // Given we're inlining this inside of safepoint poll insertion, this
546 // doesn't make any sense. Note that we do make any contained calls
547 // parseable after we inline a poll.
551 if (!shouldRewriteFunction(F))
554 bool modified = false;
556 // In various bits below, we rely on the fact that uses are reachable from
557 // defs. When there are basic blocks unreachable from the entry, dominance
558 // and reachablity queries return non-sensical results. Thus, we preprocess
559 // the function to ensure these properties hold.
560 modified |= removeUnreachableBlocks(F);
562 // STEP 1 - Insert the safepoint polling locations. We do not need to
563 // actually insert parse points yet. That will be done for all polls and
564 // calls in a single pass.
569 SmallVector<Instruction *, 16> PollsNeeded;
570 std::vector<CallSite> ParsePointNeeded;
572 if (enableBackedgeSafepoints(F)) {
573 // Construct a pass manager to run the LoopPass backedge logic. We
574 // need the pass manager to handle scheduling all the loop passes
575 // appropriately. Doing this by hand is painful and just not worth messing
576 // with for the moment.
577 legacy::FunctionPassManager FPM(F.getParent());
578 bool CanAssumeCallSafepoints = enableCallSafepoints(F);
579 PlaceBackedgeSafepointsImpl *PBS =
580 new PlaceBackedgeSafepointsImpl(CanAssumeCallSafepoints);
584 // We preserve dominance information when inserting the poll, otherwise
585 // we'd have to recalculate this on every insert
588 auto &PollLocations = PBS->PollLocations;
590 auto OrderByBBName = [](Instruction *a, Instruction *b) {
591 return a->getParent()->getName() < b->getParent()->getName();
593 // We need the order of list to be stable so that naming ends up stable
594 // when we split edges. This makes test cases much easier to write.
595 std::sort(PollLocations.begin(), PollLocations.end(), OrderByBBName);
597 // We can sometimes end up with duplicate poll locations. This happens if
598 // a single loop is visited more than once. The fact this happens seems
599 // wrong, but it does happen for the split-backedge.ll test case.
600 PollLocations.erase(std::unique(PollLocations.begin(),
601 PollLocations.end()),
602 PollLocations.end());
604 // Insert a poll at each point the analysis pass identified
605 // The poll location must be the terminator of a loop latch block.
606 for (TerminatorInst *Term : PollLocations) {
607 // We are inserting a poll, the function is modified
611 // Split the backedge of the loop and insert the poll within that new
612 // basic block. This creates a loop with two latches per original
613 // latch (which is non-ideal), but this appears to be easier to
614 // optimize in practice than inserting the poll immediately before the
617 // Since this is a latch, at least one of the successors must dominate
618 // it. Its possible that we have a) duplicate edges to the same header
619 // and b) edges to distinct loop headers. We need to insert pools on
621 SetVector<BasicBlock *> Headers;
622 for (unsigned i = 0; i < Term->getNumSuccessors(); i++) {
623 BasicBlock *Succ = Term->getSuccessor(i);
624 if (DT.dominates(Succ, Term->getParent())) {
625 Headers.insert(Succ);
628 assert(!Headers.empty() && "poll location is not a loop latch?");
630 // The split loop structure here is so that we only need to recalculate
631 // the dominator tree once. Alternatively, we could just keep it up to
632 // date and use a more natural merged loop.
633 SetVector<BasicBlock *> SplitBackedges;
634 for (BasicBlock *Header : Headers) {
635 BasicBlock *NewBB = SplitEdge(Term->getParent(), Header, &DT);
636 PollsNeeded.push_back(NewBB->getTerminator());
637 NumBackedgeSafepoints++;
640 // Split the latch block itself, right before the terminator.
641 PollsNeeded.push_back(Term);
642 NumBackedgeSafepoints++;
647 if (enableEntrySafepoints(F)) {
648 Instruction *Location = findLocationForEntrySafepoint(F, DT);
650 // policy choice not to insert?
652 PollsNeeded.push_back(Location);
654 NumEntrySafepoints++;
658 // Now that we've identified all the needed safepoint poll locations, insert
659 // safepoint polls themselves.
660 for (Instruction *PollLocation : PollsNeeded) {
661 std::vector<CallSite> RuntimeCalls;
662 InsertSafepointPoll(PollLocation, RuntimeCalls);
663 ParsePointNeeded.insert(ParsePointNeeded.end(), RuntimeCalls.begin(),
666 PollsNeeded.clear(); // make sure we don't accidentally use
667 // The dominator tree has been invalidated by the inlining performed in the
668 // above loop. TODO: Teach the inliner how to update the dom tree?
671 if (enableCallSafepoints(F)) {
672 std::vector<CallSite> Calls;
673 findCallSafepoints(F, Calls);
674 NumCallSafepoints += Calls.size();
675 ParsePointNeeded.insert(ParsePointNeeded.end(), Calls.begin(), Calls.end());
678 // Unique the vectors since we can end up with duplicates if we scan the call
679 // site for call safepoints after we add it for entry or backedge. The
680 // only reason we need tracking at all is that some functions might have
681 // polls but not call safepoints and thus we might miss marking the runtime
682 // calls for the polls. (This is useful in test cases!)
683 unique_unsorted(ParsePointNeeded);
685 // Any parse point (no matter what source) will be handled here
687 // We're about to start modifying the function
688 if (!ParsePointNeeded.empty())
691 // Now run through and insert the safepoints, but do _NOT_ update or remove
692 // any existing uses. We have references to live variables that need to
693 // survive to the last iteration of this loop.
694 std::vector<Value *> Results;
695 Results.reserve(ParsePointNeeded.size());
696 for (size_t i = 0; i < ParsePointNeeded.size(); i++) {
697 CallSite &CS = ParsePointNeeded[i];
699 // For invoke statepoints we need to remove all phi nodes at the normal
700 // destination block.
701 // Reason for this is that we can place gc_result only after last phi node
702 // in basic block. We will get malformed code after RAUW for the
703 // gc_result if one of this phi nodes uses result from the invoke.
704 if (InvokeInst *Invoke = dyn_cast<InvokeInst>(CS.getInstruction())) {
705 normalizeForInvokeSafepoint(Invoke->getNormalDest(),
706 Invoke->getParent());
709 Value *GCResult = ReplaceWithStatepoint(CS, nullptr);
710 Results.push_back(GCResult);
712 assert(Results.size() == ParsePointNeeded.size());
714 // Adjust all users of the old call sites to use the new ones instead
715 for (size_t i = 0; i < ParsePointNeeded.size(); i++) {
716 CallSite &CS = ParsePointNeeded[i];
717 Value *GCResult = Results[i];
719 // Can not RAUW for the invoke gc result in case of phi nodes preset.
720 assert(CS.isCall() || !isa<PHINode>(cast<Instruction>(GCResult)->getParent()->begin()));
722 // Replace all uses with the new call
723 CS.getInstruction()->replaceAllUsesWith(GCResult);
726 // Now that we've handled all uses, remove the original call itself
727 // Note: The insert point can't be the deleted instruction!
728 CS.getInstruction()->eraseFromParent();
733 char PlaceBackedgeSafepointsImpl::ID = 0;
734 char PlaceSafepoints::ID = 0;
736 FunctionPass *llvm::createPlaceSafepointsPass() {
737 return new PlaceSafepoints();
740 INITIALIZE_PASS_BEGIN(PlaceBackedgeSafepointsImpl,
741 "place-backedge-safepoints-impl",
742 "Place Backedge Safepoints", false, false)
743 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
744 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
745 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
746 INITIALIZE_PASS_END(PlaceBackedgeSafepointsImpl,
747 "place-backedge-safepoints-impl",
748 "Place Backedge Safepoints", false, false)
750 INITIALIZE_PASS_BEGIN(PlaceSafepoints, "place-safepoints", "Place Safepoints",
752 INITIALIZE_PASS_END(PlaceSafepoints, "place-safepoints", "Place Safepoints",
755 static bool isGCLeafFunction(const CallSite &CS) {
756 Instruction *inst = CS.getInstruction();
757 if (isa<IntrinsicInst>(inst)) {
758 // Most LLVM intrinsics are things which can never take a safepoint.
759 // As a result, we don't need to have the stack parsable at the
760 // callsite. This is a highly useful optimization since intrinsic
761 // calls are fairly prevalent, particularly in debug builds.
765 // If this function is marked explicitly as a leaf call, we don't need to
766 // place a safepoint of it. In fact, for correctness we *can't* in many
767 // cases. Note: Indirect calls return Null for the called function,
768 // these obviously aren't runtime functions with attributes
769 // TODO: Support attributes on the call site as well.
770 const Function *F = CS.getCalledFunction();
773 F->getFnAttribute("gc-leaf-function").getValueAsString().equals("true");
781 InsertSafepointPoll(Instruction *InsertBefore,
782 std::vector<CallSite> &ParsePointsNeeded /*rval*/) {
783 BasicBlock *OrigBB = InsertBefore->getParent();
784 Module *M = InsertBefore->getModule();
785 assert(M && "must be part of a module");
787 // Inline the safepoint poll implementation - this will get all the branch,
788 // control flow, etc.. Most importantly, it will introduce the actual slow
789 // path call - where we need to insert a safepoint (parsepoint).
791 auto *F = M->getFunction(GCSafepointPollName);
792 assert(F->getType()->getElementType() ==
793 FunctionType::get(Type::getVoidTy(M->getContext()), false) &&
794 "gc.safepoint_poll declared with wrong type");
795 assert(!F->empty() && "gc.safepoint_poll must be a non-empty function");
796 CallInst *PollCall = CallInst::Create(F, "", InsertBefore);
798 // Record some information about the call site we're replacing
799 BasicBlock::iterator before(PollCall), after(PollCall);
801 if (before == OrigBB->begin()) {
807 assert(after != OrigBB->end() && "must have successor");
809 // do the actual inlining
810 InlineFunctionInfo IFI;
811 bool InlineStatus = InlineFunction(PollCall, IFI);
812 assert(InlineStatus && "inline must succeed");
813 (void)InlineStatus; // suppress warning in release-asserts
815 // Check post conditions
816 assert(IFI.StaticAllocas.empty() && "can't have allocs");
818 std::vector<CallInst *> calls; // new calls
819 std::set<BasicBlock *> BBs; // new BBs + insertee
820 // Include only the newly inserted instructions, Note: begin may not be valid
821 // if we inserted to the beginning of the basic block
822 BasicBlock::iterator start;
824 start = OrigBB->begin();
830 // If your poll function includes an unreachable at the end, that's not
831 // valid. Bugpoint likes to create this, so check for it.
832 assert(isPotentiallyReachable(&*start, &*after, nullptr, nullptr) &&
833 "malformed poll function");
835 scanInlinedCode(&*(start), &*(after), calls, BBs);
836 assert(!calls.empty() && "slow path not found for safepoint poll");
838 // Record the fact we need a parsable state at the runtime call contained in
839 // the poll function. This is required so that the runtime knows how to
840 // parse the last frame when we actually take the safepoint (i.e. execute
842 assert(ParsePointsNeeded.empty());
843 for (size_t i = 0; i < calls.size(); i++) {
845 // No safepoint needed or wanted
846 if (!needsStatepoint(calls[i])) {
850 // These are likely runtime calls. Should we assert that via calling
851 // convention or something?
852 ParsePointsNeeded.push_back(CallSite(calls[i]));
854 assert(ParsePointsNeeded.size() <= calls.size());
857 /// Replaces the given call site (Call or Invoke) with a gc.statepoint
858 /// intrinsic with an empty deoptimization arguments list. This does
859 /// NOT do explicit relocation for GC support.
860 static Value *ReplaceWithStatepoint(const CallSite &CS, /* to replace */
862 assert(CS.getInstruction()->getParent()->getParent()->getParent() &&
865 // TODO: technically, a pass is not allowed to get functions from within a
866 // function pass since it might trigger a new function addition. Refactor
867 // this logic out to the initialization of the pass. Doesn't appear to
868 // matter in practice.
870 // Then go ahead and use the builder do actually do the inserts. We insert
871 // immediately before the previous instruction under the assumption that all
872 // arguments will be available here. We can't insert afterwards since we may
873 // be replacing a terminator.
874 IRBuilder<> Builder(CS.getInstruction());
876 // Note: The gc args are not filled in at this time, that's handled by
877 // RewriteStatepointsForGC (which is currently under review).
879 // Create the statepoint given all the arguments
880 Instruction *Token = nullptr;
883 uint32_t NumPatchBytes;
885 AttributeSet OriginalAttrs = CS.getAttributes();
887 OriginalAttrs.getAttribute(AttributeSet::FunctionIndex, "statepoint-id");
888 Attribute AttrNumPatchBytes = OriginalAttrs.getAttribute(
889 AttributeSet::FunctionIndex, "statepoint-num-patch-bytes");
891 AttrBuilder AttrsToRemove;
892 bool HasID = AttrID.isStringAttribute() &&
893 !AttrID.getValueAsString().getAsInteger(10, ID);
896 AttrsToRemove.addAttribute("statepoint-id");
900 bool HasNumPatchBytes =
901 AttrNumPatchBytes.isStringAttribute() &&
902 !AttrNumPatchBytes.getValueAsString().getAsInteger(10, NumPatchBytes);
904 if (HasNumPatchBytes)
905 AttrsToRemove.addAttribute("statepoint-num-patch-bytes");
909 OriginalAttrs = OriginalAttrs.removeAttributes(
910 CS.getInstruction()->getContext(), AttributeSet::FunctionIndex,
914 CallInst *ToReplace = cast<CallInst>(CS.getInstruction());
915 CallInst *Call = Builder.CreateGCStatepointCall(
916 ID, NumPatchBytes, CS.getCalledValue(),
917 makeArrayRef(CS.arg_begin(), CS.arg_end()), None, None,
919 Call->setTailCall(ToReplace->isTailCall());
920 Call->setCallingConv(ToReplace->getCallingConv());
922 // In case if we can handle this set of attributes - set up function
923 // attributes directly on statepoint and return attributes later for
924 // gc_result intrinsic.
925 Call->setAttributes(OriginalAttrs.getFnAttributes());
929 // Put the following gc_result and gc_relocate calls immediately after
930 // the old call (which we're about to delete).
931 assert(ToReplace->getNextNode() && "not a terminator, must have next");
932 Builder.SetInsertPoint(ToReplace->getNextNode());
933 Builder.SetCurrentDebugLocation(ToReplace->getNextNode()->getDebugLoc());
934 } else if (CS.isInvoke()) {
935 InvokeInst *ToReplace = cast<InvokeInst>(CS.getInstruction());
937 // Insert the new invoke into the old block. We'll remove the old one in a
938 // moment at which point this will become the new terminator for the
940 Builder.SetInsertPoint(ToReplace->getParent());
941 InvokeInst *Invoke = Builder.CreateGCStatepointInvoke(
942 ID, NumPatchBytes, CS.getCalledValue(), ToReplace->getNormalDest(),
943 ToReplace->getUnwindDest(), makeArrayRef(CS.arg_begin(), CS.arg_end()),
944 None, None, "safepoint_token");
946 Invoke->setCallingConv(ToReplace->getCallingConv());
948 // In case if we can handle this set of attributes - set up function
949 // attributes directly on statepoint and return attributes later for
950 // gc_result intrinsic.
951 Invoke->setAttributes(OriginalAttrs.getFnAttributes());
955 // We'll insert the gc.result into the normal block
956 BasicBlock *NormalDest = ToReplace->getNormalDest();
957 // Can not insert gc.result in case of phi nodes preset.
958 // Should have removed this cases prior to running this function
959 assert(!isa<PHINode>(NormalDest->begin()));
960 Instruction *IP = &*(NormalDest->getFirstInsertionPt());
961 Builder.SetInsertPoint(IP);
963 llvm_unreachable("unexpect type of CallSite");
967 // Handle the return value of the original call - update all uses to use a
968 // gc_result hanging off the statepoint node we just inserted
970 // Only add the gc_result iff there is actually a used result
971 if (!CS.getType()->isVoidTy() && !CS.getInstruction()->use_empty()) {
972 std::string TakenName =
973 CS.getInstruction()->hasName() ? CS.getInstruction()->getName() : "";
974 CallInst *GCResult = Builder.CreateGCResult(Token, CS.getType(), TakenName);
975 GCResult->setAttributes(OriginalAttrs.getRetAttributes());
978 // No return value for the call.