1	//===- CoroFrame.cpp - Builds and manipulates coroutine frame -------------===//
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	// This file contains classes used to discover if for a particular value
9	// there from sue to definition that crosses a suspend block.
10	//
11	// Using the information discovered we form a Coroutine Frame structure to
12	// contain those values. All uses of those values are replaced with appropriate
13	// GEP + load from the coroutine frame. At the point of the definition we spill
14	// the value into the coroutine frame.
15	//===----------------------------------------------------------------------===//
16
17	#include "CoroInternal.h"
18	#include "llvm/ADT/BitVector.h"
19	#include "llvm/ADT/PostOrderIterator.h"
20	#include "llvm/ADT/ScopeExit.h"
21	#include "llvm/ADT/SmallString.h"
22	#include "llvm/Analysis/PtrUseVisitor.h"
23	#include "llvm/Analysis/StackLifetime.h"
24	#include "llvm/Config/llvm-config.h"
25	#include "llvm/IR/CFG.h"
26	#include "llvm/IR/DIBuilder.h"
27	#include "llvm/IR/DebugInfo.h"
28	#include "llvm/IR/Dominators.h"
29	#include "llvm/IR/IRBuilder.h"
30	#include "llvm/IR/InstIterator.h"
31	#include "llvm/IR/IntrinsicInst.h"
32	#include "llvm/Support/Debug.h"
33	#include "llvm/Support/MathExtras.h"
34	#include "llvm/Support/OptimizedStructLayout.h"
35	#include "llvm/Support/circular_raw_ostream.h"
36	#include "llvm/Support/raw_ostream.h"
37	#include "llvm/Transforms/Utils/BasicBlockUtils.h"
38	#include "llvm/Transforms/Utils/Local.h"
39	#include "llvm/Transforms/Utils/PromoteMemToReg.h"
40	#include <algorithm>
41	#include <deque>
42	#include <optional>
43
44	using namespace llvm;
45
46	// The "coro-suspend-crossing" flag is very noisy. There is another debug type,
47	// "coro-frame", which results in leaner debug spew.
48	#define DEBUG_TYPE "coro-suspend-crossing"
49
50	enum { SmallVectorThreshold = 32 };
51
52	// Provides two way mapping between the blocks and numbers.
53	namespace {
54	class BlockToIndexMapping {
55	SmallVector<BasicBlock *, SmallVectorThreshold> V;
56
57	public:
58	size_t size() const { return V.size(); }
59
60	BlockToIndexMapping(Function &F) {
61	for (BasicBlock &BB : F)
62	V.push_back(Elt: &BB);
63	llvm::sort(C&: V);
64	}
65
66	size_t blockToIndex(BasicBlock const *BB) const {
67	auto *I = llvm::lower_bound(Range: V, Value&: BB);
68	assert(I != V.end() && *I == BB && "BasicBlockNumberng: Unknown block");
69	return I - V.begin();
70	}
71
72	BasicBlock *indexToBlock(unsigned Index) const { return V[Index]; }
73	};
74	} // end anonymous namespace
75
76	// The SuspendCrossingInfo maintains data that allows to answer a question
77	// whether given two BasicBlocks A and B there is a path from A to B that
78	// passes through a suspend point.
79	//
80	// For every basic block 'i' it maintains a BlockData that consists of:
81	// Consumes: a bit vector which contains a set of indices of blocks that can
82	// reach block 'i'. A block can trivially reach itself.
83	// Kills: a bit vector which contains a set of indices of blocks that can
84	// reach block 'i' but there is a path crossing a suspend point
85	// not repeating 'i' (path to 'i' without cycles containing 'i').
86	// Suspend: a boolean indicating whether block 'i' contains a suspend point.
87	// End: a boolean indicating whether block 'i' contains a coro.end intrinsic.
88	// KillLoop: There is a path from 'i' to 'i' not otherwise repeating 'i' that
89	// crosses a suspend point.
90	//
91	namespace {
92	class SuspendCrossingInfo {
93	BlockToIndexMapping Mapping;
94
95	struct BlockData {
96	BitVector Consumes;
97	BitVector Kills;
98	bool Suspend = false;
99	bool End = false;
100	bool KillLoop = false;
101	bool Changed = false;
102	};
103	SmallVector<BlockData, SmallVectorThreshold> Block;
104
105	iterator_range<pred_iterator> predecessors(BlockData const &BD) const {
106	BasicBlock *BB = Mapping.indexToBlock(Index: &BD - &Block[0]);
107	return llvm::predecessors(BB);
108	}
109
110	BlockData &getBlockData(BasicBlock *BB) {
111	return Block[Mapping.blockToIndex(BB)];
112	}
113
114	/// Compute the BlockData for the current function in one iteration.
115	/// Initialize - Whether this is the first iteration, we can optimize
116	/// the initial case a little bit by manual loop switch.
117	/// Returns whether the BlockData changes in this iteration.
118	template <bool Initialize = false>
119	bool computeBlockData(const ReversePostOrderTraversal<Function *> &RPOT);
120
121	public:
122	#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
123	void dump() const;
124	void dump(StringRef Label, BitVector const &BV) const;
125	#endif
126
127	SuspendCrossingInfo(Function &F, coro::Shape &Shape);
128
129	/// Returns true if there is a path from \p From to \p To crossing a suspend
130	/// point without crossing \p From a 2nd time.
131	bool hasPathCrossingSuspendPoint(BasicBlock *From, BasicBlock *To) const {
132	size_t const FromIndex = Mapping.blockToIndex(BB: From);
133	size_t const ToIndex = Mapping.blockToIndex(BB: To);
134	bool const Result = Block[ToIndex].Kills[FromIndex];
135	LLVM_DEBUG(dbgs() << From->getName() << " => " << To->getName()
136	<< " answer is " << Result << "\n");
137	return Result;
138	}
139
140	/// Returns true if there is a path from \p From to \p To crossing a suspend
141	/// point without crossing \p From a 2nd time. If \p From is the same as \p To
142	/// this will also check if there is a looping path crossing a suspend point.
143	bool hasPathOrLoopCrossingSuspendPoint(BasicBlock *From,
144	BasicBlock *To) const {
145	size_t const FromIndex = Mapping.blockToIndex(BB: From);
146	size_t const ToIndex = Mapping.blockToIndex(BB: To);
147	bool Result = Block[ToIndex].Kills[FromIndex] ||
148	(From == To && Block[ToIndex].KillLoop);
149	LLVM_DEBUG(dbgs() << From->getName() << " => " << To->getName()
150	<< " answer is " << Result << " (path or loop)\n");
151	return Result;
152	}
153
154	bool isDefinitionAcrossSuspend(BasicBlock *DefBB, User *U) const {
155	auto *I = cast<Instruction>(Val: U);
156
157	// We rewrote PHINodes, so that only the ones with exactly one incoming
158	// value need to be analyzed.
159	if (auto *PN = dyn_cast<PHINode>(Val: I))
160	if (PN->getNumIncomingValues() > 1)
161	return false;
162
163	BasicBlock *UseBB = I->getParent();
164
165	// As a special case, treat uses by an llvm.coro.suspend.retcon or an
166	// llvm.coro.suspend.async as if they were uses in the suspend's single
167	// predecessor: the uses conceptually occur before the suspend.
168	if (isa<CoroSuspendRetconInst>(Val: I) || isa<CoroSuspendAsyncInst>(Val: I)) {
169	UseBB = UseBB->getSinglePredecessor();
170	assert(UseBB && "should have split coro.suspend into its own block");
171	}
172
173	return hasPathCrossingSuspendPoint(From: DefBB, To: UseBB);
174	}
175
176	bool isDefinitionAcrossSuspend(Argument &A, User *U) const {
177	return isDefinitionAcrossSuspend(DefBB: &A.getParent()->getEntryBlock(), U);
178	}
179
180	bool isDefinitionAcrossSuspend(Instruction &I, User *U) const {
181	auto *DefBB = I.getParent();
182
183	// As a special case, treat values produced by an llvm.coro.suspend.*
184	// as if they were defined in the single successor: the uses
185	// conceptually occur after the suspend.
186	if (isa<AnyCoroSuspendInst>(Val: I)) {
187	DefBB = DefBB->getSingleSuccessor();
188	assert(DefBB && "should have split coro.suspend into its own block");
189	}
190
191	return isDefinitionAcrossSuspend(DefBB, U);
192	}
193
194	bool isDefinitionAcrossSuspend(Value &V, User *U) const {
195	if (auto *Arg = dyn_cast<Argument>(Val: &V))
196	return isDefinitionAcrossSuspend(A&: *Arg, U);
197	if (auto *Inst = dyn_cast<Instruction>(Val: &V))
198	return isDefinitionAcrossSuspend(I&: *Inst, U);
199
200	llvm_unreachable(
201	"Coroutine could only collect Argument and Instruction now.");
202	}
203	};
204	} // end anonymous namespace
205
206	#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
207	LLVM_DUMP_METHOD void SuspendCrossingInfo::dump(StringRef Label,
208	BitVector const &BV) const {
209	dbgs() << Label << ":";
210	for (size_t I = 0, N = BV.size(); I < N; ++I)
211	if (BV[I])
212	dbgs() << " " << Mapping.indexToBlock(Index: I)->getName();
213	dbgs() << "\n";
214	}
215
216	LLVM_DUMP_METHOD void SuspendCrossingInfo::dump() const {
217	for (size_t I = 0, N = Block.size(); I < N; ++I) {
218	BasicBlock *const B = Mapping.indexToBlock(Index: I);
219	dbgs() << B->getName() << ":\n";
220	dump(Label: " Consumes", BV: Block[I].Consumes);
221	dump(Label: " Kills", BV: Block[I].Kills);
222	}
223	dbgs() << "\n";
224	}
225	#endif
226
227	template <bool Initialize>
228	bool SuspendCrossingInfo::computeBlockData(
229	const ReversePostOrderTraversal<Function *> &RPOT) {
230	bool Changed = false;
231
232	for (const BasicBlock *BB : RPOT) {
233	auto BBNo = Mapping.blockToIndex(BB);
234	auto &B = Block[BBNo];
235
236	// We don't need to count the predecessors when initialization.
237	if constexpr (!Initialize)
238	// If all the predecessors of the current Block don't change,
239	// the BlockData for the current block must not change too.
240	if (all_of(predecessors(BD: B), [this](BasicBlock *BB) {
241	return !Block[Mapping.blockToIndex(BB)].Changed;
242	})) {
243	B.Changed = false;
244	continue;
245	}
246
247	// Saved Consumes and Kills bitsets so that it is easy to see
248	// if anything changed after propagation.
249	auto SavedConsumes = B.Consumes;
250	auto SavedKills = B.Kills;
251
252	for (BasicBlock *PI : predecessors(BD: B)) {
253	auto PrevNo = Mapping.blockToIndex(BB: PI);
254	auto &P = Block[PrevNo];
255
256	// Propagate Kills and Consumes from predecessors into B.
257	B.Consumes |= P.Consumes;
258	B.Kills |= P.Kills;
259
260	// If block P is a suspend block, it should propagate kills into block
261	// B for every block P consumes.
262	if (P.Suspend)
263	B.Kills |= P.Consumes;
264	}
265
266	if (B.Suspend) {
267	// If block B is a suspend block, it should kill all of the blocks it
268	// consumes.
269	B.Kills |= B.Consumes;
270	} else if (B.End) {
271	// If block B is an end block, it should not propagate kills as the
272	// blocks following coro.end() are reached during initial invocation
273	// of the coroutine while all the data are still available on the
274	// stack or in the registers.
275	B.Kills.reset();
276	} else {
277	// This is reached when B block it not Suspend nor coro.end and it
278	// need to make sure that it is not in the kill set.
279	B.KillLoop |= B.Kills[BBNo];
280	B.Kills.reset(Idx: BBNo);
281	}
282
283	if constexpr (!Initialize) {
284	B.Changed = (B.Kills != SavedKills) || (B.Consumes != SavedConsumes);
285	Changed |= B.Changed;
286	}
287	}
288
289	return Changed;
290	}
291
292	SuspendCrossingInfo::SuspendCrossingInfo(Function &F, coro::Shape &Shape)
293	: Mapping(F) {
294	const size_t N = Mapping.size();
295	Block.resize(N);
296
297	// Initialize every block so that it consumes itself
298	for (size_t I = 0; I < N; ++I) {
299	auto &B = Block[I];
300	B.Consumes.resize(N);
301	B.Kills.resize(N);
302	B.Consumes.set(I);
303	B.Changed = true;
304	}
305
306	// Mark all CoroEnd Blocks. We do not propagate Kills beyond coro.ends as
307	// the code beyond coro.end is reachable during initial invocation of the
308	// coroutine.
309	for (auto *CE : Shape.CoroEnds)
310	getBlockData(BB: CE->getParent()).End = true;
311
312	// Mark all suspend blocks and indicate that they kill everything they
313	// consume. Note, that crossing coro.save also requires a spill, as any code
314	// between coro.save and coro.suspend may resume the coroutine and all of the
315	// state needs to be saved by that time.
316	auto markSuspendBlock = [&](IntrinsicInst *BarrierInst) {
317	BasicBlock *SuspendBlock = BarrierInst->getParent();
318	auto &B = getBlockData(BB: SuspendBlock);
319	B.Suspend = true;
320	B.Kills |= B.Consumes;
321	};
322	for (auto *CSI : Shape.CoroSuspends) {
323	markSuspendBlock(CSI);
324	if (auto *Save = CSI->getCoroSave())
325	markSuspendBlock(Save);
326	}
327
328	// It is considered to be faster to use RPO traversal for forward-edges
329	// dataflow analysis.
330	ReversePostOrderTraversal<Function *> RPOT(&F);
331	computeBlockData</*Initialize=*/true>(RPOT);
332	while (computeBlockData</*Initialize*/ false>(RPOT))
333	;
334
335	LLVM_DEBUG(dump());
336	}
337
338	namespace {
339
340	// RematGraph is used to construct a DAG for rematerializable instructions
341	// When the constructor is invoked with a candidate instruction (which is
342	// materializable) it builds a DAG of materializable instructions from that
343	// point.
344	// Typically, for each instruction identified as re-materializable across a
345	// suspend point, a RematGraph will be created.
346	struct RematGraph {
347	// Each RematNode in the graph contains the edges to instructions providing
348	// operands in the current node.
349	struct RematNode {
350	Instruction *Node;
351	SmallVector<RematNode *> Operands;
352	RematNode() = default;
353	RematNode(Instruction *V) : Node(V) {}
354	};
355
356	RematNode *EntryNode;
357	using RematNodeMap =
358	SmallMapVector<Instruction *, std::unique_ptr<RematNode>, 8>;
359	RematNodeMap Remats;
360	const std::function<bool(Instruction &)> &MaterializableCallback;
361	SuspendCrossingInfo &Checker;
362
363	RematGraph(const std::function<bool(Instruction &)> &MaterializableCallback,
364	Instruction *I, SuspendCrossingInfo &Checker)
365	: MaterializableCallback(MaterializableCallback), Checker(Checker) {
366	std::unique_ptr<RematNode> FirstNode = std::make_unique<RematNode>(args&: I);
367	EntryNode = FirstNode.get();
368	std::deque<std::unique_ptr<RematNode>> WorkList;
369	addNode(NUPtr: std::move(FirstNode), WorkList, FirstUse: cast<User>(Val: I));
370	while (WorkList.size()) {
371	std::unique_ptr<RematNode> N = std::move(WorkList.front());
372	WorkList.pop_front();
373	addNode(NUPtr: std::move(N), WorkList, FirstUse: cast<User>(Val: I));
374	}
375	}
376
377	void addNode(std::unique_ptr<RematNode> NUPtr,
378	std::deque<std::unique_ptr<RematNode>> &WorkList,
379	User *FirstUse) {
380	RematNode *N = NUPtr.get();
381	if (Remats.count(Key: N->Node))
382	return;
383
384	// We haven't see this node yet - add to the list
385	Remats[N->Node] = std::move(NUPtr);
386	for (auto &Def : N->Node->operands()) {
387	Instruction *D = dyn_cast<Instruction>(Val: Def.get());
388	if (!D || !MaterializableCallback(*D) ||
389	!Checker.isDefinitionAcrossSuspend(I&: *D, U: FirstUse))
390	continue;
391
392	if (Remats.count(Key: D)) {
393	// Already have this in the graph
394	N->Operands.push_back(Elt: Remats[D].get());
395	continue;
396	}
397
398	bool NoMatch = true;
399	for (auto &I : WorkList) {
400	if (I->Node == D) {
401	NoMatch = false;
402	N->Operands.push_back(Elt: I.get());
403	break;
404	}
405	}
406	if (NoMatch) {
407	// Create a new node
408	std::unique_ptr<RematNode> ChildNode = std::make_unique<RematNode>(args&: D);
409	N->Operands.push_back(Elt: ChildNode.get());
410	WorkList.push_back(x: std::move(ChildNode));
411	}
412	}
413	}
414
415	#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
416	void dump() const {
417	dbgs() << "Entry (";
418	if (EntryNode->Node->getParent()->hasName())
419	dbgs() << EntryNode->Node->getParent()->getName();
420	else
421	EntryNode->Node->getParent()->printAsOperand(O&: dbgs(), PrintType: false);
422	dbgs() << ") : " << *EntryNode->Node << "\n";
423	for (auto &E : Remats) {
424	dbgs() << *(E.first) << "\n";
425	for (RematNode *U : E.second->Operands)
426	dbgs() << " " << *U->Node << "\n";
427	}
428	}
429	#endif
430	};
431	} // end anonymous namespace
432
433	namespace llvm {
434
435	template <> struct GraphTraits<RematGraph *> {
436	using NodeRef = RematGraph::RematNode *;
437	using ChildIteratorType = RematGraph::RematNode **;
438
439	static NodeRef getEntryNode(RematGraph *G) { return G->EntryNode; }
440	static ChildIteratorType child_begin(NodeRef N) {
441	return N->Operands.begin();
442	}
443	static ChildIteratorType child_end(NodeRef N) { return N->Operands.end(); }
444	};
445
446	} // end namespace llvm
447
448	#undef DEBUG_TYPE // "coro-suspend-crossing"
449	#define DEBUG_TYPE "coro-frame"
450
451	namespace {
452	class FrameTypeBuilder;
453	// Mapping from the to-be-spilled value to all the users that need reload.
454	using SpillInfo = SmallMapVector<Value *, SmallVector<Instruction *, 2>, 8>;
455	struct AllocaInfo {
456	AllocaInst *Alloca;
457	DenseMap<Instruction *, std::optional<APInt>> Aliases;
458	bool MayWriteBeforeCoroBegin;
459	AllocaInfo(AllocaInst *Alloca,
460	DenseMap<Instruction *, std::optional<APInt>> Aliases,
461	bool MayWriteBeforeCoroBegin)
462	: Alloca(Alloca), Aliases(std::move(Aliases)),
463	MayWriteBeforeCoroBegin(MayWriteBeforeCoroBegin) {}
464	};
465	struct FrameDataInfo {
466	// All the values (that are not allocas) that needs to be spilled to the
467	// frame.
468	SpillInfo Spills;
469	// Allocas contains all values defined as allocas that need to live in the
470	// frame.
471	SmallVector<AllocaInfo, 8> Allocas;
472
473	SmallVector<Value *, 8> getAllDefs() const {
474	SmallVector<Value *, 8> Defs;
475	for (const auto &P : Spills)
476	Defs.push_back(Elt: P.first);
477	for (const auto &A : Allocas)
478	Defs.push_back(Elt: A.Alloca);
479	return Defs;
480	}
481
482	uint32_t getFieldIndex(Value *V) const {
483	auto Itr = FieldIndexMap.find(Val: V);
484	assert(Itr != FieldIndexMap.end() &&
485	"Value does not have a frame field index");
486	return Itr->second;
487	}
488
489	void setFieldIndex(Value *V, uint32_t Index) {
490	assert((LayoutIndexUpdateStarted || FieldIndexMap.count(V) == 0) &&
491	"Cannot set the index for the same field twice.");
492	FieldIndexMap[V] = Index;
493	}
494
495	Align getAlign(Value *V) const {
496	auto Iter = FieldAlignMap.find(Val: V);
497	assert(Iter != FieldAlignMap.end());
498	return Iter->second;
499	}
500
501	void setAlign(Value *V, Align AL) {
502	assert(FieldAlignMap.count(V) == 0);
503	FieldAlignMap.insert(KV: {V, AL});
504	}
505
506	uint64_t getDynamicAlign(Value *V) const {
507	auto Iter = FieldDynamicAlignMap.find(Val: V);
508	assert(Iter != FieldDynamicAlignMap.end());
509	return Iter->second;
510	}
511
512	void setDynamicAlign(Value *V, uint64_t Align) {
513	assert(FieldDynamicAlignMap.count(V) == 0);
514	FieldDynamicAlignMap.insert(KV: {V, Align});
515	}
516
517	uint64_t getOffset(Value *V) const {
518	auto Iter = FieldOffsetMap.find(Val: V);
519	assert(Iter != FieldOffsetMap.end());
520	return Iter->second;
521	}
522
523	void setOffset(Value *V, uint64_t Offset) {
524	assert(FieldOffsetMap.count(V) == 0);
525	FieldOffsetMap.insert(KV: {V, Offset});
526	}
527
528	// Remap the index of every field in the frame, using the final layout index.
529	void updateLayoutIndex(FrameTypeBuilder &B);
530
531	private:
532	// LayoutIndexUpdateStarted is used to avoid updating the index of any field
533	// twice by mistake.
534	bool LayoutIndexUpdateStarted = false;
535	// Map from values to their slot indexes on the frame. They will be first set
536	// with their original insertion field index. After the frame is built, their
537	// indexes will be updated into the final layout index.
538	DenseMap<Value *, uint32_t> FieldIndexMap;
539	// Map from values to their alignment on the frame. They would be set after
540	// the frame is built.
541	DenseMap<Value *, Align> FieldAlignMap;
542	DenseMap<Value *, uint64_t> FieldDynamicAlignMap;
543	// Map from values to their offset on the frame. They would be set after
544	// the frame is built.
545	DenseMap<Value *, uint64_t> FieldOffsetMap;
546	};
547	} // namespace
548
549	#ifndef NDEBUG
550	static void dumpSpills(StringRef Title, const SpillInfo &Spills) {
551	dbgs() << "------------- " << Title << "--------------\n";
552	for (const auto &E : Spills) {
553	E.first->dump();
554	dbgs() << " user: ";
555	for (auto *I : E.second)
556	I->dump();
557	}
558	}
559	static void dumpRemats(
560	StringRef Title,
561	const SmallMapVector<Instruction *, std::unique_ptr<RematGraph>, 8> &RM) {
562	dbgs() << "------------- " << Title << "--------------\n";
563	for (const auto &E : RM) {
564	E.second->dump();
565	dbgs() << "--\n";
566	}
567	}
568
569	static void dumpAllocas(const SmallVectorImpl<AllocaInfo> &Allocas) {
570	dbgs() << "------------- Allocas --------------\n";
571	for (const auto &A : Allocas) {
572	A.Alloca->dump();
573	}
574	}
575	#endif
576
577	namespace {
578	using FieldIDType = size_t;
579	// We cannot rely solely on natural alignment of a type when building a
580	// coroutine frame and if the alignment specified on the Alloca instruction
581	// differs from the natural alignment of the alloca type we will need to insert
582	// padding.
583	class FrameTypeBuilder {
584	private:
585	struct Field {
586	uint64_t Size;
587	uint64_t Offset;
588	Type *Ty;
589	FieldIDType LayoutFieldIndex;
590	Align Alignment;
591	Align TyAlignment;
592	uint64_t DynamicAlignBuffer;
593	};
594
595	const DataLayout &DL;
596	LLVMContext &Context;
597	uint64_t StructSize = 0;
598	Align StructAlign;
599	bool IsFinished = false;
600
601	std::optional<Align> MaxFrameAlignment;
602
603	SmallVector<Field, 8> Fields;
604	DenseMap<Value*, unsigned> FieldIndexByKey;
605
606	public:
607	FrameTypeBuilder(LLVMContext &Context, const DataLayout &DL,
608	std::optional<Align> MaxFrameAlignment)
609	: DL(DL), Context(Context), MaxFrameAlignment(MaxFrameAlignment) {}
610
611	/// Add a field to this structure for the storage of an `alloca`
612	/// instruction.
613	[[nodiscard]] FieldIDType addFieldForAlloca(AllocaInst *AI,
614	bool IsHeader = false) {
615	Type *Ty = AI->getAllocatedType();
616
617	// Make an array type if this is a static array allocation.
618	if (AI->isArrayAllocation()) {
619	if (auto *CI = dyn_cast<ConstantInt>(Val: AI->getArraySize()))
620	Ty = ArrayType::get(ElementType: Ty, NumElements: CI->getValue().getZExtValue());
621	else
622	report_fatal_error(reason: "Coroutines cannot handle non static allocas yet");
623	}
624
625	return addField(Ty, MaybeFieldAlignment: AI->getAlign(), IsHeader);
626	}
627
628	/// We want to put the allocas whose lifetime-ranges are not overlapped
629	/// into one slot of coroutine frame.
630	/// Consider the example at:https://bugs.llvm.org/show_bug.cgi?id=45566
631	///
632	/// cppcoro::task<void> alternative_paths(bool cond) {
633	/// if (cond) {
634	/// big_structure a;
635	/// process(a);
636	/// co_await something();
637	/// } else {
638	/// big_structure b;
639	/// process2(b);
640	/// co_await something();
641	/// }
642	/// }
643	///
644	/// We want to put variable a and variable b in the same slot to
645	/// reduce the size of coroutine frame.
646	///
647	/// This function use StackLifetime algorithm to partition the AllocaInsts in
648	/// Spills to non-overlapped sets in order to put Alloca in the same
649	/// non-overlapped set into the same slot in the Coroutine Frame. Then add
650	/// field for the allocas in the same non-overlapped set by using the largest
651	/// type as the field type.
652	///
653	/// Side Effects: Because We sort the allocas, the order of allocas in the
654	/// frame may be different with the order in the source code.
655	void addFieldForAllocas(const Function &F, FrameDataInfo &FrameData,
656	coro::Shape &Shape);
657
658	/// Add a field to this structure.
659	[[nodiscard]] FieldIDType addField(Type *Ty, MaybeAlign MaybeFieldAlignment,
660	bool IsHeader = false,
661	bool IsSpillOfValue = false) {
662	assert(!IsFinished && "adding fields to a finished builder");
663	assert(Ty && "must provide a type for a field");
664
665	// The field size is always the alloc size of the type.
666	uint64_t FieldSize = DL.getTypeAllocSize(Ty);
667
668	// For an alloca with size=0, we don't need to add a field and they
669	// can just point to any index in the frame. Use index 0.
670	if (FieldSize == 0) {
671	return 0;
672	}
673
674	// The field alignment might not be the type alignment, but we need
675	// to remember the type alignment anyway to build the type.
676	// If we are spilling values we don't need to worry about ABI alignment
677	// concerns.
678	Align ABIAlign = DL.getABITypeAlign(Ty);
679	Align TyAlignment = ABIAlign;
680	if (IsSpillOfValue && MaxFrameAlignment && *MaxFrameAlignment < ABIAlign)
681	TyAlignment = *MaxFrameAlignment;
682	Align FieldAlignment = MaybeFieldAlignment.value_or(u&: TyAlignment);
683
684	// The field alignment could be bigger than the max frame case, in that case
685	// we request additional storage to be able to dynamically align the
686	// pointer.
687	uint64_t DynamicAlignBuffer = 0;
688	if (MaxFrameAlignment && (FieldAlignment > *MaxFrameAlignment)) {
689	DynamicAlignBuffer =
690	offsetToAlignment(Value: MaxFrameAlignment->value(), Alignment: FieldAlignment);
691	FieldAlignment = *MaxFrameAlignment;
692	FieldSize = FieldSize + DynamicAlignBuffer;
693	}
694
695	// Lay out header fields immediately.
696	uint64_t Offset;
697	if (IsHeader) {
698	Offset = alignTo(Size: StructSize, A: FieldAlignment);
699	StructSize = Offset + FieldSize;
700
701	// Everything else has a flexible offset.
702	} else {
703	Offset = OptimizedStructLayoutField::FlexibleOffset;
704	}
705
706	Fields.push_back(Elt: {.Size: FieldSize, .Offset: Offset, .Ty: Ty, .LayoutFieldIndex: 0, .Alignment: FieldAlignment, .TyAlignment: TyAlignment,
707	.DynamicAlignBuffer: DynamicAlignBuffer});
708	return Fields.size() - 1;
709	}
710
711	/// Finish the layout and set the body on the given type.
712	void finish(StructType *Ty);
713
714	uint64_t getStructSize() const {
715	assert(IsFinished && "not yet finished!");
716	return StructSize;
717	}
718
719	Align getStructAlign() const {
720	assert(IsFinished && "not yet finished!");
721	return StructAlign;
722	}
723
724	FieldIDType getLayoutFieldIndex(FieldIDType Id) const {
725	assert(IsFinished && "not yet finished!");
726	return Fields[Id].LayoutFieldIndex;
727	}
728
729	Field getLayoutField(FieldIDType Id) const {
730	assert(IsFinished && "not yet finished!");
731	return Fields[Id];
732	}
733	};
734	} // namespace
735
736	void FrameDataInfo::updateLayoutIndex(FrameTypeBuilder &B) {
737	auto Updater = [&](Value *I) {
738	auto Field = B.getLayoutField(Id: getFieldIndex(V: I));
739	setFieldIndex(V: I, Index: Field.LayoutFieldIndex);
740	setAlign(V: I, AL: Field.Alignment);
741	uint64_t dynamicAlign =
742	Field.DynamicAlignBuffer
743	? Field.DynamicAlignBuffer + Field.Alignment.value()
744	: 0;
745	setDynamicAlign(V: I, Align: dynamicAlign);
746	setOffset(V: I, Offset: Field.Offset);
747	};
748	LayoutIndexUpdateStarted = true;
749	for (auto &S : Spills)
750	Updater(S.first);
751	for (const auto &A : Allocas)
752	Updater(A.Alloca);
753	LayoutIndexUpdateStarted = false;
754	}
755
756	void FrameTypeBuilder::addFieldForAllocas(const Function &F,
757	FrameDataInfo &FrameData,
758	coro::Shape &Shape) {
759	using AllocaSetType = SmallVector<AllocaInst *, 4>;
760	SmallVector<AllocaSetType, 4> NonOverlapedAllocas;
761
762	// We need to add field for allocas at the end of this function.
763	auto AddFieldForAllocasAtExit = make_scope_exit(F: [&]() {
764	for (auto AllocaList : NonOverlapedAllocas) {
765	auto *LargestAI = *AllocaList.begin();
766	FieldIDType Id = addFieldForAlloca(AI: LargestAI);
767	for (auto *Alloca : AllocaList)
768	FrameData.setFieldIndex(V: Alloca, Index: Id);
769	}
770	});
771
772	if (!Shape.OptimizeFrame) {
773	for (const auto &A : FrameData.Allocas) {
774	AllocaInst *Alloca = A.Alloca;
775	NonOverlapedAllocas.emplace_back(Args: AllocaSetType(1, Alloca));
776	}
777	return;
778	}
779
780	// Because there are paths from the lifetime.start to coro.end
781	// for each alloca, the liferanges for every alloca is overlaped
782	// in the blocks who contain coro.end and the successor blocks.
783	// So we choose to skip there blocks when we calculate the liferange
784	// for each alloca. It should be reasonable since there shouldn't be uses
785	// in these blocks and the coroutine frame shouldn't be used outside the
786	// coroutine body.
787	//
788	// Note that the user of coro.suspend may not be SwitchInst. However, this
789	// case seems too complex to handle. And it is harmless to skip these
790	// patterns since it just prevend putting the allocas to live in the same
791	// slot.
792	DenseMap<SwitchInst *, BasicBlock *> DefaultSuspendDest;
793	for (auto *CoroSuspendInst : Shape.CoroSuspends) {
794	for (auto *U : CoroSuspendInst->users()) {
795	if (auto *ConstSWI = dyn_cast<SwitchInst>(Val: U)) {
796	auto *SWI = const_cast<SwitchInst *>(ConstSWI);
797	DefaultSuspendDest[SWI] = SWI->getDefaultDest();
798	SWI->setDefaultDest(SWI->getSuccessor(idx: 1));
799	}
800	}
801	}
802
803	auto ExtractAllocas = [&]() {
804	AllocaSetType Allocas;
805	Allocas.reserve(N: FrameData.Allocas.size());
806	for (const auto &A : FrameData.Allocas)
807	Allocas.push_back(Elt: A.Alloca);
808	return Allocas;
809	};
810	StackLifetime StackLifetimeAnalyzer(F, ExtractAllocas(),
811	StackLifetime::LivenessType::May);
812	StackLifetimeAnalyzer.run();
813	auto IsAllocaInferenre = [&](const AllocaInst *AI1, const AllocaInst *AI2) {
814	return StackLifetimeAnalyzer.getLiveRange(AI: AI1).overlaps(
815	Other: StackLifetimeAnalyzer.getLiveRange(AI: AI2));
816	};
817	auto GetAllocaSize = [&](const AllocaInfo &A) {
818	std::optional<TypeSize> RetSize = A.Alloca->getAllocationSize(DL);
819	assert(RetSize && "Variable Length Arrays (VLA) are not supported.\n");
820	assert(!RetSize->isScalable() && "Scalable vectors are not yet supported");
821	return RetSize->getFixedValue();
822	};
823	// Put larger allocas in the front. So the larger allocas have higher
824	// priority to merge, which can save more space potentially. Also each
825	// AllocaSet would be ordered. So we can get the largest Alloca in one
826	// AllocaSet easily.
827	sort(C&: FrameData.Allocas, Comp: [&](const auto &Iter1, const auto &Iter2) {
828	return GetAllocaSize(Iter1) > GetAllocaSize(Iter2);
829	});
830	for (const auto &A : FrameData.Allocas) {
831	AllocaInst *Alloca = A.Alloca;
832	bool Merged = false;
833	// Try to find if the Alloca is not inferenced with any existing
834	// NonOverlappedAllocaSet. If it is true, insert the alloca to that
835	// NonOverlappedAllocaSet.
836	for (auto &AllocaSet : NonOverlapedAllocas) {
837	assert(!AllocaSet.empty() && "Processing Alloca Set is not empty.\n");
838	bool NoInference = none_of(Range&: AllocaSet, P: [&](auto Iter) {
839	return IsAllocaInferenre(Alloca, Iter);
840	});
841	// If the alignment of A is multiple of the alignment of B, the address
842	// of A should satisfy the requirement for aligning for B.
843	//
844	// There may be other more fine-grained strategies to handle the alignment
845	// infomation during the merging process. But it seems hard to handle
846	// these strategies and benefit little.
847	bool Alignable = [&]() -> bool {
848	auto *LargestAlloca = *AllocaSet.begin();
849	return LargestAlloca->getAlign().value() % Alloca->getAlign().value() ==
850	0;
851	}();
852	bool CouldMerge = NoInference && Alignable;
853	if (!CouldMerge)
854	continue;
855	AllocaSet.push_back(Elt: Alloca);
856	Merged = true;
857	break;
858	}
859	if (!Merged) {
860	NonOverlapedAllocas.emplace_back(Args: AllocaSetType(1, Alloca));
861	}
862	}
863	// Recover the default target destination for each Switch statement
864	// reserved.
865	for (auto SwitchAndDefaultDest : DefaultSuspendDest) {
866	SwitchInst *SWI = SwitchAndDefaultDest.first;
867	BasicBlock *DestBB = SwitchAndDefaultDest.second;
868	SWI->setDefaultDest(DestBB);
869	}
870	// This Debug Info could tell us which allocas are merged into one slot.
871	LLVM_DEBUG(for (auto &AllocaSet
872	: NonOverlapedAllocas) {
873	if (AllocaSet.size() > 1) {
874	dbgs() << "In Function:" << F.getName() << "\n";
875	dbgs() << "Find Union Set "
876	<< "\n";
877	dbgs() << "\tAllocas are \n";
878	for (auto Alloca : AllocaSet)
879	dbgs() << "\t\t" << *Alloca << "\n";
880	}
881	});
882	}
883
884	void FrameTypeBuilder::finish(StructType *Ty) {
885	assert(!IsFinished && "already finished!");
886
887	// Prepare the optimal-layout field array.
888	// The Id in the layout field is a pointer to our Field for it.
889	SmallVector<OptimizedStructLayoutField, 8> LayoutFields;
890	LayoutFields.reserve(N: Fields.size());
891	for (auto &Field : Fields) {
892	LayoutFields.emplace_back(Args: &Field, Args&: Field.Size, Args&: Field.Alignment,
893	Args&: Field.Offset);
894	}
895
896	// Perform layout.
897	auto SizeAndAlign = performOptimizedStructLayout(Fields: LayoutFields);
898	StructSize = SizeAndAlign.first;
899	StructAlign = SizeAndAlign.second;
900
901	auto getField = [](const OptimizedStructLayoutField &LayoutField) -> Field & {
902	return *static_cast<Field *>(const_cast<void*>(LayoutField.Id));
903	};
904
905	// We need to produce a packed struct type if there's a field whose
906	// assigned offset isn't a multiple of its natural type alignment.
907	bool Packed = [&] {
908	for (auto &LayoutField : LayoutFields) {
909	auto &F = getField(LayoutField);
910	if (!isAligned(Lhs: F.TyAlignment, SizeInBytes: LayoutField.Offset))
911	return true;
912	}
913	return false;
914	}();
915
916	// Build the struct body.
917	SmallVector<Type*, 16> FieldTypes;
918	FieldTypes.reserve(N: LayoutFields.size() * 3 / 2);
919	uint64_t LastOffset = 0;
920	for (auto &LayoutField : LayoutFields) {
921	auto &F = getField(LayoutField);
922
923	auto Offset = LayoutField.Offset;
924
925	// Add a padding field if there's a padding gap and we're either
926	// building a packed struct or the padding gap is more than we'd
927	// get from aligning to the field type's natural alignment.
928	assert(Offset >= LastOffset);
929	if (Offset != LastOffset) {
930	if (Packed || alignTo(Size: LastOffset, A: F.TyAlignment) != Offset)
931	FieldTypes.push_back(Elt: ArrayType::get(ElementType: Type::getInt8Ty(C&: Context),
932	NumElements: Offset - LastOffset));
933	}
934
935	F.Offset = Offset;
936	F.LayoutFieldIndex = FieldTypes.size();
937
938	FieldTypes.push_back(Elt: F.Ty);
939	if (F.DynamicAlignBuffer) {
940	FieldTypes.push_back(
941	Elt: ArrayType::get(ElementType: Type::getInt8Ty(C&: Context), NumElements: F.DynamicAlignBuffer));
942	}
943	LastOffset = Offset + F.Size;
944	}
945
946	Ty->setBody(Elements: FieldTypes, isPacked: Packed);
947
948	#ifndef NDEBUG
949	// Check that the IR layout matches the offsets we expect.
950	auto Layout = DL.getStructLayout(Ty);
951	for (auto &F : Fields) {
952	assert(Ty->getElementType(F.LayoutFieldIndex) == F.Ty);
953	assert(Layout->getElementOffset(F.LayoutFieldIndex) == F.Offset);
954	}
955	#endif
956
957	IsFinished = true;
958	}
959
960	static void cacheDIVar(FrameDataInfo &FrameData,
961	DenseMap<Value *, DILocalVariable *> &DIVarCache) {
962	for (auto *V : FrameData.getAllDefs()) {
963	if (DIVarCache.contains(Val: V))
964	continue;
965
966	auto CacheIt = [&DIVarCache, V](const auto &Container) {
967	auto *I = llvm::find_if(Container, [](auto *DDI) {
968	return DDI->getExpression()->getNumElements() == 0;
969	});
970	if (I != Container.end())
971	DIVarCache.insert({V, (*I)->getVariable()});
972	};
973	CacheIt(findDbgDeclares(V));
974	CacheIt(findDVRDeclares(V));
975	}
976	}
977
978	/// Create name for Type. It uses MDString to store new created string to
979	/// avoid memory leak.
980	static StringRef solveTypeName(Type *Ty) {
981	if (Ty->isIntegerTy()) {
982	// The longest name in common may be '__int_128', which has 9 bits.
983	SmallString<16> Buffer;
984	raw_svector_ostream OS(Buffer);
985	OS << "__int_" << cast<IntegerType>(Val: Ty)->getBitWidth();
986	auto *MDName = MDString::get(Context&: Ty->getContext(), Str: OS.str());
987	return MDName->getString();
988	}
989
990	if (Ty->isFloatingPointTy()) {
991	if (Ty->isFloatTy())
992	return "__float_";
993	if (Ty->isDoubleTy())
994	return "__double_";
995	return "__floating_type_";
996	}
997
998	if (Ty->isPointerTy())
999	return "PointerType";
1000
1001	if (Ty->isStructTy()) {
1002	if (!cast<StructType>(Val: Ty)->hasName())
1003	return "__LiteralStructType_";
1004
1005	auto Name = Ty->getStructName();
1006
1007	SmallString<16> Buffer(Name);
1008	for (auto &Iter : Buffer)
1009	if (Iter == '.' || Iter == ':')
1010	Iter = '_';
1011	auto *MDName = MDString::get(Context&: Ty->getContext(), Str: Buffer.str());
1012	return MDName->getString();
1013	}
1014
1015	return "UnknownType";
1016	}
1017
1018	static DIType *solveDIType(DIBuilder &Builder, Type *Ty,
1019	const DataLayout &Layout, DIScope *Scope,
1020	unsigned LineNum,
1021	DenseMap<Type *, DIType *> &DITypeCache) {
1022	if (DIType *DT = DITypeCache.lookup(Val: Ty))
1023	return DT;
1024
1025	StringRef Name = solveTypeName(Ty);
1026
1027	DIType *RetType = nullptr;
1028
1029	if (Ty->isIntegerTy()) {
1030	auto BitWidth = cast<IntegerType>(Val: Ty)->getBitWidth();
1031	RetType = Builder.createBasicType(Name, SizeInBits: BitWidth, Encoding: dwarf::DW_ATE_signed,
1032	Flags: llvm::DINode::FlagArtificial);
1033	} else if (Ty->isFloatingPointTy()) {
1034	RetType = Builder.createBasicType(Name, SizeInBits: Layout.getTypeSizeInBits(Ty),
1035	Encoding: dwarf::DW_ATE_float,
1036	Flags: llvm::DINode::FlagArtificial);
1037	} else if (Ty->isPointerTy()) {
1038	// Construct PointerType points to null (aka void *) instead of exploring
1039	// pointee type to avoid infinite search problem. For example, we would be
1040	// in trouble if we traverse recursively:
1041	//
1042	// struct Node {
1043	// Node* ptr;
1044	// };
1045	RetType =
1046	Builder.createPointerType(PointeeTy: nullptr, SizeInBits: Layout.getTypeSizeInBits(Ty),
1047	AlignInBits: Layout.getABITypeAlign(Ty).value() * CHAR_BIT,
1048	/*DWARFAddressSpace=*/std::nullopt, Name);
1049	} else if (Ty->isStructTy()) {
1050	auto *DIStruct = Builder.createStructType(
1051	Scope, Name, File: Scope->getFile(), LineNumber: LineNum, SizeInBits: Layout.getTypeSizeInBits(Ty),
1052	AlignInBits: Layout.getPrefTypeAlign(Ty).value() * CHAR_BIT,
1053	Flags: llvm::DINode::FlagArtificial, DerivedFrom: nullptr, Elements: llvm::DINodeArray());
1054
1055	auto *StructTy = cast<StructType>(Val: Ty);
1056	SmallVector<Metadata *, 16> Elements;
1057	for (unsigned I = 0; I < StructTy->getNumElements(); I++) {
1058	DIType *DITy = solveDIType(Builder, Ty: StructTy->getElementType(N: I), Layout,
1059	Scope, LineNum, DITypeCache);
1060	assert(DITy);
1061	Elements.push_back(Elt: Builder.createMemberType(
1062	Scope, Name: DITy->getName(), File: Scope->getFile(), LineNo: LineNum,
1063	SizeInBits: DITy->getSizeInBits(), AlignInBits: DITy->getAlignInBits(),
1064	OffsetInBits: Layout.getStructLayout(Ty: StructTy)->getElementOffsetInBits(Idx: I),
1065	Flags: llvm::DINode::FlagArtificial, Ty: DITy));
1066	}
1067
1068	Builder.replaceArrays(T&: DIStruct, Elements: Builder.getOrCreateArray(Elements));
1069
1070	RetType = DIStruct;
1071	} else {
1072	LLVM_DEBUG(dbgs() << "Unresolved Type: " << *Ty << "\n");
1073	TypeSize Size = Layout.getTypeSizeInBits(Ty);
1074	auto *CharSizeType = Builder.createBasicType(
1075	Name, SizeInBits: 8, Encoding: dwarf::DW_ATE_unsigned_char, Flags: llvm::DINode::FlagArtificial);
1076
1077	if (Size <= 8)
1078	RetType = CharSizeType;
1079	else {
1080	if (Size % 8 != 0)
1081	Size = TypeSize::getFixed(ExactSize: Size + 8 - (Size % 8));
1082
1083	RetType = Builder.createArrayType(
1084	Size, AlignInBits: Layout.getPrefTypeAlign(Ty).value(), Ty: CharSizeType,
1085	Subscripts: Builder.getOrCreateArray(Elements: Builder.getOrCreateSubrange(Lo: 0, Count: Size / 8)));
1086	}
1087	}
1088
1089	DITypeCache.insert(KV: {Ty, RetType});
1090	return RetType;
1091	}
1092
1093	/// Build artificial debug info for C++ coroutine frames to allow users to
1094	/// inspect the contents of the frame directly
1095	///
1096	/// Create Debug information for coroutine frame with debug name "__coro_frame".
1097	/// The debug information for the fields of coroutine frame is constructed from
1098	/// the following way:
1099	/// 1. For all the value in the Frame, we search the use of dbg.declare to find
1100	/// the corresponding debug variables for the value. If we can find the
1101	/// debug variable, we can get full and accurate debug information.
1102	/// 2. If we can't get debug information in step 1 and 2, we could only try to
1103	/// build the DIType by Type. We did this in solveDIType. We only handle
1104	/// integer, float, double, integer type and struct type for now.
1105	static void buildFrameDebugInfo(Function &F, coro::Shape &Shape,
1106	FrameDataInfo &FrameData) {
1107	DISubprogram *DIS = F.getSubprogram();
1108	// If there is no DISubprogram for F, it implies the Function are not compiled
1109	// with debug info. So we also don't need to generate debug info for the frame
1110	// neither.
1111	if (!DIS || !DIS->getUnit() ||
1112	!dwarf::isCPlusPlus(
1113	S: (dwarf::SourceLanguage)DIS->getUnit()->getSourceLanguage()))
1114	return;
1115
1116	assert(Shape.ABI == coro::ABI::Switch &&
1117	"We could only build debug infomation for C++ coroutine now.\n");
1118
1119	DIBuilder DBuilder(*F.getParent(), /*AllowUnresolved*/ false);
1120
1121	AllocaInst *PromiseAlloca = Shape.getPromiseAlloca();
1122	assert(PromiseAlloca &&
1123	"Coroutine with switch ABI should own Promise alloca");
1124
1125	TinyPtrVector<DbgDeclareInst *> DIs = findDbgDeclares(V: PromiseAlloca);
1126	TinyPtrVector<DbgVariableRecord *> DVRs = findDVRDeclares(V: PromiseAlloca);
1127
1128	DILocalVariable *PromiseDIVariable = nullptr;
1129	DILocation *DILoc = nullptr;
1130	if (!DIs.empty()) {
1131	DbgDeclareInst *PromiseDDI = DIs.front();
1132	PromiseDIVariable = PromiseDDI->getVariable();
1133	DILoc = PromiseDDI->getDebugLoc().get();
1134	} else if (!DVRs.empty()) {
1135	DbgVariableRecord *PromiseDVR = DVRs.front();
1136	PromiseDIVariable = PromiseDVR->getVariable();
1137	DILoc = PromiseDVR->getDebugLoc().get();
1138	} else {
1139	return;
1140	}
1141
1142	DILocalScope *PromiseDIScope = PromiseDIVariable->getScope();
1143	DIFile *DFile = PromiseDIScope->getFile();
1144	unsigned LineNum = PromiseDIVariable->getLine();
1145
1146	DICompositeType *FrameDITy = DBuilder.createStructType(
1147	Scope: DIS->getUnit(), Name: Twine(F.getName() + ".coro_frame_ty").str(),
1148	File: DFile, LineNumber: LineNum, SizeInBits: Shape.FrameSize * 8,
1149	AlignInBits: Shape.FrameAlign.value() * 8, Flags: llvm::DINode::FlagArtificial, DerivedFrom: nullptr,
1150	Elements: llvm::DINodeArray());
1151	StructType *FrameTy = Shape.FrameTy;
1152	SmallVector<Metadata *, 16> Elements;
1153	DataLayout Layout = F.getParent()->getDataLayout();
1154
1155	DenseMap<Value *, DILocalVariable *> DIVarCache;
1156	cacheDIVar(FrameData, DIVarCache);
1157
1158	unsigned ResumeIndex = coro::Shape::SwitchFieldIndex::Resume;
1159	unsigned DestroyIndex = coro::Shape::SwitchFieldIndex::Destroy;
1160	unsigned IndexIndex = Shape.SwitchLowering.IndexField;
1161
1162	DenseMap<unsigned, StringRef> NameCache;
1163	NameCache.insert(KV: {ResumeIndex, "__resume_fn"});
1164	NameCache.insert(KV: {DestroyIndex, "__destroy_fn"});
1165	NameCache.insert(KV: {IndexIndex, "__coro_index"});
1166
1167	Type *ResumeFnTy = FrameTy->getElementType(N: ResumeIndex),
1168	*DestroyFnTy = FrameTy->getElementType(N: DestroyIndex),
1169	*IndexTy = FrameTy->getElementType(N: IndexIndex);
1170
1171	DenseMap<unsigned, DIType *> TyCache;
1172	TyCache.insert(
1173	KV: {ResumeIndex, DBuilder.createPointerType(
1174	PointeeTy: nullptr, SizeInBits: Layout.getTypeSizeInBits(Ty: ResumeFnTy))});
1175	TyCache.insert(
1176	KV: {DestroyIndex, DBuilder.createPointerType(
1177	PointeeTy: nullptr, SizeInBits: Layout.getTypeSizeInBits(Ty: DestroyFnTy))});
1178
1179	/// FIXME: If we fill the field `SizeInBits` with the actual size of
1180	/// __coro_index in bits, then __coro_index wouldn't show in the debugger.
1181	TyCache.insert(KV: {IndexIndex, DBuilder.createBasicType(
1182	Name: "__coro_index",
1183	SizeInBits: (Layout.getTypeSizeInBits(Ty: IndexTy) < 8)
1184	? 8
1185	: Layout.getTypeSizeInBits(Ty: IndexTy),
1186	Encoding: dwarf::DW_ATE_unsigned_char)});
1187
1188	for (auto *V : FrameData.getAllDefs()) {
1189	if (!DIVarCache.contains(Val: V))
1190	continue;
1191
1192	auto Index = FrameData.getFieldIndex(V);
1193
1194	NameCache.insert(KV: {Index, DIVarCache[V]->getName()});
1195	TyCache.insert(KV: {Index, DIVarCache[V]->getType()});
1196	}
1197
1198	// Cache from index to (Align, Offset Pair)
1199	DenseMap<unsigned, std::pair<unsigned, unsigned>> OffsetCache;
1200	// The Align and Offset of Resume function and Destroy function are fixed.
1201	OffsetCache.insert(KV: {ResumeIndex, {8, 0}});
1202	OffsetCache.insert(KV: {DestroyIndex, {8, 8}});
1203	OffsetCache.insert(
1204	KV: {IndexIndex,
1205	{Shape.SwitchLowering.IndexAlign, Shape.SwitchLowering.IndexOffset}});
1206
1207	for (auto *V : FrameData.getAllDefs()) {
1208	auto Index = FrameData.getFieldIndex(V);
1209
1210	OffsetCache.insert(
1211	KV: {Index, {FrameData.getAlign(V).value(), FrameData.getOffset(V)}});
1212	}
1213
1214	DenseMap<Type *, DIType *> DITypeCache;
1215	// This counter is used to avoid same type names. e.g., there would be
1216	// many i32 and i64 types in one coroutine. And we would use i32_0 and
1217	// i32_1 to avoid the same type. Since it makes no sense the name of the
1218	// fields confilicts with each other.
1219	unsigned UnknownTypeNum = 0;
1220	for (unsigned Index = 0; Index < FrameTy->getNumElements(); Index++) {
1221	if (!OffsetCache.contains(Val: Index))
1222	continue;
1223
1224	std::string Name;
1225	uint64_t SizeInBits;
1226	uint32_t AlignInBits;
1227	uint64_t OffsetInBits;
1228	DIType *DITy = nullptr;
1229
1230	Type *Ty = FrameTy->getElementType(N: Index);
1231	assert(Ty->isSized() && "We can't handle type which is not sized.\n");
1232	SizeInBits = Layout.getTypeSizeInBits(Ty).getFixedValue();
1233	AlignInBits = OffsetCache[Index].first * 8;
1234	OffsetInBits = OffsetCache[Index].second * 8;
1235
1236	if (NameCache.contains(Val: Index)) {
1237	Name = NameCache[Index].str();
1238	DITy = TyCache[Index];
1239	} else {
1240	DITy = solveDIType(Builder&: DBuilder, Ty, Layout, Scope: FrameDITy, LineNum, DITypeCache);
1241	assert(DITy && "SolveDIType shouldn't return nullptr.\n");
1242	Name = DITy->getName().str();
1243	Name += "_" + std::to_string(val: UnknownTypeNum);
1244	UnknownTypeNum++;
1245	}
1246
1247	Elements.push_back(Elt: DBuilder.createMemberType(
1248	Scope: FrameDITy, Name, File: DFile, LineNo: LineNum, SizeInBits, AlignInBits, OffsetInBits,
1249	Flags: llvm::DINode::FlagArtificial, Ty: DITy));
1250	}
1251
1252	DBuilder.replaceArrays(T&: FrameDITy, Elements: DBuilder.getOrCreateArray(Elements));
1253
1254	auto *FrameDIVar = DBuilder.createAutoVariable(Scope: PromiseDIScope, Name: "__coro_frame",
1255	File: DFile, LineNo: LineNum, Ty: FrameDITy,
1256	AlwaysPreserve: true, Flags: DINode::FlagArtificial);
1257	assert(FrameDIVar->isValidLocationForIntrinsic(DILoc));
1258
1259	// Subprogram would have ContainedNodes field which records the debug
1260	// variables it contained. So we need to add __coro_frame to the
1261	// ContainedNodes of it.
1262	//
1263	// If we don't add __coro_frame to the RetainedNodes, user may get
1264	// `no symbol __coro_frame in context` rather than `__coro_frame`
1265	// is optimized out, which is more precise.
1266	if (auto *SubProgram = dyn_cast<DISubprogram>(Val: PromiseDIScope)) {
1267	auto RetainedNodes = SubProgram->getRetainedNodes();
1268	SmallVector<Metadata *, 32> RetainedNodesVec(RetainedNodes.begin(),
1269	RetainedNodes.end());
1270	RetainedNodesVec.push_back(Elt: FrameDIVar);
1271	SubProgram->replaceOperandWith(
1272	I: 7, New: (MDTuple::get(Context&: F.getContext(), MDs: RetainedNodesVec)));
1273	}
1274
1275	if (UseNewDbgInfoFormat) {
1276	DbgVariableRecord *NewDVR =
1277	new DbgVariableRecord(ValueAsMetadata::get(V: Shape.FramePtr), FrameDIVar,
1278	DBuilder.createExpression(), DILoc,
1279	DbgVariableRecord::LocationType::Declare);
1280	BasicBlock::iterator It = Shape.getInsertPtAfterFramePtr();
1281	It->getParent()->insertDbgRecordBefore(DR: NewDVR, Here: It);
1282	} else {
1283	DBuilder.insertDeclare(Storage: Shape.FramePtr, VarInfo: FrameDIVar,
1284	Expr: DBuilder.createExpression(), DL: DILoc,
1285	InsertBefore: &*Shape.getInsertPtAfterFramePtr());
1286	}
1287	}
1288
1289	// Build a struct that will keep state for an active coroutine.
1290	// struct f.frame {
1291	// ResumeFnTy ResumeFnAddr;
1292	// ResumeFnTy DestroyFnAddr;
1293	// ... promise (if present) ...
1294	// int ResumeIndex;
1295	// ... spills ...
1296	// };
1297	static StructType *buildFrameType(Function &F, coro::Shape &Shape,
1298	FrameDataInfo &FrameData) {
1299	LLVMContext &C = F.getContext();
1300	const DataLayout &DL = F.getParent()->getDataLayout();
1301	StructType *FrameTy = [&] {
1302	SmallString<32> Name(F.getName());
1303	Name.append(RHS: ".Frame");
1304	return StructType::create(Context&: C, Name);
1305	}();
1306
1307	// We will use this value to cap the alignment of spilled values.
1308	std::optional<Align> MaxFrameAlignment;
1309	if (Shape.ABI == coro::ABI::Async)
1310	MaxFrameAlignment = Shape.AsyncLowering.getContextAlignment();
1311	FrameTypeBuilder B(C, DL, MaxFrameAlignment);
1312
1313	AllocaInst *PromiseAlloca = Shape.getPromiseAlloca();
1314	std::optional<FieldIDType> SwitchIndexFieldId;
1315
1316	if (Shape.ABI == coro::ABI::Switch) {
1317	auto *FnPtrTy = PointerType::getUnqual(C);
1318
1319	// Add header fields for the resume and destroy functions.
1320	// We can rely on these being perfectly packed.
1321	(void)B.addField(Ty: FnPtrTy, MaybeFieldAlignment: std::nullopt, /*header*/ IsHeader: true);
1322	(void)B.addField(Ty: FnPtrTy, MaybeFieldAlignment: std::nullopt, /*header*/ IsHeader: true);
1323
1324	// PromiseAlloca field needs to be explicitly added here because it's
1325	// a header field with a fixed offset based on its alignment. Hence it
1326	// needs special handling and cannot be added to FrameData.Allocas.
1327	if (PromiseAlloca)
1328	FrameData.setFieldIndex(
1329	V: PromiseAlloca, Index: B.addFieldForAlloca(AI: PromiseAlloca, /*header*/ IsHeader: true));
1330
1331	// Add a field to store the suspend index. This doesn't need to
1332	// be in the header.
1333	unsigned IndexBits = std::max(a: 1U, b: Log2_64_Ceil(Value: Shape.CoroSuspends.size()));
1334	Type *IndexType = Type::getIntNTy(C, N: IndexBits);
1335
1336	SwitchIndexFieldId = B.addField(Ty: IndexType, MaybeFieldAlignment: std::nullopt);
1337	} else {
1338	assert(PromiseAlloca == nullptr && "lowering doesn't support promises");
1339	}
1340
1341	// Because multiple allocas may own the same field slot,
1342	// we add allocas to field here.
1343	B.addFieldForAllocas(F, FrameData, Shape);
1344	// Add PromiseAlloca to Allocas list so that
1345	// 1. updateLayoutIndex could update its index after
1346	// `performOptimizedStructLayout`
1347	// 2. it is processed in insertSpills.
1348	if (Shape.ABI == coro::ABI::Switch && PromiseAlloca)
1349	// We assume that the promise alloca won't be modified before
1350	// CoroBegin and no alias will be create before CoroBegin.
1351	FrameData.Allocas.emplace_back(
1352	Args&: PromiseAlloca, Args: DenseMap<Instruction *, std::optional<APInt>>{}, Args: false);
1353	// Create an entry for every spilled value.
1354	for (auto &S : FrameData.Spills) {
1355	Type *FieldType = S.first->getType();
1356	// For byval arguments, we need to store the pointed value in the frame,
1357	// instead of the pointer itself.
1358	if (const Argument *A = dyn_cast<Argument>(Val: S.first))
1359	if (A->hasByValAttr())
1360	FieldType = A->getParamByValType();
1361	FieldIDType Id = B.addField(Ty: FieldType, MaybeFieldAlignment: std::nullopt, IsHeader: false /*header*/,
1362	IsSpillOfValue: true /*IsSpillOfValue*/);
1363	FrameData.setFieldIndex(V: S.first, Index: Id);
1364	}
1365
1366	B.finish(Ty: FrameTy);
1367	FrameData.updateLayoutIndex(B);
1368	Shape.FrameAlign = B.getStructAlign();
1369	Shape.FrameSize = B.getStructSize();
1370
1371	switch (Shape.ABI) {
1372	case coro::ABI::Switch: {
1373	// In the switch ABI, remember the switch-index field.
1374	auto IndexField = B.getLayoutField(Id: *SwitchIndexFieldId);
1375	Shape.SwitchLowering.IndexField = IndexField.LayoutFieldIndex;
1376	Shape.SwitchLowering.IndexAlign = IndexField.Alignment.value();
1377	Shape.SwitchLowering.IndexOffset = IndexField.Offset;
1378
1379	// Also round the frame size up to a multiple of its alignment, as is
1380	// generally expected in C/C++.
1381	Shape.FrameSize = alignTo(Size: Shape.FrameSize, A: Shape.FrameAlign);
1382	break;
1383	}
1384
1385	// In the retcon ABI, remember whether the frame is inline in the storage.
1386	case coro::ABI::Retcon:
1387	case coro::ABI::RetconOnce: {
1388	auto Id = Shape.getRetconCoroId();
1389	Shape.RetconLowering.IsFrameInlineInStorage
1390	= (B.getStructSize() <= Id->getStorageSize() &&
1391	B.getStructAlign() <= Id->getStorageAlignment());
1392	break;
1393	}
1394	case coro::ABI::Async: {
1395	Shape.AsyncLowering.FrameOffset =
1396	alignTo(Size: Shape.AsyncLowering.ContextHeaderSize, A: Shape.FrameAlign);
1397	// Also make the final context size a multiple of the context alignment to
1398	// make allocation easier for allocators.
1399	Shape.AsyncLowering.ContextSize =
1400	alignTo(Size: Shape.AsyncLowering.FrameOffset + Shape.FrameSize,
1401	A: Shape.AsyncLowering.getContextAlignment());
1402	if (Shape.AsyncLowering.getContextAlignment() < Shape.FrameAlign) {
1403	report_fatal_error(
1404	reason: "The alignment requirment of frame variables cannot be higher than "
1405	"the alignment of the async function context");
1406	}
1407	break;
1408	}
1409	}
1410
1411	return FrameTy;
1412	}
1413
1414	// We use a pointer use visitor to track how an alloca is being used.
1415	// The goal is to be able to answer the following three questions:
1416	// 1. Should this alloca be allocated on the frame instead.
1417	// 2. Could the content of the alloca be modified prior to CoroBegn, which would
1418	// require copying the data from alloca to the frame after CoroBegin.
1419	// 3. Is there any alias created for this alloca prior to CoroBegin, but used
1420	// after CoroBegin. In that case, we will need to recreate the alias after
1421	// CoroBegin based off the frame. To answer question 1, we track two things:
1422	// a. List of all BasicBlocks that use this alloca or any of the aliases of
1423	// the alloca. In the end, we check if there exists any two basic blocks that
1424	// cross suspension points. If so, this alloca must be put on the frame. b.
1425	// Whether the alloca or any alias of the alloca is escaped at some point,
1426	// either by storing the address somewhere, or the address is used in a
1427	// function call that might capture. If it's ever escaped, this alloca must be
1428	// put on the frame conservatively.
1429	// To answer quetion 2, we track through the variable MayWriteBeforeCoroBegin.
1430	// Whenever a potential write happens, either through a store instruction, a
1431	// function call or any of the memory intrinsics, we check whether this
1432	// instruction is prior to CoroBegin. To answer question 3, we track the offsets
1433	// of all aliases created for the alloca prior to CoroBegin but used after
1434	// CoroBegin. std::optional is used to be able to represent the case when the
1435	// offset is unknown (e.g. when you have a PHINode that takes in different
1436	// offset values). We cannot handle unknown offsets and will assert. This is the
1437	// potential issue left out. An ideal solution would likely require a
1438	// significant redesign.
1439	namespace {
1440	struct AllocaUseVisitor : PtrUseVisitor<AllocaUseVisitor> {
1441	using Base = PtrUseVisitor<AllocaUseVisitor>;
1442	AllocaUseVisitor(const DataLayout &DL, const DominatorTree &DT,
1443	const CoroBeginInst &CB, const SuspendCrossingInfo &Checker,
1444	bool ShouldUseLifetimeStartInfo)
1445	: PtrUseVisitor(DL), DT(DT), CoroBegin(CB), Checker(Checker),
1446	ShouldUseLifetimeStartInfo(ShouldUseLifetimeStartInfo) {}
1447
1448	void visit(Instruction &I) {
1449	Users.insert(Ptr: &I);
1450	Base::visit(I);
1451	// If the pointer is escaped prior to CoroBegin, we have to assume it would
1452	// be written into before CoroBegin as well.
1453	if (PI.isEscaped() && !DT.dominates(Def: &CoroBegin, User: PI.getEscapingInst())) {
1454	MayWriteBeforeCoroBegin = true;
1455	}
1456	}
1457	// We need to provide this overload as PtrUseVisitor uses a pointer based
1458	// visiting function.
1459	void visit(Instruction *I) { return visit(I&: *I); }
1460
1461	void visitPHINode(PHINode &I) {
1462	enqueueUsers(I);
1463	handleAlias(I);
1464	}
1465
1466	void visitSelectInst(SelectInst &I) {
1467	enqueueUsers(I);
1468	handleAlias(I);
1469	}
1470
1471	void visitStoreInst(StoreInst &SI) {
1472	// Regardless whether the alias of the alloca is the value operand or the
1473	// pointer operand, we need to assume the alloca is been written.
1474	handleMayWrite(I: SI);
1475
1476	if (SI.getValueOperand() != U->get())
1477	return;
1478
1479	// We are storing the pointer into a memory location, potentially escaping.
1480	// As an optimization, we try to detect simple cases where it doesn't
1481	// actually escape, for example:
1482	// %ptr = alloca ..
1483	// %addr = alloca ..
1484	// store %ptr, %addr
1485	// %x = load %addr
1486	// ..
1487	// If %addr is only used by loading from it, we could simply treat %x as
1488	// another alias of %ptr, and not considering %ptr being escaped.
1489	auto IsSimpleStoreThenLoad = [&]() {
1490	auto *AI = dyn_cast<AllocaInst>(Val: SI.getPointerOperand());
1491	// If the memory location we are storing to is not an alloca, it
1492	// could be an alias of some other memory locations, which is difficult
1493	// to analyze.
1494	if (!AI)
1495	return false;
1496	// StoreAliases contains aliases of the memory location stored into.
1497	SmallVector<Instruction *, 4> StoreAliases = {AI};
1498	while (!StoreAliases.empty()) {
1499	Instruction *I = StoreAliases.pop_back_val();
1500	for (User *U : I->users()) {
1501	// If we are loading from the memory location, we are creating an
1502	// alias of the original pointer.
1503	if (auto *LI = dyn_cast<LoadInst>(Val: U)) {
1504	enqueueUsers(I&: *LI);
1505	handleAlias(I&: *LI);
1506	continue;
1507	}
1508	// If we are overriding the memory location, the pointer certainly
1509	// won't escape.
1510	if (auto *S = dyn_cast<StoreInst>(Val: U))
1511	if (S->getPointerOperand() == I)
1512	continue;
1513	if (auto *II = dyn_cast<IntrinsicInst>(Val: U))
1514	if (II->isLifetimeStartOrEnd())
1515	continue;
1516	// BitCastInst creats aliases of the memory location being stored
1517	// into.
1518	if (auto *BI = dyn_cast<BitCastInst>(Val: U)) {
1519	StoreAliases.push_back(Elt: BI);
1520	continue;
1521	}
1522	return false;
1523	}
1524	}
1525
1526	return true;
1527	};
1528
1529	if (!IsSimpleStoreThenLoad())
1530	PI.setEscaped(&SI);
1531	}
1532
1533	// All mem intrinsics modify the data.
1534	void visitMemIntrinsic(MemIntrinsic &MI) { handleMayWrite(I: MI); }
1535
1536	void visitBitCastInst(BitCastInst &BC) {
1537	Base::visitBitCastInst(BC);
1538	handleAlias(I&: BC);
1539	}
1540
1541	void visitAddrSpaceCastInst(AddrSpaceCastInst &ASC) {
1542	Base::visitAddrSpaceCastInst(ASC);
1543	handleAlias(I&: ASC);
1544	}
1545
1546	void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
1547	// The base visitor will adjust Offset accordingly.
1548	Base::visitGetElementPtrInst(GEPI);
1549	handleAlias(I&: GEPI);
1550	}
1551
1552	void visitIntrinsicInst(IntrinsicInst &II) {
1553	// When we found the lifetime markers refers to a
1554	// subrange of the original alloca, ignore the lifetime
1555	// markers to avoid misleading the analysis.
1556	if (II.getIntrinsicID() != Intrinsic::lifetime_start || !IsOffsetKnown ||
1557	!Offset.isZero())
1558	return Base::visitIntrinsicInst(II);
1559	LifetimeStarts.insert(Ptr: &II);
1560	}
1561
1562	void visitCallBase(CallBase &CB) {
1563	for (unsigned Op = 0, OpCount = CB.arg_size(); Op < OpCount; ++Op)
1564	if (U->get() == CB.getArgOperand(i: Op) && !CB.doesNotCapture(OpNo: Op))
1565	PI.setEscaped(&CB);
1566	handleMayWrite(I: CB);
1567	}
1568
1569	bool getShouldLiveOnFrame() const {
1570	if (!ShouldLiveOnFrame)
1571	ShouldLiveOnFrame = computeShouldLiveOnFrame();
1572	return *ShouldLiveOnFrame;
1573	}
1574
1575	bool getMayWriteBeforeCoroBegin() const { return MayWriteBeforeCoroBegin; }
1576
1577	DenseMap<Instruction *, std::optional<APInt>> getAliasesCopy() const {
1578	assert(getShouldLiveOnFrame() && "This method should only be called if the "
1579	"alloca needs to live on the frame.");
1580	for (const auto &P : AliasOffetMap)
1581	if (!P.second)
1582	report_fatal_error(reason: "Unable to handle an alias with unknown offset "
1583	"created before CoroBegin.");
1584	return AliasOffetMap;
1585	}
1586
1587	private:
1588	const DominatorTree &DT;
1589	const CoroBeginInst &CoroBegin;
1590	const SuspendCrossingInfo &Checker;
1591	// All alias to the original AllocaInst, created before CoroBegin and used
1592	// after CoroBegin. Each entry contains the instruction and the offset in the
1593	// original Alloca. They need to be recreated after CoroBegin off the frame.
1594	DenseMap<Instruction *, std::optional<APInt>> AliasOffetMap{};
1595	SmallPtrSet<Instruction *, 4> Users{};
1596	SmallPtrSet<IntrinsicInst *, 2> LifetimeStarts{};
1597	bool MayWriteBeforeCoroBegin{false};
1598	bool ShouldUseLifetimeStartInfo{true};
1599
1600	mutable std::optional<bool> ShouldLiveOnFrame{};
1601
1602	bool computeShouldLiveOnFrame() const {
1603	// If lifetime information is available, we check it first since it's
1604	// more precise. We look at every pair of lifetime.start intrinsic and
1605	// every basic block that uses the pointer to see if they cross suspension
1606	// points. The uses cover both direct uses as well as indirect uses.
1607	if (ShouldUseLifetimeStartInfo && !LifetimeStarts.empty()) {
1608	for (auto *I : Users)
1609	for (auto *S : LifetimeStarts)
1610	if (Checker.isDefinitionAcrossSuspend(I&: *S, U: I))
1611	return true;
1612	// Addresses are guaranteed to be identical after every lifetime.start so
1613	// we cannot use the local stack if the address escaped and there is a
1614	// suspend point between lifetime markers. This should also cover the
1615	// case of a single lifetime.start intrinsic in a loop with suspend point.
1616	if (PI.isEscaped()) {
1617	for (auto *A : LifetimeStarts) {
1618	for (auto *B : LifetimeStarts) {
1619	if (Checker.hasPathOrLoopCrossingSuspendPoint(From: A->getParent(),
1620	To: B->getParent()))
1621	return true;
1622	}
1623	}
1624	}
1625	return false;
1626	}
1627	// FIXME: Ideally the isEscaped check should come at the beginning.
1628	// However there are a few loose ends that need to be fixed first before
1629	// we can do that. We need to make sure we are not over-conservative, so
1630	// that the data accessed in-between await_suspend and symmetric transfer
1631	// is always put on the stack, and also data accessed after coro.end is
1632	// always put on the stack (esp the return object). To fix that, we need
1633	// to:
1634	// 1) Potentially treat sret as nocapture in calls
1635	// 2) Special handle the return object and put it on the stack
1636	// 3) Utilize lifetime.end intrinsic
1637	if (PI.isEscaped())
1638	return true;
1639
1640	for (auto *U1 : Users)
1641	for (auto *U2 : Users)
1642	if (Checker.isDefinitionAcrossSuspend(I&: *U1, U: U2))
1643	return true;
1644
1645	return false;
1646	}
1647
1648	void handleMayWrite(const Instruction &I) {
1649	if (!DT.dominates(Def: &CoroBegin, User: &I))
1650	MayWriteBeforeCoroBegin = true;
1651	}
1652
1653	bool usedAfterCoroBegin(Instruction &I) {
1654	for (auto &U : I.uses())
1655	if (DT.dominates(Def: &CoroBegin, U))
1656	return true;
1657	return false;
1658	}
1659
1660	void handleAlias(Instruction &I) {
1661	// We track all aliases created prior to CoroBegin but used after.
1662	// These aliases may need to be recreated after CoroBegin if the alloca
1663	// need to live on the frame.
1664	if (DT.dominates(Def: &CoroBegin, User: &I) || !usedAfterCoroBegin(I))
1665	return;
1666
1667	if (!IsOffsetKnown) {
1668	AliasOffetMap[&I].reset();
1669	} else {
1670	auto Itr = AliasOffetMap.find(Val: &I);
1671	if (Itr == AliasOffetMap.end()) {
1672	AliasOffetMap[&I] = Offset;
1673	} else if (Itr->second && *Itr->second != Offset) {
1674	// If we have seen two different possible values for this alias, we set
1675	// it to empty.
1676	AliasOffetMap[&I].reset();
1677	}
1678	}
1679	}
1680	};
1681	} // namespace
1682
1683	// We need to make room to insert a spill after initial PHIs, but before
1684	// catchswitch instruction. Placing it before violates the requirement that
1685	// catchswitch, like all other EHPads must be the first nonPHI in a block.
1686	//
1687	// Split away catchswitch into a separate block and insert in its place:
1688	//
1689	// cleanuppad <InsertPt> cleanupret.
1690	//
1691	// cleanupret instruction will act as an insert point for the spill.
1692	static Instruction *splitBeforeCatchSwitch(CatchSwitchInst *CatchSwitch) {
1693	BasicBlock *CurrentBlock = CatchSwitch->getParent();
1694	BasicBlock *NewBlock = CurrentBlock->splitBasicBlock(I: CatchSwitch);
1695	CurrentBlock->getTerminator()->eraseFromParent();
1696
1697	auto *CleanupPad =
1698	CleanupPadInst::Create(ParentPad: CatchSwitch->getParentPad(), Args: {}, NameStr: "", InsertAtEnd: CurrentBlock);
1699	auto *CleanupRet =
1700	CleanupReturnInst::Create(CleanupPad, UnwindBB: NewBlock, InsertAtEnd: CurrentBlock);
1701	return CleanupRet;
1702	}
1703
1704	// Replace all alloca and SSA values that are accessed across suspend points
1705	// with GetElementPointer from coroutine frame + loads and stores. Create an
1706	// AllocaSpillBB that will become the new entry block for the resume parts of
1707	// the coroutine:
1708	//
1709	// %hdl = coro.begin(...)
1710	// whatever
1711	//
1712	// becomes:
1713	//
1714	// %hdl = coro.begin(...)
1715	// br label %AllocaSpillBB
1716	//
1717	// AllocaSpillBB:
1718	// ; geps corresponding to allocas that were moved to coroutine frame
1719	// br label PostSpill
1720	//
1721	// PostSpill:
1722	// whatever
1723	//
1724	//
1725	static void insertSpills(const FrameDataInfo &FrameData, coro::Shape &Shape) {
1726	auto *CB = Shape.CoroBegin;
1727	LLVMContext &C = CB->getContext();
1728	Function *F = CB->getFunction();
1729	IRBuilder<> Builder(C);
1730	StructType *FrameTy = Shape.FrameTy;
1731	Value *FramePtr = Shape.FramePtr;
1732	DominatorTree DT(*F);
1733	SmallDenseMap<Argument *, AllocaInst *, 4> ArgToAllocaMap;
1734
1735	// Create a GEP with the given index into the coroutine frame for the original
1736	// value Orig. Appends an extra 0 index for array-allocas, preserving the
1737	// original type.
1738	auto GetFramePointer = [&](Value *Orig) -> Value * {
1739	FieldIDType Index = FrameData.getFieldIndex(V: Orig);
1740	SmallVector<Value *, 3> Indices = {
1741	ConstantInt::get(Ty: Type::getInt32Ty(C), V: 0),
1742	ConstantInt::get(Ty: Type::getInt32Ty(C), V: Index),
1743	};
1744
1745	if (auto *AI = dyn_cast<AllocaInst>(Val: Orig)) {
1746	if (auto *CI = dyn_cast<ConstantInt>(Val: AI->getArraySize())) {
1747	auto Count = CI->getValue().getZExtValue();
1748	if (Count > 1) {
1749	Indices.push_back(Elt: ConstantInt::get(Ty: Type::getInt32Ty(C), V: 0));
1750	}
1751	} else {
1752	report_fatal_error(reason: "Coroutines cannot handle non static allocas yet");
1753	}
1754	}
1755
1756	auto GEP = cast<GetElementPtrInst>(
1757	Val: Builder.CreateInBoundsGEP(Ty: FrameTy, Ptr: FramePtr, IdxList: Indices));
1758	if (auto *AI = dyn_cast<AllocaInst>(Val: Orig)) {
1759	if (FrameData.getDynamicAlign(V: Orig) != 0) {
1760	assert(FrameData.getDynamicAlign(Orig) == AI->getAlign().value());
1761	auto *M = AI->getModule();
1762	auto *IntPtrTy = M->getDataLayout().getIntPtrType(AI->getType());
1763	auto *PtrValue = Builder.CreatePtrToInt(V: GEP, DestTy: IntPtrTy);
1764	auto *AlignMask =
1765	ConstantInt::get(Ty: IntPtrTy, V: AI->getAlign().value() - 1);
1766	PtrValue = Builder.CreateAdd(LHS: PtrValue, RHS: AlignMask);
1767	PtrValue = Builder.CreateAnd(LHS: PtrValue, RHS: Builder.CreateNot(V: AlignMask));
1768	return Builder.CreateIntToPtr(V: PtrValue, DestTy: AI->getType());
1769	}
1770	// If the type of GEP is not equal to the type of AllocaInst, it implies
1771	// that the AllocaInst may be reused in the Frame slot of other
1772	// AllocaInst. So We cast GEP to the AllocaInst here to re-use
1773	// the Frame storage.
1774	//
1775	// Note: If we change the strategy dealing with alignment, we need to refine
1776	// this casting.
1777	if (GEP->getType() != Orig->getType())
1778	return Builder.CreateAddrSpaceCast(V: GEP, DestTy: Orig->getType(),
1779	Name: Orig->getName() + Twine(".cast"));
1780	}
1781	return GEP;
1782	};
1783
1784	for (auto const &E : FrameData.Spills) {
1785	Value *Def = E.first;
1786	auto SpillAlignment = Align(FrameData.getAlign(V: Def));
1787	// Create a store instruction storing the value into the
1788	// coroutine frame.
1789	BasicBlock::iterator InsertPt;
1790	Type *ByValTy = nullptr;
1791	if (auto *Arg = dyn_cast<Argument>(Val: Def)) {
1792	// For arguments, we will place the store instruction right after
1793	// the coroutine frame pointer instruction, i.e. coro.begin.
1794	InsertPt = Shape.getInsertPtAfterFramePtr();
1795
1796	// If we're spilling an Argument, make sure we clear 'nocapture'
1797	// from the coroutine function.
1798	Arg->getParent()->removeParamAttr(Arg->getArgNo(), Attribute::NoCapture);
1799
1800	if (Arg->hasByValAttr())
1801	ByValTy = Arg->getParamByValType();
1802	} else if (auto *CSI = dyn_cast<AnyCoroSuspendInst>(Val: Def)) {
1803	// Don't spill immediately after a suspend; splitting assumes
1804	// that the suspend will be followed by a branch.
1805	InsertPt = CSI->getParent()->getSingleSuccessor()->getFirstNonPHIIt();
1806	} else {
1807	auto *I = cast<Instruction>(Val: Def);
1808	if (!DT.dominates(Def: CB, User: I)) {
1809	// If it is not dominated by CoroBegin, then spill should be
1810	// inserted immediately after CoroFrame is computed.
1811	InsertPt = Shape.getInsertPtAfterFramePtr();
1812	} else if (auto *II = dyn_cast<InvokeInst>(Val: I)) {
1813	// If we are spilling the result of the invoke instruction, split
1814	// the normal edge and insert the spill in the new block.
1815	auto *NewBB = SplitEdge(From: II->getParent(), To: II->getNormalDest());
1816	InsertPt = NewBB->getTerminator()->getIterator();
1817	} else if (isa<PHINode>(Val: I)) {
1818	// Skip the PHINodes and EH pads instructions.
1819	BasicBlock *DefBlock = I->getParent();
1820	if (auto *CSI = dyn_cast<CatchSwitchInst>(Val: DefBlock->getTerminator()))
1821	InsertPt = splitBeforeCatchSwitch(CatchSwitch: CSI)->getIterator();
1822	else
1823	InsertPt = DefBlock->getFirstInsertionPt();
1824	} else {
1825	assert(!I->isTerminator() && "unexpected terminator");
1826	// For all other values, the spill is placed immediately after
1827	// the definition.
1828	InsertPt = I->getNextNode()->getIterator();
1829	}
1830	}
1831
1832	auto Index = FrameData.getFieldIndex(V: Def);
1833	Builder.SetInsertPoint(TheBB: InsertPt->getParent(), IP: InsertPt);
1834	auto *G = Builder.CreateConstInBoundsGEP2_32(
1835	Ty: FrameTy, Ptr: FramePtr, Idx0: 0, Idx1: Index, Name: Def->getName() + Twine(".spill.addr"));
1836	if (ByValTy) {
1837	// For byval arguments, we need to store the pointed value in the frame,
1838	// instead of the pointer itself.
1839	auto *Value = Builder.CreateLoad(Ty: ByValTy, Ptr: Def);
1840	Builder.CreateAlignedStore(Val: Value, Ptr: G, Align: SpillAlignment);
1841	} else {
1842	Builder.CreateAlignedStore(Val: Def, Ptr: G, Align: SpillAlignment);
1843	}
1844
1845	BasicBlock *CurrentBlock = nullptr;
1846	Value *CurrentReload = nullptr;
1847	for (auto *U : E.second) {
1848	// If we have not seen the use block, create a load instruction to reload
1849	// the spilled value from the coroutine frame. Populates the Value pointer
1850	// reference provided with the frame GEP.
1851	if (CurrentBlock != U->getParent()) {
1852	CurrentBlock = U->getParent();
1853	Builder.SetInsertPoint(TheBB: CurrentBlock,
1854	IP: CurrentBlock->getFirstInsertionPt());
1855
1856	auto *GEP = GetFramePointer(E.first);
1857	GEP->setName(E.first->getName() + Twine(".reload.addr"));
1858	if (ByValTy)
1859	CurrentReload = GEP;
1860	else
1861	CurrentReload = Builder.CreateAlignedLoad(
1862	Ty: FrameTy->getElementType(N: FrameData.getFieldIndex(V: E.first)), Ptr: GEP,
1863	Align: SpillAlignment, Name: E.first->getName() + Twine(".reload"));
1864
1865	TinyPtrVector<DbgDeclareInst *> DIs = findDbgDeclares(V: Def);
1866	TinyPtrVector<DbgVariableRecord *> DVRs = findDVRDeclares(V: Def);
1867	// Try best to find dbg.declare. If the spill is a temp, there may not
1868	// be a direct dbg.declare. Walk up the load chain to find one from an
1869	// alias.
1870	if (F->getSubprogram()) {
1871	auto *CurDef = Def;
1872	while (DIs.empty() && DVRs.empty() && isa<LoadInst>(Val: CurDef)) {
1873	auto *LdInst = cast<LoadInst>(Val: CurDef);
1874	// Only consider ptr to ptr same type load.
1875	if (LdInst->getPointerOperandType() != LdInst->getType())
1876	break;
1877	CurDef = LdInst->getPointerOperand();
1878	if (!isa<AllocaInst, LoadInst>(Val: CurDef))
1879	break;
1880	DIs = findDbgDeclares(V: CurDef);
1881	DVRs = findDVRDeclares(V: CurDef);
1882	}
1883	}
1884
1885	auto SalvageOne = [&](auto *DDI) {
1886	bool AllowUnresolved = false;
1887	// This dbg.declare is preserved for all coro-split function
1888	// fragments. It will be unreachable in the main function, and
1889	// processed by coro::salvageDebugInfo() by CoroCloner.
1890	if (UseNewDbgInfoFormat) {
1891	DbgVariableRecord *NewDVR = new DbgVariableRecord(
1892	ValueAsMetadata::get(V: CurrentReload), DDI->getVariable(),
1893	DDI->getExpression(), DDI->getDebugLoc(),
1894	DbgVariableRecord::LocationType::Declare);
1895	Builder.GetInsertPoint()->getParent()->insertDbgRecordBefore(
1896	DR: NewDVR, Here: Builder.GetInsertPoint());
1897	} else {
1898	DIBuilder(*CurrentBlock->getParent()->getParent(), AllowUnresolved)
1899	.insertDeclare(CurrentReload, DDI->getVariable(),
1900	DDI->getExpression(), DDI->getDebugLoc(),
1901	&*Builder.GetInsertPoint());
1902	}
1903	// This dbg.declare is for the main function entry point. It
1904	// will be deleted in all coro-split functions.
1905	coro::salvageDebugInfo(ArgToAllocaMap, *DDI, Shape.OptimizeFrame,
1906	false /*UseEntryValue*/);
1907	};
1908	for_each(Range&: DIs, F: SalvageOne);
1909	for_each(Range&: DVRs, F: SalvageOne);
1910	}
1911
1912	// If we have a single edge PHINode, remove it and replace it with a
1913	// reload from the coroutine frame. (We already took care of multi edge
1914	// PHINodes by rewriting them in the rewritePHIs function).
1915	if (auto *PN = dyn_cast<PHINode>(Val: U)) {
1916	assert(PN->getNumIncomingValues() == 1 &&
1917	"unexpected number of incoming "
1918	"values in the PHINode");
1919	PN->replaceAllUsesWith(V: CurrentReload);
1920	PN->eraseFromParent();
1921	continue;
1922	}
1923
1924	// Replace all uses of CurrentValue in the current instruction with
1925	// reload.
1926	U->replaceUsesOfWith(From: Def, To: CurrentReload);
1927	// Instructions are added to Def's user list if the attached
1928	// debug records use Def. Update those now.
1929	for (DbgVariableRecord &DVR : filterDbgVars(R: U->getDbgRecordRange()))
1930	DVR.replaceVariableLocationOp(OldValue: Def, NewValue: CurrentReload, AllowEmpty: true);
1931	}
1932	}
1933
1934	BasicBlock *FramePtrBB = Shape.getInsertPtAfterFramePtr()->getParent();
1935
1936	auto SpillBlock = FramePtrBB->splitBasicBlock(
1937	I: Shape.getInsertPtAfterFramePtr(), BBName: "AllocaSpillBB");
1938	SpillBlock->splitBasicBlock(I: &SpillBlock->front(), BBName: "PostSpill");
1939	Shape.AllocaSpillBlock = SpillBlock;
1940
1941	// retcon and retcon.once lowering assumes all uses have been sunk.
1942	if (Shape.ABI == coro::ABI::Retcon || Shape.ABI == coro::ABI::RetconOnce ||
1943	Shape.ABI == coro::ABI::Async) {
1944	// If we found any allocas, replace all of their remaining uses with Geps.
1945	Builder.SetInsertPoint(TheBB: SpillBlock, IP: SpillBlock->begin());
1946	for (const auto &P : FrameData.Allocas) {
1947	AllocaInst *Alloca = P.Alloca;
1948	auto *G = GetFramePointer(Alloca);
1949
1950	// We are not using ReplaceInstWithInst(P.first, cast<Instruction>(G))
1951	// here, as we are changing location of the instruction.
1952	G->takeName(V: Alloca);
1953	Alloca->replaceAllUsesWith(V: G);
1954	Alloca->eraseFromParent();
1955	}
1956	return;
1957	}
1958
1959	// If we found any alloca, replace all of their remaining uses with GEP
1960	// instructions. To remain debugbility, we replace the uses of allocas for
1961	// dbg.declares and dbg.values with the reload from the frame.
1962	// Note: We cannot replace the alloca with GEP instructions indiscriminately,
1963	// as some of the uses may not be dominated by CoroBegin.
1964	Builder.SetInsertPoint(TheBB: Shape.AllocaSpillBlock,
1965	IP: Shape.AllocaSpillBlock->begin());
1966	SmallVector<Instruction *, 4> UsersToUpdate;
1967	for (const auto &A : FrameData.Allocas) {
1968	AllocaInst *Alloca = A.Alloca;
1969	UsersToUpdate.clear();
1970	for (User *U : Alloca->users()) {
1971	auto *I = cast<Instruction>(Val: U);
1972	if (DT.dominates(Def: CB, User: I))
1973	UsersToUpdate.push_back(Elt: I);
1974	}
1975	if (UsersToUpdate.empty())
1976	continue;
1977	auto *G = GetFramePointer(Alloca);
1978	G->setName(Alloca->getName() + Twine(".reload.addr"));
1979
1980	SmallVector<DbgVariableIntrinsic *, 4> DIs;
1981	SmallVector<DbgVariableRecord *> DbgVariableRecords;
1982	findDbgUsers(DbgInsts&: DIs, V: Alloca, DbgVariableRecords: &DbgVariableRecords);
1983	for (auto *DVI : DIs)
1984	DVI->replaceUsesOfWith(From: Alloca, To: G);
1985	for (auto *DVR : DbgVariableRecords)
1986	DVR->replaceVariableLocationOp(OldValue: Alloca, NewValue: G);
1987
1988	for (Instruction *I : UsersToUpdate) {
1989	// It is meaningless to retain the lifetime intrinsics refer for the
1990	// member of coroutine frames and the meaningless lifetime intrinsics
1991	// are possible to block further optimizations.
1992	if (I->isLifetimeStartOrEnd()) {
1993	I->eraseFromParent();
1994	continue;
1995	}
1996
1997	I->replaceUsesOfWith(From: Alloca, To: G);
1998	}
1999	}
2000	Builder.SetInsertPoint(&*Shape.getInsertPtAfterFramePtr());
2001	for (const auto &A : FrameData.Allocas) {
2002	AllocaInst *Alloca = A.Alloca;
2003	if (A.MayWriteBeforeCoroBegin) {
2004	// isEscaped really means potentially modified before CoroBegin.
2005	if (Alloca->isArrayAllocation())
2006	report_fatal_error(
2007	reason: "Coroutines cannot handle copying of array allocas yet");
2008
2009	auto *G = GetFramePointer(Alloca);
2010	auto *Value = Builder.CreateLoad(Ty: Alloca->getAllocatedType(), Ptr: Alloca);
2011	Builder.CreateStore(Val: Value, Ptr: G);
2012	}
2013	// For each alias to Alloca created before CoroBegin but used after
2014	// CoroBegin, we recreate them after CoroBegin by appplying the offset
2015	// to the pointer in the frame.
2016	for (const auto &Alias : A.Aliases) {
2017	auto *FramePtr = GetFramePointer(Alloca);
2018	auto &Value = *Alias.second;
2019	auto ITy = IntegerType::get(C, NumBits: Value.getBitWidth());
2020	auto *AliasPtr =
2021	Builder.CreatePtrAdd(Ptr: FramePtr, Offset: ConstantInt::get(Ty: ITy, V: Value));
2022	Alias.first->replaceUsesWithIf(
2023	New: AliasPtr, ShouldReplace: [&](Use &U) { return DT.dominates(Def: CB, U); });
2024	}
2025	}
2026
2027	// PromiseAlloca is not collected in FrameData.Allocas. So we don't handle
2028	// the case that the PromiseAlloca may have writes before CoroBegin in the
2029	// above codes. And it may be problematic in edge cases. See
2030	// https://github.com/llvm/llvm-project/issues/57861 for an example.
2031	if (Shape.ABI == coro::ABI::Switch && Shape.SwitchLowering.PromiseAlloca) {
2032	AllocaInst *PA = Shape.SwitchLowering.PromiseAlloca;
2033	// If there is memory accessing to promise alloca before CoroBegin;
2034	bool HasAccessingPromiseBeforeCB = llvm::any_of(Range: PA->uses(), P: [&](Use &U) {
2035	auto *Inst = dyn_cast<Instruction>(Val: U.getUser());
2036	if (!Inst || DT.dominates(Def: CB, User: Inst))
2037	return false;
2038
2039	if (auto *CI = dyn_cast<CallInst>(Val: Inst)) {
2040	// It is fine if the call wouldn't write to the Promise.
2041	// This is possible for @llvm.coro.id intrinsics, which
2042	// would take the promise as the second argument as a
2043	// marker.
2044	if (CI->onlyReadsMemory() ||
2045	CI->onlyReadsMemory(OpNo: CI->getArgOperandNo(U: &U)))
2046	return false;
2047	return true;
2048	}
2049
2050	return isa<StoreInst>(Val: Inst) ||
2051	// It may take too much time to track the uses.
2052	// Be conservative about the case the use may escape.
2053	isa<GetElementPtrInst>(Val: Inst) ||
2054	// There would always be a bitcast for the promise alloca
2055	// before we enabled Opaque pointers. And now given
2056	// opaque pointers are enabled by default. This should be
2057	// fine.
2058	isa<BitCastInst>(Val: Inst);
2059	});
2060	if (HasAccessingPromiseBeforeCB) {
2061	Builder.SetInsertPoint(&*Shape.getInsertPtAfterFramePtr());
2062	auto *G = GetFramePointer(PA);
2063	auto *Value = Builder.CreateLoad(Ty: PA->getAllocatedType(), Ptr: PA);
2064	Builder.CreateStore(Val: Value, Ptr: G);
2065	}
2066	}
2067	}
2068
2069	// Moves the values in the PHIs in SuccBB that correspong to PredBB into a new
2070	// PHI in InsertedBB.
2071	static void movePHIValuesToInsertedBlock(BasicBlock *SuccBB,
2072	BasicBlock *InsertedBB,
2073	BasicBlock *PredBB,
2074	PHINode *UntilPHI = nullptr) {
2075	auto *PN = cast<PHINode>(Val: &SuccBB->front());
2076	do {
2077	int Index = PN->getBasicBlockIndex(BB: InsertedBB);
2078	Value *V = PN->getIncomingValue(i: Index);
2079	PHINode *InputV = PHINode::Create(
2080	Ty: V->getType(), NumReservedValues: 1, NameStr: V->getName() + Twine(".") + SuccBB->getName());
2081	InputV->insertBefore(InsertPos: InsertedBB->begin());
2082	InputV->addIncoming(V, BB: PredBB);
2083	PN->setIncomingValue(i: Index, V: InputV);
2084	PN = dyn_cast<PHINode>(Val: PN->getNextNode());
2085	} while (PN != UntilPHI);
2086	}
2087
2088	// Rewrites the PHI Nodes in a cleanuppad.
2089	static void rewritePHIsForCleanupPad(BasicBlock *CleanupPadBB,
2090	CleanupPadInst *CleanupPad) {
2091	// For every incoming edge to a CleanupPad we will create a new block holding
2092	// all incoming values in single-value PHI nodes. We will then create another
2093	// block to act as a dispather (as all unwind edges for related EH blocks
2094	// must be the same).
2095	//
2096	// cleanuppad:
2097	// %2 = phi i32[%0, %catchswitch], [%1, %catch.1]
2098	// %3 = cleanuppad within none []
2099	//
2100	// It will create:
2101	//
2102	// cleanuppad.corodispatch
2103	// %2 = phi i8[0, %catchswitch], [1, %catch.1]
2104	// %3 = cleanuppad within none []
2105	// switch i8 % 2, label %unreachable
2106	// [i8 0, label %cleanuppad.from.catchswitch
2107	// i8 1, label %cleanuppad.from.catch.1]
2108	// cleanuppad.from.catchswitch:
2109	// %4 = phi i32 [%0, %catchswitch]
2110	// br %label cleanuppad
2111	// cleanuppad.from.catch.1:
2112	// %6 = phi i32 [%1, %catch.1]
2113	// br %label cleanuppad
2114	// cleanuppad:
2115	// %8 = phi i32 [%4, %cleanuppad.from.catchswitch],
2116	// [%6, %cleanuppad.from.catch.1]
2117
2118	// Unreachable BB, in case switching on an invalid value in the dispatcher.
2119	auto *UnreachBB = BasicBlock::Create(
2120	Context&: CleanupPadBB->getContext(), Name: "unreachable", Parent: CleanupPadBB->getParent());
2121	IRBuilder<> Builder(UnreachBB);
2122	Builder.CreateUnreachable();
2123
2124	// Create a new cleanuppad which will be the dispatcher.
2125	auto *NewCleanupPadBB =
2126	BasicBlock::Create(Context&: CleanupPadBB->getContext(),
2127	Name: CleanupPadBB->getName() + Twine(".corodispatch"),
2128	Parent: CleanupPadBB->getParent(), InsertBefore: CleanupPadBB);
2129	Builder.SetInsertPoint(NewCleanupPadBB);
2130	auto *SwitchType = Builder.getInt8Ty();
2131	auto *SetDispatchValuePN =
2132	Builder.CreatePHI(Ty: SwitchType, NumReservedValues: pred_size(BB: CleanupPadBB));
2133	CleanupPad->removeFromParent();
2134	CleanupPad->insertAfter(InsertPos: SetDispatchValuePN);
2135	auto *SwitchOnDispatch = Builder.CreateSwitch(V: SetDispatchValuePN, Dest: UnreachBB,
2136	NumCases: pred_size(BB: CleanupPadBB));
2137
2138	int SwitchIndex = 0;
2139	SmallVector<BasicBlock *, 8> Preds(predecessors(BB: CleanupPadBB));
2140	for (BasicBlock *Pred : Preds) {
2141	// Create a new cleanuppad and move the PHI values to there.
2142	auto *CaseBB = BasicBlock::Create(Context&: CleanupPadBB->getContext(),
2143	Name: CleanupPadBB->getName() +
2144	Twine(".from.") + Pred->getName(),
2145	Parent: CleanupPadBB->getParent(), InsertBefore: CleanupPadBB);
2146	updatePhiNodes(DestBB: CleanupPadBB, OldPred: Pred, NewPred: CaseBB);
2147	CaseBB->setName(CleanupPadBB->getName() + Twine(".from.") +
2148	Pred->getName());
2149	Builder.SetInsertPoint(CaseBB);
2150	Builder.CreateBr(Dest: CleanupPadBB);
2151	movePHIValuesToInsertedBlock(SuccBB: CleanupPadBB, InsertedBB: CaseBB, PredBB: NewCleanupPadBB);
2152
2153	// Update this Pred to the new unwind point.
2154	setUnwindEdgeTo(TI: Pred->getTerminator(), Succ: NewCleanupPadBB);
2155
2156	// Setup the switch in the dispatcher.
2157	auto *SwitchConstant = ConstantInt::get(Ty: SwitchType, V: SwitchIndex);
2158	SetDispatchValuePN->addIncoming(V: SwitchConstant, BB: Pred);
2159	SwitchOnDispatch->addCase(OnVal: SwitchConstant, Dest: CaseBB);
2160	SwitchIndex++;
2161	}
2162	}
2163
2164	static void cleanupSinglePredPHIs(Function &F) {
2165	SmallVector<PHINode *, 32> Worklist;
2166	for (auto &BB : F) {
2167	for (auto &Phi : BB.phis()) {
2168	if (Phi.getNumIncomingValues() == 1) {
2169	Worklist.push_back(Elt: &Phi);
2170	} else
2171	break;
2172	}
2173	}
2174	while (!Worklist.empty()) {
2175	auto *Phi = Worklist.pop_back_val();
2176	auto *OriginalValue = Phi->getIncomingValue(i: 0);
2177	Phi->replaceAllUsesWith(V: OriginalValue);
2178	}
2179	}
2180
2181	static void rewritePHIs(BasicBlock &BB) {
2182	// For every incoming edge we will create a block holding all
2183	// incoming values in a single PHI nodes.
2184	//
2185	// loop:
2186	// %n.val = phi i32[%n, %entry], [%inc, %loop]
2187	//
2188	// It will create:
2189	//
2190	// loop.from.entry:
2191	// %n.loop.pre = phi i32 [%n, %entry]
2192	// br %label loop
2193	// loop.from.loop:
2194	// %inc.loop.pre = phi i32 [%inc, %loop]
2195	// br %label loop
2196	//
2197	// After this rewrite, further analysis will ignore any phi nodes with more
2198	// than one incoming edge.
2199
2200	// TODO: Simplify PHINodes in the basic block to remove duplicate
2201	// predecessors.
2202
2203	// Special case for CleanupPad: all EH blocks must have the same unwind edge
2204	// so we need to create an additional "dispatcher" block.
2205	if (auto *CleanupPad =
2206	dyn_cast_or_null<CleanupPadInst>(Val: BB.getFirstNonPHI())) {
2207	SmallVector<BasicBlock *, 8> Preds(predecessors(BB: &BB));
2208	for (BasicBlock *Pred : Preds) {
2209	if (CatchSwitchInst *CS =
2210	dyn_cast<CatchSwitchInst>(Val: Pred->getTerminator())) {
2211	// CleanupPad with a CatchSwitch predecessor: therefore this is an
2212	// unwind destination that needs to be handle specially.
2213	assert(CS->getUnwindDest() == &BB);
2214	(void)CS;
2215	rewritePHIsForCleanupPad(CleanupPadBB: &BB, CleanupPad);
2216	return;
2217	}
2218	}
2219	}
2220
2221	LandingPadInst *LandingPad = nullptr;
2222	PHINode *ReplPHI = nullptr;
2223	if ((LandingPad = dyn_cast_or_null<LandingPadInst>(Val: BB.getFirstNonPHI()))) {
2224	// ehAwareSplitEdge will clone the LandingPad in all the edge blocks.
2225	// We replace the original landing pad with a PHINode that will collect the
2226	// results from all of them.
2227	ReplPHI = PHINode::Create(Ty: LandingPad->getType(), NumReservedValues: 1, NameStr: "");
2228	ReplPHI->insertBefore(InsertPos: LandingPad->getIterator());
2229	ReplPHI->takeName(V: LandingPad);
2230	LandingPad->replaceAllUsesWith(V: ReplPHI);
2231	// We will erase the original landing pad at the end of this function after
2232	// ehAwareSplitEdge cloned it in the transition blocks.
2233	}
2234
2235	SmallVector<BasicBlock *, 8> Preds(predecessors(BB: &BB));
2236	for (BasicBlock *Pred : Preds) {
2237	auto *IncomingBB = ehAwareSplitEdge(BB: Pred, Succ: &BB, OriginalPad: LandingPad, LandingPadReplacement: ReplPHI);
2238	IncomingBB->setName(BB.getName() + Twine(".from.") + Pred->getName());
2239
2240	// Stop the moving of values at ReplPHI, as this is either null or the PHI
2241	// that replaced the landing pad.
2242	movePHIValuesToInsertedBlock(SuccBB: &BB, InsertedBB: IncomingBB, PredBB: Pred, UntilPHI: ReplPHI);
2243	}
2244
2245	if (LandingPad) {
2246	// Calls to ehAwareSplitEdge function cloned the original lading pad.
2247	// No longer need it.
2248	LandingPad->eraseFromParent();
2249	}
2250	}
2251
2252	static void rewritePHIs(Function &F) {
2253	SmallVector<BasicBlock *, 8> WorkList;
2254
2255	for (BasicBlock &BB : F)
2256	if (auto *PN = dyn_cast<PHINode>(Val: &BB.front()))
2257	if (PN->getNumIncomingValues() > 1)
2258	WorkList.push_back(Elt: &BB);
2259
2260	for (BasicBlock *BB : WorkList)
2261	rewritePHIs(BB&: *BB);
2262	}
2263
2264	/// Default materializable callback
2265	// Check for instructions that we can recreate on resume as opposed to spill
2266	// the result into a coroutine frame.
2267	bool coro::defaultMaterializable(Instruction &V) {
2268	return (isa<CastInst>(Val: &V) || isa<GetElementPtrInst>(Val: &V) ||
2269	isa<BinaryOperator>(Val: &V) || isa<CmpInst>(Val: &V) || isa<SelectInst>(Val: &V));
2270	}
2271
2272	// Check for structural coroutine intrinsics that should not be spilled into
2273	// the coroutine frame.
2274	static bool isCoroutineStructureIntrinsic(Instruction &I) {
2275	return isa<CoroIdInst>(Val: &I) || isa<CoroSaveInst>(Val: &I) ||
2276	isa<CoroSuspendInst>(Val: &I);
2277	}
2278
2279	// For each instruction identified as materializable across the suspend point,
2280	// and its associated DAG of other rematerializable instructions,
2281	// recreate the DAG of instructions after the suspend point.
2282	static void rewriteMaterializableInstructions(
2283	const SmallMapVector<Instruction *, std::unique_ptr<RematGraph>, 8>
2284	&AllRemats) {
2285	// This has to be done in 2 phases
2286	// Do the remats and record the required defs to be replaced in the
2287	// original use instructions
2288	// Once all the remats are complete, replace the uses in the final
2289	// instructions with the new defs
2290	typedef struct {
2291	Instruction *Use;
2292	Instruction *Def;
2293	Instruction *Remat;
2294	} ProcessNode;
2295
2296	SmallVector<ProcessNode> FinalInstructionsToProcess;
2297
2298	for (const auto &E : AllRemats) {
2299	Instruction *Use = E.first;
2300	Instruction *CurrentMaterialization = nullptr;
2301	RematGraph *RG = E.second.get();
2302	ReversePostOrderTraversal<RematGraph *> RPOT(RG);
2303	SmallVector<Instruction *> InstructionsToProcess;
2304
2305	// If the target use is actually a suspend instruction then we have to
2306	// insert the remats into the end of the predecessor (there should only be
2307	// one). This is so that suspend blocks always have the suspend instruction
2308	// as the first instruction.
2309	auto InsertPoint = &*Use->getParent()->getFirstInsertionPt();
2310	if (isa<AnyCoroSuspendInst>(Val: Use)) {
2311	BasicBlock *SuspendPredecessorBlock =
2312	Use->getParent()->getSinglePredecessor();
2313	assert(SuspendPredecessorBlock && "malformed coro suspend instruction");
2314	InsertPoint = SuspendPredecessorBlock->getTerminator();
2315	}
2316
2317	// Note: skip the first instruction as this is the actual use that we're
2318	// rematerializing everything for.
2319	auto I = RPOT.begin();
2320	++I;
2321	for (; I != RPOT.end(); ++I) {
2322	Instruction *D = (*I)->Node;
2323	CurrentMaterialization = D->clone();
2324	CurrentMaterialization->setName(D->getName());
2325	CurrentMaterialization->insertBefore(InsertPos: InsertPoint);
2326	InsertPoint = CurrentMaterialization;
2327
2328	// Replace all uses of Def in the instructions being added as part of this
2329	// rematerialization group
2330	for (auto &I : InstructionsToProcess)
2331	I->replaceUsesOfWith(From: D, To: CurrentMaterialization);
2332
2333	// Don't replace the final use at this point as this can cause problems
2334	// for other materializations. Instead, for any final use that uses a
2335	// define that's being rematerialized, record the replace values
2336	for (unsigned i = 0, E = Use->getNumOperands(); i != E; ++i)
2337	if (Use->getOperand(i) == D) // Is this operand pointing to oldval?
2338	FinalInstructionsToProcess.push_back(
2339	Elt: {.Use: Use, .Def: D, .Remat: CurrentMaterialization});
2340
2341	InstructionsToProcess.push_back(Elt: CurrentMaterialization);
2342	}
2343	}
2344
2345	// Finally, replace the uses with the defines that we've just rematerialized
2346	for (auto &R : FinalInstructionsToProcess) {
2347	if (auto *PN = dyn_cast<PHINode>(Val: R.Use)) {
2348	assert(PN->getNumIncomingValues() == 1 && "unexpected number of incoming "
2349	"values in the PHINode");
2350	PN->replaceAllUsesWith(V: R.Remat);
2351	PN->eraseFromParent();
2352	continue;
2353	}
2354	R.Use->replaceUsesOfWith(From: R.Def, To: R.Remat);
2355	}
2356	}
2357
2358	// Splits the block at a particular instruction unless it is the first
2359	// instruction in the block with a single predecessor.
2360	static BasicBlock *splitBlockIfNotFirst(Instruction *I, const Twine &Name) {
2361	auto *BB = I->getParent();
2362	if (&BB->front() == I) {
2363	if (BB->getSinglePredecessor()) {
2364	BB->setName(Name);
2365	return BB;
2366	}
2367	}
2368	return BB->splitBasicBlock(I, BBName: Name);
2369	}
2370
2371	// Split above and below a particular instruction so that it
2372	// will be all alone by itself in a block.
2373	static void splitAround(Instruction *I, const Twine &Name) {
2374	splitBlockIfNotFirst(I, Name);
2375	splitBlockIfNotFirst(I: I->getNextNode(), Name: "After" + Name);
2376	}
2377
2378	static bool isSuspendBlock(BasicBlock *BB) {
2379	return isa<AnyCoroSuspendInst>(Val: BB->front());
2380	}
2381
2382	typedef SmallPtrSet<BasicBlock*, 8> VisitedBlocksSet;
2383
2384	/// Does control flow starting at the given block ever reach a suspend
2385	/// instruction before reaching a block in VisitedOrFreeBBs?
2386	static bool isSuspendReachableFrom(BasicBlock *From,
2387	VisitedBlocksSet &VisitedOrFreeBBs) {
2388	// Eagerly try to add this block to the visited set. If it's already
2389	// there, stop recursing; this path doesn't reach a suspend before
2390	// either looping or reaching a freeing block.
2391	if (!VisitedOrFreeBBs.insert(Ptr: From).second)
2392	return false;
2393
2394	// We assume that we'll already have split suspends into their own blocks.
2395	if (isSuspendBlock(BB: From))
2396	return true;
2397
2398	// Recurse on the successors.
2399	for (auto *Succ : successors(BB: From)) {
2400	if (isSuspendReachableFrom(From: Succ, VisitedOrFreeBBs))
2401	return true;
2402	}
2403
2404	return false;
2405	}
2406
2407	/// Is the given alloca "local", i.e. bounded in lifetime to not cross a
2408	/// suspend point?
2409	static bool isLocalAlloca(CoroAllocaAllocInst *AI) {
2410	// Seed the visited set with all the basic blocks containing a free
2411	// so that we won't pass them up.
2412	VisitedBlocksSet VisitedOrFreeBBs;
2413	for (auto *User : AI->users()) {
2414	if (auto FI = dyn_cast<CoroAllocaFreeInst>(Val: User))
2415	VisitedOrFreeBBs.insert(Ptr: FI->getParent());
2416	}
2417
2418	return !isSuspendReachableFrom(From: AI->getParent(), VisitedOrFreeBBs);
2419	}
2420
2421	/// After we split the coroutine, will the given basic block be along
2422	/// an obvious exit path for the resumption function?
2423	static bool willLeaveFunctionImmediatelyAfter(BasicBlock *BB,
2424	unsigned depth = 3) {
2425	// If we've bottomed out our depth count, stop searching and assume
2426	// that the path might loop back.
2427	if (depth == 0) return false;
2428
2429	// If this is a suspend block, we're about to exit the resumption function.
2430	if (isSuspendBlock(BB)) return true;
2431
2432	// Recurse into the successors.
2433	for (auto *Succ : successors(BB)) {
2434	if (!willLeaveFunctionImmediatelyAfter(BB: Succ, depth: depth - 1))
2435	return false;
2436	}
2437
2438	// If none of the successors leads back in a loop, we're on an exit/abort.
2439	return true;
2440	}
2441
2442	static bool localAllocaNeedsStackSave(CoroAllocaAllocInst *AI) {
2443	// Look for a free that isn't sufficiently obviously followed by
2444	// either a suspend or a termination, i.e. something that will leave
2445	// the coro resumption frame.
2446	for (auto *U : AI->users()) {
2447	auto FI = dyn_cast<CoroAllocaFreeInst>(Val: U);
2448	if (!FI) continue;
2449
2450	if (!willLeaveFunctionImmediatelyAfter(BB: FI->getParent()))
2451	return true;
2452	}
2453
2454	// If we never found one, we don't need a stack save.
2455	return false;
2456	}
2457
2458	/// Turn each of the given local allocas into a normal (dynamic) alloca
2459	/// instruction.
2460	static void lowerLocalAllocas(ArrayRef<CoroAllocaAllocInst*> LocalAllocas,
2461	SmallVectorImpl<Instruction*> &DeadInsts) {
2462	for (auto *AI : LocalAllocas) {
2463	IRBuilder<> Builder(AI);
2464
2465	// Save the stack depth. Try to avoid doing this if the stackrestore
2466	// is going to immediately precede a return or something.
2467	Value *StackSave = nullptr;
2468	if (localAllocaNeedsStackSave(AI))
2469	StackSave = Builder.CreateStackSave();
2470
2471	// Allocate memory.
2472	auto Alloca = Builder.CreateAlloca(Ty: Builder.getInt8Ty(), ArraySize: AI->getSize());
2473	Alloca->setAlignment(AI->getAlignment());
2474
2475	for (auto *U : AI->users()) {
2476	// Replace gets with the allocation.
2477	if (isa<CoroAllocaGetInst>(Val: U)) {
2478	U->replaceAllUsesWith(V: Alloca);
2479
2480	// Replace frees with stackrestores. This is safe because
2481	// alloca.alloc is required to obey a stack discipline, although we
2482	// don't enforce that structurally.
2483	} else {
2484	auto FI = cast<CoroAllocaFreeInst>(Val: U);
2485	if (StackSave) {
2486	Builder.SetInsertPoint(FI);
2487	Builder.CreateStackRestore(Ptr: StackSave);
2488	}
2489	}
2490	DeadInsts.push_back(Elt: cast<Instruction>(Val: U));
2491	}
2492
2493	DeadInsts.push_back(Elt: AI);
2494	}
2495	}
2496
2497	/// Turn the given coro.alloca.alloc call into a dynamic allocation.
2498	/// This happens during the all-instructions iteration, so it must not
2499	/// delete the call.
2500	static Instruction *lowerNonLocalAlloca(CoroAllocaAllocInst *AI,
2501	coro::Shape &Shape,
2502	SmallVectorImpl<Instruction*> &DeadInsts) {
2503	IRBuilder<> Builder(AI);
2504	auto Alloc = Shape.emitAlloc(Builder, Size: AI->getSize(), CG: nullptr);
2505
2506	for (User *U : AI->users()) {
2507	if (isa<CoroAllocaGetInst>(Val: U)) {
2508	U->replaceAllUsesWith(V: Alloc);
2509	} else {
2510	auto FI = cast<CoroAllocaFreeInst>(Val: U);
2511	Builder.SetInsertPoint(FI);
2512	Shape.emitDealloc(Builder, Ptr: Alloc, CG: nullptr);
2513	}
2514	DeadInsts.push_back(Elt: cast<Instruction>(Val: U));
2515	}
2516
2517	// Push this on last so that it gets deleted after all the others.
2518	DeadInsts.push_back(Elt: AI);
2519
2520	// Return the new allocation value so that we can check for needed spills.
2521	return cast<Instruction>(Val: Alloc);
2522	}
2523
2524	/// Get the current swifterror value.
2525	static Value *emitGetSwiftErrorValue(IRBuilder<> &Builder, Type *ValueTy,
2526	coro::Shape &Shape) {
2527	// Make a fake function pointer as a sort of intrinsic.
2528	auto FnTy = FunctionType::get(Result: ValueTy, Params: {}, isVarArg: false);
2529	auto Fn = ConstantPointerNull::get(T: Builder.getPtrTy());
2530
2531	auto Call = Builder.CreateCall(FTy: FnTy, Callee: Fn, Args: {});
2532	Shape.SwiftErrorOps.push_back(Elt: Call);
2533
2534	return Call;
2535	}
2536
2537	/// Set the given value as the current swifterror value.
2538	///
2539	/// Returns a slot that can be used as a swifterror slot.
2540	static Value *emitSetSwiftErrorValue(IRBuilder<> &Builder, Value *V,
2541	coro::Shape &Shape) {
2542	// Make a fake function pointer as a sort of intrinsic.
2543	auto FnTy = FunctionType::get(Result: Builder.getPtrTy(),
2544	Params: {V->getType()}, isVarArg: false);
2545	auto Fn = ConstantPointerNull::get(T: Builder.getPtrTy());
2546
2547	auto Call = Builder.CreateCall(FTy: FnTy, Callee: Fn, Args: { V });
2548	Shape.SwiftErrorOps.push_back(Elt: Call);
2549
2550	return Call;
2551	}
2552
2553	/// Set the swifterror value from the given alloca before a call,
2554	/// then put in back in the alloca afterwards.
2555	///
2556	/// Returns an address that will stand in for the swifterror slot
2557	/// until splitting.
2558	static Value *emitSetAndGetSwiftErrorValueAround(Instruction *Call,
2559	AllocaInst *Alloca,
2560	coro::Shape &Shape) {
2561	auto ValueTy = Alloca->getAllocatedType();
2562	IRBuilder<> Builder(Call);
2563
2564	// Load the current value from the alloca and set it as the
2565	// swifterror value.
2566	auto ValueBeforeCall = Builder.CreateLoad(Ty: ValueTy, Ptr: Alloca);
2567	auto Addr = emitSetSwiftErrorValue(Builder, V: ValueBeforeCall, Shape);
2568
2569	// Move to after the call. Since swifterror only has a guaranteed
2570	// value on normal exits, we can ignore implicit and explicit unwind
2571	// edges.
2572	if (isa<CallInst>(Val: Call)) {
2573	Builder.SetInsertPoint(Call->getNextNode());
2574	} else {
2575	auto Invoke = cast<InvokeInst>(Val: Call);
2576	Builder.SetInsertPoint(Invoke->getNormalDest()->getFirstNonPHIOrDbg());
2577	}
2578
2579	// Get the current swifterror value and store it to the alloca.
2580	auto ValueAfterCall = emitGetSwiftErrorValue(Builder, ValueTy, Shape);
2581	Builder.CreateStore(Val: ValueAfterCall, Ptr: Alloca);
2582
2583	return Addr;
2584	}
2585
2586	/// Eliminate a formerly-swifterror alloca by inserting the get/set
2587	/// intrinsics and attempting to MemToReg the alloca away.
2588	static void eliminateSwiftErrorAlloca(Function &F, AllocaInst *Alloca,
2589	coro::Shape &Shape) {
2590	for (Use &Use : llvm::make_early_inc_range(Range: Alloca->uses())) {
2591	// swifterror values can only be used in very specific ways.
2592	// We take advantage of that here.
2593	auto User = Use.getUser();
2594	if (isa<LoadInst>(Val: User) || isa<StoreInst>(Val: User))
2595	continue;
2596
2597	assert(isa<CallInst>(User) || isa<InvokeInst>(User));
2598	auto Call = cast<Instruction>(Val: User);
2599
2600	auto Addr = emitSetAndGetSwiftErrorValueAround(Call, Alloca, Shape);
2601
2602	// Use the returned slot address as the call argument.
2603	Use.set(Addr);
2604	}
2605
2606	// All the uses should be loads and stores now.
2607	assert(isAllocaPromotable(Alloca));
2608	}
2609
2610	/// "Eliminate" a swifterror argument by reducing it to the alloca case
2611	/// and then loading and storing in the prologue and epilog.
2612	///
2613	/// The argument keeps the swifterror flag.
2614	static void eliminateSwiftErrorArgument(Function &F, Argument &Arg,
2615	coro::Shape &Shape,
2616	SmallVectorImpl<AllocaInst*> &AllocasToPromote) {
2617	IRBuilder<> Builder(F.getEntryBlock().getFirstNonPHIOrDbg());
2618
2619	auto ArgTy = cast<PointerType>(Val: Arg.getType());
2620	auto ValueTy = PointerType::getUnqual(C&: F.getContext());
2621
2622	// Reduce to the alloca case:
2623
2624	// Create an alloca and replace all uses of the arg with it.
2625	auto Alloca = Builder.CreateAlloca(Ty: ValueTy, AddrSpace: ArgTy->getAddressSpace());
2626	Arg.replaceAllUsesWith(V: Alloca);
2627
2628	// Set an initial value in the alloca. swifterror is always null on entry.
2629	auto InitialValue = Constant::getNullValue(Ty: ValueTy);
2630	Builder.CreateStore(Val: InitialValue, Ptr: Alloca);
2631
2632	// Find all the suspends in the function and save and restore around them.
2633	for (auto *Suspend : Shape.CoroSuspends) {
2634	(void) emitSetAndGetSwiftErrorValueAround(Call: Suspend, Alloca, Shape);
2635	}
2636
2637	// Find all the coro.ends in the function and restore the error value.
2638	for (auto *End : Shape.CoroEnds) {
2639	Builder.SetInsertPoint(End);
2640	auto FinalValue = Builder.CreateLoad(Ty: ValueTy, Ptr: Alloca);
2641	(void) emitSetSwiftErrorValue(Builder, V: FinalValue, Shape);
2642	}
2643
2644	// Now we can use the alloca logic.
2645	AllocasToPromote.push_back(Elt: Alloca);
2646	eliminateSwiftErrorAlloca(F, Alloca, Shape);
2647	}
2648
2649	/// Eliminate all problematic uses of swifterror arguments and allocas
2650	/// from the function. We'll fix them up later when splitting the function.
2651	static void eliminateSwiftError(Function &F, coro::Shape &Shape) {
2652	SmallVector<AllocaInst*, 4> AllocasToPromote;
2653
2654	// Look for a swifterror argument.
2655	for (auto &Arg : F.args()) {
2656	if (!Arg.hasSwiftErrorAttr()) continue;
2657
2658	eliminateSwiftErrorArgument(F, Arg, Shape, AllocasToPromote);
2659	break;
2660	}
2661
2662	// Look for swifterror allocas.
2663	for (auto &Inst : F.getEntryBlock()) {
2664	auto Alloca = dyn_cast<AllocaInst>(Val: &Inst);
2665	if (!Alloca || !Alloca->isSwiftError()) continue;
2666
2667	// Clear the swifterror flag.
2668	Alloca->setSwiftError(false);
2669
2670	AllocasToPromote.push_back(Elt: Alloca);
2671	eliminateSwiftErrorAlloca(F, Alloca, Shape);
2672	}
2673
2674	// If we have any allocas to promote, compute a dominator tree and
2675	// promote them en masse.
2676	if (!AllocasToPromote.empty()) {
2677	DominatorTree DT(F);
2678	PromoteMemToReg(Allocas: AllocasToPromote, DT);
2679	}
2680	}
2681
2682	/// retcon and retcon.once conventions assume that all spill uses can be sunk
2683	/// after the coro.begin intrinsic.
2684	static void sinkSpillUsesAfterCoroBegin(Function &F,
2685	const FrameDataInfo &FrameData,
2686	CoroBeginInst *CoroBegin) {
2687	DominatorTree Dom(F);
2688
2689	SmallSetVector<Instruction *, 32> ToMove;
2690	SmallVector<Instruction *, 32> Worklist;
2691
2692	// Collect all users that precede coro.begin.
2693	for (auto *Def : FrameData.getAllDefs()) {
2694	for (User *U : Def->users()) {
2695	auto Inst = cast<Instruction>(Val: U);
2696	if (Inst->getParent() != CoroBegin->getParent() ||
2697	Dom.dominates(Def: CoroBegin, User: Inst))
2698	continue;
2699	if (ToMove.insert(X: Inst))
2700	Worklist.push_back(Elt: Inst);
2701	}
2702	}
2703	// Recursively collect users before coro.begin.
2704	while (!Worklist.empty()) {
2705	auto *Def = Worklist.pop_back_val();
2706	for (User *U : Def->users()) {
2707	auto Inst = cast<Instruction>(Val: U);
2708	if (Dom.dominates(Def: CoroBegin, User: Inst))
2709	continue;
2710	if (ToMove.insert(X: Inst))
2711	Worklist.push_back(Elt: Inst);
2712	}
2713	}
2714
2715	// Sort by dominance.
2716	SmallVector<Instruction *, 64> InsertionList(ToMove.begin(), ToMove.end());
2717	llvm::sort(C&: InsertionList, Comp: [&Dom](Instruction *A, Instruction *B) -> bool {
2718	// If a dominates b it should preceed (<) b.
2719	return Dom.dominates(Def: A, User: B);
2720	});
2721
2722	Instruction *InsertPt = CoroBegin->getNextNode();
2723	for (Instruction *Inst : InsertionList)
2724	Inst->moveBefore(MovePos: InsertPt);
2725	}
2726
2727	/// For each local variable that all of its user are only used inside one of
2728	/// suspended region, we sink their lifetime.start markers to the place where
2729	/// after the suspend block. Doing so minimizes the lifetime of each variable,
2730	/// hence minimizing the amount of data we end up putting on the frame.
2731	static void sinkLifetimeStartMarkers(Function &F, coro::Shape &Shape,
2732	SuspendCrossingInfo &Checker) {
2733	if (F.hasOptNone())
2734	return;
2735
2736	DominatorTree DT(F);
2737
2738	// Collect all possible basic blocks which may dominate all uses of allocas.
2739	SmallPtrSet<BasicBlock *, 4> DomSet;
2740	DomSet.insert(Ptr: &F.getEntryBlock());
2741	for (auto *CSI : Shape.CoroSuspends) {
2742	BasicBlock *SuspendBlock = CSI->getParent();
2743	assert(isSuspendBlock(SuspendBlock) && SuspendBlock->getSingleSuccessor() &&
2744	"should have split coro.suspend into its own block");
2745	DomSet.insert(Ptr: SuspendBlock->getSingleSuccessor());
2746	}
2747
2748	for (Instruction &I : instructions(F)) {
2749	AllocaInst* AI = dyn_cast<AllocaInst>(Val: &I);
2750	if (!AI)
2751	continue;
2752
2753	for (BasicBlock *DomBB : DomSet) {
2754	bool Valid = true;
2755	SmallVector<Instruction *, 1> Lifetimes;
2756
2757	auto isLifetimeStart = [](Instruction* I) {
2758	if (auto* II = dyn_cast<IntrinsicInst>(I))
2759	return II->getIntrinsicID() == Intrinsic::lifetime_start;
2760	return false;
2761	};
2762
2763	auto collectLifetimeStart = [&](Instruction *U, AllocaInst *AI) {
2764	if (isLifetimeStart(U)) {
2765	Lifetimes.push_back(Elt: U);
2766	return true;
2767	}
2768	if (!U->hasOneUse() || U->stripPointerCasts() != AI)
2769	return false;
2770	if (isLifetimeStart(U->user_back())) {
2771	Lifetimes.push_back(Elt: U->user_back());
2772	return true;
2773	}
2774	return false;
2775	};
2776
2777	for (User *U : AI->users()) {
2778	Instruction *UI = cast<Instruction>(Val: U);
2779	// For all users except lifetime.start markers, if they are all
2780	// dominated by one of the basic blocks and do not cross
2781	// suspend points as well, then there is no need to spill the
2782	// instruction.
2783	if (!DT.dominates(A: DomBB, B: UI->getParent()) ||
2784	Checker.isDefinitionAcrossSuspend(DefBB: DomBB, U: UI)) {
2785	// Skip lifetime.start, GEP and bitcast used by lifetime.start
2786	// markers.
2787	if (collectLifetimeStart(UI, AI))
2788	continue;
2789	Valid = false;
2790	break;
2791	}
2792	}
2793	// Sink lifetime.start markers to dominate block when they are
2794	// only used outside the region.
2795	if (Valid && Lifetimes.size() != 0) {
2796	auto *NewLifetime = Lifetimes[0]->clone();
2797	NewLifetime->replaceUsesOfWith(From: NewLifetime->getOperand(i: 1), To: AI);
2798	NewLifetime->insertBefore(InsertPos: DomBB->getTerminator());
2799
2800	// All the outsided lifetime.start markers are no longer necessary.
2801	for (Instruction *S : Lifetimes)
2802	S->eraseFromParent();
2803
2804	break;
2805	}
2806	}
2807	}
2808	}
2809
2810	static void collectFrameAlloca(AllocaInst *AI, coro::Shape &Shape,
2811	const SuspendCrossingInfo &Checker,
2812	SmallVectorImpl<AllocaInfo> &Allocas,
2813	const DominatorTree &DT) {
2814	if (Shape.CoroSuspends.empty())
2815	return;
2816
2817	// The PromiseAlloca will be specially handled since it needs to be in a
2818	// fixed position in the frame.
2819	if (AI == Shape.SwitchLowering.PromiseAlloca)
2820	return;
2821
2822	// The __coro_gro alloca should outlive the promise, make sure we
2823	// keep it outside the frame.
2824	if (AI->hasMetadata(KindID: LLVMContext::MD_coro_outside_frame))
2825	return;
2826
2827	// The code that uses lifetime.start intrinsic does not work for functions
2828	// with loops without exit. Disable it on ABIs we know to generate such
2829	// code.
2830	bool ShouldUseLifetimeStartInfo =
2831	(Shape.ABI != coro::ABI::Async && Shape.ABI != coro::ABI::Retcon &&
2832	Shape.ABI != coro::ABI::RetconOnce);
2833	AllocaUseVisitor Visitor{AI->getModule()->getDataLayout(), DT,
2834	*Shape.CoroBegin, Checker,
2835	ShouldUseLifetimeStartInfo};
2836	Visitor.visitPtr(I&: *AI);
2837	if (!Visitor.getShouldLiveOnFrame())
2838	return;
2839	Allocas.emplace_back(Args&: AI, Args: Visitor.getAliasesCopy(),
2840	Args: Visitor.getMayWriteBeforeCoroBegin());
2841	}
2842
2843	static std::optional<std::pair<Value &, DIExpression &>>
2844	salvageDebugInfoImpl(SmallDenseMap<Argument *, AllocaInst *, 4> &ArgToAllocaMap,
2845	bool OptimizeFrame, bool UseEntryValue, Function *F,
2846	Value *Storage, DIExpression *Expr,
2847	bool SkipOutermostLoad) {
2848	IRBuilder<> Builder(F->getContext());
2849	auto InsertPt = F->getEntryBlock().getFirstInsertionPt();
2850	while (isa<IntrinsicInst>(Val: InsertPt))
2851	++InsertPt;
2852	Builder.SetInsertPoint(TheBB: &F->getEntryBlock(), IP: InsertPt);
2853
2854	while (auto *Inst = dyn_cast_or_null<Instruction>(Val: Storage)) {
2855	if (auto *LdInst = dyn_cast<LoadInst>(Val: Inst)) {
2856	Storage = LdInst->getPointerOperand();
2857	// FIXME: This is a heuristic that works around the fact that
2858	// LLVM IR debug intrinsics cannot yet distinguish between
2859	// memory and value locations: Because a dbg.declare(alloca) is
2860	// implicitly a memory location no DW_OP_deref operation for the
2861	// last direct load from an alloca is necessary. This condition
2862	// effectively drops the *last* DW_OP_deref in the expression.
2863	if (!SkipOutermostLoad)
2864	Expr = DIExpression::prepend(Expr, Flags: DIExpression::DerefBefore);
2865	} else if (auto *StInst = dyn_cast<StoreInst>(Val: Inst)) {
2866	Storage = StInst->getValueOperand();
2867	} else {
2868	SmallVector<uint64_t, 16> Ops;
2869	SmallVector<Value *, 0> AdditionalValues;
2870	Value *Op = llvm::salvageDebugInfoImpl(
2871	I&: *Inst, CurrentLocOps: Expr ? Expr->getNumLocationOperands() : 0, Ops,
2872	AdditionalValues);
2873	if (!Op || !AdditionalValues.empty()) {
2874	// If salvaging failed or salvaging produced more than one location
2875	// operand, give up.
2876	break;
2877	}
2878	Storage = Op;
2879	Expr = DIExpression::appendOpsToArg(Expr, Ops, ArgNo: 0, /*StackValue*/ false);
2880	}
2881	SkipOutermostLoad = false;
2882	}
2883	if (!Storage)
2884	return std::nullopt;
2885
2886	auto *StorageAsArg = dyn_cast<Argument>(Val: Storage);
2887	const bool IsSwiftAsyncArg =
2888	StorageAsArg && StorageAsArg->hasAttribute(Attribute::Kind: SwiftAsync);
2889
2890	// Swift async arguments are described by an entry value of the ABI-defined
2891	// register containing the coroutine context.
2892	// Entry values in variadic expressions are not supported.
2893	if (IsSwiftAsyncArg && UseEntryValue && !Expr->isEntryValue() &&
2894	Expr->isSingleLocationExpression())
2895	Expr = DIExpression::prepend(Expr, Flags: DIExpression::EntryValue);
2896
2897	// If the coroutine frame is an Argument, store it in an alloca to improve
2898	// its availability (e.g. registers may be clobbered).
2899	// Avoid this if optimizations are enabled (they would remove the alloca) or
2900	// if the value is guaranteed to be available through other means (e.g. swift
2901	// ABI guarantees).
2902	if (StorageAsArg && !OptimizeFrame && !IsSwiftAsyncArg) {
2903	auto &Cached = ArgToAllocaMap[StorageAsArg];
2904	if (!Cached) {
2905	Cached = Builder.CreateAlloca(Ty: Storage->getType(), AddrSpace: 0, ArraySize: nullptr,
2906	Name: Storage->getName() + ".debug");
2907	Builder.CreateStore(Val: Storage, Ptr: Cached);
2908	}
2909	Storage = Cached;
2910	// FIXME: LLVM lacks nuanced semantics to differentiate between
2911	// memory and direct locations at the IR level. The backend will
2912	// turn a dbg.declare(alloca, ..., DIExpression()) into a memory
2913	// location. Thus, if there are deref and offset operations in the
2914	// expression, we need to add a DW_OP_deref at the *start* of the
2915	// expression to first load the contents of the alloca before
2916	// adjusting it with the expression.
2917	Expr = DIExpression::prepend(Expr, Flags: DIExpression::DerefBefore);
2918	}
2919
2920	return {{*Storage, *Expr}};
2921	}
2922
2923	void coro::salvageDebugInfo(
2924	SmallDenseMap<Argument *, AllocaInst *, 4> &ArgToAllocaMap,
2925	DbgVariableIntrinsic &DVI, bool OptimizeFrame, bool UseEntryValue) {
2926
2927	Function *F = DVI.getFunction();
2928	// Follow the pointer arithmetic all the way to the incoming
2929	// function argument and convert into a DIExpression.
2930	bool SkipOutermostLoad = !isa<DbgValueInst>(Val: DVI);
2931	Value *OriginalStorage = DVI.getVariableLocationOp(OpIdx: 0);
2932
2933	auto SalvagedInfo = ::salvageDebugInfoImpl(
2934	ArgToAllocaMap, OptimizeFrame, UseEntryValue, F, Storage: OriginalStorage,
2935	Expr: DVI.getExpression(), SkipOutermostLoad);
2936	if (!SalvagedInfo)
2937	return;
2938
2939	Value *Storage = &SalvagedInfo->first;
2940	DIExpression *Expr = &SalvagedInfo->second;
2941
2942	DVI.replaceVariableLocationOp(OldValue: OriginalStorage, NewValue: Storage);
2943	DVI.setExpression(Expr);
2944	// We only hoist dbg.declare today since it doesn't make sense to hoist
2945	// dbg.value since it does not have the same function wide guarantees that
2946	// dbg.declare does.
2947	if (isa<DbgDeclareInst>(Val: DVI)) {
2948	std::optional<BasicBlock::iterator> InsertPt;
2949	if (auto *I = dyn_cast<Instruction>(Val: Storage)) {
2950	InsertPt = I->getInsertionPointAfterDef();
2951	// Update DILocation only in O0 since it is easy to get out of sync in
2952	// optimizations. See https://github.com/llvm/llvm-project/pull/75104 for
2953	// an example.
2954	if (!OptimizeFrame && I->getDebugLoc())
2955	DVI.setDebugLoc(I->getDebugLoc());
2956	} else if (isa<Argument>(Val: Storage))
2957	InsertPt = F->getEntryBlock().begin();
2958	if (InsertPt)
2959	DVI.moveBefore(BB&: *(*InsertPt)->getParent(), I: *InsertPt);
2960	}
2961	}
2962
2963	void coro::salvageDebugInfo(
2964	SmallDenseMap<Argument *, AllocaInst *, 4> &ArgToAllocaMap,
2965	DbgVariableRecord &DVR, bool OptimizeFrame, bool UseEntryValue) {
2966
2967	Function *F = DVR.getFunction();
2968	// Follow the pointer arithmetic all the way to the incoming
2969	// function argument and convert into a DIExpression.
2970	bool SkipOutermostLoad = DVR.isDbgDeclare();
2971	Value *OriginalStorage = DVR.getVariableLocationOp(OpIdx: 0);
2972
2973	auto SalvagedInfo = ::salvageDebugInfoImpl(
2974	ArgToAllocaMap, OptimizeFrame, UseEntryValue, F, Storage: OriginalStorage,
2975	Expr: DVR.getExpression(), SkipOutermostLoad);
2976	if (!SalvagedInfo)
2977	return;
2978
2979	Value *Storage = &SalvagedInfo->first;
2980	DIExpression *Expr = &SalvagedInfo->second;
2981
2982	DVR.replaceVariableLocationOp(OldValue: OriginalStorage, NewValue: Storage);
2983	DVR.setExpression(Expr);
2984	// We only hoist dbg.declare today since it doesn't make sense to hoist
2985	// dbg.value since it does not have the same function wide guarantees that
2986	// dbg.declare does.
2987	if (DVR.getType() == DbgVariableRecord::LocationType::Declare) {
2988	std::optional<BasicBlock::iterator> InsertPt;
2989	if (auto *I = dyn_cast<Instruction>(Val: Storage)) {
2990	InsertPt = I->getInsertionPointAfterDef();
2991	// Update DILocation only in O0 since it is easy to get out of sync in
2992	// optimizations. See https://github.com/llvm/llvm-project/pull/75104 for
2993	// an example.
2994	if (!OptimizeFrame && I->getDebugLoc())
2995	DVR.setDebugLoc(I->getDebugLoc());
2996	} else if (isa<Argument>(Val: Storage))
2997	InsertPt = F->getEntryBlock().begin();
2998	if (InsertPt) {
2999	DVR.removeFromParent();
3000	(*InsertPt)->getParent()->insertDbgRecordBefore(DR: &DVR, Here: *InsertPt);
3001	}
3002	}
3003	}
3004
3005	static void doRematerializations(
3006	Function &F, SuspendCrossingInfo &Checker,
3007	const std::function<bool(Instruction &)> &MaterializableCallback) {
3008	if (F.hasOptNone())
3009	return;
3010
3011	SpillInfo Spills;
3012
3013	// See if there are materializable instructions across suspend points
3014	// We record these as the starting point to also identify materializable
3015	// defs of uses in these operations
3016	for (Instruction &I : instructions(F)) {
3017	if (!MaterializableCallback(I))
3018	continue;
3019	for (User *U : I.users())
3020	if (Checker.isDefinitionAcrossSuspend(I, U))
3021	Spills[&I].push_back(Elt: cast<Instruction>(Val: U));
3022	}
3023
3024	// Process each of the identified rematerializable instructions
3025	// and add predecessor instructions that can also be rematerialized.
3026	// This is actually a graph of instructions since we could potentially
3027	// have multiple uses of a def in the set of predecessor instructions.
3028	// The approach here is to maintain a graph of instructions for each bottom
3029	// level instruction - where we have a unique set of instructions (nodes)
3030	// and edges between them. We then walk the graph in reverse post-dominator
3031	// order to insert them past the suspend point, but ensure that ordering is
3032	// correct. We also rely on CSE removing duplicate defs for remats of
3033	// different instructions with a def in common (rather than maintaining more
3034	// complex graphs for each suspend point)
3035
3036	// We can do this by adding new nodes to the list for each suspend
3037	// point. Then using standard GraphTraits to give a reverse post-order
3038	// traversal when we insert the nodes after the suspend
3039	SmallMapVector<Instruction *, std::unique_ptr<RematGraph>, 8> AllRemats;
3040	for (auto &E : Spills) {
3041	for (Instruction *U : E.second) {
3042	// Don't process a user twice (this can happen if the instruction uses
3043	// more than one rematerializable def)
3044	if (AllRemats.count(Key: U))
3045	continue;
3046
3047	// Constructor creates the whole RematGraph for the given Use
3048	auto RematUPtr =
3049	std::make_unique<RematGraph>(args: MaterializableCallback, args&: U, args&: Checker);
3050
3051	LLVM_DEBUG(dbgs() << "***** Next remat group *****\n";
3052	ReversePostOrderTraversal<RematGraph *> RPOT(RematUPtr.get());
3053	for (auto I = RPOT.begin(); I != RPOT.end();
3054	++I) { (*I)->Node->dump(); } dbgs()
3055	<< "\n";);
3056
3057	AllRemats[U] = std::move(RematUPtr);
3058	}
3059	}
3060
3061	// Rewrite materializable instructions to be materialized at the use
3062	// point.
3063	LLVM_DEBUG(dumpRemats("Materializations", AllRemats));
3064	rewriteMaterializableInstructions(AllRemats);
3065	}
3066
3067	void coro::buildCoroutineFrame(
3068	Function &F, Shape &Shape, TargetTransformInfo &TTI,
3069	const std::function<bool(Instruction &)> &MaterializableCallback) {
3070	// Don't eliminate swifterror in async functions that won't be split.
3071	if (Shape.ABI != coro::ABI::Async || !Shape.CoroSuspends.empty())
3072	eliminateSwiftError(F, Shape);
3073
3074	if (Shape.ABI == coro::ABI::Switch &&
3075	Shape.SwitchLowering.PromiseAlloca) {
3076	Shape.getSwitchCoroId()->clearPromise();
3077	}
3078
3079	// Make sure that all coro.save, coro.suspend and the fallthrough coro.end
3080	// intrinsics are in their own blocks to simplify the logic of building up
3081	// SuspendCrossing data.
3082	for (auto *CSI : Shape.CoroSuspends) {
3083	if (auto *Save = CSI->getCoroSave())
3084	splitAround(I: Save, Name: "CoroSave");
3085	splitAround(I: CSI, Name: "CoroSuspend");
3086	}
3087
3088	// Put CoroEnds into their own blocks.
3089	for (AnyCoroEndInst *CE : Shape.CoroEnds) {
3090	splitAround(I: CE, Name: "CoroEnd");
3091
3092	// Emit the musttail call function in a new block before the CoroEnd.
3093	// We do this here so that the right suspend crossing info is computed for
3094	// the uses of the musttail call function call. (Arguments to the coro.end
3095	// instructions would be ignored)
3096	if (auto *AsyncEnd = dyn_cast<CoroAsyncEndInst>(Val: CE)) {
3097	auto *MustTailCallFn = AsyncEnd->getMustTailCallFunction();
3098	if (!MustTailCallFn)
3099	continue;
3100	IRBuilder<> Builder(AsyncEnd);
3101	SmallVector<Value *, 8> Args(AsyncEnd->args());
3102	auto Arguments = ArrayRef<Value *>(Args).drop_front(N: 3);
3103	auto *Call = createMustTailCall(Loc: AsyncEnd->getDebugLoc(), MustTailCallFn,
3104	TTI, Arguments, Builder);
3105	splitAround(I: Call, Name: "MustTailCall.Before.CoroEnd");
3106	}
3107	}
3108
3109	// Later code makes structural assumptions about single predecessors phis e.g
3110	// that they are not live across a suspend point.
3111	cleanupSinglePredPHIs(F);
3112
3113	// Transforms multi-edge PHI Nodes, so that any value feeding into a PHI will
3114	// never has its definition separated from the PHI by the suspend point.
3115	rewritePHIs(F);
3116
3117	// Build suspend crossing info.
3118	SuspendCrossingInfo Checker(F, Shape);
3119
3120	doRematerializations(F, Checker, MaterializableCallback);
3121
3122	FrameDataInfo FrameData;
3123	SmallVector<CoroAllocaAllocInst*, 4> LocalAllocas;
3124	SmallVector<Instruction*, 4> DeadInstructions;
3125	if (Shape.ABI != coro::ABI::Async && Shape.ABI != coro::ABI::Retcon &&
3126	Shape.ABI != coro::ABI::RetconOnce)
3127	sinkLifetimeStartMarkers(F, Shape, Checker);
3128
3129	// Collect the spills for arguments and other not-materializable values.
3130	for (Argument &A : F.args())
3131	for (User *U : A.users())
3132	if (Checker.isDefinitionAcrossSuspend(A, U))
3133	FrameData.Spills[&A].push_back(Elt: cast<Instruction>(Val: U));
3134
3135	const DominatorTree DT(F);
3136	for (Instruction &I : instructions(F)) {
3137	// Values returned from coroutine structure intrinsics should not be part
3138	// of the Coroutine Frame.
3139	if (isCoroutineStructureIntrinsic(I) || &I == Shape.CoroBegin)
3140	continue;
3141
3142	// Handle alloca.alloc specially here.
3143	if (auto AI = dyn_cast<CoroAllocaAllocInst>(Val: &I)) {
3144	// Check whether the alloca's lifetime is bounded by suspend points.
3145	if (isLocalAlloca(AI)) {
3146	LocalAllocas.push_back(Elt: AI);
3147	continue;
3148	}
3149
3150	// If not, do a quick rewrite of the alloca and then add spills of
3151	// the rewritten value. The rewrite doesn't invalidate anything in
3152	// Spills because the other alloca intrinsics have no other operands
3153	// besides AI, and it doesn't invalidate the iteration because we delay
3154	// erasing AI.
3155	auto Alloc = lowerNonLocalAlloca(AI, Shape, DeadInsts&: DeadInstructions);
3156
3157	for (User *U : Alloc->users()) {
3158	if (Checker.isDefinitionAcrossSuspend(I&: *Alloc, U))
3159	FrameData.Spills[Alloc].push_back(Elt: cast<Instruction>(Val: U));
3160	}
3161	continue;
3162	}
3163
3164	// Ignore alloca.get; we process this as part of coro.alloca.alloc.
3165	if (isa<CoroAllocaGetInst>(Val: I))
3166	continue;
3167
3168	if (auto *AI = dyn_cast<AllocaInst>(Val: &I)) {
3169	collectFrameAlloca(AI, Shape, Checker, Allocas&: FrameData.Allocas, DT);
3170	continue;
3171	}
3172
3173	for (User *U : I.users())
3174	if (Checker.isDefinitionAcrossSuspend(I, U)) {
3175	// We cannot spill a token.
3176	if (I.getType()->isTokenTy())
3177	report_fatal_error(
3178	reason: "token definition is separated from the use by a suspend point");
3179	FrameData.Spills[&I].push_back(Elt: cast<Instruction>(Val: U));
3180	}
3181	}
3182
3183	LLVM_DEBUG(dumpAllocas(FrameData.Allocas));
3184
3185	// We don't want the layout of coroutine frame to be affected
3186	// by debug information. So we only choose to salvage DbgValueInst for
3187	// whose value is already in the frame.
3188	// We would handle the dbg.values for allocas specially
3189	for (auto &Iter : FrameData.Spills) {
3190	auto *V = Iter.first;
3191	SmallVector<DbgValueInst *, 16> DVIs;
3192	SmallVector<DbgVariableRecord *, 16> DVRs;
3193	findDbgValues(DbgValues&: DVIs, V, DbgVariableRecords: &DVRs);
3194	for (DbgValueInst *DVI : DVIs)
3195	if (Checker.isDefinitionAcrossSuspend(V&: *V, U: DVI))
3196	FrameData.Spills[V].push_back(Elt: DVI);
3197	// Add the instructions which carry debug info that is in the frame.
3198	for (DbgVariableRecord *DVR : DVRs)
3199	if (Checker.isDefinitionAcrossSuspend(V&: *V, U: DVR->Marker->MarkedInstr))
3200	FrameData.Spills[V].push_back(Elt: DVR->Marker->MarkedInstr);
3201	}
3202
3203	LLVM_DEBUG(dumpSpills("Spills", FrameData.Spills));
3204	if (Shape.ABI == coro::ABI::Retcon || Shape.ABI == coro::ABI::RetconOnce ||
3205	Shape.ABI == coro::ABI::Async)
3206	sinkSpillUsesAfterCoroBegin(F, FrameData, CoroBegin: Shape.CoroBegin);
3207	Shape.FrameTy = buildFrameType(F, Shape, FrameData);
3208	Shape.FramePtr = Shape.CoroBegin;
3209	// For now, this works for C++ programs only.
3210	buildFrameDebugInfo(F, Shape, FrameData);
3211	insertSpills(FrameData, Shape);
3212	lowerLocalAllocas(LocalAllocas, DeadInsts&: DeadInstructions);
3213
3214	for (auto *I : DeadInstructions)
3215	I->eraseFromParent();
3216	}
3217