1//===- PlaceSafepoints.cpp - Place GC Safepoints --------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// Place garbage collection safepoints at appropriate locations in the IR. This 11// does not make relocation semantics or variable liveness explicit. That's 12// done by RewriteStatepointsForGC. 13// 14// Terminology: 15// - A call is said to be "parseable" if there is a stack map generated for the 16// return PC of the call. A runtime can determine where values listed in the 17// deopt arguments and (after RewriteStatepointsForGC) gc arguments are located 18// on the stack when the code is suspended inside such a call. Every parse 19// point is represented by a call wrapped in an gc.statepoint intrinsic. 20// - A "poll" is an explicit check in the generated code to determine if the 21// runtime needs the generated code to cooperate by calling a helper routine 22// and thus suspending its execution at a known state. The call to the helper 23// routine will be parseable. The (gc & runtime specific) logic of a poll is 24// assumed to be provided in a function of the name "gc.safepoint_poll". 25// 26// We aim to insert polls such that running code can quickly be brought to a 27// well defined state for inspection by the collector. In the current 28// implementation, this is done via the insertion of poll sites at method entry 29// and the backedge of most loops. We try to avoid inserting more polls than 30// are 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. 34// 35// We also need to make most call sites parseable. The callee might execute a 36// poll (or otherwise be inspected by the GC). If so, the entire stack 37// (including the suspended frame of the current method) must be parseable. 38// 39// This pass will insert: 40// - Call parse points ("call safepoints") for any call which may need to 41// reach a safepoint during the execution of the callee function. 42// - Backedge safepoint polls and entry safepoint polls to ensure that 43// executing code reaches a safepoint poll in a finite amount of time. 44// 45// We do not currently support return statepoints, but adding them would not 46// be hard. They are not required for correctness - entry safepoints are an 47// alternative - but some GCs may prefer them. Patches welcome. 48// 49//===----------------------------------------------------------------------===// 50 51#include "llvm/Pass.h" 52#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" 81 82#define DEBUG_TYPE "safepoint-placement" 83STATISTIC(NumEntrySafepoints, "Number of entry safepoints inserted"); 84STATISTIC(NumCallSafepoints, "Number of call safepoints inserted"); 85STATISTIC(NumBackedgeSafepoints, "Number of backedge safepoints inserted"); 86 87STATISTIC(CallInLoop, "Number of loops w/o safepoints due to calls in loop"); 88STATISTIC(FiniteExecution, "Number of loops w/o safepoints finite execution"); 89 90using namespace llvm; 91 92// Ignore oppurtunities to avoid placing safepoints on backedges, useful for 93// validation 94static cl::opt<bool> AllBackedges("spp-all-backedges", cl::Hidden, 95 cl::init(false)); 96 97/// If true, do not place backedge safepoints in counted loops. 98static cl::opt<bool> SkipCounted("spp-counted", cl::Hidden, cl::init(true)); 99 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 103// optimizes better. 104static cl::opt<bool> SplitBackedge("spp-split-backedge", cl::Hidden, 105 cl::init(false)); 106 107// Print tracing output 108static cl::opt<bool> TraceLSP("spp-trace", cl::Hidden, cl::init(false)); 109 110namespace { 111 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. */ 114struct PlaceBackedgeSafepointsImpl : public LoopPass { 115 static char ID; 116 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; 120 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()); 127 } 128 129 bool runOnLoop(Loop *, LPPassManager &LPM) override; 130 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); 137 138 // We no longer modify the IR at all in this pass. Thus all 139 // analysis are preserved. 140 AU.setPreservesAll(); 141 } 142}; 143} 144 145static cl::opt<bool> NoEntry("spp-no-entry", cl::Hidden, cl::init(false)); 146static cl::opt<bool> NoCall("spp-no-call", cl::Hidden, cl::init(false)); 147static cl::opt<bool> NoBackedge("spp-no-backedge", cl::Hidden, cl::init(false)); 148 149namespace { 150struct PlaceSafepoints : public ModulePass { 151 static char ID; // Pass identification, replacement for typeid 152 153 PlaceSafepoints() : ModulePass(ID) { 154 initializePlaceSafepointsPass(*PassRegistry::getPassRegistry()); 155 } 156 bool runOnModule(Module &M) override { 157 bool modified = false; 158 for (Function &F : M) { 159 modified |= runOnFunction(F); 160 } 161 return modified; 162 } 163 bool runOnFunction(Function &F); 164 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 169 } 170}; 171} 172 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 175// callers job. 176static void 177InsertSafepointPoll(DominatorTree &DT, Instruction *after, 178 std::vector<CallSite> &ParsePointsNeeded /*rval*/); 179 180static bool isGCLeafFunction(const CallSite &CS); 181 182static bool needsStatepoint(const CallSite &CS) { 183 if (isGCLeafFunction(CS)) 184 return false; 185 if (CS.isCall()) { 186 CallInst *call = cast<CallInst>(CS.getInstruction()); 187 if (call->isInlineAsm()) 188 return false; 189 } 190 if (isStatepoint(CS) || isGCRelocate(CS) || isGCResult(CS)) { 191 return false; 192 } 193 return true; 194} 195 196static Value *ReplaceWithStatepoint(const CallSite &CS, Pass *P); 197 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. 202static bool containsUnconditionalCallSafepoint(Loop *L, BasicBlock *Header, 203 BasicBlock *Pred, 204 DominatorTree &DT) { 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?"); 216 217 BasicBlock *Current = Pred; 218 while (true) { 219 for (Instruction &I : *Current) { 220 if (auto CS = CallSite(&I)) 221 // Note: Technically, needing a safepoint isn't quite the right 222 // condition here. We should instead be checking if the target method 223 // has an 224 // unconditional poll. In practice, this is only a theoretical concern 225 // since we don't have any methods with conditional-only safepoint 226 // polls. 227 if (needsStatepoint(CS)) 228 return true; 229 } 230 231 if (Current == Header) 232 break; 233 Current = DT.getNode(Current)->getIDom()->getBlock(); 234 } 235 236 return false; 237} 238 239/// Returns true if this loop is known to terminate in a finite number of 240/// iterations. Note that this function may return false for a loop which 241/// does actual terminate in a finite constant number of iterations due to 242/// conservatism in the analysis. 243static bool mustBeFiniteCountedLoop(Loop *L, ScalarEvolution *SE, 244 BasicBlock *Pred) { 245 // Only used when SkipCounted is off 246 const unsigned upperTripBound = 8192; 247 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)) 252 return true; 253 if (SkipCounted && 254 SE->getUnsignedRange(MaxTrips).getUnsignedMax().isIntN(32)) 255 return true; 256 } 257 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)) 267 return true; 268 if (SkipCounted && 269 SE->getUnsignedRange(MaxExec).getUnsignedMax().isIntN(32)) 270 return true; 271 } 272 } 273 274 return /* not finite */ false; 275} 276 277static 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); 283 itr++) { 284 if (CallInst *CI = dyn_cast<CallInst>(&*itr)) { 285 calls.push_back(CI); 286 } 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); 297 seen.insert(Succ); 298 } 299 } 300 } 301 } 302} 303static void scanInlinedCode(Instruction *start, Instruction *end, 304 std::vector<CallInst *> &calls, 305 std::set<BasicBlock *> &seen) { 306 calls.clear(); 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(); 312 worklist.pop_back(); 313 scanOneBB(&*BB->begin(), end, calls, seen, worklist); 314 } 315} 316 317bool PlaceBackedgeSafepointsImpl::runOnLoop(Loop *L, LPPassManager &LPM) { 318 ScalarEvolution *SE = &getAnalysis<ScalarEvolution>(); 319 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 323 // relax this? 324 BasicBlock *header = L->getHeader(); 325 326 // TODO: Use the analysis pass infrastructure for this. There is no reason 327 // to recalculate this here. 328 DominatorTree DT; 329 DT.recalculate(*header->getParent()); 330 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 335 continue; 336 } 337 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. 341 if (!AllBackedges) { 342 if (mustBeFiniteCountedLoop(L, SE, pred)) { 343 if (TraceLSP) 344 errs() << "skipping safepoint placement in finite loop\n"; 345 FiniteExecution++; 346 continue; 347 } 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. 353 if (TraceLSP) 354 errs() << "skipping safepoint placement due to unconditional call\n"; 355 CallInLoop++; 356 continue; 357 } 358 } 359 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. 364 365 // We're unconditionally going to modify this loop. 366 modified = true; 367 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(); 372 373 if (TraceLSP) { 374 errs() << "[LSP] terminator instruction: "; 375 term->dump(); 376 } 377 378 PollLocations.push_back(term); 379 } 380 381 return modified; 382} 383 384static Instruction *findLocationForEntrySafepoint(Function &F, 385 DominatorTree &DT) { 386 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. 392 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. 398 399 // hasNextInstruction and nextInstruction are used to iterate 400 // through a "straight line" execution sequence. 401 402 auto hasNextInstruction = [](Instruction *I) { 403 if (!I->isTerminator()) { 404 return true; 405 } 406 BasicBlock *nextBB = I->getParent()->getUniqueSuccessor(); 407 return nextBB && (nextBB->getUniquePredecessor() != nullptr); 408 }; 409 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(); 415 } else { 416 return std::next(BasicBlock::iterator(I)); 417 } 418 }; 419 420 Instruction *cursor = nullptr; 421 for (cursor = F.getEntryBlock().begin(); hasNextInstruction(cursor); 422 cursor = nextInstruction(cursor)) { 423 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 426 // size). 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) { 431 continue; 432 } 433 } 434 break; 435 } 436 } 437 438 assert((hasNextInstruction(cursor) || cursor->isTerminator()) && 439 "either we stopped because of a call, or because of terminator"); 440 441 if (cursor->isTerminator()) { 442 return cursor; 443 } 444 445 BasicBlock *BB = cursor->getParent(); 446 SplitBlock(BB, cursor, nullptr); 447 448 // Note: SplitBlock modifies the DT. Simply passing a Pass (which is a 449 // module pass) is not enough. 450 DT.recalculate(F); 451#ifndef NDEBUG 452 // SplitBlock updates the DT 453 DT.verifyDomTree(); 454#endif 455 456 return BB->getTerminator(); 457} 458 459/// Identify the list of call sites which need to be have parseable state 460static void findCallSafepoints(Function &F, 461 std::vector<CallSite> &Found /*rval*/) { 462 assert(Found.empty() && "must be empty!"); 463 for (Instruction &I : inst_range(F)) { 464 Instruction *inst = &I; 465 if (isa<CallInst>(inst) || isa<InvokeInst>(inst)) { 466 CallSite CS(inst); 467 468 // No safepoint needed or wanted 469 if (!needsStatepoint(CS)) { 470 continue; 471 } 472 473 Found.push_back(CS); 474 } 475 } 476} 477 478/// Implement a unique function which doesn't require we sort the input 479/// vector. Doing so has the effect of changing the output of a couple of 480/// tests in ways which make them less useful in testing fused safepoints. 481template <typename T> static void unique_unsorted(std::vector<T> &vec) { 482 std::set<T> seen; 483 std::vector<T> tmp; 484 vec.reserve(vec.size()); 485 std::swap(tmp, vec); 486 for (auto V : tmp) { 487 if (seen.insert(V).second) { 488 vec.push_back(V); 489 } 490 } 491} 492 493static std::string GCSafepointPollName("gc.safepoint_poll"); 494 495static bool isGCSafepointPoll(Function &F) { 496 return F.getName().equals(GCSafepointPollName); 497} 498 499/// Returns true if this function should be rewritten to include safepoint 500/// polls and parseable call sites. The main point of this function is to be 501/// an extension point for custom logic. 502static bool shouldRewriteFunction(Function &F) { 503 // TODO: This should check the GCStrategy 504 if (F.hasGC()) { 505 const std::string StatepointExampleName("statepoint-example"); 506 return StatepointExampleName == F.getGC(); 507 } else 508 return false; 509} 510 511// TODO: These should become properties of the GCStrategy, possibly with 512// command line overrides. 513static bool enableEntrySafepoints(Function &F) { return !NoEntry; } 514static bool enableBackedgeSafepoints(Function &F) { return !NoBackedge; } 515static bool enableCallSafepoints(Function &F) { return !NoCall; } 516 517 518bool PlaceSafepoints::runOnFunction(Function &F) { 519 if (F.isDeclaration() || F.empty()) { 520 // This is a declaration, nothing to do. Must exit early to avoid crash in 521 // dom tree calculation 522 return false; 523 } 524 525 if (isGCSafepointPoll(F)) { 526 // Given we're inlining this inside of safepoint poll insertion, this 527 // doesn't make any sense. Note that we do make any contained calls 528 // parseable after we inline a poll. 529 return false; 530 } 531 532 if (!shouldRewriteFunction(F)) 533 return false; 534 535 bool modified = false; 536 537 // In various bits below, we rely on the fact that uses are reachable from 538 // defs. When there are basic blocks unreachable from the entry, dominance 539 // and reachablity queries return non-sensical results. Thus, we preprocess 540 // the function to ensure these properties hold. 541 modified |= removeUnreachableBlocks(F); 542 543 // STEP 1 - Insert the safepoint polling locations. We do not need to 544 // actually insert parse points yet. That will be done for all polls and 545 // calls in a single pass. 546 547 // Note: With the migration, we need to recompute this for each 'pass'. Once 548 // we merge these, we'll do it once before the analysis 549 DominatorTree DT; 550 551 std::vector<CallSite> ParsePointNeeded; 552 553 if (enableBackedgeSafepoints(F)) { 554 // Construct a pass manager to run the LoopPass backedge logic. We 555 // need the pass manager to handle scheduling all the loop passes 556 // appropriately. Doing this by hand is painful and just not worth messing 557 // with for the moment. 558 legacy::FunctionPassManager FPM(F.getParent()); 559 bool CanAssumeCallSafepoints = enableCallSafepoints(F); 560 PlaceBackedgeSafepointsImpl *PBS = 561 new PlaceBackedgeSafepointsImpl(CanAssumeCallSafepoints); 562 FPM.add(PBS); 563 // Note: While the analysis pass itself won't modify the IR, LoopSimplify 564 // (which it depends on) may. i.e. analysis must be recalculated after run 565 FPM.run(F); 566 567 // We preserve dominance information when inserting the poll, otherwise 568 // we'd have to recalculate this on every insert 569 DT.recalculate(F); 570 571 // Insert a poll at each point the analysis pass identified 572 for (size_t i = 0; i < PBS->PollLocations.size(); i++) { 573 // We are inserting a poll, the function is modified 574 modified = true; 575 576 // The poll location must be the terminator of a loop latch block. 577 TerminatorInst *Term = PBS->PollLocations[i]; 578 579 std::vector<CallSite> ParsePoints; 580 if (SplitBackedge) { 581 // Split the backedge of the loop and insert the poll within that new 582 // basic block. This creates a loop with two latches per original 583 // latch (which is non-ideal), but this appears to be easier to 584 // optimize in practice than inserting the poll immediately before the 585 // latch test. 586 587 // Since this is a latch, at least one of the successors must dominate 588 // it. Its possible that we have a) duplicate edges to the same header 589 // and b) edges to distinct loop headers. We need to insert pools on 590 // each. (Note: This still relies on LoopSimplify.) 591 DenseSet<BasicBlock *> Headers; 592 for (unsigned i = 0; i < Term->getNumSuccessors(); i++) { 593 BasicBlock *Succ = Term->getSuccessor(i); 594 if (DT.dominates(Succ, Term->getParent())) { 595 Headers.insert(Succ); 596 } 597 } 598 assert(!Headers.empty() && "poll location is not a loop latch?"); 599 600 // The split loop structure here is so that we only need to recalculate 601 // the dominator tree once. Alternatively, we could just keep it up to 602 // date and use a more natural merged loop. 603 DenseSet<BasicBlock *> SplitBackedges; 604 for (BasicBlock *Header : Headers) { 605 BasicBlock *NewBB = SplitEdge(Term->getParent(), Header, nullptr); 606 SplitBackedges.insert(NewBB); 607 } 608 DT.recalculate(F); 609 for (BasicBlock *NewBB : SplitBackedges) { 610 InsertSafepointPoll(DT, NewBB->getTerminator(), ParsePoints); 611 NumBackedgeSafepoints++; 612 } 613 614 } else { 615 // Split the latch block itself, right before the terminator. 616 InsertSafepointPoll(DT, Term, ParsePoints); 617 NumBackedgeSafepoints++; 618 } 619 620 // Record the parse points for later use 621 ParsePointNeeded.insert(ParsePointNeeded.end(), ParsePoints.begin(), 622 ParsePoints.end()); 623 } 624 } 625 626 if (enableEntrySafepoints(F)) { 627 DT.recalculate(F); 628 Instruction *term = findLocationForEntrySafepoint(F, DT); 629 if (!term) { 630 // policy choice not to insert? 631 } else { 632 std::vector<CallSite> RuntimeCalls; 633 InsertSafepointPoll(DT, term, RuntimeCalls); 634 modified = true; 635 NumEntrySafepoints++; 636 ParsePointNeeded.insert(ParsePointNeeded.end(), RuntimeCalls.begin(), 637 RuntimeCalls.end()); 638 } 639 } 640 641 if (enableCallSafepoints(F)) { 642 DT.recalculate(F); 643 std::vector<CallSite> Calls; 644 findCallSafepoints(F, Calls); 645 NumCallSafepoints += Calls.size(); 646 ParsePointNeeded.insert(ParsePointNeeded.end(), Calls.begin(), Calls.end()); 647 } 648 649 // Unique the vectors since we can end up with duplicates if we scan the call 650 // site for call safepoints after we add it for entry or backedge. The 651 // only reason we need tracking at all is that some functions might have 652 // polls but not call safepoints and thus we might miss marking the runtime 653 // calls for the polls. (This is useful in test cases!) 654 unique_unsorted(ParsePointNeeded); 655 656 // Any parse point (no matter what source) will be handled here 657 DT.recalculate(F); // Needed? 658 659 // We're about to start modifying the function 660 if (!ParsePointNeeded.empty()) 661 modified = true; 662 663 // Now run through and insert the safepoints, but do _NOT_ update or remove 664 // any existing uses. We have references to live variables that need to 665 // survive to the last iteration of this loop. 666 std::vector<Value *> Results; 667 Results.reserve(ParsePointNeeded.size()); 668 for (size_t i = 0; i < ParsePointNeeded.size(); i++) { 669 CallSite &CS = ParsePointNeeded[i]; 670 Value *GCResult = ReplaceWithStatepoint(CS, nullptr); 671 Results.push_back(GCResult); 672 } 673 assert(Results.size() == ParsePointNeeded.size()); 674 675 // Adjust all users of the old call sites to use the new ones instead 676 for (size_t i = 0; i < ParsePointNeeded.size(); i++) { 677 CallSite &CS = ParsePointNeeded[i]; 678 Value *GCResult = Results[i]; 679 if (GCResult) { 680 // In case if we inserted result in a different basic block than the 681 // original safepoint (this can happen for invokes). We need to be sure 682 // that 683 // original result value was not used in any of the phi nodes at the 684 // beginning of basic block with gc result. Because we know that all such 685 // blocks will have single predecessor we can safely assume that all phi 686 // nodes have single entry (because of normalizeBBForInvokeSafepoint). 687 // Just remove them all here. 688 if (CS.isInvoke()) { 689 FoldSingleEntryPHINodes(cast<Instruction>(GCResult)->getParent(), 690 nullptr); 691 assert( 692 !isa<PHINode>(cast<Instruction>(GCResult)->getParent()->begin())); 693 } 694 695 // Replace all uses with the new call 696 CS.getInstruction()->replaceAllUsesWith(GCResult); 697 } 698 699 // Now that we've handled all uses, remove the original call itself 700 // Note: The insert point can't be the deleted instruction! 701 CS.getInstruction()->eraseFromParent(); 702 } 703 return modified; 704} 705 706char PlaceBackedgeSafepointsImpl::ID = 0; 707char PlaceSafepoints::ID = 0; 708 709ModulePass *llvm::createPlaceSafepointsPass() { return new PlaceSafepoints(); } 710 711INITIALIZE_PASS_BEGIN(PlaceBackedgeSafepointsImpl, 712 "place-backedge-safepoints-impl", 713 "Place Backedge Safepoints", false, false) 714INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 715INITIALIZE_PASS_DEPENDENCY(LoopSimplify) 716INITIALIZE_PASS_END(PlaceBackedgeSafepointsImpl, 717 "place-backedge-safepoints-impl", 718 "Place Backedge Safepoints", false, false) 719 720INITIALIZE_PASS_BEGIN(PlaceSafepoints, "place-safepoints", "Place Safepoints", 721 false, false) 722INITIALIZE_PASS_END(PlaceSafepoints, "place-safepoints", "Place Safepoints", 723 false, false) 724 725static bool isGCLeafFunction(const CallSite &CS) { 726 Instruction *inst = CS.getInstruction(); 727 if (isa<IntrinsicInst>(inst)) { 728 // Most LLVM intrinsics are things which can never take a safepoint. 729 // As a result, we don't need to have the stack parsable at the 730 // callsite. This is a highly useful optimization since intrinsic 731 // calls are fairly prevelent, particularly in debug builds. 732 return true; 733 } 734 735 // If this function is marked explicitly as a leaf call, we don't need to 736 // place a safepoint of it. In fact, for correctness we *can't* in many 737 // cases. Note: Indirect calls return Null for the called function, 738 // these obviously aren't runtime functions with attributes 739 // TODO: Support attributes on the call site as well. 740 const Function *F = CS.getCalledFunction(); 741 bool isLeaf = 742 F && 743 F->getFnAttribute("gc-leaf-function").getValueAsString().equals("true"); 744 if (isLeaf) { 745 return true; 746 } 747 return false; 748} 749 750static void 751InsertSafepointPoll(DominatorTree &DT, Instruction *term, 752 std::vector<CallSite> &ParsePointsNeeded /*rval*/) { 753 Module *M = term->getParent()->getParent()->getParent(); 754 assert(M); 755 756 // Inline the safepoint poll implementation - this will get all the branch, 757 // control flow, etc.. Most importantly, it will introduce the actual slow 758 // path call - where we need to insert a safepoint (parsepoint). 759 FunctionType *ftype = 760 FunctionType::get(Type::getVoidTy(M->getContext()), false); 761 assert(ftype && "null?"); 762 // Note: This cast can fail if there's a function of the same name with a 763 // different type inserted previously 764 Function *F = 765 dyn_cast<Function>(M->getOrInsertFunction("gc.safepoint_poll", ftype)); 766 assert(F && "void @gc.safepoint_poll() must be defined"); 767 assert(!F->empty() && "gc.safepoint_poll must be a non-empty function"); 768 CallInst *poll = CallInst::Create(F, "", term); 769 770 // Record some information about the call site we're replacing 771 BasicBlock *OrigBB = term->getParent(); 772 BasicBlock::iterator before(poll), after(poll); 773 bool isBegin(false); 774 if (before == term->getParent()->begin()) { 775 isBegin = true; 776 } else { 777 before--; 778 } 779 after++; 780 assert(after != poll->getParent()->end() && "must have successor"); 781 assert(DT.dominates(before, after) && "trivially true"); 782 783 // do the actual inlining 784 InlineFunctionInfo IFI; 785 bool inlineStatus = InlineFunction(poll, IFI); 786 assert(inlineStatus && "inline must succeed"); 787 (void)inlineStatus; // suppress warning in release-asserts 788 789 // Check post conditions 790 assert(IFI.StaticAllocas.empty() && "can't have allocs"); 791 792 std::vector<CallInst *> calls; // new calls 793 std::set<BasicBlock *> BBs; // new BBs + insertee 794 // Include only the newly inserted instructions, Note: begin may not be valid 795 // if we inserted to the beginning of the basic block 796 BasicBlock::iterator start; 797 if (isBegin) { 798 start = OrigBB->begin(); 799 } else { 800 start = before; 801 start++; 802 } 803 804 // If your poll function includes an unreachable at the end, that's not 805 // valid. Bugpoint likes to create this, so check for it. 806 assert(isPotentiallyReachable(&*start, &*after, nullptr, nullptr) && 807 "malformed poll function"); 808 809 scanInlinedCode(&*(start), &*(after), calls, BBs); 810 811 // Recompute since we've invalidated cached data. Conceptually we 812 // shouldn't need to do this, but implementation wise we appear to. Needed 813 // so we can insert safepoints correctly. 814 // TODO: update more cheaply 815 DT.recalculate(*after->getParent()->getParent()); 816 817 assert(!calls.empty() && "slow path not found for safepoint poll"); 818 819 // Record the fact we need a parsable state at the runtime call contained in 820 // the poll function. This is required so that the runtime knows how to 821 // parse the last frame when we actually take the safepoint (i.e. execute 822 // the slow path) 823 assert(ParsePointsNeeded.empty()); 824 for (size_t i = 0; i < calls.size(); i++) { 825 826 // No safepoint needed or wanted 827 if (!needsStatepoint(calls[i])) { 828 continue; 829 } 830 831 // These are likely runtime calls. Should we assert that via calling 832 // convention or something? 833 ParsePointsNeeded.push_back(CallSite(calls[i])); 834 } 835 assert(ParsePointsNeeded.size() <= calls.size()); 836} 837 838// Normalize basic block to make it ready to be target of invoke statepoint. 839// It means spliting it to have single predecessor. Return newly created BB 840// ready to be successor of invoke statepoint. 841static BasicBlock *normalizeBBForInvokeSafepoint(BasicBlock *BB, 842 BasicBlock *InvokeParent) { 843 BasicBlock *ret = BB; 844 845 if (!BB->getUniquePredecessor()) { 846 ret = SplitBlockPredecessors(BB, InvokeParent, ""); 847 } 848 849 // Another requirement for such basic blocks is to not have any phi nodes. 850 // Since we just ensured that new BB will have single predecessor, 851 // all phi nodes in it will have one value. Here it would be naturall place 852 // to 853 // remove them all. But we can not do this because we are risking to remove 854 // one of the values stored in liveset of another statepoint. We will do it 855 // later after placing all safepoints. 856 857 return ret; 858} 859 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. 863static Value *ReplaceWithStatepoint(const CallSite &CS, /* to replace */ 864 Pass *P) { 865 BasicBlock *BB = CS.getInstruction()->getParent(); 866 Function *F = BB->getParent(); 867 Module *M = F->getParent(); 868 assert(M && "must be set"); 869 870 // TODO: technically, a pass is not allowed to get functions from within a 871 // function pass since it might trigger a new function addition. Refactor 872 // this logic out to the initialization of the pass. Doesn't appear to 873 // matter in practice. 874 875 // Then go ahead and use the builder do actually do the inserts. We insert 876 // immediately before the previous instruction under the assumption that all 877 // arguments will be available here. We can't insert afterwards since we may 878 // be replacing a terminator. 879 Instruction *insertBefore = CS.getInstruction(); 880 IRBuilder<> Builder(insertBefore); 881 882 // Note: The gc args are not filled in at this time, that's handled by 883 // RewriteStatepointsForGC (which is currently under review). 884 885 // Create the statepoint given all the arguments 886 Instruction *token = nullptr; 887 AttributeSet return_attributes; 888 if (CS.isCall()) { 889 CallInst *toReplace = cast<CallInst>(CS.getInstruction()); 890 CallInst *Call = Builder.CreateGCStatepoint( 891 CS.getCalledValue(), makeArrayRef(CS.arg_begin(), CS.arg_end()), None, 892 None, "safepoint_token"); 893 Call->setTailCall(toReplace->isTailCall()); 894 Call->setCallingConv(toReplace->getCallingConv()); 895 896 // Before we have to worry about GC semantics, all attributes are legal 897 AttributeSet new_attrs = toReplace->getAttributes(); 898 // In case if we can handle this set of sttributes - set up function attrs 899 // directly on statepoint and return attrs later for gc_result intrinsic. 900 Call->setAttributes(new_attrs.getFnAttributes()); 901 return_attributes = new_attrs.getRetAttributes(); 902 // TODO: handle param attributes 903 904 token = Call; 905 906 // Put the following gc_result and gc_relocate calls immediately after the 907 // the old call (which we're about to delete) 908 BasicBlock::iterator next(toReplace); 909 assert(BB->end() != next && "not a terminator, must have next"); 910 next++; 911 Instruction *IP = &*(next); 912 Builder.SetInsertPoint(IP); 913 Builder.SetCurrentDebugLocation(IP->getDebugLoc()); 914 915 } else if (CS.isInvoke()) { 916 // TODO: make CreateGCStatepoint return an Instruction that we can cast to a 917 // Call or Invoke, instead of doing this junk here. 918 919 // Fill in the one generic type'd argument (the function is also 920 // vararg) 921 std::vector<Type *> argTypes; 922 argTypes.push_back(CS.getCalledValue()->getType()); 923 924 Function *gc_statepoint_decl = Intrinsic::getDeclaration( 925 M, Intrinsic::experimental_gc_statepoint, argTypes); 926 927 // First, create the statepoint (with all live ptrs as arguments). 928 std::vector<llvm::Value *> args; 929 // target, #call args, unused, ... call parameters, #deopt args, ... deopt 930 // parameters, ... gc parameters 931 Value *Target = CS.getCalledValue(); 932 args.push_back(Target); 933 int callArgSize = CS.arg_size(); 934 // #call args 935 args.push_back(Builder.getInt32(callArgSize)); 936 // unused 937 args.push_back(Builder.getInt32(0)); 938 // call parameters 939 args.insert(args.end(), CS.arg_begin(), CS.arg_end()); 940 // #deopt args: 0 941 args.push_back(Builder.getInt32(0)); 942 943 InvokeInst *toReplace = cast<InvokeInst>(CS.getInstruction()); 944 945 // Insert the new invoke into the old block. We'll remove the old one in a 946 // moment at which point this will become the new terminator for the 947 // original block. 948 InvokeInst *invoke = InvokeInst::Create( 949 gc_statepoint_decl, toReplace->getNormalDest(), 950 toReplace->getUnwindDest(), args, "", toReplace->getParent()); 951 invoke->setCallingConv(toReplace->getCallingConv()); 952 953 // Currently we will fail on parameter attributes and on certain 954 // function attributes. 955 AttributeSet new_attrs = toReplace->getAttributes(); 956 // In case if we can handle this set of sttributes - set up function attrs 957 // directly on statepoint and return attrs later for gc_result intrinsic. 958 invoke->setAttributes(new_attrs.getFnAttributes()); 959 return_attributes = new_attrs.getRetAttributes(); 960 961 token = invoke; 962 963 // We'll insert the gc.result into the normal block 964 BasicBlock *normalDest = normalizeBBForInvokeSafepoint( 965 toReplace->getNormalDest(), invoke->getParent()); 966 Instruction *IP = &*(normalDest->getFirstInsertionPt()); 967 Builder.SetInsertPoint(IP); 968 } else { 969 llvm_unreachable("unexpect type of CallSite"); 970 } 971 assert(token); 972 973 // Handle the return value of the original call - update all uses to use a 974 // gc_result hanging off the statepoint node we just inserted 975 976 // Only add the gc_result iff there is actually a used result 977 if (!CS.getType()->isVoidTy() && !CS.getInstruction()->use_empty()) { 978 std::string takenName = 979 CS.getInstruction()->hasName() ? CS.getInstruction()->getName() : ""; 980 CallInst *gc_result = 981 Builder.CreateGCResult(token, CS.getType(), takenName); 982 gc_result->setAttributes(return_attributes); 983 return gc_result; 984 } else { 985 // No return value for the call. 986 return nullptr; 987 } 988} 989