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 neccessary 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/Statistic.h"
55 #include "llvm/Analysis/LoopPass.h"
56 #include "llvm/Analysis/LoopInfo.h"
57 #include "llvm/Analysis/ScalarEvolution.h"
58 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
59 #include "llvm/Analysis/CFG.h"
60 #include "llvm/Analysis/InstructionSimplify.h"
61 #include "llvm/IR/BasicBlock.h"
62 #include "llvm/IR/CallSite.h"
63 #include "llvm/IR/Dominators.h"
64 #include "llvm/IR/Function.h"
65 #include "llvm/IR/IRBuilder.h"
66 #include "llvm/IR/InstIterator.h"
67 #include "llvm/IR/Instructions.h"
68 #include "llvm/IR/Intrinsics.h"
69 #include "llvm/IR/IntrinsicInst.h"
70 #include "llvm/IR/Module.h"
71 #include "llvm/IR/Statepoint.h"
72 #include "llvm/IR/Value.h"
73 #include "llvm/IR/Verifier.h"
74 #include "llvm/Support/Debug.h"
75 #include "llvm/Support/CommandLine.h"
76 #include "llvm/Support/raw_ostream.h"
77 #include "llvm/Transforms/Scalar.h"
78 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
79 #include "llvm/Transforms/Utils/Cloning.h"
80 #include "llvm/Transforms/Utils/Local.h"
82 #define DEBUG_TYPE "safepoint-placement"
83 STATISTIC(NumEntrySafepoints, "Number of entry safepoints inserted");
84 STATISTIC(NumCallSafepoints, "Number of call safepoints inserted");
85 STATISTIC(NumBackedgeSafepoints, "Number of backedge safepoints inserted");
87 STATISTIC(CallInLoop, "Number of loops w/o safepoints due to calls in loop");
88 STATISTIC(FiniteExecution, "Number of loops w/o safepoints finite execution");
92 // Ignore oppurtunities to avoid placing safepoints on backedges, useful for
94 static cl::opt<bool> AllBackedges("spp-all-backedges", cl::Hidden,
97 /// If true, do not place backedge safepoints in counted loops.
98 static cl::opt<bool> SkipCounted("spp-counted", cl::Hidden, cl::init(true));
100 // If true, split the backedge of a loop when placing the safepoint, otherwise
101 // split the latch block itself. Both are useful to support for
102 // experimentation, but in practice, it looks like splitting the backedge
104 static cl::opt<bool> SplitBackedge("spp-split-backedge", cl::Hidden,
107 // Print tracing output
108 static cl::opt<bool> TraceLSP("spp-trace", cl::Hidden, cl::init(false));
112 /** An analysis pass whose purpose is to identify each of the backedges in
113 the function which require a safepoint poll to be inserted. */
114 struct PlaceBackedgeSafepointsImpl : public LoopPass {
117 /// The output of the pass - gives a list of each backedge (described by
118 /// pointing at the branch) which need a poll inserted.
119 std::vector<TerminatorInst *> PollLocations;
121 /// True unless we're running spp-no-calls in which case we need to disable
122 /// the call dependend placement opts.
123 bool CallSafepointsEnabled;
124 PlaceBackedgeSafepointsImpl(bool CallSafepoints = false)
125 : LoopPass(ID), CallSafepointsEnabled(CallSafepoints) {
126 initializePlaceBackedgeSafepointsImplPass(*PassRegistry::getPassRegistry());
129 bool runOnLoop(Loop *, LPPassManager &LPM) override;
131 void getAnalysisUsage(AnalysisUsage &AU) const override {
132 // needed for determining if the loop is finite
133 AU.addRequired<ScalarEvolution>();
134 // to ensure each edge has a single backedge
135 // TODO: is this still required?
136 AU.addRequiredID(LoopSimplifyID);
138 // We no longer modify the IR at all in this pass. Thus all
139 // analysis are preserved.
140 AU.setPreservesAll();
145 static cl::opt<bool> NoEntry("spp-no-entry", cl::Hidden, cl::init(false));
146 static cl::opt<bool> NoCall("spp-no-call", cl::Hidden, cl::init(false));
147 static cl::opt<bool> NoBackedge("spp-no-backedge", cl::Hidden, cl::init(false));
150 struct PlaceSafepoints : public ModulePass {
151 static char ID; // Pass identification, replacement for typeid
153 PlaceSafepoints() : ModulePass(ID) {
154 initializePlaceSafepointsPass(*PassRegistry::getPassRegistry());
156 bool runOnModule(Module &M) override {
157 bool modified = false;
158 for (Function &F : M) {
159 modified |= runOnFunction(F);
163 bool runOnFunction(Function &F);
165 void getAnalysisUsage(AnalysisUsage &AU) const override {
166 // We modify the graph wholesale (inlining, block insertion, etc). We
167 // preserve nothing at the moment. We could potentially preserve dom tree
168 // if that was worth doing
173 // Insert a safepoint poll immediately before the given instruction. Does
174 // not handle the parsability of state at the runtime call, that's the
177 InsertSafepointPoll(DominatorTree &DT, Instruction *after,
178 std::vector<CallSite> &ParsePointsNeeded /*rval*/);
180 static bool isGCLeafFunction(const CallSite &CS);
182 static bool needsStatepoint(const CallSite &CS) {
183 if (isGCLeafFunction(CS))
186 CallInst *call = cast<CallInst>(CS.getInstruction());
187 if (call->isInlineAsm())
190 if (isStatepoint(CS) || isGCRelocate(CS) || isGCResult(CS)) {
196 static Value *ReplaceWithStatepoint(const CallSite &CS, Pass *P);
198 /// Returns true if this loop is known to contain a call safepoint which
199 /// must unconditionally execute on any iteration of the loop which returns
200 /// to the loop header via an edge from Pred. Returns a conservative correct
201 /// answer; i.e. false is always valid.
202 static bool containsUnconditionalCallSafepoint(Loop *L, BasicBlock *Header,
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 substaintially more occurences 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?");
217 BasicBlock *Current = Pred;
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
224 // unconditional poll. In practice, this is only a theoretical concern
225 // since we don't have any methods with conditional-only safepoint
227 if (needsStatepoint(CS))
231 if (Current == Header)
233 Current = DT.getNode(Current)->getIDom()->getBlock();
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.
243 static bool mustBeFiniteCountedLoop(Loop *L, ScalarEvolution *SE,
245 // Only used when SkipCounted is off
246 const unsigned upperTripBound = 8192;
248 // A conservative bound on the loop as a whole.
249 const SCEV *MaxTrips = SE->getMaxBackedgeTakenCount(L);
250 if (MaxTrips != SE->getCouldNotCompute()) {
251 if (SE->getUnsignedRange(MaxTrips).getUnsignedMax().ult(upperTripBound))
254 SE->getUnsignedRange(MaxTrips).getUnsignedMax().isIntN(32))
258 // If this is a conditional branch to the header with the alternate path
259 // being outside the loop, we can ask questions about the execution frequency
260 // of the exit block.
261 if (L->isLoopExiting(Pred)) {
262 // This returns an exact expression only. TODO: We really only need an
263 // upper bound here, but SE doesn't expose that.
264 const SCEV *MaxExec = SE->getExitCount(L, Pred);
265 if (MaxExec != SE->getCouldNotCompute()) {
266 if (SE->getUnsignedRange(MaxExec).getUnsignedMax().ult(upperTripBound))
269 SE->getUnsignedRange(MaxExec).getUnsignedMax().isIntN(32))
274 return /* not finite */ false;
277 static void scanOneBB(Instruction *start, Instruction *end,
278 std::vector<CallInst *> &calls,
279 std::set<BasicBlock *> &seen,
280 std::vector<BasicBlock *> &worklist) {
281 for (BasicBlock::iterator itr(start);
282 itr != start->getParent()->end() && itr != BasicBlock::iterator(end);
284 if (CallInst *CI = dyn_cast<CallInst>(&*itr)) {
287 // FIXME: This code does not handle invokes
288 assert(!dyn_cast<InvokeInst>(&*itr) &&
289 "support for invokes in poll code needed");
290 // Only add the successor blocks if we reach the terminator instruction
291 // without encountering end first
292 if (itr->isTerminator()) {
293 BasicBlock *BB = itr->getParent();
294 for (BasicBlock *Succ : successors(BB)) {
295 if (seen.count(Succ) == 0) {
296 worklist.push_back(Succ);
303 static void scanInlinedCode(Instruction *start, Instruction *end,
304 std::vector<CallInst *> &calls,
305 std::set<BasicBlock *> &seen) {
307 std::vector<BasicBlock *> worklist;
308 seen.insert(start->getParent());
309 scanOneBB(start, end, calls, seen, worklist);
310 while (!worklist.empty()) {
311 BasicBlock *BB = worklist.back();
313 scanOneBB(&*BB->begin(), end, calls, seen, worklist);
317 bool PlaceBackedgeSafepointsImpl::runOnLoop(Loop *L, LPPassManager &LPM) {
318 ScalarEvolution *SE = &getAnalysis<ScalarEvolution>();
320 // Loop through all predecessors of the loop header and identify all
321 // backedges. We need to place a safepoint on every backedge (potentially).
322 // Note: Due to LoopSimplify there should only be one. Assert? Or can we
324 BasicBlock *header = L->getHeader();
326 // TODO: Use the analysis pass infrastructure for this. There is no reason
327 // to recalculate this here.
329 DT.recalculate(*header->getParent());
331 bool modified = false;
332 for (BasicBlock *pred : predecessors(header)) {
333 if (!L->contains(pred)) {
334 // This is not a backedge, it's coming from outside the loop
338 // Make a policy decision about whether this loop needs a safepoint or
339 // not. Note that this is about unburdening the optimizer in loops, not
340 // avoiding the runtime cost of the actual safepoint.
342 if (mustBeFiniteCountedLoop(L, SE, pred)) {
344 errs() << "skipping safepoint placement in finite loop\n";
348 if (CallSafepointsEnabled &&
349 containsUnconditionalCallSafepoint(L, header, pred, DT)) {
350 // Note: This is only semantically legal since we won't do any further
351 // IPO or inlining before the actual call insertion.. If we hadn't, we
352 // might latter loose this call safepoint.
354 errs() << "skipping safepoint placement due to unconditional call\n";
360 // TODO: We can create an inner loop which runs a finite number of
361 // iterations with an outer loop which contains a safepoint. This would
362 // not help runtime performance that much, but it might help our ability to
363 // optimize the inner loop.
365 // We're unconditionally going to modify this loop.
368 // Safepoint insertion would involve creating a new basic block (as the
369 // target of the current backedge) which does the safepoint (of all live
370 // variables) and branches to the true header
371 TerminatorInst *term = pred->getTerminator();
374 errs() << "[LSP] terminator instruction: ";
378 PollLocations.push_back(term);
384 static Instruction *findLocationForEntrySafepoint(Function &F,
387 // Conceptually, this poll needs to be on method entry, but in
388 // practice, we place it as late in the entry block as possible. We
389 // can place it as late as we want as long as it dominates all calls
390 // that can grow the stack. This, combined with backedge polls,
391 // give us all the progress guarantees we need.
393 // Due to the way the frontend generates IR, we may have a couple of initial
394 // basic blocks before the first bytecode. These will be single-entry
395 // single-exit blocks which conceptually are just part of the first 'real
396 // basic block'. Since we don't have deopt state until the first bytecode,
397 // walk forward until we've found the first unconditional branch or merge.
399 // hasNextInstruction and nextInstruction are used to iterate
400 // through a "straight line" execution sequence.
402 auto hasNextInstruction = [](Instruction *I) {
403 if (!I->isTerminator()) {
406 BasicBlock *nextBB = I->getParent()->getUniqueSuccessor();
407 return nextBB && (nextBB->getUniquePredecessor() != nullptr);
410 auto nextInstruction = [&hasNextInstruction](Instruction *I) {
411 assert(hasNextInstruction(I) &&
412 "first check if there is a next instruction!");
413 if (I->isTerminator()) {
414 return I->getParent()->getUniqueSuccessor()->begin();
416 return std::next(BasicBlock::iterator(I));
420 Instruction *cursor = nullptr;
421 for (cursor = F.getEntryBlock().begin(); hasNextInstruction(cursor);
422 cursor = nextInstruction(cursor)) {
424 // We need to stop going forward as soon as we see a call that can
425 // grow the stack (i.e. the call target has a non-zero frame
427 if (CallSite(cursor)) {
428 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(cursor)) {
429 // llvm.assume(...) are not really calls.
430 if (II->getIntrinsicID() == Intrinsic::assume) {
433 // llvm.frameescape() intrinsic is not a real call. The intrinsic can
434 // exist only in the entry block.
435 // Inserting a statepoint before llvm.frameescape() may split the
436 // entry block, and push the intrinsic out of the entry block.
437 if (II->getIntrinsicID() == Intrinsic::frameescape) {
445 assert((hasNextInstruction(cursor) || cursor->isTerminator()) &&
446 "either we stopped because of a call, or because of terminator");
448 if (cursor->isTerminator()) {
452 BasicBlock *BB = cursor->getParent();
453 SplitBlock(BB, cursor, nullptr);
455 // Note: SplitBlock modifies the DT. Simply passing a Pass (which is a
456 // module pass) is not enough.
459 // SplitBlock updates the DT
460 DEBUG(DT.verifyDomTree());
462 return BB->getTerminator();
465 /// Identify the list of call sites which need to be have parseable state
466 static void findCallSafepoints(Function &F,
467 std::vector<CallSite> &Found /*rval*/) {
468 assert(Found.empty() && "must be empty!");
469 for (Instruction &I : inst_range(F)) {
470 Instruction *inst = &I;
471 if (isa<CallInst>(inst) || isa<InvokeInst>(inst)) {
474 // No safepoint needed or wanted
475 if (!needsStatepoint(CS)) {
484 /// Implement a unique function which doesn't require we sort the input
485 /// vector. Doing so has the effect of changing the output of a couple of
486 /// tests in ways which make them less useful in testing fused safepoints.
487 template <typename T> static void unique_unsorted(std::vector<T> &vec) {
490 vec.reserve(vec.size());
493 if (seen.insert(V).second) {
499 static std::string GCSafepointPollName("gc.safepoint_poll");
501 static bool isGCSafepointPoll(Function &F) {
502 return F.getName().equals(GCSafepointPollName);
505 /// Returns true if this function should be rewritten to include safepoint
506 /// polls and parseable call sites. The main point of this function is to be
507 /// an extension point for custom logic.
508 static bool shouldRewriteFunction(Function &F) {
509 // TODO: This should check the GCStrategy
511 const std::string StatepointExampleName("statepoint-example");
512 return StatepointExampleName == F.getGC();
517 // TODO: These should become properties of the GCStrategy, possibly with
518 // command line overrides.
519 static bool enableEntrySafepoints(Function &F) { return !NoEntry; }
520 static bool enableBackedgeSafepoints(Function &F) { return !NoBackedge; }
521 static bool enableCallSafepoints(Function &F) { return !NoCall; }
523 // Normalize basic block to make it ready to be target of invoke statepoint.
524 // Ensure that 'BB' does not have phi nodes. It may require spliting it.
525 static BasicBlock *normalizeForInvokeSafepoint(BasicBlock *BB,
526 BasicBlock *InvokeParent) {
527 BasicBlock *ret = BB;
529 if (!BB->getUniquePredecessor()) {
530 ret = SplitBlockPredecessors(BB, InvokeParent, "");
533 // Now that 'ret' has unique predecessor we can safely remove all phi nodes
535 FoldSingleEntryPHINodes(ret);
536 assert(!isa<PHINode>(ret->begin()));
541 bool PlaceSafepoints::runOnFunction(Function &F) {
542 if (F.isDeclaration() || F.empty()) {
543 // This is a declaration, nothing to do. Must exit early to avoid crash in
544 // dom tree calculation
548 if (isGCSafepointPoll(F)) {
549 // Given we're inlining this inside of safepoint poll insertion, this
550 // doesn't make any sense. Note that we do make any contained calls
551 // parseable after we inline a poll.
555 if (!shouldRewriteFunction(F))
558 bool modified = false;
560 // In various bits below, we rely on the fact that uses are reachable from
561 // defs. When there are basic blocks unreachable from the entry, dominance
562 // and reachablity queries return non-sensical results. Thus, we preprocess
563 // the function to ensure these properties hold.
564 modified |= removeUnreachableBlocks(F);
566 // STEP 1 - Insert the safepoint polling locations. We do not need to
567 // actually insert parse points yet. That will be done for all polls and
568 // calls in a single pass.
570 // Note: With the migration, we need to recompute this for each 'pass'. Once
571 // we merge these, we'll do it once before the analysis
574 std::vector<CallSite> ParsePointNeeded;
576 if (enableBackedgeSafepoints(F)) {
577 // Construct a pass manager to run the LoopPass backedge logic. We
578 // need the pass manager to handle scheduling all the loop passes
579 // appropriately. Doing this by hand is painful and just not worth messing
580 // with for the moment.
581 legacy::FunctionPassManager FPM(F.getParent());
582 bool CanAssumeCallSafepoints = enableCallSafepoints(F);
583 PlaceBackedgeSafepointsImpl *PBS =
584 new PlaceBackedgeSafepointsImpl(CanAssumeCallSafepoints);
586 // Note: While the analysis pass itself won't modify the IR, LoopSimplify
587 // (which it depends on) may. i.e. analysis must be recalculated after run
590 // We preserve dominance information when inserting the poll, otherwise
591 // we'd have to recalculate this on every insert
594 // Insert a poll at each point the analysis pass identified
595 for (size_t i = 0; i < PBS->PollLocations.size(); i++) {
596 // We are inserting a poll, the function is modified
599 // The poll location must be the terminator of a loop latch block.
600 TerminatorInst *Term = PBS->PollLocations[i];
602 std::vector<CallSite> ParsePoints;
604 // Split the backedge of the loop and insert the poll within that new
605 // basic block. This creates a loop with two latches per original
606 // latch (which is non-ideal), but this appears to be easier to
607 // optimize in practice than inserting the poll immediately before the
610 // Since this is a latch, at least one of the successors must dominate
611 // it. Its possible that we have a) duplicate edges to the same header
612 // and b) edges to distinct loop headers. We need to insert pools on
613 // each. (Note: This still relies on LoopSimplify.)
614 DenseSet<BasicBlock *> Headers;
615 for (unsigned i = 0; i < Term->getNumSuccessors(); i++) {
616 BasicBlock *Succ = Term->getSuccessor(i);
617 if (DT.dominates(Succ, Term->getParent())) {
618 Headers.insert(Succ);
621 assert(!Headers.empty() && "poll location is not a loop latch?");
623 // The split loop structure here is so that we only need to recalculate
624 // the dominator tree once. Alternatively, we could just keep it up to
625 // date and use a more natural merged loop.
626 DenseSet<BasicBlock *> SplitBackedges;
627 for (BasicBlock *Header : Headers) {
628 BasicBlock *NewBB = SplitEdge(Term->getParent(), Header, nullptr);
629 SplitBackedges.insert(NewBB);
632 for (BasicBlock *NewBB : SplitBackedges) {
633 InsertSafepointPoll(DT, NewBB->getTerminator(), ParsePoints);
634 NumBackedgeSafepoints++;
638 // Split the latch block itself, right before the terminator.
639 InsertSafepointPoll(DT, Term, ParsePoints);
640 NumBackedgeSafepoints++;
643 // Record the parse points for later use
644 ParsePointNeeded.insert(ParsePointNeeded.end(), ParsePoints.begin(),
649 if (enableEntrySafepoints(F)) {
651 Instruction *term = findLocationForEntrySafepoint(F, DT);
653 // policy choice not to insert?
655 std::vector<CallSite> RuntimeCalls;
656 InsertSafepointPoll(DT, term, RuntimeCalls);
658 NumEntrySafepoints++;
659 ParsePointNeeded.insert(ParsePointNeeded.end(), RuntimeCalls.begin(),
664 if (enableCallSafepoints(F)) {
666 std::vector<CallSite> Calls;
667 findCallSafepoints(F, Calls);
668 NumCallSafepoints += Calls.size();
669 ParsePointNeeded.insert(ParsePointNeeded.end(), Calls.begin(), Calls.end());
672 // Unique the vectors since we can end up with duplicates if we scan the call
673 // site for call safepoints after we add it for entry or backedge. The
674 // only reason we need tracking at all is that some functions might have
675 // polls but not call safepoints and thus we might miss marking the runtime
676 // calls for the polls. (This is useful in test cases!)
677 unique_unsorted(ParsePointNeeded);
679 // Any parse point (no matter what source) will be handled here
680 DT.recalculate(F); // Needed?
682 // We're about to start modifying the function
683 if (!ParsePointNeeded.empty())
686 // Now run through and insert the safepoints, but do _NOT_ update or remove
687 // any existing uses. We have references to live variables that need to
688 // survive to the last iteration of this loop.
689 std::vector<Value *> Results;
690 Results.reserve(ParsePointNeeded.size());
691 for (size_t i = 0; i < ParsePointNeeded.size(); i++) {
692 CallSite &CS = ParsePointNeeded[i];
694 // For invoke statepoints we need to remove all phi nodes at the normal
695 // destination block.
696 // Reason for this is that we can place gc_result only after last phi node
697 // in basic block. We will get malformed code after RAUW for the
698 // gc_result if one of this phi nodes uses result from the invoke.
699 if (InvokeInst *Invoke = dyn_cast<InvokeInst>(CS.getInstruction())) {
700 normalizeForInvokeSafepoint(Invoke->getNormalDest(),
701 Invoke->getParent());
704 Value *GCResult = ReplaceWithStatepoint(CS, nullptr);
705 Results.push_back(GCResult);
707 assert(Results.size() == ParsePointNeeded.size());
709 // Adjust all users of the old call sites to use the new ones instead
710 for (size_t i = 0; i < ParsePointNeeded.size(); i++) {
711 CallSite &CS = ParsePointNeeded[i];
712 Value *GCResult = Results[i];
714 // Can not RAUW for the gc result in case of phi nodes preset.
715 assert(!isa<PHINode>(cast<Instruction>(GCResult)->getParent()->begin()));
717 // Replace all uses with the new call
718 CS.getInstruction()->replaceAllUsesWith(GCResult);
721 // Now that we've handled all uses, remove the original call itself
722 // Note: The insert point can't be the deleted instruction!
723 CS.getInstruction()->eraseFromParent();
728 char PlaceBackedgeSafepointsImpl::ID = 0;
729 char PlaceSafepoints::ID = 0;
731 ModulePass *llvm::createPlaceSafepointsPass() { return new PlaceSafepoints(); }
733 INITIALIZE_PASS_BEGIN(PlaceBackedgeSafepointsImpl,
734 "place-backedge-safepoints-impl",
735 "Place Backedge Safepoints", false, false)
736 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
737 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
738 INITIALIZE_PASS_END(PlaceBackedgeSafepointsImpl,
739 "place-backedge-safepoints-impl",
740 "Place Backedge Safepoints", false, false)
742 INITIALIZE_PASS_BEGIN(PlaceSafepoints, "place-safepoints", "Place Safepoints",
744 INITIALIZE_PASS_END(PlaceSafepoints, "place-safepoints", "Place Safepoints",
747 static bool isGCLeafFunction(const CallSite &CS) {
748 Instruction *inst = CS.getInstruction();
749 if (isa<IntrinsicInst>(inst)) {
750 // Most LLVM intrinsics are things which can never take a safepoint.
751 // As a result, we don't need to have the stack parsable at the
752 // callsite. This is a highly useful optimization since intrinsic
753 // calls are fairly prevelent, particularly in debug builds.
757 // If this function is marked explicitly as a leaf call, we don't need to
758 // place a safepoint of it. In fact, for correctness we *can't* in many
759 // cases. Note: Indirect calls return Null for the called function,
760 // these obviously aren't runtime functions with attributes
761 // TODO: Support attributes on the call site as well.
762 const Function *F = CS.getCalledFunction();
765 F->getFnAttribute("gc-leaf-function").getValueAsString().equals("true");
773 InsertSafepointPoll(DominatorTree &DT, Instruction *term,
774 std::vector<CallSite> &ParsePointsNeeded /*rval*/) {
775 Module *M = term->getParent()->getParent()->getParent();
778 // Inline the safepoint poll implementation - this will get all the branch,
779 // control flow, etc.. Most importantly, it will introduce the actual slow
780 // path call - where we need to insert a safepoint (parsepoint).
781 FunctionType *ftype =
782 FunctionType::get(Type::getVoidTy(M->getContext()), false);
783 assert(ftype && "null?");
784 // Note: This cast can fail if there's a function of the same name with a
785 // different type inserted previously
787 dyn_cast<Function>(M->getOrInsertFunction("gc.safepoint_poll", ftype));
788 assert(F && "void @gc.safepoint_poll() must be defined");
789 assert(!F->empty() && "gc.safepoint_poll must be a non-empty function");
790 CallInst *poll = CallInst::Create(F, "", term);
792 // Record some information about the call site we're replacing
793 BasicBlock *OrigBB = term->getParent();
794 BasicBlock::iterator before(poll), after(poll);
796 if (before == term->getParent()->begin()) {
802 assert(after != poll->getParent()->end() && "must have successor");
803 assert(DT.dominates(before, after) && "trivially true");
805 // do the actual inlining
806 InlineFunctionInfo IFI;
807 bool inlineStatus = InlineFunction(poll, IFI);
808 assert(inlineStatus && "inline must succeed");
809 (void)inlineStatus; // suppress warning in release-asserts
811 // Check post conditions
812 assert(IFI.StaticAllocas.empty() && "can't have allocs");
814 std::vector<CallInst *> calls; // new calls
815 std::set<BasicBlock *> BBs; // new BBs + insertee
816 // Include only the newly inserted instructions, Note: begin may not be valid
817 // if we inserted to the beginning of the basic block
818 BasicBlock::iterator start;
820 start = OrigBB->begin();
826 // If your poll function includes an unreachable at the end, that's not
827 // valid. Bugpoint likes to create this, so check for it.
828 assert(isPotentiallyReachable(&*start, &*after, nullptr, nullptr) &&
829 "malformed poll function");
831 scanInlinedCode(&*(start), &*(after), calls, BBs);
833 // Recompute since we've invalidated cached data. Conceptually we
834 // shouldn't need to do this, but implementation wise we appear to. Needed
835 // so we can insert safepoints correctly.
836 // TODO: update more cheaply
837 DT.recalculate(*after->getParent()->getParent());
839 assert(!calls.empty() && "slow path not found for safepoint poll");
841 // Record the fact we need a parsable state at the runtime call contained in
842 // the poll function. This is required so that the runtime knows how to
843 // parse the last frame when we actually take the safepoint (i.e. execute
845 assert(ParsePointsNeeded.empty());
846 for (size_t i = 0; i < calls.size(); i++) {
848 // No safepoint needed or wanted
849 if (!needsStatepoint(calls[i])) {
853 // These are likely runtime calls. Should we assert that via calling
854 // convention or something?
855 ParsePointsNeeded.push_back(CallSite(calls[i]));
857 assert(ParsePointsNeeded.size() <= calls.size());
860 /// Replaces the given call site (Call or Invoke) with a gc.statepoint
861 /// intrinsic with an empty deoptimization arguments list. This does
862 /// NOT do explicit relocation for GC support.
863 static Value *ReplaceWithStatepoint(const CallSite &CS, /* to replace */
865 assert(CS.getInstruction()->getParent()->getParent()->getParent() &&
868 // TODO: technically, a pass is not allowed to get functions from within a
869 // function pass since it might trigger a new function addition. Refactor
870 // this logic out to the initialization of the pass. Doesn't appear to
871 // matter in practice.
873 // Then go ahead and use the builder do actually do the inserts. We insert
874 // immediately before the previous instruction under the assumption that all
875 // arguments will be available here. We can't insert afterwards since we may
876 // be replacing a terminator.
877 IRBuilder<> Builder(CS.getInstruction());
879 // Note: The gc args are not filled in at this time, that's handled by
880 // RewriteStatepointsForGC (which is currently under review).
882 // Create the statepoint given all the arguments
883 Instruction *Token = nullptr;
884 AttributeSet OriginalAttrs;
887 CallInst *ToReplace = cast<CallInst>(CS.getInstruction());
888 CallInst *Call = Builder.CreateGCStatepointCall(
889 CS.getCalledValue(), makeArrayRef(CS.arg_begin(), CS.arg_end()), None,
890 None, "safepoint_token");
891 Call->setTailCall(ToReplace->isTailCall());
892 Call->setCallingConv(ToReplace->getCallingConv());
894 // Before we have to worry about GC semantics, all attributes are legal
895 // TODO: handle param attributes
896 OriginalAttrs = ToReplace->getAttributes();
898 // In case if we can handle this set of attributes - set up function
899 // attributes directly on statepoint and return attributes later for
900 // gc_result intrinsic.
901 Call->setAttributes(OriginalAttrs.getFnAttributes());
905 // Put the following gc_result and gc_relocate calls immediately after the
906 // the old call (which we're about to delete).
907 assert(ToReplace->getNextNode() && "not a terminator, must have next");
908 Builder.SetInsertPoint(ToReplace->getNextNode());
909 Builder.SetCurrentDebugLocation(ToReplace->getNextNode()->getDebugLoc());
910 } else if (CS.isInvoke()) {
911 InvokeInst *ToReplace = cast<InvokeInst>(CS.getInstruction());
913 // Insert the new invoke into the old block. We'll remove the old one in a
914 // moment at which point this will become the new terminator for the
916 Builder.SetInsertPoint(ToReplace->getParent());
917 InvokeInst *Invoke = Builder.CreateGCStatepointInvoke(
918 CS.getCalledValue(), ToReplace->getNormalDest(),
919 ToReplace->getUnwindDest(), makeArrayRef(CS.arg_begin(), CS.arg_end()),
920 Builder.getInt32(0), None, "safepoint_token");
922 // Currently we will fail on parameter attributes and on certain
923 // function attributes.
924 OriginalAttrs = ToReplace->getAttributes();
926 // In case if we can handle this set of attributes - set up function
927 // attributes directly on statepoint and return attributes later for
928 // gc_result intrinsic.
929 Invoke->setAttributes(OriginalAttrs.getFnAttributes());
933 // We'll insert the gc.result into the normal block
934 BasicBlock *NormalDest = ToReplace->getNormalDest();
935 // Can not insert gc.result in case of phi nodes preset.
936 // Should have removed this cases prior to runnning this function
937 assert(!isa<PHINode>(NormalDest->begin()));
938 Instruction *IP = &*(NormalDest->getFirstInsertionPt());
939 Builder.SetInsertPoint(IP);
941 llvm_unreachable("unexpect type of CallSite");
945 // Handle the return value of the original call - update all uses to use a
946 // gc_result hanging off the statepoint node we just inserted
948 // Only add the gc_result iff there is actually a used result
949 if (!CS.getType()->isVoidTy() && !CS.getInstruction()->use_empty()) {
950 std::string TakenName =
951 CS.getInstruction()->hasName() ? CS.getInstruction()->getName() : "";
952 CallInst *GCResult = Builder.CreateGCResult(Token, CS.getType(), TakenName);
953 GCResult->setAttributes(OriginalAttrs.getRetAttributes());
956 // No return value for the call.