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// its definition precedes and its uses follow a suspend block. This is
10// referred to as a suspend crossing value.
11//
12// Using the information discovered we form a Coroutine Frame structure to
13// contain those values. All uses of those values are replaced with appropriate
14// GEP + load from the coroutine frame. At the point of the definition we spill
15// the value into the coroutine frame.
16//===----------------------------------------------------------------------===//
17
18#include "CoroInternal.h"
19#include "llvm/ADT/ScopeExit.h"
20#include "llvm/ADT/SmallString.h"
21#include "llvm/Analysis/StackLifetime.h"
22#include "llvm/IR/DIBuilder.h"
23#include "llvm/IR/DebugInfo.h"
24#include "llvm/IR/Dominators.h"
25#include "llvm/IR/IRBuilder.h"
26#include "llvm/IR/InstIterator.h"
27#include "llvm/IR/IntrinsicInst.h"
28#include "llvm/IR/LLVMContext.h"
29#include "llvm/IR/MDBuilder.h"
30#include "llvm/IR/Module.h"
31#include "llvm/IR/ProfDataUtils.h"
32#include "llvm/Support/Compiler.h"
33#include "llvm/Support/Debug.h"
34#include "llvm/Support/OptimizedStructLayout.h"
35#include "llvm/Transforms/Coroutines/ABI.h"
36#include "llvm/Transforms/Coroutines/CoroInstr.h"
37#include "llvm/Transforms/Coroutines/MaterializationUtils.h"
38#include "llvm/Transforms/Coroutines/SpillUtils.h"
39#include "llvm/Transforms/Coroutines/SuspendCrossingInfo.h"
40#include "llvm/Transforms/Utils/BasicBlockUtils.h"
41#include "llvm/Transforms/Utils/Local.h"
42#include "llvm/Transforms/Utils/PromoteMemToReg.h"
43#include <algorithm>
44#include <optional>
45
46using namespace llvm;
47
48namespace llvm {
49extern cl::opt<bool> ProfcheckDisableMetadataFixes;
50}
51
52#define DEBUG_TYPE "coro-frame"
53
54namespace {
55class FrameTypeBuilder;
56// Mapping from the to-be-spilled value to all the users that need reload.
57struct FrameDataInfo {
58 // All the values (that are not allocas) that needs to be spilled to the
59 // frame.
60 coro::SpillInfo &Spills;
61 // Allocas contains all values defined as allocas that need to live in the
62 // frame.
63 SmallVectorImpl<coro::AllocaInfo> &Allocas;
64
65 FrameDataInfo(coro::SpillInfo &Spills,
66 SmallVectorImpl<coro::AllocaInfo> &Allocas)
67 : Spills(Spills), Allocas(Allocas) {}
68
69 SmallVector<Value *, 8> getAllDefs() const {
70 SmallVector<Value *, 8> Defs;
71 for (const auto &P : Spills)
72 Defs.push_back(Elt: P.first);
73 for (const auto &A : Allocas)
74 Defs.push_back(Elt: A.Alloca);
75 return Defs;
76 }
77
78 uint32_t getFieldIndex(Value *V) const {
79 auto Itr = FieldIndexMap.find(Val: V);
80 assert(Itr != FieldIndexMap.end() &&
81 "Value does not have a frame field index");
82 return Itr->second;
83 }
84
85 void setFieldIndex(Value *V, uint32_t Index) {
86 assert(FieldIndexMap.count(V) == 0 &&
87 "Cannot set the index for the same field twice.");
88 FieldIndexMap[V] = Index;
89 }
90
91 Align getAlign(Value *V) const {
92 auto Iter = FieldAlignMap.find(Val: V);
93 assert(Iter != FieldAlignMap.end());
94 return Iter->second;
95 }
96
97 void setAlign(Value *V, Align AL) {
98 assert(FieldAlignMap.count(V) == 0);
99 FieldAlignMap.insert(KV: {V, AL});
100 }
101
102 uint64_t getDynamicAlign(Value *V) const {
103 auto Iter = FieldDynamicAlignMap.find(Val: V);
104 assert(Iter != FieldDynamicAlignMap.end());
105 return Iter->second;
106 }
107
108 void setDynamicAlign(Value *V, uint64_t Align) {
109 assert(FieldDynamicAlignMap.count(V) == 0);
110 FieldDynamicAlignMap.insert(KV: {V, Align});
111 }
112
113 uint64_t getOffset(Value *V) const {
114 auto Iter = FieldOffsetMap.find(Val: V);
115 assert(Iter != FieldOffsetMap.end());
116 return Iter->second;
117 }
118
119 void setOffset(Value *V, uint64_t Offset) {
120 assert(FieldOffsetMap.count(V) == 0);
121 FieldOffsetMap.insert(KV: {V, Offset});
122 }
123
124 // Update field offset and alignment information from FrameTypeBuilder.
125 void updateLayoutInfo(FrameTypeBuilder &B);
126
127private:
128 // Map from values to their slot indexes on the frame (insertion order).
129 DenseMap<Value *, uint32_t> FieldIndexMap;
130 // Map from values to their alignment on the frame. They would be set after
131 // the frame is built.
132 DenseMap<Value *, Align> FieldAlignMap;
133 DenseMap<Value *, uint64_t> FieldDynamicAlignMap;
134 // Map from values to their offset on the frame. They would be set after
135 // the frame is built.
136 DenseMap<Value *, uint64_t> FieldOffsetMap;
137};
138} // namespace
139
140#ifndef NDEBUG
141static void dumpSpills(StringRef Title, const coro::SpillInfo &Spills) {
142 dbgs() << "------------- " << Title << " --------------\n";
143 for (const auto &E : Spills) {
144 E.first->dump();
145 dbgs() << " user: ";
146 for (auto *I : E.second)
147 I->dump();
148 }
149}
150
151static void dumpAllocas(const SmallVectorImpl<coro::AllocaInfo> &Allocas) {
152 dbgs() << "------------- Allocas --------------\n";
153 for (const auto &A : Allocas) {
154 A.Alloca->dump();
155 }
156}
157#endif
158
159namespace {
160using FieldIDType = size_t;
161// We cannot rely solely on natural alignment of a type when building a
162// coroutine frame and if the alignment specified on the Alloca instruction
163// differs from the natural alignment of the alloca type we will need to insert
164// padding.
165class FrameTypeBuilder {
166private:
167 struct Field {
168 uint64_t Size;
169 uint64_t Offset;
170 Align Alignment;
171 uint64_t DynamicAlignBuffer;
172 };
173
174 const DataLayout &DL;
175 uint64_t StructSize = 0;
176 Align StructAlign;
177 bool IsFinished = false;
178
179 std::optional<Align> MaxFrameAlignment;
180
181 SmallVector<Field, 8> Fields;
182
183public:
184 FrameTypeBuilder(const DataLayout &DL, std::optional<Align> MaxFrameAlignment)
185 : DL(DL), MaxFrameAlignment(MaxFrameAlignment) {}
186
187 /// Add a field to this structure for the storage of an `alloca`
188 /// instruction.
189 [[nodiscard]] FieldIDType addFieldForAlloca(AllocaInst *AI,
190 bool IsHeader = false) {
191 auto Size = AI->getAllocationSize(DL: AI->getDataLayout());
192 if (!Size || !Size->isFixed())
193 report_fatal_error(
194 reason: "Coroutines cannot handle non static or vscale allocas yet");
195 return addField(FieldSize: Size->getFixedValue(), FieldAlignment: AI->getAlign(), IsHeader);
196 }
197
198 /// We want to put the allocas whose lifetime-ranges are not overlapped
199 /// into one slot of coroutine frame.
200 /// Consider the example at:https://bugs.llvm.org/show_bug.cgi?id=45566
201 ///
202 /// cppcoro::task<void> alternative_paths(bool cond) {
203 /// if (cond) {
204 /// big_structure a;
205 /// process(a);
206 /// co_await something();
207 /// } else {
208 /// big_structure b;
209 /// process2(b);
210 /// co_await something();
211 /// }
212 /// }
213 ///
214 /// We want to put variable a and variable b in the same slot to
215 /// reduce the size of coroutine frame.
216 ///
217 /// This function use StackLifetime algorithm to partition the AllocaInsts in
218 /// Spills to non-overlapped sets in order to put Alloca in the same
219 /// non-overlapped set into the same slot in the Coroutine Frame. Then add
220 /// field for the allocas in the same non-overlapped set by using the largest
221 /// type as the field type.
222 ///
223 /// Side Effects: Because We sort the allocas, the order of allocas in the
224 /// frame may be different with the order in the source code.
225 void addFieldForAllocas(const Function &F, FrameDataInfo &FrameData,
226 coro::Shape &Shape, bool OptimizeFrame);
227
228 /// Add a field to this structure for a spill.
229 [[nodiscard]] FieldIDType addField(Type *Ty, MaybeAlign MaybeFieldAlignment,
230 bool IsHeader = false,
231 bool IsSpillOfValue = false) {
232 assert(Ty && "must provide a type for a field");
233 // The field size is the alloc size of the type.
234 uint64_t FieldSize = DL.getTypeAllocSize(Ty);
235 // The field alignment is usually the type alignment.
236 // But if we are spilling values we don't need to worry about ABI alignment
237 // concerns.
238 Align ABIAlign = DL.getABITypeAlign(Ty);
239 Align TyAlignment = ABIAlign;
240 if (IsSpillOfValue && MaxFrameAlignment && *MaxFrameAlignment < ABIAlign)
241 TyAlignment = *MaxFrameAlignment;
242 Align FieldAlignment = MaybeFieldAlignment.value_or(u&: TyAlignment);
243 return addField(FieldSize, FieldAlignment, IsHeader);
244 }
245
246 /// Add a field to this structure.
247 [[nodiscard]] FieldIDType addField(uint64_t FieldSize, Align FieldAlignment,
248 bool IsHeader = false) {
249 assert(!IsFinished && "adding fields to a finished builder");
250
251 // For an alloca with size=0, we don't need to add a field and they
252 // can just point to any index in the frame. Use index 0.
253 if (FieldSize == 0)
254 return 0;
255
256 // The field alignment could be bigger than the max frame case, in that case
257 // we request additional storage to be able to dynamically align the
258 // pointer.
259 uint64_t DynamicAlignBuffer = 0;
260 if (MaxFrameAlignment && (FieldAlignment > *MaxFrameAlignment)) {
261 DynamicAlignBuffer =
262 offsetToAlignment(Value: MaxFrameAlignment->value(), Alignment: FieldAlignment);
263 FieldAlignment = *MaxFrameAlignment;
264 FieldSize = FieldSize + DynamicAlignBuffer;
265 }
266
267 // Lay out header fields immediately.
268 uint64_t Offset;
269 if (IsHeader) {
270 Offset = alignTo(Size: StructSize, A: FieldAlignment);
271 StructSize = Offset + FieldSize;
272
273 // Everything else has a flexible offset.
274 } else {
275 Offset = OptimizedStructLayoutField::FlexibleOffset;
276 }
277
278 Fields.push_back(Elt: {.Size: FieldSize, .Offset: Offset, .Alignment: FieldAlignment, .DynamicAlignBuffer: DynamicAlignBuffer});
279 return Fields.size() - 1;
280 }
281
282 /// Finish the layout and compute final size and alignment.
283 void finish();
284
285 uint64_t getStructSize() const {
286 assert(IsFinished && "not yet finished!");
287 return StructSize;
288 }
289
290 Align getStructAlign() const {
291 assert(IsFinished && "not yet finished!");
292 return StructAlign;
293 }
294
295 Field getLayoutField(FieldIDType Id) const {
296 assert(IsFinished && "not yet finished!");
297 return Fields[Id];
298 }
299};
300} // namespace
301
302void FrameDataInfo::updateLayoutInfo(FrameTypeBuilder &B) {
303 auto Updater = [&](Value *I) {
304 uint32_t FieldIndex = getFieldIndex(V: I);
305 auto Field = B.getLayoutField(Id: FieldIndex);
306 setAlign(V: I, AL: Field.Alignment);
307 uint64_t dynamicAlign =
308 Field.DynamicAlignBuffer
309 ? Field.DynamicAlignBuffer + Field.Alignment.value()
310 : 0;
311 setDynamicAlign(V: I, Align: dynamicAlign);
312 setOffset(V: I, Offset: Field.Offset);
313 };
314 for (auto &S : Spills)
315 Updater(S.first);
316 for (const auto &A : Allocas)
317 Updater(A.Alloca);
318}
319
320void FrameTypeBuilder::addFieldForAllocas(const Function &F,
321 FrameDataInfo &FrameData,
322 coro::Shape &Shape,
323 bool OptimizeFrame) {
324 using AllocaSetType = SmallVector<AllocaInst *, 4>;
325 SmallVector<AllocaSetType, 4> NonOverlapedAllocas;
326
327 // We need to add field for allocas at the end of this function.
328 llvm::scope_exit AddFieldForAllocasAtExit([&]() {
329 for (auto AllocaList : NonOverlapedAllocas) {
330 auto *LargestAI = *AllocaList.begin();
331 FieldIDType Id = addFieldForAlloca(AI: LargestAI);
332 for (auto *Alloca : AllocaList)
333 FrameData.setFieldIndex(V: Alloca, Index: Id);
334 }
335 });
336
337 if (!OptimizeFrame) {
338 for (const auto &A : FrameData.Allocas) {
339 AllocaInst *Alloca = A.Alloca;
340 NonOverlapedAllocas.emplace_back(Args: AllocaSetType(1, Alloca));
341 }
342 return;
343 }
344
345 // Because there are paths from the lifetime.start to coro.end
346 // for each alloca, the liferanges for every alloca is overlaped
347 // in the blocks who contain coro.end and the successor blocks.
348 // So we choose to skip there blocks when we calculate the liferange
349 // for each alloca. It should be reasonable since there shouldn't be uses
350 // in these blocks and the coroutine frame shouldn't be used outside the
351 // coroutine body.
352 //
353 // Note that the user of coro.suspend may not be SwitchInst. However, this
354 // case seems too complex to handle. And it is harmless to skip these
355 // patterns since it just prevend putting the allocas to live in the same
356 // slot.
357 DenseMap<SwitchInst *, BasicBlock *> DefaultSuspendDest;
358 for (auto *CoroSuspendInst : Shape.CoroSuspends) {
359 for (auto *U : CoroSuspendInst->users()) {
360 if (auto *ConstSWI = dyn_cast<SwitchInst>(Val: U)) {
361 auto *SWI = const_cast<SwitchInst *>(ConstSWI);
362 DefaultSuspendDest[SWI] = SWI->getDefaultDest();
363 SWI->setDefaultDest(SWI->getSuccessor(idx: 1));
364 }
365 }
366 }
367
368 auto ExtractAllocas = [&]() {
369 AllocaSetType Allocas;
370 Allocas.reserve(N: FrameData.Allocas.size());
371 for (const auto &A : FrameData.Allocas)
372 Allocas.push_back(Elt: A.Alloca);
373 return Allocas;
374 };
375 StackLifetime StackLifetimeAnalyzer(F, ExtractAllocas(),
376 StackLifetime::LivenessType::May);
377 StackLifetimeAnalyzer.run();
378 auto DoAllocasInterfere = [&](const AllocaInst *AI1, const AllocaInst *AI2) {
379 return StackLifetimeAnalyzer.getLiveRange(AI: AI1).overlaps(
380 Other: StackLifetimeAnalyzer.getLiveRange(AI: AI2));
381 };
382 auto GetAllocaSize = [&](const coro::AllocaInfo &A) {
383 std::optional<TypeSize> RetSize = A.Alloca->getAllocationSize(DL);
384 assert(RetSize && "Variable Length Arrays (VLA) are not supported.\n");
385 assert(!RetSize->isScalable() && "Scalable vectors are not yet supported");
386 return RetSize->getFixedValue();
387 };
388 // Put larger allocas in the front. So the larger allocas have higher
389 // priority to merge, which can save more space potentially. Also each
390 // AllocaSet would be ordered. So we can get the largest Alloca in one
391 // AllocaSet easily.
392 sort(C&: FrameData.Allocas, Comp: [&](const auto &Iter1, const auto &Iter2) {
393 return GetAllocaSize(Iter1) > GetAllocaSize(Iter2);
394 });
395 for (const auto &A : FrameData.Allocas) {
396 AllocaInst *Alloca = A.Alloca;
397 bool Merged = false;
398 // Try to find if the Alloca does not interfere with any existing
399 // NonOverlappedAllocaSet. If it is true, insert the alloca to that
400 // NonOverlappedAllocaSet.
401 for (auto &AllocaSet : NonOverlapedAllocas) {
402 assert(!AllocaSet.empty() && "Processing Alloca Set is not empty.\n");
403 bool NoInterference = none_of(Range&: AllocaSet, P: [&](auto Iter) {
404 return DoAllocasInterfere(Alloca, Iter);
405 });
406 // If the alignment of A is multiple of the alignment of B, the address
407 // of A should satisfy the requirement for aligning for B.
408 //
409 // There may be other more fine-grained strategies to handle the alignment
410 // infomation during the merging process. But it seems hard to handle
411 // these strategies and benefit little.
412 bool Alignable = [&]() -> bool {
413 auto *LargestAlloca = *AllocaSet.begin();
414 return LargestAlloca->getAlign().value() % Alloca->getAlign().value() ==
415 0;
416 }();
417 bool CouldMerge = NoInterference && Alignable;
418 if (!CouldMerge)
419 continue;
420 AllocaSet.push_back(Elt: Alloca);
421 Merged = true;
422 break;
423 }
424 if (!Merged) {
425 NonOverlapedAllocas.emplace_back(Args: AllocaSetType(1, Alloca));
426 }
427 }
428 // Recover the default target destination for each Switch statement
429 // reserved.
430 for (auto SwitchAndDefaultDest : DefaultSuspendDest) {
431 SwitchInst *SWI = SwitchAndDefaultDest.first;
432 BasicBlock *DestBB = SwitchAndDefaultDest.second;
433 SWI->setDefaultDest(DestBB);
434 }
435 // This Debug Info could tell us which allocas are merged into one slot.
436 LLVM_DEBUG(for (auto &AllocaSet
437 : NonOverlapedAllocas) {
438 if (AllocaSet.size() > 1) {
439 dbgs() << "In Function:" << F.getName() << "\n";
440 dbgs() << "Find Union Set "
441 << "\n";
442 dbgs() << "\tAllocas are \n";
443 for (auto Alloca : AllocaSet)
444 dbgs() << "\t\t" << *Alloca << "\n";
445 }
446 });
447}
448
449void FrameTypeBuilder::finish() {
450 assert(!IsFinished && "already finished!");
451
452 // Prepare the optimal-layout field array.
453 // The Id in the layout field is a pointer to our Field for it.
454 SmallVector<OptimizedStructLayoutField, 8> LayoutFields;
455 LayoutFields.reserve(N: Fields.size());
456 for (auto &Field : Fields) {
457 LayoutFields.emplace_back(Args: &Field, Args&: Field.Size, Args&: Field.Alignment,
458 Args&: Field.Offset);
459 }
460
461 // Perform layout to compute size, alignment, and field offsets.
462 auto SizeAndAlign = performOptimizedStructLayout(Fields: LayoutFields);
463 StructSize = SizeAndAlign.first;
464 StructAlign = SizeAndAlign.second;
465
466 auto getField = [](const OptimizedStructLayoutField &LayoutField) -> Field & {
467 return *static_cast<Field *>(const_cast<void*>(LayoutField.Id));
468 };
469
470 // Update field offsets from the computed layout.
471 for (auto &LayoutField : LayoutFields) {
472 auto &F = getField(LayoutField);
473 F.Offset = LayoutField.Offset;
474 }
475
476 IsFinished = true;
477}
478
479static void cacheDIVar(FrameDataInfo &FrameData,
480 DenseMap<Value *, DILocalVariable *> &DIVarCache) {
481 for (auto *V : FrameData.getAllDefs()) {
482 if (DIVarCache.contains(Val: V))
483 continue;
484
485 auto CacheIt = [&DIVarCache, V](const auto &Container) {
486 auto *I = llvm::find_if(Container, [](auto *DDI) {
487 return DDI->getExpression()->getNumElements() == 0;
488 });
489 if (I != Container.end())
490 DIVarCache.insert({V, (*I)->getVariable()});
491 };
492 CacheIt(findDVRDeclares(V));
493 CacheIt(findDVRDeclareValues(V));
494 }
495}
496
497/// Create name for Type. It uses MDString to store new created string to
498/// avoid memory leak.
499static StringRef solveTypeName(Type *Ty) {
500 if (Ty->isIntegerTy()) {
501 // The longest name in common may be '__int_128', which has 9 bits.
502 SmallString<16> Buffer;
503 raw_svector_ostream OS(Buffer);
504 OS << "__int_" << cast<IntegerType>(Val: Ty)->getBitWidth();
505 auto *MDName = MDString::get(Context&: Ty->getContext(), Str: OS.str());
506 return MDName->getString();
507 }
508
509 if (Ty->isFloatingPointTy()) {
510 if (Ty->isFloatTy())
511 return "__float_";
512 if (Ty->isDoubleTy())
513 return "__double_";
514 return "__floating_type_";
515 }
516
517 if (Ty->isPointerTy())
518 return "PointerType";
519
520 if (Ty->isStructTy()) {
521 if (!cast<StructType>(Val: Ty)->hasName())
522 return "__LiteralStructType_";
523
524 auto Name = Ty->getStructName();
525
526 SmallString<16> Buffer(Name);
527 for (auto &Iter : Buffer)
528 if (Iter == '.' || Iter == ':')
529 Iter = '_';
530 auto *MDName = MDString::get(Context&: Ty->getContext(), Str: Buffer.str());
531 return MDName->getString();
532 }
533
534 return "UnknownType";
535}
536
537static DIType *solveDIType(DIBuilder &Builder, Type *Ty,
538 const DataLayout &Layout, DIScope *Scope,
539 unsigned LineNum,
540 DenseMap<Type *, DIType *> &DITypeCache) {
541 if (DIType *DT = DITypeCache.lookup(Val: Ty))
542 return DT;
543
544 StringRef Name = solveTypeName(Ty);
545
546 DIType *RetType = nullptr;
547
548 if (Ty->isIntegerTy()) {
549 auto BitWidth = cast<IntegerType>(Val: Ty)->getBitWidth();
550 RetType = Builder.createBasicType(Name, SizeInBits: BitWidth, Encoding: dwarf::DW_ATE_signed,
551 Flags: llvm::DINode::FlagArtificial);
552 } else if (Ty->isFloatingPointTy()) {
553 RetType = Builder.createBasicType(Name, SizeInBits: Layout.getTypeSizeInBits(Ty),
554 Encoding: dwarf::DW_ATE_float,
555 Flags: llvm::DINode::FlagArtificial);
556 } else if (Ty->isPointerTy()) {
557 // Construct PointerType points to null (aka void *) instead of exploring
558 // pointee type to avoid infinite search problem. For example, we would be
559 // in trouble if we traverse recursively:
560 //
561 // struct Node {
562 // Node* ptr;
563 // };
564 RetType =
565 Builder.createPointerType(PointeeTy: nullptr, SizeInBits: Layout.getTypeSizeInBits(Ty),
566 AlignInBits: Layout.getABITypeAlign(Ty).value() * CHAR_BIT,
567 /*DWARFAddressSpace=*/std::nullopt, Name);
568 } else if (Ty->isStructTy()) {
569 auto *DIStruct = Builder.createStructType(
570 Scope, Name, File: Scope->getFile(), LineNumber: LineNum, SizeInBits: Layout.getTypeSizeInBits(Ty),
571 AlignInBits: Layout.getPrefTypeAlign(Ty).value() * CHAR_BIT,
572 Flags: llvm::DINode::FlagArtificial, DerivedFrom: nullptr, Elements: llvm::DINodeArray());
573
574 auto *StructTy = cast<StructType>(Val: Ty);
575 SmallVector<Metadata *, 16> Elements;
576 for (unsigned I = 0; I < StructTy->getNumElements(); I++) {
577 DIType *DITy = solveDIType(Builder, Ty: StructTy->getElementType(N: I), Layout,
578 Scope: DIStruct, LineNum, DITypeCache);
579 assert(DITy);
580 Elements.push_back(Elt: Builder.createMemberType(
581 Scope: DIStruct, Name: DITy->getName(), File: DIStruct->getFile(), LineNo: LineNum,
582 SizeInBits: DITy->getSizeInBits(), AlignInBits: DITy->getAlignInBits(),
583 OffsetInBits: Layout.getStructLayout(Ty: StructTy)->getElementOffsetInBits(Idx: I),
584 Flags: llvm::DINode::FlagArtificial, Ty: DITy));
585 }
586
587 Builder.replaceArrays(T&: DIStruct, Elements: Builder.getOrCreateArray(Elements));
588
589 RetType = DIStruct;
590 } else {
591 LLVM_DEBUG(dbgs() << "Unresolved Type: " << *Ty << "\n");
592 TypeSize Size = Layout.getTypeSizeInBits(Ty);
593 auto *CharSizeType = Builder.createBasicType(
594 Name, SizeInBits: 8, Encoding: dwarf::DW_ATE_unsigned_char, Flags: llvm::DINode::FlagArtificial);
595
596 if (Size <= 8)
597 RetType = CharSizeType;
598 else {
599 if (Size % 8 != 0)
600 Size = TypeSize::getFixed(ExactSize: Size + 8 - (Size % 8));
601
602 RetType = Builder.createArrayType(
603 Size, AlignInBits: Layout.getPrefTypeAlign(Ty).value(), Ty: CharSizeType,
604 Subscripts: Builder.getOrCreateArray(Elements: Builder.getOrCreateSubrange(Lo: 0, Count: Size / 8)));
605 }
606 }
607
608 DITypeCache.insert(KV: {Ty, RetType});
609 return RetType;
610}
611
612/// Build artificial debug info for C++ coroutine frames to allow users to
613/// inspect the contents of the frame directly
614///
615/// Create Debug information for coroutine frame with debug name "__coro_frame".
616/// The debug information for the fields of coroutine frame is constructed from
617/// the following way:
618/// 1. For all the value in the Frame, we search the use of dbg.declare to find
619/// the corresponding debug variables for the value. If we can find the
620/// debug variable, we can get full and accurate debug information.
621/// 2. If we can't get debug information in step 1 and 2, we could only try to
622/// build the DIType by Type. We did this in solveDIType. We only handle
623/// integer, float, double, integer type and struct type for now.
624static void buildFrameDebugInfo(Function &F, coro::Shape &Shape,
625 FrameDataInfo &FrameData) {
626 DISubprogram *DIS = F.getSubprogram();
627 // If there is no DISubprogram for F, it implies the function is compiled
628 // without debug info. So we also don't generate debug info for the frame.
629
630 if (!DIS || !DIS->getUnit())
631 return;
632
633 if (!dwarf::isCPlusPlus(S: static_cast<llvm::dwarf::SourceLanguage>(
634 DIS->getUnit()->getSourceLanguage().getUnversionedName())) ||
635 DIS->getUnit()->getEmissionKind() !=
636 DICompileUnit::DebugEmissionKind::FullDebug)
637 return;
638
639 assert(Shape.ABI == coro::ABI::Switch &&
640 "We could only build debug infomation for C++ coroutine now.\n");
641
642 DIBuilder DBuilder(*F.getParent(), /*AllowUnresolved*/ false);
643
644 DIFile *DFile = DIS->getFile();
645 unsigned LineNum = DIS->getLine();
646
647 DICompositeType *FrameDITy = DBuilder.createStructType(
648 Scope: DIS->getUnit(), Name: Twine(F.getName() + ".coro_frame_ty").str(), File: DFile,
649 LineNumber: LineNum, SizeInBits: Shape.FrameSize * 8, AlignInBits: Shape.FrameAlign.value() * 8,
650 Flags: llvm::DINode::FlagArtificial, DerivedFrom: nullptr, Elements: llvm::DINodeArray());
651 SmallVector<Metadata *, 16> Elements;
652 DataLayout Layout = F.getDataLayout();
653
654 DenseMap<Value *, DILocalVariable *> DIVarCache;
655 cacheDIVar(FrameData, DIVarCache);
656
657 // This counter is used to avoid same type names. e.g., there would be
658 // many i32 and i64 types in one coroutine. And we would use i32_0 and
659 // i32_1 to avoid the same type. Since it makes no sense the name of the
660 // fields confilicts with each other.
661 unsigned UnknownTypeNum = 0;
662 DenseMap<Type *, DIType *> DITypeCache;
663
664 auto addElement = [&](StringRef Name, uint64_t SizeInBits, uint64_t Alignment,
665 uint64_t Offset, DIType *DITy) {
666 Elements.push_back(Elt: DBuilder.createMemberType(
667 Scope: FrameDITy, Name, File: DFile, LineNo: LineNum, SizeInBits, AlignInBits: Alignment, OffsetInBits: Offset * 8,
668 Flags: llvm::DINode::FlagArtificial, Ty: DITy));
669 };
670
671 auto addDIDef = [&](Value *V) {
672 // Get the offset and alignment for this value.
673 uint64_t Offset = FrameData.getOffset(V);
674 Align Alignment = FrameData.getAlign(V);
675
676 std::string Name;
677 uint64_t SizeInBits;
678 DIType *DITy = nullptr;
679
680 auto It = DIVarCache.find(Val: V);
681 if (It != DIVarCache.end()) {
682 // Get the type from the debug variable.
683 Name = It->second->getName().str();
684 DITy = It->second->getType();
685 } else {
686 if (auto AI = dyn_cast<AllocaInst>(Val: V)) {
687 // Frame alloca
688 DITy = solveDIType(Builder&: DBuilder, Ty: AI->getAllocatedType(), Layout, Scope: FrameDITy,
689 LineNum, DITypeCache);
690 } else {
691 // Spill
692 DITy = solveDIType(Builder&: DBuilder, Ty: V->getType(), Layout, Scope: FrameDITy, LineNum,
693 DITypeCache);
694 }
695 assert(DITy && "SolveDIType shouldn't return nullptr.\n");
696 Name = DITy->getName().str();
697 Name += "_" + std::to_string(val: UnknownTypeNum);
698 UnknownTypeNum++;
699 }
700
701 if (auto AI = dyn_cast<AllocaInst>(Val: V)) {
702 // Lookup the total size of this alloca originally
703 auto Size = AI->getAllocationSize(DL: Layout);
704 assert(Size && Size->isFixed() &&
705 "unreachable due to addFieldForAlloca checks");
706 SizeInBits = Size->getFixedValue() * 8;
707 } else {
708 // Compute the size of the active data of this member for this spill
709 SizeInBits = Layout.getTypeSizeInBits(Ty: V->getType());
710 }
711
712 addElement(Name, SizeInBits, Alignment.value() * 8, Offset, DITy);
713 };
714
715 // For Switch ABI, add debug info for the added fields (resume, destroy).
716 if (Shape.ABI == coro::ABI::Switch) {
717 auto *FnPtrTy = Shape.getSwitchResumePointerType();
718 uint64_t PtrSize = Layout.getPointerSizeInBits(AS: FnPtrTy->getAddressSpace());
719 uint64_t PtrAlign =
720 Layout.getPointerABIAlignment(AS: FnPtrTy->getAddressSpace()).value() * 8;
721 auto *DIPtr = DBuilder.createPointerType(PointeeTy: nullptr, SizeInBits: PtrSize,
722 AlignInBits: FnPtrTy->getAddressSpace());
723 addElement("__resume_fn", PtrSize, PtrAlign, 0, DIPtr);
724 addElement("__destroy_fn", PtrSize, PtrAlign,
725 Shape.SwitchLowering.DestroyOffset, DIPtr);
726 uint64_t IndexSize =
727 Layout.getTypeSizeInBits(Ty: Shape.getIndexType()).getFixedValue();
728 addElement("__coro_index", IndexSize, Shape.SwitchLowering.IndexAlign * 8,
729 Shape.SwitchLowering.IndexOffset,
730 DBuilder.createBasicType(Name: "__coro_index",
731 SizeInBits: (IndexSize < 8) ? 8 : IndexSize,
732 Encoding: dwarf::DW_ATE_unsigned_char));
733 }
734 auto Defs = FrameData.getAllDefs();
735 for (auto *V : Defs)
736 addDIDef(V);
737
738 DBuilder.replaceArrays(T&: FrameDITy, Elements: DBuilder.getOrCreateArray(Elements));
739
740 auto *FrameDIVar =
741 DBuilder.createAutoVariable(Scope: DIS, Name: "__coro_frame", File: DFile, LineNo: LineNum,
742 Ty: FrameDITy, AlwaysPreserve: true, Flags: DINode::FlagArtificial);
743
744 // Subprogram would have ContainedNodes field which records the debug
745 // variables it contained. So we need to add __coro_frame to the
746 // ContainedNodes of it.
747 //
748 // If we don't add __coro_frame to the RetainedNodes, user may get
749 // `no symbol __coro_frame in context` rather than `__coro_frame`
750 // is optimized out, which is more precise.
751 DIS->retainNodes(NodesBegin: &FrameDIVar, NodesEnd: &FrameDIVar + 1);
752
753 // Construct the location for the frame debug variable. The column number
754 // is fake but it should be fine.
755 DILocation *DILoc =
756 DILocation::get(Context&: DIS->getContext(), Line: LineNum, /*Column=*/1, Scope: DIS);
757 assert(FrameDIVar->isValidLocationForIntrinsic(DILoc));
758
759 DbgVariableRecord *NewDVR =
760 new DbgVariableRecord(ValueAsMetadata::get(V: Shape.FramePtr), FrameDIVar,
761 DBuilder.createExpression(), DILoc,
762 DbgVariableRecord::LocationType::Declare);
763 BasicBlock::iterator It = Shape.getInsertPtAfterFramePtr();
764 It->getParent()->insertDbgRecordBefore(DR: NewDVR, Here: It);
765}
766
767// If there is memory accessing to promise alloca before CoroBegin
768static bool hasAccessingPromiseBeforeCB(const DominatorTree &DT,
769 coro::Shape &Shape) {
770 auto *PA = Shape.SwitchLowering.PromiseAlloca;
771 return llvm::any_of(Range: PA->uses(), P: [&](Use &U) {
772 auto *Inst = dyn_cast<Instruction>(Val: U.getUser());
773 if (!Inst || DT.dominates(Def: Shape.CoroBegin, User: Inst))
774 return false;
775
776 if (auto *CI = dyn_cast<CallInst>(Val: Inst)) {
777 // It is fine if the call wouldn't write to the Promise.
778 // This is possible for @llvm.coro.id intrinsics, which
779 // would take the promise as the second argument as a
780 // marker.
781 if (CI->onlyReadsMemory() || CI->onlyReadsMemory(OpNo: CI->getArgOperandNo(U: &U)))
782 return false;
783 return true;
784 }
785
786 return isa<StoreInst>(Val: Inst) ||
787 // It may take too much time to track the uses.
788 // Be conservative about the case the use may escape.
789 isa<GetElementPtrInst>(Val: Inst) ||
790 // There would always be a bitcast for the promise alloca
791 // before we enabled Opaque pointers. And now given
792 // opaque pointers are enabled by default. This should be
793 // fine.
794 isa<BitCastInst>(Val: Inst);
795 });
796}
797
798// Collect pointers into the promise alloca that are created before CoroBegin
799// and used after it, with their offsets, so that insertSpills can recreate
800// them from the frame. SROA, for example, may place GEPs of the promise at the
801// end of the entry block.
802static SmallMapVector<Instruction *, std::optional<APInt>, 4>
803collectPromiseAliasesBeforeCB(const DominatorTree &DT,
804 const coro::Shape &Shape) {
805 SmallMapVector<Instruction *, std::optional<APInt>, 4> Aliases;
806 auto *PA = Shape.SwitchLowering.PromiseAlloca;
807 const DataLayout &DL = PA->getDataLayout();
808 unsigned IdxWidth = DL.getIndexTypeSizeInBits(Ty: PA->getType());
809 SmallVector<std::pair<Instruction *, APInt>> Worklist;
810 Worklist.emplace_back(Args&: PA, Args: APInt(IdxWidth, 0));
811 while (!Worklist.empty()) {
812 auto [Ptr, Offset] = Worklist.pop_back_val();
813 for (User *U : Ptr->users()) {
814 auto *I = dyn_cast<Instruction>(Val: U);
815 if (!I || DT.dominates(Def: Shape.CoroBegin, User: I))
816 continue;
817 APInt NewOffset = Offset;
818 if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: I)) {
819 APInt GEPOffset(IdxWidth, 0);
820 if (!GEP->accumulateConstantOffset(DL, Offset&: GEPOffset))
821 report_fatal_error(reason: "Unable to handle an alias with unknown offset "
822 "created before CoroBegin.");
823 NewOffset += GEPOffset;
824 } else if (!isa<BitCastInst>(Val: I)) {
825 continue;
826 }
827 if (any_of(Range: I->uses(),
828 P: [&](Use &U) { return DT.dominates(Def: Shape.CoroBegin, U); }))
829 Aliases[I] = NewOffset;
830 Worklist.emplace_back(Args&: I, Args&: NewOffset);
831 }
832 }
833 return Aliases;
834}
835
836// Build the coroutine frame type as a byte array.
837// The frame layout includes:
838// - Resume function pointer at offset 0 (Switch ABI only)
839// - Destroy function pointer at offset ptrsize (Switch ABI only)
840// - Promise alloca (Switch ABI only, only if present)
841// - Suspend/Resume index
842// - Spilled values and allocas
843static void buildFrameLayout(Function &F, const DominatorTree &DT,
844 coro::Shape &Shape, FrameDataInfo &FrameData,
845 bool OptimizeFrame) {
846 const DataLayout &DL = F.getDataLayout();
847
848 // We will use this value to cap the alignment of spilled values.
849 std::optional<Align> MaxFrameAlignment;
850 if (Shape.ABI == coro::ABI::Async)
851 MaxFrameAlignment = Shape.AsyncLowering.getContextAlignment();
852 FrameTypeBuilder B(DL, MaxFrameAlignment);
853
854 AllocaInst *PromiseAlloca = Shape.getPromiseAlloca();
855 std::optional<FieldIDType> SwitchIndexFieldId;
856 IntegerType *SwitchIndexType = nullptr;
857
858 if (Shape.ABI == coro::ABI::Switch) {
859 auto *FnPtrTy = Shape.getSwitchResumePointerType();
860
861 // Add header fields for the resume and destroy functions.
862 // We can rely on these being perfectly packed.
863 (void)B.addField(Ty: FnPtrTy, MaybeFieldAlignment: MaybeAlign(), /*header*/ IsHeader: true);
864 (void)B.addField(Ty: FnPtrTy, MaybeFieldAlignment: MaybeAlign(), /*header*/ IsHeader: true);
865
866 // PromiseAlloca field needs to be explicitly added here because it's
867 // a header field with a fixed offset based on its alignment. Hence it
868 // needs special handling.
869 if (PromiseAlloca)
870 FrameData.setFieldIndex(
871 V: PromiseAlloca, Index: B.addFieldForAlloca(AI: PromiseAlloca, /*header*/ IsHeader: true));
872
873 // Add a field to store the suspend index. This doesn't need to
874 // be in the header.
875 unsigned IndexBits = std::max(a: 1U, b: Log2_64_Ceil(Value: Shape.CoroSuspends.size()));
876 Type *LegalTy =
877 F.getDataLayout().getSmallestLegalIntType(C&: F.getContext(), Width: IndexBits);
878 SwitchIndexType = LegalTy ? cast<IntegerType>(Val: LegalTy)
879 : Type::getIntNTy(C&: F.getContext(), N: IndexBits);
880
881 SwitchIndexFieldId = B.addField(Ty: SwitchIndexType, MaybeFieldAlignment: MaybeAlign());
882 } else {
883 assert(PromiseAlloca == nullptr && "lowering doesn't support promises");
884 }
885
886 // Because multiple allocas may own the same field slot,
887 // we add allocas to field here.
888 B.addFieldForAllocas(F, FrameData, Shape, OptimizeFrame);
889 // Add PromiseAlloca to Allocas list so that
890 // 1. updateLayoutIndex could update its index after
891 // `performOptimizedStructLayout`
892 // 2. it is processed in insertSpills.
893 if (Shape.ABI == coro::ABI::Switch && PromiseAlloca) {
894 FrameData.Allocas.emplace_back(Args&: PromiseAlloca,
895 Args: collectPromiseAliasesBeforeCB(DT, Shape),
896 Args: hasAccessingPromiseBeforeCB(DT, Shape));
897 }
898 // Create an entry for every spilled value.
899 for (auto &S : FrameData.Spills) {
900 Type *FieldType = S.first->getType();
901 MaybeAlign MA;
902 // For byval arguments, we need to store the pointed value in the frame,
903 // instead of the pointer itself.
904 if (const Argument *A = dyn_cast<Argument>(Val: S.first)) {
905 if (A->hasByValAttr()) {
906 FieldType = A->getParamByValType();
907 MA = A->getParamAlign();
908 }
909 }
910 FieldIDType Id =
911 B.addField(Ty: FieldType, MaybeFieldAlignment: MA, IsHeader: false /*header*/, IsSpillOfValue: true /*IsSpillOfValue*/);
912 FrameData.setFieldIndex(V: S.first, Index: Id);
913 }
914
915 B.finish();
916
917 FrameData.updateLayoutInfo(B);
918 Shape.FrameAlign = B.getStructAlign();
919 Shape.FrameSize = B.getStructSize();
920
921 switch (Shape.ABI) {
922 case coro::ABI::Switch: {
923 // In the switch ABI, remember the function pointer and index field info.
924 // Resume and Destroy function pointers are in the frame header.
925 const DataLayout &DL = F.getDataLayout();
926 Shape.SwitchLowering.DestroyOffset = DL.getPointerSize();
927
928 auto IndexField = B.getLayoutField(Id: *SwitchIndexFieldId);
929 Shape.SwitchLowering.IndexType = SwitchIndexType;
930 Shape.SwitchLowering.IndexAlign = IndexField.Alignment.value();
931 Shape.SwitchLowering.IndexOffset = IndexField.Offset;
932
933 // Also round the frame size up to a multiple of its alignment, as is
934 // generally expected in C/C++.
935 Shape.FrameSize = alignTo(Size: Shape.FrameSize, A: Shape.FrameAlign);
936 break;
937 }
938
939 // In the retcon ABI, remember whether the frame is inline in the storage.
940 case coro::ABI::Retcon:
941 case coro::ABI::RetconOnce: {
942 auto Id = Shape.getRetconCoroId();
943 Shape.RetconLowering.IsFrameInlineInStorage
944 = (B.getStructSize() <= Id->getStorageSize() &&
945 B.getStructAlign() <= Id->getStorageAlignment());
946 break;
947 }
948 case coro::ABI::Async: {
949 Shape.AsyncLowering.FrameOffset =
950 alignTo(Size: Shape.AsyncLowering.ContextHeaderSize, A: Shape.FrameAlign);
951 // Also make the final context size a multiple of the context alignment to
952 // make allocation easier for allocators.
953 Shape.AsyncLowering.ContextSize =
954 alignTo(Size: Shape.AsyncLowering.FrameOffset + Shape.FrameSize,
955 A: Shape.AsyncLowering.getContextAlignment());
956 if (Shape.AsyncLowering.getContextAlignment() < Shape.FrameAlign) {
957 report_fatal_error(
958 reason: "The alignment requirment of frame variables cannot be higher than "
959 "the alignment of the async function context");
960 }
961 break;
962 }
963 }
964}
965
966/// If MaybeArgument is a byval Argument, return its byval type. Also removes
967/// the captures attribute, so that the argument *value* may be stored directly
968/// on the coroutine frame.
969static Type *extractByvalIfArgument(Value *MaybeArgument) {
970 if (auto *Arg = dyn_cast<Argument>(Val: MaybeArgument)) {
971 Arg->getParent()->removeParamAttr(ArgNo: Arg->getArgNo(), Kind: Attribute::Captures);
972
973 if (Arg->hasByValAttr())
974 return Arg->getParamByValType();
975 }
976 return nullptr;
977}
978
979/// Store Def into the coroutine frame.
980static void createStoreIntoFrame(IRBuilder<> &Builder, Value *Def,
981 Type *ByValTy, const coro::Shape &Shape,
982 const FrameDataInfo &FrameData) {
983 uint64_t Offset = FrameData.getOffset(V: Def);
984
985 Value *G = Shape.FramePtr;
986 if (Offset != 0) {
987 G = Builder.CreatePtrAddWithUnsignedOffset(
988 Ptr: G, Offset, Name: Def->getName() + Twine(".spill.addr"),
989 NW: GEPNoWrapFlags::inBounds());
990 }
991 auto SpillAlignment = Align(FrameData.getAlign(V: Def));
992
993 // For byval arguments, copy the pointed-to value to the frame.
994 if (ByValTy) {
995 auto &DL = Builder.getDataLayout();
996 auto Size = DL.getTypeStoreSize(Ty: ByValTy);
997 // Def is a pointer to the byval argument
998 Builder.CreateMemCpy(Dst: G, DstAlign: SpillAlignment, Src: Def, SrcAlign: SpillAlignment, Size);
999 } else {
1000 Builder.CreateAlignedStore(Val: Def, Ptr: G, Align: SpillAlignment);
1001 }
1002}
1003
1004/// Returns a pointer into the coroutine frame at the offset where Orig is
1005/// located.
1006static Value *createGEPToFramePointer(const FrameDataInfo &FrameData,
1007 IRBuilder<> &Builder, coro::Shape &Shape,
1008 Value *Orig) {
1009 uint64_t Offset = FrameData.getOffset(V: Orig);
1010 Value *Ptr = Builder.CreatePtrAddWithUnsignedOffset(
1011 Ptr: Shape.FramePtr, Offset, Name: "", NW: GEPNoWrapFlags::inBounds());
1012
1013 if (auto *AI = dyn_cast<AllocaInst>(Val: Orig)) {
1014 if (FrameData.getDynamicAlign(V: Orig) != 0) {
1015 assert(FrameData.getDynamicAlign(Orig) == AI->getAlign().value());
1016 auto *M = AI->getModule();
1017 auto *IntPtrTy = M->getDataLayout().getIntPtrType(AI->getType());
1018 auto *PtrValue = Builder.CreatePtrToInt(V: Ptr, DestTy: IntPtrTy);
1019 auto *AlignMask = ConstantInt::get(Ty: IntPtrTy, V: AI->getAlign().value() - 1);
1020 PtrValue = Builder.CreateAdd(LHS: PtrValue, RHS: AlignMask);
1021 PtrValue = Builder.CreateAnd(LHS: PtrValue, RHS: Builder.CreateNot(V: AlignMask));
1022 return Builder.CreateIntToPtr(V: PtrValue, DestTy: AI->getType());
1023 }
1024 // If the type of Ptr is not equal to the type of AllocaInst, it implies
1025 // that the AllocaInst may be reused in the Frame slot of other AllocaInst.
1026 // Note: If the strategy dealing with alignment changes, this cast must be
1027 // refined
1028 if (Ptr->getType() != Orig->getType())
1029 Ptr = Builder.CreateAddrSpaceCast(V: Ptr, DestTy: Orig->getType(),
1030 Name: Orig->getName() + Twine(".cast"));
1031 }
1032 return Ptr;
1033}
1034
1035/// Find dbg.declare or dbg.declare_value records referencing `Def`. If none are
1036/// found, walk up the load chain to find one.
1037template <DbgVariableRecord::LocationType record_type>
1038static TinyPtrVector<DbgVariableRecord *>
1039findDbgRecordsThroughLoads(Function &F, Value *Def) {
1040 static_assert(record_type == DbgVariableRecord::LocationType::Declare ||
1041 record_type == DbgVariableRecord::LocationType::DeclareValue);
1042 constexpr auto FindFunc =
1043 record_type == DbgVariableRecord::LocationType::Declare
1044 ? findDVRDeclares
1045 : findDVRDeclareValues;
1046
1047 TinyPtrVector<DbgVariableRecord *> Records = FindFunc(Def);
1048
1049 if (!F.getSubprogram())
1050 return Records;
1051
1052 Value *CurDef = Def;
1053 while (Records.empty() && isa<LoadInst>(Val: CurDef)) {
1054 auto *LdInst = cast<LoadInst>(Val: CurDef);
1055 if (!LdInst->getType()->isPointerTy())
1056 break;
1057 CurDef = LdInst->getPointerOperand();
1058 if (!isa<AllocaInst, LoadInst>(Val: CurDef))
1059 break;
1060 Records = FindFunc(CurDef);
1061 }
1062
1063 return Records;
1064}
1065
1066// Helper function to handle allocas that may be accessed before CoroBegin.
1067// This creates a memcpy from the original alloca to the coroutine frame after
1068// CoroBegin, ensuring the frame has the correct initial values.
1069static void handleAccessBeforeCoroBegin(const FrameDataInfo &FrameData,
1070 coro::Shape &Shape,
1071 IRBuilder<> &Builder,
1072 AllocaInst *Alloca) {
1073 Value *Size = Builder.CreateAllocationSize(DestTy: Builder.getInt64Ty(), AI: Alloca);
1074 auto *G = createGEPToFramePointer(FrameData, Builder, Shape, Orig: Alloca);
1075 Builder.CreateMemCpy(Dst: G, DstAlign: FrameData.getAlign(V: Alloca), Src: Alloca,
1076 SrcAlign: Alloca->getAlign(), Size);
1077}
1078
1079// Replace all alloca and SSA values that are accessed across suspend points
1080// with GetElementPointer from coroutine frame + loads and stores. Create an
1081// AllocaSpillBB that will become the new entry block for the resume parts of
1082// the coroutine:
1083//
1084// %hdl = coro.begin(...)
1085// whatever
1086//
1087// becomes:
1088//
1089// %hdl = coro.begin(...)
1090// br label %AllocaSpillBB
1091//
1092// AllocaSpillBB:
1093// ; geps corresponding to allocas that were moved to coroutine frame
1094// br label PostSpill
1095//
1096// PostSpill:
1097// whatever
1098//
1099//
1100static void insertSpills(const FrameDataInfo &FrameData, coro::Shape &Shape) {
1101 LLVMContext &C = Shape.CoroBegin->getContext();
1102 Function *F = Shape.CoroBegin->getFunction();
1103 IRBuilder<> Builder(*F->getParent());
1104 DominatorTree DT(*F);
1105 SmallDenseMap<Argument *, AllocaInst *, 4> ArgToAllocaMap;
1106
1107 MDBuilder MDB(C);
1108 // Create a TBAA tag for accesses to certain coroutine frame slots, so that
1109 // subsequent alias analysis will understand they do not intersect with
1110 // user memory.
1111 // We do this only if a suitable TBAA root already exists in the module.
1112 MDNode *TBAATag = nullptr;
1113 if (auto *CppTBAAStr = MDString::getIfExists(Context&: C, Str: "Simple C++ TBAA")) {
1114 auto *TBAARoot = MDNode::getIfExists(Context&: C, MDs: CppTBAAStr);
1115 // Create a "fake" scalar type; all other types defined in the source
1116 // language will be assumed non-aliasing with this type.
1117 MDNode *Scalar = MDB.createTBAAScalarTypeNode(
1118 Name: (F->getName() + ".Frame Slot").str(), Parent: TBAARoot);
1119 TBAATag = MDB.createTBAAStructTagNode(BaseType: Scalar, AccessType: Scalar, Offset: 0);
1120 }
1121 for (auto const &E : FrameData.Spills) {
1122 Value *Def = E.first;
1123 Type *ByValTy = extractByvalIfArgument(MaybeArgument: Def);
1124
1125 Builder.SetInsertPoint(coro::getSpillInsertionPt(Shape, Def, DT));
1126 createStoreIntoFrame(Builder, Def, ByValTy, Shape, FrameData);
1127
1128 BasicBlock *CurrentBlock = nullptr;
1129 Value *CurrentReload = nullptr;
1130 for (auto *U : E.second) {
1131 // If we have not seen the use block, create a load instruction to reload
1132 // the spilled value from the coroutine frame. Populates the Value pointer
1133 // reference provided with the frame GEP.
1134 if (CurrentBlock != U->getParent()) {
1135 CurrentBlock = U->getParent();
1136 Builder.SetInsertPoint(CurrentBlock->getFirstInsertionPt());
1137
1138 auto *GEP = createGEPToFramePointer(FrameData, Builder, Shape, Orig: E.first);
1139 GEP->setName(E.first->getName() + Twine(".reload.addr"));
1140 if (ByValTy) {
1141 CurrentReload = GEP;
1142 } else {
1143 auto SpillAlignment = Align(FrameData.getAlign(V: Def));
1144 auto *LI =
1145 Builder.CreateAlignedLoad(Ty: E.first->getType(), Ptr: GEP, Align: SpillAlignment,
1146 Name: E.first->getName() + Twine(".reload"));
1147 if (TBAATag)
1148 LI->setMetadata(KindID: LLVMContext::MD_tbaa, Node: TBAATag);
1149 CurrentReload = LI;
1150 }
1151
1152 TinyPtrVector<DbgVariableRecord *> DVRs = findDbgRecordsThroughLoads<
1153 DbgVariableRecord::LocationType::Declare>(F&: *F, Def);
1154
1155 auto SalvageOne = [&](DbgVariableRecord *DDI) {
1156 // This dbg.declare is preserved for all coro-split function
1157 // fragments. It will be unreachable in the main function, and
1158 // processed by coro::salvageDebugInfo() by the Cloner.
1159 DbgVariableRecord *NewDVR = new DbgVariableRecord(
1160 ValueAsMetadata::get(V: CurrentReload), DDI->getVariable(),
1161 DDI->getExpression(), DDI->getDebugLoc(),
1162 DbgVariableRecord::LocationType::Declare);
1163 Builder.GetInsertPoint()->getParent()->insertDbgRecordBefore(
1164 DR: NewDVR, Here: Builder.GetInsertPoint());
1165 // This dbg.declare is for the main function entry point. It
1166 // will be deleted in all coro-split functions.
1167 coro::salvageDebugInfo(ArgToAllocaMap, DVR&: *DDI, UseEntryValue: false /*UseEntryValue*/);
1168 };
1169 for_each(Range&: DVRs, F: SalvageOne);
1170 }
1171
1172 TinyPtrVector<DbgVariableRecord *> DVRDeclareValues =
1173 findDbgRecordsThroughLoads<
1174 DbgVariableRecord::LocationType::DeclareValue>(F&: *F, Def);
1175
1176 auto SalvageOneCoro = [&](auto *DDI) {
1177 // This dbg.declare_value is preserved for all coro-split function
1178 // fragments. It will be unreachable in the main function, and
1179 // processed by coro::salvageDebugInfo() by the Cloner. However, convert
1180 // it to a dbg.declare to make sure future passes don't have to deal
1181 // with a dbg.declare_value.
1182 auto *VAM = ValueAsMetadata::get(V: CurrentReload);
1183 Type *Ty = VAM->getValue()->getType();
1184 // If the metadata type is not a pointer, emit a dbg.value instead.
1185 DbgVariableRecord *NewDVR = new DbgVariableRecord(
1186 ValueAsMetadata::get(V: CurrentReload), DDI->getVariable(),
1187 DDI->getExpression(), DDI->getDebugLoc(),
1188 Ty->isPointerTy() ? DbgVariableRecord::LocationType::Declare
1189 : DbgVariableRecord::LocationType::Value);
1190 Builder.GetInsertPoint()->getParent()->insertDbgRecordBefore(
1191 DR: NewDVR, Here: Builder.GetInsertPoint());
1192 // This dbg.declare_value is for the main function entry point. It
1193 // will be deleted in all coro-split functions.
1194 coro::salvageDebugInfo(ArgToAllocaMap, DVR&: *DDI, UseEntryValue: false /*UseEntryValue*/);
1195 };
1196 for_each(Range&: DVRDeclareValues, F: SalvageOneCoro);
1197
1198 // If we have a single edge PHINode, remove it and replace it with a
1199 // reload from the coroutine frame. (We already took care of multi edge
1200 // PHINodes by normalizing them in the rewritePHIs function).
1201 if (auto *PN = dyn_cast<PHINode>(Val: U)) {
1202 assert(PN->getNumIncomingValues() == 1 &&
1203 "unexpected number of incoming "
1204 "values in the PHINode");
1205 PN->replaceAllUsesWith(V: CurrentReload);
1206 PN->eraseFromParent();
1207 continue;
1208 }
1209
1210 // Replace all uses of CurrentValue in the current instruction with
1211 // reload.
1212 U->replaceUsesOfWith(From: Def, To: CurrentReload);
1213 // Instructions are added to Def's user list if the attached
1214 // debug records use Def. Update those now.
1215 for (DbgVariableRecord &DVR : filterDbgVars(R: U->getDbgRecordRange()))
1216 DVR.replaceVariableLocationOp(OldValue: Def, NewValue: CurrentReload, AllowEmpty: true);
1217 }
1218 }
1219
1220 BasicBlock *FramePtrBB = Shape.getInsertPtAfterFramePtr()->getParent();
1221
1222 auto SpillBlock = FramePtrBB->splitBasicBlock(
1223 I: Shape.getInsertPtAfterFramePtr(), BBName: "AllocaSpillBB");
1224 SpillBlock->splitBasicBlock(I: &SpillBlock->front(), BBName: "PostSpill");
1225 Shape.AllocaSpillBlock = SpillBlock;
1226
1227 // retcon and retcon.once lowering assumes all uses have been sunk.
1228 if (Shape.ABI == coro::ABI::Retcon || Shape.ABI == coro::ABI::RetconOnce ||
1229 Shape.ABI == coro::ABI::Async) {
1230 // If we found any allocas, replace all of their remaining uses with Geps.
1231 Builder.SetInsertPoint(SpillBlock->begin());
1232 for (const auto &P : FrameData.Allocas) {
1233 AllocaInst *Alloca = P.Alloca;
1234 auto *G = createGEPToFramePointer(FrameData, Builder, Shape, Orig: Alloca);
1235
1236 // Remove any lifetime intrinsics, now that these are no longer allocas.
1237 for (User *U : make_early_inc_range(Range: Alloca->users())) {
1238 auto *I = cast<Instruction>(Val: U);
1239 if (I->isLifetimeStartOrEnd())
1240 I->eraseFromParent();
1241 }
1242
1243 // We are not using ReplaceInstWithInst(P.first, cast<Instruction>(G))
1244 // here, as we are changing location of the instruction.
1245 G->takeName(V: Alloca);
1246 Alloca->replaceAllUsesWith(V: G);
1247 Alloca->eraseFromParent();
1248 }
1249 return;
1250 }
1251
1252 // If we found any alloca, replace all of their remaining uses with GEP
1253 // instructions. To remain debugbility, we replace the uses of allocas for
1254 // dbg.declares and dbg.values with the reload from the frame.
1255 // Note: We cannot replace the alloca with GEP instructions indiscriminately,
1256 // as some of the uses may not be dominated by CoroBegin.
1257 Builder.SetInsertPoint(Shape.AllocaSpillBlock->begin());
1258 SmallVector<Instruction *, 4> UsersToUpdate;
1259 for (const auto &A : FrameData.Allocas) {
1260 AllocaInst *Alloca = A.Alloca;
1261 UsersToUpdate.clear();
1262 for (User *U : make_early_inc_range(Range: Alloca->users())) {
1263 auto *I = cast<Instruction>(Val: U);
1264 // It is meaningless to retain the lifetime intrinsics refer for the
1265 // member of coroutine frames and the meaningless lifetime intrinsics
1266 // are possible to block further optimizations.
1267 if (I->isLifetimeStartOrEnd())
1268 I->eraseFromParent();
1269 else if (DT.dominates(Def: Shape.CoroBegin, User: I))
1270 UsersToUpdate.push_back(Elt: I);
1271 }
1272
1273 if (UsersToUpdate.empty())
1274 continue;
1275 auto *G = createGEPToFramePointer(FrameData, Builder, Shape, Orig: Alloca);
1276 G->setName(Alloca->getName() + Twine(".reload.addr"));
1277
1278 SmallVector<DbgVariableRecord *> DbgVariableRecords;
1279 findDbgUsers(V: Alloca, DbgVariableRecords);
1280 for (auto *DVR : DbgVariableRecords)
1281 DVR->replaceVariableLocationOp(OldValue: Alloca, NewValue: G);
1282
1283 for (Instruction *I : UsersToUpdate)
1284 I->replaceUsesOfWith(From: Alloca, To: G);
1285
1286 if (Alloca->user_empty())
1287 Alloca->eraseFromParent();
1288 }
1289 Builder.SetInsertPoint(&*Shape.getInsertPtAfterFramePtr());
1290 for (const auto &A : FrameData.Allocas) {
1291 AllocaInst *Alloca = A.Alloca;
1292 if (A.MayWriteBeforeCoroBegin) {
1293 // isEscaped really means potentially modified before CoroBegin.
1294 handleAccessBeforeCoroBegin(FrameData, Shape, Builder, Alloca);
1295 }
1296 // For each alias to Alloca created before CoroBegin but used after
1297 // CoroBegin, we recreate them after CoroBegin by applying the offset
1298 // to the pointer in the frame.
1299 for (const auto &Alias : A.Aliases) {
1300 auto *FramePtr =
1301 createGEPToFramePointer(FrameData, Builder, Shape, Orig: Alloca);
1302 auto &Offset = *Alias.second;
1303 auto ITy = IntegerType::get(C, NumBits: Offset.getBitWidth());
1304 Value *AliasPtr =
1305 Builder.CreateInBoundsPtrAdd(Ptr: FramePtr, Offset: ConstantInt::get(Ty: ITy, V: Offset));
1306 if (auto *CI = dyn_cast<CastInst>(Val: Alias.first);
1307 CI && !CI->getType()->isPtrOrPtrVectorTy())
1308 AliasPtr = Builder.CreateCast(Op: CI->getOpcode(), V: AliasPtr, DestTy: CI->getType());
1309 Alias.first->replaceUsesWithIf(
1310 New: AliasPtr, ShouldReplace: [&](Use &U) { return DT.dominates(Def: Shape.CoroBegin, U); });
1311 }
1312 }
1313}
1314
1315// Moves the values in the PHIs in SuccBB that correspong to PredBB into a new
1316// PHI in InsertedBB.
1317static void movePHIValuesToInsertedBlock(BasicBlock *SuccBB,
1318 BasicBlock *InsertedBB,
1319 BasicBlock *PredBB,
1320 PHINode *UntilPHI = nullptr) {
1321 auto *PN = cast<PHINode>(Val: &SuccBB->front());
1322 do {
1323 int Index = PN->getBasicBlockIndex(BB: InsertedBB);
1324 Value *V = PN->getIncomingValue(i: Index);
1325 PHINode *InputV = PHINode::Create(
1326 Ty: V->getType(), NumReservedValues: 1, NameStr: V->getName() + Twine(".") + SuccBB->getName());
1327 InputV->insertBefore(InsertPos: InsertedBB->begin());
1328 InputV->addIncoming(V, BB: PredBB);
1329 PN->setIncomingValue(i: Index, V: InputV);
1330 PN = dyn_cast<PHINode>(Val: PN->getNextNode());
1331 } while (PN != UntilPHI);
1332}
1333
1334// Rewrites the PHI Nodes in a cleanuppad.
1335static void rewritePHIsForCleanupPad(BasicBlock *CleanupPadBB,
1336 CleanupPadInst *CleanupPad) {
1337 // For every incoming edge to a CleanupPad we will create a new block holding
1338 // all incoming values in single-value PHI nodes. We will then create another
1339 // block to act as a dispather (as all unwind edges for related EH blocks
1340 // must be the same).
1341 //
1342 // cleanuppad:
1343 // %2 = phi i32[%0, %catchswitch], [%1, %catch.1]
1344 // %3 = cleanuppad within none []
1345 //
1346 // It will create:
1347 //
1348 // cleanuppad.corodispatch
1349 // %2 = phi i8[0, %catchswitch], [1, %catch.1]
1350 // %3 = cleanuppad within none []
1351 // switch i8 % 2, label %unreachable
1352 // [i8 0, label %cleanuppad.from.catchswitch
1353 // i8 1, label %cleanuppad.from.catch.1]
1354 // cleanuppad.from.catchswitch:
1355 // %4 = phi i32 [%0, %catchswitch]
1356 // br %label cleanuppad
1357 // cleanuppad.from.catch.1:
1358 // %6 = phi i32 [%1, %catch.1]
1359 // br %label cleanuppad
1360 // cleanuppad:
1361 // %8 = phi i32 [%4, %cleanuppad.from.catchswitch],
1362 // [%6, %cleanuppad.from.catch.1]
1363
1364 // Unreachable BB, in case switching on an invalid value in the dispatcher.
1365 auto *UnreachBB = BasicBlock::Create(
1366 Context&: CleanupPadBB->getContext(), Name: "unreachable", Parent: CleanupPadBB->getParent());
1367 IRBuilder<> Builder(UnreachBB);
1368 Builder.CreateUnreachable();
1369
1370 // Create a new cleanuppad which will be the dispatcher.
1371 auto *NewCleanupPadBB =
1372 BasicBlock::Create(Context&: CleanupPadBB->getContext(),
1373 Name: CleanupPadBB->getName() + Twine(".corodispatch"),
1374 Parent: CleanupPadBB->getParent(), InsertBefore: CleanupPadBB);
1375 Builder.SetInsertPoint(NewCleanupPadBB);
1376 auto *SwitchType = Builder.getInt8Ty();
1377 auto *SetDispatchValuePN =
1378 Builder.CreatePHI(Ty: SwitchType, NumReservedValues: pred_size(BB: CleanupPadBB));
1379 CleanupPad->removeFromParent();
1380 CleanupPad->insertAfter(InsertPos: SetDispatchValuePN->getIterator());
1381 auto *SwitchOnDispatch = Builder.CreateSwitch(V: SetDispatchValuePN, Dest: UnreachBB,
1382 NumCases: pred_size(BB: CleanupPadBB));
1383
1384 int SwitchIndex = 0;
1385 SmallVector<BasicBlock *, 8> Preds(predecessors(BB: CleanupPadBB));
1386 for (BasicBlock *Pred : Preds) {
1387 // Create a new cleanuppad and move the PHI values to there.
1388 auto *CaseBB = BasicBlock::Create(Context&: CleanupPadBB->getContext(),
1389 Name: CleanupPadBB->getName() +
1390 Twine(".from.") + Pred->getName(),
1391 Parent: CleanupPadBB->getParent(), InsertBefore: CleanupPadBB);
1392 updatePhiNodes(DestBB: CleanupPadBB, OldPred: Pred, NewPred: CaseBB);
1393 CaseBB->setName(CleanupPadBB->getName() + Twine(".from.") +
1394 Pred->getName());
1395 Builder.SetInsertPoint(CaseBB);
1396 Builder.CreateBr(Dest: CleanupPadBB);
1397 movePHIValuesToInsertedBlock(SuccBB: CleanupPadBB, InsertedBB: CaseBB, PredBB: NewCleanupPadBB);
1398
1399 // Update this Pred to the new unwind point.
1400 setUnwindEdgeTo(TI: Pred->getTerminator(), Succ: NewCleanupPadBB);
1401
1402 // Setup the switch in the dispatcher.
1403 auto *SwitchConstant = ConstantInt::get(Ty: SwitchType, V: SwitchIndex);
1404 SetDispatchValuePN->addIncoming(V: SwitchConstant, BB: Pred);
1405 SwitchOnDispatch->addCase(OnVal: SwitchConstant, Dest: CaseBB);
1406 SwitchIndex++;
1407 }
1408
1409 if (!ProfcheckDisableMetadataFixes) {
1410 // Add branch weights to SwitchOnDispatch, where branches are unreachable by
1411 // default. We mark all branches as having equal weights because they are
1412 // mutually exclusive.
1413 MDBuilder MDB(CleanupPadBB->getContext());
1414 SmallVector<uint32_t> Weights;
1415 Weights.push_back(Elt: 0);
1416 for (int i = 0; i < SwitchIndex; ++i) {
1417 Weights.push_back(Elt: llvm::MDBuilder::kUnlikelyBranchWeight);
1418 }
1419 SwitchOnDispatch->setMetadata(KindID: LLVMContext::MD_prof,
1420 Node: MDB.createBranchWeights(Weights));
1421 }
1422}
1423
1424static void cleanupSinglePredPHIs(Function &F) {
1425 SmallVector<PHINode *, 32> Worklist;
1426 for (auto &BB : F) {
1427 for (auto &Phi : BB.phis()) {
1428 if (Phi.getNumIncomingValues() == 1) {
1429 Worklist.push_back(Elt: &Phi);
1430 } else
1431 break;
1432 }
1433 }
1434 while (!Worklist.empty()) {
1435 auto *Phi = Worklist.pop_back_val();
1436 auto *OriginalValue = Phi->getIncomingValue(i: 0);
1437 Phi->replaceAllUsesWith(V: OriginalValue);
1438 }
1439}
1440
1441static void rewritePHIs(BasicBlock &BB) {
1442 // For every incoming edge we will create a block holding all
1443 // incoming values in a single PHI nodes.
1444 //
1445 // loop:
1446 // %n.val = phi i32[%n, %entry], [%inc, %loop]
1447 //
1448 // It will create:
1449 //
1450 // loop.from.entry:
1451 // %n.loop.pre = phi i32 [%n, %entry]
1452 // br %label loop
1453 // loop.from.loop:
1454 // %inc.loop.pre = phi i32 [%inc, %loop]
1455 // br %label loop
1456 //
1457 // After this rewrite, further analysis will ignore any phi nodes with more
1458 // than one incoming edge.
1459
1460 // TODO: Simplify PHINodes in the basic block to remove duplicate
1461 // predecessors.
1462
1463 // Special case for CleanupPad: all EH blocks must have the same unwind edge
1464 // so we need to create an additional "dispatcher" block.
1465 if (!BB.empty()) {
1466 if (auto *CleanupPad =
1467 dyn_cast_or_null<CleanupPadInst>(Val: BB.getFirstNonPHIIt())) {
1468 SmallVector<BasicBlock *, 8> Preds(predecessors(BB: &BB));
1469 for (BasicBlock *Pred : Preds) {
1470 if (CatchSwitchInst *CS =
1471 dyn_cast<CatchSwitchInst>(Val: Pred->getTerminator())) {
1472 // CleanupPad with a CatchSwitch predecessor: therefore this is an
1473 // unwind destination that needs to be handle specially.
1474 assert(CS->getUnwindDest() == &BB);
1475 (void)CS;
1476 rewritePHIsForCleanupPad(CleanupPadBB: &BB, CleanupPad);
1477 return;
1478 }
1479 }
1480 }
1481 }
1482
1483 LandingPadInst *LandingPad = nullptr;
1484 PHINode *ReplPHI = nullptr;
1485 if (!BB.empty()) {
1486 if ((LandingPad =
1487 dyn_cast_or_null<LandingPadInst>(Val: BB.getFirstNonPHIIt()))) {
1488 // ehAwareSplitEdge will clone the LandingPad in all the edge blocks.
1489 // We replace the original landing pad with a PHINode that will collect the
1490 // results from all of them.
1491 ReplPHI = PHINode::Create(Ty: LandingPad->getType(), NumReservedValues: 1, NameStr: "");
1492 ReplPHI->insertBefore(InsertPos: LandingPad->getIterator());
1493 ReplPHI->takeName(V: LandingPad);
1494 LandingPad->replaceAllUsesWith(V: ReplPHI);
1495 // We will erase the original landing pad at the end of this function after
1496 // ehAwareSplitEdge cloned it in the transition blocks.
1497 }
1498 }
1499
1500 SmallVector<BasicBlock *, 8> Preds(predecessors(BB: &BB));
1501 for (BasicBlock *Pred : Preds) {
1502 auto *IncomingBB = ehAwareSplitEdge(BB: Pred, Succ: &BB, OriginalPad: LandingPad, LandingPadReplacement: ReplPHI);
1503 IncomingBB->setName(BB.getName() + Twine(".from.") + Pred->getName());
1504
1505 // Stop the moving of values at ReplPHI, as this is either null or the PHI
1506 // that replaced the landing pad.
1507 movePHIValuesToInsertedBlock(SuccBB: &BB, InsertedBB: IncomingBB, PredBB: Pred, UntilPHI: ReplPHI);
1508 }
1509
1510 if (LandingPad) {
1511 // Calls to ehAwareSplitEdge function cloned the original lading pad.
1512 // No longer need it.
1513 LandingPad->eraseFromParent();
1514 }
1515}
1516
1517static void rewritePHIs(Function &F) {
1518 SmallVector<BasicBlock *, 8> WorkList;
1519
1520 for (BasicBlock &BB : F)
1521 if (auto *PN = dyn_cast<PHINode>(Val: &BB.front()))
1522 if (PN->getNumIncomingValues() > 1)
1523 WorkList.push_back(Elt: &BB);
1524
1525 for (BasicBlock *BB : WorkList)
1526 rewritePHIs(BB&: *BB);
1527}
1528
1529// Splits the block at a particular instruction unless it is the first
1530// instruction in the block with a single predecessor.
1531static BasicBlock *splitBlockIfNotFirst(Instruction *I, const Twine &Name) {
1532 auto *BB = I->getParent();
1533 if (&BB->front() == I) {
1534 if (BB->getSinglePredecessor()) {
1535 BB->setName(Name);
1536 return BB;
1537 }
1538 }
1539 return BB->splitBasicBlock(I, BBName: Name);
1540}
1541
1542// Split above and below a particular instruction so that it
1543// will be all alone by itself in a block.
1544static void splitAround(Instruction *I, const Twine &Name) {
1545 splitBlockIfNotFirst(I, Name);
1546 splitBlockIfNotFirst(I: I->getNextNode(), Name: "After" + Name);
1547}
1548
1549/// After we split the coroutine, will the given basic block be along
1550/// an obvious exit path for the resumption function?
1551static bool willLeaveFunctionImmediatelyAfter(BasicBlock *BB,
1552 unsigned depth = 3) {
1553 // If we've bottomed out our depth count, stop searching and assume
1554 // that the path might loop back.
1555 if (depth == 0) return false;
1556
1557 // If this is a suspend block, we're about to exit the resumption function.
1558 if (coro::isSuspendBlock(BB))
1559 return true;
1560
1561 // Recurse into the successors.
1562 for (auto *Succ : successors(BB)) {
1563 if (!willLeaveFunctionImmediatelyAfter(BB: Succ, depth: depth - 1))
1564 return false;
1565 }
1566
1567 // If none of the successors leads back in a loop, we're on an exit/abort.
1568 return true;
1569}
1570
1571static bool localAllocaNeedsStackSave(CoroAllocaAllocInst *AI) {
1572 // Look for a free that isn't sufficiently obviously followed by
1573 // either a suspend or a termination, i.e. something that will leave
1574 // the coro resumption frame.
1575 for (auto *U : AI->users()) {
1576 auto FI = dyn_cast<CoroAllocaFreeInst>(Val: U);
1577 if (!FI) continue;
1578
1579 if (!willLeaveFunctionImmediatelyAfter(BB: FI->getParent()))
1580 return true;
1581 }
1582
1583 // If we never found one, we don't need a stack save.
1584 return false;
1585}
1586
1587/// Turn each of the given local allocas into a normal (dynamic) alloca
1588/// instruction.
1589static void lowerLocalAllocas(ArrayRef<CoroAllocaAllocInst*> LocalAllocas,
1590 SmallVectorImpl<Instruction*> &DeadInsts) {
1591 for (auto *AI : LocalAllocas) {
1592 IRBuilder<> Builder(AI);
1593
1594 // Save the stack depth. Try to avoid doing this if the stackrestore
1595 // is going to immediately precede a return or something.
1596 Value *StackSave = nullptr;
1597 if (localAllocaNeedsStackSave(AI))
1598 StackSave = Builder.CreateStackSave();
1599
1600 // Allocate memory.
1601 auto Alloca = Builder.CreateAlloca(Ty: Builder.getInt8Ty(), ArraySize: AI->getSize());
1602 Alloca->setAlignment(AI->getAlignment());
1603
1604 for (auto *U : AI->users()) {
1605 // Replace gets with the allocation.
1606 if (isa<CoroAllocaGetInst>(Val: U)) {
1607 U->replaceAllUsesWith(V: Alloca);
1608
1609 // Replace frees with stackrestores. This is safe because
1610 // alloca.alloc is required to obey a stack discipline, although we
1611 // don't enforce that structurally.
1612 } else {
1613 auto FI = cast<CoroAllocaFreeInst>(Val: U);
1614 if (StackSave) {
1615 Builder.SetInsertPoint(FI);
1616 Builder.CreateStackRestore(Ptr: StackSave);
1617 }
1618 }
1619 DeadInsts.push_back(Elt: cast<Instruction>(Val: U));
1620 }
1621
1622 DeadInsts.push_back(Elt: AI);
1623 }
1624}
1625
1626/// Get the current swifterror value.
1627static Value *emitGetSwiftErrorValue(IRBuilder<> &Builder, Type *ValueTy,
1628 coro::Shape &Shape) {
1629 // Make a fake function pointer as a sort of intrinsic.
1630 auto FnTy = FunctionType::get(Result: ValueTy, Params: {}, isVarArg: false);
1631 auto Fn = ConstantPointerNull::get(T: Builder.getPtrTy());
1632
1633 auto Call = Builder.CreateCall(FTy: FnTy, Callee: Fn, Args: {});
1634 Shape.SwiftErrorOps.push_back(Elt: Call);
1635
1636 return Call;
1637}
1638
1639/// Set the given value as the current swifterror value.
1640///
1641/// Returns a slot that can be used as a swifterror slot.
1642static Value *emitSetSwiftErrorValue(IRBuilder<> &Builder, Value *V,
1643 coro::Shape &Shape) {
1644 // Make a fake function pointer as a sort of intrinsic.
1645 auto FnTy = FunctionType::get(Result: Builder.getPtrTy(),
1646 Params: {V->getType()}, isVarArg: false);
1647 auto Fn = ConstantPointerNull::get(T: Builder.getPtrTy());
1648
1649 auto Call = Builder.CreateCall(FTy: FnTy, Callee: Fn, Args: { V });
1650 Shape.SwiftErrorOps.push_back(Elt: Call);
1651
1652 return Call;
1653}
1654
1655/// Set the swifterror value from the given alloca before a call,
1656/// then put in back in the alloca afterwards.
1657///
1658/// Returns an address that will stand in for the swifterror slot
1659/// until splitting.
1660static Value *emitSetAndGetSwiftErrorValueAround(Instruction *Call,
1661 AllocaInst *Alloca,
1662 coro::Shape &Shape) {
1663 auto ValueTy = Alloca->getAllocatedType();
1664 IRBuilder<> Builder(Call);
1665
1666 // Load the current value from the alloca and set it as the
1667 // swifterror value.
1668 auto ValueBeforeCall = Builder.CreateLoad(Ty: ValueTy, Ptr: Alloca);
1669 auto Addr = emitSetSwiftErrorValue(Builder, V: ValueBeforeCall, Shape);
1670
1671 // Move to after the call. Since swifterror only has a guaranteed
1672 // value on normal exits, we can ignore implicit and explicit unwind
1673 // edges.
1674 if (isa<CallInst>(Val: Call)) {
1675 Builder.SetInsertPoint(Call->getNextNode());
1676 } else {
1677 auto Invoke = cast<InvokeInst>(Val: Call);
1678 Builder.SetInsertPoint(
1679 Invoke->getNormalDest()->getFirstNonPHIOrPseudoProbe());
1680 }
1681
1682 // Get the current swifterror value and store it to the alloca.
1683 auto ValueAfterCall = emitGetSwiftErrorValue(Builder, ValueTy, Shape);
1684 Builder.CreateStore(Val: ValueAfterCall, Ptr: Alloca);
1685
1686 return Addr;
1687}
1688
1689/// Eliminate a formerly-swifterror alloca by inserting the get/set
1690/// intrinsics and attempting to MemToReg the alloca away.
1691static void eliminateSwiftErrorAlloca(Function &F, AllocaInst *Alloca,
1692 coro::Shape &Shape) {
1693 for (Use &Use : llvm::make_early_inc_range(Range: Alloca->uses())) {
1694 // swifterror values can only be used in very specific ways.
1695 // We take advantage of that here.
1696 auto User = Use.getUser();
1697 if (isa<LoadInst>(Val: User) || isa<StoreInst>(Val: User))
1698 continue;
1699
1700 assert(isa<CallInst>(User) || isa<InvokeInst>(User));
1701 auto Call = cast<Instruction>(Val: User);
1702
1703 auto Addr = emitSetAndGetSwiftErrorValueAround(Call, Alloca, Shape);
1704
1705 // Use the returned slot address as the call argument.
1706 Use.set(Addr);
1707 }
1708
1709 // All the uses should be loads and stores now.
1710 assert(isAllocaPromotable(Alloca));
1711}
1712
1713/// "Eliminate" a swifterror argument by reducing it to the alloca case
1714/// and then loading and storing in the prologue and epilog.
1715///
1716/// The argument keeps the swifterror flag.
1717static void eliminateSwiftErrorArgument(Function &F, Argument &Arg,
1718 coro::Shape &Shape,
1719 SmallVectorImpl<AllocaInst*> &AllocasToPromote) {
1720 IRBuilder<> Builder(F.getEntryBlock().getFirstNonPHIOrPseudoProbe());
1721
1722 auto ArgTy = cast<PointerType>(Val: Arg.getType());
1723 auto ValueTy = PointerType::getUnqual(C&: F.getContext());
1724
1725 // Reduce to the alloca case:
1726
1727 // Create an alloca and replace all uses of the arg with it.
1728 auto Alloca = Builder.CreateAlloca(Ty: ValueTy, AddrSpace: ArgTy->getAddressSpace());
1729 Arg.replaceAllUsesWith(V: Alloca);
1730
1731 // Set an initial value in the alloca. swifterror is always null on entry.
1732 auto InitialValue = Constant::getNullValue(Ty: ValueTy);
1733 Builder.CreateStore(Val: InitialValue, Ptr: Alloca);
1734
1735 // Find all the suspends in the function and save and restore around them.
1736 for (auto *Suspend : Shape.CoroSuspends) {
1737 (void) emitSetAndGetSwiftErrorValueAround(Call: Suspend, Alloca, Shape);
1738 }
1739
1740 // Find all the coro.ends in the function and restore the error value.
1741 for (auto *End : Shape.CoroEnds) {
1742 Builder.SetInsertPoint(End);
1743 auto FinalValue = Builder.CreateLoad(Ty: ValueTy, Ptr: Alloca);
1744 (void) emitSetSwiftErrorValue(Builder, V: FinalValue, Shape);
1745 }
1746
1747 // Now we can use the alloca logic.
1748 AllocasToPromote.push_back(Elt: Alloca);
1749 eliminateSwiftErrorAlloca(F, Alloca, Shape);
1750}
1751
1752/// Eliminate all problematic uses of swifterror arguments and allocas
1753/// from the function. We'll fix them up later when splitting the function.
1754static void eliminateSwiftError(Function &F, coro::Shape &Shape) {
1755 SmallVector<AllocaInst*, 4> AllocasToPromote;
1756
1757 // Look for a swifterror argument.
1758 for (auto &Arg : F.args()) {
1759 if (!Arg.hasSwiftErrorAttr()) continue;
1760
1761 eliminateSwiftErrorArgument(F, Arg, Shape, AllocasToPromote);
1762 break;
1763 }
1764
1765 // Look for swifterror allocas.
1766 for (auto &Inst : F.getEntryBlock()) {
1767 auto Alloca = dyn_cast<AllocaInst>(Val: &Inst);
1768 if (!Alloca || !Alloca->isSwiftError()) continue;
1769
1770 // Clear the swifterror flag.
1771 Alloca->setSwiftError(false);
1772
1773 AllocasToPromote.push_back(Elt: Alloca);
1774 eliminateSwiftErrorAlloca(F, Alloca, Shape);
1775 }
1776
1777 // If we have any allocas to promote, compute a dominator tree and
1778 // promote them en masse.
1779 if (!AllocasToPromote.empty()) {
1780 DominatorTree DT(F);
1781 PromoteMemToReg(Allocas: AllocasToPromote, DT);
1782 }
1783}
1784
1785/// For each local variable that all of its user are only used inside one of
1786/// suspended region, we sink their lifetime.start markers to the place where
1787/// after the suspend block. Doing so minimizes the lifetime of each variable,
1788/// hence minimizing the amount of data we end up putting on the frame.
1789static void sinkLifetimeStartMarkers(Function &F, coro::Shape &Shape,
1790 SuspendCrossingInfo &Checker,
1791 const DominatorTree &DT) {
1792 if (F.hasOptNone())
1793 return;
1794
1795 // Collect all possible basic blocks which may dominate all uses of allocas.
1796 SmallPtrSet<BasicBlock *, 4> DomSet;
1797 DomSet.insert(Ptr: &F.getEntryBlock());
1798 for (auto *CSI : Shape.CoroSuspends) {
1799 BasicBlock *SuspendBlock = CSI->getParent();
1800 assert(coro::isSuspendBlock(SuspendBlock) &&
1801 SuspendBlock->getSingleSuccessor() &&
1802 "should have split coro.suspend into its own block");
1803 DomSet.insert(Ptr: SuspendBlock->getSingleSuccessor());
1804 }
1805
1806 for (Instruction &I : instructions(F)) {
1807 AllocaInst* AI = dyn_cast<AllocaInst>(Val: &I);
1808 if (!AI)
1809 continue;
1810
1811 for (BasicBlock *DomBB : DomSet) {
1812 bool Valid = true;
1813 SmallVector<Instruction *, 1> Lifetimes;
1814
1815 auto isLifetimeStart = [](Instruction* I) {
1816 if (auto* II = dyn_cast<IntrinsicInst>(Val: I))
1817 return II->getIntrinsicID() == Intrinsic::lifetime_start;
1818 return false;
1819 };
1820
1821 auto collectLifetimeStart = [&](Instruction *U, AllocaInst *AI) {
1822 if (isLifetimeStart(U)) {
1823 Lifetimes.push_back(Elt: U);
1824 return true;
1825 }
1826 if (!U->hasOneUse() || U->stripPointerCasts() != AI)
1827 return false;
1828 if (isLifetimeStart(U->user_back())) {
1829 Lifetimes.push_back(Elt: U->user_back());
1830 return true;
1831 }
1832 return false;
1833 };
1834
1835 for (User *U : AI->users()) {
1836 Instruction *UI = cast<Instruction>(Val: U);
1837 // For all users except lifetime.start markers, if they are all
1838 // dominated by one of the basic blocks and do not cross
1839 // suspend points as well, then there is no need to spill the
1840 // instruction.
1841 if (!DT.dominates(A: DomBB, B: UI->getParent()) ||
1842 Checker.isDefinitionAcrossSuspend(DefBB: DomBB, U: UI)) {
1843 // Skip lifetime.start, GEP and bitcast used by lifetime.start
1844 // markers.
1845 if (collectLifetimeStart(UI, AI))
1846 continue;
1847 Valid = false;
1848 break;
1849 }
1850 }
1851 // Sink lifetime.start markers to dominate block when they are
1852 // only used outside the region.
1853 if (Valid && Lifetimes.size() != 0) {
1854 auto *NewLifetime = Lifetimes[0]->clone();
1855 NewLifetime->replaceUsesOfWith(From: NewLifetime->getOperand(i: 0), To: AI);
1856 NewLifetime->insertBefore(InsertPos: DomBB->getTerminator()->getIterator());
1857
1858 // All the outsided lifetime.start markers are no longer necessary.
1859 for (Instruction *S : Lifetimes)
1860 S->eraseFromParent();
1861
1862 break;
1863 }
1864 }
1865 }
1866}
1867
1868static std::optional<std::pair<Value &, DIExpression &>>
1869salvageDebugInfoImpl(SmallDenseMap<Argument *, AllocaInst *, 4> &ArgToAllocaMap,
1870 bool UseEntryValue, Function *F, Value *Storage,
1871 DIExpression *Expr, bool SkipOutermostLoad) {
1872 auto InsertPt = F->getEntryBlock().getFirstInsertionPt();
1873 while (isa<IntrinsicInst>(Val: InsertPt))
1874 ++InsertPt;
1875 IRBuilder<> Builder(InsertPt);
1876
1877 while (auto *Inst = dyn_cast_or_null<Instruction>(Val: Storage)) {
1878 if (auto *LdInst = dyn_cast<LoadInst>(Val: Inst)) {
1879 Storage = LdInst->getPointerOperand();
1880 // FIXME: This is a heuristic that works around the fact that
1881 // LLVM IR debug intrinsics cannot yet distinguish between
1882 // memory and value locations: Because a dbg.declare(alloca) is
1883 // implicitly a memory location no DW_OP_deref operation for the
1884 // last direct load from an alloca is necessary. This condition
1885 // effectively drops the *last* DW_OP_deref in the expression.
1886 if (!SkipOutermostLoad)
1887 Expr = DIExpression::prepend(Expr, Flags: DIExpression::DerefBefore);
1888 } else if (auto *StInst = dyn_cast<StoreInst>(Val: Inst)) {
1889 Storage = StInst->getValueOperand();
1890 } else {
1891 SmallVector<uint64_t, 16> Ops;
1892 SmallVector<Value *, 0> AdditionalValues;
1893 Value *Op = llvm::salvageDebugInfoImpl(
1894 I&: *Inst, CurrentLocOps: Expr ? Expr->getNumLocationOperands() : 0, Ops,
1895 AdditionalValues);
1896 if (!Op || !AdditionalValues.empty()) {
1897 // If salvaging failed or salvaging produced more than one location
1898 // operand, give up.
1899 break;
1900 }
1901 Storage = Op;
1902 Expr = DIExpression::appendOpsToArg(Expr, Ops, ArgNo: 0, /*StackValue*/ false);
1903 }
1904 SkipOutermostLoad = false;
1905 }
1906 if (!Storage)
1907 return std::nullopt;
1908
1909 auto *StorageAsArg = dyn_cast<Argument>(Val: Storage);
1910
1911 const bool IsSingleLocationExpression = Expr->isSingleLocationExpression();
1912 // Use an EntryValue when requested (UseEntryValue) for swift async Arguments.
1913 // Entry values in variadic expressions are not supported.
1914 const bool WillUseEntryValue =
1915 UseEntryValue && StorageAsArg &&
1916 StorageAsArg->hasAttribute(Kind: Attribute::SwiftAsync) &&
1917 !Expr->isEntryValue() && IsSingleLocationExpression;
1918
1919 if (WillUseEntryValue)
1920 Expr = DIExpression::prepend(Expr, Flags: DIExpression::EntryValue);
1921
1922 // If the coroutine frame is an Argument, store it in an alloca to improve
1923 // its availability (e.g. registers may be clobbered).
1924 // Avoid this if the value is guaranteed to be available through other means
1925 // (e.g. swift ABI guarantees).
1926 // Avoid this if multiple location expressions are involved, as LLVM does not
1927 // know how to prepend a deref in this scenario.
1928 if (StorageAsArg && !WillUseEntryValue && IsSingleLocationExpression) {
1929 auto &Cached = ArgToAllocaMap[StorageAsArg];
1930 if (!Cached) {
1931 Cached = Builder.CreateAlloca(Ty: Storage->getType(), AddrSpace: 0, ArraySize: nullptr,
1932 Name: Storage->getName() + ".debug");
1933 Builder.CreateStore(Val: Storage, Ptr: Cached);
1934 }
1935 Storage = Cached;
1936 // FIXME: LLVM lacks nuanced semantics to differentiate between
1937 // memory and direct locations at the IR level. The backend will
1938 // turn a dbg.declare(alloca, ..., DIExpression()) into a memory
1939 // location. Thus, if there are deref and offset operations in the
1940 // expression, we need to add a DW_OP_deref at the *start* of the
1941 // expression to first load the contents of the alloca before
1942 // adjusting it with the expression.
1943 Expr = DIExpression::prepend(Expr, Flags: DIExpression::DerefBefore);
1944 }
1945
1946 Expr = Expr->foldConstantMath();
1947 return {{*Storage, *Expr}};
1948}
1949
1950void coro::salvageDebugInfo(
1951 SmallDenseMap<Argument *, AllocaInst *, 4> &ArgToAllocaMap,
1952 DbgVariableRecord &DVR, bool UseEntryValue) {
1953
1954 Function *F = DVR.getFunction();
1955 // Follow the pointer arithmetic all the way to the incoming
1956 // function argument and convert into a DIExpression.
1957 bool SkipOutermostLoad = DVR.isDbgDeclare() || DVR.isDbgDeclareValue();
1958 Value *OriginalStorage = DVR.getVariableLocationOp(OpIdx: 0);
1959
1960 auto SalvagedInfo =
1961 ::salvageDebugInfoImpl(ArgToAllocaMap, UseEntryValue, F, Storage: OriginalStorage,
1962 Expr: DVR.getExpression(), SkipOutermostLoad);
1963 if (!SalvagedInfo)
1964 return;
1965
1966 Value *Storage = &SalvagedInfo->first;
1967 DIExpression *Expr = &SalvagedInfo->second;
1968
1969 DVR.replaceVariableLocationOp(OldValue: OriginalStorage, NewValue: Storage);
1970 DVR.setExpression(Expr);
1971 // We only hoist dbg.declare and dbg.declare_value today since it doesn't make
1972 // sense to hoist dbg.value since it does not have the same function wide
1973 // guarantees that dbg.declare does.
1974 if (DVR.getType() == DbgVariableRecord::LocationType::Declare ||
1975 DVR.getType() == DbgVariableRecord::LocationType::DeclareValue) {
1976 std::optional<BasicBlock::iterator> InsertPt;
1977 if (auto *I = dyn_cast<Instruction>(Val: Storage)) {
1978 InsertPt = I->getInsertionPointAfterDef();
1979 // Update DILocation only if variable was not inlined.
1980 DebugLoc ILoc = I->getDebugLoc();
1981 DebugLoc DVRLoc = DVR.getDebugLoc();
1982 if (ILoc && DVRLoc &&
1983 DVRLoc->getScope()->getSubprogram() ==
1984 ILoc->getScope()->getSubprogram())
1985 DVR.setDebugLoc(ILoc);
1986 } else if (isa<Argument>(Val: Storage))
1987 InsertPt = F->getEntryBlock().begin();
1988 if (InsertPt) {
1989 DVR.removeFromParent();
1990 // If there is a dbg.declare_value being reinserted, insert it as a
1991 // dbg.declare instead, so that subsequent passes don't have to deal with
1992 // a dbg.declare_value.
1993 if (DVR.getType() == DbgVariableRecord::LocationType::DeclareValue) {
1994 auto *MD = DVR.getRawLocation();
1995 if (auto *VAM = dyn_cast<ValueAsMetadata>(Val: MD)) {
1996 Type *Ty = VAM->getValue()->getType();
1997 if (Ty->isPointerTy())
1998 DVR.Type = DbgVariableRecord::LocationType::Declare;
1999 else
2000 DVR.Type = DbgVariableRecord::LocationType::Value;
2001 }
2002 }
2003 (*InsertPt)->getParent()->insertDbgRecordBefore(DR: &DVR, Here: *InsertPt);
2004 }
2005 }
2006}
2007
2008void coro::normalizeCoroutine(Function &F, coro::Shape &Shape,
2009 TargetTransformInfo &TTI) {
2010 // Don't eliminate swifterror in async functions that won't be split.
2011 if (Shape.ABI != coro::ABI::Async || !Shape.CoroSuspends.empty())
2012 eliminateSwiftError(F, Shape);
2013
2014 if (Shape.ABI == coro::ABI::Switch &&
2015 Shape.SwitchLowering.PromiseAlloca) {
2016 Shape.getSwitchCoroId()->clearPromise();
2017 }
2018
2019 // Make sure that all coro.save, coro.suspend and the fallthrough coro.end
2020 // intrinsics are in their own blocks to simplify the logic of building up
2021 // SuspendCrossing data.
2022 for (auto *CSI : Shape.CoroSuspends) {
2023 if (auto *Save = CSI->getCoroSave())
2024 splitAround(I: Save, Name: "CoroSave");
2025 splitAround(I: CSI, Name: "CoroSuspend");
2026 }
2027
2028 // Put CoroEnds into their own blocks.
2029 for (AnyCoroEndInst *CE : Shape.CoroEnds) {
2030 splitAround(I: CE, Name: "CoroEnd");
2031
2032 // Emit the musttail call function in a new block before the CoroEnd.
2033 // We do this here so that the right suspend crossing info is computed for
2034 // the uses of the musttail call function call. (Arguments to the coro.end
2035 // instructions would be ignored)
2036 if (auto *AsyncEnd = dyn_cast<CoroAsyncEndInst>(Val: CE)) {
2037 auto *MustTailCallFn = AsyncEnd->getMustTailCallFunction();
2038 if (!MustTailCallFn)
2039 continue;
2040 IRBuilder<> Builder(AsyncEnd);
2041 SmallVector<Value *, 8> Args(AsyncEnd->args());
2042 auto Arguments = ArrayRef<Value *>(Args).drop_front(N: 3);
2043 auto *Call = coro::createMustTailCall(
2044 Loc: AsyncEnd->getDebugLoc(), MustTailCallFn, TTI, Arguments, Builder);
2045 splitAround(I: Call, Name: "MustTailCall.Before.CoroEnd");
2046 }
2047 }
2048
2049 // Later code makes structural assumptions about single predecessors phis e.g
2050 // that they are not live across a suspend point.
2051 cleanupSinglePredPHIs(F);
2052
2053 // Transforms multi-edge PHI Nodes, so that any value feeding into a PHI will
2054 // never have its definition separated from the PHI by the suspend point.
2055 rewritePHIs(F);
2056}
2057
2058void coro::BaseABI::buildCoroutineFrame(bool OptimizeFrame) {
2059 SuspendCrossingInfo Checker(F, Shape);
2060 doRematerializations(F, Checker, IsMaterializable);
2061
2062 const DominatorTree DT(F);
2063 if (Shape.ABI != coro::ABI::Async && Shape.ABI != coro::ABI::Retcon &&
2064 Shape.ABI != coro::ABI::RetconOnce)
2065 sinkLifetimeStartMarkers(F, Shape, Checker, DT);
2066
2067 // All values (that are not allocas) that needs to be spilled to the frame.
2068 coro::SpillInfo Spills;
2069 // All values defined as allocas that need to live in the frame.
2070 SmallVector<coro::AllocaInfo, 8> Allocas;
2071
2072 // Collect the spills for arguments and other not-materializable values.
2073 coro::collectSpillsFromArgs(Spills, F, Checker);
2074 SmallVector<Instruction *, 4> DeadInstructions;
2075 SmallVector<CoroAllocaAllocInst *, 4> LocalAllocas;
2076 coro::collectSpillsAndAllocasFromInsts(Spills, Allocas, DeadInstructions,
2077 LocalAllocas, F, Checker, DT, Shape);
2078 coro::collectSpillsFromDbgInfo(Spills, F, Checker);
2079
2080 LLVM_DEBUG(dumpAllocas(Allocas));
2081 LLVM_DEBUG(dumpSpills("Spills", Spills));
2082
2083 if (Shape.ABI == coro::ABI::Retcon || Shape.ABI == coro::ABI::RetconOnce ||
2084 Shape.ABI == coro::ABI::Async)
2085 sinkSpillUsesAfterCoroBegin(DT, CoroBegin: Shape.CoroBegin, Spills, Allocas);
2086
2087 // Build frame layout
2088 FrameDataInfo FrameData(Spills, Allocas);
2089 buildFrameLayout(F, DT, Shape, FrameData, OptimizeFrame);
2090 Shape.FramePtr = Shape.CoroBegin;
2091 // For now, this works for C++ programs only.
2092 buildFrameDebugInfo(F, Shape, FrameData);
2093 // Insert spills and reloads
2094 insertSpills(FrameData, Shape);
2095 lowerLocalAllocas(LocalAllocas, DeadInsts&: DeadInstructions);
2096
2097 for (auto *I : DeadInstructions)
2098 I->eraseFromParent();
2099}
2100