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