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-exception
6//
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/DebugInfo.h"
15#include "llvm/IR/Dominators.h"
16#include "llvm/IR/InstIterator.h"
17#include "llvm/Transforms/Utils/BasicBlockUtils.h"
18
19using namespace llvm;
20using namespace llvm::coro;
21
22typedef SmallPtrSet<BasicBlock *, 8> VisitedBlocksSet;
23
24static bool isNonSpilledIntrinsic(Instruction &I) {
25 // Structural coroutine intrinsics that should not be spilled into the
26 // coroutine frame.
27 return isa<CoroIdInst>(Val: &I) || isa<CoroSaveInst>(Val: &I);
28}
29
30/// Does control flow starting at the given block ever reach a suspend
31/// instruction before reaching a block in VisitedOrFreeBBs?
32static bool isSuspendReachableFrom(BasicBlock *From,
33 VisitedBlocksSet &VisitedOrFreeBBs) {
34 // Eagerly try to add this block to the visited set. If it's already
35 // there, stop recursing; this path doesn't reach a suspend before
36 // either looping or reaching a freeing block.
37 if (!VisitedOrFreeBBs.insert(Ptr: From).second)
38 return false;
39
40 // We assume that we'll already have split suspends into their own blocks.
41 if (coro::isSuspendBlock(BB: From))
42 return true;
43
44 // Recurse on the successors.
45 for (auto *Succ : successors(BB: From)) {
46 if (isSuspendReachableFrom(From: Succ, VisitedOrFreeBBs))
47 return true;
48 }
49
50 return false;
51}
52
53/// Is the given alloca "local", i.e. bounded in lifetime to not cross a
54/// suspend point?
55static bool isLocalAlloca(CoroAllocaAllocInst *AI) {
56 // Seed the visited set with all the basic blocks containing a free
57 // so that we won't pass them up.
58 VisitedBlocksSet VisitedOrFreeBBs;
59 for (auto *User : AI->users()) {
60 if (auto FI = dyn_cast<CoroAllocaFreeInst>(Val: User))
61 VisitedOrFreeBBs.insert(Ptr: FI->getParent());
62 }
63
64 return !isSuspendReachableFrom(From: AI->getParent(), VisitedOrFreeBBs);
65}
66
67/// Turn the given coro.alloca.alloc call into a dynamic allocation.
68/// This happens during the all-instructions iteration, so it must not
69/// delete the call.
70static Instruction *
71lowerNonLocalAlloca(CoroAllocaAllocInst *AI, const Shape &Shape,
72 SmallVectorImpl<Instruction *> &DeadInsts) {
73 IRBuilder<> Builder(AI);
74 auto Alloc = Shape.emitAlloc(Builder, Size: AI->getSize(), CG: nullptr);
75
76 for (User *U : AI->users()) {
77 if (isa<CoroAllocaGetInst>(Val: U)) {
78 U->replaceAllUsesWith(V: Alloc);
79 } else {
80 auto FI = cast<CoroAllocaFreeInst>(Val: U);
81 Builder.SetInsertPoint(FI);
82 Shape.emitDealloc(Builder, Ptr: Alloc, CG: nullptr);
83 }
84 DeadInsts.push_back(Elt: cast<Instruction>(Val: U));
85 }
86
87 // Push this on last so that it gets deleted after all the others.
88 DeadInsts.push_back(Elt: AI);
89
90 // Return the new allocation value so that we can check for needed spills.
91 return cast<Instruction>(Val: Alloc);
92}
93
94// We need to make room to insert a spill after initial PHIs, but before
95// catchswitch instruction. Placing it before violates the requirement that
96// catchswitch, like all other EHPads must be the first nonPHI in a block.
97//
98// Split away catchswitch into a separate block and insert in its place:
99//
100// cleanuppad <InsertPt> cleanupret.
101//
102// cleanupret instruction will act as an insert point for the spill.
103static Instruction *splitBeforeCatchSwitch(CatchSwitchInst *CatchSwitch) {
104 BasicBlock *CurrentBlock = CatchSwitch->getParent();
105 BasicBlock *NewBlock = CurrentBlock->splitBasicBlock(I: CatchSwitch);
106 CurrentBlock->getTerminator()->eraseFromParent();
107
108 auto *CleanupPad =
109 CleanupPadInst::Create(ParentPad: CatchSwitch->getParentPad(), Args: {}, NameStr: "", InsertBefore: CurrentBlock);
110 auto *CleanupRet =
111 CleanupReturnInst::Create(CleanupPad, UnwindBB: NewBlock, InsertBefore: CurrentBlock);
112 return CleanupRet;
113}
114
115// We use a pointer use visitor to track how an alloca is being used.
116// The goal is to be able to answer the following three questions:
117// 1. Should this alloca be allocated on the frame instead.
118// 2. Could the content of the alloca be modified prior to CoroBegin, which
119// would require copying the data from the alloca to the frame after
120// CoroBegin.
121// 3. Are there any aliases created for this alloca prior to CoroBegin, but
122// used after CoroBegin. In that case, we will need to recreate the alias
123// after CoroBegin based off the frame.
124//
125// To answer question 1, we track two things:
126// A. List of all BasicBlocks that use this alloca or any of the aliases of
127// the alloca. In the end, we check if there exists any two basic blocks that
128// cross suspension points. If so, this alloca must be put on the frame.
129// B. Whether the alloca or any alias of the alloca is escaped at some point,
130// either by storing the address somewhere, or the address is used in a
131// function call that might capture. If it's ever escaped, this alloca must be
132// put on the frame conservatively.
133//
134// To answer quetion 2, we track through the variable MayWriteBeforeCoroBegin.
135// Whenever a potential write happens, either through a store instruction, a
136// function call or any of the memory intrinsics, we check whether this
137// instruction is prior to CoroBegin.
138//
139// To answer question 3, we track the offsets of all aliases created for the
140// alloca prior to CoroBegin but used after CoroBegin. std::optional is used to
141// be able to represent the case when the offset is unknown (e.g. when you have
142// a PHINode that takes in different offset values). We cannot handle unknown
143// offsets and will assert. This is the potential issue left out. An ideal
144// solution would likely require a significant redesign.
145
146namespace {
147struct AllocaUseVisitor : PtrUseVisitor<AllocaUseVisitor> {
148 using Base = PtrUseVisitor<AllocaUseVisitor>;
149 AllocaUseVisitor(const DataLayout &DL, const DominatorTree &DT,
150 const coro::Shape &CoroShape,
151 const SuspendCrossingInfo &Checker,
152 bool ShouldUseLifetimeStartInfo)
153 : PtrUseVisitor(DL), DT(DT), CoroShape(CoroShape), Checker(Checker),
154 ShouldUseLifetimeStartInfo(ShouldUseLifetimeStartInfo) {
155 for (AnyCoroSuspendInst *SuspendInst : CoroShape.CoroSuspends)
156 CoroSuspendBBs.insert(Ptr: SuspendInst->getParent());
157 }
158
159 void visit(Instruction &I) {
160 Users.insert(Ptr: &I);
161 Base::visit(I);
162 // If the pointer is escaped prior to CoroBegin, we have to assume it would
163 // be written into before CoroBegin as well.
164 if (PI.isEscaped() &&
165 !DT.dominates(Def: CoroShape.CoroBegin, User: PI.getEscapingInst())) {
166 MayWriteBeforeCoroBegin = true;
167 }
168 }
169 // We need to provide this overload as PtrUseVisitor uses a pointer based
170 // visiting function.
171 void visit(Instruction *I) { return visit(I&: *I); }
172
173 void visitPHINode(PHINode &I) {
174 enqueueUsers(I);
175 handleAlias(I);
176 }
177
178 void visitSelectInst(SelectInst &I) {
179 enqueueUsers(I);
180 handleAlias(I);
181 }
182
183 void visitCatchPadInst(CatchPadInst &I) {
184 // Windows EH requires exception objects allocated on the stack,
185 // shortcut the traversal and keep it on stack.
186 ShouldLiveOnFrame = false;
187 Base::Worklist.clear();
188 }
189
190 void visitInsertElementInst(InsertElementInst &I) {
191 enqueueUsers(I);
192 handleAlias(I);
193 }
194
195 void visitInsertValueInst(InsertValueInst &I) {
196 enqueueUsers(I);
197 handleAlias(I);
198 }
199
200 void visitStoreInst(StoreInst &SI) {
201 // Regardless whether the alias of the alloca is the value operand or the
202 // pointer operand, we need to assume the alloca is been written.
203 handleMayWrite(I: SI);
204
205 if (SI.getValueOperand() != U->get())
206 return;
207
208 // We are storing the pointer into a memory location, potentially escaping.
209 // As an optimization, we try to detect simple cases where it doesn't
210 // actually escape, for example:
211 // %ptr = alloca ..
212 // %addr = alloca ..
213 // store %ptr, %addr
214 // %x = load %addr
215 // ..
216 // If %addr is only used by loading from it, we could simply treat %x as
217 // another alias of %ptr, and not considering %ptr being escaped.
218 auto IsSimpleStoreThenLoad = [&]() {
219 auto *AI = dyn_cast<AllocaInst>(Val: SI.getPointerOperand());
220 // If the memory location we are storing to is not an alloca, it
221 // could be an alias of some other memory locations, which is difficult
222 // to analyze.
223 if (!AI)
224 return false;
225 // StoreAliases contains aliases of the memory location stored into.
226 SmallVector<Instruction *, 4> StoreAliases = {AI};
227 while (!StoreAliases.empty()) {
228 Instruction *I = StoreAliases.pop_back_val();
229 for (User *U : I->users()) {
230 // If we are loading from the memory location, we are creating an
231 // alias of the original pointer.
232 if (auto *LI = dyn_cast<LoadInst>(Val: U)) {
233 enqueueUsers(I&: *LI);
234 handleAlias(I&: *LI);
235 continue;
236 }
237 // If we are overriding the memory location, the pointer certainly
238 // won't escape.
239 if (auto *S = dyn_cast<StoreInst>(Val: U))
240 if (S->getPointerOperand() == I)
241 continue;
242 if (isa<LifetimeIntrinsic>(Val: U))
243 continue;
244 // BitCastInst creats aliases of the memory location being stored
245 // into.
246 if (auto *BI = dyn_cast<BitCastInst>(Val: U)) {
247 StoreAliases.push_back(Elt: BI);
248 continue;
249 }
250 return false;
251 }
252 }
253
254 return true;
255 };
256
257 if (!IsSimpleStoreThenLoad())
258 PI.setEscaped(&SI);
259 }
260
261 // All mem intrinsics modify the data.
262 void visitMemIntrinsic(MemIntrinsic &MI) { handleMayWrite(I: MI); }
263
264 void visitBitCastInst(BitCastInst &BC) {
265 Base::visitBitCastInst(BC);
266 handleAlias(I&: BC);
267 }
268
269 void visitAddrSpaceCastInst(AddrSpaceCastInst &ASC) {
270 Base::visitAddrSpaceCastInst(ASC);
271 handleAlias(I&: ASC);
272 }
273
274 void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
275 // The base visitor will adjust Offset accordingly.
276 Base::visitGetElementPtrInst(GEPI);
277 handleAlias(I&: GEPI);
278 }
279
280 void visitIntrinsicInst(IntrinsicInst &II) {
281 switch (II.getIntrinsicID()) {
282 default:
283 return Base::visitIntrinsicInst(II);
284 case Intrinsic::lifetime_start:
285 LifetimeStarts.insert(Ptr: &II);
286 LifetimeStartBBs.push_back(Elt: II.getParent());
287 break;
288 case Intrinsic::lifetime_end:
289 LifetimeEndBBs.insert(Ptr: II.getParent());
290 break;
291 }
292 }
293
294 void visitCallBase(CallBase &CB) {
295 for (unsigned Op = 0, OpCount = CB.arg_size(); Op < OpCount; ++Op)
296 if (U->get() == CB.getArgOperand(i: Op) && !CB.doesNotCapture(OpNo: Op))
297 PI.setEscaped(&CB);
298 handleMayWrite(I: CB);
299 }
300
301 bool getShouldLiveOnFrame() const {
302 if (!ShouldLiveOnFrame)
303 ShouldLiveOnFrame = computeShouldLiveOnFrame();
304 return *ShouldLiveOnFrame;
305 }
306
307 bool getMayWriteBeforeCoroBegin() const { return MayWriteBeforeCoroBegin; }
308
309 SmallMapVector<Instruction *, std::optional<APInt>, 4>
310 getAliasesCopy() const {
311 assert(getShouldLiveOnFrame() && "This method should only be called if the "
312 "alloca needs to live on the frame.");
313 for (const auto &P : AliasOffetMap)
314 if (!P.second)
315 report_fatal_error(reason: "Unable to handle an alias with unknown offset "
316 "created before CoroBegin.");
317 return AliasOffetMap;
318 }
319
320private:
321 const DominatorTree &DT;
322 const coro::Shape &CoroShape;
323 const SuspendCrossingInfo &Checker;
324 // All alias to the original AllocaInst, created before CoroBegin and used
325 // after CoroBegin. Each entry contains the instruction and the offset in the
326 // original Alloca. They need to be recreated after CoroBegin off the frame.
327 SmallMapVector<Instruction *, std::optional<APInt>, 4> AliasOffetMap{};
328 SmallPtrSet<Instruction *, 4> Users{};
329 SmallPtrSet<IntrinsicInst *, 2> LifetimeStarts{};
330 SmallVector<BasicBlock *> LifetimeStartBBs{};
331 SmallPtrSet<BasicBlock *, 2> LifetimeEndBBs{};
332 SmallPtrSet<const BasicBlock *, 2> CoroSuspendBBs{};
333 bool MayWriteBeforeCoroBegin{false};
334 bool ShouldUseLifetimeStartInfo{true};
335
336 mutable std::optional<bool> ShouldLiveOnFrame{};
337
338 bool computeShouldLiveOnFrame() const {
339 // If lifetime information is available, we check it first since it's
340 // more precise. We look at every pair of lifetime.start intrinsic and
341 // every basic block that uses the pointer to see if they cross suspension
342 // points. The uses cover both direct uses as well as indirect uses.
343 if (ShouldUseLifetimeStartInfo && !LifetimeStarts.empty()) {
344 // If there is no explicit lifetime.end, then assume the address can
345 // cross suspension points.
346 if (LifetimeEndBBs.empty())
347 return true;
348
349 // If there is a path from a lifetime.start to a suspend without a
350 // corresponding lifetime.end, then the alloca's lifetime persists
351 // beyond that suspension point and the alloca must go on the frame.
352 llvm::SmallVector<BasicBlock *> Worklist(LifetimeStartBBs);
353 if (isManyPotentiallyReachableFromMany(Worklist, StopSet: CoroSuspendBBs,
354 ExclusionSet: &LifetimeEndBBs, DT: &DT))
355 return true;
356
357 // Addresses are guaranteed to be identical after every lifetime.start so
358 // we cannot use the local stack if the address escaped and there is a
359 // suspend point between lifetime markers. This should also cover the
360 // case of a single lifetime.start intrinsic in a loop with suspend point.
361 if (PI.isEscaped()) {
362 for (auto *A : LifetimeStarts) {
363 for (auto *B : LifetimeStarts) {
364 if (Checker.hasPathOrLoopCrossingSuspendPoint(From: A->getParent(),
365 To: B->getParent()))
366 return true;
367 }
368 }
369 }
370 return false;
371 }
372 // FIXME: Ideally the isEscaped check should come at the beginning.
373 // However there are a few loose ends that need to be fixed first before
374 // we can do that. We need to make sure we are not over-conservative, so
375 // that the data accessed in-between await_suspend and symmetric transfer
376 // is always put on the stack, and also data accessed after coro.end is
377 // always put on the stack (esp the return object). To fix that, we need
378 // to:
379 // 1) Potentially treat sret as nocapture in calls
380 // 2) Special handle the return object and put it on the stack
381 // 3) Utilize lifetime.end intrinsic
382 if (PI.isEscaped())
383 return true;
384
385 for (auto *U1 : Users)
386 for (auto *U2 : Users)
387 if (Checker.isDefinitionAcrossSuspend(I&: *U1, U: U2))
388 return true;
389
390 return false;
391 }
392
393 void handleMayWrite(const Instruction &I) {
394 if (!DT.dominates(Def: CoroShape.CoroBegin, User: &I))
395 MayWriteBeforeCoroBegin = true;
396 }
397
398 bool usedAfterCoroBegin(Instruction &I) {
399 for (auto &U : I.uses())
400 if (DT.dominates(Def: CoroShape.CoroBegin, U))
401 return true;
402 return false;
403 }
404
405 void handleAlias(Instruction &I) {
406 // We track all aliases created prior to CoroBegin but used after.
407 // These aliases may need to be recreated after CoroBegin if the alloca
408 // need to live on the frame.
409 if (DT.dominates(Def: CoroShape.CoroBegin, User: &I) || !usedAfterCoroBegin(I))
410 return;
411
412 if (!IsOffsetKnown) {
413 AliasOffetMap[&I].reset();
414 } else {
415 auto [Itr, Inserted] = AliasOffetMap.try_emplace(Key: &I, Args&: Offset);
416 if (!Inserted && Itr->second && *Itr->second != Offset) {
417 // If we have seen two different possible values for this alias, we set
418 // it to empty.
419 Itr->second.reset();
420 }
421 }
422 }
423};
424} // namespace
425
426static void collectFrameAlloca(AllocaInst *AI, const coro::Shape &Shape,
427 const SuspendCrossingInfo &Checker,
428 SmallVectorImpl<AllocaInfo> &Allocas,
429 const DominatorTree &DT) {
430 if (Shape.CoroSuspends.empty())
431 return;
432
433 // The PromiseAlloca will be specially handled since it needs to be in a
434 // fixed position in the frame.
435 if (AI == Shape.SwitchLowering.PromiseAlloca)
436 return;
437
438 // The __coro_gro alloca should outlive the promise, make sure we
439 // keep it outside the frame.
440 if (AI->hasMetadata(KindID: LLVMContext::MD_coro_outside_frame))
441 return;
442
443 // The code that uses lifetime.start intrinsic does not work for functions
444 // with loops without exit. Disable it on ABIs we know to generate such
445 // code.
446 bool ShouldUseLifetimeStartInfo =
447 (Shape.ABI != coro::ABI::Async && Shape.ABI != coro::ABI::Retcon &&
448 Shape.ABI != coro::ABI::RetconOnce);
449 AllocaUseVisitor Visitor{AI->getDataLayout(), DT, Shape, Checker,
450 ShouldUseLifetimeStartInfo};
451 Visitor.visitPtr(I&: *AI);
452 if (!Visitor.getShouldLiveOnFrame())
453 return;
454 Allocas.emplace_back(Args&: AI, Args: Visitor.getAliasesCopy(),
455 Args: Visitor.getMayWriteBeforeCoroBegin());
456}
457
458void coro::collectSpillsFromArgs(SpillInfo &Spills, Function &F,
459 const SuspendCrossingInfo &Checker) {
460 // Collect the spills for arguments and other not-materializable values.
461 for (Argument &A : F.args())
462 for (User *U : A.users())
463 if (Checker.isDefinitionAcrossSuspend(A, U))
464 Spills[&A].push_back(Elt: cast<Instruction>(Val: U));
465}
466
467void coro::collectSpillsAndAllocasFromInsts(
468 SpillInfo &Spills, SmallVector<AllocaInfo, 8> &Allocas,
469 SmallVector<Instruction *, 4> &DeadInstructions,
470 SmallVector<CoroAllocaAllocInst *, 4> &LocalAllocas, Function &F,
471 const SuspendCrossingInfo &Checker, const DominatorTree &DT,
472 const coro::Shape &Shape) {
473
474 for (Instruction &I : instructions(F)) {
475 // Values returned from coroutine structure intrinsics should not be part
476 // of the Coroutine Frame.
477 if (isNonSpilledIntrinsic(I) || &I == Shape.CoroBegin)
478 continue;
479
480 // Handle alloca.alloc specially here.
481 if (auto AI = dyn_cast<CoroAllocaAllocInst>(Val: &I)) {
482 // Check whether the alloca's lifetime is bounded by suspend points.
483 if (isLocalAlloca(AI)) {
484 LocalAllocas.push_back(Elt: AI);
485 continue;
486 }
487
488 // If not, do a quick rewrite of the alloca and then add spills of
489 // the rewritten value. The rewrite doesn't invalidate anything in
490 // Spills because the other alloca intrinsics have no other operands
491 // besides AI, and it doesn't invalidate the iteration because we delay
492 // erasing AI.
493 auto Alloc = lowerNonLocalAlloca(AI, Shape, DeadInsts&: DeadInstructions);
494
495 for (User *U : Alloc->users()) {
496 if (Checker.isDefinitionAcrossSuspend(I&: *Alloc, U))
497 Spills[Alloc].push_back(Elt: cast<Instruction>(Val: U));
498 }
499 continue;
500 }
501
502 // Ignore alloca.get; we process this as part of coro.alloca.alloc.
503 if (isa<CoroAllocaGetInst>(Val: I))
504 continue;
505
506 if (auto *AI = dyn_cast<AllocaInst>(Val: &I)) {
507 collectFrameAlloca(AI, Shape, Checker, Allocas, DT);
508 continue;
509 }
510
511 for (User *U : I.users())
512 if (Checker.isDefinitionAcrossSuspend(I, U)) {
513 // We cannot spill a token.
514 if (I.getType()->isTokenTy())
515 report_fatal_error(
516 reason: "token definition is separated from the use by a suspend point");
517 Spills[&I].push_back(Elt: cast<Instruction>(Val: U));
518 }
519 }
520}
521
522void coro::collectSpillsFromDbgInfo(SpillInfo &Spills, Function &F,
523 const SuspendCrossingInfo &Checker) {
524 // We don't want the layout of coroutine frame to be affected
525 // by debug information. So we only choose to salvage dbg.values for
526 // whose value is already in the frame.
527 // We would handle the dbg.values for allocas specially
528 for (auto &Iter : Spills) {
529 auto *V = Iter.first;
530 SmallVector<DbgVariableRecord *, 16> DVRs;
531 findDbgValues(V, DbgVariableRecords&: DVRs);
532 // Add the instructions which carry debug info that is in the frame.
533 for (DbgVariableRecord *DVR : DVRs)
534 if (Checker.isDefinitionAcrossSuspend(V&: *V, U: DVR->Marker->MarkedInstr))
535 Spills[V].push_back(Elt: DVR->Marker->MarkedInstr);
536 }
537}
538
539/// Async and Retcon{Once} conventions assume that all spill uses can be sunk
540/// after the coro.begin intrinsic.
541void coro::sinkSpillUsesAfterCoroBegin(
542 const DominatorTree &Dom, CoroBeginInst *CoroBegin, coro::SpillInfo &Spills,
543 SmallVectorImpl<coro::AllocaInfo> &Allocas) {
544 SmallSetVector<Instruction *, 32> ToMove;
545 SmallVector<Instruction *, 32> Worklist;
546
547 // Collect all users that precede coro.begin.
548 auto collectUsers = [&](Value *Def) {
549 for (User *U : Def->users()) {
550 auto Inst = cast<Instruction>(Val: U);
551 if (Inst->getParent() != CoroBegin->getParent() ||
552 Dom.dominates(Def: CoroBegin, User: Inst))
553 continue;
554 if (ToMove.insert(X: Inst))
555 Worklist.push_back(Elt: Inst);
556 }
557 };
558 for (auto &I : Spills)
559 collectUsers(I.first);
560 for (auto &I : Allocas)
561 collectUsers(I.Alloca);
562
563 // Recursively collect users before coro.begin.
564 while (!Worklist.empty()) {
565 auto *Def = Worklist.pop_back_val();
566 for (User *U : Def->users()) {
567 auto Inst = cast<Instruction>(Val: U);
568 if (Dom.dominates(Def: CoroBegin, User: Inst))
569 continue;
570 if (ToMove.insert(X: Inst))
571 Worklist.push_back(Elt: Inst);
572 }
573 }
574
575 // Sort by dominance.
576 SmallVector<Instruction *, 64> InsertionList(ToMove.begin(), ToMove.end());
577 llvm::sort(C&: InsertionList, Comp: [&Dom](Instruction *A, Instruction *B) -> bool {
578 // If a dominates b it should precede (<) b.
579 return Dom.dominates(Def: A, User: B);
580 });
581
582 Instruction *InsertPt = CoroBegin->getNextNode();
583 for (Instruction *Inst : InsertionList)
584 Inst->moveBefore(InsertPos: InsertPt->getIterator());
585}
586
587BasicBlock::iterator coro::getSpillInsertionPt(const coro::Shape &Shape,
588 Value *Def,
589 const DominatorTree &DT) {
590 BasicBlock::iterator InsertPt;
591 if (auto *Arg = dyn_cast<Argument>(Val: Def)) {
592 // For arguments, we will place the store instruction right after
593 // the coroutine frame pointer instruction, i.e. coro.begin.
594 InsertPt = Shape.getInsertPtAfterFramePtr();
595
596 // If we're spilling an Argument, make sure we clear 'captures'
597 // from the coroutine function.
598 Arg->getParent()->removeParamAttr(ArgNo: Arg->getArgNo(), Kind: Attribute::Captures);
599 } else if (auto *CSI = dyn_cast<AnyCoroSuspendInst>(Val: Def)) {
600 // Don't spill immediately after a suspend; splitting assumes
601 // that the suspend will be followed by a branch.
602 InsertPt = CSI->getParent()->getSingleSuccessor()->getFirstNonPHIIt();
603 } else {
604 auto *I = cast<Instruction>(Val: Def);
605 if (!DT.dominates(Def: Shape.CoroBegin, User: I)) {
606 // If it is not dominated by CoroBegin, then spill should be
607 // inserted immediately after CoroFrame is computed.
608 InsertPt = Shape.getInsertPtAfterFramePtr();
609 } else if (auto *II = dyn_cast<InvokeInst>(Val: I)) {
610 // If we are spilling the result of the invoke instruction, split
611 // the normal edge and insert the spill in the new block.
612 auto *NewBB = SplitEdge(From: II->getParent(), To: II->getNormalDest());
613 InsertPt = NewBB->getTerminator()->getIterator();
614 } else if (isa<PHINode>(Val: I)) {
615 // Skip the PHINodes and EH pads instructions.
616 BasicBlock *DefBlock = I->getParent();
617 if (auto *CSI = dyn_cast<CatchSwitchInst>(Val: DefBlock->getTerminator()))
618 InsertPt = splitBeforeCatchSwitch(CatchSwitch: CSI)->getIterator();
619 else
620 InsertPt = DefBlock->getFirstInsertionPt();
621 } else {
622 assert(!I->isTerminator() && "unexpected terminator");
623 // For all other values, the spill is placed immediately after
624 // the definition.
625 InsertPt = I->getNextNode()->getIterator();
626 }
627 }
628
629 return InsertPt;
630}
631