/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp

Bug Summary

File:	llvm/lib/Transforms/Utils/CodeExtractor.cpp
Warning:	line 1761, column 11 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 -disable-llvm-verifier -discard-value-names -main-file-name CodeExtractor.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 -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-12/lib/clang/12.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/build-llvm/lib/Transforms/Utils -I /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils -I /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/build-llvm/include -I /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-12/lib/clang/12.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/build-llvm/lib/Transforms/Utils -fdebug-prefix-map=/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-09-28-092409-31635-1 -x c++ /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp

/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp

→

1//===- CodeExtractor.cpp - Pull code region into a new function -----------===//
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 implements the interface to tear out a code region, such as an
10// individual loop or a parallel section, into a new function, replacing it with
11// a call to the new function.
12//
13//===----------------------------------------------------------------------===//

15#include "llvm/Transforms/Utils/CodeExtractor.h"
16#include "llvm/ADT/ArrayRef.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/Optional.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SetVector.h"
21#include "llvm/ADT/SmallPtrSet.h"
22#include "llvm/ADT/SmallVector.h"
23#include "llvm/Analysis/AssumptionCache.h"
24#include "llvm/Analysis/BlockFrequencyInfo.h"
25#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
26#include "llvm/Analysis/BranchProbabilityInfo.h"
27#include "llvm/Analysis/LoopInfo.h"
28#include "llvm/IR/Argument.h"
29#include "llvm/IR/Attributes.h"
30#include "llvm/IR/BasicBlock.h"
31#include "llvm/IR/CFG.h"
32#include "llvm/IR/Constant.h"
33#include "llvm/IR/Constants.h"
34#include "llvm/IR/DIBuilder.h"
35#include "llvm/IR/DataLayout.h"
36#include "llvm/IR/DebugInfoMetadata.h"
37#include "llvm/IR/DerivedTypes.h"
38#include "llvm/IR/Dominators.h"
39#include "llvm/IR/Function.h"
40#include "llvm/IR/GlobalValue.h"
41#include "llvm/IR/InstIterator.h"
42#include "llvm/IR/InstrTypes.h"
43#include "llvm/IR/Instruction.h"
44#include "llvm/IR/Instructions.h"
45#include "llvm/IR/IntrinsicInst.h"
46#include "llvm/IR/Intrinsics.h"
47#include "llvm/IR/LLVMContext.h"
48#include "llvm/IR/MDBuilder.h"
49#include "llvm/IR/Module.h"
50#include "llvm/IR/PatternMatch.h"
51#include "llvm/IR/Type.h"
52#include "llvm/IR/User.h"
53#include "llvm/IR/Value.h"
54#include "llvm/IR/Verifier.h"
55#include "llvm/Pass.h"
56#include "llvm/Support/BlockFrequency.h"
57#include "llvm/Support/BranchProbability.h"
58#include "llvm/Support/Casting.h"
59#include "llvm/Support/CommandLine.h"
60#include "llvm/Support/Debug.h"
61#include "llvm/Support/ErrorHandling.h"
62#include "llvm/Support/raw_ostream.h"
63#include "llvm/Transforms/Utils/BasicBlockUtils.h"
64#include "llvm/Transforms/Utils/Local.h"
65#include <cassert>
66#include <cstdint>
67#include <iterator>
68#include <map>
69#include <set>
70#include <utility>
71#include <vector>

73using namespace llvm;
74using namespace llvm::PatternMatch;
75using ProfileCount = Function::ProfileCount;

77#define DEBUG_TYPE"code-extractor" "code-extractor"

79// Provide a command-line option to aggregate function arguments into a struct
80// for functions produced by the code extractor. This is useful when converting
81// extracted functions to pthread-based code, as only one argument (void*) can
82// be passed in to pthread_create().
83static cl::opt<bool>
84AggregateArgsOpt("aggregate-extracted-args", cl::Hidden,
               cl::desc("Aggregate arguments to code-extracted functions"));

87/// Test whether a block is valid for extraction.
88static bool isBlockValidForExtraction(const BasicBlock &BB,
                                    const SetVector<BasicBlock *> &Result,
                                    bool AllowVarArgs, bool AllowAlloca) {
// taking the address of a basic block moved to another function is illegal
if (BB.hasAddressTaken())
  return false;

// don't hoist code that uses another basicblock address, as it's likely to
// lead to unexpected behavior, like cross-function jumps
SmallPtrSet<User const *, 16> Visited;
SmallVector<User const *, 16> ToVisit;

for (Instruction const &Inst : BB)
  ToVisit.push_back(&Inst);

while (!ToVisit.empty()) {
  User const *Curr = ToVisit.pop_back_val();
  if (!Visited.insert(Curr).second)
    continue;
  if (isa<BlockAddress const>(Curr))
    return false; // even a reference to self is likely to be not compatible

  if (isa<Instruction>(Curr) && cast<Instruction>(Curr)->getParent() != &BB)
    continue;

  for (auto const &U : Curr->operands()) {
    if (auto *UU = dyn_cast<User>(U))
      ToVisit.push_back(UU);
  }
}

// If explicitly requested, allow vastart and alloca. For invoke instructions
// verify that extraction is valid.
for (BasicBlock::const_iterator I = BB.begin(), E = BB.end(); I != E; ++I) {
  if (isa<AllocaInst>(I)) {
     if (!AllowAlloca)
       return false;
     continue;
  }

  if (const auto *II = dyn_cast<InvokeInst>(I)) {
    // Unwind destination (either a landingpad, catchswitch, or cleanuppad)
    // must be a part of the subgraph which is being extracted.
    if (auto *UBB = II->getUnwindDest())
      if (!Result.count(UBB))
        return false;
    continue;
  }

  // All catch handlers of a catchswitch instruction as well as the unwind
  // destination must be in the subgraph.
  if (const auto *CSI = dyn_cast<CatchSwitchInst>(I)) {
    if (auto *UBB = CSI->getUnwindDest())
      if (!Result.count(UBB))
        return false;
    for (auto *HBB : CSI->handlers())
      if (!Result.count(const_cast<BasicBlock*>(HBB)))
        return false;
    continue;
  }

  // Make sure that entire catch handler is within subgraph. It is sufficient
  // to check that catch return's block is in the list.
  if (const auto *CPI = dyn_cast<CatchPadInst>(I)) {
    for (const auto *U : CPI->users())
      if (const auto *CRI = dyn_cast<CatchReturnInst>(U))
        if (!Result.count(const_cast<BasicBlock*>(CRI->getParent())))
          return false;
    continue;
  }

  // And do similar checks for cleanup handler - the entire handler must be
  // in subgraph which is going to be extracted. For cleanup return should
  // additionally check that the unwind destination is also in the subgraph.
  if (const auto *CPI = dyn_cast<CleanupPadInst>(I)) {
    for (const auto *U : CPI->users())
      if (const auto *CRI = dyn_cast<CleanupReturnInst>(U))
        if (!Result.count(const_cast<BasicBlock*>(CRI->getParent())))
          return false;
    continue;
  }
  if (const auto *CRI = dyn_cast<CleanupReturnInst>(I)) {
    if (auto *UBB = CRI->getUnwindDest())
      if (!Result.count(UBB))
        return false;
    continue;
  }

  if (const CallInst *CI = dyn_cast<CallInst>(I)) {
    if (const Function *F = CI->getCalledFunction()) {
      auto IID = F->getIntrinsicID();
      if (IID == Intrinsic::vastart) {
        if (AllowVarArgs)
          continue;
        else
          return false;
      }

      // Currently, we miscompile outlined copies of eh_typid_for. There are
      // proposals for fixing this in llvm.org/PR39545.
      if (IID == Intrinsic::eh_typeid_for)
        return false;
    }
  }
}

return true;
195}

197/// Build a set of blocks to extract if the input blocks are viable.
198static SetVector<BasicBlock *>
199buildExtractionBlockSet(ArrayRef<BasicBlock *> BBs, DominatorTree *DT,
                      bool AllowVarArgs, bool AllowAlloca) {
assert(!BBs.empty() && "The set of blocks to extract must be non-empty")((!BBs.empty() && "The set of blocks to extract must be non-empty"
) ? static_cast<void> (0) : __assert_fail ("!BBs.empty() && \"The set of blocks to extract must be non-empty\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 201, __PRETTY_FUNCTION__));
SetVector<BasicBlock *> Result;

// Loop over the blocks, adding them to our set-vector, and aborting with an
// empty set if we encounter invalid blocks.
for (BasicBlock *BB : BBs) {
  // If this block is dead, don't process it.
  if (DT && !DT->isReachableFromEntry(BB))
    continue;

  if (!Result.insert(BB))
    llvm_unreachable("Repeated basic blocks in extraction input")::llvm::llvm_unreachable_internal("Repeated basic blocks in extraction input"
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 212);
}

LLVM_DEBUG(dbgs() << "Region front block: " << Result.front()->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "Region front block: " <<
 Result.front()->getName() << '\n'; } } while (false
)
                  << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "Region front block: " <<
 Result.front()->getName() << '\n'; } } while (false
);

for (auto *BB : Result) {
  if (!isBlockValidForExtraction(*BB, Result, AllowVarArgs, AllowAlloca))
    return {};

  // Make sure that the first block is not a landing pad.
  if (BB == Result.front()) {
    if (BB->isEHPad()) {
      LLVM_DEBUG(dbgs() << "The first block cannot be an unwind block\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "The first block cannot be an unwind block\n"
; } } while (false);
      return {};
    }
    continue;
  }

  // All blocks other than the first must not have predecessors outside of
  // the subgraph which is being extracted.
  for (auto *PBB : predecessors(BB))
    if (!Result.count(PBB)) {
      LLVM_DEBUG(dbgs() << "No blocks in this region may have entries from "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "No blocks in this region may have entries from "
 "outside the region except for the first block!\n" << "Problematic source BB: "
 << BB->getName() << "\n" << "Problematic destination BB: "
 << PBB->getName() << "\n"; } } while (false)
                           "outside the region except for the first block!\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "No blocks in this region may have entries from "
 "outside the region except for the first block!\n" << "Problematic source BB: "
 << BB->getName() << "\n" << "Problematic destination BB: "
 << PBB->getName() << "\n"; } } while (false)
                        << "Problematic source BB: " << BB->getName() << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "No blocks in this region may have entries from "
 "outside the region except for the first block!\n" << "Problematic source BB: "
 << BB->getName() << "\n" << "Problematic destination BB: "
 << PBB->getName() << "\n"; } } while (false)
                        << "Problematic destination BB: " << PBB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "No blocks in this region may have entries from "
 "outside the region except for the first block!\n" << "Problematic source BB: "
 << BB->getName() << "\n" << "Problematic destination BB: "
 << PBB->getName() << "\n"; } } while (false)
                        << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "No blocks in this region may have entries from "
 "outside the region except for the first block!\n" << "Problematic source BB: "
 << BB->getName() << "\n" << "Problematic destination BB: "
 << PBB->getName() << "\n"; } } while (false);
      return {};
    }
}

return Result;
245}

247CodeExtractor::CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT,
                           bool AggregateArgs, BlockFrequencyInfo *BFI,
                           BranchProbabilityInfo *BPI, AssumptionCache *AC,
                           bool AllowVarArgs, bool AllowAlloca,
                           std::string Suffix)
  : DT(DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI),
    BPI(BPI), AC(AC), AllowVarArgs(AllowVarArgs),
    Blocks(buildExtractionBlockSet(BBs, DT, AllowVarArgs, AllowAlloca)),
    Suffix(Suffix) {}

257CodeExtractor::CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs,
                           BlockFrequencyInfo *BFI,
                           BranchProbabilityInfo *BPI, AssumptionCache *AC,
                           std::string Suffix)
  : DT(&DT), AggregateArgs(AggregateArgs || AggregateArgsOpt), BFI(BFI),
    BPI(BPI), AC(AC), AllowVarArgs(false),
    Blocks(buildExtractionBlockSet(L.getBlocks(), &DT,
                                   /* AllowVarArgs */ false,
                                   /* AllowAlloca */ false)),
    Suffix(Suffix) {}

268/// definedInRegion - Return true if the specified value is defined in the
269/// extracted region.
270static bool definedInRegion(const SetVector<BasicBlock *> &Blocks, Value *V) {
if (Instruction *I = dyn_cast<Instruction>(V))
  if (Blocks.count(I->getParent()))
    return true;
return false;
275}

277/// definedInCaller - Return true if the specified value is defined in the
278/// function being code extracted, but not in the region being extracted.
279/// These values must be passed in as live-ins to the function.
280static bool definedInCaller(const SetVector<BasicBlock *> &Blocks, Value *V) {
if (isa<Argument>(V)) return true;
if (Instruction *I = dyn_cast<Instruction>(V))
  if (!Blocks.count(I->getParent()))
    return true;
return false;
286}

288static BasicBlock *getCommonExitBlock(const SetVector<BasicBlock *> &Blocks) {
BasicBlock *CommonExitBlock = nullptr;
auto hasNonCommonExitSucc = [&](BasicBlock *Block) {
  for (auto *Succ : successors(Block)) {
    // Internal edges, ok.
    if (Blocks.count(Succ))
      continue;
    if (!CommonExitBlock) {
      CommonExitBlock = Succ;
      continue;
    }
    if (CommonExitBlock != Succ)
      return true;
  }
  return false;
};

if (any_of(Blocks, hasNonCommonExitSucc))
  return nullptr;

return CommonExitBlock;
309}

311CodeExtractorAnalysisCache::CodeExtractorAnalysisCache(Function &F) {
for (BasicBlock &BB : F) {
  for (Instruction &II : BB.instructionsWithoutDebug())
    if (auto *AI = dyn_cast<AllocaInst>(&II))
      Allocas.push_back(AI);

  findSideEffectInfoForBlock(BB);
}
319}

321void CodeExtractorAnalysisCache::findSideEffectInfoForBlock(BasicBlock &BB) {
for (Instruction &II : BB.instructionsWithoutDebug()) {
  unsigned Opcode = II.getOpcode();
  Value *MemAddr = nullptr;
  switch (Opcode) {
  case Instruction::Store:
  case Instruction::Load: {
    if (Opcode == Instruction::Store) {
      StoreInst *SI = cast<StoreInst>(&II);
      MemAddr = SI->getPointerOperand();
    } else {
      LoadInst *LI = cast<LoadInst>(&II);
      MemAddr = LI->getPointerOperand();
    }
    // Global variable can not be aliased with locals.
    if (dyn_cast<Constant>(MemAddr))
      break;
    Value *Base = MemAddr->stripInBoundsConstantOffsets();
    if (!isa<AllocaInst>(Base)) {
      SideEffectingBlocks.insert(&BB);
      return;
    }
    BaseMemAddrs[&BB].insert(Base);
    break;
  }
  default: {
    IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&II);
    if (IntrInst) {
      if (IntrInst->isLifetimeStartOrEnd())
        break;
      SideEffectingBlocks.insert(&BB);
      return;
    }
    // Treat all the other cases conservatively if it has side effects.
    if (II.mayHaveSideEffects()) {
      SideEffectingBlocks.insert(&BB);
      return;
    }
  }
  }
}
362}

364bool CodeExtractorAnalysisCache::doesBlockContainClobberOfAddr(
  BasicBlock &BB, AllocaInst *Addr) const {
if (SideEffectingBlocks.count(&BB))
  return true;
auto It = BaseMemAddrs.find(&BB);
if (It != BaseMemAddrs.end())
  return It->second.count(Addr);
return false;
372}

374bool CodeExtractor::isLegalToShrinkwrapLifetimeMarkers(
  const CodeExtractorAnalysisCache &CEAC, Instruction *Addr) const {
AllocaInst *AI = cast<AllocaInst>(Addr->stripInBoundsConstantOffsets());
Function *Func = (*Blocks.begin())->getParent();
for (BasicBlock &BB : *Func) {
  if (Blocks.count(&BB))
    continue;
  if (CEAC.doesBlockContainClobberOfAddr(BB, AI))
    return false;
}
return true;
385}

387BasicBlock *
388CodeExtractor::findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock) {
BasicBlock *SinglePredFromOutlineRegion = nullptr;
assert(!Blocks.count(CommonExitBlock) &&((!Blocks.count(CommonExitBlock) && "Expect a block outside the region!"
) ? static_cast<void> (0) : __assert_fail ("!Blocks.count(CommonExitBlock) && \"Expect a block outside the region!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 391, __PRETTY_FUNCTION__))
       "Expect a block outside the region!")((!Blocks.count(CommonExitBlock) && "Expect a block outside the region!"
) ? static_cast<void> (0) : __assert_fail ("!Blocks.count(CommonExitBlock) && \"Expect a block outside the region!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 391, __PRETTY_FUNCTION__));
for (auto *Pred : predecessors(CommonExitBlock)) {
  if (!Blocks.count(Pred))
    continue;
  if (!SinglePredFromOutlineRegion) {
    SinglePredFromOutlineRegion = Pred;
  } else if (SinglePredFromOutlineRegion != Pred) {
    SinglePredFromOutlineRegion = nullptr;
    break;
  }
}

if (SinglePredFromOutlineRegion)
  return SinglePredFromOutlineRegion;

406#ifndef NDEBUG
auto getFirstPHI = [](BasicBlock *BB) {
  BasicBlock::iterator I = BB->begin();
  PHINode *FirstPhi = nullptr;
  while (I != BB->end()) {
    PHINode *Phi = dyn_cast<PHINode>(I);
    if (!Phi)
      break;
    if (!FirstPhi) {
      FirstPhi = Phi;
      break;
    }
  }
  return FirstPhi;
};
// If there are any phi nodes, the single pred either exists or has already
// be created before code extraction.
assert(!getFirstPHI(CommonExitBlock) && "Phi not expected")((!getFirstPHI(CommonExitBlock) && "Phi not expected"
) ? static_cast<void> (0) : __assert_fail ("!getFirstPHI(CommonExitBlock) && \"Phi not expected\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 423, __PRETTY_FUNCTION__));
424#endif

BasicBlock *NewExitBlock = CommonExitBlock->splitBasicBlock(
    CommonExitBlock->getFirstNonPHI()->getIterator());

for (auto PI = pred_begin(CommonExitBlock), PE = pred_end(CommonExitBlock);
     PI != PE;) {
  BasicBlock *Pred = *PI++;
  if (Blocks.count(Pred))
    continue;
  Pred->getTerminator()->replaceUsesOfWith(CommonExitBlock, NewExitBlock);
}
// Now add the old exit block to the outline region.
Blocks.insert(CommonExitBlock);
return CommonExitBlock;
439}

441// Find the pair of life time markers for address 'Addr' that are either
442// defined inside the outline region or can legally be shrinkwrapped into the
443// outline region. If there are not other untracked uses of the address, return
444// the pair of markers if found; otherwise return a pair of nullptr.
445CodeExtractor::LifetimeMarkerInfo
446CodeExtractor::getLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC,
                                Instruction *Addr,
                                BasicBlock *ExitBlock) const {
LifetimeMarkerInfo Info;

for (User *U : Addr->users()) {
  IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(U);
  if (IntrInst) {
    // We don't model addresses with multiple start/end markers, but the
    // markers do not need to be in the region.
    if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start) {
      if (Info.LifeStart)
        return {};
      Info.LifeStart = IntrInst;
      continue;
    }
    if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end) {
      if (Info.LifeEnd)
        return {};
      Info.LifeEnd = IntrInst;
      continue;
    }
    // At this point, permit debug uses outside of the region.
    // This is fixed in a later call to fixupDebugInfoPostExtraction().
    if (isa<DbgInfoIntrinsic>(IntrInst))
      continue;
  }
  // Find untracked uses of the address, bail.
  if (!definedInRegion(Blocks, U))
    return {};
}

if (!Info.LifeStart || !Info.LifeEnd)
  return {};

Info.SinkLifeStart = !definedInRegion(Blocks, Info.LifeStart);
Info.HoistLifeEnd = !definedInRegion(Blocks, Info.LifeEnd);
// Do legality check.
if ((Info.SinkLifeStart || Info.HoistLifeEnd) &&
    !isLegalToShrinkwrapLifetimeMarkers(CEAC, Addr))
  return {};

// Check to see if we have a place to do hoisting, if not, bail.
if (Info.HoistLifeEnd && !ExitBlock)
  return {};

return Info;
493}

495void CodeExtractor::findAllocas(const CodeExtractorAnalysisCache &CEAC,
                              ValueSet &SinkCands, ValueSet &HoistCands,
                              BasicBlock *&ExitBlock) const {
Function *Func = (*Blocks.begin())->getParent();
ExitBlock = getCommonExitBlock(Blocks);

auto moveOrIgnoreLifetimeMarkers =
    [&](const LifetimeMarkerInfo &LMI) -> bool {
  if (!LMI.LifeStart)
    return false;
  if (LMI.SinkLifeStart) {
    LLVM_DEBUG(dbgs() << "Sinking lifetime.start: " << *LMI.LifeStartdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "Sinking lifetime.start: "
 << *LMI.LifeStart << "\n"; } } while (false)
                      << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "Sinking lifetime.start: "
 << *LMI.LifeStart << "\n"; } } while (false);
    SinkCands.insert(LMI.LifeStart);
  }
  if (LMI.HoistLifeEnd) {
    LLVM_DEBUG(dbgs() << "Hoisting lifetime.end: " << *LMI.LifeEnd << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "Hoisting lifetime.end: "
 << *LMI.LifeEnd << "\n"; } } while (false);
    HoistCands.insert(LMI.LifeEnd);
  }
  return true;
};

// Look up allocas in the original function in CodeExtractorAnalysisCache, as
// this is much faster than walking all the instructions.
for (AllocaInst *AI : CEAC.getAllocas()) {
  BasicBlock *BB = AI->getParent();
  if (Blocks.count(BB))
    continue;

  // As a prior call to extractCodeRegion() may have shrinkwrapped the alloca,
  // check whether it is actually still in the original function.
  Function *AIFunc = BB->getParent();
  if (AIFunc != Func)
    continue;

  LifetimeMarkerInfo MarkerInfo = getLifetimeMarkers(CEAC, AI, ExitBlock);
  bool Moved = moveOrIgnoreLifetimeMarkers(MarkerInfo);
  if (Moved) {
    LLVM_DEBUG(dbgs() << "Sinking alloca: " << *AI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "Sinking alloca: " <<
 *AI << "\n"; } } while (false);
    SinkCands.insert(AI);
    continue;
  }

  // Follow any bitcasts.
  SmallVector<Instruction *, 2> Bitcasts;
  SmallVector<LifetimeMarkerInfo, 2> BitcastLifetimeInfo;
  for (User *U : AI->users()) {
    if (U->stripInBoundsConstantOffsets() == AI) {
      Instruction *Bitcast = cast<Instruction>(U);
      LifetimeMarkerInfo LMI = getLifetimeMarkers(CEAC, Bitcast, ExitBlock);
      if (LMI.LifeStart) {
        Bitcasts.push_back(Bitcast);
        BitcastLifetimeInfo.push_back(LMI);
        continue;
      }
    }

    // Found unknown use of AI.
    if (!definedInRegion(Blocks, U)) {
      Bitcasts.clear();
      break;
    }
  }

  // Either no bitcasts reference the alloca or there are unknown uses.
  if (Bitcasts.empty())
    continue;

  LLVM_DEBUG(dbgs() << "Sinking alloca (via bitcast): " << *AI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "Sinking alloca (via bitcast): "
 << *AI << "\n"; } } while (false);
  SinkCands.insert(AI);
  for (unsigned I = 0, E = Bitcasts.size(); I != E; ++I) {
    Instruction *BitcastAddr = Bitcasts[I];
    const LifetimeMarkerInfo &LMI = BitcastLifetimeInfo[I];
    assert(LMI.LifeStart &&((LMI.LifeStart && "Unsafe to sink bitcast without lifetime markers"
) ? static_cast<void> (0) : __assert_fail ("LMI.LifeStart && \"Unsafe to sink bitcast without lifetime markers\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 569, __PRETTY_FUNCTION__))
           "Unsafe to sink bitcast without lifetime markers")((LMI.LifeStart && "Unsafe to sink bitcast without lifetime markers"
) ? static_cast<void> (0) : __assert_fail ("LMI.LifeStart && \"Unsafe to sink bitcast without lifetime markers\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 569, __PRETTY_FUNCTION__));
    moveOrIgnoreLifetimeMarkers(LMI);
    if (!definedInRegion(Blocks, BitcastAddr)) {
      LLVM_DEBUG(dbgs() << "Sinking bitcast-of-alloca: " << *BitcastAddrdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "Sinking bitcast-of-alloca: "
 << *BitcastAddr << "\n"; } } while (false)
                        << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "Sinking bitcast-of-alloca: "
 << *BitcastAddr << "\n"; } } while (false);
      SinkCands.insert(BitcastAddr);
    }
  }
}
578}

580bool CodeExtractor::isEligible() const {
if (Blocks.empty())
  return false;
BasicBlock *Header = *Blocks.begin();
Function *F = Header->getParent();

// For functions with varargs, check that varargs handling is only done in the
// outlined function, i.e vastart and vaend are only used in outlined blocks.
if (AllowVarArgs && F->getFunctionType()->isVarArg()) {
  auto containsVarArgIntrinsic = [](const Instruction &I) {
    if (const CallInst *CI = dyn_cast<CallInst>(&I))
      if (const Function *Callee = CI->getCalledFunction())
        return Callee->getIntrinsicID() == Intrinsic::vastart ||
               Callee->getIntrinsicID() == Intrinsic::vaend;
    return false;
  };

  for (auto &BB : *F) {
    if (Blocks.count(&BB))
      continue;
    if (llvm::any_of(BB, containsVarArgIntrinsic))
      return false;
  }
}
return true;
605}

607void CodeExtractor::findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
                                    const ValueSet &SinkCands) const {
for (BasicBlock *BB : Blocks) {
  // If a used value is defined outside the region, it's an input.  If an
  // instruction is used outside the region, it's an output.
  for (Instruction &II : *BB) {
    for (auto &OI : II.operands()) {
      Value *V = OI;
      if (!SinkCands.count(V) && definedInCaller(Blocks, V))
        Inputs.insert(V);
    }

    for (User *U : II.users())
      if (!definedInRegion(Blocks, U)) {
        Outputs.insert(&II);
        break;
      }
  }
}
626}

628/// severSplitPHINodesOfEntry - If a PHI node has multiple inputs from outside
629/// of the region, we need to split the entry block of the region so that the
630/// PHI node is easier to deal with.
631void CodeExtractor::severSplitPHINodesOfEntry(BasicBlock *&Header) {
unsigned NumPredsFromRegion = 0;
unsigned NumPredsOutsideRegion = 0;

if (Header != &Header->getParent()->getEntryBlock()) {
  PHINode *PN = dyn_cast<PHINode>(Header->begin());
  if (!PN) return;  // No PHI nodes.

  // If the header node contains any PHI nodes, check to see if there is more
  // than one entry from outside the region.  If so, we need to sever the
  // header block into two.
  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
    if (Blocks.count(PN->getIncomingBlock(i)))
      ++NumPredsFromRegion;
    else
      ++NumPredsOutsideRegion;

  // If there is one (or fewer) predecessor from outside the region, we don't
  // need to do anything special.
  if (NumPredsOutsideRegion <= 1) return;
}

// Otherwise, we need to split the header block into two pieces: one
// containing PHI nodes merging values from outside of the region, and a
// second that contains all of the code for the block and merges back any
// incoming values from inside of the region.
BasicBlock *NewBB = SplitBlock(Header, Header->getFirstNonPHI(), DT);

// We only want to code extract the second block now, and it becomes the new
// header of the region.
BasicBlock *OldPred = Header;
Blocks.remove(OldPred);
Blocks.insert(NewBB);
Header = NewBB;

// Okay, now we need to adjust the PHI nodes and any branches from within the
// region to go to the new header block instead of the old header block.
if (NumPredsFromRegion) {
  PHINode *PN = cast<PHINode>(OldPred->begin());
  // Loop over all of the predecessors of OldPred that are in the region,
  // changing them to branch to NewBB instead.
  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
    if (Blocks.count(PN->getIncomingBlock(i))) {
      Instruction *TI = PN->getIncomingBlock(i)->getTerminator();
      TI->replaceUsesOfWith(OldPred, NewBB);
    }

  // Okay, everything within the region is now branching to the right block, we
  // just have to update the PHI nodes now, inserting PHI nodes into NewBB.
  BasicBlock::iterator AfterPHIs;
  for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) {
    PHINode *PN = cast<PHINode>(AfterPHIs);
    // Create a new PHI node in the new region, which has an incoming value
    // from OldPred of PN.
    PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion,
                                     PN->getName() + ".ce", &NewBB->front());
    PN->replaceAllUsesWith(NewPN);
    NewPN->addIncoming(PN, OldPred);

    // Loop over all of the incoming value in PN, moving them to NewPN if they
    // are from the extracted region.
    for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
      if (Blocks.count(PN->getIncomingBlock(i))) {
        NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i));
        PN->removeIncomingValue(i);
        --i;
      }
    }
  }
}
701}

703/// severSplitPHINodesOfExits - if PHI nodes in exit blocks have inputs from
704/// outlined region, we split these PHIs on two: one with inputs from region
705/// and other with remaining incoming blocks; then first PHIs are placed in
706/// outlined region.
707void CodeExtractor::severSplitPHINodesOfExits(
  const SmallPtrSetImpl<BasicBlock *> &Exits) {
for (BasicBlock *ExitBB : Exits) {
  BasicBlock *NewBB = nullptr;

  for (PHINode &PN : ExitBB->phis()) {
    // Find all incoming values from the outlining region.
    SmallVector<unsigned, 2> IncomingVals;
    for (unsigned i = 0; i < PN.getNumIncomingValues(); ++i)
      if (Blocks.count(PN.getIncomingBlock(i)))
        IncomingVals.push_back(i);

    // Do not process PHI if there is one (or fewer) predecessor from region.
    // If PHI has exactly one predecessor from region, only this one incoming
    // will be replaced on codeRepl block, so it should be safe to skip PHI.
    if (IncomingVals.size() <= 1)
      continue;

    // Create block for new PHIs and add it to the list of outlined if it
    // wasn't done before.
    if (!NewBB) {
      NewBB = BasicBlock::Create(ExitBB->getContext(),
                                 ExitBB->getName() + ".split",
                                 ExitBB->getParent(), ExitBB);
      SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBB),
                                         pred_end(ExitBB));
      for (BasicBlock *PredBB : Preds)
        if (Blocks.count(PredBB))
          PredBB->getTerminator()->replaceUsesOfWith(ExitBB, NewBB);
      BranchInst::Create(ExitBB, NewBB);
      Blocks.insert(NewBB);
    }

    // Split this PHI.
    PHINode *NewPN =
        PHINode::Create(PN.getType(), IncomingVals.size(),
                        PN.getName() + ".ce", NewBB->getFirstNonPHI());
    for (unsigned i : IncomingVals)
      NewPN->addIncoming(PN.getIncomingValue(i), PN.getIncomingBlock(i));
    for (unsigned i : reverse(IncomingVals))
      PN.removeIncomingValue(i, false);
    PN.addIncoming(NewPN, NewBB);
  }
}
751}

753void CodeExtractor::splitReturnBlocks() {
for (BasicBlock *Block : Blocks)
  if (ReturnInst *RI = dyn_cast<ReturnInst>(Block->getTerminator())) {
    BasicBlock *New =
        Block->splitBasicBlock(RI->getIterator(), Block->getName() + ".ret");
    if (DT) {
      // Old dominates New. New node dominates all other nodes dominated
      // by Old.
      DomTreeNode *OldNode = DT->getNode(Block);
      SmallVector<DomTreeNode *, 8> Children(OldNode->begin(),
                                             OldNode->end());

      DomTreeNode *NewNode = DT->addNewBlock(New, Block);

      for (DomTreeNode *I : Children)
        DT->changeImmediateDominator(I, NewNode);
    }
  }
771}

773/// constructFunction - make a function based on inputs and outputs, as follows:
774/// f(in0, ..., inN, out0, ..., outN)
775Function *CodeExtractor::constructFunction(const ValueSet &inputs,
                                         const ValueSet &outputs,
                                         BasicBlock *header,
                                         BasicBlock *newRootNode,
                                         BasicBlock *newHeader,
                                         Function *oldFunction,
                                         Module *M) {
LLVM_DEBUG(dbgs() << "inputs: " << inputs.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "inputs: " << inputs
.size() << "\n"; } } while (false);
LLVM_DEBUG(dbgs() << "outputs: " << outputs.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "outputs: " << outputs
.size() << "\n"; } } while (false);

// This function returns unsigned, outputs will go back by reference.
switch (NumExitBlocks) {
case 0:
case 1: RetTy = Type::getVoidTy(header->getContext()); break;
case 2: RetTy = Type::getInt1Ty(header->getContext()); break;
default: RetTy = Type::getInt16Ty(header->getContext()); break;
}

std::vector<Type *> paramTy;

// Add the types of the input values to the function's argument list
for (Value *value : inputs) {
  LLVM_DEBUG(dbgs() << "value used in func: " << *value << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "value used in func: " <<
 *value << "\n"; } } while (false);
  paramTy.push_back(value->getType());
}

// Add the types of the output values to the function's argument list.
for (Value *output : outputs) {
  LLVM_DEBUG(dbgs() << "instr used in func: " << *output << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { dbgs() << "instr used in func: " <<
 *output << "\n"; } } while (false);
  if (AggregateArgs)
    paramTy.push_back(output->getType());
  else
    paramTy.push_back(PointerType::getUnqual(output->getType()));
}

LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { { dbgs() << "Function type: " <<
 *RetTy << " f("; for (Type *i : paramTy) dbgs() <<
 *i << ", "; dbgs() << ")\n"; }; } } while (false
)
  dbgs() << "Function type: " << *RetTy << " f(";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { { dbgs() << "Function type: " <<
 *RetTy << " f("; for (Type *i : paramTy) dbgs() <<
 *i << ", "; dbgs() << ")\n"; }; } } while (false
)
  for (Type *i : paramTy)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { { dbgs() << "Function type: " <<
 *RetTy << " f("; for (Type *i : paramTy) dbgs() <<
 *i << ", "; dbgs() << ")\n"; }; } } while (false
)
    dbgs() << *i << ", ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { { dbgs() << "Function type: " <<
 *RetTy << " f("; for (Type *i : paramTy) dbgs() <<
 *i << ", "; dbgs() << ")\n"; }; } } while (false
)
  dbgs() << ")\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { { dbgs() << "Function type: " <<
 *RetTy << " f("; for (Type *i : paramTy) dbgs() <<
 *i << ", "; dbgs() << ")\n"; }; } } while (false
)
})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { { dbgs() << "Function type: " <<
 *RetTy << " f("; for (Type *i : paramTy) dbgs() <<
 *i << ", "; dbgs() << ")\n"; }; } } while (false
);

StructType *StructTy = nullptr;
if (AggregateArgs && (inputs.size() + outputs.size() > 0)) {
  StructTy = StructType::get(M->getContext(), paramTy);
  paramTy.clear();
  paramTy.push_back(PointerType::getUnqual(StructTy));
}
FunctionType *funcType =
                FunctionType::get(RetTy, paramTy,
                                  AllowVarArgs && oldFunction->isVarArg());

std::string SuffixToUse =
    Suffix.empty()
        ? (header->getName().empty() ? "extracted" : header->getName().str())
        : Suffix;
// Create the new function
Function *newFunction = Function::Create(
    funcType, GlobalValue::InternalLinkage, oldFunction->getAddressSpace(),
    oldFunction->getName() + "." + SuffixToUse, M);
// If the old function is no-throw, so is the new one.
if (oldFunction->doesNotThrow())
  newFunction->setDoesNotThrow();

// Inherit the uwtable attribute if we need to.
if (oldFunction->hasUWTable())
  newFunction->setHasUWTable();

// Inherit all of the target dependent attributes and white-listed
// target independent attributes.
//  (e.g. If the extracted region contains a call to an x86.sse
//  instruction we need to make sure that the extracted region has the
//  "target-features" attribute allowing it to be lowered.
// FIXME: This should be changed to check to see if a specific
//           attribute can not be inherited.
for (const auto &Attr : oldFunction->getAttributes().getFnAttributes()) {
  if (Attr.isStringAttribute()) {
    if (Attr.getKindAsString() == "thunk")
      continue;
  } else
    switch (Attr.getKindAsEnum()) {
    // Those attributes cannot be propagated safely. Explicitly list them
    // here so we get a warning if new attributes are added. This list also
    // includes non-function attributes.
    case Attribute::Alignment:
    case Attribute::AllocSize:
    case Attribute::ArgMemOnly:
    case Attribute::Builtin:
    case Attribute::ByVal:
    case Attribute::Convergent:
    case Attribute::Dereferenceable:
    case Attribute::DereferenceableOrNull:
    case Attribute::InAlloca:
    case Attribute::InReg:
    case Attribute::InaccessibleMemOnly:
    case Attribute::InaccessibleMemOrArgMemOnly:
    case Attribute::JumpTable:
    case Attribute::Naked:
    case Attribute::Nest:
    case Attribute::NoAlias:
    case Attribute::NoBuiltin:
    case Attribute::NoCapture:
    case Attribute::NoMerge:
    case Attribute::NoReturn:
    case Attribute::NoSync:
    case Attribute::NoUndef:
    case Attribute::None:
    case Attribute::NonNull:
    case Attribute::Preallocated:
    case Attribute::ReadNone:
    case Attribute::ReadOnly:
    case Attribute::Returned:
    case Attribute::ReturnsTwice:
    case Attribute::SExt:
    case Attribute::Speculatable:
    case Attribute::StackAlignment:
    case Attribute::StructRet:
    case Attribute::SwiftError:
    case Attribute::SwiftSelf:
    case Attribute::WillReturn:
    case Attribute::WriteOnly:
    case Attribute::ZExt:
    case Attribute::ImmArg:
    case Attribute::ByRef:
    case Attribute::EndAttrKinds:
    case Attribute::EmptyKey:
    case Attribute::TombstoneKey:
      continue;
    // Those attributes should be safe to propagate to the extracted function.
    case Attribute::AlwaysInline:
    case Attribute::Cold:
    case Attribute::NoRecurse:
    case Attribute::InlineHint:
    case Attribute::MinSize:
    case Attribute::NoDuplicate:
    case Attribute::NoFree:
    case Attribute::NoImplicitFloat:
    case Attribute::NoInline:
    case Attribute::NonLazyBind:
    case Attribute::NoRedZone:
    case Attribute::NoUnwind:
    case Attribute::NullPointerIsValid:
    case Attribute::OptForFuzzing:
    case Attribute::OptimizeNone:
    case Attribute::OptimizeForSize:
    case Attribute::SafeStack:
    case Attribute::ShadowCallStack:
    case Attribute::SanitizeAddress:
    case Attribute::SanitizeMemory:
    case Attribute::SanitizeThread:
    case Attribute::SanitizeHWAddress:
    case Attribute::SanitizeMemTag:
    case Attribute::SpeculativeLoadHardening:
    case Attribute::StackProtect:
    case Attribute::StackProtectReq:
    case Attribute::StackProtectStrong:
    case Attribute::StrictFP:
    case Attribute::UWTable:
    case Attribute::NoCfCheck:
      break;
    }

  newFunction->addFnAttr(Attr);
}
newFunction->getBasicBlockList().push_back(newRootNode);

// Create an iterator to name all of the arguments we inserted.
Function::arg_iterator AI = newFunction->arg_begin();

// Rewrite all users of the inputs in the extracted region to use the
// arguments (or appropriate addressing into struct) instead.
for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
  Value *RewriteVal;
  if (AggregateArgs) {
    Value *Idx[2];
    Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext()));
    Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i);
    Instruction *TI = newFunction->begin()->getTerminator();
    GetElementPtrInst *GEP = GetElementPtrInst::Create(
        StructTy, &*AI, Idx, "gep_" + inputs[i]->getName(), TI);
    RewriteVal = new LoadInst(StructTy->getElementType(i), GEP,
                              "loadgep_" + inputs[i]->getName(), TI);
  } else
    RewriteVal = &*AI++;

  std::vector<User *> Users(inputs[i]->user_begin(), inputs[i]->user_end());
  for (User *use : Users)
    if (Instruction *inst = dyn_cast<Instruction>(use))
      if (Blocks.count(inst->getParent()))
        inst->replaceUsesOfWith(inputs[i], RewriteVal);
}

// Set names for input and output arguments.
if (!AggregateArgs) {
  AI = newFunction->arg_begin();
  for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI)
    AI->setName(inputs[i]->getName());
  for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI)
    AI->setName(outputs[i]->getName()+".out");
}

// Rewrite branches to basic blocks outside of the loop to new dummy blocks
// within the new function. This must be done before we lose track of which
// blocks were originally in the code region.
std::vector<User *> Users(header->user_begin(), header->user_end());
for (auto &U : Users)
  // The BasicBlock which contains the branch is not in the region
  // modify the branch target to a new block
  if (Instruction *I = dyn_cast<Instruction>(U))
    if (I->isTerminator() && I->getFunction() == oldFunction &&
        !Blocks.count(I->getParent()))
      I->replaceUsesOfWith(header, newHeader);

return newFunction;
989}

991/// Erase lifetime.start markers which reference inputs to the extraction
992/// region, and insert the referenced memory into \p LifetimesStart.
993///
994/// The extraction region is defined by a set of blocks (\p Blocks), and a set
995/// of allocas which will be moved from the caller function into the extracted
996/// function (\p SunkAllocas).
997static void eraseLifetimeMarkersOnInputs(const SetVector<BasicBlock *> &Blocks,
                                       const SetVector<Value *> &SunkAllocas,
                                       SetVector<Value *> &LifetimesStart) {
for (BasicBlock *BB : Blocks) {
  for (auto It = BB->begin(), End = BB->end(); It != End;) {
    auto *II = dyn_cast<IntrinsicInst>(&*It);
    ++It;
    if (!II || !II->isLifetimeStartOrEnd())
      continue;

    // Get the memory operand of the lifetime marker. If the underlying
    // object is a sunk alloca, or is otherwise defined in the extraction
    // region, the lifetime marker must not be erased.
    Value *Mem = II->getOperand(1)->stripInBoundsOffsets();
    if (SunkAllocas.count(Mem) || definedInRegion(Blocks, Mem))
      continue;

    if (II->getIntrinsicID() == Intrinsic::lifetime_start)
      LifetimesStart.insert(Mem);
    II->eraseFromParent();
  }
}
1019}

1021/// Insert lifetime start/end markers surrounding the call to the new function
1022/// for objects defined in the caller.
1023static void insertLifetimeMarkersSurroundingCall(
  Module *M, ArrayRef<Value *> LifetimesStart, ArrayRef<Value *> LifetimesEnd,
  CallInst *TheCall) {
LLVMContext &Ctx = M->getContext();
auto Int8PtrTy = Type::getInt8PtrTy(Ctx);
auto NegativeOne = ConstantInt::getSigned(Type::getInt64Ty(Ctx), -1);
Instruction *Term = TheCall->getParent()->getTerminator();

// The memory argument to a lifetime marker must be a i8*. Cache any bitcasts
// needed to satisfy this requirement so they may be reused.
DenseMap<Value *, Value *> Bitcasts;

// Emit lifetime markers for the pointers given in \p Objects. Insert the
// markers before the call if \p InsertBefore, and after the call otherwise.
auto insertMarkers = [&](Function *MarkerFunc, ArrayRef<Value *> Objects,
                         bool InsertBefore) {
  for (Value *Mem : Objects) {
    assert((!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() ==(((!isa<Instruction>(Mem) || cast<Instruction>(Mem
)->getFunction() == TheCall->getFunction()) && "Input memory not defined in original function"
) ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() == TheCall->getFunction()) && \"Input memory not defined in original function\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 1042, __PRETTY_FUNCTION__))
                                          TheCall->getFunction()) &&(((!isa<Instruction>(Mem) || cast<Instruction>(Mem
)->getFunction() == TheCall->getFunction()) && "Input memory not defined in original function"
) ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() == TheCall->getFunction()) && \"Input memory not defined in original function\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 1042, __PRETTY_FUNCTION__))
           "Input memory not defined in original function")(((!isa<Instruction>(Mem) || cast<Instruction>(Mem
)->getFunction() == TheCall->getFunction()) && "Input memory not defined in original function"
) ? static_cast<void> (0) : __assert_fail ("(!isa<Instruction>(Mem) || cast<Instruction>(Mem)->getFunction() == TheCall->getFunction()) && \"Input memory not defined in original function\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 1042, __PRETTY_FUNCTION__));
    Value *&MemAsI8Ptr = Bitcasts[Mem];
    if (!MemAsI8Ptr) {
      if (Mem->getType() == Int8PtrTy)
        MemAsI8Ptr = Mem;
      else
        MemAsI8Ptr =
            CastInst::CreatePointerCast(Mem, Int8PtrTy, "lt.cast", TheCall);
    }

    auto Marker = CallInst::Create(MarkerFunc, {NegativeOne, MemAsI8Ptr});
    if (InsertBefore)
      Marker->insertBefore(TheCall);
    else
      Marker->insertBefore(Term);
  }
};

if (!LifetimesStart.empty()) {
  auto StartFn = llvm::Intrinsic::getDeclaration(
      M, llvm::Intrinsic::lifetime_start, Int8PtrTy);
  insertMarkers(StartFn, LifetimesStart, /*InsertBefore=*/true);
}

if (!LifetimesEnd.empty()) {
  auto EndFn = llvm::Intrinsic::getDeclaration(
      M, llvm::Intrinsic::lifetime_end, Int8PtrTy);
  insertMarkers(EndFn, LifetimesEnd, /*InsertBefore=*/false);
}
1071}

1073/// emitCallAndSwitchStatement - This method sets up the caller side by adding
1074/// the call instruction, splitting any PHI nodes in the header block as
1075/// necessary.
1076CallInst *CodeExtractor::emitCallAndSwitchStatement(Function *newFunction,
                                                  BasicBlock *codeReplacer,
                                                  ValueSet &inputs,
                                                  ValueSet &outputs) {
// Emit a call to the new function, passing in: *pointer to struct (if
// aggregating parameters), or plan inputs and allocated memory for outputs
std::vector<Value *> params, StructValues, ReloadOutputs, Reloads;

Module *M = newFunction->getParent();
LLVMContext &Context = M->getContext();
const DataLayout &DL = M->getDataLayout();
CallInst *call = nullptr;

// Add inputs as params, or to be filled into the struct
unsigned ArgNo = 0;
SmallVector<unsigned, 1> SwiftErrorArgs;
for (Value *input : inputs) {
  if (AggregateArgs)
    StructValues.push_back(input);
  else {
    params.push_back(input);
    if (input->isSwiftError())
      SwiftErrorArgs.push_back(ArgNo);
  }
  ++ArgNo;
}

// Create allocas for the outputs
for (Value *output : outputs) {
  if (AggregateArgs) {
    StructValues.push_back(output);
  } else {
    AllocaInst *alloca =
      new AllocaInst(output->getType(), DL.getAllocaAddrSpace(),
                     nullptr, output->getName() + ".loc",
                     &codeReplacer->getParent()->front().front());
    ReloadOutputs.push_back(alloca);
    params.push_back(alloca);
  }
}

StructType *StructArgTy = nullptr;
AllocaInst *Struct = nullptr;
if (AggregateArgs && (inputs.size() + outputs.size() > 0)) {
  std::vector<Type *> ArgTypes;
  for (ValueSet::iterator v = StructValues.begin(),
         ve = StructValues.end(); v != ve; ++v)
    ArgTypes.push_back((*v)->getType());

  // Allocate a struct at the beginning of this function
  StructArgTy = StructType::get(newFunction->getContext(), ArgTypes);
  Struct = new AllocaInst(StructArgTy, DL.getAllocaAddrSpace(), nullptr,
                          "structArg",
                          &codeReplacer->getParent()->front().front());
  params.push_back(Struct);

  for (unsigned i = 0, e = inputs.size(); i != e; ++i) {
    Value *Idx[2];
    Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
    Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i);
    GetElementPtrInst *GEP = GetElementPtrInst::Create(
        StructArgTy, Struct, Idx, "gep_" + StructValues[i]->getName());
    codeReplacer->getInstList().push_back(GEP);
    new StoreInst(StructValues[i], GEP, codeReplacer);
  }
}

// Emit the call to the function
call = CallInst::Create(newFunction, params,
                        NumExitBlocks > 1 ? "targetBlock" : "");
// Add debug location to the new call, if the original function has debug
// info. In that case, the terminator of the entry block of the extracted
// function contains the first debug location of the extracted function,
// set in extractCodeRegion.
if (codeReplacer->getParent()->getSubprogram()) {
  if (auto DL = newFunction->getEntryBlock().getTerminator()->getDebugLoc())
    call->setDebugLoc(DL);
}
codeReplacer->getInstList().push_back(call);

// Set swifterror parameter attributes.
for (unsigned SwiftErrArgNo : SwiftErrorArgs) {
  call->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
  newFunction->addParamAttr(SwiftErrArgNo, Attribute::SwiftError);
}

Function::arg_iterator OutputArgBegin = newFunction->arg_begin();
unsigned FirstOut = inputs.size();
if (!AggregateArgs)
  std::advance(OutputArgBegin, inputs.size());

// Reload the outputs passed in by reference.
for (unsigned i = 0, e = outputs.size(); i != e; ++i) {
  Value *Output = nullptr;
  if (AggregateArgs) {
    Value *Idx[2];
    Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
    Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
    GetElementPtrInst *GEP = GetElementPtrInst::Create(
        StructArgTy, Struct, Idx, "gep_reload_" + outputs[i]->getName());
    codeReplacer->getInstList().push_back(GEP);
    Output = GEP;
  } else {
    Output = ReloadOutputs[i];
  }
  LoadInst *load = new LoadInst(outputs[i]->getType(), Output,
                                outputs[i]->getName() + ".reload",
                                codeReplacer);
  Reloads.push_back(load);
  std::vector<User *> Users(outputs[i]->user_begin(), outputs[i]->user_end());
  for (unsigned u = 0, e = Users.size(); u != e; ++u) {
    Instruction *inst = cast<Instruction>(Users[u]);
    if (!Blocks.count(inst->getParent()))
      inst->replaceUsesOfWith(outputs[i], load);
  }
}

// Now we can emit a switch statement using the call as a value.
SwitchInst *TheSwitch =
    SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)),
                       codeReplacer, 0, codeReplacer);

// Since there may be multiple exits from the original region, make the new
// function return an unsigned, switch on that number.  This loop iterates
// over all of the blocks in the extracted region, updating any terminator
// instructions in the to-be-extracted region that branch to blocks that are
// not in the region to be extracted.
std::map<BasicBlock *, BasicBlock *> ExitBlockMap;

unsigned switchVal = 0;
for (BasicBlock *Block : Blocks) {
  Instruction *TI = Block->getTerminator();
  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
    if (!Blocks.count(TI->getSuccessor(i))) {
      BasicBlock *OldTarget = TI->getSuccessor(i);
      // add a new basic block which returns the appropriate value
      BasicBlock *&NewTarget = ExitBlockMap[OldTarget];
      if (!NewTarget) {
        // If we don't already have an exit stub for this non-extracted
        // destination, create one now!
        NewTarget = BasicBlock::Create(Context,
                                       OldTarget->getName() + ".exitStub",
                                       newFunction);
        unsigned SuccNum = switchVal++;

        Value *brVal = nullptr;
        switch (NumExitBlocks) {
        case 0:
        case 1: break;  // No value needed.
        case 2:         // Conditional branch, return a bool
          brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum);
          break;
        default:
          brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum);
          break;
        }

        ReturnInst::Create(Context, brVal, NewTarget);

        // Update the switch instruction.
        TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context),
                                            SuccNum),
                           OldTarget);
      }

      // rewrite the original branch instruction with this new target
      TI->setSuccessor(i, NewTarget);
    }
}

// Store the arguments right after the definition of output value.
// This should be proceeded after creating exit stubs to be ensure that invoke
// result restore will be placed in the outlined function.
Function::arg_iterator OAI = OutputArgBegin;
for (unsigned i = 0, e = outputs.size(); i != e; ++i) {
  auto *OutI = dyn_cast<Instruction>(outputs[i]);
  if (!OutI)
    continue;

  // Find proper insertion point.
  BasicBlock::iterator InsertPt;
  // In case OutI is an invoke, we insert the store at the beginning in the
  // 'normal destination' BB. Otherwise we insert the store right after OutI.
  if (auto *InvokeI = dyn_cast<InvokeInst>(OutI))
    InsertPt = InvokeI->getNormalDest()->getFirstInsertionPt();
  else if (auto *Phi = dyn_cast<PHINode>(OutI))
    InsertPt = Phi->getParent()->getFirstInsertionPt();
  else
    InsertPt = std::next(OutI->getIterator());

  Instruction *InsertBefore = &*InsertPt;
  assert((InsertBefore->getFunction() == newFunction ||(((InsertBefore->getFunction() == newFunction || Blocks.count
(InsertBefore->getParent())) && "InsertPt should be in new function"
) ? static_cast<void> (0) : __assert_fail ("(InsertBefore->getFunction() == newFunction || Blocks.count(InsertBefore->getParent())) && \"InsertPt should be in new function\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 1269, __PRETTY_FUNCTION__))
          Blocks.count(InsertBefore->getParent())) &&(((InsertBefore->getFunction() == newFunction || Blocks.count
(InsertBefore->getParent())) && "InsertPt should be in new function"
) ? static_cast<void> (0) : __assert_fail ("(InsertBefore->getFunction() == newFunction || Blocks.count(InsertBefore->getParent())) && \"InsertPt should be in new function\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 1269, __PRETTY_FUNCTION__))
         "InsertPt should be in new function")(((InsertBefore->getFunction() == newFunction || Blocks.count
(InsertBefore->getParent())) && "InsertPt should be in new function"
) ? static_cast<void> (0) : __assert_fail ("(InsertBefore->getFunction() == newFunction || Blocks.count(InsertBefore->getParent())) && \"InsertPt should be in new function\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 1269, __PRETTY_FUNCTION__));
  assert(OAI != newFunction->arg_end() &&((OAI != newFunction->arg_end() && "Number of output arguments should match "
 "the amount of defined values") ? static_cast<void> (0
) : __assert_fail ("OAI != newFunction->arg_end() && \"Number of output arguments should match \" \"the amount of defined values\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 1272, __PRETTY_FUNCTION__))
         "Number of output arguments should match "((OAI != newFunction->arg_end() && "Number of output arguments should match "
 "the amount of defined values") ? static_cast<void> (0
) : __assert_fail ("OAI != newFunction->arg_end() && \"Number of output arguments should match \" \"the amount of defined values\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 1272, __PRETTY_FUNCTION__))
         "the amount of defined values")((OAI != newFunction->arg_end() && "Number of output arguments should match "
 "the amount of defined values") ? static_cast<void> (0
) : __assert_fail ("OAI != newFunction->arg_end() && \"Number of output arguments should match \" \"the amount of defined values\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 1272, __PRETTY_FUNCTION__));
  if (AggregateArgs) {
    Value *Idx[2];
    Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context));
    Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i);
    GetElementPtrInst *GEP = GetElementPtrInst::Create(
        StructArgTy, &*OAI, Idx, "gep_" + outputs[i]->getName(),
        InsertBefore);
    new StoreInst(outputs[i], GEP, InsertBefore);
    // Since there should be only one struct argument aggregating
    // all the output values, we shouldn't increment OAI, which always
    // points to the struct argument, in this case.
  } else {
    new StoreInst(outputs[i], &*OAI, InsertBefore);
    ++OAI;
  }
}

// Now that we've done the deed, simplify the switch instruction.
Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType();
switch (NumExitBlocks) {
case 0:
  // There are no successors (the block containing the switch itself), which
  // means that previously this was the last part of the function, and hence
  // this should be rewritten as a `ret'

  // Check if the function should return a value
  if (OldFnRetTy->isVoidTy()) {
    ReturnInst::Create(Context, nullptr, TheSwitch);  // Return void
  } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) {
    // return what we have
    ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch);
  } else {
    // Otherwise we must have code extracted an unwind or something, just
    // return whatever we want.
    ReturnInst::Create(Context,
                       Constant::getNullValue(OldFnRetTy), TheSwitch);
  }

  TheSwitch->eraseFromParent();
  break;
case 1:
  // Only a single destination, change the switch into an unconditional
  // branch.
  BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch);
  TheSwitch->eraseFromParent();
  break;
case 2:
  BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2),
                     call, TheSwitch);
  TheSwitch->eraseFromParent();
  break;
default:
  // Otherwise, make the default destination of the switch instruction be one
  // of the other successors.
  TheSwitch->setCondition(call);
  TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks));
  // Remove redundant case
  TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1));
  break;
}

// Insert lifetime markers around the reloads of any output values. The
// allocas output values are stored in are only in-use in the codeRepl block.
insertLifetimeMarkersSurroundingCall(M, ReloadOutputs, ReloadOutputs, call);

return call;
1339}

1341void CodeExtractor::moveCodeToFunction(Function *newFunction) {
Function *oldFunc = (*Blocks.begin())->getParent();
Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList();
Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList();

for (BasicBlock *Block : Blocks) {
  // Delete the basic block from the old function, and the list of blocks
  oldBlocks.remove(Block);

  // Insert this basic block into the new function
  newBlocks.push_back(Block);
}
1353}

1355void CodeExtractor::calculateNewCallTerminatorWeights(
  BasicBlock *CodeReplacer,
  DenseMap<BasicBlock *, BlockFrequency> &ExitWeights,
  BranchProbabilityInfo *BPI) {
using Distribution = BlockFrequencyInfoImplBase::Distribution;
using BlockNode = BlockFrequencyInfoImplBase::BlockNode;

// Update the branch weights for the exit block.
Instruction *TI = CodeReplacer->getTerminator();
SmallVector<unsigned, 8> BranchWeights(TI->getNumSuccessors(), 0);

// Block Frequency distribution with dummy node.
Distribution BranchDist;

SmallVector<BranchProbability, 4> EdgeProbabilities(
    TI->getNumSuccessors(), BranchProbability::getUnknown());

// Add each of the frequencies of the successors.
for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) {
  BlockNode ExitNode(i);
  uint64_t ExitFreq = ExitWeights[TI->getSuccessor(i)].getFrequency();
  if (ExitFreq != 0)
    BranchDist.addExit(ExitNode, ExitFreq);
  else
    EdgeProbabilities[i] = BranchProbability::getZero();
}

// Check for no total weight.
if (BranchDist.Total == 0) {
  BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
  return;
}

// Normalize the distribution so that they can fit in unsigned.
BranchDist.normalize();

// Create normalized branch weights and set the metadata.
for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) {
  const auto &Weight = BranchDist.Weights[I];

  // Get the weight and update the current BFI.
  BranchWeights[Weight.TargetNode.Index] = Weight.Amount;
  BranchProbability BP(Weight.Amount, BranchDist.Total);
  EdgeProbabilities[Weight.TargetNode.Index] = BP;
}
BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
TI->setMetadata(
    LLVMContext::MD_prof,
    MDBuilder(TI->getContext()).createBranchWeights(BranchWeights));
1404}

1406/// Erase debug info intrinsics which refer to values in \p F but aren't in
1407/// \p F.
1408static void eraseDebugIntrinsicsWithNonLocalRefs(Function &F) {
for (Instruction &I : instructions(F)) {
  SmallVector<DbgVariableIntrinsic *, 4> DbgUsers;
  findDbgUsers(DbgUsers, &I);
  for (DbgVariableIntrinsic *DVI : DbgUsers)
    if (DVI->getFunction() != &F)
      DVI->eraseFromParent();
}
1416}

1418/// Fix up the debug info in the old and new functions by pointing line
1419/// locations and debug intrinsics to the new subprogram scope, and by deleting
1420/// intrinsics which point to values outside of the new function.
1421static void fixupDebugInfoPostExtraction(Function &OldFunc, Function &NewFunc,
                                       CallInst &TheCall) {
DISubprogram *OldSP = OldFunc.getSubprogram();
LLVMContext &Ctx = OldFunc.getContext();

if (!OldSP) {
  // Erase any debug info the new function contains.
  stripDebugInfo(NewFunc);
  // Make sure the old function doesn't contain any non-local metadata refs.
  eraseDebugIntrinsicsWithNonLocalRefs(NewFunc);
  return;
}

// Create a subprogram for the new function. Leave out a description of the
// function arguments, as the parameters don't correspond to anything at the
// source level.
assert(OldSP->getUnit() && "Missing compile unit for subprogram")((OldSP->getUnit() && "Missing compile unit for subprogram"
) ? static_cast<void> (0) : __assert_fail ("OldSP->getUnit() && \"Missing compile unit for subprogram\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 1437, __PRETTY_FUNCTION__));
DIBuilder DIB(*OldFunc.getParent(), /*AllowUnresolved=*/false,
              OldSP->getUnit());
auto SPType = DIB.createSubroutineType(DIB.getOrCreateTypeArray(None));
DISubprogram::DISPFlags SPFlags = DISubprogram::SPFlagDefinition |
                                  DISubprogram::SPFlagOptimized |
                                  DISubprogram::SPFlagLocalToUnit;
auto NewSP = DIB.createFunction(
    OldSP->getUnit(), NewFunc.getName(), NewFunc.getName(), OldSP->getFile(),
    /*LineNo=*/0, SPType, /*ScopeLine=*/0, DINode::FlagZero, SPFlags);
NewFunc.setSubprogram(NewSP);

// Debug intrinsics in the new function need to be updated in one of two
// ways:
//  1) They need to be deleted, because they describe a value in the old
//     function.
//  2) They need to point to fresh metadata, e.g. because they currently
//     point to a variable in the wrong scope.
SmallDenseMap<DINode *, DINode *> RemappedMetadata;
SmallVector<Instruction *, 4> DebugIntrinsicsToDelete;
for (Instruction &I : instructions(NewFunc)) {
  auto *DII = dyn_cast<DbgInfoIntrinsic>(&I);
  if (!DII)
    continue;

  // Point the intrinsic to a fresh label within the new function.
  if (auto *DLI = dyn_cast<DbgLabelInst>(&I)) {
    DILabel *OldLabel = DLI->getLabel();
    DINode *&NewLabel = RemappedMetadata[OldLabel];
    if (!NewLabel)
      NewLabel = DILabel::get(Ctx, NewSP, OldLabel->getName(),
                              OldLabel->getFile(), OldLabel->getLine());
    DLI->setArgOperand(0, MetadataAsValue::get(Ctx, NewLabel));
    continue;
  }

  // If the location isn't a constant or an instruction, delete the
  // intrinsic.
  auto *DVI = cast<DbgVariableIntrinsic>(DII);
  Value *Location = DVI->getVariableLocation();
  if (!Location ||
      (!isa<Constant>(Location) && !isa<Instruction>(Location))) {
    DebugIntrinsicsToDelete.push_back(DVI);
    continue;
  }

  // If the variable location is an instruction but isn't in the new
  // function, delete the intrinsic.
  Instruction *LocationInst = dyn_cast<Instruction>(Location);
  if (LocationInst && LocationInst->getFunction() != &NewFunc) {
    DebugIntrinsicsToDelete.push_back(DVI);
    continue;
  }

  // Point the intrinsic to a fresh variable within the new function.
  DILocalVariable *OldVar = DVI->getVariable();
  DINode *&NewVar = RemappedMetadata[OldVar];
  if (!NewVar)
    NewVar = DIB.createAutoVariable(
        NewSP, OldVar->getName(), OldVar->getFile(), OldVar->getLine(),
        OldVar->getType(), /*AlwaysPreserve=*/false, DINode::FlagZero,
        OldVar->getAlignInBits());
  DVI->setArgOperand(1, MetadataAsValue::get(Ctx, NewVar));
}
for (auto *DII : DebugIntrinsicsToDelete)
  DII->eraseFromParent();
DIB.finalizeSubprogram(NewSP);

// Fix up the scope information attached to the line locations in the new
// function.
for (Instruction &I : instructions(NewFunc)) {
  if (const DebugLoc &DL = I.getDebugLoc())
    I.setDebugLoc(DebugLoc::get(DL.getLine(), DL.getCol(), NewSP));

  // Loop info metadata may contain line locations. Fix them up.
  auto updateLoopInfoLoc = [&Ctx,
                            NewSP](const DILocation &Loc) -> DILocation * {
    return DILocation::get(Ctx, Loc.getLine(), Loc.getColumn(), NewSP,
                           nullptr);
  };
  updateLoopMetadataDebugLocations(I, updateLoopInfoLoc);
}
if (!TheCall.getDebugLoc())
  TheCall.setDebugLoc(DebugLoc::get(0, 0, OldSP));

eraseDebugIntrinsicsWithNonLocalRefs(NewFunc);
1523}

1525Function *
1526CodeExtractor::extractCodeRegion(const CodeExtractorAnalysisCache &CEAC) {
if (!isEligible())
1
Taking false branch→
  return nullptr;

// Assumption: this is a single-entry code region, and the header is the first
// block in the region.
BasicBlock *header = *Blocks.begin();
Function *oldFunction = header->getParent();

// Calculate the entry frequency of the new function before we change the root
//   block.
BlockFrequency EntryFreq;
if (BFI) {
2
←
Assuming field 'BFI' is null→
3
←
Taking false branch→
  assert(BPI && "Both BPI and BFI are required to preserve profile info")((BPI && "Both BPI and BFI are required to preserve profile info"
) ? static_cast<void> (0) : __assert_fail ("BPI && \"Both BPI and BFI are required to preserve profile info\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 1539, __PRETTY_FUNCTION__));
  for (BasicBlock *Pred : predecessors(header)) {
    if (Blocks.count(Pred))
      continue;
    EntryFreq +=
        BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header);
  }
}

// Remove @llvm.assume calls that will be moved to the new function from the
// old function's assumption cache.
for (BasicBlock *Block : Blocks) {
  for (auto It = Block->begin(), End = Block->end(); It != End;) {
    Instruction *I = &*It;
    ++It;

    if (match(I, m_Intrinsic<Intrinsic::assume>())) {
      if (AC)
        AC->unregisterAssumption(cast<CallInst>(I));
      I->eraseFromParent();
    }
  }
}

// If we have any return instructions in the region, split those blocks so
// that the return is not in the region.
splitReturnBlocks();

// Calculate the exit blocks for the extracted region and the total exit
// weights for each of those blocks.
DenseMap<BasicBlock *, BlockFrequency> ExitWeights;
SmallPtrSet<BasicBlock *, 1> ExitBlocks;
for (BasicBlock *Block : Blocks) {
  for (succ_iterator SI = succ_begin(Block), SE = succ_end(Block); SI != SE;
       ++SI) {
    if (!Blocks.count(*SI)) {
      // Update the branch weight for this successor.
      if (BFI) {
        BlockFrequency &BF = ExitWeights[*SI];
        BF += BFI->getBlockFreq(Block) * BPI->getEdgeProbability(Block, *SI);
      }
      ExitBlocks.insert(*SI);
    }
  }
}
NumExitBlocks = ExitBlocks.size();

// If we have to split PHI nodes of the entry or exit blocks, do so now.
severSplitPHINodesOfEntry(header);
severSplitPHINodesOfExits(ExitBlocks);

// This takes place of the original loop
BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(),
                                              "codeRepl", oldFunction,
                                              header);

// The new function needs a root node because other nodes can branch to the
// head of the region, but the entry node of a function cannot have preds.
BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(),
                                             "newFuncRoot");
auto *BranchI = BranchInst::Create(header);
// If the original function has debug info, we have to add a debug location
// to the new branch instruction from the artificial entry block.
// We use the debug location of the first instruction in the extracted
// blocks, as there is no other equivalent line in the source code.
if (oldFunction->getSubprogram()) {
4
←
Assuming the condition is false→
5
←
Taking false branch→
  any_of(Blocks, [&BranchI](const BasicBlock *BB) {
    return any_of(*BB, [&BranchI](const Instruction &I) {
      if (!I.getDebugLoc())
        return false;
      BranchI->setDebugLoc(I.getDebugLoc());
      return true;
    });
  });
}
newFuncRoot->getInstList().push_back(BranchI);

ValueSet inputs, outputs, SinkingCands, HoistingCands;
BasicBlock *CommonExit = nullptr;
findAllocas(CEAC, SinkingCands, HoistingCands, CommonExit);
assert(HoistingCands.empty() || CommonExit)((HoistingCands.empty() || CommonExit) ? static_cast<void>
 (0) : __assert_fail ("HoistingCands.empty() || CommonExit", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 1619, __PRETTY_FUNCTION__));
6
←
Assuming the condition is true→

// Find inputs to, outputs from the code region.
findInputsOutputs(inputs, outputs, SinkingCands);

// Now sink all instructions which only have non-phi uses inside the region.
// Group the allocas at the start of the block, so that any bitcast uses of
// the allocas are well-defined.
AllocaInst *FirstSunkAlloca = nullptr;
for (auto *II : SinkingCands) {
  if (auto *AI = dyn_cast<AllocaInst>(II)) {
    AI->moveBefore(*newFuncRoot, newFuncRoot->getFirstInsertionPt());
    if (!FirstSunkAlloca)
      FirstSunkAlloca = AI;
  }
}
assert((SinkingCands.empty() || FirstSunkAlloca) &&(((SinkingCands.empty() || FirstSunkAlloca) && "Did not expect a sink candidate without any allocas"
) ? static_cast<void> (0) : __assert_fail ("(SinkingCands.empty() || FirstSunkAlloca) && \"Did not expect a sink candidate without any allocas\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 1636, __PRETTY_FUNCTION__))
7
←
Assuming the condition is true→
8
←
'?' condition is true→
       "Did not expect a sink candidate without any allocas")(((SinkingCands.empty() || FirstSunkAlloca) && "Did not expect a sink candidate without any allocas"
) ? static_cast<void> (0) : __assert_fail ("(SinkingCands.empty() || FirstSunkAlloca) && \"Did not expect a sink candidate without any allocas\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 1636, __PRETTY_FUNCTION__));
for (auto *II : SinkingCands) {
  if (!isa<AllocaInst>(II)) {
    cast<Instruction>(II)->moveAfter(FirstSunkAlloca);
  }
}

if (!HoistingCands.empty()) {
9
←
Assuming the condition is false→
10
←
Taking false branch→
  auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit);
  Instruction *TI = HoistToBlock->getTerminator();
  for (auto *II : HoistingCands)
    cast<Instruction>(II)->moveBefore(TI);
}

// Collect objects which are inputs to the extraction region and also
// referenced by lifetime start markers within it. The effects of these
// markers must be replicated in the calling function to prevent the stack
// coloring pass from merging slots which store input objects.
ValueSet LifetimesStart;
eraseLifetimeMarkersOnInputs(Blocks, SinkingCands, LifetimesStart);

// Construct new function based on inputs/outputs & add allocas for all defs.
Function *newFunction =
    constructFunction(inputs, outputs, header, newFuncRoot, codeReplacer,
                      oldFunction, oldFunction->getParent());

// Update the entry count of the function.
if (BFI) {
11
←
Assuming field 'BFI' is null→
12
←
Taking false branch→
  auto Count = BFI->getProfileCountFromFreq(EntryFreq.getFrequency());
  if (Count.hasValue())
    newFunction->setEntryCount(
        ProfileCount(Count.getValue(), Function::PCT_Real)); // FIXME
  BFI->setBlockFreq(codeReplacer, EntryFreq.getFrequency());
}

CallInst *TheCall =
    emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs);

moveCodeToFunction(newFunction);

// Replicate the effects of any lifetime start/end markers which referenced
// input objects in the extraction region by placing markers around the call.
insertLifetimeMarkersSurroundingCall(
    oldFunction->getParent(), LifetimesStart.getArrayRef(), {}, TheCall);

// Propagate personality info to the new function if there is one.
if (oldFunction->hasPersonalityFn())
13
←
Assuming the condition is false→
14
←
Taking false branch→
  newFunction->setPersonalityFn(oldFunction->getPersonalityFn());

// Update the branch weights for the exit block.
if (BFI && NumExitBlocks > 1)
15
←
Assuming field 'BFI' is null→
  calculateNewCallTerminatorWeights(codeReplacer, ExitWeights, BPI);

// Loop over all of the PHI nodes in the header and exit blocks, and change
// any references to the old incoming edge to be the new incoming edge.
for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) {
16
←
Assuming 'I' is not a 'PHINode'→
17
←
Loop condition is false. Execution continues on line 1698→
  PHINode *PN = cast<PHINode>(I);
  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
    if (!Blocks.count(PN->getIncomingBlock(i)))
      PN->setIncomingBlock(i, newFuncRoot);
}

for (BasicBlock *ExitBB : ExitBlocks)
  for (PHINode &PN : ExitBB->phis()) {
    Value *IncomingCodeReplacerVal = nullptr;
    for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
      // Ignore incoming values from outside of the extracted region.
      if (!Blocks.count(PN.getIncomingBlock(i)))
        continue;

      // Ensure that there is only one incoming value from codeReplacer.
      if (!IncomingCodeReplacerVal) {
        PN.setIncomingBlock(i, codeReplacer);
        IncomingCodeReplacerVal = PN.getIncomingValue(i);
      } else
        assert(IncomingCodeReplacerVal == PN.getIncomingValue(i) &&((IncomingCodeReplacerVal == PN.getIncomingValue(i) &&
 "PHI has two incompatbile incoming values from codeRepl") ? static_cast
<void> (0) : __assert_fail ("IncomingCodeReplacerVal == PN.getIncomingValue(i) && \"PHI has two incompatbile incoming values from codeRepl\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 1712, __PRETTY_FUNCTION__))
               "PHI has two incompatbile incoming values from codeRepl")((IncomingCodeReplacerVal == PN.getIncomingValue(i) &&
 "PHI has two incompatbile incoming values from codeRepl") ? static_cast
<void> (0) : __assert_fail ("IncomingCodeReplacerVal == PN.getIncomingValue(i) && \"PHI has two incompatbile incoming values from codeRepl\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Transforms/Utils/CodeExtractor.cpp"
, 1712, __PRETTY_FUNCTION__));
    }
  }

fixupDebugInfoPostExtraction(*oldFunction, *newFunction, *TheCall);

// Mark the new function `noreturn` if applicable. Terminators which resume
// exception propagation are treated as returning instructions. This is to
// avoid inserting traps after calls to outlined functions which unwind.
bool doesNotReturn = none_of(*newFunction, [](const BasicBlock &BB) {
  const Instruction *Term = BB.getTerminator();
  return isa<ReturnInst>(Term) || isa<ResumeInst>(Term);
});
if (doesNotReturn17.1
'doesNotReturn' is true
1
'doesNotReturn' is true
1
'doesNotReturn' is true
)
18
←
Taking true branch→
  newFunction->setDoesNotReturn();

LLVM_DEBUG(if (verifyFunction(*newFunction, &errs())) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { if (verifyFunction(*newFunction, &errs
())) { newFunction->dump(); report_fatal_error("verification of newFunction failed!"
); }; } } while (false)
19
←
Assuming 'DebugFlag' is true→
20
←
Assuming the condition is false→
21
←
Taking false branch→
22
←
Loop condition is false.  Exiting loop→
  newFunction->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { if (verifyFunction(*newFunction, &errs
())) { newFunction->dump(); report_fatal_error("verification of newFunction failed!"
); }; } } while (false)
  report_fatal_error("verification of newFunction failed!");do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { if (verifyFunction(*newFunction, &errs
())) { newFunction->dump(); report_fatal_error("verification of newFunction failed!"
); }; } } while (false)
})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { if (verifyFunction(*newFunction, &errs
())) { newFunction->dump(); report_fatal_error("verification of newFunction failed!"
); }; } } while (false);
LLVM_DEBUG(if (verifyFunction(*oldFunction))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { if (verifyFunction(*oldFunction)) report_fatal_error
("verification of oldFunction failed!"); } } while (false)
23
←
Assuming 'DebugFlag' is true→
24
←
Assuming the condition is false→
25
←
Taking false branch→
26
←
Loop condition is false.  Exiting loop→
           report_fatal_error("verification of oldFunction failed!"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { if (verifyFunction(*oldFunction)) report_fatal_error
("verification of oldFunction failed!"); } } while (false);
LLVM_DEBUG(if (AC && verifyAssumptionCache(*oldFunction, *newFunction, AC))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { if (AC && verifyAssumptionCache
(*oldFunction, *newFunction, AC)) report_fatal_error("Stale Asumption cache for old Function!"
); } } while (false)
27
←
Assuming 'DebugFlag' is true→
28
←
Assuming the condition is true→
29
←
Taking true branch→
30
←
Assuming field 'AC' is non-null→
31
←
Calling 'CodeExtractor::verifyAssumptionCache'→
               report_fatal_error("Stale Asumption cache for old Function!"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("code-extractor")) { if (AC && verifyAssumptionCache
(*oldFunction, *newFunction, AC)) report_fatal_error("Stale Asumption cache for old Function!"
); } } while (false);
return newFunction;
1737}

1739bool CodeExtractor::verifyAssumptionCache(const Function &OldFunc,
                                        const Function &NewFunc,
                                        AssumptionCache *AC) {
for (auto AssumeVH : AC->assumptions()) {
32
←
Assuming '__begin1' is not equal to '__end1'→
33
←
Calling implicit copy constructor for 'ResultElem'→
34
←
Calling copy constructor for 'WeakTrackingVH'→
42
←
Returning from copy constructor for 'WeakTrackingVH'→
43
←
Returning from copy constructor for 'ResultElem'→
  CallInst *I = dyn_cast_or_null<CallInst>(AssumeVH);
44
←
Calling 'dyn_cast_or_null<llvm::CallInst, llvm::AssumptionCache::ResultElem>'→
53
←
Returning from 'dyn_cast_or_null<llvm::CallInst, llvm::AssumptionCache::ResultElem>'→
  if (!I53.1
'I' is non-null
1
'I' is non-null
1
'I' is non-null
)
54
←
Taking false branch→
    continue;

  // There shouldn't be any llvm.assume intrinsics in the new function.
  if (I->getFunction() != &OldFunc)
55
←
Assuming the condition is false→
56
←
Taking false branch→
    return true;

  // There shouldn't be any stale affected values in the assumption cache
  // that were previously in the old function, but that have now been moved
  // to the new function.
  for (auto AffectedValVH : AC->assumptionsFor(I->getOperand(0))) {
57
←
Assuming '__begin2' is not equal to '__end2'→
58
←
Calling implicit copy constructor for 'ResultElem'→
59
←
Calling copy constructor for 'WeakTrackingVH'→
67
←
Returning from copy constructor for 'WeakTrackingVH'→
68
←
Returning from copy constructor for 'ResultElem'→
    CallInst *AffectedCI = dyn_cast_or_null<CallInst>(AffectedValVH);
69
←
Calling 'dyn_cast_or_null<llvm::CallInst, llvm::AssumptionCache::ResultElem>'→
78
←
Returning from 'dyn_cast_or_null<llvm::CallInst, llvm::AssumptionCache::ResultElem>'→
    if (!AffectedCI78.1
'AffectedCI' is non-null
1
'AffectedCI' is non-null
1
'AffectedCI' is non-null
)
79
←
Taking false branch→
      continue;
    if (AffectedCI->getFunction() != &OldFunc)
80
←
Assuming the condition is false→
81
←
Taking false branch→
      return true;
    auto *AssumedInst = dyn_cast<Instruction>(AffectedCI->getOperand(0));
82
←
Assuming the object is not a 'Instruction'→
83
←
'AssumedInst' initialized to a null pointer value→
    if (AssumedInst->getFunction() != &OldFunc)
84
←
Called C++ object pointer is null
      return true;
  }
}
return false;
1766}

←

/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/IR/ValueHandle.h

→

1//===- ValueHandle.h - Value Smart Pointer classes --------------*- 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 declares the ValueHandle class and its sub-classes.
10//
11//===----------------------------------------------------------------------===//
12 
13#ifndef LLVM_IR_VALUEHANDLE_H
14#define LLVM_IR_VALUEHANDLE_H
15 
16#include "llvm/ADT/DenseMapInfo.h"
17#include "llvm/ADT/PointerIntPair.h"
18#include "llvm/IR/Value.h"
19#include "llvm/Support/Casting.h"
20#include <cassert>
21 
22namespace llvm {
23 
24/// This is the common base class of value handles.
25///
26/// ValueHandle's are smart pointers to Value's that have special behavior when
27/// the value is deleted or ReplaceAllUsesWith'd.  See the specific handles
28/// below for details.
29class ValueHandleBase {
30  friend class Value;
31 
32protected:
33  /// This indicates what sub class the handle actually is.
34  ///
35  /// This is to avoid having a vtable for the light-weight handle pointers. The
36  /// fully general Callback version does have a vtable.
37  enum HandleBaseKind { Assert, Callback, Weak, WeakTracking };
38 
39  ValueHandleBase(const ValueHandleBase &RHS)
40      : ValueHandleBase(RHS.PrevPair.getInt(), RHS) {}
41 
42  ValueHandleBase(HandleBaseKind Kind, const ValueHandleBase &RHS)
43      : PrevPair(nullptr, Kind), Val(RHS.getValPtr()) {
44    if (isValid(getValPtr()))
36
←
Calling 'ValueHandleBase::isValid'→
39
←
Returning from 'ValueHandleBase::isValid'→
40
←
Taking false branch→
61
←
Calling 'ValueHandleBase::isValid'→
64
←
Returning from 'ValueHandleBase::isValid'→
65
←
Taking false branch→
45      AddToExistingUseList(RHS.getPrevPtr());
46  }
47 
48private:
49  PointerIntPair<ValueHandleBase**, 2, HandleBaseKind> PrevPair;
50  ValueHandleBase *Next = nullptr;
51  Value *Val = nullptr;
52 
53  void setValPtr(Value *V) { Val = V; }
54 
55public:
56  explicit ValueHandleBase(HandleBaseKind Kind)
57      : PrevPair(nullptr, Kind) {}
58  ValueHandleBase(HandleBaseKind Kind, Value *V)
59      : PrevPair(nullptr, Kind), Val(V) {
60    if (isValid(getValPtr()))
61      AddToUseList();
62  }
63 
64  ~ValueHandleBase() {
65    if (isValid(getValPtr()))
66      RemoveFromUseList();
67  }
68 
69  Value *operator=(Value *RHS) {
70    if (getValPtr() == RHS)
71      return RHS;
72    if (isValid(getValPtr()))
73      RemoveFromUseList();
74    setValPtr(RHS);
75    if (isValid(getValPtr()))
76      AddToUseList();
77    return RHS;
78  }
79 
80  Value *operator=(const ValueHandleBase &RHS) {
81    if (getValPtr() == RHS.getValPtr())
82      return RHS.getValPtr();
83    if (isValid(getValPtr()))
84      RemoveFromUseList();
85    setValPtr(RHS.getValPtr());
86    if (isValid(getValPtr()))
87      AddToExistingUseList(RHS.getPrevPtr());
88    return getValPtr();
89  }
90 
91  Value *operator->() const { return getValPtr(); }
92  Value &operator*() const {
93    Value *V = getValPtr();
94    assert(V && "Dereferencing deleted ValueHandle")((V && "Dereferencing deleted ValueHandle") ? static_cast
<void> (0) : __assert_fail ("V && \"Dereferencing deleted ValueHandle\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/IR/ValueHandle.h"
, 94, __PRETTY_FUNCTION__));
95    return *V;
96  }
97 
98protected:
99  Value *getValPtr() const { return Val; }
100 
101  static bool isValid(Value *V) {
102    return V &&
37
←
Assuming 'V' is non-null, which participates in a condition later→
62
←
Assuming 'V' is non-null, which participates in a condition later→
103           V != DenseMapInfo<Value *>::getEmptyKey() &&
38
←
Assuming the condition is false→
63
←
Assuming the condition is false→
104           V != DenseMapInfo<Value *>::getTombstoneKey();
105  }
106 
107  /// Remove this ValueHandle from its current use list.
108  void RemoveFromUseList();
109 
110  /// Clear the underlying pointer without clearing the use list.
111  ///
112  /// This should only be used if a derived class has manually removed the
113  /// handle from the use list.
114  void clearValPtr() { setValPtr(nullptr); }
115 
116public:
117  // Callbacks made from Value.
118  static void ValueIsDeleted(Value *V);
119  static void ValueIsRAUWd(Value *Old, Value *New);
120 
121private:
122  // Internal implementation details.
123  ValueHandleBase **getPrevPtr() const { return PrevPair.getPointer(); }
124  HandleBaseKind getKind() const { return PrevPair.getInt(); }
125  void setPrevPtr(ValueHandleBase **Ptr) { PrevPair.setPointer(Ptr); }
126 
127  /// Add this ValueHandle to the use list for V.
128  ///
129  /// List is the address of either the head of the list or a Next node within
130  /// the existing use list.
131  void AddToExistingUseList(ValueHandleBase **List);
132 
133  /// Add this ValueHandle to the use list after Node.
134  void AddToExistingUseListAfter(ValueHandleBase *Node);
135 
136  /// Add this ValueHandle to the use list for V.
137  void AddToUseList();
138};
139 
140/// A nullable Value handle that is nullable.
141///
142/// This is a value handle that points to a value, and nulls itself
143/// out if that value is deleted.
144class WeakVH : public ValueHandleBase {
145public:
146  WeakVH() : ValueHandleBase(Weak) {}
147  WeakVH(Value *P) : ValueHandleBase(Weak, P) {}
148  WeakVH(const WeakVH &RHS)
149      : ValueHandleBase(Weak, RHS) {}
150 
151  WeakVH &operator=(const WeakVH &RHS) = default;
152 
153  Value *operator=(Value *RHS) {
154    return ValueHandleBase::operator=(RHS);
155  }
156  Value *operator=(const ValueHandleBase &RHS) {
157    return ValueHandleBase::operator=(RHS);
158  }
159 
160  operator Value*() const {
161    return getValPtr();
162  }
163};
164 
165// Specialize simplify_type to allow WeakVH to participate in
166// dyn_cast, isa, etc.
167template <> struct simplify_type<WeakVH> {
168  using SimpleType = Value *;
169 
170  static SimpleType getSimplifiedValue(WeakVH &WVH) { return WVH; }
171};
172template <> struct simplify_type<const WeakVH> {
173  using SimpleType = Value *;
174 
175  static SimpleType getSimplifiedValue(const WeakVH &WVH) { return WVH; }
176};
177 
178// Specialize DenseMapInfo to allow WeakVH to participate in DenseMap.
179template <> struct DenseMapInfo<WeakVH> {
180  static inline WeakVH getEmptyKey() {
181    return WeakVH(DenseMapInfo<Value *>::getEmptyKey());
182  }
183 
184  static inline WeakVH getTombstoneKey() {
185    return WeakVH(DenseMapInfo<Value *>::getTombstoneKey());
186  }
187 
188  static unsigned getHashValue(const WeakVH &Val) {
189    return DenseMapInfo<Value *>::getHashValue(Val);
190  }
191 
192  static bool isEqual(const WeakVH &LHS, const WeakVH &RHS) {
193    return DenseMapInfo<Value *>::isEqual(LHS, RHS);
194  }
195};
196 
197/// Value handle that is nullable, but tries to track the Value.
198///
199/// This is a value handle that tries hard to point to a Value, even across
200/// RAUW operations, but will null itself out if the value is destroyed.  this
201/// is useful for advisory sorts of information, but should not be used as the
202/// key of a map (since the map would have to rearrange itself when the pointer
203/// changes).
204class WeakTrackingVH : public ValueHandleBase {
205public:
206  WeakTrackingVH() : ValueHandleBase(WeakTracking) {}
207  WeakTrackingVH(Value *P) : ValueHandleBase(WeakTracking, P) {}
208  WeakTrackingVH(const WeakTrackingVH &RHS)
209      : ValueHandleBase(WeakTracking, RHS) {}
35
←
Calling constructor for 'ValueHandleBase'→
41
←
Returning from constructor for 'ValueHandleBase'→
60
←
Calling constructor for 'ValueHandleBase'→
66
←
Returning from constructor for 'ValueHandleBase'→
210 
211  WeakTrackingVH &operator=(const WeakTrackingVH &RHS) = default;
212 
213  Value *operator=(Value *RHS) {
214    return ValueHandleBase::operator=(RHS);
215  }
216  Value *operator=(const ValueHandleBase &RHS) {
217    return ValueHandleBase::operator=(RHS);
218  }
219 
220  operator Value*() const {
221    return getValPtr();
222  }
223 
224  bool pointsToAliveValue() const {
225    return ValueHandleBase::isValid(getValPtr());
226  }
227};
228 
229// Specialize simplify_type to allow WeakTrackingVH to participate in
230// dyn_cast, isa, etc.
231template <> struct simplify_type<WeakTrackingVH> {
232  using SimpleType = Value *;
233 
234  static SimpleType getSimplifiedValue(WeakTrackingVH &WVH) { return WVH; }
235};
236template <> struct simplify_type<const WeakTrackingVH> {
237  using SimpleType = Value *;
238 
239  static SimpleType getSimplifiedValue(const WeakTrackingVH &WVH) {
240    return WVH;
241  }
242};
243 
244/// Value handle that asserts if the Value is deleted.
245///
246/// This is a Value Handle that points to a value and asserts out if the value
247/// is destroyed while the handle is still live.  This is very useful for
248/// catching dangling pointer bugs and other things which can be non-obvious.
249/// One particularly useful place to use this is as the Key of a map.  Dangling
250/// pointer bugs often lead to really subtle bugs that only occur if another
251/// object happens to get allocated to the same address as the old one.  Using
252/// an AssertingVH ensures that an assert is triggered as soon as the bad
253/// delete occurs.
254///
255/// Note that an AssertingVH handle does *not* follow values across RAUW
256/// operations.  This means that RAUW's need to explicitly update the
257/// AssertingVH's as it moves.  This is required because in non-assert mode this
258/// class turns into a trivial wrapper around a pointer.
259template <typename ValueTy>
260class AssertingVH
261#ifndef NDEBUG
262  : public ValueHandleBase
263#endif
264  {
265  friend struct DenseMapInfo<AssertingVH<ValueTy>>;
266 
267#ifndef NDEBUG
268  Value *getRawValPtr() const { return ValueHandleBase::getValPtr(); }
269  void setRawValPtr(Value *P) { ValueHandleBase::operator=(P); }
270#else
271  Value *ThePtr;
272  Value *getRawValPtr() const { return ThePtr; }
273  void setRawValPtr(Value *P) { ThePtr = P; }
274#endif
275  // Convert a ValueTy*, which may be const, to the raw Value*.
276  static Value *GetAsValue(Value *V) { return V; }
277  static Value *GetAsValue(const Value *V) { return const_cast<Value*>(V); }
278 
279  ValueTy *getValPtr() const { return static_cast<ValueTy *>(getRawValPtr()); }
280  void setValPtr(ValueTy *P) { setRawValPtr(GetAsValue(P)); }
281 
282public:
283#ifndef NDEBUG
284  AssertingVH() : ValueHandleBase(Assert) {}
285  AssertingVH(ValueTy *P) : ValueHandleBase(Assert, GetAsValue(P)) {}
286  AssertingVH(const AssertingVH &RHS) : ValueHandleBase(Assert, RHS) {}
287#else
288  AssertingVH() : ThePtr(nullptr) {}
289  AssertingVH(ValueTy *P) : ThePtr(GetAsValue(P)) {}
290  AssertingVH(const AssertingVH<ValueTy> &) = default;
291#endif
292 
293  operator ValueTy*() const {
294    return getValPtr();
295  }
296 
297  ValueTy *operator=(ValueTy *RHS) {
298    setValPtr(RHS);
299    return getValPtr();
300  }
301  ValueTy *operator=(const AssertingVH<ValueTy> &RHS) {
302    setValPtr(RHS.getValPtr());
303    return getValPtr();
304  }
305 
306  ValueTy *operator->() const { return getValPtr(); }
307  ValueTy &operator*() const { return *getValPtr(); }
308};
309 
310// Treat AssertingVH<T> like T* inside maps. This also allows using find_as()
311// to look up a value without constructing a value handle.
312template<typename T>
313struct DenseMapInfo<AssertingVH<T>> : DenseMapInfo<T *> {};
314 
315/// Value handle that tracks a Value across RAUW.
316///
317/// TrackingVH is designed for situations where a client needs to hold a handle
318/// to a Value (or subclass) across some operations which may move that value,
319/// but should never destroy it or replace it with some unacceptable type.
320///
321/// It is an error to attempt to replace a value with one of a type which is
322/// incompatible with any of its outstanding TrackingVHs.
323///
324/// It is an error to read from a TrackingVH that does not point to a valid
325/// value.  A TrackingVH is said to not point to a valid value if either it
326/// hasn't yet been assigned a value yet or because the value it was tracking
327/// has since been deleted.
328///
329/// Assigning a value to a TrackingVH is always allowed, even if said TrackingVH
330/// no longer points to a valid value.
331template <typename ValueTy> class TrackingVH {
332  WeakTrackingVH InnerHandle;
333 
334public:
335  ValueTy *getValPtr() const {
336    assert(InnerHandle.pointsToAliveValue() &&((InnerHandle.pointsToAliveValue() && "TrackingVH must be non-null and valid on dereference!"
) ? static_cast<void> (0) : __assert_fail ("InnerHandle.pointsToAliveValue() && \"TrackingVH must be non-null and valid on dereference!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/IR/ValueHandle.h"
, 337, __PRETTY_FUNCTION__))
337           "TrackingVH must be non-null and valid on dereference!")((InnerHandle.pointsToAliveValue() && "TrackingVH must be non-null and valid on dereference!"
) ? static_cast<void> (0) : __assert_fail ("InnerHandle.pointsToAliveValue() && \"TrackingVH must be non-null and valid on dereference!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/IR/ValueHandle.h"
, 337, __PRETTY_FUNCTION__));
338 
339    // Check that the value is a member of the correct subclass. We would like
340    // to check this property on assignment for better debugging, but we don't
341    // want to require a virtual interface on this VH. Instead we allow RAUW to
342    // replace this value with a value of an invalid type, and check it here.
343    assert(isa<ValueTy>(InnerHandle) &&((isa<ValueTy>(InnerHandle) && "Tracked Value was replaced by one with an invalid type!"
) ? static_cast<void> (0) : __assert_fail ("isa<ValueTy>(InnerHandle) && \"Tracked Value was replaced by one with an invalid type!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/IR/ValueHandle.h"
, 344, __PRETTY_FUNCTION__))
344           "Tracked Value was replaced by one with an invalid type!")((isa<ValueTy>(InnerHandle) && "Tracked Value was replaced by one with an invalid type!"
) ? static_cast<void> (0) : __assert_fail ("isa<ValueTy>(InnerHandle) && \"Tracked Value was replaced by one with an invalid type!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/IR/ValueHandle.h"
, 344, __PRETTY_FUNCTION__));
345    return cast<ValueTy>(InnerHandle);
346  }
347 
348  void setValPtr(ValueTy *P) {
349    // Assigning to non-valid TrackingVH's are fine so we just unconditionally
350    // assign here.
351    InnerHandle = GetAsValue(P);
352  }
353 
354  // Convert a ValueTy*, which may be const, to the type the base
355  // class expects.
356  static Value *GetAsValue(Value *V) { return V; }
357  static Value *GetAsValue(const Value *V) { return const_cast<Value*>(V); }
358 
359public:
360  TrackingVH() = default;
361  TrackingVH(ValueTy *P) { setValPtr(P); }
362 
363  operator ValueTy*() const {
364    return getValPtr();
365  }
366 
367  ValueTy *operator=(ValueTy *RHS) {
368    setValPtr(RHS);
369    return getValPtr();
370  }
371 
372  ValueTy *operator->() const { return getValPtr(); }
373  ValueTy &operator*() const { return *getValPtr(); }
374};
375 
376/// Value handle with callbacks on RAUW and destruction.
377///
378/// This is a value handle that allows subclasses to define callbacks that run
379/// when the underlying Value has RAUW called on it or is destroyed.  This
380/// class can be used as the key of a map, as long as the user takes it out of
381/// the map before calling setValPtr() (since the map has to rearrange itself
382/// when the pointer changes).  Unlike ValueHandleBase, this class has a vtable.
383class CallbackVH : public ValueHandleBase {
384  virtual void anchor();
385protected:
386  ~CallbackVH() = default;
387  CallbackVH(const CallbackVH &) = default;
388  CallbackVH &operator=(const CallbackVH &) = default;
389 
390  void setValPtr(Value *P) {
391    ValueHandleBase::operator=(P);
392  }
393 
394public:
395  CallbackVH() : ValueHandleBase(Callback) {}
396  CallbackVH(Value *P) : ValueHandleBase(Callback, P) {}
397  CallbackVH(const Value *P) : CallbackVH(const_cast<Value *>(P)) {}
398 
399  operator Value*() const {
400    return getValPtr();
401  }
402 
403  /// Callback for Value destruction.
404  ///
405  /// Called when this->getValPtr() is destroyed, inside ~Value(), so you
406  /// may call any non-virtual Value method on getValPtr(), but no subclass
407  /// methods.  If WeakTrackingVH were implemented as a CallbackVH, it would use
408  /// this
409  /// method to call setValPtr(NULL).  AssertingVH would use this method to
410  /// cause an assertion failure.
411  ///
412  /// All implementations must remove the reference from this object to the
413  /// Value that's being destroyed.
414  virtual void deleted() { setValPtr(nullptr); }
415 
416  /// Callback for Value RAUW.
417  ///
418  /// Called when this->getValPtr()->replaceAllUsesWith(new_value) is called,
419  /// _before_ any of the uses have actually been replaced.  If WeakTrackingVH
420  /// were
421  /// implemented as a CallbackVH, it would use this method to call
422  /// setValPtr(new_value).  AssertingVH would do nothing in this method.
423  virtual void allUsesReplacedWith(Value *) {}
424};
425 
426/// Value handle that poisons itself if the Value is deleted.
427///
428/// This is a Value Handle that points to a value and poisons itself if the
429/// value is destroyed while the handle is still live.  This is very useful for
430/// catching dangling pointer bugs where an \c AssertingVH cannot be used
431/// because the dangling handle needs to outlive the value without ever being
432/// used.
433///
434/// One particularly useful place to use this is as the Key of a map. Dangling
435/// pointer bugs often lead to really subtle bugs that only occur if another
436/// object happens to get allocated to the same address as the old one. Using
437/// a PoisoningVH ensures that an assert is triggered if looking up a new value
438/// in the map finds a handle from the old value.
439///
440/// Note that a PoisoningVH handle does *not* follow values across RAUW
441/// operations. This means that RAUW's need to explicitly update the
442/// PoisoningVH's as it moves. This is required because in non-assert mode this
443/// class turns into a trivial wrapper around a pointer.
444template <typename ValueTy>
445class PoisoningVH
446#ifndef NDEBUG
447    final : public CallbackVH
448#endif
449{
450  friend struct DenseMapInfo<PoisoningVH<ValueTy>>;
451 
452  // Convert a ValueTy*, which may be const, to the raw Value*.
453  static Value *GetAsValue(Value *V) { return V; }
454  static Value *GetAsValue(const Value *V) { return const_cast<Value *>(V); }
455 
456#ifndef NDEBUG
457  /// A flag tracking whether this value has been poisoned.
458  ///
459  /// On delete and RAUW, we leave the value pointer alone so that as a raw
460  /// pointer it produces the same value (and we fit into the same key of
461  /// a hash table, etc), but we poison the handle so that any top-level usage
462  /// will fail.
463  bool Poisoned = false;
464 
465  Value *getRawValPtr() const { return ValueHandleBase::getValPtr(); }
466  void setRawValPtr(Value *P) { ValueHandleBase::operator=(P); }
467 
468  /// Handle deletion by poisoning the handle.
469  void deleted() override {
470    assert(!Poisoned && "Tried to delete an already poisoned handle!")((!Poisoned && "Tried to delete an already poisoned handle!"
) ? static_cast<void> (0) : __assert_fail ("!Poisoned && \"Tried to delete an already poisoned handle!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/IR/ValueHandle.h"
, 470, __PRETTY_FUNCTION__));
471    Poisoned = true;
472    RemoveFromUseList();
473  }
474 
475  /// Handle RAUW by poisoning the handle.
476  void allUsesReplacedWith(Value *) override {
477    assert(!Poisoned && "Tried to RAUW an already poisoned handle!")((!Poisoned && "Tried to RAUW an already poisoned handle!"
) ? static_cast<void> (0) : __assert_fail ("!Poisoned && \"Tried to RAUW an already poisoned handle!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/IR/ValueHandle.h"
, 477, __PRETTY_FUNCTION__));
478    Poisoned = true;
479    RemoveFromUseList();
480  }
481#else // NDEBUG
482  Value *ThePtr = nullptr;
483 
484  Value *getRawValPtr() const { return ThePtr; }
485  void setRawValPtr(Value *P) { ThePtr = P; }
486#endif
487 
488  ValueTy *getValPtr() const {
489    assert(!Poisoned && "Accessed a poisoned value handle!")((!Poisoned && "Accessed a poisoned value handle!") ?
 static_cast<void> (0) : __assert_fail ("!Poisoned && \"Accessed a poisoned value handle!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/IR/ValueHandle.h"
, 489, __PRETTY_FUNCTION__));
490    return static_cast<ValueTy *>(getRawValPtr());
491  }
492  void setValPtr(ValueTy *P) { setRawValPtr(GetAsValue(P)); }
493 
494public:
495  PoisoningVH() = default;
496#ifndef NDEBUG
497  PoisoningVH(ValueTy *P) : CallbackVH(GetAsValue(P)) {}
498  PoisoningVH(const PoisoningVH &RHS)
499      : CallbackVH(RHS), Poisoned(RHS.Poisoned) {}
500 
501  ~PoisoningVH() {
502    if (Poisoned)
503      clearValPtr();
504  }
505 
506  PoisoningVH &operator=(const PoisoningVH &RHS) {
507    if (Poisoned)
508      clearValPtr();
509    CallbackVH::operator=(RHS);
510    Poisoned = RHS.Poisoned;
511    return *this;
512  }
513#else
514  PoisoningVH(ValueTy *P) : ThePtr(GetAsValue(P)) {}
515#endif
516 
517  operator ValueTy *() const { return getValPtr(); }
518 
519  ValueTy *operator->() const { return getValPtr(); }
520  ValueTy &operator*() const { return *getValPtr(); }
521};
522 
523// Specialize DenseMapInfo to allow PoisoningVH to participate in DenseMap.
524template <typename T> struct DenseMapInfo<PoisoningVH<T>> {
525  static inline PoisoningVH<T> getEmptyKey() {
526    PoisoningVH<T> Res;
527    Res.setRawValPtr(DenseMapInfo<Value *>::getEmptyKey());
528    return Res;
529  }
530 
531  static inline PoisoningVH<T> getTombstoneKey() {
532    PoisoningVH<T> Res;
533    Res.setRawValPtr(DenseMapInfo<Value *>::getTombstoneKey());
534    return Res;
535  }
536 
537  static unsigned getHashValue(const PoisoningVH<T> &Val) {
538    return DenseMapInfo<Value *>::getHashValue(Val.getRawValPtr());
539  }
540 
541  static bool isEqual(const PoisoningVH<T> &LHS, const PoisoningVH<T> &RHS) {
542    return DenseMapInfo<Value *>::isEqual(LHS.getRawValPtr(),
543                                          RHS.getRawValPtr());
544  }
545 
546  // Allow lookup by T* via find_as(), without constructing a temporary
547  // value handle.
548 
549  static unsigned getHashValue(const T *Val) {
550    return DenseMapInfo<Value *>::getHashValue(Val);
551  }
552 
553  static bool isEqual(const T *LHS, const PoisoningVH<T> &RHS) {
554    return DenseMapInfo<Value *>::isEqual(LHS, RHS.getRawValPtr());
555  }
556};
557 
558} // end namespace llvm
559 
560#endif // LLVM_IR_VALUEHANDLE_H

←

/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/Support/Casting.h

1//===- llvm/Support/Casting.h - Allow flexible, checked, casts --*- 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 the isa<X>(), cast<X>(), dyn_cast<X>(), cast_or_null<X>(),
10// and dyn_cast_or_null<X>() templates.
11//
12//===----------------------------------------------------------------------===//
13 
14#ifndef LLVM_SUPPORT_CASTING_H
15#define LLVM_SUPPORT_CASTING_H
16 
17#include "llvm/Support/Compiler.h"
18#include "llvm/Support/type_traits.h"
19#include <cassert>
20#include <memory>
21#include <type_traits>
22 
23namespace llvm {
24 
25//===----------------------------------------------------------------------===//
26//                          isa<x> Support Templates
27//===----------------------------------------------------------------------===//
28 
29// Define a template that can be specialized by smart pointers to reflect the
30// fact that they are automatically dereferenced, and are not involved with the
31// template selection process...  the default implementation is a noop.
32//
33template<typename From> struct simplify_type {
34  using SimpleType = From; // The real type this represents...
35 
36  // An accessor to get the real value...
37  static SimpleType &getSimplifiedValue(From &Val) { return Val; }
38};
39 
40template<typename From> struct simplify_type<const From> {
41  using NonConstSimpleType = typename simplify_type<From>::SimpleType;
42  using SimpleType =
43      typename add_const_past_pointer<NonConstSimpleType>::type;
44  using RetType =
45      typename add_lvalue_reference_if_not_pointer<SimpleType>::type;
46 
47  static RetType getSimplifiedValue(const From& Val) {
48    return simplify_type<From>::getSimplifiedValue(const_cast<From&>(Val));
49  }
50};
51 
52// The core of the implementation of isa<X> is here; To and From should be
53// the names of classes.  This template can be specialized to customize the
54// implementation of isa<> without rewriting it from scratch.
55template <typename To, typename From, typename Enabler = void>
56struct isa_impl {
57  static inline bool doit(const From &Val) {
58    return To::classof(&Val);
59  }
60};
61 
62/// Always allow upcasts, and perform no dynamic check for them.
63template <typename To, typename From>
64struct isa_impl<To, From, std::enable_if_t<std::is_base_of<To, From>::value>> {
65  static inline bool doit(const From &) { return true; }
66};
67 
68template <typename To, typename From> struct isa_impl_cl {
69  static inline bool doit(const From &Val) {
70    return isa_impl<To, From>::doit(Val);
71  }
72};
73 
74template <typename To, typename From> struct isa_impl_cl<To, const From> {
75  static inline bool doit(const From &Val) {
76    return isa_impl<To, From>::doit(Val);
77  }
78};
79 
80template <typename To, typename From>
81struct isa_impl_cl<To, const std::unique_ptr<From>> {
82  static inline bool doit(const std::unique_ptr<From> &Val) {
83    assert(Val && "isa<> used on a null pointer")((Val && "isa<> used on a null pointer") ? static_cast
<void> (0) : __assert_fail ("Val && \"isa<> used on a null pointer\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/Support/Casting.h"
, 83, __PRETTY_FUNCTION__));
84    return isa_impl_cl<To, From>::doit(*Val);
85  }
86};
87 
88template <typename To, typename From> struct isa_impl_cl<To, From*> {
89  static inline bool doit(const From *Val) {
90    assert(Val && "isa<> used on a null pointer")((Val && "isa<> used on a null pointer") ? static_cast
<void> (0) : __assert_fail ("Val && \"isa<> used on a null pointer\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/Support/Casting.h"
, 90, __PRETTY_FUNCTION__));
91    return isa_impl<To, From>::doit(*Val);
92  }
93};
94 
95template <typename To, typename From> struct isa_impl_cl<To, From*const> {
96  static inline bool doit(const From *Val) {
97    assert(Val && "isa<> used on a null pointer")((Val && "isa<> used on a null pointer") ? static_cast
<void> (0) : __assert_fail ("Val && \"isa<> used on a null pointer\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/Support/Casting.h"
, 97, __PRETTY_FUNCTION__));
98    return isa_impl<To, From>::doit(*Val);
99  }
100};
101 
102template <typename To, typename From> struct isa_impl_cl<To, const From*> {
103  static inline bool doit(const From *Val) {
104    assert(Val && "isa<> used on a null pointer")((Val && "isa<> used on a null pointer") ? static_cast
<void> (0) : __assert_fail ("Val && \"isa<> used on a null pointer\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/Support/Casting.h"
, 104, __PRETTY_FUNCTION__));
105    return isa_impl<To, From>::doit(*Val);
106  }
107};
108 
109template <typename To, typename From> struct isa_impl_cl<To, const From*const> {
110  static inline bool doit(const From *Val) {
111    assert(Val && "isa<> used on a null pointer")((Val && "isa<> used on a null pointer") ? static_cast
<void> (0) : __assert_fail ("Val && \"isa<> used on a null pointer\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/Support/Casting.h"
, 111, __PRETTY_FUNCTION__));
112    return isa_impl<To, From>::doit(*Val);
113  }
114};
115 
116template<typename To, typename From, typename SimpleFrom>
117struct isa_impl_wrap {
118  // When From != SimplifiedType, we can simplify the type some more by using
119  // the simplify_type template.
120  static bool doit(const From &Val) {
121    return isa_impl_wrap<To, SimpleFrom,
122      typename simplify_type<SimpleFrom>::SimpleType>::doit(
123                          simplify_type<const From>::getSimplifiedValue(Val));
124  }
125};
126 
127template<typename To, typename FromTy>
128struct isa_impl_wrap<To, FromTy, FromTy> {
129  // When From == SimpleType, we are as simple as we are going to get.
130  static bool doit(const FromTy &Val) {
131    return isa_impl_cl<To,FromTy>::doit(Val);
132  }
133};
134 
135// isa<X> - Return true if the parameter to the template is an instance of one
136// of the template type arguments.  Used like this:
137//
138//  if (isa<Type>(myVal)) { ... }
139//  if (isa<Type0, Type1, Type2>(myVal)) { ... }
140//
141template <class X, class Y> LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isa(const Y &Val) {
142  return isa_impl_wrap<X, const Y,
143                       typename simplify_type<const Y>::SimpleType>::doit(Val);
144}
145 
146template <typename First, typename Second, typename... Rest, typename Y>
147LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isa(const Y &Val) {
148  return isa<First>(Val) || isa<Second, Rest...>(Val);
149}
150 
151// isa_and_nonnull<X> - Functionally identical to isa, except that a null value
152// is accepted.
153//
154template <typename... X, class Y>
155LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isa_and_nonnull(const Y &Val) {
156  if (!Val)
157    return false;
158  return isa<X...>(Val);
159}
160 
161//===----------------------------------------------------------------------===//
162//                          cast<x> Support Templates
163//===----------------------------------------------------------------------===//
164 
165template<class To, class From> struct cast_retty;
166 
167// Calculate what type the 'cast' function should return, based on a requested
168// type of To and a source type of From.
169template<class To, class From> struct cast_retty_impl {
170  using ret_type = To &;       // Normal case, return Ty&
171};
172template<class To, class From> struct cast_retty_impl<To, const From> {
173  using ret_type = const To &; // Normal case, return Ty&
174};
175 
176template<class To, class From> struct cast_retty_impl<To, From*> {
177  using ret_type = To *;       // Pointer arg case, return Ty*
178};
179 
180template<class To, class From> struct cast_retty_impl<To, const From*> {
181  using ret_type = const To *; // Constant pointer arg case, return const Ty*
182};
183 
184template<class To, class From> struct cast_retty_impl<To, const From*const> {
185  using ret_type = const To *; // Constant pointer arg case, return const Ty*
186};
187 
188template <class To, class From>
189struct cast_retty_impl<To, std::unique_ptr<From>> {
190private:
191  using PointerType = typename cast_retty_impl<To, From *>::ret_type;
192  using ResultType = std::remove_pointer_t<PointerType>;
193 
194public:
195  using ret_type = std::unique_ptr<ResultType>;
196};
197 
198template<class To, class From, class SimpleFrom>
199struct cast_retty_wrap {
200  // When the simplified type and the from type are not the same, use the type
201  // simplifier to reduce the type, then reuse cast_retty_impl to get the
202  // resultant type.
203  using ret_type = typename cast_retty<To, SimpleFrom>::ret_type;
204};
205 
206template<class To, class FromTy>
207struct cast_retty_wrap<To, FromTy, FromTy> {
208  // When the simplified type is equal to the from type, use it directly.
209  using ret_type = typename cast_retty_impl<To,FromTy>::ret_type;
210};
211 
212template<class To, class From>
213struct cast_retty {
214  using ret_type = typename cast_retty_wrap<
215      To, From, typename simplify_type<From>::SimpleType>::ret_type;
216};
217 
218// Ensure the non-simple values are converted using the simplify_type template
219// that may be specialized by smart pointers...
220//
221template<class To, class From, class SimpleFrom> struct cast_convert_val {
222  // This is not a simple type, use the template to simplify it...
223  static typename cast_retty<To, From>::ret_type doit(From &Val) {
224    return cast_convert_val<To, SimpleFrom,
225      typename simplify_type<SimpleFrom>::SimpleType>::doit(
226                          simplify_type<From>::getSimplifiedValue(Val));
227  }
228};
229 
230template<class To, class FromTy> struct cast_convert_val<To,FromTy,FromTy> {
231  // This _is_ a simple type, just cast it.
232  static typename cast_retty<To, FromTy>::ret_type doit(const FromTy &Val) {
233    typename cast_retty<To, FromTy>::ret_type Res2
234     = (typename cast_retty<To, FromTy>::ret_type)const_cast<FromTy&>(Val);
235    return Res2;
236  }
237};
238 
239template <class X> struct is_simple_type {
240  static const bool value =
241      std::is_same<X, typename simplify_type<X>::SimpleType>::value;
242};
243 
244// cast<X> - Return the argument parameter cast to the specified type.  This
245// casting operator asserts that the type is correct, so it does not return null
246// on failure.  It does not allow a null argument (use cast_or_null for that).
247// It is typically used like this:
248//
249//  cast<Instruction>(myVal)->getParent()
250//
251template <class X, class Y>
252inline std::enable_if_t<!is_simple_type<Y>::value,
253                        typename cast_retty<X, const Y>::ret_type>
254cast(const Y &Val) {
255  assert(isa<X>(Val) && "cast<Ty>() argument of incompatible type!")((isa<X>(Val) && "cast<Ty>() argument of incompatible type!"
) ? static_cast<void> (0) : __assert_fail ("isa<X>(Val) && \"cast<Ty>() argument of incompatible type!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/Support/Casting.h"
, 255, __PRETTY_FUNCTION__));
256  return cast_convert_val<
257      X, const Y, typename simplify_type<const Y>::SimpleType>::doit(Val);
258}
259 
260template <class X, class Y>
261inline typename cast_retty<X, Y>::ret_type cast(Y &Val) {
262  assert(isa<X>(Val) && "cast<Ty>() argument of incompatible type!")((isa<X>(Val) && "cast<Ty>() argument of incompatible type!"
) ? static_cast<void> (0) : __assert_fail ("isa<X>(Val) && \"cast<Ty>() argument of incompatible type!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/Support/Casting.h"
, 262, __PRETTY_FUNCTION__));
48
←
Assuming 'Val' is a 'CallInst'→
49
←
'?' condition is true→
73
←
Assuming 'Val' is a 'CallInst'→
74
←
'?' condition is true→
263  return cast_convert_val<X, Y,
50
←
Returning pointer, which participates in a condition later→
75
←
Returning pointer, which participates in a condition later→
264                          typename simplify_type<Y>::SimpleType>::doit(Val);
265}
266 
267template <class X, class Y>
268inline typename cast_retty<X, Y *>::ret_type cast(Y *Val) {
269  assert(isa<X>(Val) && "cast<Ty>() argument of incompatible type!")((isa<X>(Val) && "cast<Ty>() argument of incompatible type!"
) ? static_cast<void> (0) : __assert_fail ("isa<X>(Val) && \"cast<Ty>() argument of incompatible type!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/Support/Casting.h"
, 269, __PRETTY_FUNCTION__));
270  return cast_convert_val<X, Y*,
271                          typename simplify_type<Y*>::SimpleType>::doit(Val);
272}
273 
274template <class X, class Y>
275inline typename cast_retty<X, std::unique_ptr<Y>>::ret_type
276cast(std::unique_ptr<Y> &&Val) {
277  assert(isa<X>(Val.get()) && "cast<Ty>() argument of incompatible type!")((isa<X>(Val.get()) && "cast<Ty>() argument of incompatible type!"
) ? static_cast<void> (0) : __assert_fail ("isa<X>(Val.get()) && \"cast<Ty>() argument of incompatible type!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/Support/Casting.h"
, 277, __PRETTY_FUNCTION__));
278  using ret_type = typename cast_retty<X, std::unique_ptr<Y>>::ret_type;
279  return ret_type(
280      cast_convert_val<X, Y *, typename simplify_type<Y *>::SimpleType>::doit(
281          Val.release()));
282}
283 
284// cast_or_null<X> - Functionally identical to cast, except that a null value is
285// accepted.
286//
287template <class X, class Y>
288LLVM_NODISCARD[[clang::warn_unused_result]] inline std::enable_if_t<
289    !is_simple_type<Y>::value, typename cast_retty<X, const Y>::ret_type>
290cast_or_null(const Y &Val) {
291  if (!Val)
292    return nullptr;
293  assert(isa<X>(Val) && "cast_or_null<Ty>() argument of incompatible type!")((isa<X>(Val) && "cast_or_null<Ty>() argument of incompatible type!"
) ? static_cast<void> (0) : __assert_fail ("isa<X>(Val) && \"cast_or_null<Ty>() argument of incompatible type!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/Support/Casting.h"
, 293, __PRETTY_FUNCTION__));
294  return cast<X>(Val);
295}
296 
297template <class X, class Y>
298LLVM_NODISCARD[[clang::warn_unused_result]] inline std::enable_if_t<!is_simple_type<Y>::value,
299                                       typename cast_retty<X, Y>::ret_type>
300cast_or_null(Y &Val) {
301  if (!Val)
302    return nullptr;
303  assert(isa<X>(Val) && "cast_or_null<Ty>() argument of incompatible type!")((isa<X>(Val) && "cast_or_null<Ty>() argument of incompatible type!"
) ? static_cast<void> (0) : __assert_fail ("isa<X>(Val) && \"cast_or_null<Ty>() argument of incompatible type!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/Support/Casting.h"
, 303, __PRETTY_FUNCTION__));
304  return cast<X>(Val);
305}
306 
307template <class X, class Y>
308LLVM_NODISCARD[[clang::warn_unused_result]] inline typename cast_retty<X, Y *>::ret_type
309cast_or_null(Y *Val) {
310  if (!Val) return nullptr;
311  assert(isa<X>(Val) && "cast_or_null<Ty>() argument of incompatible type!")((isa<X>(Val) && "cast_or_null<Ty>() argument of incompatible type!"
) ? static_cast<void> (0) : __assert_fail ("isa<X>(Val) && \"cast_or_null<Ty>() argument of incompatible type!\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include/llvm/Support/Casting.h"
, 311, __PRETTY_FUNCTION__));
312  return cast<X>(Val);
313}
314 
315template <class X, class Y>
316inline typename cast_retty<X, std::unique_ptr<Y>>::ret_type
317cast_or_null(std::unique_ptr<Y> &&Val) {
318  if (!Val)
319    return nullptr;
320  return cast<X>(std::move(Val));
321}
322 
323// dyn_cast<X> - Return the argument parameter cast to the specified type.  This
324// casting operator returns null if the argument is of the wrong type, so it can
325// be used to test for a type as well as cast if successful.  This should be
326// used in the context of an if statement like this:
327//
328//  if (const Instruction *I = dyn_cast<Instruction>(myVal)) { ... }
329//
330 
331template <class X, class Y>
332LLVM_NODISCARD[[clang::warn_unused_result]] inline std::enable_if_t<
333    !is_simple_type<Y>::value, typename cast_retty<X, const Y>::ret_type>
334dyn_cast(const Y &Val) {
335  return isa<X>(Val) ? cast<X>(Val) : nullptr;
336}
337 
338template <class X, class Y>
339LLVM_NODISCARD[[clang::warn_unused_result]] inline typename cast_retty<X, Y>::ret_type dyn_cast(Y &Val) {
340  return isa<X>(Val) ? cast<X>(Val) : nullptr;
341}
342 
343template <class X, class Y>
344LLVM_NODISCARD[[clang::warn_unused_result]] inline typename cast_retty<X, Y *>::ret_type dyn_cast(Y *Val) {
345  return isa<X>(Val) ? cast<X>(Val) : nullptr;
346}
347 
348// dyn_cast_or_null<X> - Functionally identical to dyn_cast, except that a null
349// value is accepted.
350//
351template <class X, class Y>
352LLVM_NODISCARD[[clang::warn_unused_result]] inline std::enable_if_t<
353    !is_simple_type<Y>::value, typename cast_retty<X, const Y>::ret_type>
354dyn_cast_or_null(const Y &Val) {
355  return (Val && isa<X>(Val)) ? cast<X>(Val) : nullptr;
356}
357 
358template <class X, class Y>
359LLVM_NODISCARD[[clang::warn_unused_result]] inline std::enable_if_t<!is_simple_type<Y>::value,
360                                       typename cast_retty<X, Y>::ret_type>
361dyn_cast_or_null(Y &Val) {
362  return (Val && isa<X>(Val)) ? cast<X>(Val) : nullptr;
45
←
Assuming 'Val' is a 'CallInst'→
46
←
'?' condition is true→
47
←
Calling 'cast<llvm::CallInst, llvm::AssumptionCache::ResultElem>'→
51
←
Returning from 'cast<llvm::CallInst, llvm::AssumptionCache::ResultElem>'→
52
←
Returning pointer, which participates in a condition later→
70
←
Assuming 'Val' is a 'CallInst'→
71
←
'?' condition is true→
72
←
Calling 'cast<llvm::CallInst, llvm::AssumptionCache::ResultElem>'→
76
←
Returning from 'cast<llvm::CallInst, llvm::AssumptionCache::ResultElem>'→
77
←
Returning pointer, which participates in a condition later→
363}
364 
365template <class X, class Y>
366LLVM_NODISCARD[[clang::warn_unused_result]] inline typename cast_retty<X, Y *>::ret_type
367dyn_cast_or_null(Y *Val) {
368  return (Val && isa<X>(Val)) ? cast<X>(Val) : nullptr;
369}
370 
371// unique_dyn_cast<X> - Given a unique_ptr<Y>, try to return a unique_ptr<X>,
372// taking ownership of the input pointer iff isa<X>(Val) is true.  If the
373// cast is successful, From refers to nullptr on exit and the casted value
374// is returned.  If the cast is unsuccessful, the function returns nullptr
375// and From is unchanged.
376template <class X, class Y>
377LLVM_NODISCARD[[clang::warn_unused_result]] inline auto unique_dyn_cast(std::unique_ptr<Y> &Val)
378    -> decltype(cast<X>(Val)) {
379  if (!isa<X>(Val))
380    return nullptr;
381  return cast<X>(std::move(Val));
382}
383 
384template <class X, class Y>
385LLVM_NODISCARD[[clang::warn_unused_result]] inline auto unique_dyn_cast(std::unique_ptr<Y> &&Val) {
386  return unique_dyn_cast<X, Y>(Val);
387}
388 
389// dyn_cast_or_null<X> - Functionally identical to unique_dyn_cast, except that
390// a null value is accepted.
391template <class X, class Y>
392LLVM_NODISCARD[[clang::warn_unused_result]] inline auto unique_dyn_cast_or_null(std::unique_ptr<Y> &Val)
393    -> decltype(cast<X>(Val)) {
394  if (!Val)
395    return nullptr;
396  return unique_dyn_cast<X, Y>(Val);
397}
398 
399template <class X, class Y>
400LLVM_NODISCARD[[clang::warn_unused_result]] inline auto unique_dyn_cast_or_null(std::unique_ptr<Y> &&Val) {
401  return unique_dyn_cast_or_null<X, Y>(Val);
402}
403 
404} // end namespace llvm
405 
406#endif // LLVM_SUPPORT_CASTING_H