brintos / llvm-project-archived public Read only

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-exception6//7//===----------------------------------------------------------------------===//8// This file contains classes used to discover if for a particular value9// its definition precedes and its uses follow a suspend block. This is10// referred to as a suspend crossing value.11//12// Using the information discovered we form a Coroutine Frame structure to13// contain those values. All uses of those values are replaced with appropriate14// GEP + load from the coroutine frame. At the point of the definition we spill15// 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/Module.h"29#include "llvm/Support/Compiler.h"30#include "llvm/Support/Debug.h"31#include "llvm/Support/OptimizedStructLayout.h"32#include "llvm/Transforms/Coroutines/ABI.h"33#include "llvm/Transforms/Coroutines/CoroInstr.h"34#include "llvm/Transforms/Coroutines/MaterializationUtils.h"35#include "llvm/Transforms/Coroutines/SpillUtils.h"36#include "llvm/Transforms/Coroutines/SuspendCrossingInfo.h"37#include "llvm/Transforms/Utils/BasicBlockUtils.h"38#include "llvm/Transforms/Utils/Local.h"39#include "llvm/Transforms/Utils/PromoteMemToReg.h"40#include <algorithm>41#include <limits>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 the53  // frame.54  coro::SpillInfo &Spills;55  // Allocas contains all values defined as allocas that need to live in the56  // 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(P.first);67    for (const auto &A : Allocas)68      Defs.push_back(A.Alloca);69    return Defs;70  }71 72  uint32_t getFieldIndex(Value *V) const {73    auto Itr = FieldIndexMap.find(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((LayoutIndexUpdateStarted || 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(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({V, AL});94  }95 96  uint64_t getDynamicAlign(Value *V) const {97    auto Iter = FieldDynamicAlignMap.find(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({V, Align});105  }106 107  uint64_t getOffset(Value *V) const {108    auto Iter = FieldOffsetMap.find(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({V, Offset});116  }117 118  // Remap the index of every field in the frame, using the final layout index.119  void updateLayoutIndex(FrameTypeBuilder &B);120 121private:122  // LayoutIndexUpdateStarted is used to avoid updating the index of any field123  // twice by mistake.124  bool LayoutIndexUpdateStarted = false;125  // Map from values to their slot indexes on the frame. They will be first set126  // with their original insertion field index. After the frame is built, their127  // indexes will be updated into the final layout index.128  DenseMap<Value *, uint32_t> FieldIndexMap;129  // Map from values to their alignment on the frame. They would be set after130  // the frame is built.131  DenseMap<Value *, Align> FieldAlignMap;132  DenseMap<Value *, uint64_t> FieldDynamicAlignMap;133  // Map from values to their offset on the frame. They would be set after134  // the frame is built.135  DenseMap<Value *, uint64_t> FieldOffsetMap;136};137} // namespace138 139#ifndef NDEBUG140static void dumpSpills(StringRef Title, const coro::SpillInfo &Spills) {141  dbgs() << "------------- " << Title << " --------------\n";142  for (const auto &E : Spills) {143    E.first->dump();144    dbgs() << "   user: ";145    for (auto *I : E.second)146      I->dump();147  }148}149 150static void dumpAllocas(const SmallVectorImpl<coro::AllocaInfo> &Allocas) {151  dbgs() << "------------- Allocas --------------\n";152  for (const auto &A : Allocas) {153    A.Alloca->dump();154  }155}156#endif157 158namespace {159using FieldIDType = size_t;160// We cannot rely solely on natural alignment of a type when building a161// coroutine frame and if the alignment specified on the Alloca instruction162// differs from the natural alignment of the alloca type we will need to insert163// padding.164class FrameTypeBuilder {165private:166  struct Field {167    uint64_t Size;168    uint64_t Offset;169    Type *Ty;170    FieldIDType LayoutFieldIndex;171    Align Alignment;172    Align TyAlignment;173    uint64_t DynamicAlignBuffer;174  };175 176  const DataLayout &DL;177  LLVMContext &Context;178  uint64_t StructSize = 0;179  Align StructAlign;180  bool IsFinished = false;181 182  std::optional<Align> MaxFrameAlignment;183 184  SmallVector<Field, 8> Fields;185  DenseMap<Value*, unsigned> FieldIndexByKey;186 187public:188  FrameTypeBuilder(LLVMContext &Context, const DataLayout &DL,189                   std::optional<Align> MaxFrameAlignment)190      : DL(DL), Context(Context), MaxFrameAlignment(MaxFrameAlignment) {}191 192  /// Add a field to this structure for the storage of an `alloca`193  /// instruction.194  [[nodiscard]] FieldIDType addFieldForAlloca(AllocaInst *AI,195                                              bool IsHeader = false) {196    Type *Ty = AI->getAllocatedType();197 198    // Make an array type if this is a static array allocation.199    if (AI->isArrayAllocation()) {200      if (auto *CI = dyn_cast<ConstantInt>(AI->getArraySize()))201        Ty = ArrayType::get(Ty, CI->getValue().getZExtValue());202      else203        report_fatal_error("Coroutines cannot handle non static allocas yet");204    }205 206    return addField(Ty, AI->getAlign(), IsHeader);207  }208 209  /// We want to put the allocas whose lifetime-ranges are not overlapped210  /// into one slot of coroutine frame.211  /// Consider the example at:https://bugs.llvm.org/show_bug.cgi?id=45566212  ///213  ///     cppcoro::task<void> alternative_paths(bool cond) {214  ///         if (cond) {215  ///             big_structure a;216  ///             process(a);217  ///             co_await something();218  ///         } else {219  ///             big_structure b;220  ///             process2(b);221  ///             co_await something();222  ///         }223  ///     }224  ///225  /// We want to put variable a and variable b in the same slot to226  /// reduce the size of coroutine frame.227  ///228  /// This function use StackLifetime algorithm to partition the AllocaInsts in229  /// Spills to non-overlapped sets in order to put Alloca in the same230  /// non-overlapped set into the same slot in the Coroutine Frame. Then add231  /// field for the allocas in the same non-overlapped set by using the largest232  /// type as the field type.233  ///234  /// Side Effects: Because We sort the allocas, the order of allocas in the235  /// frame may be different with the order in the source code.236  void addFieldForAllocas(const Function &F, FrameDataInfo &FrameData,237                          coro::Shape &Shape, bool OptimizeFrame);238 239  /// Add a field to this structure.240  [[nodiscard]] FieldIDType addField(Type *Ty, MaybeAlign MaybeFieldAlignment,241                                     bool IsHeader = false,242                                     bool IsSpillOfValue = false) {243    assert(!IsFinished && "adding fields to a finished builder");244    assert(Ty && "must provide a type for a field");245 246    // The field size is always the alloc size of the type.247    uint64_t FieldSize = DL.getTypeAllocSize(Ty);248 249    // For an alloca with size=0, we don't need to add a field and they250    // can just point to any index in the frame. Use index 0.251    if (FieldSize == 0) {252      return 0;253    }254 255    // The field alignment might not be the type alignment, but we need256    // to remember the type alignment anyway to build the type.257    // If we are spilling values we don't need to worry about ABI alignment258    // concerns.259    Align ABIAlign = DL.getABITypeAlign(Ty);260    Align TyAlignment = ABIAlign;261    if (IsSpillOfValue && MaxFrameAlignment && *MaxFrameAlignment < ABIAlign)262      TyAlignment = *MaxFrameAlignment;263    Align FieldAlignment = MaybeFieldAlignment.value_or(TyAlignment);264 265    // The field alignment could be bigger than the max frame case, in that case266    // we request additional storage to be able to dynamically align the267    // pointer.268    uint64_t DynamicAlignBuffer = 0;269    if (MaxFrameAlignment && (FieldAlignment > *MaxFrameAlignment)) {270      DynamicAlignBuffer =271          offsetToAlignment(MaxFrameAlignment->value(), FieldAlignment);272      FieldAlignment = *MaxFrameAlignment;273      FieldSize = FieldSize + DynamicAlignBuffer;274    }275 276    // Lay out header fields immediately.277    uint64_t Offset;278    if (IsHeader) {279      Offset = alignTo(StructSize, FieldAlignment);280      StructSize = Offset + FieldSize;281 282      // Everything else has a flexible offset.283    } else {284      Offset = OptimizedStructLayoutField::FlexibleOffset;285    }286 287    Fields.push_back({FieldSize, Offset, Ty, 0, FieldAlignment, TyAlignment,288                      DynamicAlignBuffer});289    return Fields.size() - 1;290  }291 292  /// Finish the layout and create the struct type with the given name.293  StructType *finish(StringRef Name);294 295  uint64_t getStructSize() const {296    assert(IsFinished && "not yet finished!");297    return StructSize;298  }299 300  Align getStructAlign() const {301    assert(IsFinished && "not yet finished!");302    return StructAlign;303  }304 305  FieldIDType getLayoutFieldIndex(FieldIDType Id) const {306    assert(IsFinished && "not yet finished!");307    return Fields[Id].LayoutFieldIndex;308  }309 310  Field getLayoutField(FieldIDType Id) const {311    assert(IsFinished && "not yet finished!");312    return Fields[Id];313  }314};315} // namespace316 317void FrameDataInfo::updateLayoutIndex(FrameTypeBuilder &B) {318  auto Updater = [&](Value *I) {319    auto Field = B.getLayoutField(getFieldIndex(I));320    setFieldIndex(I, Field.LayoutFieldIndex);321    setAlign(I, Field.Alignment);322    uint64_t dynamicAlign =323        Field.DynamicAlignBuffer324            ? Field.DynamicAlignBuffer + Field.Alignment.value()325            : 0;326    setDynamicAlign(I, dynamicAlign);327    setOffset(I, Field.Offset);328  };329  LayoutIndexUpdateStarted = true;330  for (auto &S : Spills)331    Updater(S.first);332  for (const auto &A : Allocas)333    Updater(A.Alloca);334  LayoutIndexUpdateStarted = false;335}336 337void FrameTypeBuilder::addFieldForAllocas(const Function &F,338                                          FrameDataInfo &FrameData,339                                          coro::Shape &Shape,340                                          bool OptimizeFrame) {341  using AllocaSetType = SmallVector<AllocaInst *, 4>;342  SmallVector<AllocaSetType, 4> NonOverlapedAllocas;343 344  // We need to add field for allocas at the end of this function.345  auto AddFieldForAllocasAtExit = make_scope_exit([&]() {346    for (auto AllocaList : NonOverlapedAllocas) {347      auto *LargestAI = *AllocaList.begin();348      FieldIDType Id = addFieldForAlloca(LargestAI);349      for (auto *Alloca : AllocaList)350        FrameData.setFieldIndex(Alloca, Id);351    }352  });353 354  if (!OptimizeFrame) {355    for (const auto &A : FrameData.Allocas) {356      AllocaInst *Alloca = A.Alloca;357      NonOverlapedAllocas.emplace_back(AllocaSetType(1, Alloca));358    }359    return;360  }361 362  // Because there are paths from the lifetime.start to coro.end363  // for each alloca, the liferanges for every alloca is overlaped364  // in the blocks who contain coro.end and the successor blocks.365  // So we choose to skip there blocks when we calculate the liferange366  // for each alloca. It should be reasonable since there shouldn't be uses367  // in these blocks and the coroutine frame shouldn't be used outside the368  // coroutine body.369  //370  // Note that the user of coro.suspend may not be SwitchInst. However, this371  // case seems too complex to handle. And it is harmless to skip these372  // patterns since it just prevend putting the allocas to live in the same373  // slot.374  DenseMap<SwitchInst *, BasicBlock *> DefaultSuspendDest;375  for (auto *CoroSuspendInst : Shape.CoroSuspends) {376    for (auto *U : CoroSuspendInst->users()) {377      if (auto *ConstSWI = dyn_cast<SwitchInst>(U)) {378        auto *SWI = const_cast<SwitchInst *>(ConstSWI);379        DefaultSuspendDest[SWI] = SWI->getDefaultDest();380        SWI->setDefaultDest(SWI->getSuccessor(1));381      }382    }383  }384 385  auto ExtractAllocas = [&]() {386    AllocaSetType Allocas;387    Allocas.reserve(FrameData.Allocas.size());388    for (const auto &A : FrameData.Allocas)389      Allocas.push_back(A.Alloca);390    return Allocas;391  };392  StackLifetime StackLifetimeAnalyzer(F, ExtractAllocas(),393                                      StackLifetime::LivenessType::May);394  StackLifetimeAnalyzer.run();395  auto DoAllocasInterfere = [&](const AllocaInst *AI1, const AllocaInst *AI2) {396    return StackLifetimeAnalyzer.getLiveRange(AI1).overlaps(397        StackLifetimeAnalyzer.getLiveRange(AI2));398  };399  auto GetAllocaSize = [&](const coro::AllocaInfo &A) -> uint64_t {400    std::optional<TypeSize> RetSize = A.Alloca->getAllocationSize(DL);401    assert(RetSize && "Variable Length Arrays (VLA) are not supported.\n");402    assert(!RetSize->isScalable() && "Scalable vectors are not yet supported");403    // A dynamically sized alloca has no statically known size, so404    // getAllocationSize() returns std::nullopt. Such an alloca must not reach405    // here -- collectFrameAlloca() keeps it off the frame (or fails loudly) --406    // but never dereference the empty optional even in a no-assertions build:407    // doing so reads uninitialized memory and makes this comparator408    // non-deterministic, which is undefined behavior for the sort below and409    // corrupts the frame layout (observed as a SIGSEGV). Sort it first410    // deterministically so addFieldForAlloca's never-silent "non static411    // allocas" fatal fires instead of crashing.412    if (!RetSize)413      return std::numeric_limits<uint64_t>::max();414    return RetSize->getFixedValue();415  };416  // Put larger allocas in the front. So the larger allocas have higher417  // priority to merge, which can save more space potentially. Also each418  // AllocaSet would be ordered. So we can get the largest Alloca in one419  // AllocaSet easily.420  sort(FrameData.Allocas, [&](const auto &Iter1, const auto &Iter2) {421    return GetAllocaSize(Iter1) > GetAllocaSize(Iter2);422  });423  for (const auto &A : FrameData.Allocas) {424    AllocaInst *Alloca = A.Alloca;425    bool Merged = false;426    // Try to find if the Alloca does not interfere with any existing427    // NonOverlappedAllocaSet. If it is true, insert the alloca to that428    // NonOverlappedAllocaSet.429    for (auto &AllocaSet : NonOverlapedAllocas) {430      assert(!AllocaSet.empty() && "Processing Alloca Set is not empty.\n");431      bool NoInterference = none_of(AllocaSet, [&](auto Iter) {432        return DoAllocasInterfere(Alloca, Iter);433      });434      // If the alignment of A is multiple of the alignment of B, the address435      // of A should satisfy the requirement for aligning for B.436      //437      // There may be other more fine-grained strategies to handle the alignment438      // infomation during the merging process. But it seems hard to handle439      // these strategies and benefit little.440      bool Alignable = [&]() -> bool {441        auto *LargestAlloca = *AllocaSet.begin();442        return LargestAlloca->getAlign().value() % Alloca->getAlign().value() ==443               0;444      }();445      bool CouldMerge = NoInterference && Alignable;446      if (!CouldMerge)447        continue;448      AllocaSet.push_back(Alloca);449      Merged = true;450      break;451    }452    if (!Merged) {453      NonOverlapedAllocas.emplace_back(AllocaSetType(1, Alloca));454    }455  }456  // Recover the default target destination for each Switch statement457  // reserved.458  for (auto SwitchAndDefaultDest : DefaultSuspendDest) {459    SwitchInst *SWI = SwitchAndDefaultDest.first;460    BasicBlock *DestBB = SwitchAndDefaultDest.second;461    SWI->setDefaultDest(DestBB);462  }463  // This Debug Info could tell us which allocas are merged into one slot.464  LLVM_DEBUG(for (auto &AllocaSet465                  : NonOverlapedAllocas) {466    if (AllocaSet.size() > 1) {467      dbgs() << "In Function:" << F.getName() << "\n";468      dbgs() << "Find Union Set "469             << "\n";470      dbgs() << "\tAllocas are \n";471      for (auto Alloca : AllocaSet)472        dbgs() << "\t\t" << *Alloca << "\n";473    }474  });475}476 477StructType *FrameTypeBuilder::finish(StringRef Name) {478  assert(!IsFinished && "already finished!");479 480  // Prepare the optimal-layout field array.481  // The Id in the layout field is a pointer to our Field for it.482  SmallVector<OptimizedStructLayoutField, 8> LayoutFields;483  LayoutFields.reserve(Fields.size());484  for (auto &Field : Fields) {485    LayoutFields.emplace_back(&Field, Field.Size, Field.Alignment,486                              Field.Offset);487  }488 489  // Perform layout.490  auto SizeAndAlign = performOptimizedStructLayout(LayoutFields);491  StructSize = SizeAndAlign.first;492  StructAlign = SizeAndAlign.second;493 494  auto getField = [](const OptimizedStructLayoutField &LayoutField) -> Field & {495    return *static_cast<Field *>(const_cast<void*>(LayoutField.Id));496  };497 498  // We need to produce a packed struct type if there's a field whose499  // assigned offset isn't a multiple of its natural type alignment.500  bool Packed = [&] {501    for (auto &LayoutField : LayoutFields) {502      auto &F = getField(LayoutField);503      if (!isAligned(F.TyAlignment, LayoutField.Offset))504        return true;505    }506    return false;507  }();508 509  // Build the struct body.510  SmallVector<Type*, 16> FieldTypes;511  FieldTypes.reserve(LayoutFields.size() * 3 / 2);512  uint64_t LastOffset = 0;513  for (auto &LayoutField : LayoutFields) {514    auto &F = getField(LayoutField);515 516    auto Offset = LayoutField.Offset;517 518    // Add a padding field if there's a padding gap and we're either519    // building a packed struct or the padding gap is more than we'd520    // get from aligning to the field type's natural alignment.521    assert(Offset >= LastOffset);522    if (Offset != LastOffset) {523      if (Packed || alignTo(LastOffset, F.TyAlignment) != Offset)524        FieldTypes.push_back(ArrayType::get(Type::getInt8Ty(Context),525                                            Offset - LastOffset));526    }527 528    F.Offset = Offset;529    F.LayoutFieldIndex = FieldTypes.size();530 531    FieldTypes.push_back(F.Ty);532    if (F.DynamicAlignBuffer) {533      FieldTypes.push_back(534          ArrayType::get(Type::getInt8Ty(Context), F.DynamicAlignBuffer));535    }536    LastOffset = Offset + F.Size;537  }538 539  StructType *Ty = StructType::create(Context, FieldTypes, Name, Packed);540 541#ifndef NDEBUG542  // Check that the IR layout matches the offsets we expect.543  auto Layout = DL.getStructLayout(Ty);544  for (auto &F : Fields) {545    assert(Ty->getElementType(F.LayoutFieldIndex) == F.Ty);546    assert(Layout->getElementOffset(F.LayoutFieldIndex) == F.Offset);547  }548#endif549 550  IsFinished = true;551 552  return Ty;553}554 555static void cacheDIVar(FrameDataInfo &FrameData,556                       DenseMap<Value *, DILocalVariable *> &DIVarCache) {557  for (auto *V : FrameData.getAllDefs()) {558    if (DIVarCache.contains(V))559      continue;560 561    auto CacheIt = [&DIVarCache, V](const auto &Container) {562      auto *I = llvm::find_if(Container, [](auto *DDI) {563        return DDI->getExpression()->getNumElements() == 0;564      });565      if (I != Container.end())566        DIVarCache.insert({V, (*I)->getVariable()});567    };568    CacheIt(findDVRDeclares(V));569    CacheIt(findDVRDeclareValues(V));570  }571}572 573/// Create name for Type. It uses MDString to store new created string to574/// avoid memory leak.575static StringRef solveTypeName(Type *Ty) {576  if (Ty->isIntegerTy()) {577    // The longest name in common may be '__int_128', which has 9 bits.578    SmallString<16> Buffer;579    raw_svector_ostream OS(Buffer);580    OS << "__int_" << cast<IntegerType>(Ty)->getBitWidth();581    auto *MDName = MDString::get(Ty->getContext(), OS.str());582    return MDName->getString();583  }584 585  if (Ty->isFloatingPointTy()) {586    if (Ty->isFloatTy())587      return "__float_";588    if (Ty->isDoubleTy())589      return "__double_";590    return "__floating_type_";591  }592 593  if (Ty->isPointerTy())594    return "PointerType";595 596  if (Ty->isStructTy()) {597    if (!cast<StructType>(Ty)->hasName())598      return "__LiteralStructType_";599 600    auto Name = Ty->getStructName();601 602    SmallString<16> Buffer(Name);603    for (auto &Iter : Buffer)604      if (Iter == '.' || Iter == ':')605        Iter = '_';606    auto *MDName = MDString::get(Ty->getContext(), Buffer.str());607    return MDName->getString();608  }609 610  return "UnknownType";611}612 613static DIType *solveDIType(DIBuilder &Builder, Type *Ty,614                           const DataLayout &Layout, DIScope *Scope,615                           unsigned LineNum,616                           DenseMap<Type *, DIType *> &DITypeCache) {617  if (DIType *DT = DITypeCache.lookup(Ty))618    return DT;619 620  StringRef Name = solveTypeName(Ty);621 622  DIType *RetType = nullptr;623 624  if (Ty->isIntegerTy()) {625    auto BitWidth = cast<IntegerType>(Ty)->getBitWidth();626    RetType = Builder.createBasicType(Name, BitWidth, dwarf::DW_ATE_signed,627                                      llvm::DINode::FlagArtificial);628  } else if (Ty->isFloatingPointTy()) {629    RetType = Builder.createBasicType(Name, Layout.getTypeSizeInBits(Ty),630                                      dwarf::DW_ATE_float,631                                      llvm::DINode::FlagArtificial);632  } else if (Ty->isPointerTy()) {633    // Construct PointerType points to null (aka void *) instead of exploring634    // pointee type to avoid infinite search problem. For example, we would be635    // in trouble if we traverse recursively:636    //637    //  struct Node {638    //      Node* ptr;639    //  };640    RetType =641        Builder.createPointerType(nullptr, Layout.getTypeSizeInBits(Ty),642                                  Layout.getABITypeAlign(Ty).value() * CHAR_BIT,643                                  /*DWARFAddressSpace=*/std::nullopt, Name);644  } else if (Ty->isStructTy()) {645    auto *DIStruct = Builder.createStructType(646        Scope, Name, Scope->getFile(), LineNum, Layout.getTypeSizeInBits(Ty),647        Layout.getPrefTypeAlign(Ty).value() * CHAR_BIT,648        llvm::DINode::FlagArtificial, nullptr, llvm::DINodeArray());649 650    auto *StructTy = cast<StructType>(Ty);651    SmallVector<Metadata *, 16> Elements;652    for (unsigned I = 0; I < StructTy->getNumElements(); I++) {653      DIType *DITy = solveDIType(Builder, StructTy->getElementType(I), Layout,654                                 DIStruct, LineNum, DITypeCache);655      assert(DITy);656      Elements.push_back(Builder.createMemberType(657          DIStruct, DITy->getName(), DIStruct->getFile(), LineNum,658          DITy->getSizeInBits(), DITy->getAlignInBits(),659          Layout.getStructLayout(StructTy)->getElementOffsetInBits(I),660          llvm::DINode::FlagArtificial, DITy));661    }662 663    Builder.replaceArrays(DIStruct, Builder.getOrCreateArray(Elements));664 665    RetType = DIStruct;666  } else {667    LLVM_DEBUG(dbgs() << "Unresolved Type: " << *Ty << "\n");668    TypeSize Size = Layout.getTypeSizeInBits(Ty);669    auto *CharSizeType = Builder.createBasicType(670        Name, 8, dwarf::DW_ATE_unsigned_char, llvm::DINode::FlagArtificial);671 672    if (Size <= 8)673      RetType = CharSizeType;674    else {675      if (Size % 8 != 0)676        Size = TypeSize::getFixed(Size + 8 - (Size % 8));677 678      RetType = Builder.createArrayType(679          Size, Layout.getPrefTypeAlign(Ty).value(), CharSizeType,680          Builder.getOrCreateArray(Builder.getOrCreateSubrange(0, Size / 8)));681    }682  }683 684  DITypeCache.insert({Ty, RetType});685  return RetType;686}687 688/// Build artificial debug info for C++ coroutine frames to allow users to689/// inspect the contents of the frame directly690///691/// Create Debug information for coroutine frame with debug name "__coro_frame".692/// The debug information for the fields of coroutine frame is constructed from693/// the following way:694/// 1. For all the value in the Frame, we search the use of dbg.declare to find695///    the corresponding debug variables for the value. If we can find the696///    debug variable, we can get full and accurate debug information.697/// 2. If we can't get debug information in step 1 and 2, we could only try to698///    build the DIType by Type. We did this in solveDIType. We only handle699///    integer, float, double, integer type and struct type for now.700static void buildFrameDebugInfo(Function &F, coro::Shape &Shape,701                                FrameDataInfo &FrameData) {702  DISubprogram *DIS = F.getSubprogram();703  // If there is no DISubprogram for F, it implies the function is compiled704  // without debug info. So we also don't generate debug info for the frame.705 706  if (!DIS || !DIS->getUnit())707    return;708 709  if (!dwarf::isCPlusPlus(static_cast<llvm::dwarf::SourceLanguage>(710          DIS->getUnit()->getSourceLanguage().getUnversionedName())) ||711      DIS->getUnit()->getEmissionKind() !=712          DICompileUnit::DebugEmissionKind::FullDebug)713    return;714 715  assert(Shape.ABI == coro::ABI::Switch &&716         "We could only build debug infomation for C++ coroutine now.\n");717 718  DIBuilder DBuilder(*F.getParent(), /*AllowUnresolved*/ false);719 720  DIFile *DFile = DIS->getFile();721  unsigned LineNum = DIS->getLine();722 723  DICompositeType *FrameDITy = DBuilder.createStructType(724      DIS->getUnit(), Twine(F.getName() + ".coro_frame_ty").str(),725      DFile, LineNum, Shape.FrameSize * 8,726      Shape.FrameAlign.value() * 8, llvm::DINode::FlagArtificial, nullptr,727      llvm::DINodeArray());728  StructType *FrameTy = Shape.FrameTy;729  SmallVector<Metadata *, 16> Elements;730  DataLayout Layout = F.getDataLayout();731 732  DenseMap<Value *, DILocalVariable *> DIVarCache;733  cacheDIVar(FrameData, DIVarCache);734 735  unsigned ResumeIndex = coro::Shape::SwitchFieldIndex::Resume;736  unsigned DestroyIndex = coro::Shape::SwitchFieldIndex::Destroy;737  unsigned IndexIndex = Shape.SwitchLowering.IndexField;738 739  DenseMap<unsigned, StringRef> NameCache;740  NameCache.insert({ResumeIndex, "__resume_fn"});741  NameCache.insert({DestroyIndex, "__destroy_fn"});742  NameCache.insert({IndexIndex, "__coro_index"});743 744  Type *ResumeFnTy = FrameTy->getElementType(ResumeIndex),745       *DestroyFnTy = FrameTy->getElementType(DestroyIndex),746       *IndexTy = FrameTy->getElementType(IndexIndex);747 748  DenseMap<unsigned, DIType *> TyCache;749  TyCache.insert(750      {ResumeIndex, DBuilder.createPointerType(751                        nullptr, Layout.getTypeSizeInBits(ResumeFnTy))});752  TyCache.insert(753      {DestroyIndex, DBuilder.createPointerType(754                         nullptr, Layout.getTypeSizeInBits(DestroyFnTy))});755 756  /// FIXME: If we fill the field `SizeInBits` with the actual size of757  /// __coro_index in bits, then __coro_index wouldn't show in the debugger.758  TyCache.insert({IndexIndex, DBuilder.createBasicType(759                                  "__coro_index",760                                  (Layout.getTypeSizeInBits(IndexTy) < 8)761                                      ? 8762                                      : Layout.getTypeSizeInBits(IndexTy),763                                  dwarf::DW_ATE_unsigned_char)});764 765  for (auto *V : FrameData.getAllDefs()) {766    auto It = DIVarCache.find(V);767    if (It == DIVarCache.end())768      continue;769 770    auto Index = FrameData.getFieldIndex(V);771 772    NameCache.insert({Index, It->second->getName()});773    TyCache.insert({Index, It->second->getType()});774  }775 776  // Cache from index to (Align, Offset Pair)777  DenseMap<unsigned, std::pair<unsigned, unsigned>> OffsetCache;778  // The Align and Offset of Resume function and Destroy function are fixed.779  OffsetCache.insert({ResumeIndex, {8, 0}});780  OffsetCache.insert({DestroyIndex, {8, 8}});781  OffsetCache.insert(782      {IndexIndex,783       {Shape.SwitchLowering.IndexAlign, Shape.SwitchLowering.IndexOffset}});784 785  for (auto *V : FrameData.getAllDefs()) {786    auto Index = FrameData.getFieldIndex(V);787 788    OffsetCache.insert(789        {Index, {FrameData.getAlign(V).value(), FrameData.getOffset(V)}});790  }791 792  DenseMap<Type *, DIType *> DITypeCache;793  // This counter is used to avoid same type names. e.g., there would be794  // many i32 and i64 types in one coroutine. And we would use i32_0 and795  // i32_1 to avoid the same type. Since it makes no sense the name of the796  // fields confilicts with each other.797  unsigned UnknownTypeNum = 0;798  for (unsigned Index = 0; Index < FrameTy->getNumElements(); Index++) {799    auto OCIt = OffsetCache.find(Index);800    if (OCIt == OffsetCache.end())801      continue;802 803    std::string Name;804    uint64_t SizeInBits;805    uint32_t AlignInBits;806    uint64_t OffsetInBits;807    DIType *DITy = nullptr;808 809    Type *Ty = FrameTy->getElementType(Index);810    assert(Ty->isSized() && "We can't handle type which is not sized.\n");811    SizeInBits = Layout.getTypeSizeInBits(Ty).getFixedValue();812    AlignInBits = OCIt->second.first * 8;813    OffsetInBits = OCIt->second.second * 8;814 815    if (auto It = NameCache.find(Index); It != NameCache.end()) {816      Name = It->second.str();817      DITy = TyCache[Index];818    } else {819      DITy = solveDIType(DBuilder, Ty, Layout, FrameDITy, LineNum, DITypeCache);820      assert(DITy && "SolveDIType shouldn't return nullptr.\n");821      Name = DITy->getName().str();822      Name += "_" + std::to_string(UnknownTypeNum);823      UnknownTypeNum++;824    }825 826    Elements.push_back(DBuilder.createMemberType(827        FrameDITy, Name, DFile, LineNum, SizeInBits, AlignInBits, OffsetInBits,828        llvm::DINode::FlagArtificial, DITy));829  }830 831  DBuilder.replaceArrays(FrameDITy, DBuilder.getOrCreateArray(Elements));832 833  auto *FrameDIVar =834      DBuilder.createAutoVariable(DIS, "__coro_frame", DFile, LineNum,835                                  FrameDITy, true, DINode::FlagArtificial);836 837  // Subprogram would have ContainedNodes field which records the debug838  // variables it contained. So we need to add __coro_frame to the839  // ContainedNodes of it.840  //841  // If we don't add __coro_frame to the RetainedNodes, user may get842  // `no symbol __coro_frame in context` rather than `__coro_frame`843  // is optimized out, which is more precise.844  auto RetainedNodes = DIS->getRetainedNodes();845  SmallVector<Metadata *, 32> RetainedNodesVec(RetainedNodes.begin(),846                                               RetainedNodes.end());847  RetainedNodesVec.push_back(FrameDIVar);848  DIS->replaceOperandWith(7, (MDTuple::get(F.getContext(), RetainedNodesVec)));849 850  // Construct the location for the frame debug variable. The column number851  // is fake but it should be fine.852  DILocation *DILoc =853      DILocation::get(DIS->getContext(), LineNum, /*Column=*/1, DIS);854  assert(FrameDIVar->isValidLocationForIntrinsic(DILoc));855 856  DbgVariableRecord *NewDVR =857      new DbgVariableRecord(ValueAsMetadata::get(Shape.FramePtr), FrameDIVar,858                            DBuilder.createExpression(), DILoc,859                            DbgVariableRecord::LocationType::Declare);860  BasicBlock::iterator It = Shape.getInsertPtAfterFramePtr();861  It->getParent()->insertDbgRecordBefore(NewDVR, It);862}863 864// Build a struct that will keep state for an active coroutine.865//   struct f.frame {866//     ResumeFnTy ResumeFnAddr;867//     ResumeFnTy DestroyFnAddr;868//     ... promise (if present) ...869//     int ResumeIndex;870//     ... spills ...871//   };872static StructType *buildFrameType(Function &F, coro::Shape &Shape,873                                  FrameDataInfo &FrameData,874                                  bool OptimizeFrame) {875  LLVMContext &C = F.getContext();876  const DataLayout &DL = F.getDataLayout();877 878  // We will use this value to cap the alignment of spilled values.879  std::optional<Align> MaxFrameAlignment;880  if (Shape.ABI == coro::ABI::Async)881    MaxFrameAlignment = Shape.AsyncLowering.getContextAlignment();882  FrameTypeBuilder B(C, DL, MaxFrameAlignment);883 884  AllocaInst *PromiseAlloca = Shape.getPromiseAlloca();885  std::optional<FieldIDType> SwitchIndexFieldId;886 887  if (Shape.ABI == coro::ABI::Switch) {888    auto *FnPtrTy = PointerType::getUnqual(C);889 890    // Add header fields for the resume and destroy functions.891    // We can rely on these being perfectly packed.892    (void)B.addField(FnPtrTy, std::nullopt, /*header*/ true);893    (void)B.addField(FnPtrTy, std::nullopt, /*header*/ true);894 895    // PromiseAlloca field needs to be explicitly added here because it's896    // a header field with a fixed offset based on its alignment. Hence it897    // needs special handling and cannot be added to FrameData.Allocas.898    if (PromiseAlloca)899      FrameData.setFieldIndex(900          PromiseAlloca, B.addFieldForAlloca(PromiseAlloca, /*header*/ true));901 902    // Add a field to store the suspend index.  This doesn't need to903    // be in the header.904    unsigned IndexBits = std::max(1U, Log2_64_Ceil(Shape.CoroSuspends.size()));905    Type *IndexType = Type::getIntNTy(C, IndexBits);906 907    SwitchIndexFieldId = B.addField(IndexType, std::nullopt);908  } else {909    assert(PromiseAlloca == nullptr && "lowering doesn't support promises");910  }911 912  // Because multiple allocas may own the same field slot,913  // we add allocas to field here.914  B.addFieldForAllocas(F, FrameData, Shape, OptimizeFrame);915  // Add PromiseAlloca to Allocas list so that916  // 1. updateLayoutIndex could update its index after917  // `performOptimizedStructLayout`918  // 2. it is processed in insertSpills.919  if (Shape.ABI == coro::ABI::Switch && PromiseAlloca)920    // We assume that the promise alloca won't be modified before921    // CoroBegin and no alias will be create before CoroBegin.922    FrameData.Allocas.emplace_back(923        PromiseAlloca, DenseMap<Instruction *, std::optional<APInt>>{}, false);924  // Create an entry for every spilled value.925  for (auto &S : FrameData.Spills) {926    Type *FieldType = S.first->getType();927    MaybeAlign MA;928    // For byval arguments, we need to store the pointed value in the frame,929    // instead of the pointer itself.930    if (const Argument *A = dyn_cast<Argument>(S.first)) {931      if (A->hasByValAttr()) {932        FieldType = A->getParamByValType();933        MA = A->getParamAlign();934      }935    }936    FieldIDType Id =937        B.addField(FieldType, MA, false /*header*/, true /*IsSpillOfValue*/);938    FrameData.setFieldIndex(S.first, Id);939  }940 941  StructType *FrameTy = [&] {942    SmallString<32> Name(F.getName());943    Name.append(".Frame");944    return B.finish(Name);945  }();946 947  FrameData.updateLayoutIndex(B);948  Shape.FrameAlign = B.getStructAlign();949  Shape.FrameSize = B.getStructSize();950 951  switch (Shape.ABI) {952  case coro::ABI::Switch: {953    // In the switch ABI, remember the switch-index field.954    auto IndexField = B.getLayoutField(*SwitchIndexFieldId);955    Shape.SwitchLowering.IndexField = IndexField.LayoutFieldIndex;956    Shape.SwitchLowering.IndexAlign = IndexField.Alignment.value();957    Shape.SwitchLowering.IndexOffset = IndexField.Offset;958 959    // Also round the frame size up to a multiple of its alignment, as is960    // generally expected in C/C++.961    Shape.FrameSize = alignTo(Shape.FrameSize, Shape.FrameAlign);962    break;963  }964 965  // In the retcon ABI, remember whether the frame is inline in the storage.966  case coro::ABI::Retcon:967  case coro::ABI::RetconOnce: {968    auto Id = Shape.getRetconCoroId();969    Shape.RetconLowering.IsFrameInlineInStorage970      = (B.getStructSize() <= Id->getStorageSize() &&971         B.getStructAlign() <= Id->getStorageAlignment());972    break;973  }974  case coro::ABI::Async: {975    Shape.AsyncLowering.FrameOffset =976        alignTo(Shape.AsyncLowering.ContextHeaderSize, Shape.FrameAlign);977    // Also make the final context size a multiple of the context alignment to978    // make allocation easier for allocators.979    Shape.AsyncLowering.ContextSize =980        alignTo(Shape.AsyncLowering.FrameOffset + Shape.FrameSize,981                Shape.AsyncLowering.getContextAlignment());982    if (Shape.AsyncLowering.getContextAlignment() < Shape.FrameAlign) {983      report_fatal_error(984          "The alignment requirment of frame variables cannot be higher than "985          "the alignment of the async function context");986    }987    break;988  }989  }990 991  return FrameTy;992}993 994// Replace all alloca and SSA values that are accessed across suspend points995// with GetElementPointer from coroutine frame + loads and stores. Create an996// AllocaSpillBB that will become the new entry block for the resume parts of997// the coroutine:998//999//    %hdl = coro.begin(...)1000//    whatever1001//1002// becomes:1003//1004//    %hdl = coro.begin(...)1005//    br label %AllocaSpillBB1006//1007//  AllocaSpillBB:1008//    ; geps corresponding to allocas that were moved to coroutine frame1009//    br label PostSpill1010//1011//  PostSpill:1012//    whatever1013//1014//1015static void insertSpills(const FrameDataInfo &FrameData, coro::Shape &Shape) {1016  LLVMContext &C = Shape.CoroBegin->getContext();1017  Function *F = Shape.CoroBegin->getFunction();1018  IRBuilder<> Builder(C);1019  StructType *FrameTy = Shape.FrameTy;1020  Value *FramePtr = Shape.FramePtr;1021  DominatorTree DT(*F);1022  SmallDenseMap<Argument *, AllocaInst *, 4> ArgToAllocaMap;1023 1024  // Create a GEP with the given index into the coroutine frame for the original1025  // value Orig. Appends an extra 0 index for array-allocas, preserving the1026  // original type.1027  auto GetFramePointer = [&](Value *Orig) -> Value * {1028    FieldIDType Index = FrameData.getFieldIndex(Orig);1029    SmallVector<Value *, 3> Indices = {1030        ConstantInt::get(Type::getInt32Ty(C), 0),1031        ConstantInt::get(Type::getInt32Ty(C), Index),1032    };1033 1034    if (auto *AI = dyn_cast<AllocaInst>(Orig)) {1035      if (auto *CI = dyn_cast<ConstantInt>(AI->getArraySize())) {1036        auto Count = CI->getValue().getZExtValue();1037        if (Count > 1) {1038          Indices.push_back(ConstantInt::get(Type::getInt32Ty(C), 0));1039        }1040      } else {1041        report_fatal_error("Coroutines cannot handle non static allocas yet");1042      }1043    }1044 1045    auto GEP = cast<GetElementPtrInst>(1046        Builder.CreateInBoundsGEP(FrameTy, FramePtr, Indices));1047    if (auto *AI = dyn_cast<AllocaInst>(Orig)) {1048      if (FrameData.getDynamicAlign(Orig) != 0) {1049        assert(FrameData.getDynamicAlign(Orig) == AI->getAlign().value());1050        auto *M = AI->getModule();1051        auto *IntPtrTy = M->getDataLayout().getIntPtrType(AI->getType());1052        auto *PtrValue = Builder.CreatePtrToInt(GEP, IntPtrTy);1053        auto *AlignMask =1054            ConstantInt::get(IntPtrTy, AI->getAlign().value() - 1);1055        PtrValue = Builder.CreateAdd(PtrValue, AlignMask);1056        PtrValue = Builder.CreateAnd(PtrValue, Builder.CreateNot(AlignMask));1057        return Builder.CreateIntToPtr(PtrValue, AI->getType());1058      }1059      // If the type of GEP is not equal to the type of AllocaInst, it implies1060      // that the AllocaInst may be reused in the Frame slot of other1061      // AllocaInst. So We cast GEP to the AllocaInst here to re-use1062      // the Frame storage.1063      //1064      // Note: If we change the strategy dealing with alignment, we need to refine1065      // this casting.1066      if (GEP->getType() != Orig->getType())1067        return Builder.CreateAddrSpaceCast(GEP, Orig->getType(),1068                                           Orig->getName() + Twine(".cast"));1069    }1070    return GEP;1071  };1072 1073  for (auto const &E : FrameData.Spills) {1074    Value *Def = E.first;1075    auto SpillAlignment = Align(FrameData.getAlign(Def));1076    // Create a store instruction storing the value into the1077    // coroutine frame.1078    BasicBlock::iterator InsertPt = coro::getSpillInsertionPt(Shape, Def, DT);1079 1080    Type *ByValTy = nullptr;1081    if (auto *Arg = dyn_cast<Argument>(Def)) {1082      // If we're spilling an Argument, make sure we clear 'captures'1083      // from the coroutine function.1084      Arg->getParent()->removeParamAttr(Arg->getArgNo(), Attribute::Captures);1085 1086      if (Arg->hasByValAttr())1087        ByValTy = Arg->getParamByValType();1088    }1089 1090    auto Index = FrameData.getFieldIndex(Def);1091    Builder.SetInsertPoint(InsertPt->getParent(), InsertPt);1092    auto *G = Builder.CreateConstInBoundsGEP2_32(1093        FrameTy, FramePtr, 0, Index, Def->getName() + Twine(".spill.addr"));1094    if (ByValTy) {1095      // For byval arguments, we need to store the pointed value in the frame,1096      // instead of the pointer itself.1097      auto *Value = Builder.CreateLoad(ByValTy, Def);1098      Builder.CreateAlignedStore(Value, G, SpillAlignment);1099    } else {1100      Builder.CreateAlignedStore(Def, G, SpillAlignment);1101    }1102 1103    BasicBlock *CurrentBlock = nullptr;1104    Value *CurrentReload = nullptr;1105    for (auto *U : E.second) {1106      // If we have not seen the use block, create a load instruction to reload1107      // the spilled value from the coroutine frame. Populates the Value pointer1108      // reference provided with the frame GEP.1109      if (CurrentBlock != U->getParent()) {1110        CurrentBlock = U->getParent();1111        Builder.SetInsertPoint(CurrentBlock,1112                               CurrentBlock->getFirstInsertionPt());1113 1114        auto *GEP = GetFramePointer(E.first);1115        GEP->setName(E.first->getName() + Twine(".reload.addr"));1116        if (ByValTy)1117          CurrentReload = GEP;1118        else1119          CurrentReload = Builder.CreateAlignedLoad(1120              FrameTy->getElementType(FrameData.getFieldIndex(E.first)), GEP,1121              SpillAlignment, E.first->getName() + Twine(".reload"));1122 1123        TinyPtrVector<DbgVariableRecord *> DVRs = findDVRDeclares(Def);1124        // Try best to find dbg.declare. If the spill is a temp, there may not1125        // be a direct dbg.declare. Walk up the load chain to find one from an1126        // alias.1127        if (F->getSubprogram()) {1128          auto *CurDef = Def;1129          while (DVRs.empty() && isa<LoadInst>(CurDef)) {1130            auto *LdInst = cast<LoadInst>(CurDef);1131            // Only consider ptr to ptr same type load.1132            if (LdInst->getPointerOperandType() != LdInst->getType())1133              break;1134            CurDef = LdInst->getPointerOperand();1135            if (!isa<AllocaInst, LoadInst>(CurDef))1136              break;1137            DVRs = findDVRDeclares(CurDef);1138          }1139        }1140 1141        auto SalvageOne = [&](DbgVariableRecord *DDI) {1142          // This dbg.declare is preserved for all coro-split function1143          // fragments. It will be unreachable in the main function, and1144          // processed by coro::salvageDebugInfo() by the Cloner.1145          DbgVariableRecord *NewDVR = new DbgVariableRecord(1146              ValueAsMetadata::get(CurrentReload), DDI->getVariable(),1147              DDI->getExpression(), DDI->getDebugLoc(),1148              DbgVariableRecord::LocationType::Declare);1149          Builder.GetInsertPoint()->getParent()->insertDbgRecordBefore(1150              NewDVR, Builder.GetInsertPoint());1151          // This dbg.declare is for the main function entry point.  It1152          // will be deleted in all coro-split functions.1153          coro::salvageDebugInfo(ArgToAllocaMap, *DDI, false /*UseEntryValue*/);1154        };1155        for_each(DVRs, SalvageOne);1156      }1157 1158      TinyPtrVector<DbgVariableRecord *> DVRDeclareValues =1159          findDVRDeclareValues(Def);1160      // Try best to find dbg.declare_value. If the spill is a temp, there may1161      // not be a direct dbg.declare_value. Walk up the load chain to find one1162      // from an alias.1163      if (F->getSubprogram()) {1164        auto *CurDef = Def;1165        while (DVRDeclareValues.empty() && isa<LoadInst>(CurDef)) {1166          auto *LdInst = cast<LoadInst>(CurDef);1167          // Only consider ptr to ptr same type load.1168          if (LdInst->getPointerOperandType() != LdInst->getType())1169            break;1170          CurDef = LdInst->getPointerOperand();1171          if (!isa<AllocaInst, LoadInst>(CurDef))1172            break;1173          DVRDeclareValues = findDVRDeclareValues(CurDef);1174        }1175      }1176 1177      auto SalvageOneCoro = [&](auto *DDI) {1178        // This dbg.declare_value is preserved for all coro-split function1179        // fragments. It will be unreachable in the main function, and1180        // processed by coro::salvageDebugInfo() by the Cloner. However, convert1181        // it to a dbg.declare to make sure future passes don't have to deal1182        // with a dbg.declare_value.1183        auto *VAM = ValueAsMetadata::get(CurrentReload);1184        Type *Ty = VAM->getValue()->getType();1185        // If the metadata type is not a pointer, emit a dbg.value instead.1186        DbgVariableRecord *NewDVR = new DbgVariableRecord(1187            ValueAsMetadata::get(CurrentReload), DDI->getVariable(),1188            DDI->getExpression(), DDI->getDebugLoc(),1189            Ty->isPointerTy() ? DbgVariableRecord::LocationType::Declare1190                              : DbgVariableRecord::LocationType::Value);1191        Builder.GetInsertPoint()->getParent()->insertDbgRecordBefore(1192            NewDVR, Builder.GetInsertPoint());1193        // This dbg.declare_value is for the main function entry point.  It1194        // will be deleted in all coro-split functions.1195        coro::salvageDebugInfo(ArgToAllocaMap, *DDI, false /*UseEntryValue*/);1196      };1197      for_each(DVRDeclareValues, SalvageOneCoro);1198 1199      // If we have a single edge PHINode, remove it and replace it with a1200      // reload from the coroutine frame. (We already took care of multi edge1201      // PHINodes by normalizing them in the rewritePHIs function).1202      if (auto *PN = dyn_cast<PHINode>(U)) {1203        assert(PN->getNumIncomingValues() == 1 &&1204               "unexpected number of incoming "1205               "values in the PHINode");1206        PN->replaceAllUsesWith(CurrentReload);1207        PN->eraseFromParent();1208        continue;1209      }1210 1211      // Replace all uses of CurrentValue in the current instruction with1212      // reload.1213      U->replaceUsesOfWith(Def, CurrentReload);1214      // Instructions are added to Def's user list if the attached1215      // debug records use Def. Update those now.1216      for (DbgVariableRecord &DVR : filterDbgVars(U->getDbgRecordRange()))1217        DVR.replaceVariableLocationOp(Def, CurrentReload, true);1218    }1219  }1220 1221  BasicBlock *FramePtrBB = Shape.getInsertPtAfterFramePtr()->getParent();1222 1223  auto SpillBlock = FramePtrBB->splitBasicBlock(1224      Shape.getInsertPtAfterFramePtr(), "AllocaSpillBB");1225  SpillBlock->splitBasicBlock(&SpillBlock->front(), "PostSpill");1226  Shape.AllocaSpillBlock = SpillBlock;1227 1228  // retcon and retcon.once lowering assumes all uses have been sunk.1229  if (Shape.ABI == coro::ABI::Retcon || Shape.ABI == coro::ABI::RetconOnce ||1230      Shape.ABI == coro::ABI::Async) {1231    // If we found any allocas, replace all of their remaining uses with Geps.1232    Builder.SetInsertPoint(SpillBlock, SpillBlock->begin());1233    for (const auto &P : FrameData.Allocas) {1234      AllocaInst *Alloca = P.Alloca;1235      auto *G = GetFramePointer(Alloca);1236 1237      // Remove any lifetime intrinsics, now that these are no longer allocas.1238      for (User *U : make_early_inc_range(Alloca->users())) {1239        auto *I = cast<Instruction>(U);1240        if (I->isLifetimeStartOrEnd())1241          I->eraseFromParent();1242      }1243 1244      // We are not using ReplaceInstWithInst(P.first, cast<Instruction>(G))1245      // here, as we are changing location of the instruction.1246      G->takeName(Alloca);1247      Alloca->replaceAllUsesWith(G);1248      Alloca->eraseFromParent();1249    }1250    return;1251  }1252 1253  // If we found any alloca, replace all of their remaining uses with GEP1254  // instructions. To remain debugbility, we replace the uses of allocas for1255  // dbg.declares and dbg.values with the reload from the frame.1256  // Note: We cannot replace the alloca with GEP instructions indiscriminately,1257  // as some of the uses may not be dominated by CoroBegin.1258  Builder.SetInsertPoint(Shape.AllocaSpillBlock,1259                         Shape.AllocaSpillBlock->begin());1260  SmallVector<Instruction *, 4> UsersToUpdate;1261  for (const auto &A : FrameData.Allocas) {1262    AllocaInst *Alloca = A.Alloca;1263    UsersToUpdate.clear();1264    for (User *U : make_early_inc_range(Alloca->users())) {1265      auto *I = cast<Instruction>(U);1266      // It is meaningless to retain the lifetime intrinsics refer for the1267      // member of coroutine frames and the meaningless lifetime intrinsics1268      // are possible to block further optimizations.1269      if (I->isLifetimeStartOrEnd())1270        I->eraseFromParent();1271      else if (DT.dominates(Shape.CoroBegin, I))1272        UsersToUpdate.push_back(I);1273    }1274 1275    if (UsersToUpdate.empty())1276      continue;1277    auto *G = GetFramePointer(Alloca);1278    G->setName(Alloca->getName() + Twine(".reload.addr"));1279 1280    SmallVector<DbgVariableRecord *> DbgVariableRecords;1281    findDbgUsers(Alloca, DbgVariableRecords);1282    for (auto *DVR : DbgVariableRecords)1283      DVR->replaceVariableLocationOp(Alloca, G);1284 1285    for (Instruction *I : UsersToUpdate)1286      I->replaceUsesOfWith(Alloca, G);1287  }1288  Builder.SetInsertPoint(&*Shape.getInsertPtAfterFramePtr());1289  for (const auto &A : FrameData.Allocas) {1290    AllocaInst *Alloca = A.Alloca;1291    if (A.MayWriteBeforeCoroBegin) {1292      // isEscaped really means potentially modified before CoroBegin.1293      if (Alloca->isArrayAllocation())1294        report_fatal_error(1295            "Coroutines cannot handle copying of array allocas yet");1296 1297      auto *G = GetFramePointer(Alloca);1298      auto *Value = Builder.CreateLoad(Alloca->getAllocatedType(), Alloca);1299      Builder.CreateStore(Value, G);1300    }1301    // For each alias to Alloca created before CoroBegin but used after1302    // CoroBegin, we recreate them after CoroBegin by applying the offset1303    // to the pointer in the frame.1304    for (const auto &Alias : A.Aliases) {1305      auto *FramePtr = GetFramePointer(Alloca);1306      auto &Value = *Alias.second;1307      auto ITy = IntegerType::get(C, Value.getBitWidth());1308      auto *AliasPtr =1309          Builder.CreatePtrAdd(FramePtr, ConstantInt::get(ITy, Value));1310      Alias.first->replaceUsesWithIf(1311          AliasPtr, [&](Use &U) { return DT.dominates(Shape.CoroBegin, U); });1312    }1313  }1314 1315  // PromiseAlloca is not collected in FrameData.Allocas. So we don't handle1316  // the case that the PromiseAlloca may have writes before CoroBegin in the1317  // above codes. And it may be problematic in edge cases. See1318  // https://github.com/llvm/llvm-project/issues/57861 for an example.1319  if (Shape.ABI == coro::ABI::Switch && Shape.SwitchLowering.PromiseAlloca) {1320    AllocaInst *PA = Shape.SwitchLowering.PromiseAlloca;1321    // If there is memory accessing to promise alloca before CoroBegin;1322    bool HasAccessingPromiseBeforeCB = llvm::any_of(PA->uses(), [&](Use &U) {1323      auto *Inst = dyn_cast<Instruction>(U.getUser());1324      if (!Inst || DT.dominates(Shape.CoroBegin, Inst))1325        return false;1326 1327      if (auto *CI = dyn_cast<CallInst>(Inst)) {1328        // It is fine if the call wouldn't write to the Promise.1329        // This is possible for @llvm.coro.id intrinsics, which1330        // would take the promise as the second argument as a1331        // marker.1332        if (CI->onlyReadsMemory() ||1333            CI->onlyReadsMemory(CI->getArgOperandNo(&U)))1334          return false;1335        return true;1336      }1337 1338      return isa<StoreInst>(Inst) ||1339             // It may take too much time to track the uses.1340             // Be conservative about the case the use may escape.1341             isa<GetElementPtrInst>(Inst) ||1342             // There would always be a bitcast for the promise alloca1343             // before we enabled Opaque pointers. And now given1344             // opaque pointers are enabled by default. This should be1345             // fine.1346             isa<BitCastInst>(Inst);1347    });1348    if (HasAccessingPromiseBeforeCB) {1349      Builder.SetInsertPoint(&*Shape.getInsertPtAfterFramePtr());1350      auto *G = GetFramePointer(PA);1351      auto *Value = Builder.CreateLoad(PA->getAllocatedType(), PA);1352      Builder.CreateStore(Value, G);1353    }1354  }1355}1356 1357// Moves the values in the PHIs in SuccBB that correspong to PredBB into a new1358// PHI in InsertedBB.1359static void movePHIValuesToInsertedBlock(BasicBlock *SuccBB,1360                                         BasicBlock *InsertedBB,1361                                         BasicBlock *PredBB,1362                                         PHINode *UntilPHI = nullptr) {1363  auto *PN = cast<PHINode>(&SuccBB->front());1364  do {1365    int Index = PN->getBasicBlockIndex(InsertedBB);1366    Value *V = PN->getIncomingValue(Index);1367    PHINode *InputV = PHINode::Create(1368        V->getType(), 1, V->getName() + Twine(".") + SuccBB->getName());1369    InputV->insertBefore(InsertedBB->begin());1370    InputV->addIncoming(V, PredBB);1371    PN->setIncomingValue(Index, InputV);1372    PN = dyn_cast<PHINode>(PN->getNextNode());1373  } while (PN != UntilPHI);1374}1375 1376// Rewrites the PHI Nodes in a cleanuppad.1377static void rewritePHIsForCleanupPad(BasicBlock *CleanupPadBB,1378                                     CleanupPadInst *CleanupPad) {1379  // For every incoming edge to a CleanupPad we will create a new block holding1380  // all incoming values in single-value PHI nodes. We will then create another1381  // block to act as a dispather (as all unwind edges for related EH blocks1382  // must be the same).1383  //1384  // cleanuppad:1385  //    %2 = phi i32[%0, %catchswitch], [%1, %catch.1]1386  //    %3 = cleanuppad within none []1387  //1388  // It will create:1389  //1390  // cleanuppad.corodispatch1391  //    %2 = phi i8[0, %catchswitch], [1, %catch.1]1392  //    %3 = cleanuppad within none []1393  //    switch i8 % 2, label %unreachable1394  //            [i8 0, label %cleanuppad.from.catchswitch1395  //             i8 1, label %cleanuppad.from.catch.1]1396  // cleanuppad.from.catchswitch:1397  //    %4 = phi i32 [%0, %catchswitch]1398  //    br %label cleanuppad1399  // cleanuppad.from.catch.1:1400  //    %6 = phi i32 [%1, %catch.1]1401  //    br %label cleanuppad1402  // cleanuppad:1403  //    %8 = phi i32 [%4, %cleanuppad.from.catchswitch],1404  //                 [%6, %cleanuppad.from.catch.1]1405 1406  // Unreachable BB, in case switching on an invalid value in the dispatcher.1407  auto *UnreachBB = BasicBlock::Create(1408      CleanupPadBB->getContext(), "unreachable", CleanupPadBB->getParent());1409  IRBuilder<> Builder(UnreachBB);1410  Builder.CreateUnreachable();1411 1412  // Create a new cleanuppad which will be the dispatcher.1413  auto *NewCleanupPadBB =1414      BasicBlock::Create(CleanupPadBB->getContext(),1415                         CleanupPadBB->getName() + Twine(".corodispatch"),1416                         CleanupPadBB->getParent(), CleanupPadBB);1417  Builder.SetInsertPoint(NewCleanupPadBB);1418  auto *SwitchType = Builder.getInt8Ty();1419  auto *SetDispatchValuePN =1420      Builder.CreatePHI(SwitchType, pred_size(CleanupPadBB));1421  CleanupPad->removeFromParent();1422  CleanupPad->insertAfter(SetDispatchValuePN->getIterator());1423  auto *SwitchOnDispatch = Builder.CreateSwitch(SetDispatchValuePN, UnreachBB,1424                                                pred_size(CleanupPadBB));1425 1426  int SwitchIndex = 0;1427  SmallVector<BasicBlock *, 8> Preds(predecessors(CleanupPadBB));1428  for (BasicBlock *Pred : Preds) {1429    // Create a new cleanuppad and move the PHI values to there.1430    auto *CaseBB = BasicBlock::Create(CleanupPadBB->getContext(),1431                                      CleanupPadBB->getName() +1432                                          Twine(".from.") + Pred->getName(),1433                                      CleanupPadBB->getParent(), CleanupPadBB);1434    updatePhiNodes(CleanupPadBB, Pred, CaseBB);1435    CaseBB->setName(CleanupPadBB->getName() + Twine(".from.") +1436                    Pred->getName());1437    Builder.SetInsertPoint(CaseBB);1438    Builder.CreateBr(CleanupPadBB);1439    movePHIValuesToInsertedBlock(CleanupPadBB, CaseBB, NewCleanupPadBB);1440 1441    // Update this Pred to the new unwind point.1442    setUnwindEdgeTo(Pred->getTerminator(), NewCleanupPadBB);1443 1444    // Setup the switch in the dispatcher.1445    auto *SwitchConstant = ConstantInt::get(SwitchType, SwitchIndex);1446    SetDispatchValuePN->addIncoming(SwitchConstant, Pred);1447    SwitchOnDispatch->addCase(SwitchConstant, CaseBB);1448    SwitchIndex++;1449  }1450}1451 1452static void cleanupSinglePredPHIs(Function &F) {1453  SmallVector<PHINode *, 32> Worklist;1454  for (auto &BB : F) {1455    for (auto &Phi : BB.phis()) {1456      if (Phi.getNumIncomingValues() == 1) {1457        Worklist.push_back(&Phi);1458      } else1459        break;1460    }1461  }1462  while (!Worklist.empty()) {1463    auto *Phi = Worklist.pop_back_val();1464    auto *OriginalValue = Phi->getIncomingValue(0);1465    Phi->replaceAllUsesWith(OriginalValue);1466  }1467}1468 1469static void rewritePHIs(BasicBlock &BB) {1470  // For every incoming edge we will create a block holding all1471  // incoming values in a single PHI nodes.1472  //1473  // loop:1474  //    %n.val = phi i32[%n, %entry], [%inc, %loop]1475  //1476  // It will create:1477  //1478  // loop.from.entry:1479  //    %n.loop.pre = phi i32 [%n, %entry]1480  //    br %label loop1481  // loop.from.loop:1482  //    %inc.loop.pre = phi i32 [%inc, %loop]1483  //    br %label loop1484  //1485  // After this rewrite, further analysis will ignore any phi nodes with more1486  // than one incoming edge.1487 1488  // TODO: Simplify PHINodes in the basic block to remove duplicate1489  // predecessors.1490 1491  // Special case for CleanupPad: all EH blocks must have the same unwind edge1492  // so we need to create an additional "dispatcher" block.1493  if (!BB.empty()) {1494    if (auto *CleanupPad =1495            dyn_cast_or_null<CleanupPadInst>(BB.getFirstNonPHIIt())) {1496      SmallVector<BasicBlock *, 8> Preds(predecessors(&BB));1497      for (BasicBlock *Pred : Preds) {1498        if (CatchSwitchInst *CS =1499                dyn_cast<CatchSwitchInst>(Pred->getTerminator())) {1500          // CleanupPad with a CatchSwitch predecessor: therefore this is an1501          // unwind destination that needs to be handle specially.1502          assert(CS->getUnwindDest() == &BB);1503          (void)CS;1504          rewritePHIsForCleanupPad(&BB, CleanupPad);1505          return;1506        }1507      }1508    }1509  }1510 1511  LandingPadInst *LandingPad = nullptr;1512  PHINode *ReplPHI = nullptr;1513  if (!BB.empty()) {1514    if ((LandingPad =1515             dyn_cast_or_null<LandingPadInst>(BB.getFirstNonPHIIt()))) {1516      // ehAwareSplitEdge will clone the LandingPad in all the edge blocks.1517      // We replace the original landing pad with a PHINode that will collect the1518      // results from all of them.1519      ReplPHI = PHINode::Create(LandingPad->getType(), 1, "");1520      ReplPHI->insertBefore(LandingPad->getIterator());1521      ReplPHI->takeName(LandingPad);1522      LandingPad->replaceAllUsesWith(ReplPHI);1523      // We will erase the original landing pad at the end of this function after1524      // ehAwareSplitEdge cloned it in the transition blocks.1525    }1526  }1527 1528  SmallVector<BasicBlock *, 8> Preds(predecessors(&BB));1529  for (BasicBlock *Pred : Preds) {1530    auto *IncomingBB = ehAwareSplitEdge(Pred, &BB, LandingPad, ReplPHI);1531    // ehAwareSplitEdge (via SplitEdge/SplitKnownCriticalEdge) returns null when1532    // the critical edge cannot be split the ordinary way -- most notably an1533    // edge out of an indirectbr, whose successor's address is taken.1534    // normalizeCoroutine runs SplitIndirectBrCriticalEdges before this, which1535    // removes the common indirectbr-into-multi-PHI shape; if some residual1536    // un-splittable shape still reaches here, fail loudly rather than1537    // dereferencing null (never-silent floor: no SIGSEGV / null-deref).1538    if (!IncomingBB)1539      report_fatal_error(1540          "coro-split: cannot split a critical edge into PHI block '" +1541          BB.getName() +1542          "' from predecessor '" + Pred->getName() +1543          "' (likely an un-splittable indirectbr edge); the coroutine frame "1544          "PHIs cannot be normalized for this control-flow shape");1545    IncomingBB->setName(BB.getName() + Twine(".from.") + Pred->getName());1546 1547    // Stop the moving of values at ReplPHI, as this is either null or the PHI1548    // that replaced the landing pad.1549    movePHIValuesToInsertedBlock(&BB, IncomingBB, Pred, ReplPHI);1550  }1551 1552  if (LandingPad) {1553    // Calls to ehAwareSplitEdge function cloned the original lading pad.1554    // No longer need it.1555    LandingPad->eraseFromParent();1556  }1557}1558 1559static void rewritePHIs(Function &F) {1560  SmallVector<BasicBlock *, 8> WorkList;1561 1562  for (BasicBlock &BB : F)1563    if (auto *PN = dyn_cast<PHINode>(&BB.front()))1564      if (PN->getNumIncomingValues() > 1)1565        WorkList.push_back(&BB);1566 1567  for (BasicBlock *BB : WorkList)1568    rewritePHIs(*BB);1569}1570 1571// Splits the block at a particular instruction unless it is the first1572// instruction in the block with a single predecessor.1573static BasicBlock *splitBlockIfNotFirst(Instruction *I, const Twine &Name) {1574  auto *BB = I->getParent();1575  if (&BB->front() == I) {1576    if (BB->getSinglePredecessor()) {1577      BB->setName(Name);1578      return BB;1579    }1580  }1581  return BB->splitBasicBlock(I, Name);1582}1583 1584// Split above and below a particular instruction so that it1585// will be all alone by itself in a block.1586static void splitAround(Instruction *I, const Twine &Name) {1587  splitBlockIfNotFirst(I, Name);1588  splitBlockIfNotFirst(I->getNextNode(), "After" + Name);1589}1590 1591/// After we split the coroutine, will the given basic block be along1592/// an obvious exit path for the resumption function?1593static bool willLeaveFunctionImmediatelyAfter(BasicBlock *BB,1594                                              unsigned depth = 3) {1595  // If we've bottomed out our depth count, stop searching and assume1596  // that the path might loop back.1597  if (depth == 0) return false;1598 1599  // If this is a suspend block, we're about to exit the resumption function.1600  if (coro::isSuspendBlock(BB))1601    return true;1602 1603  // Recurse into the successors.1604  for (auto *Succ : successors(BB)) {1605    if (!willLeaveFunctionImmediatelyAfter(Succ, depth - 1))1606      return false;1607  }1608 1609  // If none of the successors leads back in a loop, we're on an exit/abort.1610  return true;1611}1612 1613static bool localAllocaNeedsStackSave(CoroAllocaAllocInst *AI) {1614  // Look for a free that isn't sufficiently obviously followed by1615  // either a suspend or a termination, i.e. something that will leave1616  // the coro resumption frame.1617  for (auto *U : AI->users()) {1618    auto FI = dyn_cast<CoroAllocaFreeInst>(U);1619    if (!FI) continue;1620 1621    if (!willLeaveFunctionImmediatelyAfter(FI->getParent()))1622      return true;1623  }1624 1625  // If we never found one, we don't need a stack save.1626  return false;1627}1628 1629/// Turn each of the given local allocas into a normal (dynamic) alloca1630/// instruction.1631static void lowerLocalAllocas(ArrayRef<CoroAllocaAllocInst*> LocalAllocas,1632                              SmallVectorImpl<Instruction*> &DeadInsts) {1633  for (auto *AI : LocalAllocas) {1634    IRBuilder<> Builder(AI);1635 1636    // Save the stack depth.  Try to avoid doing this if the stackrestore1637    // is going to immediately precede a return or something.1638    Value *StackSave = nullptr;1639    if (localAllocaNeedsStackSave(AI))1640      StackSave = Builder.CreateStackSave();1641 1642    // Allocate memory.1643    auto Alloca = Builder.CreateAlloca(Builder.getInt8Ty(), AI->getSize());1644    Alloca->setAlignment(AI->getAlignment());1645 1646    for (auto *U : AI->users()) {1647      // Replace gets with the allocation.1648      if (isa<CoroAllocaGetInst>(U)) {1649        U->replaceAllUsesWith(Alloca);1650 1651      // Replace frees with stackrestores.  This is safe because1652      // alloca.alloc is required to obey a stack discipline, although we1653      // don't enforce that structurally.1654      } else {1655        auto FI = cast<CoroAllocaFreeInst>(U);1656        if (StackSave) {1657          Builder.SetInsertPoint(FI);1658          Builder.CreateStackRestore(StackSave);1659        }1660      }1661      DeadInsts.push_back(cast<Instruction>(U));1662    }1663 1664    DeadInsts.push_back(AI);1665  }1666}1667 1668/// Get the current swifterror value.1669static Value *emitGetSwiftErrorValue(IRBuilder<> &Builder, Type *ValueTy,1670                                     coro::Shape &Shape) {1671  // Make a fake function pointer as a sort of intrinsic.1672  auto FnTy = FunctionType::get(ValueTy, {}, false);1673  auto Fn = ConstantPointerNull::get(Builder.getPtrTy());1674 1675  auto Call = Builder.CreateCall(FnTy, Fn, {});1676  Shape.SwiftErrorOps.push_back(Call);1677 1678  return Call;1679}1680 1681/// Set the given value as the current swifterror value.1682///1683/// Returns a slot that can be used as a swifterror slot.1684static Value *emitSetSwiftErrorValue(IRBuilder<> &Builder, Value *V,1685                                     coro::Shape &Shape) {1686  // Make a fake function pointer as a sort of intrinsic.1687  auto FnTy = FunctionType::get(Builder.getPtrTy(),1688                                {V->getType()}, false);1689  auto Fn = ConstantPointerNull::get(Builder.getPtrTy());1690 1691  auto Call = Builder.CreateCall(FnTy, Fn, { V });1692  Shape.SwiftErrorOps.push_back(Call);1693 1694  return Call;1695}1696 1697/// Set the swifterror value from the given alloca before a call,1698/// then put in back in the alloca afterwards.1699///1700/// Returns an address that will stand in for the swifterror slot1701/// until splitting.1702static Value *emitSetAndGetSwiftErrorValueAround(Instruction *Call,1703                                                 AllocaInst *Alloca,1704                                                 coro::Shape &Shape) {1705  auto ValueTy = Alloca->getAllocatedType();1706  IRBuilder<> Builder(Call);1707 1708  // Load the current value from the alloca and set it as the1709  // swifterror value.1710  auto ValueBeforeCall = Builder.CreateLoad(ValueTy, Alloca);1711  auto Addr = emitSetSwiftErrorValue(Builder, ValueBeforeCall, Shape);1712 1713  // Move to after the call.  Since swifterror only has a guaranteed1714  // value on normal exits, we can ignore implicit and explicit unwind1715  // edges.1716  if (isa<CallInst>(Call)) {1717    Builder.SetInsertPoint(Call->getNextNode());1718  } else {1719    auto Invoke = cast<InvokeInst>(Call);1720    Builder.SetInsertPoint(Invoke->getNormalDest()->getFirstNonPHIOrDbg());1721  }1722 1723  // Get the current swifterror value and store it to the alloca.1724  auto ValueAfterCall = emitGetSwiftErrorValue(Builder, ValueTy, Shape);1725  Builder.CreateStore(ValueAfterCall, Alloca);1726 1727  return Addr;1728}1729 1730/// Eliminate a formerly-swifterror alloca by inserting the get/set1731/// intrinsics and attempting to MemToReg the alloca away.1732static void eliminateSwiftErrorAlloca(Function &F, AllocaInst *Alloca,1733                                      coro::Shape &Shape) {1734  for (Use &Use : llvm::make_early_inc_range(Alloca->uses())) {1735    // swifterror values can only be used in very specific ways.1736    // We take advantage of that here.1737    auto User = Use.getUser();1738    if (isa<LoadInst>(User) || isa<StoreInst>(User))1739      continue;1740 1741    assert(isa<CallInst>(User) || isa<InvokeInst>(User));1742    auto Call = cast<Instruction>(User);1743 1744    auto Addr = emitSetAndGetSwiftErrorValueAround(Call, Alloca, Shape);1745 1746    // Use the returned slot address as the call argument.1747    Use.set(Addr);1748  }1749 1750  // All the uses should be loads and stores now.1751  assert(isAllocaPromotable(Alloca));1752}1753 1754/// "Eliminate" a swifterror argument by reducing it to the alloca case1755/// and then loading and storing in the prologue and epilog.1756///1757/// The argument keeps the swifterror flag.1758static void eliminateSwiftErrorArgument(Function &F, Argument &Arg,1759                                        coro::Shape &Shape,1760                             SmallVectorImpl<AllocaInst*> &AllocasToPromote) {1761  IRBuilder<> Builder(&F.getEntryBlock(),1762                      F.getEntryBlock().getFirstNonPHIOrDbg());1763 1764  auto ArgTy = cast<PointerType>(Arg.getType());1765  auto ValueTy = PointerType::getUnqual(F.getContext());1766 1767  // Reduce to the alloca case:1768 1769  // Create an alloca and replace all uses of the arg with it.1770  auto Alloca = Builder.CreateAlloca(ValueTy, ArgTy->getAddressSpace());1771  Arg.replaceAllUsesWith(Alloca);1772 1773  // Set an initial value in the alloca.  swifterror is always null on entry.1774  auto InitialValue = Constant::getNullValue(ValueTy);1775  Builder.CreateStore(InitialValue, Alloca);1776 1777  // Find all the suspends in the function and save and restore around them.1778  for (auto *Suspend : Shape.CoroSuspends) {1779    (void) emitSetAndGetSwiftErrorValueAround(Suspend, Alloca, Shape);1780  }1781 1782  // Find all the coro.ends in the function and restore the error value.1783  for (auto *End : Shape.CoroEnds) {1784    Builder.SetInsertPoint(End);1785    auto FinalValue = Builder.CreateLoad(ValueTy, Alloca);1786    (void) emitSetSwiftErrorValue(Builder, FinalValue, Shape);1787  }1788 1789  // Now we can use the alloca logic.1790  AllocasToPromote.push_back(Alloca);1791  eliminateSwiftErrorAlloca(F, Alloca, Shape);1792}1793 1794/// Eliminate all problematic uses of swifterror arguments and allocas1795/// from the function.  We'll fix them up later when splitting the function.1796static void eliminateSwiftError(Function &F, coro::Shape &Shape) {1797  SmallVector<AllocaInst*, 4> AllocasToPromote;1798 1799  // Look for a swifterror argument.1800  for (auto &Arg : F.args()) {1801    if (!Arg.hasSwiftErrorAttr()) continue;1802 1803    eliminateSwiftErrorArgument(F, Arg, Shape, AllocasToPromote);1804    break;1805  }1806 1807  // Look for swifterror allocas.1808  for (auto &Inst : F.getEntryBlock()) {1809    auto Alloca = dyn_cast<AllocaInst>(&Inst);1810    if (!Alloca || !Alloca->isSwiftError()) continue;1811 1812    // Clear the swifterror flag.1813    Alloca->setSwiftError(false);1814 1815    AllocasToPromote.push_back(Alloca);1816    eliminateSwiftErrorAlloca(F, Alloca, Shape);1817  }1818 1819  // If we have any allocas to promote, compute a dominator tree and1820  // promote them en masse.1821  if (!AllocasToPromote.empty()) {1822    DominatorTree DT(F);1823    PromoteMemToReg(AllocasToPromote, DT);1824  }1825}1826 1827/// For each local variable that all of its user are only used inside one of1828/// suspended region, we sink their lifetime.start markers to the place where1829/// after the suspend block. Doing so minimizes the lifetime of each variable,1830/// hence minimizing the amount of data we end up putting on the frame.1831static void sinkLifetimeStartMarkers(Function &F, coro::Shape &Shape,1832                                     SuspendCrossingInfo &Checker,1833                                     const DominatorTree &DT) {1834  if (F.hasOptNone())1835    return;1836 1837  // Collect all possible basic blocks which may dominate all uses of allocas.1838  SmallPtrSet<BasicBlock *, 4> DomSet;1839  DomSet.insert(&F.getEntryBlock());1840  for (auto *CSI : Shape.CoroSuspends) {1841    BasicBlock *SuspendBlock = CSI->getParent();1842    assert(coro::isSuspendBlock(SuspendBlock) &&1843           SuspendBlock->getSingleSuccessor() &&1844           "should have split coro.suspend into its own block");1845    DomSet.insert(SuspendBlock->getSingleSuccessor());1846  }1847 1848  for (Instruction &I : instructions(F)) {1849    AllocaInst* AI = dyn_cast<AllocaInst>(&I);1850    if (!AI)1851      continue;1852 1853    for (BasicBlock *DomBB : DomSet) {1854      bool Valid = true;1855      SmallVector<Instruction *, 1> Lifetimes;1856 1857      auto isLifetimeStart = [](Instruction* I) {1858        if (auto* II = dyn_cast<IntrinsicInst>(I))1859          return II->getIntrinsicID() == Intrinsic::lifetime_start;1860        return false;1861      };1862 1863      auto collectLifetimeStart = [&](Instruction *U, AllocaInst *AI) {1864        if (isLifetimeStart(U)) {1865          Lifetimes.push_back(U);1866          return true;1867        }1868        if (!U->hasOneUse() || U->stripPointerCasts() != AI)1869          return false;1870        if (isLifetimeStart(U->user_back())) {1871          Lifetimes.push_back(U->user_back());1872          return true;1873        }1874        return false;1875      };1876 1877      for (User *U : AI->users()) {1878        Instruction *UI = cast<Instruction>(U);1879        // For all users except lifetime.start markers, if they are all1880        // dominated by one of the basic blocks and do not cross1881        // suspend points as well, then there is no need to spill the1882        // instruction.1883        if (!DT.dominates(DomBB, UI->getParent()) ||1884            Checker.isDefinitionAcrossSuspend(DomBB, UI)) {1885          // Skip lifetime.start, GEP and bitcast used by lifetime.start1886          // markers.1887          if (collectLifetimeStart(UI, AI))1888            continue;1889          Valid = false;1890          break;1891        }1892      }1893      // Sink lifetime.start markers to dominate block when they are1894      // only used outside the region.1895      if (Valid && Lifetimes.size() != 0) {1896        auto *NewLifetime = Lifetimes[0]->clone();1897        NewLifetime->replaceUsesOfWith(NewLifetime->getOperand(0), AI);1898        NewLifetime->insertBefore(DomBB->getTerminator()->getIterator());1899 1900        // All the outsided lifetime.start markers are no longer necessary.1901        for (Instruction *S : Lifetimes)1902          S->eraseFromParent();1903 1904        break;1905      }1906    }1907  }1908}1909 1910static std::optional<std::pair<Value &, DIExpression &>>1911salvageDebugInfoImpl(SmallDenseMap<Argument *, AllocaInst *, 4> &ArgToAllocaMap,1912                     bool UseEntryValue, Function *F, Value *Storage,1913                     DIExpression *Expr, bool SkipOutermostLoad) {1914  IRBuilder<> Builder(F->getContext());1915  auto InsertPt = F->getEntryBlock().getFirstInsertionPt();1916  while (isa<IntrinsicInst>(InsertPt))1917    ++InsertPt;1918  Builder.SetInsertPoint(&F->getEntryBlock(), InsertPt);1919 1920  while (auto *Inst = dyn_cast_or_null<Instruction>(Storage)) {1921    if (auto *LdInst = dyn_cast<LoadInst>(Inst)) {1922      Storage = LdInst->getPointerOperand();1923      // FIXME: This is a heuristic that works around the fact that1924      // LLVM IR debug intrinsics cannot yet distinguish between1925      // memory and value locations: Because a dbg.declare(alloca) is1926      // implicitly a memory location no DW_OP_deref operation for the1927      // last direct load from an alloca is necessary.  This condition1928      // effectively drops the *last* DW_OP_deref in the expression.1929      if (!SkipOutermostLoad)1930        Expr = DIExpression::prepend(Expr, DIExpression::DerefBefore);1931    } else if (auto *StInst = dyn_cast<StoreInst>(Inst)) {1932      Storage = StInst->getValueOperand();1933    } else {1934      SmallVector<uint64_t, 16> Ops;1935      SmallVector<Value *, 0> AdditionalValues;1936      Value *Op = llvm::salvageDebugInfoImpl(1937          *Inst, Expr ? Expr->getNumLocationOperands() : 0, Ops,1938          AdditionalValues);1939      if (!Op || !AdditionalValues.empty()) {1940        // If salvaging failed or salvaging produced more than one location1941        // operand, give up.1942        break;1943      }1944      Storage = Op;1945      Expr = DIExpression::appendOpsToArg(Expr, Ops, 0, /*StackValue*/ false);1946    }1947    SkipOutermostLoad = false;1948  }1949  if (!Storage)1950    return std::nullopt;1951 1952  auto *StorageAsArg = dyn_cast<Argument>(Storage);1953  const bool IsSwiftAsyncArg =1954      StorageAsArg && StorageAsArg->hasAttribute(Attribute::SwiftAsync);1955 1956  // Swift async arguments are described by an entry value of the ABI-defined1957  // register containing the coroutine context.1958  // Entry values in variadic expressions are not supported.1959  if (IsSwiftAsyncArg && UseEntryValue && !Expr->isEntryValue() &&1960      Expr->isSingleLocationExpression())1961    Expr = DIExpression::prepend(Expr, DIExpression::EntryValue);1962 1963  // If the coroutine frame is an Argument, store it in an alloca to improve1964  // its availability (e.g. registers may be clobbered).1965  // Avoid this if the value is guaranteed to be available through other means1966  // (e.g. swift ABI guarantees).1967  if (StorageAsArg && !IsSwiftAsyncArg) {1968    auto &Cached = ArgToAllocaMap[StorageAsArg];1969    if (!Cached) {1970      Cached = Builder.CreateAlloca(Storage->getType(), 0, nullptr,1971                                    Storage->getName() + ".debug");1972      Builder.CreateStore(Storage, Cached);1973    }1974    Storage = Cached;1975    // FIXME: LLVM lacks nuanced semantics to differentiate between1976    // memory and direct locations at the IR level. The backend will1977    // turn a dbg.declare(alloca, ..., DIExpression()) into a memory1978    // location. Thus, if there are deref and offset operations in the1979    // expression, we need to add a DW_OP_deref at the *start* of the1980    // expression to first load the contents of the alloca before1981    // adjusting it with the expression.1982    Expr = DIExpression::prepend(Expr, DIExpression::DerefBefore);1983  }1984 1985  Expr = Expr->foldConstantMath();1986  return {{*Storage, *Expr}};1987}1988 1989void coro::salvageDebugInfo(1990    SmallDenseMap<Argument *, AllocaInst *, 4> &ArgToAllocaMap,1991    DbgVariableRecord &DVR, bool UseEntryValue) {1992 1993  Function *F = DVR.getFunction();1994  // Follow the pointer arithmetic all the way to the incoming1995  // function argument and convert into a DIExpression.1996  bool SkipOutermostLoad = DVR.isDbgDeclare() || DVR.isDbgDeclareValue();1997  Value *OriginalStorage = DVR.getVariableLocationOp(0);1998 1999  auto SalvagedInfo =2000      ::salvageDebugInfoImpl(ArgToAllocaMap, UseEntryValue, F, OriginalStorage,2001                             DVR.getExpression(), SkipOutermostLoad);2002  if (!SalvagedInfo)2003    return;2004 2005  Value *Storage = &SalvagedInfo->first;2006  DIExpression *Expr = &SalvagedInfo->second;2007 2008  DVR.replaceVariableLocationOp(OriginalStorage, Storage);2009  DVR.setExpression(Expr);2010  // We only hoist dbg.declare and dbg.declare_value today since it doesn't make2011  // sense to hoist dbg.value since it does not have the same function wide2012  // guarantees that dbg.declare does.2013  if (DVR.getType() == DbgVariableRecord::LocationType::Declare ||2014      DVR.getType() == DbgVariableRecord::LocationType::DeclareValue) {2015    std::optional<BasicBlock::iterator> InsertPt;2016    if (auto *I = dyn_cast<Instruction>(Storage)) {2017      InsertPt = I->getInsertionPointAfterDef();2018      // Update DILocation only if variable was not inlined.2019      DebugLoc ILoc = I->getDebugLoc();2020      DebugLoc DVRLoc = DVR.getDebugLoc();2021      if (ILoc && DVRLoc &&2022          DVRLoc->getScope()->getSubprogram() ==2023              ILoc->getScope()->getSubprogram())2024        DVR.setDebugLoc(ILoc);2025    } else if (isa<Argument>(Storage))2026      InsertPt = F->getEntryBlock().begin();2027    if (InsertPt) {2028      DVR.removeFromParent();2029      // If there is a dbg.declare_value being reinserted, insert it as a2030      // dbg.declare instead, so that subsequent passes don't have to deal with2031      // a dbg.declare_value.2032      if (DVR.getType() == DbgVariableRecord::LocationType::DeclareValue) {2033        auto *MD = DVR.getRawLocation();2034        if (auto *VAM = dyn_cast<ValueAsMetadata>(MD)) {2035          Type *Ty = VAM->getValue()->getType();2036          if (Ty->isPointerTy())2037            DVR.Type = DbgVariableRecord::LocationType::Declare;2038          else2039            DVR.Type = DbgVariableRecord::LocationType::Value;2040        }2041      }2042      (*InsertPt)->getParent()->insertDbgRecordBefore(&DVR, *InsertPt);2043    }2044  }2045}2046 2047void coro::normalizeCoroutine(Function &F, coro::Shape &Shape,2048                              TargetTransformInfo &TTI) {2049  // Don't eliminate swifterror in async functions that won't be split.2050  if (Shape.ABI != coro::ABI::Async || !Shape.CoroSuspends.empty())2051    eliminateSwiftError(F, Shape);2052 2053  if (Shape.ABI == coro::ABI::Switch &&2054      Shape.SwitchLowering.PromiseAlloca) {2055    Shape.getSwitchCoroId()->clearPromise();2056  }2057 2058  // Make sure that all coro.save, coro.suspend and the fallthrough coro.end2059  // intrinsics are in their own blocks to simplify the logic of building up2060  // SuspendCrossing data.2061  for (auto *CSI : Shape.CoroSuspends) {2062    if (auto *Save = CSI->getCoroSave())2063      splitAround(Save, "CoroSave");2064    splitAround(CSI, "CoroSuspend");2065  }2066 2067  // Put CoroEnds into their own blocks.2068  for (AnyCoroEndInst *CE : Shape.CoroEnds) {2069    splitAround(CE, "CoroEnd");2070 2071    // Emit the musttail call function in a new block before the CoroEnd.2072    // We do this here so that the right suspend crossing info is computed for2073    // the uses of the musttail call function call. (Arguments to the coro.end2074    // instructions would be ignored)2075    if (auto *AsyncEnd = dyn_cast<CoroAsyncEndInst>(CE)) {2076      auto *MustTailCallFn = AsyncEnd->getMustTailCallFunction();2077      if (!MustTailCallFn)2078        continue;2079      IRBuilder<> Builder(AsyncEnd);2080      SmallVector<Value *, 8> Args(AsyncEnd->args());2081      auto Arguments = ArrayRef<Value *>(Args).drop_front(3);2082      auto *Call = coro::createMustTailCall(2083          AsyncEnd->getDebugLoc(), MustTailCallFn, TTI, Arguments, Builder);2084      splitAround(Call, "MustTailCall.Before.CoroEnd");2085    }2086  }2087 2088  // Later code makes structural assumptions about single predecessors phis e.g2089  // that they are not live across a suspend point.2090  cleanupSinglePredPHIs(F);2091 2092  // A critical edge out of an indirectbr cannot be split the ordinary way (the2093  // successor block's address is taken), so rewritePHIs' SplitEdge would return2094  // null and the subsequent setName would deref null. Split those edges up2095  // front with the indirectbr-aware utility (it clones the PHI-only target so2096  // the indirectbr keeps a single, un-split edge while the direct predecessors2097  // get a separate clone), exactly as CodeGenPrepare and the profiling passes2098  // do. After this, no un-splittable indirectbr critical edge into a multi-2099  // incoming-PHI block can reach rewritePHIs. This is needed for, e.g.,2100  // printf's computed-goto format dispatch (glibc printf_positional) when it is2101  // a presplit coroutine.2102  SplitIndirectBrCriticalEdges(F, /*IgnoreBlocksWithoutPHI=*/true);2103 2104  // Transforms multi-edge PHI Nodes, so that any value feeding into a PHI will2105  // never have its definition separated from the PHI by the suspend point.2106  rewritePHIs(F);2107}2108 2109void coro::BaseABI::buildCoroutineFrame(bool OptimizeFrame) {2110  SuspendCrossingInfo Checker(F, Shape.CoroSuspends, Shape.CoroEnds);2111  doRematerializations(F, Checker, IsMaterializable);2112 2113  const DominatorTree DT(F);2114  if (Shape.ABI != coro::ABI::Async && Shape.ABI != coro::ABI::Retcon &&2115      Shape.ABI != coro::ABI::RetconOnce)2116    sinkLifetimeStartMarkers(F, Shape, Checker, DT);2117 2118  // All values (that are not allocas) that needs to be spilled to the frame.2119  coro::SpillInfo Spills;2120  // All values defined as allocas that need to live in the frame.2121  SmallVector<coro::AllocaInfo, 8> Allocas;2122 2123  // Collect the spills for arguments and other not-materializable values.2124  coro::collectSpillsFromArgs(Spills, F, Checker);2125  SmallVector<Instruction *, 4> DeadInstructions;2126  SmallVector<CoroAllocaAllocInst *, 4> LocalAllocas;2127  coro::collectSpillsAndAllocasFromInsts(Spills, Allocas, DeadInstructions,2128                                         LocalAllocas, F, Checker, DT, Shape);2129  coro::collectSpillsFromDbgInfo(Spills, F, Checker);2130 2131  LLVM_DEBUG(dumpAllocas(Allocas));2132  LLVM_DEBUG(dumpSpills("Spills", Spills));2133 2134  if (Shape.ABI == coro::ABI::Retcon || Shape.ABI == coro::ABI::RetconOnce ||2135      Shape.ABI == coro::ABI::Async)2136    sinkSpillUsesAfterCoroBegin(DT, Shape.CoroBegin, Spills, Allocas);2137 2138  // Build frame2139  FrameDataInfo FrameData(Spills, Allocas);2140  Shape.FrameTy = buildFrameType(F, Shape, FrameData, OptimizeFrame);2141  Shape.FramePtr = Shape.CoroBegin;2142  // For now, this works for C++ programs only.2143  buildFrameDebugInfo(F, Shape, FrameData);2144  // Insert spills and reloads2145  insertSpills(FrameData, Shape);2146  lowerLocalAllocas(LocalAllocas, DeadInstructions);2147 2148  for (auto *I : DeadInstructions)2149    I->eraseFromParent();2150}2151