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