/build/llvm-toolchain-snapshot-15~++20220211101351+43a1756a5d53/llvm/include/llvm/IR/IntrinsicInst.h

Bug Summary

File:	llvm/include/llvm/IR/IntrinsicInst.h
Warning:	line 218, column 43 Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name CoroFrame.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-15~++20220211101351+43a1756a5d53/build-llvm -resource-dir /usr/lib/llvm-15/lib/clang/15.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Transforms/Coroutines -I /build/llvm-toolchain-snapshot-15~++20220211101351+43a1756a5d53/llvm/lib/Transforms/Coroutines -I include -I /build/llvm-toolchain-snapshot-15~++20220211101351+43a1756a5d53/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-15/lib/clang/15.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220211101351+43a1756a5d53/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220211101351+43a1756a5d53/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220211101351+43a1756a5d53/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220211101351+43a1756a5d53/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-15~++20220211101351+43a1756a5d53/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220211101351+43a1756a5d53/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220211101351+43a1756a5d53/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-02-12-012820-35430-1 -x c++ /build/llvm-toolchain-snapshot-15~++20220211101351+43a1756a5d53/llvm/lib/Transforms/Coroutines/CoroFrame.cpp

/build/llvm-toolchain-snapshot-15~++20220211101351+43a1756a5d53/llvm/lib/Transforms/Coroutines/CoroFrame.cpp

→

1//===- CoroFrame.cpp - Builds and manipulates coroutine frame -------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8// This file contains classes used to discover if for a particular value
9// there from sue to definition that crosses a suspend block.
10//
11// Using the information discovered we form a Coroutine Frame structure to
12// contain those values. All uses of those values are replaced with appropriate
13// GEP + load from the coroutine frame. At the point of the definition we spill
14// the value into the coroutine frame.
15//===----------------------------------------------------------------------===//

17#include "CoroInternal.h"
18#include "llvm/ADT/BitVector.h"
19#include "llvm/ADT/ScopeExit.h"
20#include "llvm/ADT/SmallString.h"
21#include "llvm/Analysis/PtrUseVisitor.h"
22#include "llvm/Analysis/StackLifetime.h"
23#include "llvm/Config/llvm-config.h"
24#include "llvm/IR/CFG.h"
25#include "llvm/IR/DIBuilder.h"
26#include "llvm/IR/DebugInfo.h"
27#include "llvm/IR/Dominators.h"
28#include "llvm/IR/IRBuilder.h"
29#include "llvm/IR/InstIterator.h"
30#include "llvm/Support/CommandLine.h"
31#include "llvm/Support/Debug.h"
32#include "llvm/Support/MathExtras.h"
33#include "llvm/Support/OptimizedStructLayout.h"
34#include "llvm/Support/circular_raw_ostream.h"
35#include "llvm/Support/raw_ostream.h"
36#include "llvm/Transforms/Utils/BasicBlockUtils.h"
37#include "llvm/Transforms/Utils/Local.h"
38#include "llvm/Transforms/Utils/PromoteMemToReg.h"
39#include <algorithm>

41using namespace llvm;

43// The "coro-suspend-crossing" flag is very noisy. There is another debug type,
44// "coro-frame", which results in leaner debug spew.
45#define DEBUG_TYPE"coro-frame" "coro-suspend-crossing"

47static cl::opt<bool> EnableReuseStorageInFrame(
  "reuse-storage-in-coroutine-frame", cl::Hidden,
  cl::desc(
      "Enable the optimization which would reuse the storage in the coroutine \
       frame for allocas whose liferanges are not overlapped, for testing purposes"),
  llvm::cl::init(false));

54enum { SmallVectorThreshold = 32 };

56// Provides two way mapping between the blocks and numbers.
57namespace {
58class BlockToIndexMapping {
SmallVector<BasicBlock *, SmallVectorThreshold> V;

61public:
size_t size() const { return V.size(); }

BlockToIndexMapping(Function &F) {
  for (BasicBlock &BB : F)
    V.push_back(&BB);
  llvm::sort(V);
}

size_t blockToIndex(BasicBlock *BB) const {
  auto *I = llvm::lower_bound(V, BB);
  assert(I != V.end() && *I == BB && "BasicBlockNumberng: Unknown block")(static_cast <bool> (I != V.end() && *I == BB &&
 "BasicBlockNumberng: Unknown block") ? void (0) : __assert_fail
 ("I != V.end() && *I == BB && \"BasicBlockNumberng: Unknown block\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 72, __extension__
 __PRETTY_FUNCTION__));
  return I - V.begin();
}

BasicBlock *indexToBlock(unsigned Index) const { return V[Index]; }
77};
78} // end anonymous namespace

80// The SuspendCrossingInfo maintains data that allows to answer a question
81// whether given two BasicBlocks A and B there is a path from A to B that
82// passes through a suspend point.
83//
84// For every basic block 'i' it maintains a BlockData that consists of:
85//   Consumes:  a bit vector which contains a set of indices of blocks that can
86//              reach block 'i'
87//   Kills: a bit vector which contains a set of indices of blocks that can
88//          reach block 'i', but one of the path will cross a suspend point
89//   Suspend: a boolean indicating whether block 'i' contains a suspend point.
90//   End: a boolean indicating whether block 'i' contains a coro.end intrinsic.
91//
92namespace {
93struct SuspendCrossingInfo {
BlockToIndexMapping Mapping;

struct BlockData {
  BitVector Consumes;
  BitVector Kills;
  bool Suspend = false;
  bool End = false;
};
SmallVector<BlockData, SmallVectorThreshold> Block;

iterator_range<succ_iterator> successors(BlockData const &BD) const {
  BasicBlock *BB = Mapping.indexToBlock(&BD - &Block[0]);
  return llvm::successors(BB);
}

BlockData &getBlockData(BasicBlock *BB) {
  return Block[Mapping.blockToIndex(BB)];
}

void dump() const;
void dump(StringRef Label, BitVector const &BV) const;

SuspendCrossingInfo(Function &F, coro::Shape &Shape);

bool hasPathCrossingSuspendPoint(BasicBlock *DefBB, BasicBlock *UseBB) const {
  size_t const DefIndex = Mapping.blockToIndex(DefBB);
  size_t const UseIndex = Mapping.blockToIndex(UseBB);

  bool const Result = Block[UseIndex].Kills[DefIndex];
  LLVM_DEBUG(dbgs() << UseBB->getName() << " => " << DefBB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << UseBB->getName() <<
 " => " << DefBB->getName() << " answer is "
 << Result << "\n"; } } while (false)
                    << " answer is " << Result << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << UseBB->getName() <<
 " => " << DefBB->getName() << " answer is "
 << Result << "\n"; } } while (false);
  return Result;
}

bool isDefinitionAcrossSuspend(BasicBlock *DefBB, User *U) const {
  auto *I = cast<Instruction>(U);

  // We rewrote PHINodes, so that only the ones with exactly one incoming
  // value need to be analyzed.
  if (auto *PN = dyn_cast<PHINode>(I))
    if (PN->getNumIncomingValues() > 1)
      return false;

  BasicBlock *UseBB = I->getParent();

  // As a special case, treat uses by an llvm.coro.suspend.retcon or an
  // llvm.coro.suspend.async as if they were uses in the suspend's single
  // predecessor: the uses conceptually occur before the suspend.
  if (isa<CoroSuspendRetconInst>(I) || isa<CoroSuspendAsyncInst>(I)) {
    UseBB = UseBB->getSinglePredecessor();
    assert(UseBB && "should have split coro.suspend into its own block")(static_cast <bool> (UseBB && "should have split coro.suspend into its own block"
) ? void (0) : __assert_fail ("UseBB && \"should have split coro.suspend into its own block\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 144, __extension__
 __PRETTY_FUNCTION__));
  }

  return hasPathCrossingSuspendPoint(DefBB, UseBB);
}

bool isDefinitionAcrossSuspend(Argument &A, User *U) const {
  return isDefinitionAcrossSuspend(&A.getParent()->getEntryBlock(), U);
}

bool isDefinitionAcrossSuspend(Instruction &I, User *U) const {
  auto *DefBB = I.getParent();

  // As a special case, treat values produced by an llvm.coro.suspend.*
  // as if they were defined in the single successor: the uses
  // conceptually occur after the suspend.
  if (isa<AnyCoroSuspendInst>(I)) {
    DefBB = DefBB->getSingleSuccessor();
    assert(DefBB && "should have split coro.suspend into its own block")(static_cast <bool> (DefBB && "should have split coro.suspend into its own block"
) ? void (0) : __assert_fail ("DefBB && \"should have split coro.suspend into its own block\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 162, __extension__
 __PRETTY_FUNCTION__));
  }

  return isDefinitionAcrossSuspend(DefBB, U);
}

bool isDefinitionAcrossSuspend(Value &V, User *U) const {
  if (auto *Arg = dyn_cast<Argument>(&V))
    return isDefinitionAcrossSuspend(*Arg, U);
  if (auto *Inst = dyn_cast<Instruction>(&V))
    return isDefinitionAcrossSuspend(*Inst, U);

  llvm_unreachable(::llvm::llvm_unreachable_internal("Coroutine could only collect Argument and Instruction now."
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 175)
      "Coroutine could only collect Argument and Instruction now.")::llvm::llvm_unreachable_internal("Coroutine could only collect Argument and Instruction now."
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 175);
}
177};
178} // end anonymous namespace

180#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
181LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void SuspendCrossingInfo::dump(StringRef Label,
                                              BitVector const &BV) const {
dbgs() << Label << ":";
for (size_t I = 0, N = BV.size(); I < N; ++I)
  if (BV[I])
    dbgs() << " " << Mapping.indexToBlock(I)->getName();
dbgs() << "\n";
188}

190LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void SuspendCrossingInfo::dump() const {
for (size_t I = 0, N = Block.size(); I < N; ++I) {
  BasicBlock *const B = Mapping.indexToBlock(I);
  dbgs() << B->getName() << ":\n";
  dump("   Consumes", Block[I].Consumes);
  dump("      Kills", Block[I].Kills);
}
dbgs() << "\n";
198}
199#endif

201SuspendCrossingInfo::SuspendCrossingInfo(Function &F, coro::Shape &Shape)
  : Mapping(F) {
const size_t N = Mapping.size();
Block.resize(N);

// Initialize every block so that it consumes itself
for (size_t I = 0; I < N; ++I) {
  auto &B = Block[I];
  B.Consumes.resize(N);
  B.Kills.resize(N);
  B.Consumes.set(I);
}

// Mark all CoroEnd Blocks. We do not propagate Kills beyond coro.ends as
// the code beyond coro.end is reachable during initial invocation of the
// coroutine.
for (auto *CE : Shape.CoroEnds)
  getBlockData(CE->getParent()).End = true;

// Mark all suspend blocks and indicate that they kill everything they
// consume. Note, that crossing coro.save also requires a spill, as any code
// between coro.save and coro.suspend may resume the coroutine and all of the
// state needs to be saved by that time.
auto markSuspendBlock = [&](IntrinsicInst *BarrierInst) {
  BasicBlock *SuspendBlock = BarrierInst->getParent();
  auto &B = getBlockData(SuspendBlock);
  B.Suspend = true;
  B.Kills |= B.Consumes;
};
for (auto *CSI : Shape.CoroSuspends) {
  markSuspendBlock(CSI);
  if (auto *Save = CSI->getCoroSave())
    markSuspendBlock(Save);
}

// Iterate propagating consumes and kills until they stop changing.
int Iteration = 0;
(void)Iteration;

bool Changed;
do {
  LLVM_DEBUG(dbgs() << "iteration " << ++Iteration)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << "iteration " << ++Iteration
; } } while (false);
  LLVM_DEBUG(dbgs() << "==============\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << "==============\n"; } } while
 (false);

  Changed = false;
  for (size_t I = 0; I < N; ++I) {
    auto &B = Block[I];
    for (BasicBlock *SI : successors(B)) {

      auto SuccNo = Mapping.blockToIndex(SI);

      // Saved Consumes and Kills bitsets so that it is easy to see
      // if anything changed after propagation.
      auto &S = Block[SuccNo];
      auto SavedConsumes = S.Consumes;
      auto SavedKills = S.Kills;

      // Propagate Kills and Consumes from block B into its successor S.
      S.Consumes |= B.Consumes;
      S.Kills |= B.Kills;

      // If block B is a suspend block, it should propagate kills into the
      // its successor for every block B consumes.
      if (B.Suspend) {
        S.Kills |= B.Consumes;
      }
      if (S.Suspend) {
        // If block S is a suspend block, it should kill all of the blocks it
        // consumes.
        S.Kills |= S.Consumes;
      } else if (S.End) {
        // If block S is an end block, it should not propagate kills as the
        // blocks following coro.end() are reached during initial invocation
        // of the coroutine while all the data are still available on the
        // stack or in the registers.
        S.Kills.reset();
      } else {
        // This is reached when S block it not Suspend nor coro.end and it
        // need to make sure that it is not in the kill set.
        S.Kills.reset(SuccNo);
      }

      // See if anything changed.
      Changed |= (S.Kills != SavedKills) || (S.Consumes != SavedConsumes);

      if (S.Kills != SavedKills) {
        LLVM_DEBUG(dbgs() << "\nblock " << I << " follower " << SI->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << "\nblock " << I <<
 " follower " << SI->getName() << "\n"; } } while
 (false)
                          << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << "\nblock " << I <<
 " follower " << SI->getName() << "\n"; } } while
 (false);
        LLVM_DEBUG(dump("S.Kills", S.Kills))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dump("S.Kills", S.Kills); } } while (false);
        LLVM_DEBUG(dump("SavedKills", SavedKills))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dump("SavedKills", SavedKills); } } while (
false);
      }
      if (S.Consumes != SavedConsumes) {
        LLVM_DEBUG(dbgs() << "\nblock " << I << " follower " << SI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << "\nblock " << I <<
 " follower " << SI << "\n"; } } while (false);
        LLVM_DEBUG(dump("S.Consume", S.Consumes))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dump("S.Consume", S.Consumes); } } while (false
);
        LLVM_DEBUG(dump("SavedCons", SavedConsumes))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dump("SavedCons", SavedConsumes); } } while
 (false);
      }
    }
  }
} while (Changed);
LLVM_DEBUG(dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dump(); } } while (false);
301}

303#undef DEBUG_TYPE"coro-frame" // "coro-suspend-crossing"
304#define DEBUG_TYPE"coro-frame" "coro-frame"

306namespace {
307class FrameTypeBuilder;
308// Mapping from the to-be-spilled value to all the users that need reload.
309using SpillInfo = SmallMapVector<Value *, SmallVector<Instruction *, 2>, 8>;
310struct AllocaInfo {
AllocaInst *Alloca;
DenseMap<Instruction *, llvm::Optional<APInt>> Aliases;
bool MayWriteBeforeCoroBegin;
AllocaInfo(AllocaInst *Alloca,
           DenseMap<Instruction *, llvm::Optional<APInt>> Aliases,
           bool MayWriteBeforeCoroBegin)
    : Alloca(Alloca), Aliases(std::move(Aliases)),
      MayWriteBeforeCoroBegin(MayWriteBeforeCoroBegin) {}
319};
320struct FrameDataInfo {
// All the values (that are not allocas) that needs to be spilled to the
// frame.
SpillInfo Spills;
// Allocas contains all values defined as allocas that need to live in the
// frame.
SmallVector<AllocaInfo, 8> Allocas;

SmallVector<Value *, 8> getAllDefs() const {
  SmallVector<Value *, 8> Defs;
  for (const auto &P : Spills)
    Defs.push_back(P.first);
  for (const auto &A : Allocas)
    Defs.push_back(A.Alloca);
  return Defs;
}

uint32_t getFieldIndex(Value *V) const {
  auto Itr = FieldIndexMap.find(V);
  assert(Itr != FieldIndexMap.end() &&(static_cast <bool> (Itr != FieldIndexMap.end() &&
 "Value does not have a frame field index") ? void (0) : __assert_fail
 ("Itr != FieldIndexMap.end() && \"Value does not have a frame field index\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 340, __extension__
 __PRETTY_FUNCTION__))
         "Value does not have a frame field index")(static_cast <bool> (Itr != FieldIndexMap.end() &&
 "Value does not have a frame field index") ? void (0) : __assert_fail
 ("Itr != FieldIndexMap.end() && \"Value does not have a frame field index\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 340, __extension__
 __PRETTY_FUNCTION__));
  return Itr->second;
}

void setFieldIndex(Value *V, uint32_t Index) {
  assert((LayoutIndexUpdateStarted || FieldIndexMap.count(V) == 0) &&(static_cast <bool> ((LayoutIndexUpdateStarted || FieldIndexMap
.count(V) == 0) && "Cannot set the index for the same field twice."
) ? void (0) : __assert_fail ("(LayoutIndexUpdateStarted || FieldIndexMap.count(V) == 0) && \"Cannot set the index for the same field twice.\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 346, __extension__
 __PRETTY_FUNCTION__))
         "Cannot set the index for the same field twice.")(static_cast <bool> ((LayoutIndexUpdateStarted || FieldIndexMap
.count(V) == 0) && "Cannot set the index for the same field twice."
) ? void (0) : __assert_fail ("(LayoutIndexUpdateStarted || FieldIndexMap.count(V) == 0) && \"Cannot set the index for the same field twice.\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 346, __extension__
 __PRETTY_FUNCTION__));
  FieldIndexMap[V] = Index;
}

uint64_t getAlign(Value *V) const {
  auto Iter = FieldAlignMap.find(V);
  assert(Iter != FieldAlignMap.end())(static_cast <bool> (Iter != FieldAlignMap.end()) ? void
 (0) : __assert_fail ("Iter != FieldAlignMap.end()", "llvm/lib/Transforms/Coroutines/CoroFrame.cpp"
, 352, __extension__ __PRETTY_FUNCTION__));
  return Iter->second;
}

void setAlign(Value *V, uint64_t Align) {
  assert(FieldAlignMap.count(V) == 0)(static_cast <bool> (FieldAlignMap.count(V) == 0) ? void
 (0) : __assert_fail ("FieldAlignMap.count(V) == 0", "llvm/lib/Transforms/Coroutines/CoroFrame.cpp"
, 357, __extension__ __PRETTY_FUNCTION__));
  FieldAlignMap.insert({V, Align});
}

uint64_t getOffset(Value *V) const {
  auto Iter = FieldOffsetMap.find(V);
  assert(Iter != FieldOffsetMap.end())(static_cast <bool> (Iter != FieldOffsetMap.end()) ? void
 (0) : __assert_fail ("Iter != FieldOffsetMap.end()", "llvm/lib/Transforms/Coroutines/CoroFrame.cpp"
, 363, __extension__ __PRETTY_FUNCTION__));
  return Iter->second;
}

void setOffset(Value *V, uint64_t Offset) {
  assert(FieldOffsetMap.count(V) == 0)(static_cast <bool> (FieldOffsetMap.count(V) == 0) ? void
 (0) : __assert_fail ("FieldOffsetMap.count(V) == 0", "llvm/lib/Transforms/Coroutines/CoroFrame.cpp"
, 368, __extension__ __PRETTY_FUNCTION__));
  FieldOffsetMap.insert({V, Offset});
}

// Remap the index of every field in the frame, using the final layout index.
void updateLayoutIndex(FrameTypeBuilder &B);

375private:
// LayoutIndexUpdateStarted is used to avoid updating the index of any field
// twice by mistake.
bool LayoutIndexUpdateStarted = false;
// Map from values to their slot indexes on the frame. They will be first set
// with their original insertion field index. After the frame is built, their
// indexes will be updated into the final layout index.
DenseMap<Value *, uint32_t> FieldIndexMap;
// Map from values to their alignment on the frame. They would be set after
// the frame is built.
DenseMap<Value *, uint64_t> FieldAlignMap;
// Map from values to their offset on the frame. They would be set after
// the frame is built.
DenseMap<Value *, uint64_t> FieldOffsetMap;
389};
390} // namespace

392#ifndef NDEBUG
393static void dumpSpills(StringRef Title, const SpillInfo &Spills) {
dbgs() << "------------- " << Title << "--------------\n";
for (const auto &E : Spills) {
  E.first->dump();
  dbgs() << "   user: ";
  for (auto *I : E.second)
    I->dump();
}
401}

403static void dumpAllocas(const SmallVectorImpl<AllocaInfo> &Allocas) {
dbgs() << "------------- Allocas --------------\n";
for (const auto &A : Allocas) {
  A.Alloca->dump();
}
408}
409#endif

411namespace {
412using FieldIDType = size_t;
413// We cannot rely solely on natural alignment of a type when building a
414// coroutine frame and if the alignment specified on the Alloca instruction
415// differs from the natural alignment of the alloca type we will need to insert
416// padding.
417class FrameTypeBuilder {
418private:
struct Field {
  uint64_t Size;
  uint64_t Offset;
  Type *Ty;
  FieldIDType LayoutFieldIndex;
  Align Alignment;
  Align TyAlignment;
};

const DataLayout &DL;
LLVMContext &Context;
uint64_t StructSize = 0;
Align StructAlign;
bool IsFinished = false;

Optional<Align> MaxFrameAlignment;

SmallVector<Field, 8> Fields;
DenseMap<Value*, unsigned> FieldIndexByKey;

439public:
FrameTypeBuilder(LLVMContext &Context, const DataLayout &DL,
                 Optional<Align> MaxFrameAlignment)
    : DL(DL), Context(Context), MaxFrameAlignment(MaxFrameAlignment) {}

/// Add a field to this structure for the storage of an `alloca`
/// instruction.
LLVM_NODISCARD[[clang::warn_unused_result]] FieldIDType addFieldForAlloca(AllocaInst *AI,
                                             bool IsHeader = false) {
  Type *Ty = AI->getAllocatedType();

  // Make an array type if this is a static array allocation.
  if (AI->isArrayAllocation()) {
    if (auto *CI = dyn_cast<ConstantInt>(AI->getArraySize()))
      Ty = ArrayType::get(Ty, CI->getValue().getZExtValue());
    else
      report_fatal_error("Coroutines cannot handle non static allocas yet");
  }

  return addField(Ty, AI->getAlign(), IsHeader);
}

/// We want to put the allocas whose lifetime-ranges are not overlapped
/// into one slot of coroutine frame.
/// Consider the example at:https://bugs.llvm.org/show_bug.cgi?id=45566
///
///     cppcoro::task<void> alternative_paths(bool cond) {
///         if (cond) {
///             big_structure a;
///             process(a);
///             co_await something();
///         } else {
///             big_structure b;
///             process2(b);
///             co_await something();
///         }
///     }
///
/// We want to put variable a and variable b in the same slot to
/// reduce the size of coroutine frame.
///
/// This function use StackLifetime algorithm to partition the AllocaInsts in
/// Spills to non-overlapped sets in order to put Alloca in the same
/// non-overlapped set into the same slot in the Coroutine Frame. Then add
/// field for the allocas in the same non-overlapped set by using the largest
/// type as the field type.
///
/// Side Effects: Because We sort the allocas, the order of allocas in the
/// frame may be different with the order in the source code.
void addFieldForAllocas(const Function &F, FrameDataInfo &FrameData,
                        coro::Shape &Shape);

/// Add a field to this structure.
LLVM_NODISCARD[[clang::warn_unused_result]] FieldIDType addField(Type *Ty, MaybeAlign FieldAlignment,
                                    bool IsHeader = false,
                                    bool IsSpillOfValue = false) {
  assert(!IsFinished && "adding fields to a finished builder")(static_cast <bool> (!IsFinished && "adding fields to a finished builder"
) ? void (0) : __assert_fail ("!IsFinished && \"adding fields to a finished builder\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 495, __extension__
 __PRETTY_FUNCTION__));
  assert(Ty && "must provide a type for a field")(static_cast <bool> (Ty && "must provide a type for a field"
) ? void (0) : __assert_fail ("Ty && \"must provide a type for a field\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 496, __extension__
 __PRETTY_FUNCTION__));

  // The field size is always the alloc size of the type.
  uint64_t FieldSize = DL.getTypeAllocSize(Ty);

  // For an alloca with size=0, we don't need to add a field and they
  // can just point to any index in the frame. Use index 0.
  if (FieldSize == 0) {
    return 0;
  }

  // The field alignment might not be the type alignment, but we need
  // to remember the type alignment anyway to build the type.
  // If we are spilling values we don't need to worry about ABI alignment
  // concerns.
  auto ABIAlign = DL.getABITypeAlign(Ty);
  Align TyAlignment =
      (IsSpillOfValue && MaxFrameAlignment)
          ? (*MaxFrameAlignment < ABIAlign ? *MaxFrameAlignment : ABIAlign)
          : ABIAlign;
  if (!FieldAlignment) {
    FieldAlignment = TyAlignment;
  }

  // Lay out header fields immediately.
  uint64_t Offset;
  if (IsHeader) {
    Offset = alignTo(StructSize, FieldAlignment);
    StructSize = Offset + FieldSize;

  // Everything else has a flexible offset.
  } else {
    Offset = OptimizedStructLayoutField::FlexibleOffset;
  }

  Fields.push_back({FieldSize, Offset, Ty, 0, *FieldAlignment, TyAlignment});
  return Fields.size() - 1;
}

/// Finish the layout and set the body on the given type.
void finish(StructType *Ty);

uint64_t getStructSize() const {
  assert(IsFinished && "not yet finished!")(static_cast <bool> (IsFinished && "not yet finished!"
) ? void (0) : __assert_fail ("IsFinished && \"not yet finished!\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 539, __extension__
 __PRETTY_FUNCTION__));
  return StructSize;
}

Align getStructAlign() const {
  assert(IsFinished && "not yet finished!")(static_cast <bool> (IsFinished && "not yet finished!"
) ? void (0) : __assert_fail ("IsFinished && \"not yet finished!\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 544, __extension__
 __PRETTY_FUNCTION__));
  return StructAlign;
}

FieldIDType getLayoutFieldIndex(FieldIDType Id) const {
  assert(IsFinished && "not yet finished!")(static_cast <bool> (IsFinished && "not yet finished!"
) ? void (0) : __assert_fail ("IsFinished && \"not yet finished!\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 549, __extension__
 __PRETTY_FUNCTION__));
  return Fields[Id].LayoutFieldIndex;
}

Field getLayoutField(FieldIDType Id) const {
  assert(IsFinished && "not yet finished!")(static_cast <bool> (IsFinished && "not yet finished!"
) ? void (0) : __assert_fail ("IsFinished && \"not yet finished!\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 554, __extension__
 __PRETTY_FUNCTION__));
  return Fields[Id];
}
557};
558} // namespace

560void FrameDataInfo::updateLayoutIndex(FrameTypeBuilder &B) {
auto Updater = [&](Value *I) {
  auto Field = B.getLayoutField(getFieldIndex(I));
  setFieldIndex(I, Field.LayoutFieldIndex);
  setAlign(I, Field.Alignment.value());
  setOffset(I, Field.Offset);
};
LayoutIndexUpdateStarted = true;
for (auto &S : Spills)
  Updater(S.first);
for (const auto &A : Allocas)
  Updater(A.Alloca);
LayoutIndexUpdateStarted = false;
573}

575void FrameTypeBuilder::addFieldForAllocas(const Function &F,
                                        FrameDataInfo &FrameData,
                                        coro::Shape &Shape) {
using AllocaSetType = SmallVector<AllocaInst *, 4>;
SmallVector<AllocaSetType, 4> NonOverlapedAllocas;

// We need to add field for allocas at the end of this function.
auto AddFieldForAllocasAtExit = make_scope_exit([&]() {
  for (auto AllocaList : NonOverlapedAllocas) {
    auto *LargestAI = *AllocaList.begin();
    FieldIDType Id = addFieldForAlloca(LargestAI);
    for (auto *Alloca : AllocaList)
      FrameData.setFieldIndex(Alloca, Id);
  }
});

if (!Shape.OptimizeFrame && !EnableReuseStorageInFrame) {
  for (const auto &A : FrameData.Allocas) {
    AllocaInst *Alloca = A.Alloca;
    NonOverlapedAllocas.emplace_back(AllocaSetType(1, Alloca));
  }
  return;
}

// Because there are pathes from the lifetime.start to coro.end
// for each alloca, the liferanges for every alloca is overlaped
// in the blocks who contain coro.end and the successor blocks.
// So we choose to skip there blocks when we calculates the liferange
// for each alloca. It should be reasonable since there shouldn't be uses
// in these blocks and the coroutine frame shouldn't be used outside the
// coroutine body.
//
// Note that the user of coro.suspend may not be SwitchInst. However, this
// case seems too complex to handle. And it is harmless to skip these
// patterns since it just prevend putting the allocas to live in the same
// slot.
DenseMap<SwitchInst *, BasicBlock *> DefaultSuspendDest;
for (auto CoroSuspendInst : Shape.CoroSuspends) {
  for (auto U : CoroSuspendInst->users()) {
    if (auto *ConstSWI = dyn_cast<SwitchInst>(U)) {
      auto *SWI = const_cast<SwitchInst *>(ConstSWI);
      DefaultSuspendDest[SWI] = SWI->getDefaultDest();
      SWI->setDefaultDest(SWI->getSuccessor(1));
    }
  }
}

auto ExtractAllocas = [&]() {
  AllocaSetType Allocas;
  Allocas.reserve(FrameData.Allocas.size());
  for (const auto &A : FrameData.Allocas)
    Allocas.push_back(A.Alloca);
  return Allocas;
};
StackLifetime StackLifetimeAnalyzer(F, ExtractAllocas(),
                                    StackLifetime::LivenessType::May);
StackLifetimeAnalyzer.run();
auto IsAllocaInferenre = [&](const AllocaInst *AI1, const AllocaInst *AI2) {
  return StackLifetimeAnalyzer.getLiveRange(AI1).overlaps(
      StackLifetimeAnalyzer.getLiveRange(AI2));
};
auto GetAllocaSize = [&](const AllocaInfo &A) {
  Optional<TypeSize> RetSize = A.Alloca->getAllocationSizeInBits(DL);
  assert(RetSize && "Variable Length Arrays (VLA) are not supported.\n")(static_cast <bool> (RetSize && "Variable Length Arrays (VLA) are not supported.\n"
) ? void (0) : __assert_fail ("RetSize && \"Variable Length Arrays (VLA) are not supported.\\n\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 638, __extension__
 __PRETTY_FUNCTION__));
  assert(!RetSize->isScalable() && "Scalable vectors are not yet supported")(static_cast <bool> (!RetSize->isScalable() &&
 "Scalable vectors are not yet supported") ? void (0) : __assert_fail
 ("!RetSize->isScalable() && \"Scalable vectors are not yet supported\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 639, __extension__
 __PRETTY_FUNCTION__));
  return RetSize->getFixedSize();
};
// Put larger allocas in the front. So the larger allocas have higher
// priority to merge, which can save more space potentially. Also each
// AllocaSet would be ordered. So we can get the largest Alloca in one
// AllocaSet easily.
sort(FrameData.Allocas, [&](const auto &Iter1, const auto &Iter2) {
  return GetAllocaSize(Iter1) > GetAllocaSize(Iter2);
});
for (const auto &A : FrameData.Allocas) {
  AllocaInst *Alloca = A.Alloca;
  bool Merged = false;
  // Try to find if the Alloca is not inferenced with any existing
  // NonOverlappedAllocaSet. If it is true, insert the alloca to that
  // NonOverlappedAllocaSet.
  for (auto &AllocaSet : NonOverlapedAllocas) {
    assert(!AllocaSet.empty() && "Processing Alloca Set is not empty.\n")(static_cast <bool> (!AllocaSet.empty() && "Processing Alloca Set is not empty.\n"
) ? void (0) : __assert_fail ("!AllocaSet.empty() && \"Processing Alloca Set is not empty.\\n\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 656, __extension__
 __PRETTY_FUNCTION__));
    bool NoInference = none_of(AllocaSet, [&](auto Iter) {
      return IsAllocaInferenre(Alloca, Iter);
    });
    // If the alignment of A is multiple of the alignment of B, the address
    // of A should satisfy the requirement for aligning for B.
    //
    // There may be other more fine-grained strategies to handle the alignment
    // infomation during the merging process. But it seems hard to handle
    // these strategies and benefit little.
    bool Alignable = [&]() -> bool {
      auto *LargestAlloca = *AllocaSet.begin();
      return LargestAlloca->getAlign().value() % Alloca->getAlign().value() ==
             0;
    }();
    bool CouldMerge = NoInference && Alignable;
    if (!CouldMerge)
      continue;
    AllocaSet.push_back(Alloca);
    Merged = true;
    break;
  }
  if (!Merged) {
    NonOverlapedAllocas.emplace_back(AllocaSetType(1, Alloca));
  }
}
// Recover the default target destination for each Switch statement
// reserved.
for (auto SwitchAndDefaultDest : DefaultSuspendDest) {
  SwitchInst *SWI = SwitchAndDefaultDest.first;
  BasicBlock *DestBB = SwitchAndDefaultDest.second;
  SWI->setDefaultDest(DestBB);
}
// This Debug Info could tell us which allocas are merged into one slot.
LLVM_DEBUG(for (auto &AllocaSetdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { for (auto &AllocaSet : NonOverlapedAllocas
) { if (AllocaSet.size() > 1) { dbgs() << "In Function:"
 << F.getName() << "\n"; dbgs() << "Find Union Set "
 << "\n"; dbgs() << "\tAllocas are \n"; for (auto
 Alloca : AllocaSet) dbgs() << "\t\t" << *Alloca <<
 "\n"; } }; } } while (false)
                : NonOverlapedAllocas) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { for (auto &AllocaSet : NonOverlapedAllocas
) { if (AllocaSet.size() > 1) { dbgs() << "In Function:"
 << F.getName() << "\n"; dbgs() << "Find Union Set "
 << "\n"; dbgs() << "\tAllocas are \n"; for (auto
 Alloca : AllocaSet) dbgs() << "\t\t" << *Alloca <<
 "\n"; } }; } } while (false)
  if (AllocaSet.size() > 1) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { for (auto &AllocaSet : NonOverlapedAllocas
) { if (AllocaSet.size() > 1) { dbgs() << "In Function:"
 << F.getName() << "\n"; dbgs() << "Find Union Set "
 << "\n"; dbgs() << "\tAllocas are \n"; for (auto
 Alloca : AllocaSet) dbgs() << "\t\t" << *Alloca <<
 "\n"; } }; } } while (false)
    dbgs() << "In Function:" << F.getName() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { for (auto &AllocaSet : NonOverlapedAllocas
) { if (AllocaSet.size() > 1) { dbgs() << "In Function:"
 << F.getName() << "\n"; dbgs() << "Find Union Set "
 << "\n"; dbgs() << "\tAllocas are \n"; for (auto
 Alloca : AllocaSet) dbgs() << "\t\t" << *Alloca <<
 "\n"; } }; } } while (false)
    dbgs() << "Find Union Set "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { for (auto &AllocaSet : NonOverlapedAllocas
) { if (AllocaSet.size() > 1) { dbgs() << "In Function:"
 << F.getName() << "\n"; dbgs() << "Find Union Set "
 << "\n"; dbgs() << "\tAllocas are \n"; for (auto
 Alloca : AllocaSet) dbgs() << "\t\t" << *Alloca <<
 "\n"; } }; } } while (false)
           << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { for (auto &AllocaSet : NonOverlapedAllocas
) { if (AllocaSet.size() > 1) { dbgs() << "In Function:"
 << F.getName() << "\n"; dbgs() << "Find Union Set "
 << "\n"; dbgs() << "\tAllocas are \n"; for (auto
 Alloca : AllocaSet) dbgs() << "\t\t" << *Alloca <<
 "\n"; } }; } } while (false)
    dbgs() << "\tAllocas are \n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { for (auto &AllocaSet : NonOverlapedAllocas
) { if (AllocaSet.size() > 1) { dbgs() << "In Function:"
 << F.getName() << "\n"; dbgs() << "Find Union Set "
 << "\n"; dbgs() << "\tAllocas are \n"; for (auto
 Alloca : AllocaSet) dbgs() << "\t\t" << *Alloca <<
 "\n"; } }; } } while (false)
    for (auto Alloca : AllocaSet)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { for (auto &AllocaSet : NonOverlapedAllocas
) { if (AllocaSet.size() > 1) { dbgs() << "In Function:"
 << F.getName() << "\n"; dbgs() << "Find Union Set "
 << "\n"; dbgs() << "\tAllocas are \n"; for (auto
 Alloca : AllocaSet) dbgs() << "\t\t" << *Alloca <<
 "\n"; } }; } } while (false)
      dbgs() << "\t\t" << *Alloca << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { for (auto &AllocaSet : NonOverlapedAllocas
) { if (AllocaSet.size() > 1) { dbgs() << "In Function:"
 << F.getName() << "\n"; dbgs() << "Find Union Set "
 << "\n"; dbgs() << "\tAllocas are \n"; for (auto
 Alloca : AllocaSet) dbgs() << "\t\t" << *Alloca <<
 "\n"; } }; } } while (false)
  }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { for (auto &AllocaSet : NonOverlapedAllocas
) { if (AllocaSet.size() > 1) { dbgs() << "In Function:"
 << F.getName() << "\n"; dbgs() << "Find Union Set "
 << "\n"; dbgs() << "\tAllocas are \n"; for (auto
 Alloca : AllocaSet) dbgs() << "\t\t" << *Alloca <<
 "\n"; } }; } } while (false)
})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { for (auto &AllocaSet : NonOverlapedAllocas
) { if (AllocaSet.size() > 1) { dbgs() << "In Function:"
 << F.getName() << "\n"; dbgs() << "Find Union Set "
 << "\n"; dbgs() << "\tAllocas are \n"; for (auto
 Alloca : AllocaSet) dbgs() << "\t\t" << *Alloca <<
 "\n"; } }; } } while (false);
701}

703void FrameTypeBuilder::finish(StructType *Ty) {
assert(!IsFinished && "already finished!")(static_cast <bool> (!IsFinished && "already finished!"
) ? void (0) : __assert_fail ("!IsFinished && \"already finished!\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 704, __extension__
 __PRETTY_FUNCTION__));

// Prepare the optimal-layout field array.
// The Id in the layout field is a pointer to our Field for it.
SmallVector<OptimizedStructLayoutField, 8> LayoutFields;
LayoutFields.reserve(Fields.size());
for (auto &Field : Fields) {
  LayoutFields.emplace_back(&Field, Field.Size, Field.Alignment,
                            Field.Offset);
}

// Perform layout.
auto SizeAndAlign = performOptimizedStructLayout(LayoutFields);
StructSize = SizeAndAlign.first;
StructAlign = SizeAndAlign.second;

auto getField = [](const OptimizedStructLayoutField &LayoutField) -> Field & {
  return *static_cast<Field *>(const_cast<void*>(LayoutField.Id));
};

// We need to produce a packed struct type if there's a field whose
// assigned offset isn't a multiple of its natural type alignment.
bool Packed = [&] {
  for (auto &LayoutField : LayoutFields) {
    auto &F = getField(LayoutField);
    if (!isAligned(F.TyAlignment, LayoutField.Offset))
      return true;
  }
  return false;
}();

// Build the struct body.
SmallVector<Type*, 16> FieldTypes;
FieldTypes.reserve(LayoutFields.size() * 3 / 2);
uint64_t LastOffset = 0;
for (auto &LayoutField : LayoutFields) {
  auto &F = getField(LayoutField);

  auto Offset = LayoutField.Offset;

  // Add a padding field if there's a padding gap and we're either
  // building a packed struct or the padding gap is more than we'd
  // get from aligning to the field type's natural alignment.
  assert(Offset >= LastOffset)(static_cast <bool> (Offset >= LastOffset) ? void (0
) : __assert_fail ("Offset >= LastOffset", "llvm/lib/Transforms/Coroutines/CoroFrame.cpp"
, 747, __extension__ __PRETTY_FUNCTION__));
  if (Offset != LastOffset) {
    if (Packed || alignTo(LastOffset, F.TyAlignment) != Offset)
      FieldTypes.push_back(ArrayType::get(Type::getInt8Ty(Context),
                                          Offset - LastOffset));
  }

  F.Offset = Offset;
  F.LayoutFieldIndex = FieldTypes.size();

  FieldTypes.push_back(F.Ty);
  LastOffset = Offset + F.Size;
}

Ty->setBody(FieldTypes, Packed);

763#ifndef NDEBUG
// Check that the IR layout matches the offsets we expect.
auto Layout = DL.getStructLayout(Ty);
for (auto &F : Fields) {
  assert(Ty->getElementType(F.LayoutFieldIndex) == F.Ty)(static_cast <bool> (Ty->getElementType(F.LayoutFieldIndex
) == F.Ty) ? void (0) : __assert_fail ("Ty->getElementType(F.LayoutFieldIndex) == F.Ty"
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 767, __extension__
 __PRETTY_FUNCTION__));
  assert(Layout->getElementOffset(F.LayoutFieldIndex) == F.Offset)(static_cast <bool> (Layout->getElementOffset(F.LayoutFieldIndex
) == F.Offset) ? void (0) : __assert_fail ("Layout->getElementOffset(F.LayoutFieldIndex) == F.Offset"
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 768, __extension__
 __PRETTY_FUNCTION__));
}
770#endif

IsFinished = true;
773}

775static void cacheDIVar(FrameDataInfo &FrameData,
                     DenseMap<Value *, DILocalVariable *> &DIVarCache) {
for (auto *V : FrameData.getAllDefs()) {
  if (DIVarCache.find(V) != DIVarCache.end())
    continue;

  auto DDIs = FindDbgDeclareUses(V);
  auto *I = llvm::find_if(DDIs, [](DbgDeclareInst *DDI) {
    return DDI->getExpression()->getNumElements() == 0;
  });
  if (I != DDIs.end())
    DIVarCache.insert({V, (*I)->getVariable()});
}
788}

790/// Create name for Type. It uses MDString to store new created string to
791/// avoid memory leak.
792static StringRef solveTypeName(Type *Ty) {
if (Ty->isIntegerTy()) {
  // The longest name in common may be '__int_128', which has 9 bits.
  SmallString<16> Buffer;
  raw_svector_ostream OS(Buffer);
  OS << "__int_" << cast<IntegerType>(Ty)->getBitWidth();
  auto *MDName = MDString::get(Ty->getContext(), OS.str());
  return MDName->getString();
}

if (Ty->isFloatingPointTy()) {
  if (Ty->isFloatTy())
    return "__float_";
  if (Ty->isDoubleTy())
    return "__double_";
  return "__floating_type_";
}

if (Ty->isPointerTy()) {
  auto *PtrTy = cast<PointerType>(Ty);
  Type *PointeeTy = PtrTy->getPointerElementType();
  auto Name = solveTypeName(PointeeTy);
  if (Name == "UnknownType")
    return "PointerType";
  SmallString<16> Buffer;
  Twine(Name + "_Ptr").toStringRef(Buffer);
  auto *MDName = MDString::get(Ty->getContext(), Buffer.str());
  return MDName->getString();
}

if (Ty->isStructTy()) {
  if (!cast<StructType>(Ty)->hasName())
    return "__LiteralStructType_";

  auto Name = Ty->getStructName();

  SmallString<16> Buffer(Name);
  for_each(Buffer, [](auto &Iter) {
    if (Iter == '.' || Iter == ':')
      Iter = '_';
  });
  auto *MDName = MDString::get(Ty->getContext(), Buffer.str());
  return MDName->getString();
}

return "UnknownType";
838}

840static DIType *solveDIType(DIBuilder &Builder, Type *Ty,
                         const DataLayout &Layout, DIScope *Scope,
                         unsigned LineNum,
                         DenseMap<Type *, DIType *> &DITypeCache) {
if (DIType *DT = DITypeCache.lookup(Ty))
  return DT;

StringRef Name = solveTypeName(Ty);

DIType *RetType = nullptr;

if (Ty->isIntegerTy()) {
  auto BitWidth = cast<IntegerType>(Ty)->getBitWidth();
  RetType = Builder.createBasicType(Name, BitWidth, dwarf::DW_ATE_signed,
                                    llvm::DINode::FlagArtificial);
} else if (Ty->isFloatingPointTy()) {
  RetType = Builder.createBasicType(Name, Layout.getTypeSizeInBits(Ty),
                                    dwarf::DW_ATE_float,
                                    llvm::DINode::FlagArtificial);
} else if (Ty->isPointerTy()) {
  // Construct BasicType instead of PointerType to avoid infinite
  // search problem.
  // For example, we would be in trouble if we traverse recursively:
  //
  //  struct Node {
  //      Node* ptr;
  //  };
  RetType = Builder.createBasicType(Name, Layout.getTypeSizeInBits(Ty),
                                    dwarf::DW_ATE_address,
                                    llvm::DINode::FlagArtificial);
} else if (Ty->isStructTy()) {
  auto *DIStruct = Builder.createStructType(
      Scope, Name, Scope->getFile(), LineNum, Layout.getTypeSizeInBits(Ty),
      Layout.getPrefTypeAlignment(Ty), llvm::DINode::FlagArtificial, nullptr,
      llvm::DINodeArray());

  auto *StructTy = cast<StructType>(Ty);
  SmallVector<Metadata *, 16> Elements;
  for (unsigned I = 0; I < StructTy->getNumElements(); I++) {
    DIType *DITy = solveDIType(Builder, StructTy->getElementType(I), Layout,
                               Scope, LineNum, DITypeCache);
    assert(DITy)(static_cast <bool> (DITy) ? void (0) : __assert_fail (
"DITy", "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 881, __extension__
 __PRETTY_FUNCTION__));
    Elements.push_back(Builder.createMemberType(
        Scope, DITy->getName(), Scope->getFile(), LineNum,
        DITy->getSizeInBits(), DITy->getAlignInBits(),
        Layout.getStructLayout(StructTy)->getElementOffsetInBits(I),
        llvm::DINode::FlagArtificial, DITy));
  }

  Builder.replaceArrays(DIStruct, Builder.getOrCreateArray(Elements));

  RetType = DIStruct;
} else {
  LLVM_DEBUG(dbgs() << "Unresolved Type: " << *Ty << "\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << "Unresolved Type: " <<
 *Ty << "\n";; } } while (false);
  SmallString<32> Buffer;
  raw_svector_ostream OS(Buffer);
  OS << Name.str() << "_" << Layout.getTypeSizeInBits(Ty);
  RetType = Builder.createBasicType(OS.str(), Layout.getTypeSizeInBits(Ty),
                                    dwarf::DW_ATE_address,
                                    llvm::DINode::FlagArtificial);
}

DITypeCache.insert({Ty, RetType});
return RetType;
904}

906/// Build artificial debug info for C++ coroutine frames to allow users to
907/// inspect the contents of the frame directly
908///
909/// Create Debug information for coroutine frame with debug name "__coro_frame".
910/// The debug information for the fields of coroutine frame is constructed from
911/// the following way:
912/// 1. For all the value in the Frame, we search the use of dbg.declare to find
913///    the corresponding debug variables for the value. If we can find the
914///    debug variable, we can get full and accurate debug information.
915/// 2. If we can't get debug information in step 1 and 2, we could only try to
916///    build the DIType by Type. We did this in solveDIType. We only handle
917///    integer, float, double, integer type and struct type for now.
918static void buildFrameDebugInfo(Function &F, coro::Shape &Shape,
                              FrameDataInfo &FrameData) {
DISubprogram *DIS = F.getSubprogram();
// If there is no DISubprogram for F, it implies the Function are not compiled
// with debug info. So we also don't need to generate debug info for the frame
// neither.
if (!DIS || !DIS->getUnit() ||
    !dwarf::isCPlusPlus(
        (dwarf::SourceLanguage)DIS->getUnit()->getSourceLanguage()))
  return;

assert(Shape.ABI == coro::ABI::Switch &&(static_cast <bool> (Shape.ABI == coro::ABI::Switch &&
 "We could only build debug infomation for C++ coroutine now.\n"
) ? void (0) : __assert_fail ("Shape.ABI == coro::ABI::Switch && \"We could only build debug infomation for C++ coroutine now.\\n\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 930, __extension__
 __PRETTY_FUNCTION__))
       "We could only build debug infomation for C++ coroutine now.\n")(static_cast <bool> (Shape.ABI == coro::ABI::Switch &&
 "We could only build debug infomation for C++ coroutine now.\n"
) ? void (0) : __assert_fail ("Shape.ABI == coro::ABI::Switch && \"We could only build debug infomation for C++ coroutine now.\\n\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 930, __extension__
 __PRETTY_FUNCTION__));

DIBuilder DBuilder(*F.getParent(), /*AllowUnresolved*/ false);

AllocaInst *PromiseAlloca = Shape.getPromiseAlloca();
assert(PromiseAlloca &&(static_cast <bool> (PromiseAlloca && "Coroutine with switch ABI should own Promise alloca"
) ? void (0) : __assert_fail ("PromiseAlloca && \"Coroutine with switch ABI should own Promise alloca\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 936, __extension__
 __PRETTY_FUNCTION__))
       "Coroutine with switch ABI should own Promise alloca")(static_cast <bool> (PromiseAlloca && "Coroutine with switch ABI should own Promise alloca"
) ? void (0) : __assert_fail ("PromiseAlloca && \"Coroutine with switch ABI should own Promise alloca\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 936, __extension__
 __PRETTY_FUNCTION__));

TinyPtrVector<DbgDeclareInst *> DIs = FindDbgDeclareUses(PromiseAlloca);
if (DIs.empty())
  return;

DbgDeclareInst *PromiseDDI = DIs.front();
DILocalVariable *PromiseDIVariable = PromiseDDI->getVariable();
DILocalScope *PromiseDIScope = PromiseDIVariable->getScope();
DIFile *DFile = PromiseDIScope->getFile();
DILocation *DILoc = PromiseDDI->getDebugLoc().get();
unsigned LineNum = PromiseDIVariable->getLine();

DICompositeType *FrameDITy = DBuilder.createStructType(
    DIS, "__coro_frame_ty", DFile, LineNum, Shape.FrameSize * 8,
    Shape.FrameAlign.value() * 8, llvm::DINode::FlagArtificial, nullptr,
    llvm::DINodeArray());
StructType *FrameTy = Shape.FrameTy;
SmallVector<Metadata *, 16> Elements;
DataLayout Layout = F.getParent()->getDataLayout();

DenseMap<Value *, DILocalVariable *> DIVarCache;
cacheDIVar(FrameData, DIVarCache);

unsigned ResumeIndex = coro::Shape::SwitchFieldIndex::Resume;
unsigned DestroyIndex = coro::Shape::SwitchFieldIndex::Destroy;
unsigned IndexIndex = Shape.SwitchLowering.IndexField;

DenseMap<unsigned, StringRef> NameCache;
NameCache.insert({ResumeIndex, "__resume_fn"});
NameCache.insert({DestroyIndex, "__destroy_fn"});
NameCache.insert({IndexIndex, "__coro_index"});

Type *ResumeFnTy = FrameTy->getElementType(ResumeIndex),
     *DestroyFnTy = FrameTy->getElementType(DestroyIndex),
     *IndexTy = FrameTy->getElementType(IndexIndex);

DenseMap<unsigned, DIType *> TyCache;
TyCache.insert({ResumeIndex,
                DBuilder.createBasicType("__resume_fn",
                                         Layout.getTypeSizeInBits(ResumeFnTy),
                                         dwarf::DW_ATE_address)});
TyCache.insert(
    {DestroyIndex, DBuilder.createBasicType(
                       "__destroy_fn", Layout.getTypeSizeInBits(DestroyFnTy),
                       dwarf::DW_ATE_address)});

/// FIXME: If we fill the field `SizeInBits` with the actual size of
/// __coro_index in bits, then __coro_index wouldn't show in the debugger.
TyCache.insert({IndexIndex, DBuilder.createBasicType(
                                "__coro_index",
                                (Layout.getTypeSizeInBits(IndexTy) < 8)
                                    ? 8
                                    : Layout.getTypeSizeInBits(IndexTy),
                                dwarf::DW_ATE_unsigned_char)});

for (auto *V : FrameData.getAllDefs()) {
  if (DIVarCache.find(V) == DIVarCache.end())
    continue;

  auto Index = FrameData.getFieldIndex(V);

  NameCache.insert({Index, DIVarCache[V]->getName()});
  TyCache.insert({Index, DIVarCache[V]->getType()});
}

// Cache from index to (Align, Offset Pair)
DenseMap<unsigned, std::pair<unsigned, unsigned>> OffsetCache;
// The Align and Offset of Resume function and Destroy function are fixed.
OffsetCache.insert({ResumeIndex, {8, 0}});
OffsetCache.insert({DestroyIndex, {8, 8}});
OffsetCache.insert(
    {IndexIndex,
     {Shape.SwitchLowering.IndexAlign, Shape.SwitchLowering.IndexOffset}});

for (auto *V : FrameData.getAllDefs()) {
  auto Index = FrameData.getFieldIndex(V);

  OffsetCache.insert(
      {Index, {FrameData.getAlign(V), FrameData.getOffset(V)}});
}

DenseMap<Type *, DIType *> DITypeCache;
// This counter is used to avoid same type names. e.g., there would be
// many i32 and i64 types in one coroutine. And we would use i32_0 and
// i32_1 to avoid the same type. Since it makes no sense the name of the
// fields confilicts with each other.
unsigned UnknownTypeNum = 0;
for (unsigned Index = 0; Index < FrameTy->getNumElements(); Index++) {
  if (OffsetCache.find(Index) == OffsetCache.end())
    continue;

  std::string Name;
  uint64_t SizeInBits;
  uint32_t AlignInBits;
  uint64_t OffsetInBits;
  DIType *DITy = nullptr;

  Type *Ty = FrameTy->getElementType(Index);
  assert(Ty->isSized() && "We can't handle type which is not sized.\n")(static_cast <bool> (Ty->isSized() && "We can't handle type which is not sized.\n"
) ? void (0) : __assert_fail ("Ty->isSized() && \"We can't handle type which is not sized.\\n\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 1035, __extension__
 __PRETTY_FUNCTION__));
  SizeInBits = Layout.getTypeSizeInBits(Ty).getFixedSize();
  AlignInBits = OffsetCache[Index].first * 8;
  OffsetInBits = OffsetCache[Index].second * 8;

  if (NameCache.find(Index) != NameCache.end()) {
    Name = NameCache[Index].str();
    DITy = TyCache[Index];
  } else {
    DITy = solveDIType(DBuilder, Ty, Layout, FrameDITy, LineNum, DITypeCache);
    assert(DITy && "SolveDIType shouldn't return nullptr.\n")(static_cast <bool> (DITy && "SolveDIType shouldn't return nullptr.\n"
) ? void (0) : __assert_fail ("DITy && \"SolveDIType shouldn't return nullptr.\\n\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 1045, __extension__
 __PRETTY_FUNCTION__));
    Name = DITy->getName().str();
    Name += "_" + std::to_string(UnknownTypeNum);
    UnknownTypeNum++;
  }

  Elements.push_back(DBuilder.createMemberType(
      FrameDITy, Name, DFile, LineNum, SizeInBits, AlignInBits, OffsetInBits,
      llvm::DINode::FlagArtificial, DITy));
}

DBuilder.replaceArrays(FrameDITy, DBuilder.getOrCreateArray(Elements));

auto *FrameDIVar = DBuilder.createAutoVariable(PromiseDIScope, "__coro_frame",
                                               DFile, LineNum, FrameDITy,
                                               true, DINode::FlagArtificial);
assert(FrameDIVar->isValidLocationForIntrinsic(PromiseDDI->getDebugLoc()))(static_cast <bool> (FrameDIVar->isValidLocationForIntrinsic
(PromiseDDI->getDebugLoc())) ? void (0) : __assert_fail ("FrameDIVar->isValidLocationForIntrinsic(PromiseDDI->getDebugLoc())"
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 1061, __extension__
 __PRETTY_FUNCTION__));

// Subprogram would have ContainedNodes field which records the debug
// variables it contained. So we need to add __coro_frame to the
// ContainedNodes of it.
//
// If we don't add __coro_frame to the RetainedNodes, user may get
// `no symbol __coro_frame in context` rather than `__coro_frame`
// is optimized out, which is more precise.
if (auto *SubProgram = dyn_cast<DISubprogram>(PromiseDIScope)) {
  auto RetainedNodes = SubProgram->getRetainedNodes();
  SmallVector<Metadata *, 32> RetainedNodesVec(RetainedNodes.begin(),
                                               RetainedNodes.end());
  RetainedNodesVec.push_back(FrameDIVar);
  SubProgram->replaceOperandWith(
      7, (MDTuple::get(F.getContext(), RetainedNodesVec)));
}

DBuilder.insertDeclare(Shape.FramePtr, FrameDIVar,
                       DBuilder.createExpression(), DILoc,
                       Shape.FramePtr->getNextNode());
1082}

1084// Build a struct that will keep state for an active coroutine.
1085//   struct f.frame {
1086//     ResumeFnTy ResumeFnAddr;
1087//     ResumeFnTy DestroyFnAddr;
1088//     int ResumeIndex;
1089//     ... promise (if present) ...
1090//     ... spills ...
1091//   };
1092static StructType *buildFrameType(Function &F, coro::Shape &Shape,
                                FrameDataInfo &FrameData) {
LLVMContext &C = F.getContext();
const DataLayout &DL = F.getParent()->getDataLayout();
StructType *FrameTy = [&] {
  SmallString<32> Name(F.getName());
  Name.append(".Frame");
  return StructType::create(C, Name);
}();

// We will use this value to cap the alignment of spilled values.
Optional<Align> MaxFrameAlignment;
if (Shape.ABI == coro::ABI::Async)
  MaxFrameAlignment = Shape.AsyncLowering.getContextAlignment();
FrameTypeBuilder B(C, DL, MaxFrameAlignment);

AllocaInst *PromiseAlloca = Shape.getPromiseAlloca();
Optional<FieldIDType> SwitchIndexFieldId;

if (Shape.ABI == coro::ABI::Switch) {
  auto *FramePtrTy = FrameTy->getPointerTo();
  auto *FnTy = FunctionType::get(Type::getVoidTy(C), FramePtrTy,
                                 /*IsVarArg=*/false);
  auto *FnPtrTy = FnTy->getPointerTo();

  // Add header fields for the resume and destroy functions.
  // We can rely on these being perfectly packed.
  (void)B.addField(FnPtrTy, None, /*header*/ true);
  (void)B.addField(FnPtrTy, None, /*header*/ true);

  // PromiseAlloca field needs to be explicitly added here because it's
  // a header field with a fixed offset based on its alignment. Hence it
  // needs special handling and cannot be added to FrameData.Allocas.
  if (PromiseAlloca)
    FrameData.setFieldIndex(
        PromiseAlloca, B.addFieldForAlloca(PromiseAlloca, /*header*/ true));

  // Add a field to store the suspend index.  This doesn't need to
  // be in the header.
  unsigned IndexBits = std::max(1U, Log2_64_Ceil(Shape.CoroSuspends.size()));
  Type *IndexType = Type::getIntNTy(C, IndexBits);

  SwitchIndexFieldId = B.addField(IndexType, None);
} else {
  assert(PromiseAlloca == nullptr && "lowering doesn't support promises")(static_cast <bool> (PromiseAlloca == nullptr &&
 "lowering doesn't support promises") ? void (0) : __assert_fail
 ("PromiseAlloca == nullptr && \"lowering doesn't support promises\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 1136, __extension__
 __PRETTY_FUNCTION__));
}

// Because multiple allocas may own the same field slot,
// we add allocas to field here.
B.addFieldForAllocas(F, FrameData, Shape);
// Add PromiseAlloca to Allocas list so that
// 1. updateLayoutIndex could update its index after
// `performOptimizedStructLayout`
// 2. it is processed in insertSpills.
if (Shape.ABI == coro::ABI::Switch && PromiseAlloca)
  // We assume that the promise alloca won't be modified before
  // CoroBegin and no alias will be create before CoroBegin.
  FrameData.Allocas.emplace_back(
      PromiseAlloca, DenseMap<Instruction *, llvm::Optional<APInt>>{}, false);
// Create an entry for every spilled value.
for (auto &S : FrameData.Spills) {
  Type *FieldType = S.first->getType();
  // For byval arguments, we need to store the pointed value in the frame,
  // instead of the pointer itself.
  if (const Argument *A = dyn_cast<Argument>(S.first))
    if (A->hasByValAttr())
      FieldType = A->getParamByValType();
  FieldIDType Id =
      B.addField(FieldType, None, false /*header*/, true /*IsSpillOfValue*/);
  FrameData.setFieldIndex(S.first, Id);
}

B.finish(FrameTy);
FrameData.updateLayoutIndex(B);
Shape.FrameAlign = B.getStructAlign();
Shape.FrameSize = B.getStructSize();

switch (Shape.ABI) {
case coro::ABI::Switch: {
  // In the switch ABI, remember the switch-index field.
  auto IndexField = B.getLayoutField(*SwitchIndexFieldId);
  Shape.SwitchLowering.IndexField = IndexField.LayoutFieldIndex;
  Shape.SwitchLowering.IndexAlign = IndexField.Alignment.value();
  Shape.SwitchLowering.IndexOffset = IndexField.Offset;

  // Also round the frame size up to a multiple of its alignment, as is
  // generally expected in C/C++.
  Shape.FrameSize = alignTo(Shape.FrameSize, Shape.FrameAlign);
  break;
}

// In the retcon ABI, remember whether the frame is inline in the storage.
case coro::ABI::Retcon:
case coro::ABI::RetconOnce: {
  auto Id = Shape.getRetconCoroId();
  Shape.RetconLowering.IsFrameInlineInStorage
    = (B.getStructSize() <= Id->getStorageSize() &&
       B.getStructAlign() <= Id->getStorageAlignment());
  break;
}
case coro::ABI::Async: {
  Shape.AsyncLowering.FrameOffset =
      alignTo(Shape.AsyncLowering.ContextHeaderSize, Shape.FrameAlign);
  // Also make the final context size a multiple of the context alignment to
  // make allocation easier for allocators.
  Shape.AsyncLowering.ContextSize =
      alignTo(Shape.AsyncLowering.FrameOffset + Shape.FrameSize,
              Shape.AsyncLowering.getContextAlignment());
  if (Shape.AsyncLowering.getContextAlignment() < Shape.FrameAlign) {
    report_fatal_error(
        "The alignment requirment of frame variables cannot be higher than "
        "the alignment of the async function context");
  }
  break;
}
}

return FrameTy;
1210}

1212// We use a pointer use visitor to track how an alloca is being used.
1213// The goal is to be able to answer the following three questions:
1214// 1. Should this alloca be allocated on the frame instead.
1215// 2. Could the content of the alloca be modified prior to CoroBegn, which would
1216// require copying the data from alloca to the frame after CoroBegin.
1217// 3. Is there any alias created for this alloca prior to CoroBegin, but used
1218// after CoroBegin. In that case, we will need to recreate the alias after
1219// CoroBegin based off the frame. To answer question 1, we track two things:
1220//   a. List of all BasicBlocks that use this alloca or any of the aliases of
1221//   the alloca. In the end, we check if there exists any two basic blocks that
1222//   cross suspension points. If so, this alloca must be put on the frame. b.
1223//   Whether the alloca or any alias of the alloca is escaped at some point,
1224//   either by storing the address somewhere, or the address is used in a
1225//   function call that might capture. If it's ever escaped, this alloca must be
1226//   put on the frame conservatively.
1227// To answer quetion 2, we track through the variable MayWriteBeforeCoroBegin.
1228// Whenever a potential write happens, either through a store instruction, a
1229// function call or any of the memory intrinsics, we check whether this
1230// instruction is prior to CoroBegin. To answer question 3, we track the offsets
1231// of all aliases created for the alloca prior to CoroBegin but used after
1232// CoroBegin. llvm::Optional is used to be able to represent the case when the
1233// offset is unknown (e.g. when you have a PHINode that takes in different
1234// offset values). We cannot handle unknown offsets and will assert. This is the
1235// potential issue left out. An ideal solution would likely require a
1236// significant redesign.
1237namespace {
1238struct AllocaUseVisitor : PtrUseVisitor<AllocaUseVisitor> {
using Base = PtrUseVisitor<AllocaUseVisitor>;
AllocaUseVisitor(const DataLayout &DL, const DominatorTree &DT,
                 const CoroBeginInst &CB, const SuspendCrossingInfo &Checker,
                 bool ShouldUseLifetimeStartInfo)
    : PtrUseVisitor(DL), DT(DT), CoroBegin(CB), Checker(Checker),
      ShouldUseLifetimeStartInfo(ShouldUseLifetimeStartInfo) {}

void visit(Instruction &I) {
  Users.insert(&I);
  Base::visit(I);
  // If the pointer is escaped prior to CoroBegin, we have to assume it would
  // be written into before CoroBegin as well.
  if (PI.isEscaped() && !DT.dominates(&CoroBegin, PI.getEscapingInst())) {
    MayWriteBeforeCoroBegin = true;
  }
}
// We need to provide this overload as PtrUseVisitor uses a pointer based
// visiting function.
void visit(Instruction *I) { return visit(*I); }

void visitPHINode(PHINode &I) {
  enqueueUsers(I);
  handleAlias(I);
}

void visitSelectInst(SelectInst &I) {
  enqueueUsers(I);
  handleAlias(I);
}

void visitStoreInst(StoreInst &SI) {
  // Regardless whether the alias of the alloca is the value operand or the
  // pointer operand, we need to assume the alloca is been written.
  handleMayWrite(SI);

  if (SI.getValueOperand() != U->get())
    return;

  // We are storing the pointer into a memory location, potentially escaping.
  // As an optimization, we try to detect simple cases where it doesn't
  // actually escape, for example:
  //   %ptr = alloca ..
  //   %addr = alloca ..
  //   store %ptr, %addr
  //   %x = load %addr
  //   ..
  // If %addr is only used by loading from it, we could simply treat %x as
  // another alias of %ptr, and not considering %ptr being escaped.
  auto IsSimpleStoreThenLoad = [&]() {
    auto *AI = dyn_cast<AllocaInst>(SI.getPointerOperand());
    // If the memory location we are storing to is not an alloca, it
    // could be an alias of some other memory locations, which is difficult
    // to analyze.
    if (!AI)
      return false;
    // StoreAliases contains aliases of the memory location stored into.
    SmallVector<Instruction *, 4> StoreAliases = {AI};
    while (!StoreAliases.empty()) {
      Instruction *I = StoreAliases.pop_back_val();
      for (User *U : I->users()) {
        // If we are loading from the memory location, we are creating an
        // alias of the original pointer.
        if (auto *LI = dyn_cast<LoadInst>(U)) {
          enqueueUsers(*LI);
          handleAlias(*LI);
          continue;
        }
        // If we are overriding the memory location, the pointer certainly
        // won't escape.
        if (auto *S = dyn_cast<StoreInst>(U))
          if (S->getPointerOperand() == I)
            continue;
        if (auto *II = dyn_cast<IntrinsicInst>(U))
          if (II->isLifetimeStartOrEnd())
            continue;
        // BitCastInst creats aliases of the memory location being stored
        // into.
        if (auto *BI = dyn_cast<BitCastInst>(U)) {
          StoreAliases.push_back(BI);
          continue;
        }
        return false;
      }
    }

    return true;
  };

  if (!IsSimpleStoreThenLoad())
    PI.setEscaped(&SI);
}

// All mem intrinsics modify the data.
void visitMemIntrinsic(MemIntrinsic &MI) { handleMayWrite(MI); }

void visitBitCastInst(BitCastInst &BC) {
  Base::visitBitCastInst(BC);
  handleAlias(BC);
}

void visitAddrSpaceCastInst(AddrSpaceCastInst &ASC) {
  Base::visitAddrSpaceCastInst(ASC);
  handleAlias(ASC);
}

void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
  // The base visitor will adjust Offset accordingly.
  Base::visitGetElementPtrInst(GEPI);
  handleAlias(GEPI);
}

void visitIntrinsicInst(IntrinsicInst &II) {
  // When we found the lifetime markers refers to a
  // subrange of the original alloca, ignore the lifetime
  // markers to avoid misleading the analysis.
  if (II.getIntrinsicID() != Intrinsic::lifetime_start || !IsOffsetKnown ||
      !Offset.isZero())
    return Base::visitIntrinsicInst(II);
  LifetimeStarts.insert(&II);
}

void visitCallBase(CallBase &CB) {
  for (unsigned Op = 0, OpCount = CB.arg_size(); Op < OpCount; ++Op)
    if (U->get() == CB.getArgOperand(Op) && !CB.doesNotCapture(Op))
      PI.setEscaped(&CB);
  handleMayWrite(CB);
}

bool getShouldLiveOnFrame() const {
  if (!ShouldLiveOnFrame)
    ShouldLiveOnFrame = computeShouldLiveOnFrame();
  return ShouldLiveOnFrame.getValue();
}

bool getMayWriteBeforeCoroBegin() const { return MayWriteBeforeCoroBegin; }

DenseMap<Instruction *, llvm::Optional<APInt>> getAliasesCopy() const {
  assert(getShouldLiveOnFrame() && "This method should only be called if the "(static_cast <bool> (getShouldLiveOnFrame() && "This method should only be called if the "
 "alloca needs to live on the frame.") ? void (0) : __assert_fail
 ("getShouldLiveOnFrame() && \"This method should only be called if the \" \"alloca needs to live on the frame.\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 1377, __extension__
 __PRETTY_FUNCTION__))
                                   "alloca needs to live on the frame.")(static_cast <bool> (getShouldLiveOnFrame() && "This method should only be called if the "
 "alloca needs to live on the frame.") ? void (0) : __assert_fail
 ("getShouldLiveOnFrame() && \"This method should only be called if the \" \"alloca needs to live on the frame.\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 1377, __extension__
 __PRETTY_FUNCTION__));
  for (const auto &P : AliasOffetMap)
    if (!P.second)
      report_fatal_error("Unable to handle an alias with unknown offset "
                         "created before CoroBegin.");
  return AliasOffetMap;
}

1385private:
const DominatorTree &DT;
const CoroBeginInst &CoroBegin;
const SuspendCrossingInfo &Checker;
// All alias to the original AllocaInst, created before CoroBegin and used
// after CoroBegin. Each entry contains the instruction and the offset in the
// original Alloca. They need to be recreated after CoroBegin off the frame.
DenseMap<Instruction *, llvm::Optional<APInt>> AliasOffetMap{};
SmallPtrSet<Instruction *, 4> Users{};
SmallPtrSet<IntrinsicInst *, 2> LifetimeStarts{};
bool MayWriteBeforeCoroBegin{false};
bool ShouldUseLifetimeStartInfo{true};

mutable llvm::Optional<bool> ShouldLiveOnFrame{};

bool computeShouldLiveOnFrame() const {
  // If lifetime information is available, we check it first since it's
  // more precise. We look at every pair of lifetime.start intrinsic and
  // every basic block that uses the pointer to see if they cross suspension
  // points. The uses cover both direct uses as well as indirect uses.
  if (ShouldUseLifetimeStartInfo && !LifetimeStarts.empty()) {
    for (auto *I : Users)
      for (auto *S : LifetimeStarts)
        if (Checker.isDefinitionAcrossSuspend(*S, I))
          return true;
    return false;
  }
  // FIXME: Ideally the isEscaped check should come at the beginning.
  // However there are a few loose ends that need to be fixed first before
  // we can do that. We need to make sure we are not over-conservative, so
  // that the data accessed in-between await_suspend and symmetric transfer
  // is always put on the stack, and also data accessed after coro.end is
  // always put on the stack (esp the return object). To fix that, we need
  // to:
  //  1) Potentially treat sret as nocapture in calls
  //  2) Special handle the return object and put it on the stack
  //  3) Utilize lifetime.end intrinsic
  if (PI.isEscaped())
    return true;

  for (auto *U1 : Users)
    for (auto *U2 : Users)
      if (Checker.isDefinitionAcrossSuspend(*U1, U2))
        return true;

  return false;
}

void handleMayWrite(const Instruction &I) {
  if (!DT.dominates(&CoroBegin, &I))
    MayWriteBeforeCoroBegin = true;
}

bool usedAfterCoroBegin(Instruction &I) {
  for (auto &U : I.uses())
    if (DT.dominates(&CoroBegin, U))
      return true;
  return false;
}

void handleAlias(Instruction &I) {
  // We track all aliases created prior to CoroBegin but used after.
  // These aliases may need to be recreated after CoroBegin if the alloca
  // need to live on the frame.
  if (DT.dominates(&CoroBegin, &I) || !usedAfterCoroBegin(I))
    return;

  if (!IsOffsetKnown) {
    AliasOffetMap[&I].reset();
  } else {
    auto Itr = AliasOffetMap.find(&I);
    if (Itr == AliasOffetMap.end()) {
      AliasOffetMap[&I] = Offset;
    } else if (Itr->second.hasValue() && Itr->second.getValue() != Offset) {
      // If we have seen two different possible values for this alias, we set
      // it to empty.
      AliasOffetMap[&I].reset();
    }
  }
}
1465};
1466} // namespace

1468// We need to make room to insert a spill after initial PHIs, but before
1469// catchswitch instruction. Placing it before violates the requirement that
1470// catchswitch, like all other EHPads must be the first nonPHI in a block.
1471//
1472// Split away catchswitch into a separate block and insert in its place:
1473//
1474//   cleanuppad <InsertPt> cleanupret.
1475//
1476// cleanupret instruction will act as an insert point for the spill.
1477static Instruction *splitBeforeCatchSwitch(CatchSwitchInst *CatchSwitch) {
BasicBlock *CurrentBlock = CatchSwitch->getParent();
BasicBlock *NewBlock = CurrentBlock->splitBasicBlock(CatchSwitch);
CurrentBlock->getTerminator()->eraseFromParent();

auto *CleanupPad =
    CleanupPadInst::Create(CatchSwitch->getParentPad(), {}, "", CurrentBlock);
auto *CleanupRet =
    CleanupReturnInst::Create(CleanupPad, NewBlock, CurrentBlock);
return CleanupRet;
1487}

1489static void createFramePtr(coro::Shape &Shape) {
auto *CB = Shape.CoroBegin;
IRBuilder<> Builder(CB->getNextNode());
StructType *FrameTy = Shape.FrameTy;
PointerType *FramePtrTy = FrameTy->getPointerTo();
Shape.FramePtr =
    cast<Instruction>(Builder.CreateBitCast(CB, FramePtrTy, "FramePtr"));
1496}

1498// Replace all alloca and SSA values that are accessed across suspend points
1499// with GetElementPointer from coroutine frame + loads and stores. Create an
1500// AllocaSpillBB that will become the new entry block for the resume parts of
1501// the coroutine:
1502//
1503//    %hdl = coro.begin(...)
1504//    whatever
1505//
1506// becomes:
1507//
1508//    %hdl = coro.begin(...)
1509//    %FramePtr = bitcast i8* hdl to %f.frame*
1510//    br label %AllocaSpillBB
1511//
1512//  AllocaSpillBB:
1513//    ; geps corresponding to allocas that were moved to coroutine frame
1514//    br label PostSpill
1515//
1516//  PostSpill:
1517//    whatever
1518//
1519//
1520static Instruction *insertSpills(const FrameDataInfo &FrameData,
                               coro::Shape &Shape) {
auto *CB = Shape.CoroBegin;
LLVMContext &C = CB->getContext();
IRBuilder<> Builder(C);
StructType *FrameTy = Shape.FrameTy;
Instruction *FramePtr = Shape.FramePtr;
DominatorTree DT(*CB->getFunction());
SmallDenseMap<llvm::Value *, llvm::AllocaInst *, 4> DbgPtrAllocaCache;

// Create a GEP with the given index into the coroutine frame for the original
// value Orig. Appends an extra 0 index for array-allocas, preserving the
// original type.
auto GetFramePointer = [&](Value *Orig) -> Value * {
  FieldIDType Index = FrameData.getFieldIndex(Orig);
  SmallVector<Value *, 3> Indices = {
      ConstantInt::get(Type::getInt32Ty(C), 0),
      ConstantInt::get(Type::getInt32Ty(C), Index),
  };

  if (auto *AI = dyn_cast<AllocaInst>(Orig)) {
    if (auto *CI = dyn_cast<ConstantInt>(AI->getArraySize())) {
      auto Count = CI->getValue().getZExtValue();
      if (Count > 1) {
        Indices.push_back(ConstantInt::get(Type::getInt32Ty(C), 0));
      }
    } else {
      report_fatal_error("Coroutines cannot handle non static allocas yet");
    }
  }

  auto GEP = cast<GetElementPtrInst>(
      Builder.CreateInBoundsGEP(FrameTy, FramePtr, Indices));
  if (isa<AllocaInst>(Orig)) {
    // If the type of GEP is not equal to the type of AllocaInst, it implies
    // that the AllocaInst may be reused in the Frame slot of other
    // AllocaInst. So We cast GEP to the AllocaInst here to re-use
    // the Frame storage.
    //
    // Note: If we change the strategy dealing with alignment, we need to refine
    // this casting.
    if (GEP->getResultElementType() != Orig->getType())
      return Builder.CreateBitCast(GEP, Orig->getType(),
                                   Orig->getName() + Twine(".cast"));
  }
  return GEP;
};

for (auto const &E : FrameData.Spills) {
  Value *Def = E.first;
  auto SpillAlignment = Align(FrameData.getAlign(Def));
  // Create a store instruction storing the value into the
  // coroutine frame.
  Instruction *InsertPt = nullptr;
  Type *ByValTy = nullptr;
  if (auto *Arg = dyn_cast<Argument>(Def)) {
    // For arguments, we will place the store instruction right after
    // the coroutine frame pointer instruction, i.e. bitcast of
    // coro.begin from i8* to %f.frame*.
    InsertPt = FramePtr->getNextNode();

    // If we're spilling an Argument, make sure we clear 'nocapture'
    // from the coroutine function.
    Arg->getParent()->removeParamAttr(Arg->getArgNo(), Attribute::NoCapture);

    if (Arg->hasByValAttr())
      ByValTy = Arg->getParamByValType();
  } else if (auto *CSI = dyn_cast<AnyCoroSuspendInst>(Def)) {
    // Don't spill immediately after a suspend; splitting assumes
    // that the suspend will be followed by a branch.
    InsertPt = CSI->getParent()->getSingleSuccessor()->getFirstNonPHI();
  } else {
    auto *I = cast<Instruction>(Def);
    if (!DT.dominates(CB, I)) {
      // If it is not dominated by CoroBegin, then spill should be
      // inserted immediately after CoroFrame is computed.
      InsertPt = FramePtr->getNextNode();
    } else if (auto *II = dyn_cast<InvokeInst>(I)) {
      // If we are spilling the result of the invoke instruction, split
      // the normal edge and insert the spill in the new block.
      auto *NewBB = SplitEdge(II->getParent(), II->getNormalDest());
      InsertPt = NewBB->getTerminator();
    } else if (isa<PHINode>(I)) {
      // Skip the PHINodes and EH pads instructions.
      BasicBlock *DefBlock = I->getParent();
      if (auto *CSI = dyn_cast<CatchSwitchInst>(DefBlock->getTerminator()))
        InsertPt = splitBeforeCatchSwitch(CSI);
      else
        InsertPt = &*DefBlock->getFirstInsertionPt();
    } else {
      assert(!I->isTerminator() && "unexpected terminator")(static_cast <bool> (!I->isTerminator() && "unexpected terminator"
) ? void (0) : __assert_fail ("!I->isTerminator() && \"unexpected terminator\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 1610, __extension__
 __PRETTY_FUNCTION__));
      // For all other values, the spill is placed immediately after
      // the definition.
      InsertPt = I->getNextNode();
    }
  }

  auto Index = FrameData.getFieldIndex(Def);
  Builder.SetInsertPoint(InsertPt);
  auto *G = Builder.CreateConstInBoundsGEP2_32(
      FrameTy, FramePtr, 0, Index, Def->getName() + Twine(".spill.addr"));
  if (ByValTy) {
    // For byval arguments, we need to store the pointed value in the frame,
    // instead of the pointer itself.
    auto *Value = Builder.CreateLoad(ByValTy, Def);
    Builder.CreateAlignedStore(Value, G, SpillAlignment);
  } else {
    Builder.CreateAlignedStore(Def, G, SpillAlignment);
  }

  BasicBlock *CurrentBlock = nullptr;
  Value *CurrentReload = nullptr;
  for (auto *U : E.second) {
    // If we have not seen the use block, create a load instruction to reload
    // the spilled value from the coroutine frame. Populates the Value pointer
    // reference provided with the frame GEP.
    if (CurrentBlock != U->getParent()) {
      CurrentBlock = U->getParent();
      Builder.SetInsertPoint(&*CurrentBlock->getFirstInsertionPt());

      auto *GEP = GetFramePointer(E.first);
      GEP->setName(E.first->getName() + Twine(".reload.addr"));
      if (ByValTy)
        CurrentReload = GEP;
      else
        CurrentReload = Builder.CreateAlignedLoad(
            FrameTy->getElementType(FrameData.getFieldIndex(E.first)), GEP,
            SpillAlignment, E.first->getName() + Twine(".reload"));

      TinyPtrVector<DbgDeclareInst *> DIs = FindDbgDeclareUses(Def);
      for (DbgDeclareInst *DDI : DIs) {
        bool AllowUnresolved = false;
        // This dbg.declare is preserved for all coro-split function
        // fragments. It will be unreachable in the main function, and
        // processed by coro::salvageDebugInfo() by CoroCloner.
        DIBuilder(*CurrentBlock->getParent()->getParent(), AllowUnresolved)
            .insertDeclare(CurrentReload, DDI->getVariable(),
                           DDI->getExpression(), DDI->getDebugLoc(),
                           &*Builder.GetInsertPoint());
        // This dbg.declare is for the main function entry point.  It
        // will be deleted in all coro-split functions.
        coro::salvageDebugInfo(DbgPtrAllocaCache, DDI, Shape.OptimizeFrame);
      }
    }

    // If we have a single edge PHINode, remove it and replace it with a
    // reload from the coroutine frame. (We already took care of multi edge
    // PHINodes by rewriting them in the rewritePHIs function).
    if (auto *PN = dyn_cast<PHINode>(U)) {
      assert(PN->getNumIncomingValues() == 1 &&(static_cast <bool> (PN->getNumIncomingValues() == 1
 && "unexpected number of incoming " "values in the PHINode"
) ? void (0) : __assert_fail ("PN->getNumIncomingValues() == 1 && \"unexpected number of incoming \" \"values in the PHINode\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 1671, __extension__
 __PRETTY_FUNCTION__))
             "unexpected number of incoming "(static_cast <bool> (PN->getNumIncomingValues() == 1
 && "unexpected number of incoming " "values in the PHINode"
) ? void (0) : __assert_fail ("PN->getNumIncomingValues() == 1 && \"unexpected number of incoming \" \"values in the PHINode\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 1671, __extension__
 __PRETTY_FUNCTION__))
             "values in the PHINode")(static_cast <bool> (PN->getNumIncomingValues() == 1
 && "unexpected number of incoming " "values in the PHINode"
) ? void (0) : __assert_fail ("PN->getNumIncomingValues() == 1 && \"unexpected number of incoming \" \"values in the PHINode\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 1671, __extension__
 __PRETTY_FUNCTION__));
      PN->replaceAllUsesWith(CurrentReload);
      PN->eraseFromParent();
      continue;
    }

    // Replace all uses of CurrentValue in the current instruction with
    // reload.
    U->replaceUsesOfWith(Def, CurrentReload);
  }
}

BasicBlock *FramePtrBB = FramePtr->getParent();

auto SpillBlock =
    FramePtrBB->splitBasicBlock(FramePtr->getNextNode(), "AllocaSpillBB");
SpillBlock->splitBasicBlock(&SpillBlock->front(), "PostSpill");
Shape.AllocaSpillBlock = SpillBlock;

// retcon and retcon.once lowering assumes all uses have been sunk.
if (Shape.ABI == coro::ABI::Retcon || Shape.ABI == coro::ABI::RetconOnce ||
    Shape.ABI == coro::ABI::Async) {
  // If we found any allocas, replace all of their remaining uses with Geps.
  Builder.SetInsertPoint(&SpillBlock->front());
  for (const auto &P : FrameData.Allocas) {
    AllocaInst *Alloca = P.Alloca;
    auto *G = GetFramePointer(Alloca);

    // We are not using ReplaceInstWithInst(P.first, cast<Instruction>(G))
    // here, as we are changing location of the instruction.
    G->takeName(Alloca);
    Alloca->replaceAllUsesWith(G);
    Alloca->eraseFromParent();
  }
  return FramePtr;
}

// If we found any alloca, replace all of their remaining uses with GEP
// instructions. To remain debugbility, we replace the uses of allocas for
// dbg.declares and dbg.values with the reload from the frame.
// Note: We cannot replace the alloca with GEP instructions indiscriminately,
// as some of the uses may not be dominated by CoroBegin.
Builder.SetInsertPoint(&Shape.AllocaSpillBlock->front());
SmallVector<Instruction *, 4> UsersToUpdate;
for (const auto &A : FrameData.Allocas) {
  AllocaInst *Alloca = A.Alloca;
  UsersToUpdate.clear();
  for (User *U : Alloca->users()) {
    auto *I = cast<Instruction>(U);
    if (DT.dominates(CB, I))
      UsersToUpdate.push_back(I);
  }
  if (UsersToUpdate.empty())
    continue;
  auto *G = GetFramePointer(Alloca);
  G->setName(Alloca->getName() + Twine(".reload.addr"));

  SmallVector<DbgVariableIntrinsic *, 4> DIs;
  findDbgUsers(DIs, Alloca);
  for (auto *DVI : DIs)
    DVI->replaceUsesOfWith(Alloca, G);

  for (Instruction *I : UsersToUpdate)
    I->replaceUsesOfWith(Alloca, G);
}
Builder.SetInsertPoint(FramePtr->getNextNode());
for (const auto &A : FrameData.Allocas) {
  AllocaInst *Alloca = A.Alloca;
  if (A.MayWriteBeforeCoroBegin) {
    // isEscaped really means potentially modified before CoroBegin.
    if (Alloca->isArrayAllocation())
      report_fatal_error(
          "Coroutines cannot handle copying of array allocas yet");

    auto *G = GetFramePointer(Alloca);
    auto *Value = Builder.CreateLoad(Alloca->getAllocatedType(), Alloca);
    Builder.CreateStore(Value, G);
  }
  // For each alias to Alloca created before CoroBegin but used after
  // CoroBegin, we recreate them after CoroBegin by appplying the offset
  // to the pointer in the frame.
  for (const auto &Alias : A.Aliases) {
    auto *FramePtr = GetFramePointer(Alloca);
    auto *FramePtrRaw =
        Builder.CreateBitCast(FramePtr, Type::getInt8PtrTy(C));
    auto *AliasPtr = Builder.CreateGEP(
        Type::getInt8Ty(C), FramePtrRaw,
        ConstantInt::get(Type::getInt64Ty(C), Alias.second.getValue()));
    auto *AliasPtrTyped =
        Builder.CreateBitCast(AliasPtr, Alias.first->getType());
    Alias.first->replaceUsesWithIf(
        AliasPtrTyped, [&](Use &U) { return DT.dominates(CB, U); });
  }
}
return FramePtr;
1766}

1768// Moves the values in the PHIs in SuccBB that correspong to PredBB into a new
1769// PHI in InsertedBB.
1770static void movePHIValuesToInsertedBlock(BasicBlock *SuccBB,
                                       BasicBlock *InsertedBB,
                                       BasicBlock *PredBB,
                                       PHINode *UntilPHI = nullptr) {
auto *PN = cast<PHINode>(&SuccBB->front());
do {
  int Index = PN->getBasicBlockIndex(InsertedBB);
  Value *V = PN->getIncomingValue(Index);
  PHINode *InputV = PHINode::Create(
      V->getType(), 1, V->getName() + Twine(".") + SuccBB->getName(),
      &InsertedBB->front());
  InputV->addIncoming(V, PredBB);
  PN->setIncomingValue(Index, InputV);
  PN = dyn_cast<PHINode>(PN->getNextNode());
} while (PN != UntilPHI);
1785}

1787// Rewrites the PHI Nodes in a cleanuppad.
1788static void rewritePHIsForCleanupPad(BasicBlock *CleanupPadBB,
                                   CleanupPadInst *CleanupPad) {
// For every incoming edge to a CleanupPad we will create a new block holding
// all incoming values in single-value PHI nodes. We will then create another
// block to act as a dispather (as all unwind edges for related EH blocks
// must be the same).
//
// cleanuppad:
//    %2 = phi i32[%0, %catchswitch], [%1, %catch.1]
//    %3 = cleanuppad within none []
//
// It will create:
//
// cleanuppad.corodispatch
//    %2 = phi i8[0, %catchswitch], [1, %catch.1]
//    %3 = cleanuppad within none []
//    switch i8 % 2, label %unreachable
//            [i8 0, label %cleanuppad.from.catchswitch
//             i8 1, label %cleanuppad.from.catch.1]
// cleanuppad.from.catchswitch:
//    %4 = phi i32 [%0, %catchswitch]
//    br %label cleanuppad
// cleanuppad.from.catch.1:
//    %6 = phi i32 [%1, %catch.1]
//    br %label cleanuppad
// cleanuppad:
//    %8 = phi i32 [%4, %cleanuppad.from.catchswitch],
//                 [%6, %cleanuppad.from.catch.1]

// Unreachable BB, in case switching on an invalid value in the dispatcher.
auto *UnreachBB = BasicBlock::Create(
    CleanupPadBB->getContext(), "unreachable", CleanupPadBB->getParent());
IRBuilder<> Builder(UnreachBB);
Builder.CreateUnreachable();

// Create a new cleanuppad which will be the dispatcher.
auto *NewCleanupPadBB =
    BasicBlock::Create(CleanupPadBB->getContext(),
                       CleanupPadBB->getName() + Twine(".corodispatch"),
                       CleanupPadBB->getParent(), CleanupPadBB);
Builder.SetInsertPoint(NewCleanupPadBB);
auto *SwitchType = Builder.getInt8Ty();
auto *SetDispatchValuePN =
    Builder.CreatePHI(SwitchType, pred_size(CleanupPadBB));
CleanupPad->removeFromParent();
CleanupPad->insertAfter(SetDispatchValuePN);
auto *SwitchOnDispatch = Builder.CreateSwitch(SetDispatchValuePN, UnreachBB,
                                              pred_size(CleanupPadBB));

int SwitchIndex = 0;
SmallVector<BasicBlock *, 8> Preds(predecessors(CleanupPadBB));
for (BasicBlock *Pred : Preds) {
  // Create a new cleanuppad and move the PHI values to there.
  auto *CaseBB = BasicBlock::Create(CleanupPadBB->getContext(),
                                    CleanupPadBB->getName() +
                                        Twine(".from.") + Pred->getName(),
                                    CleanupPadBB->getParent(), CleanupPadBB);
  updatePhiNodes(CleanupPadBB, Pred, CaseBB);
  CaseBB->setName(CleanupPadBB->getName() + Twine(".from.") +
                  Pred->getName());
  Builder.SetInsertPoint(CaseBB);
  Builder.CreateBr(CleanupPadBB);
  movePHIValuesToInsertedBlock(CleanupPadBB, CaseBB, NewCleanupPadBB);

  // Update this Pred to the new unwind point.
  setUnwindEdgeTo(Pred->getTerminator(), NewCleanupPadBB);

  // Setup the switch in the dispatcher.
  auto *SwitchConstant = ConstantInt::get(SwitchType, SwitchIndex);
  SetDispatchValuePN->addIncoming(SwitchConstant, Pred);
  SwitchOnDispatch->addCase(SwitchConstant, CaseBB);
  SwitchIndex++;
}
1861}

1863static void cleanupSinglePredPHIs(Function &F) {
SmallVector<PHINode *, 32> Worklist;
for (auto &BB : F) {
  for (auto &Phi : BB.phis()) {
    if (Phi.getNumIncomingValues() == 1) {
      Worklist.push_back(&Phi);
    } else
      break;
  }
}
while (!Worklist.empty()) {
  auto *Phi = Worklist.pop_back_val();
  auto *OriginalValue = Phi->getIncomingValue(0);
  Phi->replaceAllUsesWith(OriginalValue);
}
1878}

1880static void rewritePHIs(BasicBlock &BB) {
// For every incoming edge we will create a block holding all
// incoming values in a single PHI nodes.
//
// loop:
//    %n.val = phi i32[%n, %entry], [%inc, %loop]
//
// It will create:
//
// loop.from.entry:
//    %n.loop.pre = phi i32 [%n, %entry]
//    br %label loop
// loop.from.loop:
//    %inc.loop.pre = phi i32 [%inc, %loop]
//    br %label loop
//
// After this rewrite, further analysis will ignore any phi nodes with more
// than one incoming edge.

// TODO: Simplify PHINodes in the basic block to remove duplicate
// predecessors.

// Special case for CleanupPad: all EH blocks must have the same unwind edge
// so we need to create an additional "dispatcher" block.
if (auto *CleanupPad =
        dyn_cast_or_null<CleanupPadInst>(BB.getFirstNonPHI())) {
  SmallVector<BasicBlock *, 8> Preds(predecessors(&BB));
  for (BasicBlock *Pred : Preds) {
    if (CatchSwitchInst *CS =
            dyn_cast<CatchSwitchInst>(Pred->getTerminator())) {
      // CleanupPad with a CatchSwitch predecessor: therefore this is an
      // unwind destination that needs to be handle specially.
      assert(CS->getUnwindDest() == &BB)(static_cast <bool> (CS->getUnwindDest() == &BB)
 ? void (0) : __assert_fail ("CS->getUnwindDest() == &BB"
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 1912, __extension__
 __PRETTY_FUNCTION__));
      (void)CS;
      rewritePHIsForCleanupPad(&BB, CleanupPad);
      return;
    }
  }
}

LandingPadInst *LandingPad = nullptr;
PHINode *ReplPHI = nullptr;
if ((LandingPad = dyn_cast_or_null<LandingPadInst>(BB.getFirstNonPHI()))) {
  // ehAwareSplitEdge will clone the LandingPad in all the edge blocks.
  // We replace the original landing pad with a PHINode that will collect the
  // results from all of them.
  ReplPHI = PHINode::Create(LandingPad->getType(), 1, "", LandingPad);
  ReplPHI->takeName(LandingPad);
  LandingPad->replaceAllUsesWith(ReplPHI);
  // We will erase the original landing pad at the end of this function after
  // ehAwareSplitEdge cloned it in the transition blocks.
}

SmallVector<BasicBlock *, 8> Preds(predecessors(&BB));
for (BasicBlock *Pred : Preds) {
  auto *IncomingBB = ehAwareSplitEdge(Pred, &BB, LandingPad, ReplPHI);
  IncomingBB->setName(BB.getName() + Twine(".from.") + Pred->getName());

  // Stop the moving of values at ReplPHI, as this is either null or the PHI
  // that replaced the landing pad.
  movePHIValuesToInsertedBlock(&BB, IncomingBB, Pred, ReplPHI);
}

if (LandingPad) {
  // Calls to ehAwareSplitEdge function cloned the original lading pad.
  // No longer need it.
  LandingPad->eraseFromParent();
}
1948}

1950static void rewritePHIs(Function &F) {
SmallVector<BasicBlock *, 8> WorkList;

for (BasicBlock &BB : F)
  if (auto *PN = dyn_cast<PHINode>(&BB.front()))
    if (PN->getNumIncomingValues() > 1)
      WorkList.push_back(&BB);

for (BasicBlock *BB : WorkList)
  rewritePHIs(*BB);
1960}

1962// Check for instructions that we can recreate on resume as opposed to spill
1963// the result into a coroutine frame.
1964static bool materializable(Instruction &V) {
return isa<CastInst>(&V) || isa<GetElementPtrInst>(&V) ||
       isa<BinaryOperator>(&V) || isa<CmpInst>(&V) || isa<SelectInst>(&V);
1967}

1969// Check for structural coroutine intrinsics that should not be spilled into
1970// the coroutine frame.
1971static bool isCoroutineStructureIntrinsic(Instruction &I) {
return isa<CoroIdInst>(&I) || isa<CoroSaveInst>(&I) ||
       isa<CoroSuspendInst>(&I);
1974}

1976// For every use of the value that is across suspend point, recreate that value
1977// after a suspend point.
1978static void rewriteMaterializableInstructions(IRBuilder<> &IRB,
                                            const SpillInfo &Spills) {
for (const auto &E : Spills) {
  Value *Def = E.first;
  BasicBlock *CurrentBlock = nullptr;
  Instruction *CurrentMaterialization = nullptr;
  for (Instruction *U : E.second) {
    // If we have not seen this block, materialize the value.
    if (CurrentBlock != U->getParent()) {

      bool IsInCoroSuspendBlock = isa<AnyCoroSuspendInst>(U);
      CurrentBlock = U->getParent();
      auto *InsertBlock = IsInCoroSuspendBlock
                              ? CurrentBlock->getSinglePredecessor()
                              : CurrentBlock;
      CurrentMaterialization = cast<Instruction>(Def)->clone();
      CurrentMaterialization->setName(Def->getName());
      CurrentMaterialization->insertBefore(
          IsInCoroSuspendBlock ? InsertBlock->getTerminator()
                               : &*InsertBlock->getFirstInsertionPt());
    }
    if (auto *PN = dyn_cast<PHINode>(U)) {
      assert(PN->getNumIncomingValues() == 1 &&(static_cast <bool> (PN->getNumIncomingValues() == 1
 && "unexpected number of incoming " "values in the PHINode"
) ? void (0) : __assert_fail ("PN->getNumIncomingValues() == 1 && \"unexpected number of incoming \" \"values in the PHINode\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 2002, __extension__
 __PRETTY_FUNCTION__))
             "unexpected number of incoming "(static_cast <bool> (PN->getNumIncomingValues() == 1
 && "unexpected number of incoming " "values in the PHINode"
) ? void (0) : __assert_fail ("PN->getNumIncomingValues() == 1 && \"unexpected number of incoming \" \"values in the PHINode\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 2002, __extension__
 __PRETTY_FUNCTION__))
             "values in the PHINode")(static_cast <bool> (PN->getNumIncomingValues() == 1
 && "unexpected number of incoming " "values in the PHINode"
) ? void (0) : __assert_fail ("PN->getNumIncomingValues() == 1 && \"unexpected number of incoming \" \"values in the PHINode\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 2002, __extension__
 __PRETTY_FUNCTION__));
      PN->replaceAllUsesWith(CurrentMaterialization);
      PN->eraseFromParent();
      continue;
    }
    // Replace all uses of Def in the current instruction with the
    // CurrentMaterialization for the block.
    U->replaceUsesOfWith(Def, CurrentMaterialization);
  }
}
2012}

2014// Splits the block at a particular instruction unless it is the first
2015// instruction in the block with a single predecessor.
2016static BasicBlock *splitBlockIfNotFirst(Instruction *I, const Twine &Name) {
auto *BB = I->getParent();
if (&BB->front() == I) {
  if (BB->getSinglePredecessor()) {
    BB->setName(Name);
    return BB;
  }
}
return BB->splitBasicBlock(I, Name);
2025}

2027// Split above and below a particular instruction so that it
2028// will be all alone by itself in a block.
2029static void splitAround(Instruction *I, const Twine &Name) {
splitBlockIfNotFirst(I, Name);
splitBlockIfNotFirst(I->getNextNode(), "After" + Name);
2032}

2034static bool isSuspendBlock(BasicBlock *BB) {
return isa<AnyCoroSuspendInst>(BB->front());
2036}

2038typedef SmallPtrSet<BasicBlock*, 8> VisitedBlocksSet;

2040/// Does control flow starting at the given block ever reach a suspend
2041/// instruction before reaching a block in VisitedOrFreeBBs?
2042static bool isSuspendReachableFrom(BasicBlock *From,
                                 VisitedBlocksSet &VisitedOrFreeBBs) {
// Eagerly try to add this block to the visited set.  If it's already
// there, stop recursing; this path doesn't reach a suspend before
// either looping or reaching a freeing block.
if (!VisitedOrFreeBBs.insert(From).second)
  return false;

// We assume that we'll already have split suspends into their own blocks.
if (isSuspendBlock(From))
  return true;

// Recurse on the successors.
for (auto Succ : successors(From)) {
  if (isSuspendReachableFrom(Succ, VisitedOrFreeBBs))
    return true;
}

return false;
2061}

2063/// Is the given alloca "local", i.e. bounded in lifetime to not cross a
2064/// suspend point?
2065static bool isLocalAlloca(CoroAllocaAllocInst *AI) {
// Seed the visited set with all the basic blocks containing a free
// so that we won't pass them up.
VisitedBlocksSet VisitedOrFreeBBs;
for (auto User : AI->users()) {
  if (auto FI = dyn_cast<CoroAllocaFreeInst>(User))
    VisitedOrFreeBBs.insert(FI->getParent());
}

return !isSuspendReachableFrom(AI->getParent(), VisitedOrFreeBBs);
2075}

2077/// After we split the coroutine, will the given basic block be along
2078/// an obvious exit path for the resumption function?
2079static bool willLeaveFunctionImmediatelyAfter(BasicBlock *BB,
                                            unsigned depth = 3) {
// If we've bottomed out our depth count, stop searching and assume
// that the path might loop back.
if (depth == 0) return false;

// If this is a suspend block, we're about to exit the resumption function.
if (isSuspendBlock(BB)) return true;

// Recurse into the successors.
for (auto Succ : successors(BB)) {
  if (!willLeaveFunctionImmediatelyAfter(Succ, depth - 1))
    return false;
}

// If none of the successors leads back in a loop, we're on an exit/abort.
return true;
2096}

2098static bool localAllocaNeedsStackSave(CoroAllocaAllocInst *AI) {
// Look for a free that isn't sufficiently obviously followed by
// either a suspend or a termination, i.e. something that will leave
// the coro resumption frame.
for (auto U : AI->users()) {
  auto FI = dyn_cast<CoroAllocaFreeInst>(U);
  if (!FI) continue;

  if (!willLeaveFunctionImmediatelyAfter(FI->getParent()))
    return true;
}

// If we never found one, we don't need a stack save.
return false;
2112}

2114/// Turn each of the given local allocas into a normal (dynamic) alloca
2115/// instruction.
2116static void lowerLocalAllocas(ArrayRef<CoroAllocaAllocInst*> LocalAllocas,
                            SmallVectorImpl<Instruction*> &DeadInsts) {
for (auto AI : LocalAllocas) {
  auto M = AI->getModule();
  IRBuilder<> Builder(AI);

  // Save the stack depth.  Try to avoid doing this if the stackrestore
  // is going to immediately precede a return or something.
  Value *StackSave = nullptr;
  if (localAllocaNeedsStackSave(AI))
    StackSave = Builder.CreateCall(
                          Intrinsic::getDeclaration(M, Intrinsic::stacksave));

  // Allocate memory.
  auto Alloca = Builder.CreateAlloca(Builder.getInt8Ty(), AI->getSize());
  Alloca->setAlignment(Align(AI->getAlignment()));

  for (auto U : AI->users()) {
    // Replace gets with the allocation.
    if (isa<CoroAllocaGetInst>(U)) {
      U->replaceAllUsesWith(Alloca);

    // Replace frees with stackrestores.  This is safe because
    // alloca.alloc is required to obey a stack discipline, although we
    // don't enforce that structurally.
    } else {
      auto FI = cast<CoroAllocaFreeInst>(U);
      if (StackSave) {
        Builder.SetInsertPoint(FI);
        Builder.CreateCall(
                  Intrinsic::getDeclaration(M, Intrinsic::stackrestore),
                           StackSave);
      }
    }
    DeadInsts.push_back(cast<Instruction>(U));
  }

  DeadInsts.push_back(AI);
}
2155}

2157/// Turn the given coro.alloca.alloc call into a dynamic allocation.
2158/// This happens during the all-instructions iteration, so it must not
2159/// delete the call.
2160static Instruction *lowerNonLocalAlloca(CoroAllocaAllocInst *AI,
                                      coro::Shape &Shape,
                                 SmallVectorImpl<Instruction*> &DeadInsts) {
IRBuilder<> Builder(AI);
auto Alloc = Shape.emitAlloc(Builder, AI->getSize(), nullptr);

for (User *U : AI->users()) {
  if (isa<CoroAllocaGetInst>(U)) {
    U->replaceAllUsesWith(Alloc);
  } else {
    auto FI = cast<CoroAllocaFreeInst>(U);
    Builder.SetInsertPoint(FI);
    Shape.emitDealloc(Builder, Alloc, nullptr);
  }
  DeadInsts.push_back(cast<Instruction>(U));
}

// Push this on last so that it gets deleted after all the others.
DeadInsts.push_back(AI);

// Return the new allocation value so that we can check for needed spills.
return cast<Instruction>(Alloc);
2182}

2184/// Get the current swifterror value.
2185static Value *emitGetSwiftErrorValue(IRBuilder<> &Builder, Type *ValueTy,
                                   coro::Shape &Shape) {
// Make a fake function pointer as a sort of intrinsic.
auto FnTy = FunctionType::get(ValueTy, {}, false);
auto Fn = ConstantPointerNull::get(FnTy->getPointerTo());

auto Call = Builder.CreateCall(FnTy, Fn, {});
Shape.SwiftErrorOps.push_back(Call);

return Call;
2195}

2197/// Set the given value as the current swifterror value.
2198///
2199/// Returns a slot that can be used as a swifterror slot.
2200static Value *emitSetSwiftErrorValue(IRBuilder<> &Builder, Value *V,
                                   coro::Shape &Shape) {
// Make a fake function pointer as a sort of intrinsic.
auto FnTy = FunctionType::get(V->getType()->getPointerTo(),
                              {V->getType()}, false);
auto Fn = ConstantPointerNull::get(FnTy->getPointerTo());

auto Call = Builder.CreateCall(FnTy, Fn, { V });
Shape.SwiftErrorOps.push_back(Call);

return Call;
2211}

2213/// Set the swifterror value from the given alloca before a call,
2214/// then put in back in the alloca afterwards.
2215///
2216/// Returns an address that will stand in for the swifterror slot
2217/// until splitting.
2218static Value *emitSetAndGetSwiftErrorValueAround(Instruction *Call,
                                               AllocaInst *Alloca,
                                               coro::Shape &Shape) {
auto ValueTy = Alloca->getAllocatedType();
IRBuilder<> Builder(Call);

// Load the current value from the alloca and set it as the
// swifterror value.
auto ValueBeforeCall = Builder.CreateLoad(ValueTy, Alloca);
auto Addr = emitSetSwiftErrorValue(Builder, ValueBeforeCall, Shape);

// Move to after the call.  Since swifterror only has a guaranteed
// value on normal exits, we can ignore implicit and explicit unwind
// edges.
if (isa<CallInst>(Call)) {
  Builder.SetInsertPoint(Call->getNextNode());
} else {
  auto Invoke = cast<InvokeInst>(Call);
  Builder.SetInsertPoint(Invoke->getNormalDest()->getFirstNonPHIOrDbg());
}

// Get the current swifterror value and store it to the alloca.
auto ValueAfterCall = emitGetSwiftErrorValue(Builder, ValueTy, Shape);
Builder.CreateStore(ValueAfterCall, Alloca);

return Addr;
2244}

2246/// Eliminate a formerly-swifterror alloca by inserting the get/set
2247/// intrinsics and attempting to MemToReg the alloca away.
2248static void eliminateSwiftErrorAlloca(Function &F, AllocaInst *Alloca,
                                    coro::Shape &Shape) {
for (Use &Use : llvm::make_early_inc_range(Alloca->uses())) {
  // swifterror values can only be used in very specific ways.
  // We take advantage of that here.
  auto User = Use.getUser();
  if (isa<LoadInst>(User) || isa<StoreInst>(User))
    continue;

  assert(isa<CallInst>(User) || isa<InvokeInst>(User))(static_cast <bool> (isa<CallInst>(User) || isa<
InvokeInst>(User)) ? void (0) : __assert_fail ("isa<CallInst>(User) || isa<InvokeInst>(User)"
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 2257, __extension__
 __PRETTY_FUNCTION__));
  auto Call = cast<Instruction>(User);

  auto Addr = emitSetAndGetSwiftErrorValueAround(Call, Alloca, Shape);

  // Use the returned slot address as the call argument.
  Use.set(Addr);
}

// All the uses should be loads and stores now.
assert(isAllocaPromotable(Alloca))(static_cast <bool> (isAllocaPromotable(Alloca)) ? void
 (0) : __assert_fail ("isAllocaPromotable(Alloca)", "llvm/lib/Transforms/Coroutines/CoroFrame.cpp"
, 2267, __extension__ __PRETTY_FUNCTION__));
2268}

2270/// "Eliminate" a swifterror argument by reducing it to the alloca case
2271/// and then loading and storing in the prologue and epilog.
2272///
2273/// The argument keeps the swifterror flag.
2274static void eliminateSwiftErrorArgument(Function &F, Argument &Arg,
                                      coro::Shape &Shape,
                           SmallVectorImpl<AllocaInst*> &AllocasToPromote) {
IRBuilder<> Builder(F.getEntryBlock().getFirstNonPHIOrDbg());

auto ArgTy = cast<PointerType>(Arg.getType());
auto ValueTy = ArgTy->getPointerElementType();

// Reduce to the alloca case:

// Create an alloca and replace all uses of the arg with it.
auto Alloca = Builder.CreateAlloca(ValueTy, ArgTy->getAddressSpace());
Arg.replaceAllUsesWith(Alloca);

// Set an initial value in the alloca.  swifterror is always null on entry.
auto InitialValue = Constant::getNullValue(ValueTy);
Builder.CreateStore(InitialValue, Alloca);

// Find all the suspends in the function and save and restore around them.
for (auto Suspend : Shape.CoroSuspends) {
  (void) emitSetAndGetSwiftErrorValueAround(Suspend, Alloca, Shape);
}

// Find all the coro.ends in the function and restore the error value.
for (auto End : Shape.CoroEnds) {
  Builder.SetInsertPoint(End);
  auto FinalValue = Builder.CreateLoad(ValueTy, Alloca);
  (void) emitSetSwiftErrorValue(Builder, FinalValue, Shape);
}

// Now we can use the alloca logic.
AllocasToPromote.push_back(Alloca);
eliminateSwiftErrorAlloca(F, Alloca, Shape);
2307}

2309/// Eliminate all problematic uses of swifterror arguments and allocas
2310/// from the function.  We'll fix them up later when splitting the function.
2311static void eliminateSwiftError(Function &F, coro::Shape &Shape) {
SmallVector<AllocaInst*, 4> AllocasToPromote;

// Look for a swifterror argument.
for (auto &Arg : F.args()) {
  if (!Arg.hasSwiftErrorAttr()) continue;

  eliminateSwiftErrorArgument(F, Arg, Shape, AllocasToPromote);
  break;
}

// Look for swifterror allocas.
for (auto &Inst : F.getEntryBlock()) {
  auto Alloca = dyn_cast<AllocaInst>(&Inst);
  if (!Alloca || !Alloca->isSwiftError()) continue;

  // Clear the swifterror flag.
  Alloca->setSwiftError(false);

  AllocasToPromote.push_back(Alloca);
  eliminateSwiftErrorAlloca(F, Alloca, Shape);
}

// If we have any allocas to promote, compute a dominator tree and
// promote them en masse.
if (!AllocasToPromote.empty()) {
  DominatorTree DT(F);
  PromoteMemToReg(AllocasToPromote, DT);
}
2340}

2342/// retcon and retcon.once conventions assume that all spill uses can be sunk
2343/// after the coro.begin intrinsic.
2344static void sinkSpillUsesAfterCoroBegin(Function &F,
                                      const FrameDataInfo &FrameData,
                                      CoroBeginInst *CoroBegin) {
DominatorTree Dom(F);

SmallSetVector<Instruction *, 32> ToMove;
SmallVector<Instruction *, 32> Worklist;

// Collect all users that precede coro.begin.
for (auto *Def : FrameData.getAllDefs()) {
  for (User *U : Def->users()) {
    auto Inst = cast<Instruction>(U);
    if (Inst->getParent() != CoroBegin->getParent() ||
        Dom.dominates(CoroBegin, Inst))
      continue;
    if (ToMove.insert(Inst))
      Worklist.push_back(Inst);
  }
}
// Recursively collect users before coro.begin.
while (!Worklist.empty()) {
  auto *Def = Worklist.pop_back_val();
  for (User *U : Def->users()) {
    auto Inst = cast<Instruction>(U);
    if (Dom.dominates(CoroBegin, Inst))
      continue;
    if (ToMove.insert(Inst))
      Worklist.push_back(Inst);
  }
}

// Sort by dominance.
SmallVector<Instruction *, 64> InsertionList(ToMove.begin(), ToMove.end());
llvm::sort(InsertionList, [&Dom](Instruction *A, Instruction *B) -> bool {
  // If a dominates b it should preceed (<) b.
  return Dom.dominates(A, B);
});

Instruction *InsertPt = CoroBegin->getNextNode();
for (Instruction *Inst : InsertionList)
  Inst->moveBefore(InsertPt);
2385}

2387/// For each local variable that all of its user are only used inside one of
2388/// suspended region, we sink their lifetime.start markers to the place where
2389/// after the suspend block. Doing so minimizes the lifetime of each variable,
2390/// hence minimizing the amount of data we end up putting on the frame.
2391static void sinkLifetimeStartMarkers(Function &F, coro::Shape &Shape,
                                   SuspendCrossingInfo &Checker) {
DominatorTree DT(F);

// Collect all possible basic blocks which may dominate all uses of allocas.
SmallPtrSet<BasicBlock *, 4> DomSet;
DomSet.insert(&F.getEntryBlock());
for (auto *CSI : Shape.CoroSuspends) {
  BasicBlock *SuspendBlock = CSI->getParent();
  assert(isSuspendBlock(SuspendBlock) && SuspendBlock->getSingleSuccessor() &&(static_cast <bool> (isSuspendBlock(SuspendBlock) &&
 SuspendBlock->getSingleSuccessor() && "should have split coro.suspend into its own block"
) ? void (0) : __assert_fail ("isSuspendBlock(SuspendBlock) && SuspendBlock->getSingleSuccessor() && \"should have split coro.suspend into its own block\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 2401, __extension__
 __PRETTY_FUNCTION__))
         "should have split coro.suspend into its own block")(static_cast <bool> (isSuspendBlock(SuspendBlock) &&
 SuspendBlock->getSingleSuccessor() && "should have split coro.suspend into its own block"
) ? void (0) : __assert_fail ("isSuspendBlock(SuspendBlock) && SuspendBlock->getSingleSuccessor() && \"should have split coro.suspend into its own block\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 2401, __extension__
 __PRETTY_FUNCTION__));
  DomSet.insert(SuspendBlock->getSingleSuccessor());
}

for (Instruction &I : instructions(F)) {
  AllocaInst* AI = dyn_cast<AllocaInst>(&I);
  if (!AI)
    continue;

  for (BasicBlock *DomBB : DomSet) {
    bool Valid = true;
    SmallVector<Instruction *, 1> Lifetimes;

    auto isLifetimeStart = [](Instruction* I) {
      if (auto* II = dyn_cast<IntrinsicInst>(I))
        return II->getIntrinsicID() == Intrinsic::lifetime_start;
      return false;
    };

    auto collectLifetimeStart = [&](Instruction *U, AllocaInst *AI) {
      if (isLifetimeStart(U)) {
        Lifetimes.push_back(U);
        return true;
      }
      if (!U->hasOneUse() || U->stripPointerCasts() != AI)
        return false;
      if (isLifetimeStart(U->user_back())) {
        Lifetimes.push_back(U->user_back());
        return true;
      }
      return false;
    };

    for (User *U : AI->users()) {
      Instruction *UI = cast<Instruction>(U);
      // For all users except lifetime.start markers, if they are all
      // dominated by one of the basic blocks and do not cross
      // suspend points as well, then there is no need to spill the
      // instruction.
      if (!DT.dominates(DomBB, UI->getParent()) ||
          Checker.isDefinitionAcrossSuspend(DomBB, UI)) {
        // Skip lifetime.start, GEP and bitcast used by lifetime.start
        // markers.
        if (collectLifetimeStart(UI, AI))
          continue;
        Valid = false;
        break;
      }
    }
    // Sink lifetime.start markers to dominate block when they are
    // only used outside the region.
    if (Valid && Lifetimes.size() != 0) {
      // May be AI itself, when the type of AI is i8*
      auto *NewBitCast = [&](AllocaInst *AI) -> Value* {
        if (isa<AllocaInst>(Lifetimes[0]->getOperand(1)))
          return AI;
        auto *Int8PtrTy = Type::getInt8PtrTy(F.getContext());
        return CastInst::Create(Instruction::BitCast, AI, Int8PtrTy, "",
                                DomBB->getTerminator());
      }(AI);

      auto *NewLifetime = Lifetimes[0]->clone();
      NewLifetime->replaceUsesOfWith(NewLifetime->getOperand(1), NewBitCast);
      NewLifetime->insertBefore(DomBB->getTerminator());

      // All the outsided lifetime.start markers are no longer necessary.
      for (Instruction *S : Lifetimes)
        S->eraseFromParent();

      break;
    }
  }
}
2474}

2476static void collectFrameAllocas(Function &F, coro::Shape &Shape,
                              const SuspendCrossingInfo &Checker,
                              SmallVectorImpl<AllocaInfo> &Allocas) {
for (Instruction &I : instructions(F)) {
  auto *AI = dyn_cast<AllocaInst>(&I);
  if (!AI)
    continue;
  // The PromiseAlloca will be specially handled since it needs to be in a
  // fixed position in the frame.
  if (AI == Shape.SwitchLowering.PromiseAlloca) {
    continue;
  }
  DominatorTree DT(F);
  // The code that uses lifetime.start intrinsic does not work for functions
  // with loops without exit. Disable it on ABIs we know to generate such
  // code.
  bool ShouldUseLifetimeStartInfo =
      (Shape.ABI != coro::ABI::Async && Shape.ABI != coro::ABI::Retcon &&
       Shape.ABI != coro::ABI::RetconOnce);
  AllocaUseVisitor Visitor{F.getParent()->getDataLayout(), DT,
                           *Shape.CoroBegin, Checker,
                           ShouldUseLifetimeStartInfo};
  Visitor.visitPtr(*AI);
  if (!Visitor.getShouldLiveOnFrame())
    continue;
  Allocas.emplace_back(AI, Visitor.getAliasesCopy(),
                       Visitor.getMayWriteBeforeCoroBegin());
}
2504}

2506void coro::salvageDebugInfo(
  SmallDenseMap<llvm::Value *, llvm::AllocaInst *, 4> &DbgPtrAllocaCache,
  DbgVariableIntrinsic *DVI, bool OptimizeFrame) {
Function *F = DVI->getFunction();
IRBuilder<> Builder(F->getContext());
auto InsertPt = F->getEntryBlock().getFirstInsertionPt();
while (isa<IntrinsicInst>(InsertPt))
1
Assuming 'InsertPt' is not a 'IntrinsicInst'→
2
←
Loop condition is false. Execution continues on line 2514→
  ++InsertPt;
Builder.SetInsertPoint(&F->getEntryBlock(), InsertPt);
DIExpression *Expr = DVI->getExpression();
// Follow the pointer arithmetic all the way to the incoming
// function argument and convert into a DIExpression.
bool SkipOutermostLoad = !isa<DbgValueInst>(DVI);
3
←
Assuming 'DVI' is not a 'DbgValueInst'→
Value *Storage = DVI->getVariableLocationOp(0);
Value *OriginalStorage = Storage;
while (auto *Inst = dyn_cast_or_null<Instruction>(Storage)) {
4
←
Assuming 'Storage' is a 'Instruction'→
5
←
Loop condition is true.  Entering loop body→
18
←
Assuming 'Storage' is a 'Instruction'→
19
←
Loop condition is true.  Entering loop body→
  if (auto *LdInst6.1
'LdInst' is null
1
'LdInst' is null
1
'LdInst' is null
1
'LdInst' is null
1
'LdInst' is null
1
'LdInst' is null
 = dyn_cast<LoadInst>(Inst)) {
6
←
Assuming 'Inst' is not a 'LoadInst'→
7
←
Taking false branch→
20
←
Assuming 'Inst' is not a 'LoadInst'→
21
←
Taking false branch→
    Storage = LdInst->getOperand(0);
    // FIXME: This is a heuristic that works around the fact that
    // LLVM IR debug intrinsics cannot yet distinguish between
    // memory and value locations: Because a dbg.declare(alloca) is
    // implicitly a memory location no DW_OP_deref operation for the
    // last direct load from an alloca is necessary.  This condition
    // effectively drops the *last* DW_OP_deref in the expression.
    if (!SkipOutermostLoad)
      Expr = DIExpression::prepend(Expr, DIExpression::DerefBefore);
  } else if (auto *StInst8.1
'StInst' is null
1
'StInst' is null
1
'StInst' is null
1
'StInst' is null
1
'StInst' is null
1
'StInst' is null
 = dyn_cast<StoreInst>(Inst)) {
8
←
Assuming 'Inst' is not a 'StoreInst'→
9
←
Taking false branch→
22
←
Assuming 'Inst' is not a 'StoreInst'→
23
←
Taking false branch→
    Storage = StInst->getOperand(0);
  } else {
    SmallVector<uint64_t, 16> Ops;
    SmallVector<Value *, 0> AdditionalValues;
    Value *Op = llvm::salvageDebugInfoImpl(
        *Inst, Expr9.1
'Expr' is non-null
1
'Expr' is non-null
1
'Expr' is non-null
 ? Expr->getNumLocationOperands() : 0, Ops,
10
←
'?' condition is true→
24
←
Assuming 'Expr' is null→
25
←
'?' condition is false→
        AdditionalValues);
    if (!Op || !AdditionalValues.empty()) {
11
←
Assuming 'Op' is non-null→
12
←
Calling 'SmallVectorBase::empty'→
15
←
Returning from 'SmallVectorBase::empty'→
16
←
Taking false branch→
26
←
Assuming 'Op' is null→
      // If salvaging failed or salvaging produced more than one location
      // operand, give up.
      break;
    }
    Storage = Op;
    Expr = DIExpression::appendOpsToArg(Expr, Ops, 0, /*StackValue*/ false);
17
←
Value assigned to 'Expr'→
  }
  SkipOutermostLoad = false;
}
if (!Storage27.1
'Storage' is non-null
1
'Storage' is non-null
1
'Storage' is non-null
)
27
←
 Execution continues on line 2550→
  return;

// Store a pointer to the coroutine frame object in an alloca so it
// is available throughout the function when producing unoptimized
// code. Extending the lifetime this way is correct because the
// variable has been declared by a dbg.declare intrinsic.
//
// Avoid to create the alloca would be eliminated by optimization
// passes and the corresponding dbg.declares would be invalid.
if (!OptimizeFrame && !EnableReuseStorageInFrame)
28
←
Assuming 'OptimizeFrame' is true→
  if (auto *Arg = dyn_cast<llvm::Argument>(Storage)) {
    auto &Cached = DbgPtrAllocaCache[Storage];
    if (!Cached) {
      Cached = Builder.CreateAlloca(Storage->getType(), 0, nullptr,
                                    Arg->getName() + ".debug");
      Builder.CreateStore(Storage, Cached);
    }
    Storage = Cached;
    // FIXME: LLVM lacks nuanced semantics to differentiate between
    // memory and direct locations at the IR level. The backend will
    // turn a dbg.declare(alloca, ..., DIExpression()) into a memory
    // location. Thus, if there are deref and offset operations in the
    // expression, we need to add a DW_OP_deref at the *start* of the
    // expression to first load the contents of the alloca before
    // adjusting it with the expression.
    if (Expr && Expr->isComplex())
      Expr = DIExpression::prepend(Expr, DIExpression::DerefBefore);
  }

DVI->replaceVariableLocationOp(OriginalStorage, Storage);
DVI->setExpression(Expr);
29
←
Passing null pointer value via 1st parameter 'NewExpr'→
30
←
Calling 'DbgVariableIntrinsic::setExpression'→
/// It makes no sense to move the dbg.value intrinsic.
if (!isa<DbgValueInst>(DVI)) {
  if (auto *II = dyn_cast<InvokeInst>(Storage))
    DVI->moveBefore(II->getNormalDest()->getFirstNonPHI());
  else if (auto *CBI = dyn_cast<CallBrInst>(Storage))
    DVI->moveBefore(CBI->getDefaultDest()->getFirstNonPHI());
  else if (auto *InsertPt = dyn_cast<Instruction>(Storage)) {
    assert(!InsertPt->isTerminator() &&(static_cast <bool> (!InsertPt->isTerminator() &&
 "Unimaged terminator that could return a storage.") ? void (
0) : __assert_fail ("!InsertPt->isTerminator() && \"Unimaged terminator that could return a storage.\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 2590, __extension__
 __PRETTY_FUNCTION__))
           "Unimaged terminator that could return a storage.")(static_cast <bool> (!InsertPt->isTerminator() &&
 "Unimaged terminator that could return a storage.") ? void (
0) : __assert_fail ("!InsertPt->isTerminator() && \"Unimaged terminator that could return a storage.\""
, "llvm/lib/Transforms/Coroutines/CoroFrame.cpp", 2590, __extension__
 __PRETTY_FUNCTION__));
    DVI->moveAfter(InsertPt);
  } else if (isa<Argument>(Storage))
    DVI->moveAfter(F->getEntryBlock().getFirstNonPHI());
}
2595}

2597void coro::buildCoroutineFrame(Function &F, Shape &Shape) {
// Don't eliminate swifterror in async functions that won't be split.
if (Shape.ABI != coro::ABI::Async || !Shape.CoroSuspends.empty())
  eliminateSwiftError(F, Shape);

if (Shape.ABI == coro::ABI::Switch &&
    Shape.SwitchLowering.PromiseAlloca) {
  Shape.getSwitchCoroId()->clearPromise();
}

// Make sure that all coro.save, coro.suspend and the fallthrough coro.end
// intrinsics are in their own blocks to simplify the logic of building up
// SuspendCrossing data.
for (auto *CSI : Shape.CoroSuspends) {
  if (auto *Save = CSI->getCoroSave())
    splitAround(Save, "CoroSave");
  splitAround(CSI, "CoroSuspend");
}

// Put CoroEnds into their own blocks.
for (AnyCoroEndInst *CE : Shape.CoroEnds) {
  splitAround(CE, "CoroEnd");

  // Emit the musttail call function in a new block before the CoroEnd.
  // We do this here so that the right suspend crossing info is computed for
  // the uses of the musttail call function call. (Arguments to the coro.end
  // instructions would be ignored)
  if (auto *AsyncEnd = dyn_cast<CoroAsyncEndInst>(CE)) {
    auto *MustTailCallFn = AsyncEnd->getMustTailCallFunction();
    if (!MustTailCallFn)
      continue;
    IRBuilder<> Builder(AsyncEnd);
    SmallVector<Value *, 8> Args(AsyncEnd->args());
    auto Arguments = ArrayRef<Value *>(Args).drop_front(3);
    auto *Call = createMustTailCall(AsyncEnd->getDebugLoc(), MustTailCallFn,
                                    Arguments, Builder);
    splitAround(Call, "MustTailCall.Before.CoroEnd");
  }
}

// Later code makes structural assumptions about single predecessors phis e.g
// that they are not live accross a suspend point.
cleanupSinglePredPHIs(F);

// Transforms multi-edge PHI Nodes, so that any value feeding into a PHI will
// never has its definition separated from the PHI by the suspend point.
rewritePHIs(F);

// Build suspend crossing info.
SuspendCrossingInfo Checker(F, Shape);

IRBuilder<> Builder(F.getContext());
FrameDataInfo FrameData;
SmallVector<CoroAllocaAllocInst*, 4> LocalAllocas;
SmallVector<Instruction*, 4> DeadInstructions;

{
  SpillInfo Spills;
  for (int Repeat = 0; Repeat < 4; ++Repeat) {
    // See if there are materializable instructions across suspend points.
    for (Instruction &I : instructions(F))
      if (materializable(I)) {
        for (User *U : I.users())
          if (Checker.isDefinitionAcrossSuspend(I, U))
            Spills[&I].push_back(cast<Instruction>(U));

        // Manually add dbg.value metadata uses of I.
        SmallVector<DbgValueInst *, 16> DVIs;
        findDbgValues(DVIs, &I);
        for (auto *DVI : DVIs)
          if (Checker.isDefinitionAcrossSuspend(I, DVI))
            Spills[&I].push_back(DVI);
      }

    if (Spills.empty())
      break;

    // Rewrite materializable instructions to be materialized at the use
    // point.
    LLVM_DEBUG(dumpSpills("Materializations", Spills))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dumpSpills("Materializations", Spills); } }
 while (false);
    rewriteMaterializableInstructions(Builder, Spills);
    Spills.clear();
  }
}

if (Shape.ABI != coro::ABI::Async && Shape.ABI != coro::ABI::Retcon &&
    Shape.ABI != coro::ABI::RetconOnce)
  sinkLifetimeStartMarkers(F, Shape, Checker);

if (Shape.ABI != coro::ABI::Async || !Shape.CoroSuspends.empty())
  collectFrameAllocas(F, Shape, Checker, FrameData.Allocas);
LLVM_DEBUG(dumpAllocas(FrameData.Allocas))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dumpAllocas(FrameData.Allocas); } } while (
false);

// Collect the spills for arguments and other not-materializable values.
for (Argument &A : F.args())
  for (User *U : A.users())
    if (Checker.isDefinitionAcrossSuspend(A, U))
      FrameData.Spills[&A].push_back(cast<Instruction>(U));

for (Instruction &I : instructions(F)) {
  // Values returned from coroutine structure intrinsics should not be part
  // of the Coroutine Frame.
  if (isCoroutineStructureIntrinsic(I) || &I == Shape.CoroBegin)
    continue;

  // The Coroutine Promise always included into coroutine frame, no need to
  // check for suspend crossing.
  if (Shape.ABI == coro::ABI::Switch &&
      Shape.SwitchLowering.PromiseAlloca == &I)
    continue;

  // Handle alloca.alloc specially here.
  if (auto AI = dyn_cast<CoroAllocaAllocInst>(&I)) {
    // Check whether the alloca's lifetime is bounded by suspend points.
    if (isLocalAlloca(AI)) {
      LocalAllocas.push_back(AI);
      continue;
    }

    // If not, do a quick rewrite of the alloca and then add spills of
    // the rewritten value.  The rewrite doesn't invalidate anything in
    // Spills because the other alloca intrinsics have no other operands
    // besides AI, and it doesn't invalidate the iteration because we delay
    // erasing AI.
    auto Alloc = lowerNonLocalAlloca(AI, Shape, DeadInstructions);

    for (User *U : Alloc->users()) {
      if (Checker.isDefinitionAcrossSuspend(*Alloc, U))
        FrameData.Spills[Alloc].push_back(cast<Instruction>(U));
    }
    continue;
  }

  // Ignore alloca.get; we process this as part of coro.alloca.alloc.
  if (isa<CoroAllocaGetInst>(I))
    continue;

  if (isa<AllocaInst>(I))
    continue;

  for (User *U : I.users())
    if (Checker.isDefinitionAcrossSuspend(I, U)) {
      // We cannot spill a token.
      if (I.getType()->isTokenTy())
        report_fatal_error(
            "token definition is separated from the use by a suspend point");
      FrameData.Spills[&I].push_back(cast<Instruction>(U));
    }
}

// We don't want the layout of coroutine frame to be affected
// by debug information. So we only choose to salvage DbgValueInst for
// whose value is already in the frame.
// We would handle the dbg.values for allocas specially
for (auto &Iter : FrameData.Spills) {
  auto *V = Iter.first;
  SmallVector<DbgValueInst *, 16> DVIs;
  findDbgValues(DVIs, V);
  llvm::for_each(DVIs, [&](DbgValueInst *DVI) {
    if (Checker.isDefinitionAcrossSuspend(*V, DVI))
      FrameData.Spills[V].push_back(DVI);
  });
}

LLVM_DEBUG(dumpSpills("Spills", FrameData.Spills))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dumpSpills("Spills", FrameData.Spills); } }
 while (false);
if (Shape.ABI == coro::ABI::Retcon || Shape.ABI == coro::ABI::RetconOnce ||
    Shape.ABI == coro::ABI::Async)
  sinkSpillUsesAfterCoroBegin(F, FrameData, Shape.CoroBegin);
Shape.FrameTy = buildFrameType(F, Shape, FrameData);
createFramePtr(Shape);
// For now, this works for C++ programs only.
buildFrameDebugInfo(F, Shape, FrameData);
insertSpills(FrameData, Shape);
lowerLocalAllocas(LocalAllocas, DeadInstructions);

for (auto I : DeadInstructions)
  I->eraseFromParent();
2774}

←

/build/llvm-toolchain-snapshot-15~++20220211101351+43a1756a5d53/llvm/include/llvm/ADT/SmallVector.h

→

1//===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
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///
9/// /file
10/// This file defines the SmallVector class.
11///
12//===----------------------------------------------------------------------===//

14#ifndef LLVM_ADT_SMALLVECTOR_H
15#define LLVM_ADT_SMALLVECTOR_H

17#include "llvm/Support/Compiler.h"
18#include "llvm/Support/type_traits.h"
19#include <algorithm>
20#include <cassert>
21#include <cstddef>
22#include <cstdlib>
23#include <cstring>
24#include <functional>
25#include <initializer_list>
26#include <iterator>
27#include <limits>
28#include <memory>
29#include <new>
30#include <type_traits>
31#include <utility>

33namespace llvm {

35template <typename IteratorT> class iterator_range;

37/// This is all the stuff common to all SmallVectors.
38///
39/// The template parameter specifies the type which should be used to hold the
40/// Size and Capacity of the SmallVector, so it can be adjusted.
41/// Using 32 bit size is desirable to shrink the size of the SmallVector.
42/// Using 64 bit size is desirable for cases like SmallVector<char>, where a
43/// 32 bit size would limit the vector to ~4GB. SmallVectors are used for
44/// buffering bitcode output - which can exceed 4GB.
45template <class Size_T> class SmallVectorBase {
46protected:
void *BeginX;
Size_T Size = 0, Capacity;

/// The maximum value of the Size_T used.
static constexpr size_t SizeTypeMax() {
  return std::numeric_limits<Size_T>::max();
}

SmallVectorBase() = delete;
SmallVectorBase(void *FirstEl, size_t TotalCapacity)
    : BeginX(FirstEl), Capacity(TotalCapacity) {}

/// This is a helper for \a grow() that's out of line to reduce code
/// duplication.  This function will report a fatal error if it can't grow at
/// least to \p MinSize.
void *mallocForGrow(size_t MinSize, size_t TSize, size_t &NewCapacity);

/// This is an implementation of the grow() method which only works
/// on POD-like data types and is out of line to reduce code duplication.
/// This function will report a fatal error if it cannot increase capacity.
void grow_pod(void *FirstEl, size_t MinSize, size_t TSize);

69public:
size_t size() const { return Size; }
size_t capacity() const { return Capacity; }

LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const { return !Size; }
13
←
Assuming field 'Size' is 0→
14
←
Returning the value 1, which participates in a condition later→

75protected:
/// Set the array size to \p N, which the current array must have enough
/// capacity for.
///
/// This does not construct or destroy any elements in the vector.
void set_size(size_t N) {
  assert(N <= capacity())(static_cast <bool> (N <= capacity()) ? void (0) : __assert_fail
 ("N <= capacity()", "llvm/include/llvm/ADT/SmallVector.h"
, 81, __extension__ __PRETTY_FUNCTION__));
  Size = N;
}
84};

86template <class T>
87using SmallVectorSizeType =
  typename std::conditional<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t,
                            uint32_t>::type;

91/// Figure out the offset of the first element.
92template <class T, typename = void> struct SmallVectorAlignmentAndSize {
alignas(SmallVectorBase<SmallVectorSizeType<T>>) char Base[sizeof(
    SmallVectorBase<SmallVectorSizeType<T>>)];
alignas(T) char FirstEl[sizeof(T)];
96};

98/// This is the part of SmallVectorTemplateBase which does not depend on whether
99/// the type T is a POD. The extra dummy template argument is used by ArrayRef
100/// to avoid unnecessarily requiring T to be complete.
101template <typename T, typename = void>
102class SmallVectorTemplateCommon
  : public SmallVectorBase<SmallVectorSizeType<T>> {
using Base = SmallVectorBase<SmallVectorSizeType<T>>;

/// Find the address of the first element.  For this pointer math to be valid
/// with small-size of 0 for T with lots of alignment, it's important that
/// SmallVectorStorage is properly-aligned even for small-size of 0.
void *getFirstEl() const {
  return const_cast<void *>(reinterpret_cast<const void *>(
      reinterpret_cast<const char *>(this) +
      offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)__builtin_offsetof(SmallVectorAlignmentAndSize<T>, FirstEl
)));
}
// Space after 'FirstEl' is clobbered, do not add any instance vars after it.

116protected:
SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}

void grow_pod(size_t MinSize, size_t TSize) {
  Base::grow_pod(getFirstEl(), MinSize, TSize);
}

/// Return true if this is a smallvector which has not had dynamic
/// memory allocated for it.
bool isSmall() const { return this->BeginX == getFirstEl(); }

/// Put this vector in a state of being small.
void resetToSmall() {
  this->BeginX = getFirstEl();
  this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
}

/// Return true if V is an internal reference to the given range.
bool isReferenceToRange(const void *V, const void *First, const void *Last) const {
  // Use std::less to avoid UB.
  std::less<> LessThan;
  return !LessThan(V, First) && LessThan(V, Last);
}

/// Return true if V is an internal reference to this vector.
bool isReferenceToStorage(const void *V) const {
  return isReferenceToRange(V, this->begin(), this->end());
}

/// Return true if First and Last form a valid (possibly empty) range in this
/// vector's storage.
bool isRangeInStorage(const void *First, const void *Last) const {
  // Use std::less to avoid UB.
  std::less<> LessThan;
  return !LessThan(First, this->begin()) && !LessThan(Last, First) &&
         !LessThan(this->end(), Last);
}

/// Return true unless Elt will be invalidated by resizing the vector to
/// NewSize.
bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
  // Past the end.
  if (LLVM_LIKELY(!isReferenceToStorage(Elt))__builtin_expect((bool)(!isReferenceToStorage(Elt)), true))
    return true;

  // Return false if Elt will be destroyed by shrinking.
  if (NewSize <= this->size())
    return Elt < this->begin() + NewSize;

  // Return false if we need to grow.
  return NewSize <= this->capacity();
}

/// Check whether Elt will be invalidated by resizing the vector to NewSize.
void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
  assert(isSafeToReferenceAfterResize(Elt, NewSize) &&(static_cast <bool> (isSafeToReferenceAfterResize(Elt, NewSize
) && "Attempting to reference an element of the vector in an operation "
 "that invalidates it") ? void (0) : __assert_fail ("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\""
, "llvm/include/llvm/ADT/SmallVector.h", 173, __extension__ __PRETTY_FUNCTION__
))
         "Attempting to reference an element of the vector in an operation "(static_cast <bool> (isSafeToReferenceAfterResize(Elt, NewSize
) && "Attempting to reference an element of the vector in an operation "
 "that invalidates it") ? void (0) : __assert_fail ("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\""
, "llvm/include/llvm/ADT/SmallVector.h", 173, __extension__ __PRETTY_FUNCTION__
))
         "that invalidates it")(static_cast <bool> (isSafeToReferenceAfterResize(Elt, NewSize
) && "Attempting to reference an element of the vector in an operation "
 "that invalidates it") ? void (0) : __assert_fail ("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\""
, "llvm/include/llvm/ADT/SmallVector.h", 173, __extension__ __PRETTY_FUNCTION__
));
}

/// Check whether Elt will be invalidated by increasing the size of the
/// vector by N.
void assertSafeToAdd(const void *Elt, size_t N = 1) {
  this->assertSafeToReferenceAfterResize(Elt, this->size() + N);
}

/// Check whether any part of the range will be invalidated by clearing.
void assertSafeToReferenceAfterClear(const T *From, const T *To) {
  if (From == To)
    return;
  this->assertSafeToReferenceAfterResize(From, 0);
  this->assertSafeToReferenceAfterResize(To - 1, 0);
}
template <
    class ItTy,
    std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
                     bool> = false>
void assertSafeToReferenceAfterClear(ItTy, ItTy) {}

/// Check whether any part of the range will be invalidated by growing.
void assertSafeToAddRange(const T *From, const T *To) {
  if (From == To)
    return;
  this->assertSafeToAdd(From, To - From);
  this->assertSafeToAdd(To - 1, To - From);
}
template <
    class ItTy,
    std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
                     bool> = false>
void assertSafeToAddRange(ItTy, ItTy) {}

/// Reserve enough space to add one element, and return the updated element
/// pointer in case it was a reference to the storage.
template <class U>
static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt,
                                                 size_t N) {
  size_t NewSize = This->size() + N;
  if (LLVM_LIKELY(NewSize <= This->capacity())__builtin_expect((bool)(NewSize <= This->capacity()), true
))
    return &Elt;

  bool ReferencesStorage = false;
  int64_t Index = -1;
  if (!U::TakesParamByValue) {
    if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))__builtin_expect((bool)(This->isReferenceToStorage(&Elt
)), false)) {
      ReferencesStorage = true;
      Index = &Elt - This->begin();
    }
  }
  This->grow(NewSize);
  return ReferencesStorage ? This->begin() + Index : &Elt;
}

229public:
using size_type = size_t;
using difference_type = ptrdiff_t;
using value_type = T;
using iterator = T *;
using const_iterator = const T *;

using const_reverse_iterator = std::reverse_iterator<const_iterator>;
using reverse_iterator = std::reverse_iterator<iterator>;

using reference = T &;
using const_reference = const T &;
using pointer = T *;
using const_pointer = const T *;

using Base::capacity;
using Base::empty;
using Base::size;

// forward iterator creation methods.
iterator begin() { return (iterator)this->BeginX; }
const_iterator begin() const { return (const_iterator)this->BeginX; }
iterator end() { return begin() + size(); }
const_iterator end() const { return begin() + size(); }

// reverse iterator creation methods.
reverse_iterator rbegin()            { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
reverse_iterator rend()              { return reverse_iterator(begin()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin());}

size_type size_in_bytes() const { return size() * sizeof(T); }
size_type max_size() const {
  return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T));
}

size_t capacity_in_bytes() const { return capacity() * sizeof(T); }

/// Return a pointer to the vector's buffer, even if empty().
pointer data() { return pointer(begin()); }
/// Return a pointer to the vector's buffer, even if empty().
const_pointer data() const { return const_pointer(begin()); }

reference operator[](size_type idx) {
  assert(idx < size())(static_cast <bool> (idx < size()) ? void (0) : __assert_fail
 ("idx < size()", "llvm/include/llvm/ADT/SmallVector.h", 273
, __extension__ __PRETTY_FUNCTION__));
  return begin()[idx];
}
const_reference operator[](size_type idx) const {
  assert(idx < size())(static_cast <bool> (idx < size()) ? void (0) : __assert_fail
 ("idx < size()", "llvm/include/llvm/ADT/SmallVector.h", 277
, __extension__ __PRETTY_FUNCTION__));
  return begin()[idx];
}

reference front() {
  assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail
 ("!empty()", "llvm/include/llvm/ADT/SmallVector.h", 282, __extension__
 __PRETTY_FUNCTION__));
  return begin()[0];
}
const_reference front() const {
  assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail
 ("!empty()", "llvm/include/llvm/ADT/SmallVector.h", 286, __extension__
 __PRETTY_FUNCTION__));
  return begin()[0];
}

reference back() {
  assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail
 ("!empty()", "llvm/include/llvm/ADT/SmallVector.h", 291, __extension__
 __PRETTY_FUNCTION__));
  return end()[-1];
}
const_reference back() const {
  assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail
 ("!empty()", "llvm/include/llvm/ADT/SmallVector.h", 295, __extension__
 __PRETTY_FUNCTION__));
  return end()[-1];
}
298};

300/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put
301/// method implementations that are designed to work with non-trivial T's.
302///
303/// We approximate is_trivially_copyable with trivial move/copy construction and
304/// trivial destruction. While the standard doesn't specify that you're allowed
305/// copy these types with memcpy, there is no way for the type to observe this.
306/// This catches the important case of std::pair<POD, POD>, which is not
307/// trivially assignable.
308template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&
                           (is_trivially_move_constructible<T>::value) &&
                           std::is_trivially_destructible<T>::value>
311class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
friend class SmallVectorTemplateCommon<T>;

314protected:
static constexpr bool TakesParamByValue = false;
using ValueParamT = const T &;

SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}

static void destroy_range(T *S, T *E) {
  while (S != E) {
    --E;
    E->~T();
  }
}

/// Move the range [I, E) into the uninitialized memory starting with "Dest",
/// constructing elements as needed.
template<typename It1, typename It2>
static void uninitialized_move(It1 I, It1 E, It2 Dest) {
  std::uninitialized_copy(std::make_move_iterator(I),
                          std::make_move_iterator(E), Dest);
}

/// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
/// constructing elements as needed.
template<typename It1, typename It2>
static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
  std::uninitialized_copy(I, E, Dest);
}

/// Grow the allocated memory (without initializing new elements), doubling
/// the size of the allocated memory. Guarantees space for at least one more
/// element, or MinSize more elements if specified.
void grow(size_t MinSize = 0);

/// Create a new allocation big enough for \p MinSize and pass back its size
/// in \p NewCapacity. This is the first section of \a grow().
T *mallocForGrow(size_t MinSize, size_t &NewCapacity) {
  return static_cast<T *>(
      SmallVectorBase<SmallVectorSizeType<T>>::mallocForGrow(
          MinSize, sizeof(T), NewCapacity));
}

/// Move existing elements over to the new allocation \p NewElts, the middle
/// section of \a grow().
void moveElementsForGrow(T *NewElts);

/// Transfer ownership of the allocation, finishing up \a grow().
void takeAllocationForGrow(T *NewElts, size_t NewCapacity);

/// Reserve enough space to add one element, and return the updated element
/// pointer in case it was a reference to the storage.
const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
  return this->reserveForParamAndGetAddressImpl(this, Elt, N);
}

/// Reserve enough space to add one element, and return the updated element
/// pointer in case it was a reference to the storage.
T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
  return const_cast<T *>(
      this->reserveForParamAndGetAddressImpl(this, Elt, N));
}

static T &&forward_value_param(T &&V) { return std::move(V); }
static const T &forward_value_param(const T &V) { return V; }

void growAndAssign(size_t NumElts, const T &Elt) {
  // Grow manually in case Elt is an internal reference.
  size_t NewCapacity;
  T *NewElts = mallocForGrow(NumElts, NewCapacity);
  std::uninitialized_fill_n(NewElts, NumElts, Elt);
  this->destroy_range(this->begin(), this->end());
  takeAllocationForGrow(NewElts, NewCapacity);
  this->set_size(NumElts);
}

template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
  // Grow manually in case one of Args is an internal reference.
  size_t NewCapacity;
  T *NewElts = mallocForGrow(0, NewCapacity);
  ::new ((void *)(NewElts + this->size())) T(std::forward<ArgTypes>(Args)...);
  moveElementsForGrow(NewElts);
  takeAllocationForGrow(NewElts, NewCapacity);
  this->set_size(this->size() + 1);
  return this->back();
}

399public:
void push_back(const T &Elt) {
  const T *EltPtr = reserveForParamAndGetAddress(Elt);
  ::new ((void *)this->end()) T(*EltPtr);
  this->set_size(this->size() + 1);
}

void push_back(T &&Elt) {
  T *EltPtr = reserveForParamAndGetAddress(Elt);
  ::new ((void *)this->end()) T(::std::move(*EltPtr));
  this->set_size(this->size() + 1);
}

void pop_back() {
  this->set_size(this->size() - 1);
  this->end()->~T();
}
416};

418// Define this out-of-line to dissuade the C++ compiler from inlining it.
419template <typename T, bool TriviallyCopyable>
420void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) {
size_t NewCapacity;
T *NewElts = mallocForGrow(MinSize, NewCapacity);
moveElementsForGrow(NewElts);
takeAllocationForGrow(NewElts, NewCapacity);
425}

427// Define this out-of-line to dissuade the C++ compiler from inlining it.
428template <typename T, bool TriviallyCopyable>
429void SmallVectorTemplateBase<T, TriviallyCopyable>::moveElementsForGrow(
  T *NewElts) {
// Move the elements over.
this->uninitialized_move(this->begin(), this->end(), NewElts);

// Destroy the original elements.
destroy_range(this->begin(), this->end());
436}

438// Define this out-of-line to dissuade the C++ compiler from inlining it.
439template <typename T, bool TriviallyCopyable>
440void SmallVectorTemplateBase<T, TriviallyCopyable>::takeAllocationForGrow(
  T *NewElts, size_t NewCapacity) {
// If this wasn't grown from the inline copy, deallocate the old space.
if (!this->isSmall())
  free(this->begin());

this->BeginX = NewElts;
this->Capacity = NewCapacity;
448}

450/// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
451/// method implementations that are designed to work with trivially copyable
452/// T's. This allows using memcpy in place of copy/move construction and
453/// skipping destruction.
454template <typename T>
455class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
friend class SmallVectorTemplateCommon<T>;

458protected:
/// True if it's cheap enough to take parameters by value. Doing so avoids
/// overhead related to mitigations for reference invalidation.
static constexpr bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *);

/// Either const T& or T, depending on whether it's cheap enough to take
/// parameters by value.
using ValueParamT =
    typename std::conditional<TakesParamByValue, T, const T &>::type;

SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}

// No need to do a destroy loop for POD's.
static void destroy_range(T *, T *) {}

/// Move the range [I, E) onto the uninitialized memory
/// starting with "Dest", constructing elements into it as needed.
template<typename It1, typename It2>
static void uninitialized_move(It1 I, It1 E, It2 Dest) {
  // Just do a copy.
  uninitialized_copy(I, E, Dest);
}

/// Copy the range [I, E) onto the uninitialized memory
/// starting with "Dest", constructing elements into it as needed.
template<typename It1, typename It2>
static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
  // Arbitrary iterator types; just use the basic implementation.
  std::uninitialized_copy(I, E, Dest);
}

/// Copy the range [I, E) onto the uninitialized memory
/// starting with "Dest", constructing elements into it as needed.
template <typename T1, typename T2>
static void uninitialized_copy(
    T1 *I, T1 *E, T2 *Dest,
    std::enable_if_t<std::is_same<typename std::remove_const<T1>::type,
                                  T2>::value> * = nullptr) {
  // Use memcpy for PODs iterated by pointers (which includes SmallVector
  // iterators): std::uninitialized_copy optimizes to memmove, but we can
  // use memcpy here. Note that I and E are iterators and thus might be
  // invalid for memcpy if they are equal.
  if (I != E)
    memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
}

/// Double the size of the allocated memory, guaranteeing space for at
/// least one more element or MinSize if specified.
void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }

/// Reserve enough space to add one element, and return the updated element
/// pointer in case it was a reference to the storage.
const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
  return this->reserveForParamAndGetAddressImpl(this, Elt, N);
}

/// Reserve enough space to add one element, and return the updated element
/// pointer in case it was a reference to the storage.
T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
  return const_cast<T *>(
      this->reserveForParamAndGetAddressImpl(this, Elt, N));
}

/// Copy \p V or return a reference, depending on \a ValueParamT.
static ValueParamT forward_value_param(ValueParamT V) { return V; }

void growAndAssign(size_t NumElts, T Elt) {
  // Elt has been copied in case it's an internal reference, side-stepping
  // reference invalidation problems without losing the realloc optimization.
  this->set_size(0);
  this->grow(NumElts);
  std::uninitialized_fill_n(this->begin(), NumElts, Elt);
  this->set_size(NumElts);
}

template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
  // Use push_back with a copy in case Args has an internal reference,
  // side-stepping reference invalidation problems without losing the realloc
  // optimization.
  push_back(T(std::forward<ArgTypes>(Args)...));
  return this->back();
}

541public:
void push_back(ValueParamT Elt) {
  const T *EltPtr = reserveForParamAndGetAddress(Elt);
  memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T));
  this->set_size(this->size() + 1);
}

void pop_back() { this->set_size(this->size() - 1); }
549};

551/// This class consists of common code factored out of the SmallVector class to
552/// reduce code duplication based on the SmallVector 'N' template parameter.
553template <typename T>
554class SmallVectorImpl : public SmallVectorTemplateBase<T> {
using SuperClass = SmallVectorTemplateBase<T>;

557public:
using iterator = typename SuperClass::iterator;
using const_iterator = typename SuperClass::const_iterator;
using reference = typename SuperClass::reference;
using size_type = typename SuperClass::size_type;

563protected:
using SmallVectorTemplateBase<T>::TakesParamByValue;
using ValueParamT = typename SuperClass::ValueParamT;

// Default ctor - Initialize to empty.
explicit SmallVectorImpl(unsigned N)
    : SmallVectorTemplateBase<T>(N) {}

void assignRemote(SmallVectorImpl &&RHS) {
  this->destroy_range(this->begin(), this->end());
  if (!this->isSmall())
    free(this->begin());
  this->BeginX = RHS.BeginX;
  this->Size = RHS.Size;
  this->Capacity = RHS.Capacity;
  RHS.resetToSmall();
}

581public:
SmallVectorImpl(const SmallVectorImpl &) = delete;

~SmallVectorImpl() {
  // Subclass has already destructed this vector's elements.
  // If this wasn't grown from the inline copy, deallocate the old space.
  if (!this->isSmall())
    free(this->begin());
}

void clear() {
  this->destroy_range(this->begin(), this->end());
  this->Size = 0;
}

596private:
// Make set_size() private to avoid misuse in subclasses.
using SuperClass::set_size;

template <bool ForOverwrite> void resizeImpl(size_type N) {
  if (N == this->size())
    return;

  if (N < this->size()) {
    this->truncate(N);
    return;
  }

  this->reserve(N);
  for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
    if (ForOverwrite)
      new (&*I) T;
    else
      new (&*I) T();
  this->set_size(N);
}

618public:
void resize(size_type N) { resizeImpl<false>(N); }

/// Like resize, but \ref T is POD, the new values won't be initialized.
void resize_for_overwrite(size_type N) { resizeImpl<true>(N); }

/// Like resize, but requires that \p N is less than \a size().
void truncate(size_type N) {
  assert(this->size() >= N && "Cannot increase size with truncate")(static_cast <bool> (this->size() >= N &&
 "Cannot increase size with truncate") ? void (0) : __assert_fail
 ("this->size() >= N && \"Cannot increase size with truncate\""
, "llvm/include/llvm/ADT/SmallVector.h", 626, __extension__ __PRETTY_FUNCTION__
));
  this->destroy_range(this->begin() + N, this->end());
  this->set_size(N);
}

void resize(size_type N, ValueParamT NV) {
  if (N == this->size())
    return;

  if (N < this->size()) {
    this->truncate(N);
    return;
  }

  // N > this->size(). Defer to append.
  this->append(N - this->size(), NV);
}

void reserve(size_type N) {
  if (this->capacity() < N)
    this->grow(N);
}

void pop_back_n(size_type NumItems) {
  assert(this->size() >= NumItems)(static_cast <bool> (this->size() >= NumItems) ? void
 (0) : __assert_fail ("this->size() >= NumItems", "llvm/include/llvm/ADT/SmallVector.h"
, 650, __extension__ __PRETTY_FUNCTION__));
  truncate(this->size() - NumItems);
}

LLVM_NODISCARD[[clang::warn_unused_result]] T pop_back_val() {
  T Result = ::std::move(this->back());
  this->pop_back();
  return Result;
}

void swap(SmallVectorImpl &RHS);

/// Add the specified range to the end of the SmallVector.
template <typename in_iter,
          typename = std::enable_if_t<std::is_convertible<
              typename std::iterator_traits<in_iter>::iterator_category,
              std::input_iterator_tag>::value>>
void append(in_iter in_start, in_iter in_end) {
  this->assertSafeToAddRange(in_start, in_end);
  size_type NumInputs = std::distance(in_start, in_end);
  this->reserve(this->size() + NumInputs);
  this->uninitialized_copy(in_start, in_end, this->end());
  this->set_size(this->size() + NumInputs);
}

/// Append \p NumInputs copies of \p Elt to the end.
void append(size_type NumInputs, ValueParamT Elt) {
  const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumInputs);
  std::uninitialized_fill_n(this->end(), NumInputs, *EltPtr);
  this->set_size(this->size() + NumInputs);
}

void append(std::initializer_list<T> IL) {
  append(IL.begin(), IL.end());
}

void append(const SmallVectorImpl &RHS) { append(RHS.begin(), RHS.end()); }

void assign(size_type NumElts, ValueParamT Elt) {
  // Note that Elt could be an internal reference.
  if (NumElts > this->capacity()) {
    this->growAndAssign(NumElts, Elt);
    return;
  }

  // Assign over existing elements.
  std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);
  if (NumElts > this->size())
    std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt);
  else if (NumElts < this->size())
    this->destroy_range(this->begin() + NumElts, this->end());
  this->set_size(NumElts);
}

// FIXME: Consider assigning over existing elements, rather than clearing &
// re-initializing them - for all assign(...) variants.

template <typename in_iter,
          typename = std::enable_if_t<std::is_convertible<
              typename std::iterator_traits<in_iter>::iterator_category,
              std::input_iterator_tag>::value>>
void assign(in_iter in_start, in_iter in_end) {
  this->assertSafeToReferenceAfterClear(in_start, in_end);
  clear();
  append(in_start, in_end);
}

void assign(std::initializer_list<T> IL) {
  clear();
  append(IL);
}

void assign(const SmallVectorImpl &RHS) { assign(RHS.begin(), RHS.end()); }

iterator erase(const_iterator CI) {
  // Just cast away constness because this is a non-const member function.
  iterator I = const_cast<iterator>(CI);

  assert(this->isReferenceToStorage(CI) && "Iterator to erase is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(CI) &&
 "Iterator to erase is out of bounds.") ? void (0) : __assert_fail
 ("this->isReferenceToStorage(CI) && \"Iterator to erase is out of bounds.\""
, "llvm/include/llvm/ADT/SmallVector.h", 728, __extension__ __PRETTY_FUNCTION__
));

  iterator N = I;
  // Shift all elts down one.
  std::move(I+1, this->end(), I);
  // Drop the last elt.
  this->pop_back();
  return(N);
}

iterator erase(const_iterator CS, const_iterator CE) {
  // Just cast away constness because this is a non-const member function.
  iterator S = const_cast<iterator>(CS);
  iterator E = const_cast<iterator>(CE);

  assert(this->isRangeInStorage(S, E) && "Range to erase is out of bounds.")(static_cast <bool> (this->isRangeInStorage(S, E) &&
 "Range to erase is out of bounds.") ? void (0) : __assert_fail
 ("this->isRangeInStorage(S, E) && \"Range to erase is out of bounds.\""
, "llvm/include/llvm/ADT/SmallVector.h", 743, __extension__ __PRETTY_FUNCTION__
));

  iterator N = S;
  // Shift all elts down.
  iterator I = std::move(E, this->end(), S);
  // Drop the last elts.
  this->destroy_range(I, this->end());
  this->set_size(I - this->begin());
  return(N);
}

754private:
template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) {
  // Callers ensure that ArgType is derived from T.
  static_assert(
      std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>,
                   T>::value,
      "ArgType must be derived from T!");

  if (I == this->end()) {  // Important special case for empty vector.
    this->push_back(::std::forward<ArgType>(Elt));
    return this->end()-1;
  }

  assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(I) &&
 "Insertion iterator is out of bounds.") ? void (0) : __assert_fail
 ("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\""
, "llvm/include/llvm/ADT/SmallVector.h", 767, __extension__ __PRETTY_FUNCTION__
));

  // Grow if necessary.
  size_t Index = I - this->begin();
  std::remove_reference_t<ArgType> *EltPtr =
      this->reserveForParamAndGetAddress(Elt);
  I = this->begin() + Index;

  ::new ((void*) this->end()) T(::std::move(this->back()));
  // Push everything else over.
  std::move_backward(I, this->end()-1, this->end());
  this->set_size(this->size() + 1);

  // If we just moved the element we're inserting, be sure to update
  // the reference (never happens if TakesParamByValue).
  static_assert(!TakesParamByValue || std::is_same<ArgType, T>::value,
                "ArgType must be 'T' when taking by value!");
  if (!TakesParamByValue && this->isReferenceToRange(EltPtr, I, this->end()))
    ++EltPtr;

  *I = ::std::forward<ArgType>(*EltPtr);
  return I;
}

791public:
iterator insert(iterator I, T &&Elt) {
  return insert_one_impl(I, this->forward_value_param(std::move(Elt)));
}

iterator insert(iterator I, const T &Elt) {
  return insert_one_impl(I, this->forward_value_param(Elt));
}

iterator insert(iterator I, size_type NumToInsert, ValueParamT Elt) {
  // Convert iterator to elt# to avoid invalidating iterator when we reserve()
  size_t InsertElt = I - this->begin();

  if (I == this->end()) {  // Important special case for empty vector.
    append(NumToInsert, Elt);
    return this->begin()+InsertElt;
  }

  assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(I) &&
 "Insertion iterator is out of bounds.") ? void (0) : __assert_fail
 ("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\""
, "llvm/include/llvm/ADT/SmallVector.h", 809, __extension__ __PRETTY_FUNCTION__
));

  // Ensure there is enough space, and get the (maybe updated) address of
  // Elt.
  const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumToInsert);

  // Uninvalidate the iterator.
  I = this->begin()+InsertElt;

  // If there are more elements between the insertion point and the end of the
  // range than there are being inserted, we can use a simple approach to
  // insertion.  Since we already reserved space, we know that this won't
  // reallocate the vector.
  if (size_t(this->end()-I) >= NumToInsert) {
    T *OldEnd = this->end();
    append(std::move_iterator<iterator>(this->end() - NumToInsert),
           std::move_iterator<iterator>(this->end()));

    // Copy the existing elements that get replaced.
    std::move_backward(I, OldEnd-NumToInsert, OldEnd);

    // If we just moved the element we're inserting, be sure to update
    // the reference (never happens if TakesParamByValue).
    if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
      EltPtr += NumToInsert;

    std::fill_n(I, NumToInsert, *EltPtr);
    return I;
  }

  // Otherwise, we're inserting more elements than exist already, and we're
  // not inserting at the end.

  // Move over the elements that we're about to overwrite.
  T *OldEnd = this->end();
  this->set_size(this->size() + NumToInsert);
  size_t NumOverwritten = OldEnd-I;
  this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);

  // If we just moved the element we're inserting, be sure to update
  // the reference (never happens if TakesParamByValue).
  if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
    EltPtr += NumToInsert;

  // Replace the overwritten part.
  std::fill_n(I, NumOverwritten, *EltPtr);

  // Insert the non-overwritten middle part.
  std::uninitialized_fill_n(OldEnd, NumToInsert - NumOverwritten, *EltPtr);
  return I;
}

template <typename ItTy,
          typename = std::enable_if_t<std::is_convertible<
              typename std::iterator_traits<ItTy>::iterator_category,
              std::input_iterator_tag>::value>>
iterator insert(iterator I, ItTy From, ItTy To) {
  // Convert iterator to elt# to avoid invalidating iterator when we reserve()
  size_t InsertElt = I - this->begin();

  if (I == this->end()) {  // Important special case for empty vector.
    append(From, To);
    return this->begin()+InsertElt;
  }

  assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(I) &&
 "Insertion iterator is out of bounds.") ? void (0) : __assert_fail
 ("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\""
, "llvm/include/llvm/ADT/SmallVector.h", 874, __extension__ __PRETTY_FUNCTION__
));

  // Check that the reserve that follows doesn't invalidate the iterators.
  this->assertSafeToAddRange(From, To);

  size_t NumToInsert = std::distance(From, To);

  // Ensure there is enough space.
  reserve(this->size() + NumToInsert);

  // Uninvalidate the iterator.
  I = this->begin()+InsertElt;

  // If there are more elements between the insertion point and the end of the
  // range than there are being inserted, we can use a simple approach to
  // insertion.  Since we already reserved space, we know that this won't
  // reallocate the vector.
  if (size_t(this->end()-I) >= NumToInsert) {
    T *OldEnd = this->end();
    append(std::move_iterator<iterator>(this->end() - NumToInsert),
           std::move_iterator<iterator>(this->end()));

    // Copy the existing elements that get replaced.
    std::move_backward(I, OldEnd-NumToInsert, OldEnd);

    std::copy(From, To, I);
    return I;
  }

  // Otherwise, we're inserting more elements than exist already, and we're
  // not inserting at the end.

  // Move over the elements that we're about to overwrite.
  T *OldEnd = this->end();
  this->set_size(this->size() + NumToInsert);
  size_t NumOverwritten = OldEnd-I;
  this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);

  // Replace the overwritten part.
  for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
    *J = *From;
    ++J; ++From;
  }

  // Insert the non-overwritten middle part.
  this->uninitialized_copy(From, To, OldEnd);
  return I;
}

void insert(iterator I, std::initializer_list<T> IL) {
  insert(I, IL.begin(), IL.end());
}

template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
  if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false))
    return this->growAndEmplaceBack(std::forward<ArgTypes>(Args)...);

  ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
  this->set_size(this->size() + 1);
  return this->back();
}

SmallVectorImpl &operator=(const SmallVectorImpl &RHS);

SmallVectorImpl &operator=(SmallVectorImpl &&RHS);

bool operator==(const SmallVectorImpl &RHS) const {
  if (this->size() != RHS.size()) return false;
  return std::equal(this->begin(), this->end(), RHS.begin());
}
bool operator!=(const SmallVectorImpl &RHS) const {
  return !(*this == RHS);
}

bool operator<(const SmallVectorImpl &RHS) const {
  return std::lexicographical_compare(this->begin(), this->end(),
                                      RHS.begin(), RHS.end());
}
952};

954template <typename T>
955void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
if (this == &RHS) return;

// We can only avoid copying elements if neither vector is small.
if (!this->isSmall() && !RHS.isSmall()) {
  std::swap(this->BeginX, RHS.BeginX);
  std::swap(this->Size, RHS.Size);
  std::swap(this->Capacity, RHS.Capacity);
  return;
}
this->reserve(RHS.size());
RHS.reserve(this->size());

// Swap the shared elements.
size_t NumShared = this->size();
if (NumShared > RHS.size()) NumShared = RHS.size();
for (size_type i = 0; i != NumShared; ++i)
  std::swap((*this)[i], RHS[i]);

// Copy over the extra elts.
if (this->size() > RHS.size()) {
  size_t EltDiff = this->size() - RHS.size();
  this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
  RHS.set_size(RHS.size() + EltDiff);
  this->destroy_range(this->begin()+NumShared, this->end());
  this->set_size(NumShared);
} else if (RHS.size() > this->size()) {
  size_t EltDiff = RHS.size() - this->size();
  this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
  this->set_size(this->size() + EltDiff);
  this->destroy_range(RHS.begin()+NumShared, RHS.end());
  RHS.set_size(NumShared);
}
988}

990template <typename T>
991SmallVectorImpl<T> &SmallVectorImpl<T>::
operator=(const SmallVectorImpl<T> &RHS) {
// Avoid self-assignment.
if (this == &RHS) return *this;

// If we already have sufficient space, assign the common elements, then
// destroy any excess.
size_t RHSSize = RHS.size();
size_t CurSize = this->size();
if (CurSize >= RHSSize) {
  // Assign common elements.
  iterator NewEnd;
  if (RHSSize)
    NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
  else
    NewEnd = this->begin();

  // Destroy excess elements.
  this->destroy_range(NewEnd, this->end());

  // Trim.
  this->set_size(RHSSize);
  return *this;
}

// If we have to grow to have enough elements, destroy the current elements.
// This allows us to avoid copying them during the grow.
// FIXME: don't do this if they're efficiently moveable.
if (this->capacity() < RHSSize) {
  // Destroy current elements.
  this->clear();
  CurSize = 0;
  this->grow(RHSSize);
} else if (CurSize) {
  // Otherwise, use assignment for the already-constructed elements.
  std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
}

// Copy construct the new elements in place.
this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
                         this->begin()+CurSize);

// Set end.
this->set_size(RHSSize);
return *this;
1036}

1038template <typename T>
1039SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
// Avoid self-assignment.
if (this == &RHS) return *this;

// If the RHS isn't small, clear this vector and then steal its buffer.
if (!RHS.isSmall()) {
  this->assignRemote(std::move(RHS));
  return *this;
}

// If we already have sufficient space, assign the common elements, then
// destroy any excess.
size_t RHSSize = RHS.size();
size_t CurSize = this->size();
if (CurSize >= RHSSize) {
  // Assign common elements.
  iterator NewEnd = this->begin();
  if (RHSSize)
    NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);

  // Destroy excess elements and trim the bounds.
  this->destroy_range(NewEnd, this->end());
  this->set_size(RHSSize);

  // Clear the RHS.
  RHS.clear();

  return *this;
}

// If we have to grow to have enough elements, destroy the current elements.
// This allows us to avoid copying them during the grow.
// FIXME: this may not actually make any sense if we can efficiently move
// elements.
if (this->capacity() < RHSSize) {
  // Destroy current elements.
  this->clear();
  CurSize = 0;
  this->grow(RHSSize);
} else if (CurSize) {
  // Otherwise, use assignment for the already-constructed elements.
  std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
}

// Move-construct the new elements in place.
this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
                         this->begin()+CurSize);

// Set end.
this->set_size(RHSSize);

RHS.clear();
return *this;
1092}

1094/// Storage for the SmallVector elements.  This is specialized for the N=0 case
1095/// to avoid allocating unnecessary storage.
1096template <typename T, unsigned N>
1097struct SmallVectorStorage {
alignas(T) char InlineElts[N * sizeof(T)];
1099};

1101/// We need the storage to be properly aligned even for small-size of 0 so that
1102/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
1103/// well-defined.
1104template <typename T> struct alignas(T) SmallVectorStorage<T, 0> {};

1106/// Forward declaration of SmallVector so that
1107/// calculateSmallVectorDefaultInlinedElements can reference
1108/// `sizeof(SmallVector<T, 0>)`.
1109template <typename T, unsigned N> class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector;

1111/// Helper class for calculating the default number of inline elements for
1112/// `SmallVector<T>`.
1113///
1114/// This should be migrated to a constexpr function when our minimum
1115/// compiler support is enough for multi-statement constexpr functions.
1116template <typename T> struct CalculateSmallVectorDefaultInlinedElements {
// Parameter controlling the default number of inlined elements
// for `SmallVector<T>`.
//
// The default number of inlined elements ensures that
// 1. There is at least one inlined element.
// 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless
// it contradicts 1.
static constexpr size_t kPreferredSmallVectorSizeof = 64;

// static_assert that sizeof(T) is not "too big".
//
// Because our policy guarantees at least one inlined element, it is possible
// for an arbitrarily large inlined element to allocate an arbitrarily large
// amount of inline storage. We generally consider it an antipattern for a
// SmallVector to allocate an excessive amount of inline storage, so we want
// to call attention to these cases and make sure that users are making an
// intentional decision if they request a lot of inline storage.
//
// We want this assertion to trigger in pathological cases, but otherwise
// not be too easy to hit. To accomplish that, the cutoff is actually somewhat
// larger than kPreferredSmallVectorSizeof (otherwise,
// `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that
// pattern seems useful in practice).
//
// One wrinkle is that this assertion is in theory non-portable, since
// sizeof(T) is in general platform-dependent. However, we don't expect this
// to be much of an issue, because most LLVM development happens on 64-bit
// hosts, and therefore sizeof(T) is expected to *decrease* when compiled for
// 32-bit hosts, dodging the issue. The reverse situation, where development
// happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a
// 64-bit host, is expected to be very rare.
static_assert(
    sizeof(T) <= 256,
    "You are trying to use a default number of inlined elements for "
    "`SmallVector<T>` but `sizeof(T)` is really big! Please use an "
    "explicit number of inlined elements with `SmallVector<T, N>` to make "
    "sure you really want that much inline storage.");

// Discount the size of the header itself when calculating the maximum inline
// bytes.
static constexpr size_t PreferredInlineBytes =
    kPreferredSmallVectorSizeof - sizeof(SmallVector<T, 0>);
static constexpr size_t NumElementsThatFit = PreferredInlineBytes / sizeof(T);
static constexpr size_t value =
    NumElementsThatFit == 0 ? 1 : NumElementsThatFit;
1162};

1164/// This is a 'vector' (really, a variable-sized array), optimized
1165/// for the case when the array is small.  It contains some number of elements
1166/// in-place, which allows it to avoid heap allocation when the actual number of
1167/// elements is below that threshold.  This allows normal "small" cases to be
1168/// fast without losing generality for large inputs.
1169///
1170/// \note
1171/// In the absence of a well-motivated choice for the number of inlined
1172/// elements \p N, it is recommended to use \c SmallVector<T> (that is,
1173/// omitting the \p N). This will choose a default number of inlined elements
1174/// reasonable for allocation on the stack (for example, trying to keep \c
1175/// sizeof(SmallVector<T>) around 64 bytes).
1176///
1177/// \warning This does not attempt to be exception safe.
1178///
1179/// \see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h
1180template <typename T,
        unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value>
1182class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector : public SmallVectorImpl<T>,
                                 SmallVectorStorage<T, N> {
1184public:
SmallVector() : SmallVectorImpl<T>(N) {}

~SmallVector() {
  // Destroy the constructed elements in the vector.
  this->destroy_range(this->begin(), this->end());
}

explicit SmallVector(size_t Size, const T &Value = T())
  : SmallVectorImpl<T>(N) {
  this->assign(Size, Value);
}

template <typename ItTy,
          typename = std::enable_if_t<std::is_convertible<
              typename std::iterator_traits<ItTy>::iterator_category,
              std::input_iterator_tag>::value>>
SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
  this->append(S, E);
}

template <typename RangeTy>
explicit SmallVector(const iterator_range<RangeTy> &R)
    : SmallVectorImpl<T>(N) {
  this->append(R.begin(), R.end());
}

SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
  this->assign(IL);
}

SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
  if (!RHS.empty())
    SmallVectorImpl<T>::operator=(RHS);
}

SmallVector &operator=(const SmallVector &RHS) {
  SmallVectorImpl<T>::operator=(RHS);
  return *this;
}

SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
  if (!RHS.empty())
    SmallVectorImpl<T>::operator=(::std::move(RHS));
}

SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
  if (!RHS.empty())
    SmallVectorImpl<T>::operator=(::std::move(RHS));
}

SmallVector &operator=(SmallVector &&RHS) {
  if (N) {
    SmallVectorImpl<T>::operator=(::std::move(RHS));
    return *this;
  }
  // SmallVectorImpl<T>::operator= does not leverage N==0. Optimize the
  // case.
  if (this == &RHS)
    return *this;
  if (RHS.empty()) {
    this->destroy_range(this->begin(), this->end());
    this->Size = 0;
  } else {
    this->assignRemote(std::move(RHS));
  }
  return *this;
}

SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
  SmallVectorImpl<T>::operator=(::std::move(RHS));
  return *this;
}

SmallVector &operator=(std::initializer_list<T> IL) {
  this->assign(IL);
  return *this;
}
1262};

1264template <typename T, unsigned N>
1265inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
return X.capacity_in_bytes();
1267}

1269template <typename RangeType>
1270using ValueTypeFromRangeType =
  typename std::remove_const<typename std::remove_reference<
      decltype(*std::begin(std::declval<RangeType &>()))>::type>::type;

1274/// Given a range of type R, iterate the entire range and return a
1275/// SmallVector with elements of the vector.  This is useful, for example,
1276/// when you want to iterate a range and then sort the results.
1277template <unsigned Size, typename R>
1278SmallVector<ValueTypeFromRangeType<R>, Size> to_vector(R &&Range) {
return {std::begin(Range), std::end(Range)};
1280}
1281template <typename R>
1282SmallVector<ValueTypeFromRangeType<R>,
          CalculateSmallVectorDefaultInlinedElements<
              ValueTypeFromRangeType<R>>::value>
1285to_vector(R &&Range) {
return {std::begin(Range), std::end(Range)};
1287}

1289} // end namespace llvm

1291namespace std {

/// Implement std::swap in terms of SmallVector swap.
template<typename T>
inline void
swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
  LHS.swap(RHS);
}

/// Implement std::swap in terms of SmallVector swap.
template<typename T, unsigned N>
inline void
swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
  LHS.swap(RHS);
}

1307} // end namespace std

1309#endif // LLVM_ADT_SMALLVECTOR_H

←

/build/llvm-toolchain-snapshot-15~++20220211101351+43a1756a5d53/llvm/include/llvm/IR/IntrinsicInst.h

1//===-- llvm/IntrinsicInst.h - Intrinsic Instruction Wrappers ---*- C++ -*-===//
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//
9// This file defines classes that make it really easy to deal with intrinsic
10// functions with the isa/dyncast family of functions.  In particular, this
11// allows you to do things like:
12//
13//     if (MemCpyInst *MCI = dyn_cast<MemCpyInst>(Inst))
14//        ... MCI->getDest() ... MCI->getSource() ...
15//
16// All intrinsic function calls are instances of the call instruction, so these
17// are all subclasses of the CallInst class.  Note that none of these classes
18// has state or virtual methods, which is an important part of this gross/neat
19// hack working.
20//
21//===----------------------------------------------------------------------===//

23#ifndef LLVM_IR_INTRINSICINST_H
24#define LLVM_IR_INTRINSICINST_H

26#include "llvm/IR/Constants.h"
27#include "llvm/IR/DebugInfoMetadata.h"
28#include "llvm/IR/DerivedTypes.h"
29#include "llvm/IR/FPEnv.h"
30#include "llvm/IR/Function.h"
31#include "llvm/IR/GlobalVariable.h"
32#include "llvm/IR/Instructions.h"
33#include "llvm/IR/Intrinsics.h"
34#include "llvm/IR/Metadata.h"
35#include "llvm/IR/Value.h"
36#include "llvm/Support/Casting.h"
37#include <cassert>
38#include <cstdint>

40namespace llvm {

42/// A wrapper class for inspecting calls to intrinsic functions.
43/// This allows the standard isa/dyncast/cast functionality to work with calls
44/// to intrinsic functions.
45class IntrinsicInst : public CallInst {
46public:
IntrinsicInst() = delete;
IntrinsicInst(const IntrinsicInst &) = delete;
IntrinsicInst &operator=(const IntrinsicInst &) = delete;

/// Return the intrinsic ID of this intrinsic.
Intrinsic::ID getIntrinsicID() const {
  return getCalledFunction()->getIntrinsicID();
}

/// Return true if swapping the first two arguments to the intrinsic produces
/// the same result.
bool isCommutative() const {
  switch (getIntrinsicID()) {
  case Intrinsic::maxnum:
  case Intrinsic::minnum:
  case Intrinsic::maximum:
  case Intrinsic::minimum:
  case Intrinsic::smax:
  case Intrinsic::smin:
  case Intrinsic::umax:
  case Intrinsic::umin:
  case Intrinsic::sadd_sat:
  case Intrinsic::uadd_sat:
  case Intrinsic::sadd_with_overflow:
  case Intrinsic::uadd_with_overflow:
  case Intrinsic::smul_with_overflow:
  case Intrinsic::umul_with_overflow:
  case Intrinsic::smul_fix:
  case Intrinsic::umul_fix:
  case Intrinsic::smul_fix_sat:
  case Intrinsic::umul_fix_sat:
  case Intrinsic::fma:
  case Intrinsic::fmuladd:
    return true;
  default:
    return false;
  }
}

// Checks if the intrinsic is an annotation.
bool isAssumeLikeIntrinsic() const {
  switch (getIntrinsicID()) {
  default: break;
  case Intrinsic::assume:
  case Intrinsic::sideeffect:
  case Intrinsic::pseudoprobe:
  case Intrinsic::dbg_declare:
  case Intrinsic::dbg_value:
  case Intrinsic::dbg_label:
  case Intrinsic::invariant_start:
  case Intrinsic::invariant_end:
  case Intrinsic::lifetime_start:
  case Intrinsic::lifetime_end:
  case Intrinsic::experimental_noalias_scope_decl:
  case Intrinsic::objectsize:
  case Intrinsic::ptr_annotation:
  case Intrinsic::var_annotation:
    return true;
  }
  return false;
}

// Methods for support type inquiry through isa, cast, and dyn_cast:
static bool classof(const CallInst *I) {
  if (const Function *CF = I->getCalledFunction())
    return CF->isIntrinsic();
  return false;
}
static bool classof(const Value *V) {
  return isa<CallInst>(V) && classof(cast<CallInst>(V));
}
118};

120/// Check if \p ID corresponds to a debug info intrinsic.
121static inline bool isDbgInfoIntrinsic(Intrinsic::ID ID) {
switch (ID) {
case Intrinsic::dbg_declare:
case Intrinsic::dbg_value:
case Intrinsic::dbg_addr:
case Intrinsic::dbg_label:
  return true;
default:
  return false;
}
131}

133/// This is the common base class for debug info intrinsics.
134class DbgInfoIntrinsic : public IntrinsicInst {
135public:
/// \name Casting methods
/// @{
static bool classof(const IntrinsicInst *I) {
  return isDbgInfoIntrinsic(I->getIntrinsicID());
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
/// @}
145};

147/// This is the common base class for debug info intrinsics for variables.
148class DbgVariableIntrinsic : public DbgInfoIntrinsic {
149public:
// Iterator for ValueAsMetadata that internally uses direct pointer iteration
// over either a ValueAsMetadata* or a ValueAsMetadata**, dereferencing to the
// ValueAsMetadata .
class location_op_iterator
    : public iterator_facade_base<location_op_iterator,
                                  std::bidirectional_iterator_tag, Value *> {
  PointerUnion<ValueAsMetadata *, ValueAsMetadata **> I;

public:
  location_op_iterator(ValueAsMetadata *SingleIter) : I(SingleIter) {}
  location_op_iterator(ValueAsMetadata **MultiIter) : I(MultiIter) {}

  location_op_iterator(const location_op_iterator &R) : I(R.I) {}
  location_op_iterator &operator=(const location_op_iterator &R) {
    I = R.I;
    return *this;
  }
  bool operator==(const location_op_iterator &RHS) const {
    return I == RHS.I;
  }
  const Value *operator*() const {
    ValueAsMetadata *VAM = I.is<ValueAsMetadata *>()
                               ? I.get<ValueAsMetadata *>()
                               : *I.get<ValueAsMetadata **>();
    return VAM->getValue();
  };
  Value *operator*() {
    ValueAsMetadata *VAM = I.is<ValueAsMetadata *>()
                               ? I.get<ValueAsMetadata *>()
                               : *I.get<ValueAsMetadata **>();
    return VAM->getValue();
  }
  location_op_iterator &operator++() {
    if (I.is<ValueAsMetadata *>())
      I = I.get<ValueAsMetadata *>() + 1;
    else
      I = I.get<ValueAsMetadata **>() + 1;
    return *this;
  }
  location_op_iterator &operator--() {
    if (I.is<ValueAsMetadata *>())
      I = I.get<ValueAsMetadata *>() - 1;
    else
      I = I.get<ValueAsMetadata **>() - 1;
    return *this;
  }
};

/// Get the locations corresponding to the variable referenced by the debug
/// info intrinsic.  Depending on the intrinsic, this could be the
/// variable's value or its address.
iterator_range<location_op_iterator> location_ops() const;

Value *getVariableLocationOp(unsigned OpIdx) const;

void replaceVariableLocationOp(Value *OldValue, Value *NewValue);
void replaceVariableLocationOp(unsigned OpIdx, Value *NewValue);
/// Adding a new location operand will always result in this intrinsic using
/// an ArgList, and must always be accompanied by a new expression that uses
/// the new operand.
void addVariableLocationOps(ArrayRef<Value *> NewValues,
                            DIExpression *NewExpr);

void setVariable(DILocalVariable *NewVar) {
  setArgOperand(1, MetadataAsValue::get(NewVar->getContext(), NewVar));
}

void setExpression(DIExpression *NewExpr) {
  setArgOperand(2, MetadataAsValue::get(NewExpr->getContext(), NewExpr));
31
←
Called C++ object pointer is null
}

unsigned getNumVariableLocationOps() const {
  if (hasArgList())
    return cast<DIArgList>(getRawLocation())->getArgs().size();
  return 1;
}

bool hasArgList() const { return isa<DIArgList>(getRawLocation()); }

/// Does this describe the address of a local variable. True for dbg.addr
/// and dbg.declare, but not dbg.value, which describes its value.
bool isAddressOfVariable() const {
  return getIntrinsicID() != Intrinsic::dbg_value;
}

void setUndef() {
  // TODO: When/if we remove duplicate values from DIArgLists, we don't need
  // this set anymore.
  SmallPtrSet<Value *, 4> RemovedValues;
  for (Value *OldValue : location_ops()) {
    if (!RemovedValues.insert(OldValue).second)
      continue;
    Value *Undef = UndefValue::get(OldValue->getType());
    replaceVariableLocationOp(OldValue, Undef);
  }
}

bool isUndef() const {
  return (getNumVariableLocationOps() == 0 &&
          !getExpression()->isComplex()) ||
         any_of(location_ops(), [](Value *V) { return isa<UndefValue>(V); });
}

DILocalVariable *getVariable() const {
  return cast<DILocalVariable>(getRawVariable());
}

DIExpression *getExpression() const {
  return cast<DIExpression>(getRawExpression());
}

Metadata *getRawLocation() const {
  return cast<MetadataAsValue>(getArgOperand(0))->getMetadata();
}

Metadata *getRawVariable() const {
  return cast<MetadataAsValue>(getArgOperand(1))->getMetadata();
}

Metadata *getRawExpression() const {
  return cast<MetadataAsValue>(getArgOperand(2))->getMetadata();
}

/// Use of this should generally be avoided; instead,
/// replaceVariableLocationOp and addVariableLocationOps should be used where
/// possible to avoid creating invalid state.
void setRawLocation(Metadata *Location) {
  return setArgOperand(0, MetadataAsValue::get(getContext(), Location));
}

/// Get the size (in bits) of the variable, or fragment of the variable that
/// is described.
Optional<uint64_t> getFragmentSizeInBits() const;

/// \name Casting methods
/// @{
static bool classof(const IntrinsicInst *I) {
  switch (I->getIntrinsicID()) {
  case Intrinsic::dbg_declare:
  case Intrinsic::dbg_value:
  case Intrinsic::dbg_addr:
    return true;
  default:
    return false;
  }
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
/// @}
300private:
void setArgOperand(unsigned i, Value *v) {
  DbgInfoIntrinsic::setArgOperand(i, v);
}
void setOperand(unsigned i, Value *v) { DbgInfoIntrinsic::setOperand(i, v); }
305};

307/// This represents the llvm.dbg.declare instruction.
308class DbgDeclareInst : public DbgVariableIntrinsic {
309public:
Value *getAddress() const {
  assert(getNumVariableLocationOps() == 1 &&(static_cast <bool> (getNumVariableLocationOps() == 1 &&
 "dbg.declare must have exactly 1 location operand.") ? void (
0) : __assert_fail ("getNumVariableLocationOps() == 1 && \"dbg.declare must have exactly 1 location operand.\""
, "llvm/include/llvm/IR/IntrinsicInst.h", 312, __extension__ __PRETTY_FUNCTION__
))
         "dbg.declare must have exactly 1 location operand.")(static_cast <bool> (getNumVariableLocationOps() == 1 &&
 "dbg.declare must have exactly 1 location operand.") ? void (
0) : __assert_fail ("getNumVariableLocationOps() == 1 && \"dbg.declare must have exactly 1 location operand.\""
, "llvm/include/llvm/IR/IntrinsicInst.h", 312, __extension__ __PRETTY_FUNCTION__
));
  return getVariableLocationOp(0);
}

/// \name Casting methods
/// @{
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::dbg_declare;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
/// @}
325};

327/// This represents the llvm.dbg.addr instruction.
328class DbgAddrIntrinsic : public DbgVariableIntrinsic {
329public:
Value *getAddress() const {
  assert(getNumVariableLocationOps() == 1 &&(static_cast <bool> (getNumVariableLocationOps() == 1 &&
 "dbg.addr must have exactly 1 location operand.") ? void (0)
 : __assert_fail ("getNumVariableLocationOps() == 1 && \"dbg.addr must have exactly 1 location operand.\""
, "llvm/include/llvm/IR/IntrinsicInst.h", 332, __extension__ __PRETTY_FUNCTION__
))
         "dbg.addr must have exactly 1 location operand.")(static_cast <bool> (getNumVariableLocationOps() == 1 &&
 "dbg.addr must have exactly 1 location operand.") ? void (0)
 : __assert_fail ("getNumVariableLocationOps() == 1 && \"dbg.addr must have exactly 1 location operand.\""
, "llvm/include/llvm/IR/IntrinsicInst.h", 332, __extension__ __PRETTY_FUNCTION__
));
  return getVariableLocationOp(0);
}

/// \name Casting methods
/// @{
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::dbg_addr;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
344};

346/// This represents the llvm.dbg.value instruction.
347class DbgValueInst : public DbgVariableIntrinsic {
348public:
// The default argument should only be used in ISel, and the default option
// should be removed once ISel support for multiple location ops is complete.
Value *getValue(unsigned OpIdx = 0) const {
  return getVariableLocationOp(OpIdx);
}
iterator_range<location_op_iterator> getValues() const {
  return location_ops();
}

/// \name Casting methods
/// @{
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::dbg_value;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
/// @}
367};

369/// This represents the llvm.dbg.label instruction.
370class DbgLabelInst : public DbgInfoIntrinsic {
371public:
DILabel *getLabel() const { return cast<DILabel>(getRawLabel()); }

Metadata *getRawLabel() const {
  return cast<MetadataAsValue>(getArgOperand(0))->getMetadata();
}

/// Methods for support type inquiry through isa, cast, and dyn_cast:
/// @{
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::dbg_label;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
/// @}
387};

389/// This is the common base class for vector predication intrinsics.
390class VPIntrinsic : public IntrinsicInst {
391public:
/// \brief Declares a llvm.vp.* intrinsic in \p M that matches the parameters
/// \p Params. Additionally, the load and gather intrinsics require
/// \p ReturnType to be specified.
static Function *getDeclarationForParams(Module *M, Intrinsic::ID,
                                         Type *ReturnType,
                                         ArrayRef<Value *> Params);

static Optional<unsigned> getMaskParamPos(Intrinsic::ID IntrinsicID);
static Optional<unsigned> getVectorLengthParamPos(Intrinsic::ID IntrinsicID);

/// The llvm.vp.* intrinsics for this instruction Opcode
static Intrinsic::ID getForOpcode(unsigned OC);

// Whether \p ID is a VP intrinsic ID.
static bool isVPIntrinsic(Intrinsic::ID);

/// \return The mask parameter or nullptr.
Value *getMaskParam() const;
void setMaskParam(Value *);

/// \return The vector length parameter or nullptr.
Value *getVectorLengthParam() const;
void setVectorLengthParam(Value *);

/// \return Whether the vector length param can be ignored.
bool canIgnoreVectorLengthParam() const;

/// \return The static element count (vector number of elements) the vector
/// length parameter applies to.
ElementCount getStaticVectorLength() const;

/// \return The alignment of the pointer used by this load/store/gather or
/// scatter.
MaybeAlign getPointerAlignment() const;
// MaybeAlign setPointerAlignment(Align NewAlign); // TODO

/// \return The pointer operand of this load,store, gather or scatter.
Value *getMemoryPointerParam() const;
static Optional<unsigned> getMemoryPointerParamPos(Intrinsic::ID);

/// \return The data (payload) operand of this store or scatter.
Value *getMemoryDataParam() const;
static Optional<unsigned> getMemoryDataParamPos(Intrinsic::ID);

// Methods for support type inquiry through isa, cast, and dyn_cast:
static bool classof(const IntrinsicInst *I) {
  return isVPIntrinsic(I->getIntrinsicID());
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}

// Equivalent non-predicated opcode
Optional<unsigned> getFunctionalOpcode() const {
  return getFunctionalOpcodeForVP(getIntrinsicID());
}

// Equivalent non-predicated opcode
static Optional<unsigned> getFunctionalOpcodeForVP(Intrinsic::ID ID);
451};

453/// This represents vector predication reduction intrinsics.
454class VPReductionIntrinsic : public VPIntrinsic {
455public:
static bool isVPReduction(Intrinsic::ID ID);

unsigned getStartParamPos() const;
unsigned getVectorParamPos() const;

static Optional<unsigned> getStartParamPos(Intrinsic::ID ID);
static Optional<unsigned> getVectorParamPos(Intrinsic::ID ID);

/// Methods for support type inquiry through isa, cast, and dyn_cast:
/// @{
static bool classof(const IntrinsicInst *I) {
  return VPReductionIntrinsic::isVPReduction(I->getIntrinsicID());
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
/// @}
473};

475/// This is the common base class for constrained floating point intrinsics.
476class ConstrainedFPIntrinsic : public IntrinsicInst {
477public:
bool isUnaryOp() const;
bool isTernaryOp() const;
Optional<RoundingMode> getRoundingMode() const;
Optional<fp::ExceptionBehavior> getExceptionBehavior() const;
bool isDefaultFPEnvironment() const;

// Methods for support type inquiry through isa, cast, and dyn_cast:
static bool classof(const IntrinsicInst *I);
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
489};

491/// Constrained floating point compare intrinsics.
492class ConstrainedFPCmpIntrinsic : public ConstrainedFPIntrinsic {
493public:
FCmpInst::Predicate getPredicate() const;
bool isSignaling() const {
  return getIntrinsicID() == Intrinsic::experimental_constrained_fcmps;
}

// Methods for support type inquiry through isa, cast, and dyn_cast:
static bool classof(const IntrinsicInst *I) {
  switch (I->getIntrinsicID()) {
  case Intrinsic::experimental_constrained_fcmp:
  case Intrinsic::experimental_constrained_fcmps:
    return true;
  default:
    return false;
  }
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
512};

514/// This class represents min/max intrinsics.
515class MinMaxIntrinsic : public IntrinsicInst {
516public:
static bool classof(const IntrinsicInst *I) {
  switch (I->getIntrinsicID()) {
  case Intrinsic::umin:
  case Intrinsic::umax:
  case Intrinsic::smin:
  case Intrinsic::smax:
    return true;
  default:
    return false;
  }
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}

Value *getLHS() const { return const_cast<Value *>(getArgOperand(0)); }
Value *getRHS() const { return const_cast<Value *>(getArgOperand(1)); }

/// Returns the comparison predicate underlying the intrinsic.
static ICmpInst::Predicate getPredicate(Intrinsic::ID ID) {
  switch (ID) {
  case Intrinsic::umin:
    return ICmpInst::Predicate::ICMP_ULT;
  case Intrinsic::umax:
    return ICmpInst::Predicate::ICMP_UGT;
  case Intrinsic::smin:
    return ICmpInst::Predicate::ICMP_SLT;
  case Intrinsic::smax:
    return ICmpInst::Predicate::ICMP_SGT;
  default:
    llvm_unreachable("Invalid intrinsic")::llvm::llvm_unreachable_internal("Invalid intrinsic", "llvm/include/llvm/IR/IntrinsicInst.h"
, 547);
  }
}

/// Returns the comparison predicate underlying the intrinsic.
ICmpInst::Predicate getPredicate() const {
  return getPredicate(getIntrinsicID());
}

/// Whether the intrinsic is signed or unsigned.
static bool isSigned(Intrinsic::ID ID) {
  return ICmpInst::isSigned(getPredicate(ID));
};

/// Whether the intrinsic is signed or unsigned.
bool isSigned() const { return isSigned(getIntrinsicID()); };

/// Min/max intrinsics are monotonic, they operate on a fixed-bitwidth values,
/// so there is a certain threshold value, upon reaching which,
/// their value can no longer change. Return said threshold.
static APInt getSaturationPoint(Intrinsic::ID ID, unsigned numBits) {
  switch (ID) {
  case Intrinsic::umin:
    return APInt::getMinValue(numBits);
  case Intrinsic::umax:
    return APInt::getMaxValue(numBits);
  case Intrinsic::smin:
    return APInt::getSignedMinValue(numBits);
  case Intrinsic::smax:
    return APInt::getSignedMaxValue(numBits);
  default:
    llvm_unreachable("Invalid intrinsic")::llvm::llvm_unreachable_internal("Invalid intrinsic", "llvm/include/llvm/IR/IntrinsicInst.h"
, 578);
  }
}

/// Min/max intrinsics are monotonic, they operate on a fixed-bitwidth values,
/// so there is a certain threshold value, upon reaching which,
/// their value can no longer change. Return said threshold.
APInt getSaturationPoint(unsigned numBits) const {
  return getSaturationPoint(getIntrinsicID(), numBits);
}

/// Min/max intrinsics are monotonic, they operate on a fixed-bitwidth values,
/// so there is a certain threshold value, upon reaching which,
/// their value can no longer change. Return said threshold.
static Constant *getSaturationPoint(Intrinsic::ID ID, Type *Ty) {
  return Constant::getIntegerValue(
      Ty, getSaturationPoint(ID, Ty->getScalarSizeInBits()));
}

/// Min/max intrinsics are monotonic, they operate on a fixed-bitwidth values,
/// so there is a certain threshold value, upon reaching which,
/// their value can no longer change. Return said threshold.
Constant *getSaturationPoint(Type *Ty) const {
  return getSaturationPoint(getIntrinsicID(), Ty);
}
603};

605/// This class represents an intrinsic that is based on a binary operation.
606/// This includes op.with.overflow and saturating add/sub intrinsics.
607class BinaryOpIntrinsic : public IntrinsicInst {
608public:
static bool classof(const IntrinsicInst *I) {
  switch (I->getIntrinsicID()) {
  case Intrinsic::uadd_with_overflow:
  case Intrinsic::sadd_with_overflow:
  case Intrinsic::usub_with_overflow:
  case Intrinsic::ssub_with_overflow:
  case Intrinsic::umul_with_overflow:
  case Intrinsic::smul_with_overflow:
  case Intrinsic::uadd_sat:
  case Intrinsic::sadd_sat:
  case Intrinsic::usub_sat:
  case Intrinsic::ssub_sat:
    return true;
  default:
    return false;
  }
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}

Value *getLHS() const { return const_cast<Value *>(getArgOperand(0)); }
Value *getRHS() const { return const_cast<Value *>(getArgOperand(1)); }

/// Returns the binary operation underlying the intrinsic.
Instruction::BinaryOps getBinaryOp() const;

/// Whether the intrinsic is signed or unsigned.
bool isSigned() const;

/// Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
unsigned getNoWrapKind() const;
641};

643/// Represents an op.with.overflow intrinsic.
644class WithOverflowInst : public BinaryOpIntrinsic {
645public:
static bool classof(const IntrinsicInst *I) {
  switch (I->getIntrinsicID()) {
  case Intrinsic::uadd_with_overflow:
  case Intrinsic::sadd_with_overflow:
  case Intrinsic::usub_with_overflow:
  case Intrinsic::ssub_with_overflow:
  case Intrinsic::umul_with_overflow:
  case Intrinsic::smul_with_overflow:
    return true;
  default:
    return false;
  }
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
662};

664/// Represents a saturating add/sub intrinsic.
665class SaturatingInst : public BinaryOpIntrinsic {
666public:
static bool classof(const IntrinsicInst *I) {
  switch (I->getIntrinsicID()) {
  case Intrinsic::uadd_sat:
  case Intrinsic::sadd_sat:
  case Intrinsic::usub_sat:
  case Intrinsic::ssub_sat:
    return true;
  default:
    return false;
  }
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
681};

683/// Common base class for all memory intrinsics. Simply provides
684/// common methods.
685/// Written as CRTP to avoid a common base class amongst the
686/// three atomicity hierarchies.
687template <typename Derived> class MemIntrinsicBase : public IntrinsicInst {
688private:
enum { ARG_DEST = 0, ARG_LENGTH = 2 };

691public:
Value *getRawDest() const {
  return const_cast<Value *>(getArgOperand(ARG_DEST));
}
const Use &getRawDestUse() const { return getArgOperandUse(ARG_DEST); }
Use &getRawDestUse() { return getArgOperandUse(ARG_DEST); }

Value *getLength() const {
  return const_cast<Value *>(getArgOperand(ARG_LENGTH));
}
const Use &getLengthUse() const { return getArgOperandUse(ARG_LENGTH); }
Use &getLengthUse() { return getArgOperandUse(ARG_LENGTH); }

/// This is just like getRawDest, but it strips off any cast
/// instructions (including addrspacecast) that feed it, giving the
/// original input.  The returned value is guaranteed to be a pointer.
Value *getDest() const { return getRawDest()->stripPointerCasts(); }

unsigned getDestAddressSpace() const {
  return cast<PointerType>(getRawDest()->getType())->getAddressSpace();
}

/// FIXME: Remove this function once transition to Align is over.
/// Use getDestAlign() instead.
unsigned getDestAlignment() const {
  if (auto MA = getParamAlign(ARG_DEST))
    return MA->value();
  return 0;
}
MaybeAlign getDestAlign() const { return getParamAlign(ARG_DEST); }

/// Set the specified arguments of the instruction.
void setDest(Value *Ptr) {
  assert(getRawDest()->getType() == Ptr->getType() &&(static_cast <bool> (getRawDest()->getType() == Ptr->
getType() && "setDest called with pointer of wrong type!"
) ? void (0) : __assert_fail ("getRawDest()->getType() == Ptr->getType() && \"setDest called with pointer of wrong type!\""
, "llvm/include/llvm/IR/IntrinsicInst.h", 725, __extension__ __PRETTY_FUNCTION__
))
         "setDest called with pointer of wrong type!")(static_cast <bool> (getRawDest()->getType() == Ptr->
getType() && "setDest called with pointer of wrong type!"
) ? void (0) : __assert_fail ("getRawDest()->getType() == Ptr->getType() && \"setDest called with pointer of wrong type!\""
, "llvm/include/llvm/IR/IntrinsicInst.h", 725, __extension__ __PRETTY_FUNCTION__
));
  setArgOperand(ARG_DEST, Ptr);
}

/// FIXME: Remove this function once transition to Align is over.
/// Use the version that takes MaybeAlign instead of this one.
void setDestAlignment(unsigned Alignment) {
  setDestAlignment(MaybeAlign(Alignment));
}
void setDestAlignment(MaybeAlign Alignment) {
  removeParamAttr(ARG_DEST, Attribute::Alignment);
  if (Alignment)
    addParamAttr(ARG_DEST,
                 Attribute::getWithAlignment(getContext(), *Alignment));
}
void setDestAlignment(Align Alignment) {
  removeParamAttr(ARG_DEST, Attribute::Alignment);
  addParamAttr(ARG_DEST,
               Attribute::getWithAlignment(getContext(), Alignment));
}

void setLength(Value *L) {
  assert(getLength()->getType() == L->getType() &&(static_cast <bool> (getLength()->getType() == L->
getType() && "setLength called with value of wrong type!"
) ? void (0) : __assert_fail ("getLength()->getType() == L->getType() && \"setLength called with value of wrong type!\""
, "llvm/include/llvm/IR/IntrinsicInst.h", 748, __extension__ __PRETTY_FUNCTION__
))
         "setLength called with value of wrong type!")(static_cast <bool> (getLength()->getType() == L->
getType() && "setLength called with value of wrong type!"
) ? void (0) : __assert_fail ("getLength()->getType() == L->getType() && \"setLength called with value of wrong type!\""
, "llvm/include/llvm/IR/IntrinsicInst.h", 748, __extension__ __PRETTY_FUNCTION__
));
  setArgOperand(ARG_LENGTH, L);
}
751};

753/// Common base class for all memory transfer intrinsics. Simply provides
754/// common methods.
755template <class BaseCL> class MemTransferBase : public BaseCL {
756private:
enum { ARG_SOURCE = 1 };

759public:
/// Return the arguments to the instruction.
Value *getRawSource() const {
  return const_cast<Value *>(BaseCL::getArgOperand(ARG_SOURCE));
}
const Use &getRawSourceUse() const {
  return BaseCL::getArgOperandUse(ARG_SOURCE);
}
Use &getRawSourceUse() { return BaseCL::getArgOperandUse(ARG_SOURCE); }

/// This is just like getRawSource, but it strips off any cast
/// instructions that feed it, giving the original input.  The returned
/// value is guaranteed to be a pointer.
Value *getSource() const { return getRawSource()->stripPointerCasts(); }

unsigned getSourceAddressSpace() const {
  return cast<PointerType>(getRawSource()->getType())->getAddressSpace();
}

/// FIXME: Remove this function once transition to Align is over.
/// Use getSourceAlign() instead.
unsigned getSourceAlignment() const {
  if (auto MA = BaseCL::getParamAlign(ARG_SOURCE))
    return MA->value();
  return 0;
}

MaybeAlign getSourceAlign() const {
  return BaseCL::getParamAlign(ARG_SOURCE);
}

void setSource(Value *Ptr) {
  assert(getRawSource()->getType() == Ptr->getType() &&(static_cast <bool> (getRawSource()->getType() == Ptr
->getType() && "setSource called with pointer of wrong type!"
) ? void (0) : __assert_fail ("getRawSource()->getType() == Ptr->getType() && \"setSource called with pointer of wrong type!\""
, "llvm/include/llvm/IR/IntrinsicInst.h", 792, __extension__ __PRETTY_FUNCTION__
))
         "setSource called with pointer of wrong type!")(static_cast <bool> (getRawSource()->getType() == Ptr
->getType() && "setSource called with pointer of wrong type!"
) ? void (0) : __assert_fail ("getRawSource()->getType() == Ptr->getType() && \"setSource called with pointer of wrong type!\""
, "llvm/include/llvm/IR/IntrinsicInst.h", 792, __extension__ __PRETTY_FUNCTION__
));
  BaseCL::setArgOperand(ARG_SOURCE, Ptr);
}

/// FIXME: Remove this function once transition to Align is over.
/// Use the version that takes MaybeAlign instead of this one.
void setSourceAlignment(unsigned Alignment) {
  setSourceAlignment(MaybeAlign(Alignment));
}
void setSourceAlignment(MaybeAlign Alignment) {
  BaseCL::removeParamAttr(ARG_SOURCE, Attribute::Alignment);
  if (Alignment)
    BaseCL::addParamAttr(ARG_SOURCE, Attribute::getWithAlignment(
                                         BaseCL::getContext(), *Alignment));
}
void setSourceAlignment(Align Alignment) {
  BaseCL::removeParamAttr(ARG_SOURCE, Attribute::Alignment);
  BaseCL::addParamAttr(ARG_SOURCE, Attribute::getWithAlignment(
                                       BaseCL::getContext(), Alignment));
}
812};

814/// Common base class for all memset intrinsics. Simply provides
815/// common methods.
816template <class BaseCL> class MemSetBase : public BaseCL {
817private:
enum { ARG_VALUE = 1 };

820public:
Value *getValue() const {
  return const_cast<Value *>(BaseCL::getArgOperand(ARG_VALUE));
}
const Use &getValueUse() const { return BaseCL::getArgOperandUse(ARG_VALUE); }
Use &getValueUse() { return BaseCL::getArgOperandUse(ARG_VALUE); }

void setValue(Value *Val) {
  assert(getValue()->getType() == Val->getType() &&(static_cast <bool> (getValue()->getType() == Val->
getType() && "setValue called with value of wrong type!"
) ? void (0) : __assert_fail ("getValue()->getType() == Val->getType() && \"setValue called with value of wrong type!\""
, "llvm/include/llvm/IR/IntrinsicInst.h", 829, __extension__ __PRETTY_FUNCTION__
))
         "setValue called with value of wrong type!")(static_cast <bool> (getValue()->getType() == Val->
getType() && "setValue called with value of wrong type!"
) ? void (0) : __assert_fail ("getValue()->getType() == Val->getType() && \"setValue called with value of wrong type!\""
, "llvm/include/llvm/IR/IntrinsicInst.h", 829, __extension__ __PRETTY_FUNCTION__
));
  BaseCL::setArgOperand(ARG_VALUE, Val);
}
832};

834// The common base class for the atomic memset/memmove/memcpy intrinsics
835// i.e. llvm.element.unordered.atomic.memset/memcpy/memmove
836class AtomicMemIntrinsic : public MemIntrinsicBase<AtomicMemIntrinsic> {
837private:
enum { ARG_ELEMENTSIZE = 3 };

840public:
Value *getRawElementSizeInBytes() const {
  return const_cast<Value *>(getArgOperand(ARG_ELEMENTSIZE));
}

ConstantInt *getElementSizeInBytesCst() const {
  return cast<ConstantInt>(getRawElementSizeInBytes());
}

uint32_t getElementSizeInBytes() const {
  return getElementSizeInBytesCst()->getZExtValue();
}

void setElementSizeInBytes(Constant *V) {
  assert(V->getType() == Type::getInt8Ty(getContext()) &&(static_cast <bool> (V->getType() == Type::getInt8Ty
(getContext()) && "setElementSizeInBytes called with value of wrong type!"
) ? void (0) : __assert_fail ("V->getType() == Type::getInt8Ty(getContext()) && \"setElementSizeInBytes called with value of wrong type!\""
, "llvm/include/llvm/IR/IntrinsicInst.h", 855, __extension__ __PRETTY_FUNCTION__
))
         "setElementSizeInBytes called with value of wrong type!")(static_cast <bool> (V->getType() == Type::getInt8Ty
(getContext()) && "setElementSizeInBytes called with value of wrong type!"
) ? void (0) : __assert_fail ("V->getType() == Type::getInt8Ty(getContext()) && \"setElementSizeInBytes called with value of wrong type!\""
, "llvm/include/llvm/IR/IntrinsicInst.h", 855, __extension__ __PRETTY_FUNCTION__
));
  setArgOperand(ARG_ELEMENTSIZE, V);
}

static bool classof(const IntrinsicInst *I) {
  switch (I->getIntrinsicID()) {
  case Intrinsic::memcpy_element_unordered_atomic:
  case Intrinsic::memmove_element_unordered_atomic:
  case Intrinsic::memset_element_unordered_atomic:
    return true;
  default:
    return false;
  }
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
872};

874/// This class represents atomic memset intrinsic
875// i.e. llvm.element.unordered.atomic.memset
876class AtomicMemSetInst : public MemSetBase<AtomicMemIntrinsic> {
877public:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::memset_element_unordered_atomic;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
884};

886// This class wraps the atomic memcpy/memmove intrinsics
887// i.e. llvm.element.unordered.atomic.memcpy/memmove
888class AtomicMemTransferInst : public MemTransferBase<AtomicMemIntrinsic> {
889public:
static bool classof(const IntrinsicInst *I) {
  switch (I->getIntrinsicID()) {
  case Intrinsic::memcpy_element_unordered_atomic:
  case Intrinsic::memmove_element_unordered_atomic:
    return true;
  default:
    return false;
  }
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
902};

904/// This class represents the atomic memcpy intrinsic
905/// i.e. llvm.element.unordered.atomic.memcpy
906class AtomicMemCpyInst : public AtomicMemTransferInst {
907public:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::memcpy_element_unordered_atomic;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
914};

916/// This class represents the atomic memmove intrinsic
917/// i.e. llvm.element.unordered.atomic.memmove
918class AtomicMemMoveInst : public AtomicMemTransferInst {
919public:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::memmove_element_unordered_atomic;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
926};

928/// This is the common base class for memset/memcpy/memmove.
929class MemIntrinsic : public MemIntrinsicBase<MemIntrinsic> {
930private:
enum { ARG_VOLATILE = 3 };

933public:
ConstantInt *getVolatileCst() const {
  return cast<ConstantInt>(const_cast<Value *>(getArgOperand(ARG_VOLATILE)));
}

bool isVolatile() const { return !getVolatileCst()->isZero(); }

void setVolatile(Constant *V) { setArgOperand(ARG_VOLATILE, V); }

// Methods for support type inquiry through isa, cast, and dyn_cast:
static bool classof(const IntrinsicInst *I) {
  switch (I->getIntrinsicID()) {
  case Intrinsic::memcpy:
  case Intrinsic::memmove:
  case Intrinsic::memset:
  case Intrinsic::memcpy_inline:
    return true;
  default:
    return false;
  }
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
957};

959/// This class wraps the llvm.memset intrinsic.
960class MemSetInst : public MemSetBase<MemIntrinsic> {
961public:
// Methods for support type inquiry through isa, cast, and dyn_cast:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::memset;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
969};

971/// This class wraps the llvm.memcpy/memmove intrinsics.
972class MemTransferInst : public MemTransferBase<MemIntrinsic> {
973public:
// Methods for support type inquiry through isa, cast, and dyn_cast:
static bool classof(const IntrinsicInst *I) {
  switch (I->getIntrinsicID()) {
  case Intrinsic::memcpy:
  case Intrinsic::memmove:
  case Intrinsic::memcpy_inline:
    return true;
  default:
    return false;
  }
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
988};

990/// This class wraps the llvm.memcpy intrinsic.
991class MemCpyInst : public MemTransferInst {
992public:
// Methods for support type inquiry through isa, cast, and dyn_cast:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::memcpy ||
         I->getIntrinsicID() == Intrinsic::memcpy_inline;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
1001};

1003/// This class wraps the llvm.memmove intrinsic.
1004class MemMoveInst : public MemTransferInst {
1005public:
// Methods for support type inquiry through isa, cast, and dyn_cast:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::memmove;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
1013};

1015/// This class wraps the llvm.memcpy.inline intrinsic.
1016class MemCpyInlineInst : public MemCpyInst {
1017public:
ConstantInt *getLength() const {
  return cast<ConstantInt>(MemCpyInst::getLength());
}
// Methods for support type inquiry through isa, cast, and dyn_cast:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::memcpy_inline;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
1028};

1030// The common base class for any memset/memmove/memcpy intrinsics;
1031// whether they be atomic or non-atomic.
1032// i.e. llvm.element.unordered.atomic.memset/memcpy/memmove
1033//  and llvm.memset/memcpy/memmove
1034class AnyMemIntrinsic : public MemIntrinsicBase<AnyMemIntrinsic> {
1035public:
bool isVolatile() const {
  // Only the non-atomic intrinsics can be volatile
  if (auto *MI = dyn_cast<MemIntrinsic>(this))
    return MI->isVolatile();
  return false;
}

static bool classof(const IntrinsicInst *I) {
  switch (I->getIntrinsicID()) {
  case Intrinsic::memcpy:
  case Intrinsic::memcpy_inline:
  case Intrinsic::memmove:
  case Intrinsic::memset:
  case Intrinsic::memcpy_element_unordered_atomic:
  case Intrinsic::memmove_element_unordered_atomic:
  case Intrinsic::memset_element_unordered_atomic:
    return true;
  default:
    return false;
  }
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
1060};

1062/// This class represents any memset intrinsic
1063// i.e. llvm.element.unordered.atomic.memset
1064// and  llvm.memset
1065class AnyMemSetInst : public MemSetBase<AnyMemIntrinsic> {
1066public:
static bool classof(const IntrinsicInst *I) {
  switch (I->getIntrinsicID()) {
  case Intrinsic::memset:
  case Intrinsic::memset_element_unordered_atomic:
    return true;
  default:
    return false;
  }
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
1079};

1081// This class wraps any memcpy/memmove intrinsics
1082// i.e. llvm.element.unordered.atomic.memcpy/memmove
1083// and  llvm.memcpy/memmove
1084class AnyMemTransferInst : public MemTransferBase<AnyMemIntrinsic> {
1085public:
static bool classof(const IntrinsicInst *I) {
  switch (I->getIntrinsicID()) {
  case Intrinsic::memcpy:
  case Intrinsic::memcpy_inline:
  case Intrinsic::memmove:
  case Intrinsic::memcpy_element_unordered_atomic:
  case Intrinsic::memmove_element_unordered_atomic:
    return true;
  default:
    return false;
  }
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
1101};

1103/// This class represents any memcpy intrinsic
1104/// i.e. llvm.element.unordered.atomic.memcpy
1105///  and llvm.memcpy
1106class AnyMemCpyInst : public AnyMemTransferInst {
1107public:
static bool classof(const IntrinsicInst *I) {
  switch (I->getIntrinsicID()) {
  case Intrinsic::memcpy:
  case Intrinsic::memcpy_inline:
  case Intrinsic::memcpy_element_unordered_atomic:
    return true;
  default:
    return false;
  }
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
1121};

1123/// This class represents any memmove intrinsic
1124/// i.e. llvm.element.unordered.atomic.memmove
1125///  and llvm.memmove
1126class AnyMemMoveInst : public AnyMemTransferInst {
1127public:
static bool classof(const IntrinsicInst *I) {
  switch (I->getIntrinsicID()) {
  case Intrinsic::memmove:
  case Intrinsic::memmove_element_unordered_atomic:
    return true;
  default:
    return false;
  }
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
1140};

1142/// This represents the llvm.va_start intrinsic.
1143class VAStartInst : public IntrinsicInst {
1144public:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::vastart;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}

Value *getArgList() const { return const_cast<Value *>(getArgOperand(0)); }
1153};

1155/// This represents the llvm.va_end intrinsic.
1156class VAEndInst : public IntrinsicInst {
1157public:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::vaend;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}

Value *getArgList() const { return const_cast<Value *>(getArgOperand(0)); }
1166};

1168/// This represents the llvm.va_copy intrinsic.
1169class VACopyInst : public IntrinsicInst {
1170public:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::vacopy;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}

Value *getDest() const { return const_cast<Value *>(getArgOperand(0)); }
Value *getSrc() const { return const_cast<Value *>(getArgOperand(1)); }
1180};

1182/// A base class for all instrprof intrinsics.
1183class InstrProfInstBase : public IntrinsicInst {
1184public:
// The name of the instrumented function.
GlobalVariable *getName() const {
  return cast<GlobalVariable>(
      const_cast<Value *>(getArgOperand(0))->stripPointerCasts());
}
// The hash of the CFG for the instrumented function.
ConstantInt *getHash() const {
  return cast<ConstantInt>(const_cast<Value *>(getArgOperand(1)));
}
// The number of counters for the instrumented function.
ConstantInt *getNumCounters() const;
// The index of the counter that this instruction acts on.
ConstantInt *getIndex() const;
1198};

1200/// This represents the llvm.instrprof.cover intrinsic.
1201class InstrProfCoverInst : public InstrProfInstBase {
1202public:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::instrprof_cover;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
1209};

1211/// This represents the llvm.instrprof.increment intrinsic.
1212class InstrProfIncrementInst : public InstrProfInstBase {
1213public:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::instrprof_increment;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
Value *getStep() const;
1221};

1223/// This represents the llvm.instrprof.increment.step intrinsic.
1224class InstrProfIncrementInstStep : public InstrProfIncrementInst {
1225public:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::instrprof_increment_step;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
1232};

1234/// This represents the llvm.instrprof.value.profile intrinsic.
1235class InstrProfValueProfileInst : public InstrProfInstBase {
1236public:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::instrprof_value_profile;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}

Value *getTargetValue() const {
  return cast<Value>(const_cast<Value *>(getArgOperand(2)));
}

ConstantInt *getValueKind() const {
  return cast<ConstantInt>(const_cast<Value *>(getArgOperand(3)));
}

// Returns the value site index.
ConstantInt *getIndex() const {
  return cast<ConstantInt>(const_cast<Value *>(getArgOperand(4)));
}
1256};

1258class PseudoProbeInst : public IntrinsicInst {
1259public:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::pseudoprobe;
}

static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}

ConstantInt *getFuncGuid() const {
  return cast<ConstantInt>(const_cast<Value *>(getArgOperand(0)));
}

ConstantInt *getIndex() const {
  return cast<ConstantInt>(const_cast<Value *>(getArgOperand(1)));
}

ConstantInt *getAttributes() const {
  return cast<ConstantInt>(const_cast<Value *>(getArgOperand(2)));
}

ConstantInt *getFactor() const {
  return cast<ConstantInt>(const_cast<Value *>(getArgOperand(3)));
}
1283};

1285class NoAliasScopeDeclInst : public IntrinsicInst {
1286public:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::experimental_noalias_scope_decl;
}

static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}

MDNode *getScopeList() const {
  auto *MV =
      cast<MetadataAsValue>(getOperand(Intrinsic::NoAliasScopeDeclScopeArg));
  return cast<MDNode>(MV->getMetadata());
}

void setScopeList(MDNode *ScopeList) {
  setOperand(Intrinsic::NoAliasScopeDeclScopeArg,
             MetadataAsValue::get(getContext(), ScopeList));
}
1305};

1307// Defined in Statepoint.h -- NOT a subclass of IntrinsicInst
1308class GCStatepointInst;

1310/// Common base class for representing values projected from a statepoint.
1311/// Currently, the only projections available are gc.result and gc.relocate.
1312class GCProjectionInst : public IntrinsicInst {
1313public:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::experimental_gc_relocate ||
    I->getIntrinsicID() == Intrinsic::experimental_gc_result;
}

static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}

/// Return true if this relocate is tied to the invoke statepoint.
/// This includes relocates which are on the unwinding path.
bool isTiedToInvoke() const {
  const Value *Token = getArgOperand(0);

  return isa<LandingPadInst>(Token) || isa<InvokeInst>(Token);
}

/// The statepoint with which this gc.relocate is associated.
const GCStatepointInst *getStatepoint() const;
1333};

1335/// Represents calls to the gc.relocate intrinsic.
1336class GCRelocateInst : public GCProjectionInst {
1337public:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::experimental_gc_relocate;
}

static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}

/// The index into the associate statepoint's argument list
/// which contains the base pointer of the pointer whose
/// relocation this gc.relocate describes.
unsigned getBasePtrIndex() const {
  return cast<ConstantInt>(getArgOperand(1))->getZExtValue();
}

/// The index into the associate statepoint's argument list which
/// contains the pointer whose relocation this gc.relocate describes.
unsigned getDerivedPtrIndex() const {
  return cast<ConstantInt>(getArgOperand(2))->getZExtValue();
}

Value *getBasePtr() const;
Value *getDerivedPtr() const;
1361};

1363/// Represents calls to the gc.result intrinsic.
1364class GCResultInst : public GCProjectionInst {
1365public:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::experimental_gc_result;
}

static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
1373};


1376/// This represents the llvm.assume intrinsic.
1377class AssumeInst : public IntrinsicInst {
1378public:
static bool classof(const IntrinsicInst *I) {
  return I->getIntrinsicID() == Intrinsic::assume;
}
static bool classof(const Value *V) {
  return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
}
1385};

1387} // end namespace llvm

1389#endif // LLVM_IR_INTRINSICINST_H