/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

Bug Summary

File:	llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
Warning:	line 1822, column 25 Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name DeadStoreElimination.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 -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-11/lib/clang/11.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/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-11/lib/clang/11.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-11~++20200309111110+2c36c23f347/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-03-09-184146-41876-1 -x c++ /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

→

1//===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===//
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 a trivial dead store elimination that only considers
10// basic-block local redundant stores.
11//
12// FIXME: This should eventually be extended to be a post-dominator tree
13// traversal.  Doing so would be pretty trivial.
14//
15//===----------------------------------------------------------------------===//

17#include "llvm/Transforms/Scalar/DeadStoreElimination.h"
18#include "llvm/ADT/APInt.h"
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/ADT/MapVector.h"
21#include "llvm/ADT/SetVector.h"
22#include "llvm/ADT/SmallPtrSet.h"
23#include "llvm/ADT/SmallVector.h"
24#include "llvm/ADT/Statistic.h"
25#include "llvm/ADT/StringRef.h"
26#include "llvm/Analysis/AliasAnalysis.h"
27#include "llvm/Analysis/CaptureTracking.h"
28#include "llvm/Analysis/GlobalsModRef.h"
29#include "llvm/Analysis/MemoryBuiltins.h"
30#include "llvm/Analysis/MemoryDependenceAnalysis.h"
31#include "llvm/Analysis/MemoryLocation.h"
32#include "llvm/Analysis/MemorySSA.h"
33#include "llvm/Analysis/MemorySSAUpdater.h"
34#include "llvm/Analysis/PostDominators.h"
35#include "llvm/Analysis/TargetLibraryInfo.h"
36#include "llvm/Analysis/ValueTracking.h"
37#include "llvm/IR/Argument.h"
38#include "llvm/IR/BasicBlock.h"
39#include "llvm/IR/CallSite.h"
40#include "llvm/IR/Constant.h"
41#include "llvm/IR/Constants.h"
42#include "llvm/IR/DataLayout.h"
43#include "llvm/IR/Dominators.h"
44#include "llvm/IR/Function.h"
45#include "llvm/IR/InstIterator.h"
46#include "llvm/IR/InstrTypes.h"
47#include "llvm/IR/Instruction.h"
48#include "llvm/IR/Instructions.h"
49#include "llvm/IR/IntrinsicInst.h"
50#include "llvm/IR/Intrinsics.h"
51#include "llvm/IR/LLVMContext.h"
52#include "llvm/IR/Module.h"
53#include "llvm/IR/PassManager.h"
54#include "llvm/IR/Value.h"
55#include "llvm/InitializePasses.h"
56#include "llvm/Pass.h"
57#include "llvm/Support/Casting.h"
58#include "llvm/Support/CommandLine.h"
59#include "llvm/Support/Debug.h"
60#include "llvm/Support/DebugCounter.h"
61#include "llvm/Support/ErrorHandling.h"
62#include "llvm/Support/MathExtras.h"
63#include "llvm/Support/raw_ostream.h"
64#include "llvm/Transforms/Scalar.h"
65#include "llvm/Transforms/Utils/Local.h"
66#include <algorithm>
67#include <cassert>
68#include <cstddef>
69#include <cstdint>
70#include <iterator>
71#include <map>
72#include <utility>

74using namespace llvm;

76#define DEBUG_TYPE"dse" "dse"

78STATISTIC(NumRedundantStores, "Number of redundant stores deleted")static llvm::Statistic NumRedundantStores = {"dse", "NumRedundantStores"
, "Number of redundant stores deleted"};
79STATISTIC(NumFastStores, "Number of stores deleted")static llvm::Statistic NumFastStores = {"dse", "NumFastStores"
, "Number of stores deleted"};
80STATISTIC(NumFastOther, "Number of other instrs removed")static llvm::Statistic NumFastOther = {"dse", "NumFastOther",
 "Number of other instrs removed"};
81STATISTIC(NumCompletePartials, "Number of stores dead by later partials")static llvm::Statistic NumCompletePartials = {"dse", "NumCompletePartials"
, "Number of stores dead by later partials"};
82STATISTIC(NumModifiedStores, "Number of stores modified")static llvm::Statistic NumModifiedStores = {"dse", "NumModifiedStores"
, "Number of stores modified"};

84DEBUG_COUNTER(MemorySSACounter, "dse-memoryssa",static const unsigned MemorySSACounter = DebugCounter::registerCounter
("dse-memoryssa", "Controls which MemoryDefs are eliminated."
)
            "Controls which MemoryDefs are eliminated.")static const unsigned MemorySSACounter = DebugCounter::registerCounter
("dse-memoryssa", "Controls which MemoryDefs are eliminated."
);

87static cl::opt<bool>
88EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking",
cl::init(true), cl::Hidden,
cl::desc("Enable partial-overwrite tracking in DSE"));

92static cl::opt<bool>
93EnablePartialStoreMerging("enable-dse-partial-store-merging",
cl::init(true), cl::Hidden,
cl::desc("Enable partial store merging in DSE"));

97static cl::opt<bool>
  EnableMemorySSA("enable-dse-memoryssa", cl::init(false), cl::Hidden,
                  cl::desc("Use the new MemorySSA-backed DSE."));

101static cl::opt<unsigned>
  MemorySSAScanLimit("dse-memoryssa-scanlimit", cl::init(100), cl::Hidden,
                     cl::desc("The number of memory instructions to scan for "
                              "dead store elimination (default = 100)"));

106static cl::opt<unsigned> MemorySSADefsPerBlockLimit(
  "dse-memoryssa-defs-per-block-limit", cl::init(5000), cl::Hidden,
  cl::desc("The number of MemoryDefs we consider as candidates to eliminated "
           "other stores per basic block (default = 5000)"));

111//===----------------------------------------------------------------------===//
112// Helper functions
113//===----------------------------------------------------------------------===//
114using OverlapIntervalsTy = std::map<int64_t, int64_t>;
115using InstOverlapIntervalsTy = DenseMap<Instruction *, OverlapIntervalsTy>;

117/// Delete this instruction.  Before we do, go through and zero out all the
118/// operands of this instruction.  If any of them become dead, delete them and
119/// the computation tree that feeds them.
120/// If ValueSet is non-null, remove any deleted instructions from it as well.
121static void
122deleteDeadInstruction(Instruction *I, BasicBlock::iterator *BBI,
                    MemoryDependenceResults &MD, const TargetLibraryInfo &TLI,
                    InstOverlapIntervalsTy &IOL,
                    MapVector<Instruction *, bool> &ThrowableInst,
                    SmallSetVector<const Value *, 16> *ValueSet = nullptr) {
SmallVector<Instruction*, 32> NowDeadInsts;

NowDeadInsts.push_back(I);
--NumFastOther;

// Keeping the iterator straight is a pain, so we let this routine tell the
// caller what the next instruction is after we're done mucking about.
BasicBlock::iterator NewIter = *BBI;

// Before we touch this instruction, remove it from memdep!
do {
  Instruction *DeadInst = NowDeadInsts.pop_back_val();
  // Mark the DeadInst as dead in the list of throwable instructions.
  auto It = ThrowableInst.find(DeadInst);
  if (It != ThrowableInst.end())
    ThrowableInst[It->first] = false;
  ++NumFastOther;

  // Try to preserve debug information attached to the dead instruction.
  salvageDebugInfo(*DeadInst);

  // This instruction is dead, zap it, in stages.  Start by removing it from
  // MemDep, which needs to know the operands and needs it to be in the
  // function.
  MD.removeInstruction(DeadInst);

  for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
    Value *Op = DeadInst->getOperand(op);
    DeadInst->setOperand(op, nullptr);

    // If this operand just became dead, add it to the NowDeadInsts list.
    if (!Op->use_empty()) continue;

    if (Instruction *OpI = dyn_cast<Instruction>(Op))
      if (isInstructionTriviallyDead(OpI, &TLI))
        NowDeadInsts.push_back(OpI);
  }

  if (ValueSet) ValueSet->remove(DeadInst);
  IOL.erase(DeadInst);

  if (NewIter == DeadInst->getIterator())
    NewIter = DeadInst->eraseFromParent();
  else
    DeadInst->eraseFromParent();
} while (!NowDeadInsts.empty());
*BBI = NewIter;
// Pop dead entries from back of ThrowableInst till we find an alive entry.
while (!ThrowableInst.empty() && !ThrowableInst.back().second)
  ThrowableInst.pop_back();
177}

179/// Does this instruction write some memory?  This only returns true for things
180/// that we can analyze with other helpers below.
181static bool hasAnalyzableMemoryWrite(Instruction *I,
                                   const TargetLibraryInfo &TLI) {
if (isa<StoreInst>(I))
  return true;
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
  switch (II->getIntrinsicID()) {
  default:
    return false;
  case Intrinsic::memset:
  case Intrinsic::memmove:
  case Intrinsic::memcpy:
  case Intrinsic::memcpy_element_unordered_atomic:
  case Intrinsic::memmove_element_unordered_atomic:
  case Intrinsic::memset_element_unordered_atomic:
  case Intrinsic::init_trampoline:
  case Intrinsic::lifetime_end:
    return true;
  }
}
if (auto CS = CallSite(I)) {
  if (Function *F = CS.getCalledFunction()) {
    LibFunc LF;
    if (TLI.getLibFunc(*F, LF) && TLI.has(LF)) {
      switch (LF) {
      case LibFunc_strcpy:
      case LibFunc_strncpy:
      case LibFunc_strcat:
      case LibFunc_strncat:
        return true;
      default:
        return false;
      }
    }
  }
}
return false;
217}

219/// Return a Location stored to by the specified instruction. If isRemovable
220/// returns true, this function and getLocForRead completely describe the memory
221/// operations for this instruction.
222static MemoryLocation getLocForWrite(Instruction *Inst) {

if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
  return MemoryLocation::get(SI);

if (auto *MI = dyn_cast<AnyMemIntrinsic>(Inst)) {
  // memcpy/memmove/memset.
  MemoryLocation Loc = MemoryLocation::getForDest(MI);
  return Loc;
}

if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
  switch (II->getIntrinsicID()) {
  default:
    return MemoryLocation(); // Unhandled intrinsic.
  case Intrinsic::init_trampoline:
    return MemoryLocation(II->getArgOperand(0));
  case Intrinsic::lifetime_end: {
    uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue();
    return MemoryLocation(II->getArgOperand(1), Len);
  }
  }
}
if (auto CS = CallSite(Inst))
  // All the supported TLI functions so far happen to have dest as their
  // first argument.
  return MemoryLocation(CS.getArgument(0));
return MemoryLocation();
250}

252/// Return the location read by the specified "hasAnalyzableMemoryWrite"
253/// instruction if any.
254static MemoryLocation getLocForRead(Instruction *Inst,
                                  const TargetLibraryInfo &TLI) {
assert(hasAnalyzableMemoryWrite(Inst, TLI) && "Unknown instruction case")((hasAnalyzableMemoryWrite(Inst, TLI) && "Unknown instruction case"
) ? static_cast<void> (0) : __assert_fail ("hasAnalyzableMemoryWrite(Inst, TLI) && \"Unknown instruction case\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 256, __PRETTY_FUNCTION__));

// The only instructions that both read and write are the mem transfer
// instructions (memcpy/memmove).
if (auto *MTI = dyn_cast<AnyMemTransferInst>(Inst))
  return MemoryLocation::getForSource(MTI);
return MemoryLocation();
263}

265/// If the value of this instruction and the memory it writes to is unused, may
266/// we delete this instruction?
267static bool isRemovable(Instruction *I) {
// Don't remove volatile/atomic stores.
if (StoreInst *SI = dyn_cast<StoreInst>(I))
  return SI->isUnordered();

if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
  switch (II->getIntrinsicID()) {
  default: llvm_unreachable("doesn't pass 'hasAnalyzableMemoryWrite' predicate")::llvm::llvm_unreachable_internal("doesn't pass 'hasAnalyzableMemoryWrite' predicate"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 274);
  case Intrinsic::lifetime_end:
    // Never remove dead lifetime_end's, e.g. because it is followed by a
    // free.
    return false;
  case Intrinsic::init_trampoline:
    // Always safe to remove init_trampoline.
    return true;
  case Intrinsic::memset:
  case Intrinsic::memmove:
  case Intrinsic::memcpy:
    // Don't remove volatile memory intrinsics.
    return !cast<MemIntrinsic>(II)->isVolatile();
  case Intrinsic::memcpy_element_unordered_atomic:
  case Intrinsic::memmove_element_unordered_atomic:
  case Intrinsic::memset_element_unordered_atomic:
    return true;
  }
}

// note: only get here for calls with analyzable writes - i.e. libcalls
if (auto CS = CallSite(I))
  return CS.getInstruction()->use_empty();

return false;
299}

301/// Returns true if the end of this instruction can be safely shortened in
302/// length.
303static bool isShortenableAtTheEnd(Instruction *I) {
// Don't shorten stores for now
if (isa<StoreInst>(I))
  return false;

if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
  switch (II->getIntrinsicID()) {
    default: return false;
    case Intrinsic::memset:
    case Intrinsic::memcpy:
    case Intrinsic::memcpy_element_unordered_atomic:
    case Intrinsic::memset_element_unordered_atomic:
      // Do shorten memory intrinsics.
      // FIXME: Add memmove if it's also safe to transform.
      return true;
  }
}

// Don't shorten libcalls calls for now.

return false;
324}

326/// Returns true if the beginning of this instruction can be safely shortened
327/// in length.
328static bool isShortenableAtTheBeginning(Instruction *I) {
// FIXME: Handle only memset for now. Supporting memcpy/memmove should be
// easily done by offsetting the source address.
return isa<AnyMemSetInst>(I);
332}

334/// Return the pointer that is being written to.
335static Value *getStoredPointerOperand(Instruction *I) {
//TODO: factor this to reuse getLocForWrite
MemoryLocation Loc = getLocForWrite(I);
assert(Loc.Ptr &&((Loc.Ptr && "unable to find pointer written for analyzable instruction?"
) ? static_cast<void> (0) : __assert_fail ("Loc.Ptr && \"unable to find pointer written for analyzable instruction?\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 339, __PRETTY_FUNCTION__))
       "unable to find pointer written for analyzable instruction?")((Loc.Ptr && "unable to find pointer written for analyzable instruction?"
) ? static_cast<void> (0) : __assert_fail ("Loc.Ptr && \"unable to find pointer written for analyzable instruction?\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 339, __PRETTY_FUNCTION__));
// TODO: most APIs don't expect const Value *
return const_cast<Value*>(Loc.Ptr);
342}

344static uint64_t getPointerSize(const Value *V, const DataLayout &DL,
                             const TargetLibraryInfo &TLI,
                             const Function *F) {
uint64_t Size;
ObjectSizeOpts Opts;
Opts.NullIsUnknownSize = NullPointerIsDefined(F);

if (getObjectSize(V, Size, DL, &TLI, Opts))
  return Size;
return MemoryLocation::UnknownSize;
354}

356namespace {

358enum OverwriteResult {
OW_Begin,
OW_Complete,
OW_End,
OW_PartialEarlierWithFullLater,
OW_Unknown
364};

366} // end anonymous namespace

368/// Return 'OW_Complete' if a store to the 'Later' location completely
369/// overwrites a store to the 'Earlier' location, 'OW_End' if the end of the
370/// 'Earlier' location is completely overwritten by 'Later', 'OW_Begin' if the
371/// beginning of the 'Earlier' location is overwritten by 'Later'.
372/// 'OW_PartialEarlierWithFullLater' means that an earlier (big) store was
373/// overwritten by a latter (smaller) store which doesn't write outside the big
374/// store's memory locations. Returns 'OW_Unknown' if nothing can be determined.
375static OverwriteResult isOverwrite(const MemoryLocation &Later,
                                 const MemoryLocation &Earlier,
                                 const DataLayout &DL,
                                 const TargetLibraryInfo &TLI,
                                 int64_t &EarlierOff, int64_t &LaterOff,
                                 Instruction *DepWrite,
                                 InstOverlapIntervalsTy &IOL,
                                 AliasAnalysis &AA,
                                 const Function *F) {
// FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
// get imprecise values here, though (except for unknown sizes).
if (!Later.Size.isPrecise() || !Earlier.Size.isPrecise())
  return OW_Unknown;

const uint64_t LaterSize = Later.Size.getValue();
const uint64_t EarlierSize = Earlier.Size.getValue();

const Value *P1 = Earlier.Ptr->stripPointerCasts();
const Value *P2 = Later.Ptr->stripPointerCasts();

// If the start pointers are the same, we just have to compare sizes to see if
// the later store was larger than the earlier store.
if (P1 == P2 || AA.isMustAlias(P1, P2)) {
  // Make sure that the Later size is >= the Earlier size.
  if (LaterSize >= EarlierSize)
    return OW_Complete;
}

// Check to see if the later store is to the entire object (either a global,
// an alloca, or a byval/inalloca argument).  If so, then it clearly
// overwrites any other store to the same object.
const Value *UO1 = GetUnderlyingObject(P1, DL),
            *UO2 = GetUnderlyingObject(P2, DL);

// If we can't resolve the same pointers to the same object, then we can't
// analyze them at all.
if (UO1 != UO2)
  return OW_Unknown;

// If the "Later" store is to a recognizable object, get its size.
uint64_t ObjectSize = getPointerSize(UO2, DL, TLI, F);
if (ObjectSize != MemoryLocation::UnknownSize)
  if (ObjectSize == LaterSize && ObjectSize >= EarlierSize)
    return OW_Complete;

// Okay, we have stores to two completely different pointers.  Try to
// decompose the pointer into a "base + constant_offset" form.  If the base
// pointers are equal, then we can reason about the two stores.
EarlierOff = 0;
LaterOff = 0;
const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, DL);
const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, DL);

// If the base pointers still differ, we have two completely different stores.
if (BP1 != BP2)
  return OW_Unknown;

// The later store completely overlaps the earlier store if:
//
// 1. Both start at the same offset and the later one's size is greater than
//    or equal to the earlier one's, or
//
//      |--earlier--|
//      |--   later   --|
//
// 2. The earlier store has an offset greater than the later offset, but which
//    still lies completely within the later store.
//
//        |--earlier--|
//    |-----  later  ------|
//
// We have to be careful here as *Off is signed while *.Size is unsigned.
if (EarlierOff >= LaterOff &&
    LaterSize >= EarlierSize &&
    uint64_t(EarlierOff - LaterOff) + EarlierSize <= LaterSize)
  return OW_Complete;

// We may now overlap, although the overlap is not complete. There might also
// be other incomplete overlaps, and together, they might cover the complete
// earlier write.
// Note: The correctness of this logic depends on the fact that this function
// is not even called providing DepWrite when there are any intervening reads.
if (EnablePartialOverwriteTracking &&
    LaterOff < int64_t(EarlierOff + EarlierSize) &&
    int64_t(LaterOff + LaterSize) >= EarlierOff) {

  // Insert our part of the overlap into the map.
  auto &IM = IOL[DepWrite];
  LLVM_DEBUG(dbgs() << "DSE: Partial overwrite: Earlier [" << EarlierOffdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite: Earlier ["
 << EarlierOff << ", " << int64_t(EarlierOff
 + EarlierSize) << ") Later [" << LaterOff <<
 ", " << int64_t(LaterOff + LaterSize) << ")\n"; }
 } while (false)
                    << ", " << int64_t(EarlierOff + EarlierSize)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite: Earlier ["
 << EarlierOff << ", " << int64_t(EarlierOff
 + EarlierSize) << ") Later [" << LaterOff <<
 ", " << int64_t(LaterOff + LaterSize) << ")\n"; }
 } while (false)
                    << ") Later [" << LaterOff << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite: Earlier ["
 << EarlierOff << ", " << int64_t(EarlierOff
 + EarlierSize) << ") Later [" << LaterOff <<
 ", " << int64_t(LaterOff + LaterSize) << ")\n"; }
 } while (false)
                    << int64_t(LaterOff + LaterSize) << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite: Earlier ["
 << EarlierOff << ", " << int64_t(EarlierOff
 + EarlierSize) << ") Later [" << LaterOff <<
 ", " << int64_t(LaterOff + LaterSize) << ")\n"; }
 } while (false);

  // Make sure that we only insert non-overlapping intervals and combine
  // adjacent intervals. The intervals are stored in the map with the ending
  // offset as the key (in the half-open sense) and the starting offset as
  // the value.
  int64_t LaterIntStart = LaterOff, LaterIntEnd = LaterOff + LaterSize;

  // Find any intervals ending at, or after, LaterIntStart which start
  // before LaterIntEnd.
  auto ILI = IM.lower_bound(LaterIntStart);
  if (ILI != IM.end() && ILI->second <= LaterIntEnd) {
    // This existing interval is overlapped with the current store somewhere
    // in [LaterIntStart, LaterIntEnd]. Merge them by erasing the existing
    // intervals and adjusting our start and end.
    LaterIntStart = std::min(LaterIntStart, ILI->second);
    LaterIntEnd = std::max(LaterIntEnd, ILI->first);
    ILI = IM.erase(ILI);

    // Continue erasing and adjusting our end in case other previous
    // intervals are also overlapped with the current store.
    //
    // |--- ealier 1 ---|  |--- ealier 2 ---|
    //     |------- later---------|
    //
    while (ILI != IM.end() && ILI->second <= LaterIntEnd) {
      assert(ILI->second > LaterIntStart && "Unexpected interval")((ILI->second > LaterIntStart && "Unexpected interval"
) ? static_cast<void> (0) : __assert_fail ("ILI->second > LaterIntStart && \"Unexpected interval\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 492, __PRETTY_FUNCTION__));
      LaterIntEnd = std::max(LaterIntEnd, ILI->first);
      ILI = IM.erase(ILI);
    }
  }

  IM[LaterIntEnd] = LaterIntStart;

  ILI = IM.begin();
  if (ILI->second <= EarlierOff &&
      ILI->first >= int64_t(EarlierOff + EarlierSize)) {
    LLVM_DEBUG(dbgs() << "DSE: Full overwrite from partials: Earlier ["do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Full overwrite from partials: Earlier ["
 << EarlierOff << ", " << int64_t(EarlierOff
 + EarlierSize) << ") Composite Later [" << ILI->
second << ", " << ILI->first << ")\n"; }
 } while (false)
                      << EarlierOff << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Full overwrite from partials: Earlier ["
 << EarlierOff << ", " << int64_t(EarlierOff
 + EarlierSize) << ") Composite Later [" << ILI->
second << ", " << ILI->first << ")\n"; }
 } while (false)
                      << int64_t(EarlierOff + EarlierSize)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Full overwrite from partials: Earlier ["
 << EarlierOff << ", " << int64_t(EarlierOff
 + EarlierSize) << ") Composite Later [" << ILI->
second << ", " << ILI->first << ")\n"; }
 } while (false)
                      << ") Composite Later [" << ILI->second << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Full overwrite from partials: Earlier ["
 << EarlierOff << ", " << int64_t(EarlierOff
 + EarlierSize) << ") Composite Later [" << ILI->
second << ", " << ILI->first << ")\n"; }
 } while (false)
                      << ILI->first << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Full overwrite from partials: Earlier ["
 << EarlierOff << ", " << int64_t(EarlierOff
 + EarlierSize) << ") Composite Later [" << ILI->
second << ", " << ILI->first << ")\n"; }
 } while (false);
    ++NumCompletePartials;
    return OW_Complete;
  }
}

// Check for an earlier store which writes to all the memory locations that
// the later store writes to.
if (EnablePartialStoreMerging && LaterOff >= EarlierOff &&
    int64_t(EarlierOff + EarlierSize) > LaterOff &&
    uint64_t(LaterOff - EarlierOff) + LaterSize <= EarlierSize) {
  LLVM_DEBUG(dbgs() << "DSE: Partial overwrite an earlier load ["do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite an earlier load ["
 << EarlierOff << ", " << int64_t(EarlierOff
 + EarlierSize) << ") by a later store [" << LaterOff
 << ", " << int64_t(LaterOff + LaterSize) <<
 ")\n"; } } while (false)
                    << EarlierOff << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite an earlier load ["
 << EarlierOff << ", " << int64_t(EarlierOff
 + EarlierSize) << ") by a later store [" << LaterOff
 << ", " << int64_t(LaterOff + LaterSize) <<
 ")\n"; } } while (false)
                    << int64_t(EarlierOff + EarlierSize)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite an earlier load ["
 << EarlierOff << ", " << int64_t(EarlierOff
 + EarlierSize) << ") by a later store [" << LaterOff
 << ", " << int64_t(LaterOff + LaterSize) <<
 ")\n"; } } while (false)
                    << ") by a later store [" << LaterOff << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite an earlier load ["
 << EarlierOff << ", " << int64_t(EarlierOff
 + EarlierSize) << ") by a later store [" << LaterOff
 << ", " << int64_t(LaterOff + LaterSize) <<
 ")\n"; } } while (false)
                    << int64_t(LaterOff + LaterSize) << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite an earlier load ["
 << EarlierOff << ", " << int64_t(EarlierOff
 + EarlierSize) << ") by a later store [" << LaterOff
 << ", " << int64_t(LaterOff + LaterSize) <<
 ")\n"; } } while (false);
  // TODO: Maybe come up with a better name?
  return OW_PartialEarlierWithFullLater;
}

// Another interesting case is if the later store overwrites the end of the
// earlier store.
//
//      |--earlier--|
//                |--   later   --|
//
// In this case we may want to trim the size of earlier to avoid generating
// writes to addresses which will definitely be overwritten later
if (!EnablePartialOverwriteTracking &&
    (LaterOff > EarlierOff && LaterOff < int64_t(EarlierOff + EarlierSize) &&
     int64_t(LaterOff + LaterSize) >= int64_t(EarlierOff + EarlierSize)))
  return OW_End;

// Finally, we also need to check if the later store overwrites the beginning
// of the earlier store.
//
//                |--earlier--|
//      |--   later   --|
//
// In this case we may want to move the destination address and trim the size
// of earlier to avoid generating writes to addresses which will definitely
// be overwritten later.
if (!EnablePartialOverwriteTracking &&
    (LaterOff <= EarlierOff && int64_t(LaterOff + LaterSize) > EarlierOff)) {
  assert(int64_t(LaterOff + LaterSize) < int64_t(EarlierOff + EarlierSize) &&((int64_t(LaterOff + LaterSize) < int64_t(EarlierOff + EarlierSize
) && "Expect to be handled as OW_Complete") ? static_cast
<void> (0) : __assert_fail ("int64_t(LaterOff + LaterSize) < int64_t(EarlierOff + EarlierSize) && \"Expect to be handled as OW_Complete\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 552, __PRETTY_FUNCTION__))
         "Expect to be handled as OW_Complete")((int64_t(LaterOff + LaterSize) < int64_t(EarlierOff + EarlierSize
) && "Expect to be handled as OW_Complete") ? static_cast
<void> (0) : __assert_fail ("int64_t(LaterOff + LaterSize) < int64_t(EarlierOff + EarlierSize) && \"Expect to be handled as OW_Complete\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 552, __PRETTY_FUNCTION__));
  return OW_Begin;
}
// Otherwise, they don't completely overlap.
return OW_Unknown;
557}

559/// If 'Inst' might be a self read (i.e. a noop copy of a
560/// memory region into an identical pointer) then it doesn't actually make its
561/// input dead in the traditional sense.  Consider this case:
562///
563///   memmove(A <- B)
564///   memmove(A <- A)
565///
566/// In this case, the second store to A does not make the first store to A dead.
567/// The usual situation isn't an explicit A<-A store like this (which can be
568/// trivially removed) but a case where two pointers may alias.
569///
570/// This function detects when it is unsafe to remove a dependent instruction
571/// because the DSE inducing instruction may be a self-read.
572static bool isPossibleSelfRead(Instruction *Inst,
                             const MemoryLocation &InstStoreLoc,
                             Instruction *DepWrite,
                             const TargetLibraryInfo &TLI,
                             AliasAnalysis &AA) {
// Self reads can only happen for instructions that read memory.  Get the
// location read.
MemoryLocation InstReadLoc = getLocForRead(Inst, TLI);
if (!InstReadLoc.Ptr)
  return false; // Not a reading instruction.

// If the read and written loc obviously don't alias, it isn't a read.
if (AA.isNoAlias(InstReadLoc, InstStoreLoc))
  return false;

if (isa<AnyMemCpyInst>(Inst)) {
  // LLVM's memcpy overlap semantics are not fully fleshed out (see PR11763)
  // but in practice memcpy(A <- B) either means that A and B are disjoint or
  // are equal (i.e. there are not partial overlaps).  Given that, if we have:
  //
  //   memcpy/memmove(A <- B)  // DepWrite
  //   memcpy(A <- B)  // Inst
  //
  // with Inst reading/writing a >= size than DepWrite, we can reason as
  // follows:
  //
  //   - If A == B then both the copies are no-ops, so the DepWrite can be
  //     removed.
  //   - If A != B then A and B are disjoint locations in Inst.  Since
  //     Inst.size >= DepWrite.size A and B are disjoint in DepWrite too.
  //     Therefore DepWrite can be removed.
  MemoryLocation DepReadLoc = getLocForRead(DepWrite, TLI);

  if (DepReadLoc.Ptr && AA.isMustAlias(InstReadLoc.Ptr, DepReadLoc.Ptr))
    return false;
}

// If DepWrite doesn't read memory or if we can't prove it is a must alias,
// then it can't be considered dead.
return true;
612}

614/// Returns true if the memory which is accessed by the second instruction is not
615/// modified between the first and the second instruction.
616/// Precondition: Second instruction must be dominated by the first
617/// instruction.
618static bool memoryIsNotModifiedBetween(Instruction *FirstI,
                                     Instruction *SecondI,
                                     AliasAnalysis *AA,
                                     const DataLayout &DL,
                                     DominatorTree *DT) {
// Do a backwards scan through the CFG from SecondI to FirstI. Look for
// instructions which can modify the memory location accessed by SecondI.
//
// While doing the walk keep track of the address to check. It might be
// different in different basic blocks due to PHI translation.
using BlockAddressPair = std::pair<BasicBlock *, PHITransAddr>;
SmallVector<BlockAddressPair, 16> WorkList;
// Keep track of the address we visited each block with. Bail out if we
// visit a block with different addresses.
DenseMap<BasicBlock *, Value *> Visited;

BasicBlock::iterator FirstBBI(FirstI);
++FirstBBI;
BasicBlock::iterator SecondBBI(SecondI);
BasicBlock *FirstBB = FirstI->getParent();
BasicBlock *SecondBB = SecondI->getParent();
MemoryLocation MemLoc = MemoryLocation::get(SecondI);
auto *MemLocPtr = const_cast<Value *>(MemLoc.Ptr);

// Start checking the SecondBB.
WorkList.push_back(
    std::make_pair(SecondBB, PHITransAddr(MemLocPtr, DL, nullptr)));
bool isFirstBlock = true;

// Check all blocks going backward until we reach the FirstBB.
while (!WorkList.empty()) {
  BlockAddressPair Current = WorkList.pop_back_val();
  BasicBlock *B = Current.first;
  PHITransAddr &Addr = Current.second;
  Value *Ptr = Addr.getAddr();

  // Ignore instructions before FirstI if this is the FirstBB.
  BasicBlock::iterator BI = (B == FirstBB ? FirstBBI : B->begin());

  BasicBlock::iterator EI;
  if (isFirstBlock) {
    // Ignore instructions after SecondI if this is the first visit of SecondBB.
    assert(B == SecondBB && "first block is not the store block")((B == SecondBB && "first block is not the store block"
) ? static_cast<void> (0) : __assert_fail ("B == SecondBB && \"first block is not the store block\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 660, __PRETTY_FUNCTION__));
    EI = SecondBBI;
    isFirstBlock = false;
  } else {
    // It's not SecondBB or (in case of a loop) the second visit of SecondBB.
    // In this case we also have to look at instructions after SecondI.
    EI = B->end();
  }
  for (; BI != EI; ++BI) {
    Instruction *I = &*BI;
    if (I->mayWriteToMemory() && I != SecondI)
      if (isModSet(AA->getModRefInfo(I, MemLoc.getWithNewPtr(Ptr))))
        return false;
  }
  if (B != FirstBB) {
    assert(B != &FirstBB->getParent()->getEntryBlock() &&((B != &FirstBB->getParent()->getEntryBlock() &&
 "Should not hit the entry block because SI must be dominated by LI"
) ? static_cast<void> (0) : __assert_fail ("B != &FirstBB->getParent()->getEntryBlock() && \"Should not hit the entry block because SI must be dominated by LI\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 676, __PRETTY_FUNCTION__))
        "Should not hit the entry block because SI must be dominated by LI")((B != &FirstBB->getParent()->getEntryBlock() &&
 "Should not hit the entry block because SI must be dominated by LI"
) ? static_cast<void> (0) : __assert_fail ("B != &FirstBB->getParent()->getEntryBlock() && \"Should not hit the entry block because SI must be dominated by LI\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 676, __PRETTY_FUNCTION__));
    for (auto PredI = pred_begin(B), PE = pred_end(B); PredI != PE; ++PredI) {
      PHITransAddr PredAddr = Addr;
      if (PredAddr.NeedsPHITranslationFromBlock(B)) {
        if (!PredAddr.IsPotentiallyPHITranslatable())
          return false;
        if (PredAddr.PHITranslateValue(B, *PredI, DT, false))
          return false;
      }
      Value *TranslatedPtr = PredAddr.getAddr();
      auto Inserted = Visited.insert(std::make_pair(*PredI, TranslatedPtr));
      if (!Inserted.second) {
        // We already visited this block before. If it was with a different
        // address - bail out!
        if (TranslatedPtr != Inserted.first->second)
          return false;
        // ... otherwise just skip it.
        continue;
      }
      WorkList.push_back(std::make_pair(*PredI, PredAddr));
    }
  }
}
return true;
700}

702/// Find all blocks that will unconditionally lead to the block BB and append
703/// them to F.
704static void findUnconditionalPreds(SmallVectorImpl<BasicBlock *> &Blocks,
                                 BasicBlock *BB, DominatorTree *DT) {
for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
  BasicBlock *Pred = *I;
  if (Pred == BB) continue;
  Instruction *PredTI = Pred->getTerminator();
  if (PredTI->getNumSuccessors() != 1)
    continue;

  if (DT->isReachableFromEntry(Pred))
    Blocks.push_back(Pred);
}
716}

718/// Handle frees of entire structures whose dependency is a store
719/// to a field of that structure.
720static bool handleFree(CallInst *F, AliasAnalysis *AA,
                     MemoryDependenceResults *MD, DominatorTree *DT,
                     const TargetLibraryInfo *TLI,
                     InstOverlapIntervalsTy &IOL,
                     MapVector<Instruction *, bool> &ThrowableInst) {
bool MadeChange = false;

MemoryLocation Loc = MemoryLocation(F->getOperand(0));
SmallVector<BasicBlock *, 16> Blocks;
Blocks.push_back(F->getParent());
const DataLayout &DL = F->getModule()->getDataLayout();

while (!Blocks.empty()) {
  BasicBlock *BB = Blocks.pop_back_val();
  Instruction *InstPt = BB->getTerminator();
  if (BB == F->getParent()) InstPt = F;

  MemDepResult Dep =
      MD->getPointerDependencyFrom(Loc, false, InstPt->getIterator(), BB);
  while (Dep.isDef() || Dep.isClobber()) {
    Instruction *Dependency = Dep.getInst();
    if (!hasAnalyzableMemoryWrite(Dependency, *TLI) ||
        !isRemovable(Dependency))
      break;

    Value *DepPointer =
        GetUnderlyingObject(getStoredPointerOperand(Dependency), DL);

    // Check for aliasing.
    if (!AA->isMustAlias(F->getArgOperand(0), DepPointer))
      break;

    LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store to soon to be freed memory:\n  DEAD: "
 << *Dependency << '\n'; } } while (false)
        dbgs() << "DSE: Dead Store to soon to be freed memory:\n  DEAD: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store to soon to be freed memory:\n  DEAD: "
 << *Dependency << '\n'; } } while (false)
               << *Dependency << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store to soon to be freed memory:\n  DEAD: "
 << *Dependency << '\n'; } } while (false);

    // DCE instructions only used to calculate that store.
    BasicBlock::iterator BBI(Dependency);
    deleteDeadInstruction(Dependency, &BBI, *MD, *TLI, IOL,
                          ThrowableInst);
    ++NumFastStores;
    MadeChange = true;

    // Inst's old Dependency is now deleted. Compute the next dependency,
    // which may also be dead, as in
    //    s[0] = 0;
    //    s[1] = 0; // This has just been deleted.
    //    free(s);
    Dep = MD->getPointerDependencyFrom(Loc, false, BBI, BB);
  }

  if (Dep.isNonLocal())
    findUnconditionalPreds(Blocks, BB, DT);
}

return MadeChange;
776}

778/// Check to see if the specified location may alias any of the stack objects in
779/// the DeadStackObjects set. If so, they become live because the location is
780/// being loaded.
781static void removeAccessedObjects(const MemoryLocation &LoadedLoc,
                                SmallSetVector<const Value *, 16> &DeadStackObjects,
                                const DataLayout &DL, AliasAnalysis *AA,
                                const TargetLibraryInfo *TLI,
                                const Function *F) {
const Value *UnderlyingPointer = GetUnderlyingObject(LoadedLoc.Ptr, DL);

// A constant can't be in the dead pointer set.
if (isa<Constant>(UnderlyingPointer))
  return;

// If the kill pointer can be easily reduced to an alloca, don't bother doing
// extraneous AA queries.
if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) {
  DeadStackObjects.remove(UnderlyingPointer);
  return;
}

// Remove objects that could alias LoadedLoc.
DeadStackObjects.remove_if([&](const Value *I) {
  // See if the loaded location could alias the stack location.
  MemoryLocation StackLoc(I, getPointerSize(I, DL, *TLI, F));
  return !AA->isNoAlias(StackLoc, LoadedLoc);
});
805}

807/// Remove dead stores to stack-allocated locations in the function end block.
808/// Ex:
809/// %A = alloca i32
810/// ...
811/// store i32 1, i32* %A
812/// ret void
813static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA,
                         MemoryDependenceResults *MD,
                         const TargetLibraryInfo *TLI,
                         InstOverlapIntervalsTy &IOL,
                         MapVector<Instruction *, bool> &ThrowableInst) {
bool MadeChange = false;

// Keep track of all of the stack objects that are dead at the end of the
// function.
SmallSetVector<const Value*, 16> DeadStackObjects;

// Find all of the alloca'd pointers in the entry block.
BasicBlock &Entry = BB.getParent()->front();
for (Instruction &I : Entry) {
  if (isa<AllocaInst>(&I))
    DeadStackObjects.insert(&I);

  // Okay, so these are dead heap objects, but if the pointer never escapes
  // then it's leaked by this function anyways.
  else if (isAllocLikeFn(&I, TLI) && !PointerMayBeCaptured(&I, true, true))
    DeadStackObjects.insert(&I);
}

// Treat byval or inalloca arguments the same, stores to them are dead at the
// end of the function.
for (Argument &AI : BB.getParent()->args())
  if (AI.hasByValOrInAllocaAttr())
    DeadStackObjects.insert(&AI);

const DataLayout &DL = BB.getModule()->getDataLayout();

// Scan the basic block backwards
for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
  --BBI;

  // If we find a store, check to see if it points into a dead stack value.
  if (hasAnalyzableMemoryWrite(&*BBI, *TLI) && isRemovable(&*BBI)) {
    // See through pointer-to-pointer bitcasts
    SmallVector<const Value *, 4> Pointers;
    GetUnderlyingObjects(getStoredPointerOperand(&*BBI), Pointers, DL);

    // Stores to stack values are valid candidates for removal.
    bool AllDead = true;
    for (const Value *Pointer : Pointers)
      if (!DeadStackObjects.count(Pointer)) {
        AllDead = false;
        break;
      }

    if (AllDead) {
      Instruction *Dead = &*BBI;

      LLVM_DEBUG(dbgs() << "DSE: Dead Store at End of Block:\n  DEAD: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n  DEAD: "
 << *Dead << "\n  Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
 E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
                        << *Dead << "\n  Objects: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n  DEAD: "
 << *Dead << "\n  Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
 E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
                 for (SmallVectorImpl<const Value *>::iterator I =do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n  DEAD: "
 << *Dead << "\n  Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
 E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
                          Pointers.begin(),do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n  DEAD: "
 << *Dead << "\n  Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
 E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
                      E = Pointers.end();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n  DEAD: "
 << *Dead << "\n  Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
 E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
                      I != E; ++I) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n  DEAD: "
 << *Dead << "\n  Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
 E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
                   dbgs() << **I;do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n  DEAD: "
 << *Dead << "\n  Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
 E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
                   if (std::next(I) != E)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n  DEAD: "
 << *Dead << "\n  Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
 E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
                     dbgs() << ", ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n  DEAD: "
 << *Dead << "\n  Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
 E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
                 } dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n  DEAD: "
 << *Dead << "\n  Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
 E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false)
                 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Dead Store at End of Block:\n  DEAD: "
 << *Dead << "\n  Objects: "; for (SmallVectorImpl
<const Value *>::iterator I = Pointers.begin(), E = Pointers
.end(); I != E; ++I) { dbgs() << **I; if (std::next(I) !=
 E) dbgs() << ", "; } dbgs() << '\n'; } } while (
false);

      // DCE instructions only used to calculate that store.
      deleteDeadInstruction(Dead, &BBI, *MD, *TLI, IOL, ThrowableInst,
                            &DeadStackObjects);
      ++NumFastStores;
      MadeChange = true;
      continue;
    }
  }

  // Remove any dead non-memory-mutating instructions.
  if (isInstructionTriviallyDead(&*BBI, TLI)) {
    LLVM_DEBUG(dbgs() << "DSE: Removing trivially dead instruction:\n  DEAD: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Removing trivially dead instruction:\n  DEAD: "
 << *&*BBI << '\n'; } } while (false)
                      << *&*BBI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Removing trivially dead instruction:\n  DEAD: "
 << *&*BBI << '\n'; } } while (false);
    deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, IOL, ThrowableInst,
                          &DeadStackObjects);
    ++NumFastOther;
    MadeChange = true;
    continue;
  }

  if (isa<AllocaInst>(BBI)) {
    // Remove allocas from the list of dead stack objects; there can't be
    // any references before the definition.
    DeadStackObjects.remove(&*BBI);
    continue;
  }

  if (auto *Call = dyn_cast<CallBase>(&*BBI)) {
    // Remove allocation function calls from the list of dead stack objects;
    // there can't be any references before the definition.
    if (isAllocLikeFn(&*BBI, TLI))
      DeadStackObjects.remove(&*BBI);

    // If this call does not access memory, it can't be loading any of our
    // pointers.
    if (AA->doesNotAccessMemory(Call))
      continue;

    // If the call might load from any of our allocas, then any store above
    // the call is live.
    DeadStackObjects.remove_if([&](const Value *I) {
      // See if the call site touches the value.
      return isRefSet(AA->getModRefInfo(
          Call, I, getPointerSize(I, DL, *TLI, BB.getParent())));
    });

    // If all of the allocas were clobbered by the call then we're not going
    // to find anything else to process.
    if (DeadStackObjects.empty())
      break;

    continue;
  }

  // We can remove the dead stores, irrespective of the fence and its ordering
  // (release/acquire/seq_cst). Fences only constraints the ordering of
  // already visible stores, it does not make a store visible to other
  // threads. So, skipping over a fence does not change a store from being
  // dead.
  if (isa<FenceInst>(*BBI))
    continue;

  MemoryLocation LoadedLoc;

  // If we encounter a use of the pointer, it is no longer considered dead
  if (LoadInst *L = dyn_cast<LoadInst>(BBI)) {
    if (!L->isUnordered()) // Be conservative with atomic/volatile load
      break;
    LoadedLoc = MemoryLocation::get(L);
  } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
    LoadedLoc = MemoryLocation::get(V);
  } else if (!BBI->mayReadFromMemory()) {
    // Instruction doesn't read memory.  Note that stores that weren't removed
    // above will hit this case.
    continue;
  } else {
    // Unknown inst; assume it clobbers everything.
    break;
  }

  // Remove any allocas from the DeadPointer set that are loaded, as this
  // makes any stores above the access live.
  removeAccessedObjects(LoadedLoc, DeadStackObjects, DL, AA, TLI, BB.getParent());

  // If all of the allocas were clobbered by the access then we're not going
  // to find anything else to process.
  if (DeadStackObjects.empty())
    break;
}

return MadeChange;
968}

970static bool tryToShorten(Instruction *EarlierWrite, int64_t &EarlierOffset,
                       int64_t &EarlierSize, int64_t LaterOffset,
                       int64_t LaterSize, bool IsOverwriteEnd) {
// TODO: base this on the target vector size so that if the earlier
// store was too small to get vector writes anyway then its likely
// a good idea to shorten it
// Power of 2 vector writes are probably always a bad idea to optimize
// as any store/memset/memcpy is likely using vector instructions so
// shortening it to not vector size is likely to be slower
auto *EarlierIntrinsic = cast<AnyMemIntrinsic>(EarlierWrite);
unsigned EarlierWriteAlign = EarlierIntrinsic->getDestAlignment();
if (!IsOverwriteEnd)
  LaterOffset = int64_t(LaterOffset + LaterSize);

if (!(isPowerOf2_64(LaterOffset) && EarlierWriteAlign <= LaterOffset) &&
    !((EarlierWriteAlign != 0) && LaterOffset % EarlierWriteAlign == 0))
  return false;

int64_t NewLength = IsOverwriteEnd
                        ? LaterOffset - EarlierOffset
                        : EarlierSize - (LaterOffset - EarlierOffset);

if (auto *AMI = dyn_cast<AtomicMemIntrinsic>(EarlierWrite)) {
  // When shortening an atomic memory intrinsic, the newly shortened
  // length must remain an integer multiple of the element size.
  const uint32_t ElementSize = AMI->getElementSizeInBytes();
  if (0 != NewLength % ElementSize)
    return false;
}

LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  OW "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n  OW " <<
 (IsOverwriteEnd ? "END" : "BEGIN") << ": " << *EarlierWrite
 << "\n  KILLER (offset " << LaterOffset <<
 ", " << EarlierSize << ")\n"; } } while (false)
                  << (IsOverwriteEnd ? "END" : "BEGIN") << ": "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n  OW " <<
 (IsOverwriteEnd ? "END" : "BEGIN") << ": " << *EarlierWrite
 << "\n  KILLER (offset " << LaterOffset <<
 ", " << EarlierSize << ")\n"; } } while (false)
                  << *EarlierWrite << "\n  KILLER (offset " << LaterOffsetdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n  OW " <<
 (IsOverwriteEnd ? "END" : "BEGIN") << ": " << *EarlierWrite
 << "\n  KILLER (offset " << LaterOffset <<
 ", " << EarlierSize << ")\n"; } } while (false)
                  << ", " << EarlierSize << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n  OW " <<
 (IsOverwriteEnd ? "END" : "BEGIN") << ": " << *EarlierWrite
 << "\n  KILLER (offset " << LaterOffset <<
 ", " << EarlierSize << ")\n"; } } while (false);

Value *EarlierWriteLength = EarlierIntrinsic->getLength();
Value *TrimmedLength =
    ConstantInt::get(EarlierWriteLength->getType(), NewLength);
EarlierIntrinsic->setLength(TrimmedLength);

EarlierSize = NewLength;
if (!IsOverwriteEnd) {
  int64_t OffsetMoved = (LaterOffset - EarlierOffset);
  Value *Indices[1] = {
      ConstantInt::get(EarlierWriteLength->getType(), OffsetMoved)};
  GetElementPtrInst *NewDestGEP = GetElementPtrInst::CreateInBounds(
      EarlierIntrinsic->getRawDest()->getType()->getPointerElementType(),
      EarlierIntrinsic->getRawDest(), Indices, "", EarlierWrite);
  NewDestGEP->setDebugLoc(EarlierIntrinsic->getDebugLoc());
  EarlierIntrinsic->setDest(NewDestGEP);
  EarlierOffset = EarlierOffset + OffsetMoved;
}
return true;
1023}

1025static bool tryToShortenEnd(Instruction *EarlierWrite,
                          OverlapIntervalsTy &IntervalMap,
                          int64_t &EarlierStart, int64_t &EarlierSize) {
if (IntervalMap.empty() || !isShortenableAtTheEnd(EarlierWrite))
  return false;

OverlapIntervalsTy::iterator OII = --IntervalMap.end();
int64_t LaterStart = OII->second;
int64_t LaterSize = OII->first - LaterStart;

if (LaterStart > EarlierStart && LaterStart < EarlierStart + EarlierSize &&
    LaterStart + LaterSize >= EarlierStart + EarlierSize) {
  if (tryToShorten(EarlierWrite, EarlierStart, EarlierSize, LaterStart,
                   LaterSize, true)) {
    IntervalMap.erase(OII);
    return true;
  }
}
return false;
1044}

1046static bool tryToShortenBegin(Instruction *EarlierWrite,
                            OverlapIntervalsTy &IntervalMap,
                            int64_t &EarlierStart, int64_t &EarlierSize) {
if (IntervalMap.empty() || !isShortenableAtTheBeginning(EarlierWrite))
  return false;

OverlapIntervalsTy::iterator OII = IntervalMap.begin();
int64_t LaterStart = OII->second;
int64_t LaterSize = OII->first - LaterStart;

if (LaterStart <= EarlierStart && LaterStart + LaterSize > EarlierStart) {
  assert(LaterStart + LaterSize < EarlierStart + EarlierSize &&((LaterStart + LaterSize < EarlierStart + EarlierSize &&
 "Should have been handled as OW_Complete") ? static_cast<
void> (0) : __assert_fail ("LaterStart + LaterSize < EarlierStart + EarlierSize && \"Should have been handled as OW_Complete\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1058, __PRETTY_FUNCTION__))
         "Should have been handled as OW_Complete")((LaterStart + LaterSize < EarlierStart + EarlierSize &&
 "Should have been handled as OW_Complete") ? static_cast<
void> (0) : __assert_fail ("LaterStart + LaterSize < EarlierStart + EarlierSize && \"Should have been handled as OW_Complete\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1058, __PRETTY_FUNCTION__));
  if (tryToShorten(EarlierWrite, EarlierStart, EarlierSize, LaterStart,
                   LaterSize, false)) {
    IntervalMap.erase(OII);
    return true;
  }
}
return false;
1066}

1068static bool removePartiallyOverlappedStores(AliasAnalysis *AA,
                                          const DataLayout &DL,
                                          InstOverlapIntervalsTy &IOL) {
bool Changed = false;
for (auto OI : IOL) {
  Instruction *EarlierWrite = OI.first;
  MemoryLocation Loc = getLocForWrite(EarlierWrite);
  assert(isRemovable(EarlierWrite) && "Expect only removable instruction")((isRemovable(EarlierWrite) && "Expect only removable instruction"
) ? static_cast<void> (0) : __assert_fail ("isRemovable(EarlierWrite) && \"Expect only removable instruction\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1075, __PRETTY_FUNCTION__));

  const Value *Ptr = Loc.Ptr->stripPointerCasts();
  int64_t EarlierStart = 0;
  int64_t EarlierSize = int64_t(Loc.Size.getValue());
  GetPointerBaseWithConstantOffset(Ptr, EarlierStart, DL);
  OverlapIntervalsTy &IntervalMap = OI.second;
  Changed |=
      tryToShortenEnd(EarlierWrite, IntervalMap, EarlierStart, EarlierSize);
  if (IntervalMap.empty())
    continue;
  Changed |=
      tryToShortenBegin(EarlierWrite, IntervalMap, EarlierStart, EarlierSize);
}
return Changed;
1090}

1092static bool eliminateNoopStore(Instruction *Inst, BasicBlock::iterator &BBI,
                             AliasAnalysis *AA, MemoryDependenceResults *MD,
                             const DataLayout &DL,
                             const TargetLibraryInfo *TLI,
                             InstOverlapIntervalsTy &IOL,
                             MapVector<Instruction *, bool> &ThrowableInst,
                             DominatorTree *DT) {
// Must be a store instruction.
StoreInst *SI = dyn_cast<StoreInst>(Inst);
if (!SI)
  return false;

// If we're storing the same value back to a pointer that we just loaded from,
// then the store can be removed.
if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
  if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
      isRemovable(SI) &&
      memoryIsNotModifiedBetween(DepLoad, SI, AA, DL, DT)) {

    LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Store Of Load from same pointer:\n  LOAD: "
 << *DepLoad << "\n  STORE: " << *SI <<
 '\n'; } } while (false)
        dbgs() << "DSE: Remove Store Of Load from same pointer:\n  LOAD: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Store Of Load from same pointer:\n  LOAD: "
 << *DepLoad << "\n  STORE: " << *SI <<
 '\n'; } } while (false)
               << *DepLoad << "\n  STORE: " << *SI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Store Of Load from same pointer:\n  LOAD: "
 << *DepLoad << "\n  STORE: " << *SI <<
 '\n'; } } while (false);

    deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, ThrowableInst);
    ++NumRedundantStores;
    return true;
  }
}

// Remove null stores into the calloc'ed objects
Constant *StoredConstant = dyn_cast<Constant>(SI->getValueOperand());
if (StoredConstant && StoredConstant->isNullValue() && isRemovable(SI)) {
  Instruction *UnderlyingPointer =
      dyn_cast<Instruction>(GetUnderlyingObject(SI->getPointerOperand(), DL));

  if (UnderlyingPointer && isCallocLikeFn(UnderlyingPointer, TLI) &&
      memoryIsNotModifiedBetween(UnderlyingPointer, SI, AA, DL, DT)) {
    LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove null store to the calloc'ed object:\n  DEAD: "
 << *Inst << "\n  OBJECT: " << *UnderlyingPointer
 << '\n'; } } while (false)
        dbgs() << "DSE: Remove null store to the calloc'ed object:\n  DEAD: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove null store to the calloc'ed object:\n  DEAD: "
 << *Inst << "\n  OBJECT: " << *UnderlyingPointer
 << '\n'; } } while (false)
               << *Inst << "\n  OBJECT: " << *UnderlyingPointer << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove null store to the calloc'ed object:\n  DEAD: "
 << *Inst << "\n  OBJECT: " << *UnderlyingPointer
 << '\n'; } } while (false);

    deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, ThrowableInst);
    ++NumRedundantStores;
    return true;
  }
}
return false;
1139}

1141static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
                              MemoryDependenceResults *MD, DominatorTree *DT,
                              const TargetLibraryInfo *TLI) {
const DataLayout &DL = BB.getModule()->getDataLayout();
bool MadeChange = false;

MapVector<Instruction *, bool> ThrowableInst;

// A map of interval maps representing partially-overwritten value parts.
InstOverlapIntervalsTy IOL;

// Do a top-down walk on the BB.
for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
  // Handle 'free' calls specially.
  if (CallInst *F = isFreeCall(&*BBI, TLI)) {
    MadeChange |= handleFree(F, AA, MD, DT, TLI, IOL, ThrowableInst);
    // Increment BBI after handleFree has potentially deleted instructions.
    // This ensures we maintain a valid iterator.
    ++BBI;
    continue;
  }

  Instruction *Inst = &*BBI++;

  if (Inst->mayThrow()) {
    ThrowableInst[Inst] = true;
    continue;
  }

  // Check to see if Inst writes to memory.  If not, continue.
  if (!hasAnalyzableMemoryWrite(Inst, *TLI))
    continue;

  // eliminateNoopStore will update in iterator, if necessary.
  if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL,
                         ThrowableInst, DT)) {
    MadeChange = true;
    continue;
  }

  // If we find something that writes memory, get its memory dependence.
  MemDepResult InstDep = MD->getDependency(Inst);

  // Ignore any store where we can't find a local dependence.
  // FIXME: cross-block DSE would be fun. :)
  if (!InstDep.isDef() && !InstDep.isClobber())
    continue;

  // Figure out what location is being stored to.
  MemoryLocation Loc = getLocForWrite(Inst);

  // If we didn't get a useful location, fail.
  if (!Loc.Ptr)
    continue;

  // Loop until we find a store we can eliminate or a load that
  // invalidates the analysis. Without an upper bound on the number of
  // instructions examined, this analysis can become very time-consuming.
  // However, the potential gain diminishes as we process more instructions
  // without eliminating any of them. Therefore, we limit the number of
  // instructions we look at.
  auto Limit = MD->getDefaultBlockScanLimit();
  while (InstDep.isDef() || InstDep.isClobber()) {
    // Get the memory clobbered by the instruction we depend on.  MemDep will
    // skip any instructions that 'Loc' clearly doesn't interact with.  If we
    // end up depending on a may- or must-aliased load, then we can't optimize
    // away the store and we bail out.  However, if we depend on something
    // that overwrites the memory location we *can* potentially optimize it.
    //
    // Find out what memory location the dependent instruction stores.
    Instruction *DepWrite = InstDep.getInst();
    if (!hasAnalyzableMemoryWrite(DepWrite, *TLI))
      break;
    MemoryLocation DepLoc = getLocForWrite(DepWrite);
    // If we didn't get a useful location, or if it isn't a size, bail out.
    if (!DepLoc.Ptr)
      break;

    // Find the last throwable instruction not removed by call to
    // deleteDeadInstruction.
    Instruction *LastThrowing = nullptr;
    if (!ThrowableInst.empty())
      LastThrowing = ThrowableInst.back().first;

    // Make sure we don't look past a call which might throw. This is an
    // issue because MemoryDependenceAnalysis works in the wrong direction:
    // it finds instructions which dominate the current instruction, rather than
    // instructions which are post-dominated by the current instruction.
    //
    // If the underlying object is a non-escaping memory allocation, any store
    // to it is dead along the unwind edge. Otherwise, we need to preserve
    // the store.
    if (LastThrowing && DepWrite->comesBefore(LastThrowing)) {
      const Value* Underlying = GetUnderlyingObject(DepLoc.Ptr, DL);
      bool IsStoreDeadOnUnwind = isa<AllocaInst>(Underlying);
      if (!IsStoreDeadOnUnwind) {
          // We're looking for a call to an allocation function
          // where the allocation doesn't escape before the last
          // throwing instruction; PointerMayBeCaptured
          // reasonably fast approximation.
          IsStoreDeadOnUnwind = isAllocLikeFn(Underlying, TLI) &&
              !PointerMayBeCaptured(Underlying, false, true);
      }
      if (!IsStoreDeadOnUnwind)
        break;
    }

    // If we find a write that is a) removable (i.e., non-volatile), b) is
    // completely obliterated by the store to 'Loc', and c) which we know that
    // 'Inst' doesn't load from, then we can remove it.
    // Also try to merge two stores if a later one only touches memory written
    // to by the earlier one.
    if (isRemovable(DepWrite) &&
        !isPossibleSelfRead(Inst, Loc, DepWrite, *TLI, *AA)) {
      int64_t InstWriteOffset, DepWriteOffset;
      OverwriteResult OR = isOverwrite(Loc, DepLoc, DL, *TLI, DepWriteOffset,
                                       InstWriteOffset, DepWrite, IOL, *AA,
                                       BB.getParent());
      if (OR == OW_Complete) {
        LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *DepWritedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n  DEAD: "
 << *DepWrite << "\n  KILLER: " << *Inst <<
 '\n'; } } while (false)
                          << "\n  KILLER: " << *Inst << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n  DEAD: "
 << *DepWrite << "\n  KILLER: " << *Inst <<
 '\n'; } } while (false);

        // Delete the store and now-dead instructions that feed it.
        deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL,
                              ThrowableInst);
        ++NumFastStores;
        MadeChange = true;

        // We erased DepWrite; start over.
        InstDep = MD->getDependency(Inst);
        continue;
      } else if ((OR == OW_End && isShortenableAtTheEnd(DepWrite)) ||
                 ((OR == OW_Begin &&
                   isShortenableAtTheBeginning(DepWrite)))) {
        assert(!EnablePartialOverwriteTracking && "Do not expect to perform "((!EnablePartialOverwriteTracking && "Do not expect to perform "
 "when partial-overwrite " "tracking is enabled") ? static_cast
<void> (0) : __assert_fail ("!EnablePartialOverwriteTracking && \"Do not expect to perform \" \"when partial-overwrite \" \"tracking is enabled\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1277, __PRETTY_FUNCTION__))
                                                  "when partial-overwrite "((!EnablePartialOverwriteTracking && "Do not expect to perform "
 "when partial-overwrite " "tracking is enabled") ? static_cast
<void> (0) : __assert_fail ("!EnablePartialOverwriteTracking && \"Do not expect to perform \" \"when partial-overwrite \" \"tracking is enabled\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1277, __PRETTY_FUNCTION__))
                                                  "tracking is enabled")((!EnablePartialOverwriteTracking && "Do not expect to perform "
 "when partial-overwrite " "tracking is enabled") ? static_cast
<void> (0) : __assert_fail ("!EnablePartialOverwriteTracking && \"Do not expect to perform \" \"when partial-overwrite \" \"tracking is enabled\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1277, __PRETTY_FUNCTION__));
        // The overwrite result is known, so these must be known, too.
        int64_t EarlierSize = DepLoc.Size.getValue();
        int64_t LaterSize = Loc.Size.getValue();
        bool IsOverwriteEnd = (OR == OW_End);
        MadeChange |= tryToShorten(DepWrite, DepWriteOffset, EarlierSize,
                                  InstWriteOffset, LaterSize, IsOverwriteEnd);
      } else if (EnablePartialStoreMerging &&
                 OR == OW_PartialEarlierWithFullLater) {
        auto *Earlier = dyn_cast<StoreInst>(DepWrite);
        auto *Later = dyn_cast<StoreInst>(Inst);
        if (Earlier && isa<ConstantInt>(Earlier->getValueOperand()) &&
            DL.typeSizeEqualsStoreSize(
                Earlier->getValueOperand()->getType()) &&
            Later && isa<ConstantInt>(Later->getValueOperand()) &&
            DL.typeSizeEqualsStoreSize(
                Later->getValueOperand()->getType()) &&
            memoryIsNotModifiedBetween(Earlier, Later, AA, DL, DT)) {
          // If the store we find is:
          //   a) partially overwritten by the store to 'Loc'
          //   b) the later store is fully contained in the earlier one and
          //   c) they both have a constant value
          //   d) none of the two stores need padding
          // Merge the two stores, replacing the earlier store's value with a
          // merge of both values.
          // TODO: Deal with other constant types (vectors, etc), and probably
          // some mem intrinsics (if needed)

          APInt EarlierValue =
              cast<ConstantInt>(Earlier->getValueOperand())->getValue();
          APInt LaterValue =
              cast<ConstantInt>(Later->getValueOperand())->getValue();
          unsigned LaterBits = LaterValue.getBitWidth();
          assert(EarlierValue.getBitWidth() > LaterValue.getBitWidth())((EarlierValue.getBitWidth() > LaterValue.getBitWidth()) ?
 static_cast<void> (0) : __assert_fail ("EarlierValue.getBitWidth() > LaterValue.getBitWidth()"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1310, __PRETTY_FUNCTION__));
          LaterValue = LaterValue.zext(EarlierValue.getBitWidth());

          // Offset of the smaller store inside the larger store
          unsigned BitOffsetDiff = (InstWriteOffset - DepWriteOffset) * 8;
          unsigned LShiftAmount =
              DL.isBigEndian()
                  ? EarlierValue.getBitWidth() - BitOffsetDiff - LaterBits
                  : BitOffsetDiff;
          APInt Mask =
              APInt::getBitsSet(EarlierValue.getBitWidth(), LShiftAmount,
                                LShiftAmount + LaterBits);
          // Clear the bits we'll be replacing, then OR with the smaller
          // store, shifted appropriately.
          APInt Merged =
              (EarlierValue & ~Mask) | (LaterValue << LShiftAmount);
          LLVM_DEBUG(dbgs() << "DSE: Merge Stores:\n  Earlier: " << *DepWritedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Merge Stores:\n  Earlier: " <<
 *DepWrite << "\n  Later: " << *Inst << "\n  Merged Value: "
 << Merged << '\n'; } } while (false)
                            << "\n  Later: " << *Instdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Merge Stores:\n  Earlier: " <<
 *DepWrite << "\n  Later: " << *Inst << "\n  Merged Value: "
 << Merged << '\n'; } } while (false)
                            << "\n  Merged Value: " << Merged << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Merge Stores:\n  Earlier: " <<
 *DepWrite << "\n  Later: " << *Inst << "\n  Merged Value: "
 << Merged << '\n'; } } while (false);

          auto *SI = new StoreInst(
              ConstantInt::get(Earlier->getValueOperand()->getType(), Merged),
              Earlier->getPointerOperand(), false,
              MaybeAlign(Earlier->getAlignment()), Earlier->getOrdering(),
              Earlier->getSyncScopeID(), DepWrite);

          unsigned MDToKeep[] = {LLVMContext::MD_dbg, LLVMContext::MD_tbaa,
                                 LLVMContext::MD_alias_scope,
                                 LLVMContext::MD_noalias,
                                 LLVMContext::MD_nontemporal};
          SI->copyMetadata(*DepWrite, MDToKeep);
          ++NumModifiedStores;

          // Delete the old stores and now-dead instructions that feed them.
          deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL,
                                ThrowableInst);
          deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL,
                                ThrowableInst);
          MadeChange = true;

          // We erased DepWrite and Inst (Loc); start over.
          break;
        }
      }
    }

    // If this is a may-aliased store that is clobbering the store value, we
    // can keep searching past it for another must-aliased pointer that stores
    // to the same location.  For example, in:
    //   store -> P
    //   store -> Q
    //   store -> P
    // we can remove the first store to P even though we don't know if P and Q
    // alias.
    if (DepWrite == &BB.front()) break;

    // Can't look past this instruction if it might read 'Loc'.
    if (isRefSet(AA->getModRefInfo(DepWrite, Loc)))
      break;

    InstDep = MD->getPointerDependencyFrom(Loc, /*isLoad=*/ false,
                                           DepWrite->getIterator(), &BB,
                                           /*QueryInst=*/ nullptr, &Limit);
  }
}

if (EnablePartialOverwriteTracking)
  MadeChange |= removePartiallyOverlappedStores(AA, DL, IOL);

// If this block ends in a return, unwind, or unreachable, all allocas are
// dead at its end, which means stores to them are also dead.
if (BB.getTerminator()->getNumSuccessors() == 0)
  MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, ThrowableInst);

return MadeChange;
1385}

1387static bool eliminateDeadStores(Function &F, AliasAnalysis *AA,
                              MemoryDependenceResults *MD, DominatorTree *DT,
                              const TargetLibraryInfo *TLI) {
bool MadeChange = false;
for (BasicBlock &BB : F)
  // Only check non-dead blocks.  Dead blocks may have strange pointer
  // cycles that will confuse alias analysis.
  if (DT->isReachableFromEntry(&BB))
    MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI);

return MadeChange;
1398}

1400namespace {
1401//=============================================================================
1402// MemorySSA backed dead store elimination.
1403//
1404// The code below implements dead store elimination using MemorySSA. It uses
1405// the following general approach: given a MemoryDef, walk upwards to find
1406// clobbering MemoryDefs that may be killed by the starting def. Then check
1407// that there are no uses that may read the location of the original MemoryDef
1408// in between both MemoryDefs. A bit more concretely:
1409//
1410// For all MemoryDefs StartDef:
1411// 1. Get the next dominating clobbering MemoryDef (DomAccess) by walking
1412//    upwards.
1413// 2. Check that there are no reads between DomAccess and the StartDef by
1414//    checking all uses starting at DomAccess and walking until we see StartDef.
1415// 3. For each found DomDef, check that:
1416//   1. There are no barrier instructions between DomDef and StartDef (like
1417//       throws or stores with ordering constraints).
1418//   2. StartDef is executed whenever DomDef is executed.
1419//   3. StartDef completely overwrites DomDef.
1420// 4. Erase DomDef from the function and MemorySSA.

1422// Returns true if \p M is an intrisnic that does not read or write memory.
1423bool isNoopIntrinsic(MemoryUseOrDef *M) {
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(M->getMemoryInst())) {
  switch (II->getIntrinsicID()) {
  case Intrinsic::lifetime_start:
  case Intrinsic::lifetime_end:
  case Intrinsic::invariant_end:
  case Intrinsic::launder_invariant_group:
  case Intrinsic::assume:
    return true;
  case Intrinsic::dbg_addr:
  case Intrinsic::dbg_declare:
  case Intrinsic::dbg_label:
  case Intrinsic::dbg_value:
    llvm_unreachable("Intrinsic should not be modeled in MemorySSA")::llvm::llvm_unreachable_internal("Intrinsic should not be modeled in MemorySSA"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1436);
  default:
    return false;
  }
}
return false;
1442}

1444// Check if we can ignore \p D for DSE.
1445bool canSkipDef(MemoryDef *D, bool DefVisibleToCaller) {
Instruction *DI = D->getMemoryInst();
// Calls that only access inaccessible memory cannot read or write any memory
// locations we consider for elimination.
if (auto CS = CallSite(DI))
  if (CS.onlyAccessesInaccessibleMemory())
    return true;

// We can eliminate stores to locations not visible to the caller across
// throwing instructions.
if (DI->mayThrow() && !DefVisibleToCaller)
  return true;

// We can remove the dead stores, irrespective of the fence and its ordering
// (release/acquire/seq_cst). Fences only constraints the ordering of
// already visible stores, it does not make a store visible to other
// threads. So, skipping over a fence does not change a store from being
// dead.
if (isa<FenceInst>(DI))
  return true;

// Skip intrinsics that do not really read or modify memory.
if (isNoopIntrinsic(D))
  return true;

return false;
1471}

1473struct DSEState {
Function &F;
AliasAnalysis &AA;
MemorySSA &MSSA;
DominatorTree &DT;
PostDominatorTree &PDT;
const TargetLibraryInfo &TLI;

// All MemoryDefs that potentially could kill other MemDefs.
SmallVector<MemoryDef *, 64> MemDefs;
// Any that should be skipped as they are already deleted
SmallPtrSet<MemoryAccess *, 4> SkipStores;
// Keep track of all of the objects that are invisible to the caller until the
// function returns.
SmallPtrSet<const Value *, 16> InvisibleToCaller;
// Keep track of blocks with throwing instructions not modeled in MemorySSA.
SmallPtrSet<BasicBlock *, 16> ThrowingBlocks;

/// Keep track of instructions (partly) overlapping with killing MemoryDefs per
/// basic block.
DenseMap<BasicBlock *, InstOverlapIntervalsTy> IOLs;

DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
         PostDominatorTree &PDT, const TargetLibraryInfo &TLI)
    : F(F), AA(AA), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI) {}

static DSEState get(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
                    DominatorTree &DT, PostDominatorTree &PDT,
                    const TargetLibraryInfo &TLI) {
  DSEState State(F, AA, MSSA, DT, PDT, TLI);
  // Collect blocks with throwing instructions not modeled in MemorySSA and
  // alloc-like objects.
  for (Instruction &I : instructions(F)) {
    if (I.mayThrow() && !MSSA.getMemoryAccess(&I))
      State.ThrowingBlocks.insert(I.getParent());

    auto *MD = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(&I));
    if (MD && State.MemDefs.size() < MemorySSADefsPerBlockLimit &&
        hasAnalyzableMemoryWrite(&I, TLI) && isRemovable(&I))
      State.MemDefs.push_back(MD);

    // Track alloca and alloca-like objects. Here we care about objects not
    // visible to the caller during function execution. Alloca objects are
    // invalid in the caller, for alloca-like objects we ensure that they are
    // not captured throughout the function.
    if (isa<AllocaInst>(&I) ||
        (isAllocLikeFn(&I, &TLI) && !PointerMayBeCaptured(&I, false, true)))
      State.InvisibleToCaller.insert(&I);
  }
  // Treat byval or inalloca arguments the same as Allocas, stores to them are
  // dead at the end of the function.
  for (Argument &AI : F.args())
    if (AI.hasByValOrInAllocaAttr())
      State.InvisibleToCaller.insert(&AI);
  return State;
}

Optional<MemoryLocation> getLocForWriteEx(Instruction *I) const {
  if (!I->mayWriteToMemory())
    return None;

  if (auto *MTI = dyn_cast<AnyMemIntrinsic>(I))
    return {MemoryLocation::getForDest(MTI)};

  if (auto CS = CallSite(I)) {
    if (Function *F = CS.getCalledFunction()) {
      StringRef FnName = F->getName();
      if (TLI.has(LibFunc_strcpy) && FnName == TLI.getName(LibFunc_strcpy))
        return {MemoryLocation(CS.getArgument(0))};
      if (TLI.has(LibFunc_strncpy) && FnName == TLI.getName(LibFunc_strncpy))
        return {MemoryLocation(CS.getArgument(0))};
      if (TLI.has(LibFunc_strcat) && FnName == TLI.getName(LibFunc_strcat))
        return {MemoryLocation(CS.getArgument(0))};
      if (TLI.has(LibFunc_strncat) && FnName == TLI.getName(LibFunc_strncat))
        return {MemoryLocation(CS.getArgument(0))};
    }
    return None;
  }

  return MemoryLocation::getOrNone(I);
}

/// Returns true if \p Use completely overwrites \p DefLoc.
bool isCompleteOverwrite(MemoryLocation DefLoc, Instruction *UseInst) const {
  // UseInst has a MemoryDef associated in MemorySSA. It's possible for a
  // MemoryDef to not write to memory, e.g. a volatile load is modeled as a
  // MemoryDef.
  if (!UseInst->mayWriteToMemory())
    return false;

  if (auto CS = CallSite(UseInst))
    if (CS.onlyAccessesInaccessibleMemory())
      return false;

  ModRefInfo MR = AA.getModRefInfo(UseInst, DefLoc);
  // If necessary, perform additional analysis.
  if (isModSet(MR))
    MR = AA.callCapturesBefore(UseInst, DefLoc, &DT);

  Optional<MemoryLocation> UseLoc = getLocForWriteEx(UseInst);
  return isModSet(MR) && isMustSet(MR) &&
         UseLoc->Size.getValue() >= DefLoc.Size.getValue();
}

/// Returns true if \p Use may read from \p DefLoc.
bool isReadClobber(MemoryLocation DefLoc, Instruction *UseInst) const {
  if (!UseInst->mayReadFromMemory())
    return false;

  if (auto CS = CallSite(UseInst))
    if (CS.onlyAccessesInaccessibleMemory())
      return false;

  ModRefInfo MR = AA.getModRefInfo(UseInst, DefLoc);
  // If necessary, perform additional analysis.
  if (isRefSet(MR))
    MR = AA.callCapturesBefore(UseInst, DefLoc, &DT);
  return isRefSet(MR);
}

// Find a MemoryDef writing to \p DefLoc and dominating \p Current, with no
// read access in between or return None otherwise. The returned value may not
// (completely) overwrite \p DefLoc. Currently we bail out when we encounter
// any of the following
//  * An aliasing MemoryUse (read).
//  * A MemoryPHI.
Optional<MemoryAccess *> getDomMemoryDef(MemoryDef *KillingDef,
                                         MemoryAccess *Current,
                                         MemoryLocation DefLoc,
                                         bool DefVisibleToCaller,
                                         int &ScanLimit) const {
  MemoryDef *DomDef;
  MemoryAccess *StartDef = Current;
  bool StepAgain;
  LLVM_DEBUG(dbgs() << "  trying to get dominating access for " << *Currentdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "  trying to get dominating access for "
 << *Current << "\n"; } } while (false)
                    << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "  trying to get dominating access for "
 << *Current << "\n"; } } while (false);
  // Find the next clobbering Mod access for DefLoc, starting at Current.
  do {
    StepAgain = false;
    // Reached TOP.
    if (MSSA.isLiveOnEntryDef(Current))
      return None;

    MemoryUseOrDef *CurrentUD = dyn_cast<MemoryUseOrDef>(Current);
    if (!CurrentUD)
      return None;

    // Look for access that clobber DefLoc.
    MemoryAccess *DomAccess =
        MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(
            CurrentUD->getDefiningAccess(), DefLoc);
    DomDef = dyn_cast<MemoryDef>(DomAccess);
    if (!DomDef || MSSA.isLiveOnEntryDef(DomDef))
      return None;

    // Check if we can skip DomDef for DSE. We also require the KillingDef
    // execute whenever DomDef executes and use post-dominance to ensure that.
    if (canSkipDef(DomDef, DefVisibleToCaller) ||
        !PDT.dominates(KillingDef->getBlock(), DomDef->getBlock())) {
      StepAgain = true;
      Current = DomDef;
    }

  } while (StepAgain);

  LLVM_DEBUG(dbgs() << "  Checking for reads of " << *DomDef << " ("do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "  Checking for reads of " <<
 *DomDef << " (" << *DomDef->getMemoryInst() <<
 ")\n"; } } while (false)
                    << *DomDef->getMemoryInst() << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "  Checking for reads of " <<
 *DomDef << " (" << *DomDef->getMemoryInst() <<
 ")\n"; } } while (false);

  SmallSetVector<MemoryAccess *, 32> WorkList;
  auto PushMemUses = [&WorkList](MemoryAccess *Acc) {
    for (Use &U : Acc->uses())
      WorkList.insert(cast<MemoryAccess>(U.getUser()));
  };
  PushMemUses(DomDef);

  // Check if DomDef may be read.
  for (unsigned I = 0; I < WorkList.size(); I++) {
    MemoryAccess *UseAccess = WorkList[I];

    LLVM_DEBUG(dbgs() << "   Checking use " << *UseAccess)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "   Checking use " << *UseAccess
; } } while (false);
    if (--ScanLimit == 0) {
      LLVM_DEBUG(dbgs() << "  ...  hit scan limit\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "  ...  hit scan limit\n"; } } while
 (false);
      return None;
    }

    // Bail out on MemoryPhis for now.
    if (isa<MemoryPhi>(UseAccess)) {
      LLVM_DEBUG(dbgs() << "  ...  hit MemoryPhi\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "  ...  hit MemoryPhi\n"; } } while
 (false);
      return None;
    }

    Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
    LLVM_DEBUG(dbgs() << " (" << *UseInst << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " (" << *UseInst << ")\n"
; } } while (false);

    if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess))) {
      PushMemUses(UseAccess);
      continue;
    }

    // Uses which may read the original MemoryDef mean we cannot eliminate the
    // original MD. Stop walk.
    if (isReadClobber(DefLoc, UseInst)) {
      LLVM_DEBUG(dbgs() << "  ... found read clobber\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "  ... found read clobber\n"; } } while
 (false);
      return None;
    }

    if (StartDef == UseAccess)
      continue;

    // Check all uses for MemoryDefs, except for defs completely overwriting
    // the original location. Otherwise we have to check uses of *all*
    // MemoryDefs we discover, including non-aliasing ones. Otherwise we might
    // miss cases like the following
    //   1 = Def(LoE) ; <----- DomDef stores [0,1]
    //   2 = Def(1)   ; (2, 1) = NoAlias,   stores [2,3]
    //   Use(2)       ; MayAlias 2 *and* 1, loads [0, 3].
    //                  (The Use points to the *first* Def it may alias)
    //   3 = Def(1)   ; <---- Current  (3, 2) = NoAlias, (3,1) = MayAlias,
    //                  stores [0,1]
    if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess)) {
      if (!isCompleteOverwrite(DefLoc, UseInst))
        PushMemUses(UseDef);
    }
  }

  // No aliasing MemoryUses of DomDef found, DomDef is potentially dead.
  return {DomDef};
}

// Delete dead memory defs
void deleteDeadInstruction(Instruction *SI) {
  MemorySSAUpdater Updater(&MSSA);
  SmallVector<Instruction *, 32> NowDeadInsts;
  NowDeadInsts.push_back(SI);
  --NumFastOther;

  while (!NowDeadInsts.empty()) {
    Instruction *DeadInst = NowDeadInsts.pop_back_val();
    ++NumFastOther;

    // Try to preserve debug information attached to the dead instruction.
    salvageDebugInfo(*DeadInst);

    // Remove the Instruction from MSSA.
    if (MemoryAccess *MA = MSSA.getMemoryAccess(DeadInst)) {
      if (MemoryDef *MD = dyn_cast<MemoryDef>(MA)) {
        SkipStores.insert(MD);
      }
      Updater.removeMemoryAccess(MA);
    }

    auto I = IOLs.find(DeadInst->getParent());
    if (I != IOLs.end())
      I->second.erase(DeadInst);
    // Remove its operands
    for (Use &O : DeadInst->operands())
      if (Instruction *OpI = dyn_cast<Instruction>(O)) {
        O = nullptr;
        if (isInstructionTriviallyDead(OpI, &TLI))
          NowDeadInsts.push_back(OpI);
      }

    DeadInst->eraseFromParent();
  }
}

// Check for any extra throws between SI and NI that block DSE.  This only
// checks extra maythrows (those that aren't MemoryDef's). MemoryDef that may
// throw are handled during the walk from one def to the next.
bool mayThrowBetween(Instruction *SI, Instruction *NI,
                     const Value *SILocUnd) const {
  // First see if we can ignore it by using the fact that SI is an
  // alloca/alloca like object that is not visible to the caller during
  // execution of the function.
  if (SILocUnd && InvisibleToCaller.count(SILocUnd))
    return false;

  if (SI->getParent() == NI->getParent())
    return ThrowingBlocks.find(SI->getParent()) != ThrowingBlocks.end();
  return !ThrowingBlocks.empty();
}

// Check if \p NI acts as a DSE barrier for \p SI. The following instructions
// act as barriers:
//  * A memory instruction that may throw and \p SI accesses a non-stack
//  object.
//  * Atomic stores stronger that monotonic.
bool isDSEBarrier(Instruction *SI, MemoryLocation &SILoc,
                  const Value *SILocUnd, Instruction *NI,
                  MemoryLocation &NILoc) const {
  // If NI may throw it acts as a barrier, unless we are to an alloca/alloca
  // like object that does not escape.
  if (NI->mayThrow() && !InvisibleToCaller.count(SILocUnd))
    return true;

  if (NI->isAtomic()) {
    if (auto *NSI = dyn_cast<StoreInst>(NI)) {
      if (isStrongerThanMonotonic(NSI->getOrdering()))
        return true;
    } else
      llvm_unreachable(::llvm::llvm_unreachable_internal("Other instructions should be modeled/skipped in MemorySSA"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1774)
          "Other instructions should be modeled/skipped in MemorySSA")::llvm::llvm_unreachable_internal("Other instructions should be modeled/skipped in MemorySSA"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1774);
  }

  return false;
}
1779};

1781bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA,
                                MemorySSA &MSSA, DominatorTree &DT,
                                PostDominatorTree &PDT,
                                const TargetLibraryInfo &TLI) {
const DataLayout &DL = F.getParent()->getDataLayout();
bool MadeChange = false;

DSEState State = DSEState::get(F, AA, MSSA, DT, PDT, TLI);
// For each store:
for (unsigned I = 0; I < State.MemDefs.size(); I++) {
4
←
Assuming the condition is true→
5
←
Loop condition is true.  Entering loop body→
  MemoryDef *Current = State.MemDefs[I];
  if (State.SkipStores.count(Current))
6
←
Assuming the condition is false→
7
←
Taking false branch→
    continue;
  Instruction *SI = cast<MemoryDef>(Current)->getMemoryInst();
8
←
'Current' is a 'MemoryDef'→
  auto MaybeSILoc = State.getLocForWriteEx(SI);
  if (!MaybeSILoc) {
9
←
Calling 'Optional::operator bool'→
17
←
Returning from 'Optional::operator bool'→
18
←
Taking false branch→
    LLVM_DEBUG(dbgs() << "Failed to find analyzable write location for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Failed to find analyzable write location for "
 << *SI << "\n"; } } while (false)
                      << *SI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Failed to find analyzable write location for "
 << *SI << "\n"; } } while (false);
    continue;
  }
  MemoryLocation SILoc = *MaybeSILoc;
  assert(SILoc.Ptr && "SILoc should not be null")((SILoc.Ptr && "SILoc should not be null") ? static_cast
<void> (0) : __assert_fail ("SILoc.Ptr && \"SILoc should not be null\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1802, __PRETTY_FUNCTION__));
19
←
Assuming field 'Ptr' is non-null→
20
←
'?' condition is true→
  const Value *SILocUnd = GetUnderlyingObject(SILoc.Ptr, DL);
  Instruction *DefObj =
      const_cast<Instruction *>(dyn_cast<Instruction>(SILocUnd));
21
←
Assuming 'SILocUnd' is not a 'Instruction'→
  bool DefVisibleToCaller = !State.InvisibleToCaller.count(SILocUnd);
22
←
Assuming the condition is false→
  if (DefObj22.1
'DefObj' is null
1
'DefObj' is null
 && ((isAllocLikeFn(DefObj, &TLI) &&
                  !PointerMayBeCapturedBefore(DefObj, false, true, SI, &DT))))
    DefVisibleToCaller = false;

  LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs killed by " << *SIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs killed by "
 << *SI << "\n"; } } while (false)
23
←
Assuming 'DebugFlag' is false→
24
←
Loop condition is false.  Exiting loop→
                    << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs killed by "
 << *SI << "\n"; } } while (false);

  int ScanLimit = MemorySSAScanLimit;
  MemoryDef *StartDef = Current;
  // Walk MemorySSA upward to find MemoryDefs that might be killed by SI.
  while (Optional<MemoryAccess *> Next = State.getDomMemoryDef(
25
←
Calling 'Optional::operator bool'→
33
←
Returning from 'Optional::operator bool'→
34
←
Loop condition is true.  Entering loop body→
             StartDef, Current, SILoc, DefVisibleToCaller, ScanLimit)) {
    MemoryAccess *DomAccess = *Next;
    LLVM_DEBUG(dbgs() << " Checking if we can kill " << *DomAccess << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " Checking if we can kill " <<
 *DomAccess << "\n"; } } while (false);
35
←
Assuming 'DebugFlag' is false→
36
←
Loop condition is false.  Exiting loop→
    MemoryDef *NextDef = dyn_cast<MemoryDef>(DomAccess);
37
←
Assuming 'DomAccess' is not a 'MemoryDef'→
38
←
'NextDef' initialized to a null pointer value→
    Instruction *NI = NextDef->getMemoryInst();
39
←
Called C++ object pointer is null
    LLVM_DEBUG(dbgs() << "  def " << *NI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "  def " << *NI << "\n"
; } } while (false);

    if (!hasAnalyzableMemoryWrite(NI, TLI))
      break;

    if (!isRemovable(NI)) {
      LLVM_DEBUG(dbgs() << " skip, cannot remove def\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " skip, cannot remove def\n"; } } while
 (false);
      continue;
    }

    MemoryLocation NILoc = *State.getLocForWriteEx(NI);
    // Check for anything that looks like it will be a barrier to further
    // removal
    if (State.isDSEBarrier(SI, SILoc, SILocUnd, NI, NILoc)) {
      LLVM_DEBUG(dbgs() << "  stop, barrier\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "  stop, barrier\n"; } } while (false
);
      break;
    }

    // Before we try to remove anything, check for any extra throwing
    // instructions that block us from DSEing
    if (State.mayThrowBetween(SI, NI, SILocUnd)) {
      LLVM_DEBUG(dbgs() << " stop, may throw!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " stop, may throw!\n"; } } while (
false);
      break;
    }

    if (!DebugCounter::shouldExecute(MemorySSACounter))
      break;

    // Check if NI overwrites SI.
    int64_t InstWriteOffset, DepWriteOffset;
    auto Iter = State.IOLs.insert(
        std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
            NI->getParent(), InstOverlapIntervalsTy()));
    auto &IOL = Iter.first->second;
    OverwriteResult OR = isOverwrite(SILoc, NILoc, DL, TLI, DepWriteOffset,
                                     InstWriteOffset, NI, IOL, AA, &F);

    if (OR == OW_Complete) {
      LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *NIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n  DEAD: "
 << *NI << "\n  KILLER: " << *SI << '\n'
; } } while (false)
                        << "\n  KILLER: " << *SI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n  DEAD: "
 << *NI << "\n  KILLER: " << *SI << '\n'
; } } while (false);
      State.deleteDeadInstruction(NI);
      ++NumFastStores;
      MadeChange = true;
    } else
      Current = NextDef;
  }
}

if (EnablePartialOverwriteTracking)
  for (auto &KV : State.IOLs)
    MadeChange |= removePartiallyOverlappedStores(&AA, DL, KV.second);

return MadeChange;
1876}
1877} // end anonymous namespace

1879//===----------------------------------------------------------------------===//
1880// DSE Pass
1881//===----------------------------------------------------------------------===//
1882PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
AliasAnalysis &AA = AM.getResult<AAManager>(F);
const TargetLibraryInfo &TLI = AM.getResult<TargetLibraryAnalysis>(F);
DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);

if (EnableMemorySSA) {
1
Assuming the condition is true→
2
←
Taking true branch→
  MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
  PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);

  if (!eliminateDeadStoresMemorySSA(F, AA, MSSA, DT, PDT, TLI))
3
←
Calling 'eliminateDeadStoresMemorySSA'→
    return PreservedAnalyses::all();
} else {
  MemoryDependenceResults &MD = AM.getResult<MemoryDependenceAnalysis>(F);

  if (!eliminateDeadStores(F, &AA, &MD, &DT, &TLI))
    return PreservedAnalyses::all();
}

PreservedAnalyses PA;
PA.preserveSet<CFGAnalyses>();
PA.preserve<GlobalsAA>();
if (EnableMemorySSA)
  PA.preserve<MemorySSAAnalysis>();
else
  PA.preserve<MemoryDependenceAnalysis>();
return PA;
1908}

1910namespace {

1912/// A legacy pass for the legacy pass manager that wraps \c DSEPass.
1913class DSELegacyPass : public FunctionPass {
1914public:
static char ID; // Pass identification, replacement for typeid

DSELegacyPass() : FunctionPass(ID) {
  initializeDSELegacyPassPass(*PassRegistry::getPassRegistry());
}

bool runOnFunction(Function &F) override {
  if (skipFunction(F))
    return false;

  AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
  const TargetLibraryInfo &TLI =
      getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);

  if (EnableMemorySSA) {
    MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
    PostDominatorTree &PDT =
        getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();

    return eliminateDeadStoresMemorySSA(F, AA, MSSA, DT, PDT, TLI);
  } else {
    MemoryDependenceResults &MD =
        getAnalysis<MemoryDependenceWrapperPass>().getMemDep();

    return eliminateDeadStores(F, &AA, &MD, &DT, &TLI);
  }
}

void getAnalysisUsage(AnalysisUsage &AU) const override {
  AU.setPreservesCFG();
  AU.addRequired<AAResultsWrapperPass>();
  AU.addRequired<TargetLibraryInfoWrapperPass>();
  AU.addPreserved<GlobalsAAWrapperPass>();
  AU.addRequired<DominatorTreeWrapperPass>();
  AU.addPreserved<DominatorTreeWrapperPass>();

  if (EnableMemorySSA) {
    AU.addRequired<PostDominatorTreeWrapperPass>();
    AU.addRequired<MemorySSAWrapperPass>();
    AU.addPreserved<PostDominatorTreeWrapperPass>();
    AU.addPreserved<MemorySSAWrapperPass>();
  } else {
    AU.addRequired<MemoryDependenceWrapperPass>();
    AU.addPreserved<MemoryDependenceWrapperPass>();
  }
}
1962};

1964} // end anonymous namespace

1966char DSELegacyPass::ID = 0;

1968INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false,static void *initializeDSELegacyPassPassOnce(PassRegistry &
Registry) {
                    false)static void *initializeDSELegacyPassPassOnce(PassRegistry &
Registry) {
1970INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
1971INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)initializePostDominatorTreeWrapperPassPass(Registry);
1972INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
1973INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)initializeGlobalsAAWrapperPassPass(Registry);
1974INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)initializeMemorySSAWrapperPassPass(Registry);
1975INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)initializeMemoryDependenceWrapperPassPass(Registry);
1976INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
1977INITIALIZE_PASS_END(DSELegacyPass, "dse", "Dead Store Elimination", false,PassInfo *PI = new PassInfo( "Dead Store Elimination", "dse",
 &DSELegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<DSELegacyPass>), false, false); Registry.registerPass(
*PI, true); return PI; } static llvm::once_flag InitializeDSELegacyPassPassFlag
; void llvm::initializeDSELegacyPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeDSELegacyPassPassFlag, initializeDSELegacyPassPassOnce
, std::ref(Registry)); }
                  false)PassInfo *PI = new PassInfo( "Dead Store Elimination", "dse",
 &DSELegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<DSELegacyPass>), false, false); Registry.registerPass(
*PI, true); return PI; } static llvm::once_flag InitializeDSELegacyPassPassFlag
; void llvm::initializeDSELegacyPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeDSELegacyPassPassFlag, initializeDSELegacyPassPassOnce
, std::ref(Registry)); }

1980FunctionPass *llvm::createDeadStoreEliminationPass() {
return new DSELegacyPass();
1982}

←

/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/Optional.h

1//===- Optional.h - Simple variant for passing optional values --*- 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 provides Optional, a template class modeled in the spirit of
10//  OCaml's 'opt' variant.  The idea is to strongly type whether or not
11//  a value can be optional.
12//
13//===----------------------------------------------------------------------===//
14 
15#ifndef LLVM_ADT_OPTIONAL_H
16#define LLVM_ADT_OPTIONAL_H
17 
18#include "llvm/ADT/None.h"
19#include "llvm/Support/Compiler.h"
20#include "llvm/Support/type_traits.h"
21#include <cassert>
22#include <memory>
23#include <new>
24#include <utility>
25 
26namespace llvm {
27 
28class raw_ostream;
29 
30namespace optional_detail {
31 
32struct in_place_t {};
33 
34/// Storage for any type.
35template <typename T, bool = is_trivially_copyable<T>::value>
36class OptionalStorage {
37  union {
38    char empty;
39    T value;
40  };
41  bool hasVal;
42 
43public:
44  ~OptionalStorage() { reset(); }
45 
46  OptionalStorage() noexcept : empty(), hasVal(false) {}
47 
48  OptionalStorage(OptionalStorage const &other) : OptionalStorage() {
49    if (other.hasValue()) {
50      emplace(other.value);
51    }
52  }
53  OptionalStorage(OptionalStorage &&other) : OptionalStorage() {
54    if (other.hasValue()) {
55      emplace(std::move(other.value));
56    }
57  }
58 
59  template <class... Args>
60  explicit OptionalStorage(in_place_t, Args &&... args)
61      : value(std::forward<Args>(args)...), hasVal(true) {}
62 
63  void reset() noexcept {
64    if (hasVal) {
65      value.~T();
66      hasVal = false;
67    }
68  }
69 
70  bool hasValue() const noexcept { return hasVal; }
71 
72  T &getValue() LLVM_LVALUE_FUNCTION& noexcept {
73    assert(hasVal)((hasVal) ? static_cast<void> (0) : __assert_fail ("hasVal"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/Optional.h"
, 73, __PRETTY_FUNCTION__));
74    return value;
75  }
76  T const &getValue() const LLVM_LVALUE_FUNCTION& noexcept {
77    assert(hasVal)((hasVal) ? static_cast<void> (0) : __assert_fail ("hasVal"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/Optional.h"
, 77, __PRETTY_FUNCTION__));
78    return value;
79  }
80#if LLVM_HAS_RVALUE_REFERENCE_THIS1
81  T &&getValue() && noexcept {
82    assert(hasVal)((hasVal) ? static_cast<void> (0) : __assert_fail ("hasVal"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/Optional.h"
, 82, __PRETTY_FUNCTION__));
83    return std::move(value);
84  }
85#endif
86 
87  template <class... Args> void emplace(Args &&... args) {
88    reset();
89    ::new ((void *)std::addressof(value)) T(std::forward<Args>(args)...);
90    hasVal = true;
91  }
92 
93  OptionalStorage &operator=(T const &y) {
94    if (hasValue()) {
95      value = y;
96    } else {
97      ::new ((void *)std::addressof(value)) T(y);
98      hasVal = true;
99    }
100    return *this;
101  }
102  OptionalStorage &operator=(T &&y) {
103    if (hasValue()) {
104      value = std::move(y);
105    } else {
106      ::new ((void *)std::addressof(value)) T(std::move(y));
107      hasVal = true;
108    }
109    return *this;
110  }
111 
112  OptionalStorage &operator=(OptionalStorage const &other) {
113    if (other.hasValue()) {
114      if (hasValue()) {
115        value = other.value;
116      } else {
117        ::new ((void *)std::addressof(value)) T(other.value);
118        hasVal = true;
119      }
120    } else {
121      reset();
122    }
123    return *this;
124  }
125 
126  OptionalStorage &operator=(OptionalStorage &&other) {
127    if (other.hasValue()) {
128      if (hasValue()) {
129        value = std::move(other.value);
130      } else {
131        ::new ((void *)std::addressof(value)) T(std::move(other.value));
132        hasVal = true;
133      }
134    } else {
135      reset();
136    }
137    return *this;
138  }
139};
140 
141template <typename T> class OptionalStorage<T, true> {
142  union {
143    char empty;
144    T value;
145  };
146  bool hasVal = false;
147 
148public:
149  ~OptionalStorage() = default;
150 
151  OptionalStorage() noexcept : empty{} {}
152 
153  OptionalStorage(OptionalStorage const &other) = default;
154  OptionalStorage(OptionalStorage &&other) = default;
155 
156  OptionalStorage &operator=(OptionalStorage const &other) = default;
157  OptionalStorage &operator=(OptionalStorage &&other) = default;
158 
159  template <class... Args>
160  explicit OptionalStorage(in_place_t, Args &&... args)
161      : value(std::forward<Args>(args)...), hasVal(true) {}
162 
163  void reset() noexcept {
164    if (hasVal) {
165      value.~T();
166      hasVal = false;
167    }
168  }
169 
170  bool hasValue() const noexcept { return hasVal; }
12
←
Returning the value 1, which participates in a condition later→
28
←
Returning the value 1, which participates in a condition later→
171 
172  T &getValue() LLVM_LVALUE_FUNCTION& noexcept {
173    assert(hasVal)((hasVal) ? static_cast<void> (0) : __assert_fail ("hasVal"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/Optional.h"
, 173, __PRETTY_FUNCTION__));
174    return value;
175  }
176  T const &getValue() const LLVM_LVALUE_FUNCTION& noexcept {
177    assert(hasVal)((hasVal) ? static_cast<void> (0) : __assert_fail ("hasVal"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/Optional.h"
, 177, __PRETTY_FUNCTION__));
178    return value;
179  }
180#if LLVM_HAS_RVALUE_REFERENCE_THIS1
181  T &&getValue() && noexcept {
182    assert(hasVal)((hasVal) ? static_cast<void> (0) : __assert_fail ("hasVal"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/ADT/Optional.h"
, 182, __PRETTY_FUNCTION__));
183    return std::move(value);
184  }
185#endif
186 
187  template <class... Args> void emplace(Args &&... args) {
188    reset();
189    ::new ((void *)std::addressof(value)) T(std::forward<Args>(args)...);
190    hasVal = true;
191  }
192 
193  OptionalStorage &operator=(T const &y) {
194    if (hasValue()) {
195      value = y;
196    } else {
197      ::new ((void *)std::addressof(value)) T(y);
198      hasVal = true;
199    }
200    return *this;
201  }
202  OptionalStorage &operator=(T &&y) {
203    if (hasValue()) {
204      value = std::move(y);
205    } else {
206      ::new ((void *)std::addressof(value)) T(std::move(y));
207      hasVal = true;
208    }
209    return *this;
210  }
211};
212 
213} // namespace optional_detail
214 
215template <typename T> class Optional {
216  optional_detail::OptionalStorage<T> Storage;
217 
218public:
219  using value_type = T;
220 
221  constexpr Optional() {}
222  constexpr Optional(NoneType) {}
223 
224  Optional(const T &y) : Storage(optional_detail::in_place_t{}, y) {}
225  Optional(const Optional &O) = default;
226 
227  Optional(T &&y) : Storage(optional_detail::in_place_t{}, std::move(y)) {}
228  Optional(Optional &&O) = default;
229 
230  Optional &operator=(T &&y) {
231    Storage = std::move(y);
232    return *this;
233  }
234  Optional &operator=(Optional &&O) = default;
235 
236  /// Create a new object by constructing it in place with the given arguments.
237  template <typename... ArgTypes> void emplace(ArgTypes &&... Args) {
238    Storage.emplace(std::forward<ArgTypes>(Args)...);
239  }
240 
241  static inline Optional create(const T *y) {
242    return y ? Optional(*y) : Optional();
243  }
244 
245  Optional &operator=(const T &y) {
246    Storage = y;
247    return *this;
248  }
249  Optional &operator=(const Optional &O) = default;
250 
251  void reset() { Storage.reset(); }
252 
253  const T *getPointer() const { return &Storage.getValue(); }
254  T *getPointer() { return &Storage.getValue(); }
255  const T &getValue() const LLVM_LVALUE_FUNCTION& { return Storage.getValue(); }
256  T &getValue() LLVM_LVALUE_FUNCTION& { return Storage.getValue(); }
257 
258  explicit operator bool() const { return hasValue(); }
10
←
Calling 'Optional::hasValue'→
15
←
Returning from 'Optional::hasValue'→
16
←
Returning the value 1, which participates in a condition later→
26
←
Calling 'Optional::hasValue'→
31
←
Returning from 'Optional::hasValue'→
32
←
Returning the value 1, which participates in a condition later→
259  bool hasValue() const { return Storage.hasValue(); }
11
←
Calling 'OptionalStorage::hasValue'→
13
←
Returning from 'OptionalStorage::hasValue'→
14
←
Returning the value 1, which participates in a condition later→
27
←
Calling 'OptionalStorage::hasValue'→
29
←
Returning from 'OptionalStorage::hasValue'→
30
←
Returning the value 1, which participates in a condition later→
260  const T *operator->() const { return getPointer(); }
261  T *operator->() { return getPointer(); }
262  const T &operator*() const LLVM_LVALUE_FUNCTION& { return getValue(); }
263  T &operator*() LLVM_LVALUE_FUNCTION& { return getValue(); }
264 
265  template <typename U>
266  constexpr T getValueOr(U &&value) const LLVM_LVALUE_FUNCTION& {
267    return hasValue() ? getValue() : std::forward<U>(value);
268  }
269 
270  /// Apply a function to the value if present; otherwise return None.
271  template <class Function>
272  auto map(const Function &F) const LLVM_LVALUE_FUNCTION&
273      -> Optional<decltype(F(getValue()))> {
274    if (*this) return F(getValue());
275    return None;
276  }
277 
278#if LLVM_HAS_RVALUE_REFERENCE_THIS1
279  T &&getValue() && { return std::move(Storage.getValue()); }
280  T &&operator*() && { return std::move(Storage.getValue()); }
281 
282  template <typename U>
283  T getValueOr(U &&value) && {
284    return hasValue() ? std::move(getValue()) : std::forward<U>(value);
285  }
286 
287  /// Apply a function to the value if present; otherwise return None.
288  template <class Function>
289  auto map(const Function &F) &&
290      -> Optional<decltype(F(std::move(*this).getValue()))> {
291    if (*this) return F(std::move(*this).getValue());
292    return None;
293  }
294#endif
295};
296 
297template <typename T, typename U>
298bool operator==(const Optional<T> &X, const Optional<U> &Y) {
299  if (X && Y)
300    return *X == *Y;
301  return X.hasValue() == Y.hasValue();
302}
303 
304template <typename T, typename U>
305bool operator!=(const Optional<T> &X, const Optional<U> &Y) {
306  return !(X == Y);
307}
308 
309template <typename T, typename U>
310bool operator<(const Optional<T> &X, const Optional<U> &Y) {
311  if (X && Y)
312    return *X < *Y;
313  return X.hasValue() < Y.hasValue();
314}
315 
316template <typename T, typename U>
317bool operator<=(const Optional<T> &X, const Optional<U> &Y) {
318  return !(Y < X);
319}
320 
321template <typename T, typename U>
322bool operator>(const Optional<T> &X, const Optional<U> &Y) {
323  return Y < X;
324}
325 
326template <typename T, typename U>
327bool operator>=(const Optional<T> &X, const Optional<U> &Y) {
328  return !(X < Y);
329}
330 
331template<typename T>
332bool operator==(const Optional<T> &X, NoneType) {
333  return !X;
334}
335 
336template<typename T>
337bool operator==(NoneType, const Optional<T> &X) {
338  return X == None;
339}
340 
341template<typename T>
342bool operator!=(const Optional<T> &X, NoneType) {
343  return !(X == None);
344}
345 
346template<typename T>
347bool operator!=(NoneType, const Optional<T> &X) {
348  return X != None;
349}
350 
351template <typename T> bool operator<(const Optional<T> &X, NoneType) {
352  return false;
353}
354 
355template <typename T> bool operator<(NoneType, const Optional<T> &X) {
356  return X.hasValue();
357}
358 
359template <typename T> bool operator<=(const Optional<T> &X, NoneType) {
360  return !(None < X);
361}
362 
363template <typename T> bool operator<=(NoneType, const Optional<T> &X) {
364  return !(X < None);
365}
366 
367template <typename T> bool operator>(const Optional<T> &X, NoneType) {
368  return None < X;
369}
370 
371template <typename T> bool operator>(NoneType, const Optional<T> &X) {
372  return X < None;
373}
374 
375template <typename T> bool operator>=(const Optional<T> &X, NoneType) {
376  return None <= X;
377}
378 
379template <typename T> bool operator>=(NoneType, const Optional<T> &X) {
380  return X <= None;
381}
382 
383template <typename T> bool operator==(const Optional<T> &X, const T &Y) {
384  return X && *X == Y;
385}
386 
387template <typename T> bool operator==(const T &X, const Optional<T> &Y) {
388  return Y && X == *Y;
389}
390 
391template <typename T> bool operator!=(const Optional<T> &X, const T &Y) {
392  return !(X == Y);
393}
394 
395template <typename T> bool operator!=(const T &X, const Optional<T> &Y) {
396  return !(X == Y);
397}
398 
399template <typename T> bool operator<(const Optional<T> &X, const T &Y) {
400  return !X || *X < Y;
401}
402 
403template <typename T> bool operator<(const T &X, const Optional<T> &Y) {
404  return Y && X < *Y;
405}
406 
407template <typename T> bool operator<=(const Optional<T> &X, const T &Y) {
408  return !(Y < X);
409}
410 
411template <typename T> bool operator<=(const T &X, const Optional<T> &Y) {
412  return !(Y < X);
413}
414 
415template <typename T> bool operator>(const Optional<T> &X, const T &Y) {
416  return Y < X;
417}
418 
419template <typename T> bool operator>(const T &X, const Optional<T> &Y) {
420  return Y < X;
421}
422 
423template <typename T> bool operator>=(const Optional<T> &X, const T &Y) {
424  return !(X < Y);
425}
426 
427template <typename T> bool operator>=(const T &X, const Optional<T> &Y) {
428  return !(X < Y);
429}
430 
431raw_ostream &operator<<(raw_ostream &OS, NoneType);
432 
433template <typename T, typename = decltype(std::declval<raw_ostream &>()
434                                          << std::declval<const T &>())>
435raw_ostream &operator<<(raw_ostream &OS, const Optional<T> &O) {
436  if (O)
437    OS << *O;
438  else
439    OS << None;
440  return OS;
441}
442 
443} // end namespace llvm
444 
445#endif // LLVM_ADT_OPTIONAL_H