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.
14 // This pass will insert:
15 // - Call parse points ("call safepoints") for any call which may need to
16 // reach a safepoint during the execution of the callee function.
17 // - Backedge safepoint polls and entry safepoint polls to ensure that
18 // executing code reaches a safepoint poll in a finite amount of time.
19 // - We do not currently support return statepoints, but adding them would not
20 // be hard. They are not required for correctness - entry safepoints are an
21 // alternative - but some GCs may prefer them. Patches welcome.
23 // There are restrictions on the IR accepted. We require that:
24 // - Pointer values may not be cast to integers and back.
25 // - Pointers to GC objects must be tagged with address space #1
26 // - Pointers loaded from the heap or global variables must refer to the
27 // base of an object. In practice, interior pointers are probably fine as
28 // long as your GC can handle them, but exterior pointers loaded to from the
29 // heap or globals are explicitly unsupported at this time.
31 // In addition to these fundemental limitations, we currently do not support:
32 // - use of indirectbr (in loops which need backedge safepoints)
33 // - aggregate types which contain pointers to GC objects
34 // - constant pointers to GC objects (other than null)
37 // Patches welcome for the later class of items.
39 // This code is organized in two key concepts:
40 // - "parse point" - at these locations (all calls in the current
41 // implementation), the garbage collector must be able to inspect
42 // and modify all pointers to garbage collected objects. The objects
43 // may be arbitrarily relocated and thus the pointers may be modified.
44 // - "poll" - this is a location where the compiled code needs to
45 // check (or poll) if the running thread needs to collaborate with
46 // the garbage collector by taking some action. In this code, the
47 // checking condition and action are abstracted via a frontend
48 // provided "safepoint_poll" function.
50 //===----------------------------------------------------------------------===//
52 #include "llvm/Pass.h"
53 #include "llvm/PassManager.h"
54 #include "llvm/ADT/SetOperations.h"
55 #include "llvm/ADT/Statistic.h"
56 #include "llvm/Analysis/LoopPass.h"
57 #include "llvm/Analysis/LoopInfo.h"
58 #include "llvm/Analysis/ScalarEvolution.h"
59 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
60 #include "llvm/Analysis/CFG.h"
61 #include "llvm/Analysis/InstructionSimplify.h"
62 #include "llvm/IR/BasicBlock.h"
63 #include "llvm/IR/CallSite.h"
64 #include "llvm/IR/Dominators.h"
65 #include "llvm/IR/Function.h"
66 #include "llvm/IR/IRBuilder.h"
67 #include "llvm/IR/InstIterator.h"
68 #include "llvm/IR/Instructions.h"
69 #include "llvm/IR/Intrinsics.h"
70 #include "llvm/IR/IntrinsicInst.h"
71 #include "llvm/IR/Module.h"
72 #include "llvm/IR/Statepoint.h"
73 #include "llvm/IR/Value.h"
74 #include "llvm/IR/Verifier.h"
75 #include "llvm/Support/Debug.h"
76 #include "llvm/Support/CommandLine.h"
77 #include "llvm/Support/raw_ostream.h"
78 #include "llvm/Transforms/Scalar.h"
79 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
80 #include "llvm/Transforms/Utils/Cloning.h"
81 #include "llvm/Transforms/Utils/Local.h"
83 #define DEBUG_TYPE "safepoint-placement"
84 STATISTIC(NumEntrySafepoints, "Number of entry safepoints inserted");
85 STATISTIC(NumCallSafepoints, "Number of call safepoints inserted");
86 STATISTIC(NumBackedgeSafepoints, "Number of backedge safepoints inserted");
88 STATISTIC(CallInLoop, "Number of loops w/o safepoints due to calls in loop");
89 STATISTIC(FiniteExecution, "Number of loops w/o safepoints finite execution");
93 // Ignore oppurtunities to avoid placing safepoints on backedges, useful for
95 static cl::opt<bool> AllBackedges("spp-all-backedges", cl::init(false));
97 /// If true, do not place backedge safepoints in counted loops.
98 static cl::opt<bool> SkipCounted("spp-counted", 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::init(false));
106 // Print tracing output
107 cl::opt<bool> TraceLSP("spp-trace", cl::init(false));
111 /** An analysis pass whose purpose is to identify each of the backedges in
112 the function which require a safepoint poll to be inserted. */
113 struct PlaceBackedgeSafepointsImpl : public LoopPass {
116 /// The output of the pass - gives a list of each backedge (described by
117 /// pointing at the branch) which need a poll inserted.
118 std::vector<TerminatorInst *> PollLocations;
120 /// True unless we're running spp-no-calls in which case we need to disable
121 /// the call dependend placement opts.
122 bool CallSafepointsEnabled;
123 PlaceBackedgeSafepointsImpl(bool CallSafepoints = false)
124 : LoopPass(ID), CallSafepointsEnabled(CallSafepoints) {
125 initializePlaceBackedgeSafepointsImplPass(
126 *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::init(false));
146 static cl::opt<bool> NoCall("spp-no-call", cl::init(false));
147 static cl::opt<bool> NoBackedge("spp-no-backedge", cl::init(false));
150 struct PlaceSafepoints : public ModulePass {
151 static char ID; // Pass identification, replacement for typeid
153 bool EnableEntrySafepoints;
154 bool EnableBackedgeSafepoints;
155 bool EnableCallSafepoints;
157 PlaceSafepoints() : ModulePass(ID) {
158 initializePlaceSafepointsPass(*PassRegistry::getPassRegistry());
159 EnableEntrySafepoints = !NoEntry;
160 EnableBackedgeSafepoints = !NoBackedge;
161 EnableCallSafepoints = !NoCall;
163 bool runOnModule(Module &M) override {
164 bool modified = false;
165 for (Function &F : M) {
166 modified |= runOnFunction(F);
170 bool runOnFunction(Function &F);
172 void getAnalysisUsage(AnalysisUsage &AU) const override {
173 // We modify the graph wholesale (inlining, block insertion, etc). We
174 // preserve nothing at the moment. We could potentially preserve dom tree
175 // if that was worth doing
180 // Insert a safepoint poll immediately before the given instruction. Does
181 // not handle the parsability of state at the runtime call, that's the
183 static void InsertSafepointPoll(DominatorTree &DT, Instruction *after,
184 std::vector<CallSite> &ParsePointsNeeded /*rval*/);
186 static bool isGCLeafFunction(const CallSite &CS);
188 static bool needsStatepoint(const CallSite &CS) {
189 if (isGCLeafFunction(CS))
192 CallInst *call = cast<CallInst>(CS.getInstruction());
193 if (call->isInlineAsm())
196 if (isStatepoint(CS) || isGCRelocate(CS) || isGCResult(CS)) {
202 static Value *ReplaceWithStatepoint(const CallSite &CS,
205 /// Returns true if this loop is known to contain a call safepoint which
206 /// must unconditionally execute on any iteration of the loop which returns
207 /// to the loop header via an edge from Pred. Returns a conservative correct
208 /// answer; i.e. false is always valid.
209 static bool containsUnconditionalCallSafepoint(Loop *L, BasicBlock *Header,
212 // In general, we're looking for any cut of the graph which ensures
213 // there's a call safepoint along every edge between Header and Pred.
214 // For the moment, we look only for the 'cuts' that consist of a single call
215 // instruction in a block which is dominated by the Header and dominates the
216 // loop latch (Pred) block. Somewhat surprisingly, walking the entire chain
217 // of such dominating blocks gets substaintially more occurences than just
218 // checking the Pred and Header blocks themselves. This may be due to the
219 // density of loop exit conditions caused by range and null checks.
220 // TODO: structure this as an analysis pass, cache the result for subloops,
221 // avoid dom tree recalculations
222 assert(DT.dominates(Header, Pred) && "loop latch not dominated by header?");
224 BasicBlock *Current = Pred;
226 for (Instruction &I : *Current) {
227 if (CallSite CS = &I)
228 // Note: Technically, needing a safepoint isn't quite the right
229 // condition here. We should instead be checking if the target method
231 // unconditional poll. In practice, this is only a theoretical concern
232 // since we don't have any methods with conditional-only safepoint
234 if (needsStatepoint(CS))
238 if (Current == Header)
240 Current = DT.getNode(Current)->getIDom()->getBlock();
246 /// Returns true if this loop is known to terminate in a finite number of
247 /// iterations. Note that this function may return false for a loop which
248 /// does actual terminate in a finite constant number of iterations due to
249 /// conservatism in the analysis.
250 static bool mustBeFiniteCountedLoop(Loop *L, ScalarEvolution *SE,
252 // Only used when SkipCounted is off
253 const unsigned upperTripBound = 8192;
255 // A conservative bound on the loop as a whole.
256 const SCEV *MaxTrips = SE->getMaxBackedgeTakenCount(L);
257 if (MaxTrips != SE->getCouldNotCompute()) {
258 if (SE->getUnsignedRange(MaxTrips).getUnsignedMax().ult(upperTripBound))
261 SE->getUnsignedRange(MaxTrips).getUnsignedMax().isIntN(32))
265 // If this is a conditional branch to the header with the alternate path
266 // being outside the loop, we can ask questions about the execution frequency
267 // of the exit block.
268 if (L->isLoopExiting(Pred)) {
269 // This returns an exact expression only. TODO: We really only need an
270 // upper bound here, but SE doesn't expose that.
271 const SCEV *MaxExec = SE->getExitCount(L, Pred);
272 if (MaxExec != SE->getCouldNotCompute()) {
273 if (SE->getUnsignedRange(MaxExec).getUnsignedMax().ult(upperTripBound))
276 SE->getUnsignedRange(MaxExec).getUnsignedMax().isIntN(32))
281 return /* not finite */ false;
284 static void scanOneBB(Instruction *start, Instruction *end,
285 std::vector<CallInst *> &calls, 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 (succ_iterator PI = succ_begin(BB), E = succ_end(BB); PI != E;
302 BasicBlock *Succ = *PI;
303 if (seen.count(Succ) == 0) {
304 worklist.push_back(Succ);
311 static void scanInlinedCode(Instruction *start, Instruction *end,
312 std::vector<CallInst *> &calls,
313 std::set<BasicBlock *> &seen) {
315 std::vector<BasicBlock *> worklist;
316 seen.insert(start->getParent());
317 scanOneBB(start, end, calls, seen, worklist);
318 while (!worklist.empty()) {
319 BasicBlock *BB = worklist.back();
321 scanOneBB(&*BB->begin(), end, calls, seen, worklist);
325 bool PlaceBackedgeSafepointsImpl::runOnLoop(Loop *L, LPPassManager &LPM) {
326 ScalarEvolution *SE = &getAnalysis<ScalarEvolution>();
328 // Loop through all predecessors of the loop header and identify all
329 // backedges. We need to place a safepoint on every backedge (potentially).
330 // Note: Due to LoopSimplify there should only be one. Assert? Or can we
332 BasicBlock *header = L->getHeader();
334 // TODO: Use the analysis pass infrastructure for this. There is no reason
335 // to recalculate this here.
337 DT.recalculate(*header->getParent());
339 bool modified = false;
340 for (pred_iterator PI = pred_begin(header), E = pred_end(header); PI != E;
342 BasicBlock *pred = *PI;
343 if (!L->contains(pred)) {
344 // This is not a backedge, it's coming from outside the loop
348 // Make a policy decision about whether this loop needs a safepoint or
349 // not. Note that this is about unburdening the optimizer in loops, not
350 // avoiding the runtime cost of the actual safepoint.
352 if (mustBeFiniteCountedLoop(L, SE, pred)) {
354 errs() << "skipping safepoint placement in finite loop\n";
358 if (CallSafepointsEnabled &&
359 containsUnconditionalCallSafepoint(L, header, pred, DT)) {
360 // Note: This is only semantically legal since we won't do any further
361 // IPO or inlining before the actual call insertion.. If we hadn't, we
362 // might latter loose this call safepoint.
364 errs() << "skipping safepoint placement due to unconditional call\n";
370 // TODO: We can create an inner loop which runs a finite number of
371 // iterations with an outer loop which contains a safepoint. This would
372 // not help runtime performance that much, but it might help our ability to
373 // optimize the inner loop.
375 // We're unconditionally going to modify this loop.
378 // Safepoint insertion would involve creating a new basic block (as the
379 // target of the current backedge) which does the safepoint (of all live
380 // variables) and branches to the true header
381 TerminatorInst *term = pred->getTerminator();
384 errs() << "[LSP] terminator instruction: ";
388 PollLocations.push_back(term);
394 static Instruction *findLocationForEntrySafepoint(Function &F,
397 // Conceptually, this poll needs to be on method entry, but in
398 // practice, we place it as late in the entry block as possible. We
399 // can place it as late as we want as long as it dominates all calls
400 // that can grow the stack. This, combined with backedge polls,
401 // give us all the progress guarantees we need.
403 // Due to the way the frontend generates IR, we may have a couple of initial
404 // basic blocks before the first bytecode. These will be single-entry
405 // single-exit blocks which conceptually are just part of the first 'real
406 // basic block'. Since we don't have deopt state until the first bytecode,
407 // walk forward until we've found the first unconditional branch or merge.
409 // hasNextInstruction and nextInstruction are used to iterate
410 // through a "straight line" execution sequence.
412 auto hasNextInstruction = [](Instruction *I) {
413 if (!I->isTerminator()) {
416 BasicBlock *nextBB = I->getParent()->getUniqueSuccessor();
417 return nextBB && (nextBB->getUniquePredecessor() != nullptr);
420 auto nextInstruction = [&hasNextInstruction](Instruction *I) {
421 assert(hasNextInstruction(I) &&
422 "first check if there is a next instruction!");
423 if (I->isTerminator()) {
424 return I->getParent()->getUniqueSuccessor()->begin();
426 return std::next(BasicBlock::iterator(I));
430 Instruction *cursor = nullptr;
431 for (cursor = F.getEntryBlock().begin(); hasNextInstruction(cursor);
432 cursor = nextInstruction(cursor)) {
435 // We need to stop going forward as soon as we see a call that can
436 // grow the stack (i.e. the call target has a non-zero frame
438 if (CallSite CS = cursor) {
439 (void)CS; // Silence an unused variable warning by gcc 4.8.2
440 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(cursor)) {
441 // llvm.assume(...) are not really calls.
442 if (II->getIntrinsicID() == Intrinsic::assume) {
450 assert((hasNextInstruction(cursor) ||
451 cursor->isTerminator()) &&
452 "either we stopped because of a call, or because of terminator");
454 if (cursor->isTerminator()) {
458 BasicBlock *BB = cursor->getParent();
459 SplitBlock(BB, cursor, nullptr);
461 // Note: SplitBlock modifies the DT. Simply passing a Pass (which is a
462 // module pass) is not enough.
465 // SplitBlock updates the DT
469 return BB->getTerminator();
472 /// Identify the list of call sites which need to be have parseable state
473 static void findCallSafepoints(Function &F,
474 std::vector<CallSite> &Found /*rval*/) {
475 assert(Found.empty() && "must be empty!");
476 for (inst_iterator itr = inst_begin(F), end = inst_end(F); itr != end;
478 Instruction *inst = &*itr;
479 if (isa<CallInst>(inst) || isa<InvokeInst>(inst)) {
482 // No safepoint needed or wanted
483 if (!needsStatepoint(CS)) {
492 /// Implement a unique function which doesn't require we sort the input
493 /// vector. Doing so has the effect of changing the output of a couple of
494 /// tests in ways which make them less useful in testing fused safepoints.
495 template <typename T> static void unique_unsorted(std::vector<T> &vec) {
498 vec.reserve(vec.size());
501 if (seen.insert(V).second) {
507 bool PlaceSafepoints::runOnFunction(Function &F) {
508 if (F.isDeclaration() || F.empty()) {
509 // This is a declaration, nothing to do. Must exit early to avoid crash in
510 // dom tree calculation
514 bool modified = false;
516 // In various bits below, we rely on the fact that uses are reachable from
517 // defs. When there are basic blocks unreachable from the entry, dominance
518 // and reachablity queries return non-sensical results. Thus, we preprocess
519 // the function to ensure these properties hold.
520 modified |= removeUnreachableBlocks(F);
522 // STEP 1 - Insert the safepoint polling locations. We do not need to
523 // actually insert parse points yet. That will be done for all polls and
524 // calls in a single pass.
526 // Note: With the migration, we need to recompute this for each 'pass'. Once
527 // we merge these, we'll do it once before the analysis
530 std::vector<CallSite> ParsePointNeeded;
532 if (EnableBackedgeSafepoints) {
533 // Construct a pass manager to run the LoopPass backedge logic. We
534 // need the pass manager to handle scheduling all the loop passes
535 // appropriately. Doing this by hand is painful and just not worth messing
536 // with for the moment.
537 FunctionPassManager FPM(F.getParent());
538 PlaceBackedgeSafepointsImpl *PBS =
539 new PlaceBackedgeSafepointsImpl(EnableCallSafepoints);
541 // Note: While the analysis pass itself won't modify the IR, LoopSimplify
542 // (which it depends on) may. i.e. analysis must be recalculated after run
545 // We preserve dominance information when inserting the poll, otherwise
546 // we'd have to recalculate this on every insert
549 // Insert a poll at each point the analysis pass identified
550 for (size_t i = 0; i < PBS->PollLocations.size(); i++) {
551 // We are inserting a poll, the function is modified
554 // The poll location must be the terminator of a loop latch block.
555 TerminatorInst *Term = PBS->PollLocations[i];
557 std::vector<CallSite> ParsePoints;
559 // Split the backedge of the loop and insert the poll within that new
560 // basic block. This creates a loop with two latches per original
561 // latch (which is non-ideal), but this appears to be easier to
562 // optimize in practice than inserting the poll immediately before the
565 // Since this is a latch, at least one of the successors must dominate
566 // it. Its possible that we have a) duplicate edges to the same header
567 // and b) edges to distinct loop headers. We need to insert pools on
568 // each. (Note: This still relies on LoopSimplify.)
569 DenseSet<BasicBlock*> Headers;
570 for (unsigned i = 0; i < Term->getNumSuccessors(); i++) {
571 BasicBlock *Succ = Term->getSuccessor(i);
572 if (DT.dominates(Succ, Term->getParent())) {
573 Headers.insert(Succ);
576 assert(!Headers.empty() && "poll location is not a loop latch?");
578 // The split loop structure here is so that we only need to recalculate
579 // the dominator tree once. Alternatively, we could just keep it up to
580 // date and use a more natural merged loop.
581 DenseSet<BasicBlock*> SplitBackedges;
582 for (BasicBlock *Header : Headers) {
583 BasicBlock *NewBB = SplitEdge(Term->getParent(), Header, nullptr);
584 SplitBackedges.insert(NewBB);
587 for (BasicBlock *NewBB : SplitBackedges) {
588 InsertSafepointPoll(DT, NewBB->getTerminator(), ParsePoints);
589 NumBackedgeSafepoints++;
593 // Split the latch block itself, right before the terminator.
594 InsertSafepointPoll(DT, Term, ParsePoints);
595 NumBackedgeSafepoints++;
599 // Record the parse points for later use
600 ParsePointNeeded.insert(ParsePointNeeded.end(), ParsePoints.begin(),
605 if (EnableEntrySafepoints) {
607 Instruction *term = findLocationForEntrySafepoint(F, DT);
609 // policy choice not to insert?
611 std::vector<CallSite> RuntimeCalls;
612 InsertSafepointPoll(DT, term, RuntimeCalls);
614 NumEntrySafepoints++;
615 ParsePointNeeded.insert(ParsePointNeeded.end(), RuntimeCalls.begin(),
620 if (EnableCallSafepoints) {
622 std::vector<CallSite> Calls;
623 findCallSafepoints(F, Calls);
624 NumCallSafepoints += Calls.size();
625 ParsePointNeeded.insert(ParsePointNeeded.end(), Calls.begin(),
629 // Unique the vectors since we can end up with duplicates if we scan the call
630 // site for call safepoints after we add it for entry or backedge. The
631 // only reason we need tracking at all is that some functions might have
632 // polls but not call safepoints and thus we might miss marking the runtime
633 // calls for the polls. (This is useful in test cases!)
634 unique_unsorted(ParsePointNeeded);
636 // Any parse point (no matter what source) will be handled here
637 DT.recalculate(F); // Needed?
639 // We're about to start modifying the function
640 if (!ParsePointNeeded.empty())
643 // Now run through and insert the safepoints, but do _NOT_ update or remove
644 // any existing uses. We have references to live variables that need to
645 // survive to the last iteration of this loop.
646 std::vector<Value *> Results;
647 Results.reserve(ParsePointNeeded.size());
648 for (size_t i = 0; i < ParsePointNeeded.size(); i++) {
649 CallSite &CS = ParsePointNeeded[i];
650 Value *GCResult = ReplaceWithStatepoint(CS, nullptr);
651 Results.push_back(GCResult);
653 assert(Results.size() == ParsePointNeeded.size());
655 // Adjust all users of the old call sites to use the new ones instead
656 for (size_t i = 0; i < ParsePointNeeded.size(); i++) {
657 CallSite &CS = ParsePointNeeded[i];
658 Value *GCResult = Results[i];
660 // In case if we inserted result in a different basic block than the
661 // original safepoint (this can happen for invokes). We need to be sure
663 // original result value was not used in any of the phi nodes at the
664 // beginning of basic block with gc result. Because we know that all such
665 // blocks will have single predecessor we can safely assume that all phi
666 // nodes have single entry (because of normalizeBBForInvokeSafepoint).
667 // Just remove them all here.
669 FoldSingleEntryPHINodes(cast<Instruction>(GCResult)->getParent(),
672 !isa<PHINode>(cast<Instruction>(GCResult)->getParent()->begin()));
675 // Replace all uses with the new call
676 CS.getInstruction()->replaceAllUsesWith(GCResult);
679 // Now that we've handled all uses, remove the original call itself
680 // Note: The insert point can't be the deleted instruction!
681 CS.getInstruction()->eraseFromParent();
686 char PlaceBackedgeSafepointsImpl::ID = 0;
687 char PlaceSafepoints::ID = 0;
689 ModulePass *llvm::createPlaceSafepointsPass() {
690 return new PlaceSafepoints();
693 INITIALIZE_PASS_BEGIN(PlaceBackedgeSafepointsImpl,
694 "place-backedge-safepoints-impl",
695 "Place Backedge Safepoints", false, false)
696 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
697 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
698 INITIALIZE_PASS_END(PlaceBackedgeSafepointsImpl,
699 "place-backedge-safepoints-impl",
700 "Place Backedge Safepoints", false, false)
702 INITIALIZE_PASS_BEGIN(PlaceSafepoints, "place-safepoints", "Place Safepoints",
704 INITIALIZE_PASS_END(PlaceSafepoints, "place-safepoints", "Place Safepoints",
707 static bool isGCLeafFunction(const CallSite &CS) {
708 Instruction *inst = CS.getInstruction();
709 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(inst)) {
710 switch (II->getIntrinsicID()) {
712 // Most LLVM intrinsics are things which can never take a safepoint.
713 // As a result, we don't need to have the stack parsable at the
714 // callsite. This is a highly useful optimization since intrinsic
715 // calls are fairly prevelent, particularly in debug builds.
720 // If this function is marked explicitly as a leaf call, we don't need to
721 // place a safepoint of it. In fact, for correctness we *can't* in many
722 // cases. Note: Indirect calls return Null for the called function,
723 // these obviously aren't runtime functions with attributes
724 // TODO: Support attributes on the call site as well.
725 const Function *F = CS.getCalledFunction();
728 F->getFnAttribute("gc-leaf-function").getValueAsString().equals("true");
735 static void InsertSafepointPoll(
736 DominatorTree &DT, Instruction *term,
737 std::vector<CallSite> &ParsePointsNeeded /*rval*/) {
738 Module *M = term->getParent()->getParent()->getParent();
741 // Inline the safepoint poll implementation - this will get all the branch,
742 // control flow, etc.. Most importantly, it will introduce the actual slow
743 // path call - where we need to insert a safepoint (parsepoint).
744 FunctionType *ftype =
745 FunctionType::get(Type::getVoidTy(M->getContext()), false);
746 assert(ftype && "null?");
747 // Note: This cast can fail if there's a function of the same name with a
748 // different type inserted previously
750 dyn_cast<Function>(M->getOrInsertFunction("gc.safepoint_poll", ftype));
751 assert(F && !F->empty() && "definition must exist");
752 CallInst *poll = CallInst::Create(F, "", term);
754 // Record some information about the call site we're replacing
755 BasicBlock *OrigBB = term->getParent();
756 BasicBlock::iterator before(poll), after(poll);
758 if (before == term->getParent()->begin()) {
764 assert(after != poll->getParent()->end() && "must have successor");
765 assert(DT.dominates(before, after) && "trivially true");
767 // do the actual inlining
768 InlineFunctionInfo IFI;
769 bool inlineStatus = InlineFunction(poll, IFI);
770 assert(inlineStatus && "inline must succeed");
772 // Check post conditions
773 assert(IFI.StaticAllocas.empty() && "can't have allocs");
775 std::vector<CallInst *> calls; // new calls
776 std::set<BasicBlock *> BBs; // new BBs + insertee
777 // Include only the newly inserted instructions, Note: begin may not be valid
778 // if we inserted to the beginning of the basic block
779 BasicBlock::iterator start;
781 start = OrigBB->begin();
787 // If your poll function includes an unreachable at the end, that's not
788 // valid. Bugpoint likes to create this, so check for it.
789 assert(isPotentiallyReachable(&*start, &*after, nullptr, nullptr) &&
790 "malformed poll function");
792 scanInlinedCode(&*(start), &*(after), calls, BBs);
794 // Recompute since we've invalidated cached data. Conceptually we
795 // shouldn't need to do this, but implementation wise we appear to. Needed
796 // so we can insert safepoints correctly.
797 // TODO: update more cheaply
798 DT.recalculate(*after->getParent()->getParent());
800 assert(!calls.empty() && "slow path not found for safepoint poll");
802 // Record the fact we need a parsable state at the runtime call contained in
803 // the poll function. This is required so that the runtime knows how to
804 // parse the last frame when we actually take the safepoint (i.e. execute
806 assert(ParsePointsNeeded.empty());
807 for (size_t i = 0; i < calls.size(); i++) {
809 // No safepoint needed or wanted
810 if (!needsStatepoint(calls[i])) {
814 // These are likely runtime calls. Should we assert that via calling
815 // convention or something?
816 ParsePointsNeeded.push_back(CallSite(calls[i]));
818 assert(ParsePointsNeeded.size() <= calls.size());
821 // Normalize basic block to make it ready to be target of invoke statepoint.
822 // It means spliting it to have single predecessor. Return newly created BB
823 // ready to be successor of invoke statepoint.
824 static BasicBlock *normalizeBBForInvokeSafepoint(BasicBlock *BB,
825 BasicBlock *InvokeParent) {
826 BasicBlock *ret = BB;
828 if (!BB->getUniquePredecessor()) {
829 ret = SplitBlockPredecessors(BB, InvokeParent, "");
832 // Another requirement for such basic blocks is to not have any phi nodes.
833 // Since we just ensured that new BB will have single predecessor,
834 // all phi nodes in it will have one value. Here it would be naturall place
836 // remove them all. But we can not do this because we are risking to remove
837 // one of the values stored in liveset of another statepoint. We will do it
838 // later after placing all safepoints.
843 /// Replaces the given call site (Call or Invoke) with a gc.statepoint
844 /// intrinsic with an empty deoptimization arguments list. This does
845 /// NOT do explicit relocation for GC support.
846 static Value *ReplaceWithStatepoint(const CallSite &CS, /* to replace */
848 BasicBlock *BB = CS.getInstruction()->getParent();
849 Function *F = BB->getParent();
850 Module *M = F->getParent();
851 assert(M && "must be set");
853 // TODO: technically, a pass is not allowed to get functions from within a
854 // function pass since it might trigger a new function addition. Refactor
855 // this logic out to the initialization of the pass. Doesn't appear to
856 // matter in practice.
858 // Fill in the one generic type'd argument (the function is also vararg)
859 std::vector<Type *> argTypes;
860 argTypes.push_back(CS.getCalledValue()->getType());
862 Function *gc_statepoint_decl = Intrinsic::getDeclaration(
863 M, Intrinsic::experimental_gc_statepoint, argTypes);
865 // Then go ahead and use the builder do actually do the inserts. We insert
866 // immediately before the previous instruction under the assumption that all
867 // arguments will be available here. We can't insert afterwards since we may
868 // be replacing a terminator.
869 Instruction *insertBefore = CS.getInstruction();
870 IRBuilder<> Builder(insertBefore);
871 // First, create the statepoint (with all live ptrs as arguments).
872 std::vector<llvm::Value *> args;
873 // target, #args, unused, args
874 Value *Target = CS.getCalledValue();
875 args.push_back(Target);
876 int callArgSize = CS.arg_size();
878 ConstantInt::get(Type::getInt32Ty(M->getContext()), callArgSize));
879 // TODO: add a 'Needs GC-rewrite' later flag
880 args.push_back(ConstantInt::get(Type::getInt32Ty(M->getContext()), 0));
882 // Copy all the arguments of the original call
883 args.insert(args.end(), CS.arg_begin(), CS.arg_end());
885 // Create the statepoint given all the arguments
886 Instruction *token = nullptr;
887 AttributeSet return_attributes;
889 CallInst *toReplace = cast<CallInst>(CS.getInstruction());
891 Builder.CreateCall(gc_statepoint_decl, args, "safepoint_token");
892 call->setTailCall(toReplace->isTailCall());
893 call->setCallingConv(toReplace->getCallingConv());
895 // Before we have to worry about GC semantics, all attributes are legal
896 AttributeSet new_attrs = toReplace->getAttributes();
897 // In case if we can handle this set of sttributes - set up function attrs
898 // directly on statepoint and return attrs later for gc_result intrinsic.
899 call->setAttributes(new_attrs.getFnAttributes());
900 return_attributes = new_attrs.getRetAttributes();
901 // TODO: handle param attributes
905 // Put the following gc_result and gc_relocate calls immediately after the
906 // the old call (which we're about to delete)
907 BasicBlock::iterator next(toReplace);
908 assert(BB->end() != next && "not a terminator, must have next");
910 Instruction *IP = &*(next);
911 Builder.SetInsertPoint(IP);
912 Builder.SetCurrentDebugLocation(IP->getDebugLoc());
914 } else if (CS.isInvoke()) {
915 InvokeInst *toReplace = cast<InvokeInst>(CS.getInstruction());
917 // Insert the new invoke into the old block. We'll remove the old one in a
918 // moment at which point this will become the new terminator for the
920 InvokeInst *invoke = InvokeInst::Create(
921 gc_statepoint_decl, toReplace->getNormalDest(),
922 toReplace->getUnwindDest(), args, "", toReplace->getParent());
923 invoke->setCallingConv(toReplace->getCallingConv());
925 // Currently we will fail on parameter attributes and on certain
926 // function attributes.
927 AttributeSet new_attrs = toReplace->getAttributes();
928 // In case if we can handle this set of sttributes - set up function attrs
929 // directly on statepoint and return attrs later for gc_result intrinsic.
930 invoke->setAttributes(new_attrs.getFnAttributes());
931 return_attributes = new_attrs.getRetAttributes();
935 // We'll insert the gc.result into the normal block
936 BasicBlock *normalDest = normalizeBBForInvokeSafepoint(
937 toReplace->getNormalDest(), invoke->getParent());
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 Instruction *gc_result = nullptr;
951 std::vector<Type *> types; // one per 'any' type
952 types.push_back(CS.getType()); // result type
953 auto get_gc_result_id = [&](Type &Ty) {
954 if (Ty.isIntegerTy()) {
955 return Intrinsic::experimental_gc_result_int;
956 } else if (Ty.isFloatingPointTy()) {
957 return Intrinsic::experimental_gc_result_float;
958 } else if (Ty.isPointerTy()) {
959 return Intrinsic::experimental_gc_result_ptr;
961 llvm_unreachable("non java type encountered");
964 Intrinsic::ID Id = get_gc_result_id(*CS.getType());
965 Value *gc_result_func = Intrinsic::getDeclaration(M, Id, types);
967 std::vector<Value *> args;
968 args.push_back(token);
969 gc_result = Builder.CreateCall(
970 gc_result_func, args,
971 CS.getInstruction()->hasName() ? CS.getInstruction()->getName() : "");
973 cast<CallInst>(gc_result)->setAttributes(return_attributes);
976 // No return value for the call.