669 lines · cpp
1//===- SpillUtils.cpp - Utilities for checking for spills ---------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/Transforms/Coroutines/SpillUtils.h"10#include "CoroInternal.h"11#include "llvm/Analysis/CFG.h"12#include "llvm/Analysis/PtrUseVisitor.h"13#include "llvm/IR/CFG.h"14#include "llvm/IR/Constants.h"15#include "llvm/IR/DebugInfo.h"16#include "llvm/IR/Dominators.h"17#include "llvm/IR/InstIterator.h"18#include "llvm/Transforms/Utils/BasicBlockUtils.h"19 20using namespace llvm;21using namespace llvm::coro;22 23typedef SmallPtrSet<BasicBlock *, 8> VisitedBlocksSet;24 25static bool isNonSpilledIntrinsic(Instruction &I) {26 // Structural coroutine intrinsics that should not be spilled into the27 // coroutine frame.28 return isa<CoroIdInst>(&I) || isa<CoroSaveInst>(&I);29}30 31/// Does control flow starting at the given block ever reach a suspend32/// instruction before reaching a block in VisitedOrFreeBBs?33static bool isSuspendReachableFrom(BasicBlock *From,34 VisitedBlocksSet &VisitedOrFreeBBs) {35 // Eagerly try to add this block to the visited set. If it's already36 // there, stop recursing; this path doesn't reach a suspend before37 // either looping or reaching a freeing block.38 if (!VisitedOrFreeBBs.insert(From).second)39 return false;40 41 // We assume that we'll already have split suspends into their own blocks.42 if (coro::isSuspendBlock(From))43 return true;44 45 // Recurse on the successors.46 for (auto *Succ : successors(From)) {47 if (isSuspendReachableFrom(Succ, VisitedOrFreeBBs))48 return true;49 }50 51 return false;52}53 54/// Is the given alloca "local", i.e. bounded in lifetime to not cross a55/// suspend point?56static bool isLocalAlloca(CoroAllocaAllocInst *AI) {57 // Seed the visited set with all the basic blocks containing a free58 // so that we won't pass them up.59 VisitedBlocksSet VisitedOrFreeBBs;60 for (auto *User : AI->users()) {61 if (auto FI = dyn_cast<CoroAllocaFreeInst>(User))62 VisitedOrFreeBBs.insert(FI->getParent());63 }64 65 return !isSuspendReachableFrom(AI->getParent(), VisitedOrFreeBBs);66}67 68/// Turn the given coro.alloca.alloc call into a dynamic allocation.69/// This happens during the all-instructions iteration, so it must not70/// delete the call.71static Instruction *72lowerNonLocalAlloca(CoroAllocaAllocInst *AI, const Shape &Shape,73 SmallVectorImpl<Instruction *> &DeadInsts) {74 IRBuilder<> Builder(AI);75 auto Alloc = Shape.emitAlloc(Builder, AI->getSize(), nullptr);76 77 for (User *U : AI->users()) {78 if (isa<CoroAllocaGetInst>(U)) {79 U->replaceAllUsesWith(Alloc);80 } else {81 auto FI = cast<CoroAllocaFreeInst>(U);82 Builder.SetInsertPoint(FI);83 Shape.emitDealloc(Builder, Alloc, nullptr);84 }85 DeadInsts.push_back(cast<Instruction>(U));86 }87 88 // Push this on last so that it gets deleted after all the others.89 DeadInsts.push_back(AI);90 91 // Return the new allocation value so that we can check for needed spills.92 return cast<Instruction>(Alloc);93}94 95// We need to make room to insert a spill after initial PHIs, but before96// catchswitch instruction. Placing it before violates the requirement that97// catchswitch, like all other EHPads must be the first nonPHI in a block.98//99// Split away catchswitch into a separate block and insert in its place:100//101// cleanuppad <InsertPt> cleanupret.102//103// cleanupret instruction will act as an insert point for the spill.104static Instruction *splitBeforeCatchSwitch(CatchSwitchInst *CatchSwitch) {105 BasicBlock *CurrentBlock = CatchSwitch->getParent();106 BasicBlock *NewBlock = CurrentBlock->splitBasicBlock(CatchSwitch);107 CurrentBlock->getTerminator()->eraseFromParent();108 109 auto *CleanupPad =110 CleanupPadInst::Create(CatchSwitch->getParentPad(), {}, "", CurrentBlock);111 auto *CleanupRet =112 CleanupReturnInst::Create(CleanupPad, NewBlock, CurrentBlock);113 return CleanupRet;114}115 116// We use a pointer use visitor to track how an alloca is being used.117// The goal is to be able to answer the following three questions:118// 1. Should this alloca be allocated on the frame instead.119// 2. Could the content of the alloca be modified prior to CoroBegin, which120// would require copying the data from the alloca to the frame after121// CoroBegin.122// 3. Are there any aliases created for this alloca prior to CoroBegin, but123// used after CoroBegin. In that case, we will need to recreate the alias124// after CoroBegin based off the frame.125//126// To answer question 1, we track two things:127// A. List of all BasicBlocks that use this alloca or any of the aliases of128// the alloca. In the end, we check if there exists any two basic blocks that129// cross suspension points. If so, this alloca must be put on the frame.130// B. Whether the alloca or any alias of the alloca is escaped at some point,131// either by storing the address somewhere, or the address is used in a132// function call that might capture. If it's ever escaped, this alloca must be133// put on the frame conservatively.134//135// To answer quetion 2, we track through the variable MayWriteBeforeCoroBegin.136// Whenever a potential write happens, either through a store instruction, a137// function call or any of the memory intrinsics, we check whether this138// instruction is prior to CoroBegin.139//140// To answer question 3, we track the offsets of all aliases created for the141// alloca prior to CoroBegin but used after CoroBegin. std::optional is used to142// be able to represent the case when the offset is unknown (e.g. when you have143// a PHINode that takes in different offset values). We cannot handle unknown144// offsets and will assert. This is the potential issue left out. An ideal145// solution would likely require a significant redesign.146 147namespace {148struct AllocaUseVisitor : PtrUseVisitor<AllocaUseVisitor> {149 using Base = PtrUseVisitor<AllocaUseVisitor>;150 AllocaUseVisitor(const DataLayout &DL, const DominatorTree &DT,151 const coro::Shape &CoroShape,152 const SuspendCrossingInfo &Checker,153 bool ShouldUseLifetimeStartInfo)154 : PtrUseVisitor(DL), DT(DT), CoroShape(CoroShape), Checker(Checker),155 ShouldUseLifetimeStartInfo(ShouldUseLifetimeStartInfo) {156 for (AnyCoroSuspendInst *SuspendInst : CoroShape.CoroSuspends)157 CoroSuspendBBs.insert(SuspendInst->getParent());158 }159 160 void visit(Instruction &I) {161 Users.insert(&I);162 Base::visit(I);163 // If the pointer is escaped prior to CoroBegin, we have to assume it would164 // be written into before CoroBegin as well.165 if (PI.isEscaped() &&166 !DT.dominates(CoroShape.CoroBegin, PI.getEscapingInst())) {167 MayWriteBeforeCoroBegin = true;168 }169 }170 // We need to provide this overload as PtrUseVisitor uses a pointer based171 // visiting function.172 void visit(Instruction *I) { return visit(*I); }173 174 void visitPHINode(PHINode &I) {175 enqueueUsers(I);176 handleAlias(I);177 }178 179 void visitSelectInst(SelectInst &I) {180 enqueueUsers(I);181 handleAlias(I);182 }183 184 void visitInsertElementInst(InsertElementInst &I) {185 enqueueUsers(I);186 handleAlias(I);187 }188 189 void visitInsertValueInst(InsertValueInst &I) {190 enqueueUsers(I);191 handleAlias(I);192 }193 194 void visitStoreInst(StoreInst &SI) {195 // Regardless whether the alias of the alloca is the value operand or the196 // pointer operand, we need to assume the alloca is been written.197 handleMayWrite(SI);198 199 if (SI.getValueOperand() != U->get())200 return;201 202 // We are storing the pointer into a memory location, potentially escaping.203 // As an optimization, we try to detect simple cases where it doesn't204 // actually escape, for example:205 // %ptr = alloca ..206 // %addr = alloca ..207 // store %ptr, %addr208 // %x = load %addr209 // ..210 // If %addr is only used by loading from it, we could simply treat %x as211 // another alias of %ptr, and not considering %ptr being escaped.212 auto IsSimpleStoreThenLoad = [&]() {213 auto *AI = dyn_cast<AllocaInst>(SI.getPointerOperand());214 // If the memory location we are storing to is not an alloca, it215 // could be an alias of some other memory locations, which is difficult216 // to analyze.217 if (!AI)218 return false;219 // StoreAliases contains aliases of the memory location stored into.220 SmallVector<Instruction *, 4> StoreAliases = {AI};221 while (!StoreAliases.empty()) {222 Instruction *I = StoreAliases.pop_back_val();223 for (User *U : I->users()) {224 // If we are loading from the memory location, we are creating an225 // alias of the original pointer.226 if (auto *LI = dyn_cast<LoadInst>(U)) {227 enqueueUsers(*LI);228 handleAlias(*LI);229 continue;230 }231 // If we are overriding the memory location, the pointer certainly232 // won't escape.233 if (auto *S = dyn_cast<StoreInst>(U))234 if (S->getPointerOperand() == I)235 continue;236 if (isa<LifetimeIntrinsic>(U))237 continue;238 // BitCastInst creats aliases of the memory location being stored239 // into.240 if (auto *BI = dyn_cast<BitCastInst>(U)) {241 StoreAliases.push_back(BI);242 continue;243 }244 return false;245 }246 }247 248 return true;249 };250 251 if (!IsSimpleStoreThenLoad())252 PI.setEscaped(&SI);253 }254 255 // All mem intrinsics modify the data.256 void visitMemIntrinsic(MemIntrinsic &MI) { handleMayWrite(MI); }257 258 void visitBitCastInst(BitCastInst &BC) {259 Base::visitBitCastInst(BC);260 handleAlias(BC);261 }262 263 void visitAddrSpaceCastInst(AddrSpaceCastInst &ASC) {264 Base::visitAddrSpaceCastInst(ASC);265 handleAlias(ASC);266 }267 268 void visitGetElementPtrInst(GetElementPtrInst &GEPI) {269 // The base visitor will adjust Offset accordingly.270 Base::visitGetElementPtrInst(GEPI);271 handleAlias(GEPI);272 }273 274 void visitIntrinsicInst(IntrinsicInst &II) {275 switch (II.getIntrinsicID()) {276 default:277 return Base::visitIntrinsicInst(II);278 case Intrinsic::lifetime_start:279 LifetimeStarts.insert(&II);280 LifetimeStartBBs.push_back(II.getParent());281 break;282 case Intrinsic::lifetime_end:283 LifetimeEndBBs.insert(II.getParent());284 break;285 }286 }287 288 void visitCallBase(CallBase &CB) {289 for (unsigned Op = 0, OpCount = CB.arg_size(); Op < OpCount; ++Op)290 if (U->get() == CB.getArgOperand(Op) && !CB.doesNotCapture(Op))291 PI.setEscaped(&CB);292 handleMayWrite(CB);293 }294 295 bool getShouldLiveOnFrame() const {296 if (!ShouldLiveOnFrame)297 ShouldLiveOnFrame = computeShouldLiveOnFrame(/*BareEscapeForcesFrame=*/true);298 return *ShouldLiveOnFrame;299 }300 301 /// Whether the alloca is *actually* live across a suspend point, based on its302 /// lifetime markers and uses, ignoring the conservative rule that a bare303 /// escape (the address handed to a call, with no use live across a suspend)304 /// forces it onto the frame. A dynamically sized alloca can never be305 /// materialized as a fixed coroutine-frame field, so we use this precise306 /// query to tell apart "must be on the frame, hence unsupported" from "merely307 /// escaped but does not outlive any suspend, hence can stay a normal stack308 /// alloca in the ramp function".309 bool getDefinitelyLiveAcrossSuspend() const {310 return computeShouldLiveOnFrame(/*BareEscapeForcesFrame=*/false);311 }312 313 bool getMayWriteBeforeCoroBegin() const { return MayWriteBeforeCoroBegin; }314 315 DenseMap<Instruction *, std::optional<APInt>> getAliasesCopy() const {316 assert(getShouldLiveOnFrame() && "This method should only be called if the "317 "alloca needs to live on the frame.");318 for (const auto &P : AliasOffetMap)319 if (!P.second)320 report_fatal_error("Unable to handle an alias with unknown offset "321 "created before CoroBegin.");322 return AliasOffetMap;323 }324 325private:326 const DominatorTree &DT;327 const coro::Shape &CoroShape;328 const SuspendCrossingInfo &Checker;329 // All alias to the original AllocaInst, created before CoroBegin and used330 // after CoroBegin. Each entry contains the instruction and the offset in the331 // original Alloca. They need to be recreated after CoroBegin off the frame.332 DenseMap<Instruction *, std::optional<APInt>> AliasOffetMap{};333 SmallPtrSet<Instruction *, 4> Users{};334 SmallPtrSet<IntrinsicInst *, 2> LifetimeStarts{};335 SmallVector<BasicBlock *> LifetimeStartBBs{};336 SmallPtrSet<BasicBlock *, 2> LifetimeEndBBs{};337 SmallPtrSet<const BasicBlock *, 2> CoroSuspendBBs{};338 bool MayWriteBeforeCoroBegin{false};339 bool ShouldUseLifetimeStartInfo{true};340 341 mutable std::optional<bool> ShouldLiveOnFrame{};342 343 // When \p BareEscapeForcesFrame is true (the default for frame-membership344 // decisions), an escaped alloca with no lifetime information is treated as345 // frame-resident even if none of its uses are live across a suspend. When346 // false, only an actual across-suspend use/lifetime forces the frame; this347 // precise variant is used to decide dynamically sized allocas.348 bool computeShouldLiveOnFrame(bool BareEscapeForcesFrame) const {349 // If lifetime information is available, we check it first since it's350 // more precise. We look at every pair of lifetime.start intrinsic and351 // every basic block that uses the pointer to see if they cross suspension352 // points. The uses cover both direct uses as well as indirect uses.353 if (ShouldUseLifetimeStartInfo && !LifetimeStarts.empty()) {354 // If there is no explicit lifetime.end, then assume the address can355 // cross suspension points.356 if (LifetimeEndBBs.empty())357 return true;358 359 // If there is a path from a lifetime.start to a suspend without a360 // corresponding lifetime.end, then the alloca's lifetime persists361 // beyond that suspension point and the alloca must go on the frame.362 llvm::SmallVector<BasicBlock *> Worklist(LifetimeStartBBs);363 if (isManyPotentiallyReachableFromMany(Worklist, CoroSuspendBBs,364 &LifetimeEndBBs, &DT))365 return true;366 367 // Addresses are guaranteed to be identical after every lifetime.start so368 // we cannot use the local stack if the address escaped and there is a369 // suspend point between lifetime markers. This should also cover the370 // case of a single lifetime.start intrinsic in a loop with suspend point.371 if (PI.isEscaped()) {372 for (auto *A : LifetimeStarts) {373 for (auto *B : LifetimeStarts) {374 if (Checker.hasPathOrLoopCrossingSuspendPoint(A->getParent(),375 B->getParent()))376 return true;377 }378 }379 }380 return false;381 }382 // FIXME: Ideally the isEscaped check should come at the beginning.383 // However there are a few loose ends that need to be fixed first before384 // we can do that. We need to make sure we are not over-conservative, so385 // that the data accessed in-between await_suspend and symmetric transfer386 // is always put on the stack, and also data accessed after coro.end is387 // always put on the stack (esp the return object). To fix that, we need388 // to:389 // 1) Potentially treat sret as nocapture in calls390 // 2) Special handle the return object and put it on the stack391 // 3) Utilize lifetime.end intrinsic392 if (BareEscapeForcesFrame && PI.isEscaped())393 return true;394 395 for (auto *U1 : Users)396 for (auto *U2 : Users)397 if (Checker.isDefinitionAcrossSuspend(*U1, U2))398 return true;399 400 return false;401 }402 403 void handleMayWrite(const Instruction &I) {404 if (!DT.dominates(CoroShape.CoroBegin, &I))405 MayWriteBeforeCoroBegin = true;406 }407 408 bool usedAfterCoroBegin(Instruction &I) {409 for (auto &U : I.uses())410 if (DT.dominates(CoroShape.CoroBegin, U))411 return true;412 return false;413 }414 415 void handleAlias(Instruction &I) {416 // We track all aliases created prior to CoroBegin but used after.417 // These aliases may need to be recreated after CoroBegin if the alloca418 // need to live on the frame.419 if (DT.dominates(CoroShape.CoroBegin, &I) || !usedAfterCoroBegin(I))420 return;421 422 if (!IsOffsetKnown) {423 AliasOffetMap[&I].reset();424 } else {425 auto [Itr, Inserted] = AliasOffetMap.try_emplace(&I, Offset);426 if (!Inserted && Itr->second && *Itr->second != Offset) {427 // If we have seen two different possible values for this alias, we set428 // it to empty.429 Itr->second.reset();430 }431 }432 }433};434} // namespace435 436static void collectFrameAlloca(AllocaInst *AI, const coro::Shape &Shape,437 const SuspendCrossingInfo &Checker,438 SmallVectorImpl<AllocaInfo> &Allocas,439 const DominatorTree &DT) {440 if (Shape.CoroSuspends.empty())441 return;442 443 // The PromiseAlloca will be specially handled since it needs to be in a444 // fixed position in the frame.445 if (AI == Shape.SwitchLowering.PromiseAlloca)446 return;447 448 // The __coro_gro alloca should outlive the promise, make sure we449 // keep it outside the frame.450 if (AI->hasMetadata(LLVMContext::MD_coro_outside_frame))451 return;452 453 // The code that uses lifetime.start intrinsic does not work for functions454 // with loops without exit. Disable it on ABIs we know to generate such455 // code.456 bool ShouldUseLifetimeStartInfo =457 (Shape.ABI != coro::ABI::Async && Shape.ABI != coro::ABI::Retcon &&458 Shape.ABI != coro::ABI::RetconOnce);459 AllocaUseVisitor Visitor{AI->getDataLayout(), DT, Shape, Checker,460 ShouldUseLifetimeStartInfo};461 Visitor.visitPtr(*AI);462 if (!Visitor.getShouldLiveOnFrame())463 return;464 465 // A dynamically sized alloca (a C VLA / __builtin_alloca with a non-constant466 // element count) cannot be materialized as a fixed coroutine-frame field: the467 // frame layout is computed once, at coro.begin, but the size is only known at468 // run time. getShouldLiveOnFrame() conservatively reports such an alloca as469 // frame-resident as soon as its address merely *escapes* (e.g. it is handed470 // by pointer to a call), even when none of its uses are actually live across a471 // suspend point. Collecting it would feed a non-constant-sized alloca to472 // FrameTypeBuilder, whose addFieldForAllocas sort calls473 // AllocaInst::getAllocationSize() -- which returns std::nullopt for a VLA --474 // and then (asserts off) dereferences the empty optional, corrupting the sort475 // comparator and crashing (SIGSEGV); with asserts it trips the "Coroutines476 // cannot handle non static allocas yet" fatal.477 //478 // If the VLA does not actually live across a suspend, it does not belong on479 // the frame at all: it stays an ordinary stack alloca in the ramp function480 // (all of its uses execute before the first suspend), so simply do not collect481 // it. If it genuinely is live across a suspend, it is an unsupported shape --482 // fail loudly here (never-silent) rather than crashing deep inside frame483 // construction.484 if (AI->isArrayAllocation() && !isa<ConstantInt>(AI->getArraySize())) {485 if (!Visitor.getDefinitelyLiveAcrossSuspend())486 return;487 report_fatal_error(488 "coro-split: a dynamically sized alloca that is live across a suspend "489 "point cannot be placed on the coroutine frame");490 }491 492 Allocas.emplace_back(AI, Visitor.getAliasesCopy(),493 Visitor.getMayWriteBeforeCoroBegin());494}495 496void coro::collectSpillsFromArgs(SpillInfo &Spills, Function &F,497 const SuspendCrossingInfo &Checker) {498 // Collect the spills for arguments and other not-materializable values.499 for (Argument &A : F.args())500 for (User *U : A.users())501 if (Checker.isDefinitionAcrossSuspend(A, U))502 Spills[&A].push_back(cast<Instruction>(U));503}504 505void coro::collectSpillsAndAllocasFromInsts(506 SpillInfo &Spills, SmallVector<AllocaInfo, 8> &Allocas,507 SmallVector<Instruction *, 4> &DeadInstructions,508 SmallVector<CoroAllocaAllocInst *, 4> &LocalAllocas, Function &F,509 const SuspendCrossingInfo &Checker, const DominatorTree &DT,510 const coro::Shape &Shape) {511 512 for (Instruction &I : instructions(F)) {513 // Values returned from coroutine structure intrinsics should not be part514 // of the Coroutine Frame.515 if (isNonSpilledIntrinsic(I) || &I == Shape.CoroBegin)516 continue;517 518 // Handle alloca.alloc specially here.519 if (auto AI = dyn_cast<CoroAllocaAllocInst>(&I)) {520 // Check whether the alloca's lifetime is bounded by suspend points.521 if (isLocalAlloca(AI)) {522 LocalAllocas.push_back(AI);523 continue;524 }525 526 // If not, do a quick rewrite of the alloca and then add spills of527 // the rewritten value. The rewrite doesn't invalidate anything in528 // Spills because the other alloca intrinsics have no other operands529 // besides AI, and it doesn't invalidate the iteration because we delay530 // erasing AI.531 auto Alloc = lowerNonLocalAlloca(AI, Shape, DeadInstructions);532 533 for (User *U : Alloc->users()) {534 if (Checker.isDefinitionAcrossSuspend(*Alloc, U))535 Spills[Alloc].push_back(cast<Instruction>(U));536 }537 continue;538 }539 540 // Ignore alloca.get; we process this as part of coro.alloca.alloc.541 if (isa<CoroAllocaGetInst>(I))542 continue;543 544 if (auto *AI = dyn_cast<AllocaInst>(&I)) {545 collectFrameAlloca(AI, Shape, Checker, Allocas, DT);546 continue;547 }548 549 for (User *U : I.users())550 if (Checker.isDefinitionAcrossSuspend(I, U)) {551 // We cannot spill a token.552 if (I.getType()->isTokenTy())553 report_fatal_error(554 "token definition is separated from the use by a suspend point");555 Spills[&I].push_back(cast<Instruction>(U));556 }557 }558}559 560void coro::collectSpillsFromDbgInfo(SpillInfo &Spills, Function &F,561 const SuspendCrossingInfo &Checker) {562 // We don't want the layout of coroutine frame to be affected563 // by debug information. So we only choose to salvage dbg.values for564 // whose value is already in the frame.565 // We would handle the dbg.values for allocas specially566 for (auto &Iter : Spills) {567 auto *V = Iter.first;568 SmallVector<DbgVariableRecord *, 16> DVRs;569 findDbgValues(V, DVRs);570 // Add the instructions which carry debug info that is in the frame.571 for (DbgVariableRecord *DVR : DVRs)572 if (Checker.isDefinitionAcrossSuspend(*V, DVR->Marker->MarkedInstr))573 Spills[V].push_back(DVR->Marker->MarkedInstr);574 }575}576 577/// Async and Retcon{Once} conventions assume that all spill uses can be sunk578/// after the coro.begin intrinsic.579void coro::sinkSpillUsesAfterCoroBegin(580 const DominatorTree &Dom, CoroBeginInst *CoroBegin, coro::SpillInfo &Spills,581 SmallVectorImpl<coro::AllocaInfo> &Allocas) {582 SmallSetVector<Instruction *, 32> ToMove;583 SmallVector<Instruction *, 32> Worklist;584 585 // Collect all users that precede coro.begin.586 auto collectUsers = [&](Value *Def) {587 for (User *U : Def->users()) {588 auto Inst = cast<Instruction>(U);589 if (Inst->getParent() != CoroBegin->getParent() ||590 Dom.dominates(CoroBegin, Inst))591 continue;592 if (ToMove.insert(Inst))593 Worklist.push_back(Inst);594 }595 };596 for (auto &I : Spills)597 collectUsers(I.first);598 for (auto &I : Allocas)599 collectUsers(I.Alloca);600 601 // Recursively collect users before coro.begin.602 while (!Worklist.empty()) {603 auto *Def = Worklist.pop_back_val();604 for (User *U : Def->users()) {605 auto Inst = cast<Instruction>(U);606 if (Dom.dominates(CoroBegin, Inst))607 continue;608 if (ToMove.insert(Inst))609 Worklist.push_back(Inst);610 }611 }612 613 // Sort by dominance.614 SmallVector<Instruction *, 64> InsertionList(ToMove.begin(), ToMove.end());615 llvm::sort(InsertionList, [&Dom](Instruction *A, Instruction *B) -> bool {616 // If a dominates b it should precede (<) b.617 return Dom.dominates(A, B);618 });619 620 Instruction *InsertPt = CoroBegin->getNextNode();621 for (Instruction *Inst : InsertionList)622 Inst->moveBefore(InsertPt->getIterator());623}624 625BasicBlock::iterator coro::getSpillInsertionPt(const coro::Shape &Shape,626 Value *Def,627 const DominatorTree &DT) {628 BasicBlock::iterator InsertPt;629 if (auto *Arg = dyn_cast<Argument>(Def)) {630 // For arguments, we will place the store instruction right after631 // the coroutine frame pointer instruction, i.e. coro.begin.632 InsertPt = Shape.getInsertPtAfterFramePtr();633 634 // If we're spilling an Argument, make sure we clear 'captures'635 // from the coroutine function.636 Arg->getParent()->removeParamAttr(Arg->getArgNo(), Attribute::Captures);637 } else if (auto *CSI = dyn_cast<AnyCoroSuspendInst>(Def)) {638 // Don't spill immediately after a suspend; splitting assumes639 // that the suspend will be followed by a branch.640 InsertPt = CSI->getParent()->getSingleSuccessor()->getFirstNonPHIIt();641 } else {642 auto *I = cast<Instruction>(Def);643 if (!DT.dominates(Shape.CoroBegin, I)) {644 // If it is not dominated by CoroBegin, then spill should be645 // inserted immediately after CoroFrame is computed.646 InsertPt = Shape.getInsertPtAfterFramePtr();647 } else if (auto *II = dyn_cast<InvokeInst>(I)) {648 // If we are spilling the result of the invoke instruction, split649 // the normal edge and insert the spill in the new block.650 auto *NewBB = SplitEdge(II->getParent(), II->getNormalDest());651 InsertPt = NewBB->getTerminator()->getIterator();652 } else if (isa<PHINode>(I)) {653 // Skip the PHINodes and EH pads instructions.654 BasicBlock *DefBlock = I->getParent();655 if (auto *CSI = dyn_cast<CatchSwitchInst>(DefBlock->getTerminator()))656 InsertPt = splitBeforeCatchSwitch(CSI)->getIterator();657 else658 InsertPt = DefBlock->getFirstInsertionPt();659 } else {660 assert(!I->isTerminator() && "unexpected terminator");661 // For all other values, the spill is placed immediately after662 // the definition.663 InsertPt = I->getNextNode()->getIterator();664 }665 }666 667 return InsertPt;668}669