/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name MemCpyOptimizer.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 -fhalf-no-semantic-interposition -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/build-llvm/lib/Transforms/Scalar -resource-dir /usr/lib/llvm-13/lib/clang/13.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/build-llvm/include -I /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/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/c++/6.3.0/backward -internal-isystem /usr/lib/llvm-13/lib/clang/13.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../x86_64-linux-gnu/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-13~++20210413100635+64c24f493e5f/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-04-14-063029-18377-1 -x c++ /build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

→

1//===- MemCpyOptimizer.cpp - Optimize use of memcpy and friends -----------===//
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 pass performs various transformations related to eliminating memcpy
10// calls, or transforming sets of stores into memset's.
11//
12//===----------------------------------------------------------------------===//

14#include "llvm/Transforms/Scalar/MemCpyOptimizer.h"
15#include "llvm/ADT/DenseSet.h"
16#include "llvm/ADT/None.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/ADT/Statistic.h"
20#include "llvm/ADT/iterator_range.h"
21#include "llvm/Analysis/AliasAnalysis.h"
22#include "llvm/Analysis/AssumptionCache.h"
23#include "llvm/Analysis/GlobalsModRef.h"
24#include "llvm/Analysis/Loads.h"
25#include "llvm/Analysis/MemoryDependenceAnalysis.h"
26#include "llvm/Analysis/MemoryLocation.h"
27#include "llvm/Analysis/MemorySSA.h"
28#include "llvm/Analysis/MemorySSAUpdater.h"
29#include "llvm/Analysis/TargetLibraryInfo.h"
30#include "llvm/Analysis/ValueTracking.h"
31#include "llvm/IR/Argument.h"
32#include "llvm/IR/BasicBlock.h"
33#include "llvm/IR/Constants.h"
34#include "llvm/IR/DataLayout.h"
35#include "llvm/IR/DerivedTypes.h"
36#include "llvm/IR/Dominators.h"
37#include "llvm/IR/Function.h"
38#include "llvm/IR/GetElementPtrTypeIterator.h"
39#include "llvm/IR/GlobalVariable.h"
40#include "llvm/IR/IRBuilder.h"
41#include "llvm/IR/InstrTypes.h"
42#include "llvm/IR/Instruction.h"
43#include "llvm/IR/Instructions.h"
44#include "llvm/IR/IntrinsicInst.h"
45#include "llvm/IR/Intrinsics.h"
46#include "llvm/IR/LLVMContext.h"
47#include "llvm/IR/Module.h"
48#include "llvm/IR/Operator.h"
49#include "llvm/IR/PassManager.h"
50#include "llvm/IR/Type.h"
51#include "llvm/IR/User.h"
52#include "llvm/IR/Value.h"
53#include "llvm/InitializePasses.h"
54#include "llvm/Pass.h"
55#include "llvm/Support/Casting.h"
56#include "llvm/Support/Debug.h"
57#include "llvm/Support/MathExtras.h"
58#include "llvm/Support/raw_ostream.h"
59#include "llvm/Transforms/Scalar.h"
60#include "llvm/Transforms/Utils/Local.h"
61#include <algorithm>
62#include <cassert>
63#include <cstdint>
64#include <utility>

66using namespace llvm;

68#define DEBUG_TYPE"memcpyopt" "memcpyopt"

70static cl::opt<bool>
  EnableMemorySSA("enable-memcpyopt-memoryssa", cl::init(true), cl::Hidden,
                  cl::desc("Use MemorySSA-backed MemCpyOpt."));

74STATISTIC(NumMemCpyInstr, "Number of memcpy instructions deleted")static llvm::Statistic NumMemCpyInstr = {"memcpyopt", "NumMemCpyInstr"
, "Number of memcpy instructions deleted"};
75STATISTIC(NumMemSetInfer, "Number of memsets inferred")static llvm::Statistic NumMemSetInfer = {"memcpyopt", "NumMemSetInfer"
, "Number of memsets inferred"};
76STATISTIC(NumMoveToCpy,   "Number of memmoves converted to memcpy")static llvm::Statistic NumMoveToCpy = {"memcpyopt", "NumMoveToCpy"
, "Number of memmoves converted to memcpy"};
77STATISTIC(NumCpyToSet,    "Number of memcpys converted to memset")static llvm::Statistic NumCpyToSet = {"memcpyopt", "NumCpyToSet"
, "Number of memcpys converted to memset"};
78STATISTIC(NumCallSlot,    "Number of call slot optimizations performed")static llvm::Statistic NumCallSlot = {"memcpyopt", "NumCallSlot"
, "Number of call slot optimizations performed"};

80namespace {

82/// Represents a range of memset'd bytes with the ByteVal value.
83/// This allows us to analyze stores like:
84///   store 0 -> P+1
85///   store 0 -> P+0
86///   store 0 -> P+3
87///   store 0 -> P+2
88/// which sometimes happens with stores to arrays of structs etc.  When we see
89/// the first store, we make a range [1, 2).  The second store extends the range
90/// to [0, 2).  The third makes a new range [2, 3).  The fourth store joins the
91/// two ranges into [0, 3) which is memset'able.
92struct MemsetRange {
// Start/End - A semi range that describes the span that this range covers.
// The range is closed at the start and open at the end: [Start, End).
int64_t Start, End;

/// StartPtr - The getelementptr instruction that points to the start of the
/// range.
Value *StartPtr;

/// Alignment - The known alignment of the first store.
unsigned Alignment;

/// TheStores - The actual stores that make up this range.
SmallVector<Instruction*, 16> TheStores;

bool isProfitableToUseMemset(const DataLayout &DL) const;
108};

110} // end anonymous namespace

112bool MemsetRange::isProfitableToUseMemset(const DataLayout &DL) const {
// If we found more than 4 stores to merge or 16 bytes, use memset.
if (TheStores.size() >= 4 || End-Start >= 16) return true;

// If there is nothing to merge, don't do anything.
if (TheStores.size() < 2) return false;

// If any of the stores are a memset, then it is always good to extend the
// memset.
for (Instruction *SI : TheStores)
  if (!isa<StoreInst>(SI))
    return true;

// Assume that the code generator is capable of merging pairs of stores
// together if it wants to.
if (TheStores.size() == 2) return false;

// If we have fewer than 8 stores, it can still be worthwhile to do this.
// For example, merging 4 i8 stores into an i32 store is useful almost always.
// However, merging 2 32-bit stores isn't useful on a 32-bit architecture (the
// memset will be split into 2 32-bit stores anyway) and doing so can
// pessimize the llvm optimizer.
//
// Since we don't have perfect knowledge here, make some assumptions: assume
// the maximum GPR width is the same size as the largest legal integer
// size. If so, check to see whether we will end up actually reducing the
// number of stores used.
unsigned Bytes = unsigned(End-Start);
unsigned MaxIntSize = DL.getLargestLegalIntTypeSizeInBits() / 8;
if (MaxIntSize == 0)
  MaxIntSize = 1;
unsigned NumPointerStores = Bytes / MaxIntSize;

// Assume the remaining bytes if any are done a byte at a time.
unsigned NumByteStores = Bytes % MaxIntSize;

// If we will reduce the # stores (according to this heuristic), do the
// transformation.  This encourages merging 4 x i8 -> i32 and 2 x i16 -> i32
// etc.
return TheStores.size() > NumPointerStores+NumByteStores;
152}

154namespace {

156class MemsetRanges {
using range_iterator = SmallVectorImpl<MemsetRange>::iterator;

/// A sorted list of the memset ranges.
SmallVector<MemsetRange, 8> Ranges;

const DataLayout &DL;

164public:
MemsetRanges(const DataLayout &DL) : DL(DL) {}

using const_iterator = SmallVectorImpl<MemsetRange>::const_iterator;

const_iterator begin() const { return Ranges.begin(); }
const_iterator end() const { return Ranges.end(); }
bool empty() const { return Ranges.empty(); }

void addInst(int64_t OffsetFromFirst, Instruction *Inst) {
  if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
    addStore(OffsetFromFirst, SI);
  else
    addMemSet(OffsetFromFirst, cast<MemSetInst>(Inst));
}

void addStore(int64_t OffsetFromFirst, StoreInst *SI) {
  int64_t StoreSize = DL.getTypeStoreSize(SI->getOperand(0)->getType());

  addRange(OffsetFromFirst, StoreSize, SI->getPointerOperand(),
           SI->getAlign().value(), SI);
}

void addMemSet(int64_t OffsetFromFirst, MemSetInst *MSI) {
  int64_t Size = cast<ConstantInt>(MSI->getLength())->getZExtValue();
  addRange(OffsetFromFirst, Size, MSI->getDest(), MSI->getDestAlignment(), MSI);
}

void addRange(int64_t Start, int64_t Size, Value *Ptr,
              unsigned Alignment, Instruction *Inst);
194};

196} // end anonymous namespace

198/// Add a new store to the MemsetRanges data structure.  This adds a
199/// new range for the specified store at the specified offset, merging into
200/// existing ranges as appropriate.
201void MemsetRanges::addRange(int64_t Start, int64_t Size, Value *Ptr,
                          unsigned Alignment, Instruction *Inst) {
int64_t End = Start+Size;

range_iterator I = partition_point(
    Ranges, [=](const MemsetRange &O) { return O.End < Start; });

// We now know that I == E, in which case we didn't find anything to merge
// with, or that Start <= I->End.  If End < I->Start or I == E, then we need
// to insert a new range.  Handle this now.
if (I == Ranges.end() || End < I->Start) {
  MemsetRange &R = *Ranges.insert(I, MemsetRange());
  R.Start        = Start;
  R.End          = End;
  R.StartPtr     = Ptr;
  R.Alignment    = Alignment;
  R.TheStores.push_back(Inst);
  return;
}

// This store overlaps with I, add it.
I->TheStores.push_back(Inst);

// At this point, we may have an interval that completely contains our store.
// If so, just add it to the interval and return.
if (I->Start <= Start && I->End >= End)
  return;

// Now we know that Start <= I->End and End >= I->Start so the range overlaps
// but is not entirely contained within the range.

// See if the range extends the start of the range.  In this case, it couldn't
// possibly cause it to join the prior range, because otherwise we would have
// stopped on *it*.
if (Start < I->Start) {
  I->Start = Start;
  I->StartPtr = Ptr;
  I->Alignment = Alignment;
}

// Now we know that Start <= I->End and Start >= I->Start (so the startpoint
// is in or right at the end of I), and that End >= I->Start.  Extend I out to
// End.
if (End > I->End) {
  I->End = End;
  range_iterator NextI = I;
  while (++NextI != Ranges.end() && End >= NextI->Start) {
    // Merge the range in.
    I->TheStores.append(NextI->TheStores.begin(), NextI->TheStores.end());
    if (NextI->End > I->End)
      I->End = NextI->End;
    Ranges.erase(NextI);
    NextI = I;
  }
}
256}

258//===----------------------------------------------------------------------===//
259//                         MemCpyOptLegacyPass Pass
260//===----------------------------------------------------------------------===//

262namespace {

264class MemCpyOptLegacyPass : public FunctionPass {
MemCpyOptPass Impl;

267public:
static char ID; // Pass identification, replacement for typeid

MemCpyOptLegacyPass() : FunctionPass(ID) {
  initializeMemCpyOptLegacyPassPass(*PassRegistry::getPassRegistry());
}

bool runOnFunction(Function &F) override;

276private:
// This transformation requires dominator postdominator info
void getAnalysisUsage(AnalysisUsage &AU) const override {
  AU.setPreservesCFG();
  AU.addRequired<AssumptionCacheTracker>();
  AU.addRequired<DominatorTreeWrapperPass>();
  AU.addPreserved<DominatorTreeWrapperPass>();
  AU.addPreserved<GlobalsAAWrapperPass>();
  AU.addRequired<TargetLibraryInfoWrapperPass>();
  if (!EnableMemorySSA)
    AU.addRequired<MemoryDependenceWrapperPass>();
  AU.addPreserved<MemoryDependenceWrapperPass>();
  AU.addRequired<AAResultsWrapperPass>();
  AU.addPreserved<AAResultsWrapperPass>();
  if (EnableMemorySSA)
    AU.addRequired<MemorySSAWrapperPass>();
  AU.addPreserved<MemorySSAWrapperPass>();
}
294};

296} // end anonymous namespace

298char MemCpyOptLegacyPass::ID = 0;

300/// The public interface to this file...
301FunctionPass *llvm::createMemCpyOptPass() { return new MemCpyOptLegacyPass(); }

303INITIALIZE_PASS_BEGIN(MemCpyOptLegacyPass, "memcpyopt", "MemCpy Optimization",static void *initializeMemCpyOptLegacyPassPassOnce(PassRegistry
 &Registry) {
                    false, false)static void *initializeMemCpyOptLegacyPassPassOnce(PassRegistry
 &Registry) {
305INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry);
306INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
307INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)initializeMemoryDependenceWrapperPassPass(Registry);
308INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
309INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
310INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)initializeGlobalsAAWrapperPassPass(Registry);
311INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)initializeMemorySSAWrapperPassPass(Registry);
312INITIALIZE_PASS_END(MemCpyOptLegacyPass, "memcpyopt", "MemCpy Optimization",PassInfo *PI = new PassInfo( "MemCpy Optimization", "memcpyopt"
, &MemCpyOptLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<MemCpyOptLegacyPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeMemCpyOptLegacyPassPassFlag
; void llvm::initializeMemCpyOptLegacyPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeMemCpyOptLegacyPassPassFlag
, initializeMemCpyOptLegacyPassPassOnce, std::ref(Registry));
 }
                  false, false)PassInfo *PI = new PassInfo( "MemCpy Optimization", "memcpyopt"
, &MemCpyOptLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<MemCpyOptLegacyPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeMemCpyOptLegacyPassPassFlag
; void llvm::initializeMemCpyOptLegacyPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeMemCpyOptLegacyPassPassFlag
, initializeMemCpyOptLegacyPassPassOnce, std::ref(Registry));
 }

315// Check that V is either not accessible by the caller, or unwinding cannot
316// occur between Start and End.
317static bool mayBeVisibleThroughUnwinding(Value *V, Instruction *Start,
                                       Instruction *End) {
assert(Start->getParent() == End->getParent() && "Must be in same block")((Start->getParent() == End->getParent() && "Must be in same block"
) ? static_cast<void> (0) : __assert_fail ("Start->getParent() == End->getParent() && \"Must be in same block\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 319, __PRETTY_FUNCTION__));
if (!Start->getFunction()->doesNotThrow() &&
    !isa<AllocaInst>(getUnderlyingObject(V))) {
  for (const Instruction &I :
       make_range(Start->getIterator(), End->getIterator())) {
    if (I.mayThrow())
      return true;
  }
}
return false;
329}

331void MemCpyOptPass::eraseInstruction(Instruction *I) {
if (MSSAU)
  MSSAU->removeMemoryAccess(I);
if (MD)
  MD->removeInstruction(I);
I->eraseFromParent();
337}

339// Check for mod or ref of Loc between Start and End, excluding both boundaries.
340// Start and End must be in the same block
341static bool accessedBetween(AliasAnalysis &AA, MemoryLocation Loc,
                          const MemoryUseOrDef *Start,
                          const MemoryUseOrDef *End) {
assert(Start->getBlock() == End->getBlock() && "Only local supported")((Start->getBlock() == End->getBlock() && "Only local supported"
) ? static_cast<void> (0) : __assert_fail ("Start->getBlock() == End->getBlock() && \"Only local supported\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 344, __PRETTY_FUNCTION__));
for (const MemoryAccess &MA :
     make_range(++Start->getIterator(), End->getIterator())) {
  if (isModOrRefSet(AA.getModRefInfo(cast<MemoryUseOrDef>(MA).getMemoryInst(),
                                     Loc)))
    return true;
}
return false;
352}

354// Check for mod of Loc between Start and End, excluding both boundaries.
355// Start and End can be in different blocks.
356static bool writtenBetween(MemorySSA *MSSA, MemoryLocation Loc,
                         const MemoryUseOrDef *Start,
                         const MemoryUseOrDef *End) {
// TODO: Only walk until we hit Start.
MemoryAccess *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(
    End->getDefiningAccess(), Loc);
return !MSSA->dominates(Clobber, Start);
363}

365/// When scanning forward over instructions, we look for some other patterns to
366/// fold away. In particular, this looks for stores to neighboring locations of
367/// memory. If it sees enough consecutive ones, it attempts to merge them
368/// together into a memcpy/memset.
369Instruction *MemCpyOptPass::tryMergingIntoMemset(Instruction *StartInst,
                                               Value *StartPtr,
                                               Value *ByteVal) {
const DataLayout &DL = StartInst->getModule()->getDataLayout();

// Okay, so we now have a single store that can be splatable.  Scan to find
// all subsequent stores of the same value to offset from the same pointer.
// Join these together into ranges, so we can decide whether contiguous blocks
// are stored.
MemsetRanges Ranges(DL);

BasicBlock::iterator BI(StartInst);

// Keeps track of the last memory use or def before the insertion point for
// the new memset. The new MemoryDef for the inserted memsets will be inserted
// after MemInsertPoint. It points to either LastMemDef or to the last user
// before the insertion point of the memset, if there are any such users.
MemoryUseOrDef *MemInsertPoint = nullptr;
// Keeps track of the last MemoryDef between StartInst and the insertion point
// for the new memset. This will become the defining access of the inserted
// memsets.
MemoryDef *LastMemDef = nullptr;
for (++BI; !BI->isTerminator(); ++BI) {
  if (MSSAU) {
    auto *CurrentAcc = cast_or_null<MemoryUseOrDef>(
        MSSAU->getMemorySSA()->getMemoryAccess(&*BI));
    if (CurrentAcc) {
      MemInsertPoint = CurrentAcc;
      if (auto *CurrentDef = dyn_cast<MemoryDef>(CurrentAcc))
        LastMemDef = CurrentDef;
    }
  }

  if (!isa<StoreInst>(BI) && !isa<MemSetInst>(BI)) {
    // If the instruction is readnone, ignore it, otherwise bail out.  We
    // don't even allow readonly here because we don't want something like:
    // A[1] = 2; strlen(A); A[2] = 2; -> memcpy(A, ...); strlen(A).
    if (BI->mayWriteToMemory() || BI->mayReadFromMemory())
      break;
    continue;
  }

  if (StoreInst *NextStore = dyn_cast<StoreInst>(BI)) {
    // If this is a store, see if we can merge it in.
    if (!NextStore->isSimple()) break;

    Value *StoredVal = NextStore->getValueOperand();

    // Don't convert stores of non-integral pointer types to memsets (which
    // stores integers).
    if (DL.isNonIntegralPointerType(StoredVal->getType()->getScalarType()))
      break;

    // Check to see if this stored value is of the same byte-splattable value.
    Value *StoredByte = isBytewiseValue(StoredVal, DL);
    if (isa<UndefValue>(ByteVal) && StoredByte)
      ByteVal = StoredByte;
    if (ByteVal != StoredByte)
      break;

    // Check to see if this store is to a constant offset from the start ptr.
    Optional<int64_t> Offset =
        isPointerOffset(StartPtr, NextStore->getPointerOperand(), DL);
    if (!Offset)
      break;

    Ranges.addStore(*Offset, NextStore);
  } else {
    MemSetInst *MSI = cast<MemSetInst>(BI);

    if (MSI->isVolatile() || ByteVal != MSI->getValue() ||
        !isa<ConstantInt>(MSI->getLength()))
      break;

    // Check to see if this store is to a constant offset from the start ptr.
    Optional<int64_t> Offset = isPointerOffset(StartPtr, MSI->getDest(), DL);
    if (!Offset)
      break;

    Ranges.addMemSet(*Offset, MSI);
  }
}

// If we have no ranges, then we just had a single store with nothing that
// could be merged in.  This is a very common case of course.
if (Ranges.empty())
  return nullptr;

// If we had at least one store that could be merged in, add the starting
// store as well.  We try to avoid this unless there is at least something
// interesting as a small compile-time optimization.
Ranges.addInst(0, StartInst);

// If we create any memsets, we put it right before the first instruction that
// isn't part of the memset block.  This ensure that the memset is dominated
// by any addressing instruction needed by the start of the block.
IRBuilder<> Builder(&*BI);

// Now that we have full information about ranges, loop over the ranges and
// emit memset's for anything big enough to be worthwhile.
Instruction *AMemSet = nullptr;
for (const MemsetRange &Range : Ranges) {
  if (Range.TheStores.size() == 1) continue;

  // If it is profitable to lower this range to memset, do so now.
  if (!Range.isProfitableToUseMemset(DL))
    continue;

  // Otherwise, we do want to transform this!  Create a new memset.
  // Get the starting pointer of the block.
  StartPtr = Range.StartPtr;

  AMemSet = Builder.CreateMemSet(StartPtr, ByteVal, Range.End - Range.Start,
                                 MaybeAlign(Range.Alignment));
  LLVM_DEBUG(dbgs() << "Replace stores:\n"; for (Instruction *SIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Replace stores:\n"; for (Instruction
 *SI : Range.TheStores) dbgs() << *SI << '\n'; dbgs
() << "With: " << *AMemSet << '\n'; } } while
 (false)
                                                 : Range.TheStores) dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Replace stores:\n"; for (Instruction
 *SI : Range.TheStores) dbgs() << *SI << '\n'; dbgs
() << "With: " << *AMemSet << '\n'; } } while
 (false)
                                            << *SI << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Replace stores:\n"; for (Instruction
 *SI : Range.TheStores) dbgs() << *SI << '\n'; dbgs
() << "With: " << *AMemSet << '\n'; } } while
 (false)
             dbgs() << "With: " << *AMemSet << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Replace stores:\n"; for (Instruction
 *SI : Range.TheStores) dbgs() << *SI << '\n'; dbgs
() << "With: " << *AMemSet << '\n'; } } while
 (false);
  if (!Range.TheStores.empty())
    AMemSet->setDebugLoc(Range.TheStores[0]->getDebugLoc());

  if (MSSAU) {
    assert(LastMemDef && MemInsertPoint &&((LastMemDef && MemInsertPoint && "Both LastMemDef and MemInsertPoint need to be set"
) ? static_cast<void> (0) : __assert_fail ("LastMemDef && MemInsertPoint && \"Both LastMemDef and MemInsertPoint need to be set\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 492, __PRETTY_FUNCTION__))
           "Both LastMemDef and MemInsertPoint need to be set")((LastMemDef && MemInsertPoint && "Both LastMemDef and MemInsertPoint need to be set"
) ? static_cast<void> (0) : __assert_fail ("LastMemDef && MemInsertPoint && \"Both LastMemDef and MemInsertPoint need to be set\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 492, __PRETTY_FUNCTION__));
    auto *NewDef =
        cast<MemoryDef>(MemInsertPoint->getMemoryInst() == &*BI
                            ? MSSAU->createMemoryAccessBefore(
                                  AMemSet, LastMemDef, MemInsertPoint)
                            : MSSAU->createMemoryAccessAfter(
                                  AMemSet, LastMemDef, MemInsertPoint));
    MSSAU->insertDef(NewDef, /*RenameUses=*/true);
    LastMemDef = NewDef;
    MemInsertPoint = NewDef;
  }

  // Zap all the stores.
  for (Instruction *SI : Range.TheStores)
    eraseInstruction(SI);

  ++NumMemSetInfer;
}

return AMemSet;
512}

514// This method try to lift a store instruction before position P.
515// It will lift the store and its argument + that anything that
516// may alias with these.
517// The method returns true if it was successful.
518bool MemCpyOptPass::moveUp(StoreInst *SI, Instruction *P, const LoadInst *LI) {
// If the store alias this position, early bail out.
MemoryLocation StoreLoc = MemoryLocation::get(SI);
if (isModOrRefSet(AA->getModRefInfo(P, StoreLoc)))
  return false;

// Keep track of the arguments of all instruction we plan to lift
// so we can make sure to lift them as well if appropriate.
DenseSet<Instruction*> Args;
if (auto *Ptr = dyn_cast<Instruction>(SI->getPointerOperand()))
  if (Ptr->getParent() == SI->getParent())
    Args.insert(Ptr);

// Instruction to lift before P.
SmallVector<Instruction *, 8> ToLift{SI};

// Memory locations of lifted instructions.
SmallVector<MemoryLocation, 8> MemLocs{StoreLoc};

// Lifted calls.
SmallVector<const CallBase *, 8> Calls;

const MemoryLocation LoadLoc = MemoryLocation::get(LI);

for (auto I = --SI->getIterator(), E = P->getIterator(); I != E; --I) {
  auto *C = &*I;

  // Make sure hoisting does not perform a store that was not guaranteed to
  // happen.
  if (!isGuaranteedToTransferExecutionToSuccessor(C))
    return false;

  bool MayAlias = isModOrRefSet(AA->getModRefInfo(C, None));

  bool NeedLift = false;
  if (Args.erase(C))
    NeedLift = true;
  else if (MayAlias) {
    NeedLift = llvm::any_of(MemLocs, [C, this](const MemoryLocation &ML) {
      return isModOrRefSet(AA->getModRefInfo(C, ML));
    });

    if (!NeedLift)
      NeedLift = llvm::any_of(Calls, [C, this](const CallBase *Call) {
        return isModOrRefSet(AA->getModRefInfo(C, Call));
      });
  }

  if (!NeedLift)
    continue;

  if (MayAlias) {
    // Since LI is implicitly moved downwards past the lifted instructions,
    // none of them may modify its source.
    if (isModSet(AA->getModRefInfo(C, LoadLoc)))
      return false;
    else if (const auto *Call = dyn_cast<CallBase>(C)) {
      // If we can't lift this before P, it's game over.
      if (isModOrRefSet(AA->getModRefInfo(P, Call)))
        return false;

      Calls.push_back(Call);
    } else if (isa<LoadInst>(C) || isa<StoreInst>(C) || isa<VAArgInst>(C)) {
      // If we can't lift this before P, it's game over.
      auto ML = MemoryLocation::get(C);
      if (isModOrRefSet(AA->getModRefInfo(P, ML)))
        return false;

      MemLocs.push_back(ML);
    } else
      // We don't know how to lift this instruction.
      return false;
  }

  ToLift.push_back(C);
  for (unsigned k = 0, e = C->getNumOperands(); k != e; ++k)
    if (auto *A = dyn_cast<Instruction>(C->getOperand(k))) {
      if (A->getParent() == SI->getParent()) {
        // Cannot hoist user of P above P
        if(A == P) return false;
        Args.insert(A);
      }
    }
}

// Find MSSA insertion point. Normally P will always have a corresponding
// memory access before which we can insert. However, with non-standard AA
// pipelines, there may be a mismatch between AA and MSSA, in which case we
// will scan for a memory access before P. In either case, we know for sure
// that at least the load will have a memory access.
// TODO: Simplify this once P will be determined by MSSA, in which case the
// discrepancy can no longer occur.
MemoryUseOrDef *MemInsertPoint = nullptr;
if (MSSAU) {
  if (MemoryUseOrDef *MA = MSSAU->getMemorySSA()->getMemoryAccess(P)) {
    MemInsertPoint = cast<MemoryUseOrDef>(--MA->getIterator());
  } else {
    const Instruction *ConstP = P;
    for (const Instruction &I : make_range(++ConstP->getReverseIterator(),
                                           ++LI->getReverseIterator())) {
      if (MemoryUseOrDef *MA = MSSAU->getMemorySSA()->getMemoryAccess(&I)) {
        MemInsertPoint = MA;
        break;
      }
    }
  }
}

// We made it, we need to lift.
for (auto *I : llvm::reverse(ToLift)) {
  LLVM_DEBUG(dbgs() << "Lifting " << *I << " before " << *P << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Lifting " << *I <<
 " before " << *P << "\n"; } } while (false);
  I->moveBefore(P);
  if (MSSAU) {
    assert(MemInsertPoint && "Must have found insert point")((MemInsertPoint && "Must have found insert point") ?
 static_cast<void> (0) : __assert_fail ("MemInsertPoint && \"Must have found insert point\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 631, __PRETTY_FUNCTION__));
    if (MemoryUseOrDef *MA = MSSAU->getMemorySSA()->getMemoryAccess(I)) {
      MSSAU->moveAfter(MA, MemInsertPoint);
      MemInsertPoint = MA;
    }
  }
}

return true;
640}

642bool MemCpyOptPass::processStore(StoreInst *SI, BasicBlock::iterator &BBI) {
if (!SI->isSimple()) return false;

// Avoid merging nontemporal stores since the resulting
// memcpy/memset would not be able to preserve the nontemporal hint.
// In theory we could teach how to propagate the !nontemporal metadata to
// memset calls. However, that change would force the backend to
// conservatively expand !nontemporal memset calls back to sequences of
// store instructions (effectively undoing the merging).
if (SI->getMetadata(LLVMContext::MD_nontemporal))
  return false;

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

Value *StoredVal = SI->getValueOperand();

// Not all the transforms below are correct for non-integral pointers, bail
// until we've audited the individual pieces.
if (DL.isNonIntegralPointerType(StoredVal->getType()->getScalarType()))
  return false;

// Load to store forwarding can be interpreted as memcpy.
if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) {
  if (LI->isSimple() && LI->hasOneUse() &&
      LI->getParent() == SI->getParent()) {

    auto *T = LI->getType();
    if (T->isAggregateType()) {
      MemoryLocation LoadLoc = MemoryLocation::get(LI);

      // We use alias analysis to check if an instruction may store to
      // the memory we load from in between the load and the store. If
      // such an instruction is found, we try to promote there instead
      // of at the store position.
      // TODO: Can use MSSA for this.
      Instruction *P = SI;
      for (auto &I : make_range(++LI->getIterator(), SI->getIterator())) {
        if (isModSet(AA->getModRefInfo(&I, LoadLoc))) {
          P = &I;
          break;
        }
      }

      // We found an instruction that may write to the loaded memory.
      // We can try to promote at this position instead of the store
      // position if nothing alias the store memory after this and the store
      // destination is not in the range.
      if (P && P != SI) {
        if (!moveUp(SI, P, LI))
          P = nullptr;
      }

      // If a valid insertion position is found, then we can promote
      // the load/store pair to a memcpy.
      if (P) {
        // If we load from memory that may alias the memory we store to,
        // memmove must be used to preserve semantic. If not, memcpy can
        // be used.
        bool UseMemMove = false;
        if (!AA->isNoAlias(MemoryLocation::get(SI), LoadLoc))
          UseMemMove = true;

        uint64_t Size = DL.getTypeStoreSize(T);

        IRBuilder<> Builder(P);
        Instruction *M;
        if (UseMemMove)
          M = Builder.CreateMemMove(
              SI->getPointerOperand(), SI->getAlign(),
              LI->getPointerOperand(), LI->getAlign(), Size);
        else
          M = Builder.CreateMemCpy(
              SI->getPointerOperand(), SI->getAlign(),
              LI->getPointerOperand(), LI->getAlign(), Size);

        LLVM_DEBUG(dbgs() << "Promoting " << *LI << " to " << *SI << " => "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Promoting " << *LI <<
 " to " << *SI << " => " << *M << "\n"
; } } while (false)
                          << *M << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Promoting " << *LI <<
 " to " << *SI << " => " << *M << "\n"
; } } while (false);

        if (MSSAU) {
          auto *LastDef =
              cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(SI));
          auto *NewAccess =
              MSSAU->createMemoryAccessAfter(M, LastDef, LastDef);
          MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
        }

        eraseInstruction(SI);
        eraseInstruction(LI);
        ++NumMemCpyInstr;

        // Make sure we do not invalidate the iterator.
        BBI = M->getIterator();
        return true;
      }
    }

    // Detect cases where we're performing call slot forwarding, but
    // happen to be using a load-store pair to implement it, rather than
    // a memcpy.
    CallInst *C = nullptr;
    if (EnableMemorySSA) {
      if (auto *LoadClobber = dyn_cast<MemoryUseOrDef>(
              MSSA->getWalker()->getClobberingMemoryAccess(LI))) {
        // The load most post-dom the call. Limit to the same block for now.
        // TODO: Support non-local call-slot optimization?
        if (LoadClobber->getBlock() == SI->getParent())
          C = dyn_cast_or_null<CallInst>(LoadClobber->getMemoryInst());
      }
    } else {
      MemDepResult ldep = MD->getDependency(LI);
      if (ldep.isClobber() && !isa<MemCpyInst>(ldep.getInst()))
        C = dyn_cast<CallInst>(ldep.getInst());
    }

    if (C) {
      // Check that nothing touches the dest of the "copy" between
      // the call and the store.
      MemoryLocation StoreLoc = MemoryLocation::get(SI);
      if (EnableMemorySSA) {
        if (accessedBetween(*AA, StoreLoc, MSSA->getMemoryAccess(C),
                            MSSA->getMemoryAccess(SI)))
          C = nullptr;
      } else {
        for (BasicBlock::iterator I = --SI->getIterator(),
                                  E = C->getIterator();
             I != E; --I) {
          if (isModOrRefSet(AA->getModRefInfo(&*I, StoreLoc))) {
            C = nullptr;
            break;
          }
        }
      }
    }

    if (C) {
      bool changed = performCallSlotOptzn(
          LI, SI, SI->getPointerOperand()->stripPointerCasts(),
          LI->getPointerOperand()->stripPointerCasts(),
          DL.getTypeStoreSize(SI->getOperand(0)->getType()),
          commonAlignment(SI->getAlign(), LI->getAlign()), C);
      if (changed) {
        eraseInstruction(SI);
        eraseInstruction(LI);
        ++NumMemCpyInstr;
        return true;
      }
    }
  }
}

// There are two cases that are interesting for this code to handle: memcpy
// and memset.  Right now we only handle memset.

// Ensure that the value being stored is something that can be memset'able a
// byte at a time like "0" or "-1" or any width, as well as things like
// 0xA0A0A0A0 and 0.0.
auto *V = SI->getOperand(0);
if (Value *ByteVal = isBytewiseValue(V, DL)) {
  if (Instruction *I = tryMergingIntoMemset(SI, SI->getPointerOperand(),
                                            ByteVal)) {
    BBI = I->getIterator(); // Don't invalidate iterator.
    return true;
  }

  // If we have an aggregate, we try to promote it to memset regardless
  // of opportunity for merging as it can expose optimization opportunities
  // in subsequent passes.
  auto *T = V->getType();
  if (T->isAggregateType()) {
    uint64_t Size = DL.getTypeStoreSize(T);
    IRBuilder<> Builder(SI);
    auto *M = Builder.CreateMemSet(SI->getPointerOperand(), ByteVal, Size,
                                   SI->getAlign());

    LLVM_DEBUG(dbgs() << "Promoting " << *SI << " to " << *M << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Promoting " << *SI <<
 " to " << *M << "\n"; } } while (false);

    if (MSSAU) {
      assert(isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(SI)))((isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess
(SI))) ? static_cast<void> (0) : __assert_fail ("isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(SI))"
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 819, __PRETTY_FUNCTION__));
      auto *LastDef =
          cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(SI));
      auto *NewAccess = MSSAU->createMemoryAccessAfter(M, LastDef, LastDef);
      MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
    }

    eraseInstruction(SI);
    NumMemSetInfer++;

    // Make sure we do not invalidate the iterator.
    BBI = M->getIterator();
    return true;
  }
}

return false;
836}

838bool MemCpyOptPass::processMemSet(MemSetInst *MSI, BasicBlock::iterator &BBI) {
// See if there is another memset or store neighboring this memset which
// allows us to widen out the memset to do a single larger store.
if (isa<ConstantInt>(MSI->getLength()) && !MSI->isVolatile())
  if (Instruction *I = tryMergingIntoMemset(MSI, MSI->getDest(),
                                            MSI->getValue())) {
    BBI = I->getIterator(); // Don't invalidate iterator.
    return true;
  }
return false;
848}

850/// Takes a memcpy and a call that it depends on,
851/// and checks for the possibility of a call slot optimization by having
852/// the call write its result directly into the destination of the memcpy.
853bool MemCpyOptPass::performCallSlotOptzn(Instruction *cpyLoad,
                                       Instruction *cpyStore, Value *cpyDest,
                                       Value *cpySrc, uint64_t cpyLen,
                                       Align cpyAlign, CallInst *C) {
// The general transformation to keep in mind is
//
//   call @func(..., src, ...)
//   memcpy(dest, src, ...)
//
// ->
//
//   memcpy(dest, src, ...)
//   call @func(..., dest, ...)
//
// Since moving the memcpy is technically awkward, we additionally check that
// src only holds uninitialized values at the moment of the call, meaning that
// the memcpy can be discarded rather than moved.

// Lifetime marks shouldn't be operated on.
if (Function *F = C->getCalledFunction())
  if (F->isIntrinsic() && F->getIntrinsicID() == Intrinsic::lifetime_start)
    return false;

// Require that src be an alloca.  This simplifies the reasoning considerably.
AllocaInst *srcAlloca = dyn_cast<AllocaInst>(cpySrc);
if (!srcAlloca)
  return false;

ConstantInt *srcArraySize = dyn_cast<ConstantInt>(srcAlloca->getArraySize());
if (!srcArraySize)
  return false;

const DataLayout &DL = cpyLoad->getModule()->getDataLayout();
uint64_t srcSize = DL.getTypeAllocSize(srcAlloca->getAllocatedType()) *
                   srcArraySize->getZExtValue();

if (cpyLen < srcSize)
  return false;

// Check that accessing the first srcSize bytes of dest will not cause a
// trap.  Otherwise the transform is invalid since it might cause a trap
// to occur earlier than it otherwise would.
if (!isDereferenceableAndAlignedPointer(cpyDest, Align(1), APInt(64, cpyLen),
                                        DL, C, DT))
  return false;

// Make sure that nothing can observe cpyDest being written early. There are
// a number of cases to consider:
//  1. cpyDest cannot be accessed between C and cpyStore as a precondition of
//     the transform.
//  2. C itself may not access cpyDest (prior to the transform). This is
//     checked further below.
//  3. If cpyDest is accessible to the caller of this function (potentially
//     captured and not based on an alloca), we need to ensure that we cannot
//     unwind between C and cpyStore. This is checked here.
//  4. If cpyDest is potentially captured, there may be accesses to it from
//     another thread. In this case, we need to check that cpyStore is
//     guaranteed to be executed if C is. As it is a non-atomic access, it
//     renders accesses from other threads undefined.
//     TODO: This is currently not checked.
if (mayBeVisibleThroughUnwinding(cpyDest, C, cpyStore))
  return false;

// Check that dest points to memory that is at least as aligned as src.
Align srcAlign = srcAlloca->getAlign();
bool isDestSufficientlyAligned = srcAlign <= cpyAlign;
// If dest is not aligned enough and we can't increase its alignment then
// bail out.
if (!isDestSufficientlyAligned && !isa<AllocaInst>(cpyDest))
  return false;

// Check that src is not accessed except via the call and the memcpy.  This
// guarantees that it holds only undefined values when passed in (so the final
// memcpy can be dropped), that it is not read or written between the call and
// the memcpy, and that writing beyond the end of it is undefined.
SmallVector<User *, 8> srcUseList(srcAlloca->users());
while (!srcUseList.empty()) {
  User *U = srcUseList.pop_back_val();

  if (isa<BitCastInst>(U) || isa<AddrSpaceCastInst>(U)) {
    append_range(srcUseList, U->users());
    continue;
  }
  if (GetElementPtrInst *G = dyn_cast<GetElementPtrInst>(U)) {
    if (!G->hasAllZeroIndices())
      return false;

    append_range(srcUseList, U->users());
    continue;
  }
  if (const IntrinsicInst *IT = dyn_cast<IntrinsicInst>(U))
    if (IT->isLifetimeStartOrEnd())
      continue;

  if (U != C && U != cpyLoad)
    return false;
}

// Check that src isn't captured by the called function since the
// transformation can cause aliasing issues in that case.
for (unsigned ArgI = 0, E = C->arg_size(); ArgI != E; ++ArgI)
  if (C->getArgOperand(ArgI) == cpySrc && !C->doesNotCapture(ArgI))
    return false;

// Since we're changing the parameter to the callsite, we need to make sure
// that what would be the new parameter dominates the callsite.
if (!DT->dominates(cpyDest, C)) {
  // Support moving a constant index GEP before the call.
  auto *GEP = dyn_cast<GetElementPtrInst>(cpyDest);
  if (GEP && GEP->hasAllConstantIndices() &&
      DT->dominates(GEP->getPointerOperand(), C))
    GEP->moveBefore(C);
  else
    return false;
}

// In addition to knowing that the call does not access src in some
// unexpected manner, for example via a global, which we deduce from
// the use analysis, we also need to know that it does not sneakily
// access dest.  We rely on AA to figure this out for us.
ModRefInfo MR = AA->getModRefInfo(C, cpyDest, LocationSize::precise(srcSize));
// If necessary, perform additional analysis.
if (isModOrRefSet(MR))
  MR = AA->callCapturesBefore(C, cpyDest, LocationSize::precise(srcSize), DT);
if (isModOrRefSet(MR))
  return false;

// We can't create address space casts here because we don't know if they're
// safe for the target.
if (cpySrc->getType()->getPointerAddressSpace() !=
    cpyDest->getType()->getPointerAddressSpace())
  return false;
for (unsigned ArgI = 0; ArgI < C->arg_size(); ++ArgI)
  if (C->getArgOperand(ArgI)->stripPointerCasts() == cpySrc &&
      cpySrc->getType()->getPointerAddressSpace() !=
          C->getArgOperand(ArgI)->getType()->getPointerAddressSpace())
    return false;

// All the checks have passed, so do the transformation.
bool changedArgument = false;
for (unsigned ArgI = 0; ArgI < C->arg_size(); ++ArgI)
  if (C->getArgOperand(ArgI)->stripPointerCasts() == cpySrc) {
    Value *Dest = cpySrc->getType() == cpyDest->getType() ?  cpyDest
      : CastInst::CreatePointerCast(cpyDest, cpySrc->getType(),
                                    cpyDest->getName(), C);
    changedArgument = true;
    if (C->getArgOperand(ArgI)->getType() == Dest->getType())
      C->setArgOperand(ArgI, Dest);
    else
      C->setArgOperand(ArgI, CastInst::CreatePointerCast(
                                 Dest, C->getArgOperand(ArgI)->getType(),
                                 Dest->getName(), C));
  }

if (!changedArgument)
  return false;

// If the destination wasn't sufficiently aligned then increase its alignment.
if (!isDestSufficientlyAligned) {
  assert(isa<AllocaInst>(cpyDest) && "Can only increase alloca alignment!")((isa<AllocaInst>(cpyDest) && "Can only increase alloca alignment!"
) ? static_cast<void> (0) : __assert_fail ("isa<AllocaInst>(cpyDest) && \"Can only increase alloca alignment!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 1012, __PRETTY_FUNCTION__));
  cast<AllocaInst>(cpyDest)->setAlignment(srcAlign);
}

// Drop any cached information about the call, because we may have changed
// its dependence information by changing its parameter.
if (MD)
  MD->removeInstruction(C);

// Update AA metadata
// FIXME: MD_tbaa_struct and MD_mem_parallel_loop_access should also be
// handled here, but combineMetadata doesn't support them yet
unsigned KnownIDs[] = {LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
                       LLVMContext::MD_noalias,
                       LLVMContext::MD_invariant_group,
                       LLVMContext::MD_access_group};
combineMetadata(C, cpyLoad, KnownIDs, true);

++NumCallSlot;
return true;
1032}

1034/// We've found that the (upward scanning) memory dependence of memcpy 'M' is
1035/// the memcpy 'MDep'. Try to simplify M to copy from MDep's input if we can.
1036bool MemCpyOptPass::processMemCpyMemCpyDependence(MemCpyInst *M,
                                                MemCpyInst *MDep) {
// We can only transforms memcpy's where the dest of one is the source of the
// other.
if (M->getSource() != MDep->getDest() || MDep->isVolatile())
  return false;

// If dep instruction is reading from our current input, then it is a noop
// transfer and substituting the input won't change this instruction.  Just
// ignore the input and let someone else zap MDep.  This handles cases like:
//    memcpy(a <- a)
//    memcpy(b <- a)
if (M->getSource() == MDep->getSource())
  return false;

// Second, the length of the memcpy's must be the same, or the preceding one
// must be larger than the following one.
ConstantInt *MDepLen = dyn_cast<ConstantInt>(MDep->getLength());
ConstantInt *MLen = dyn_cast<ConstantInt>(M->getLength());
if (!MDepLen || !MLen || MDepLen->getZExtValue() < MLen->getZExtValue())
  return false;

// Verify that the copied-from memory doesn't change in between the two
// transfers.  For example, in:
//    memcpy(a <- b)
//    *b = 42;
//    memcpy(c <- a)
// It would be invalid to transform the second memcpy into memcpy(c <- b).
//
// TODO: If the code between M and MDep is transparent to the destination "c",
// then we could still perform the xform by moving M up to the first memcpy.
if (EnableMemorySSA) {
  // TODO: It would be sufficient to check the MDep source up to the memcpy
  // size of M, rather than MDep.
  if (writtenBetween(MSSA, MemoryLocation::getForSource(MDep),
                     MSSA->getMemoryAccess(MDep), MSSA->getMemoryAccess(M)))
    return false;
} else {
  // NOTE: This is conservative, it will stop on any read from the source loc,
  // not just the defining memcpy.
  MemDepResult SourceDep =
      MD->getPointerDependencyFrom(MemoryLocation::getForSource(MDep), false,
                                   M->getIterator(), M->getParent());
  if (!SourceDep.isClobber() || SourceDep.getInst() != MDep)
    return false;
}

// If the dest of the second might alias the source of the first, then the
// source and dest might overlap.  We still want to eliminate the intermediate
// value, but we have to generate a memmove instead of memcpy.
bool UseMemMove = false;
if (!AA->isNoAlias(MemoryLocation::getForDest(M),
                   MemoryLocation::getForSource(MDep)))
  UseMemMove = true;

// If all checks passed, then we can transform M.
LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy->memcpy src:\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "MemCpyOptPass: Forwarding memcpy->memcpy src:\n"
 << *MDep << '\n' << *M << '\n'; } } while
 (false)
                  << *MDep << '\n' << *M << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "MemCpyOptPass: Forwarding memcpy->memcpy src:\n"
 << *MDep << '\n' << *M << '\n'; } } while
 (false);

// TODO: Is this worth it if we're creating a less aligned memcpy? For
// example we could be moving from movaps -> movq on x86.
IRBuilder<> Builder(M);
Instruction *NewM;
if (UseMemMove)
  NewM = Builder.CreateMemMove(M->getRawDest(), M->getDestAlign(),
                               MDep->getRawSource(), MDep->getSourceAlign(),
                               M->getLength(), M->isVolatile());
else
  NewM = Builder.CreateMemCpy(M->getRawDest(), M->getDestAlign(),
                              MDep->getRawSource(), MDep->getSourceAlign(),
                              M->getLength(), M->isVolatile());

if (MSSAU) {
  assert(isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(M)))((isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess
(M))) ? static_cast<void> (0) : __assert_fail ("isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(M))"
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 1109, __PRETTY_FUNCTION__));
  auto *LastDef = cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(M));
  auto *NewAccess = MSSAU->createMemoryAccessAfter(NewM, LastDef, LastDef);
  MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
}

// Remove the instruction we're replacing.
eraseInstruction(M);
++NumMemCpyInstr;
return true;
1119}

1121/// We've found that the (upward scanning) memory dependence of \p MemCpy is
1122/// \p MemSet.  Try to simplify \p MemSet to only set the trailing bytes that
1123/// weren't copied over by \p MemCpy.
1124///
1125/// In other words, transform:
1126/// \code
1127///   memset(dst, c, dst_size);
1128///   memcpy(dst, src, src_size);
1129/// \endcode
1130/// into:
1131/// \code
1132///   memcpy(dst, src, src_size);
1133///   memset(dst + src_size, c, dst_size <= src_size ? 0 : dst_size - src_size);
1134/// \endcode
1135bool MemCpyOptPass::processMemSetMemCpyDependence(MemCpyInst *MemCpy,
                                                MemSetInst *MemSet) {
// We can only transform memset/memcpy with the same destination.
if (!AA->isMustAlias(MemSet->getDest(), MemCpy->getDest()))
  return false;

// Check that src and dst of the memcpy aren't the same. While memcpy
// operands cannot partially overlap, exact equality is allowed.
if (!AA->isNoAlias(MemoryLocation(MemCpy->getSource(),
                                  LocationSize::precise(1)),
                   MemoryLocation(MemCpy->getDest(),
                                  LocationSize::precise(1))))
  return false;

if (EnableMemorySSA) {
  // We know that dst up to src_size is not written. We now need to make sure
  // that dst up to dst_size is not accessed. (If we did not move the memset,
  // checking for reads would be sufficient.)
  if (accessedBetween(*AA, MemoryLocation::getForDest(MemSet),
                      MSSA->getMemoryAccess(MemSet),
                      MSSA->getMemoryAccess(MemCpy))) {
    return false;
  }
} else {
  // We have already checked that dst up to src_size is not accessed. We
  // need to make sure that there are no accesses up to dst_size either.
  MemDepResult DstDepInfo = MD->getPointerDependencyFrom(
      MemoryLocation::getForDest(MemSet), false, MemCpy->getIterator(),
      MemCpy->getParent());
  if (DstDepInfo.getInst() != MemSet)
    return false;
}

// Use the same i8* dest as the memcpy, killing the memset dest if different.
Value *Dest = MemCpy->getRawDest();
Value *DestSize = MemSet->getLength();
Value *SrcSize = MemCpy->getLength();

if (mayBeVisibleThroughUnwinding(Dest, MemSet, MemCpy))
  return false;

// If the sizes are the same, simply drop the memset instead of generating
// a replacement with zero size.
if (DestSize == SrcSize) {
  eraseInstruction(MemSet);
  return true;
}

// By default, create an unaligned memset.
unsigned Align = 1;
// If Dest is aligned, and SrcSize is constant, use the minimum alignment
// of the sum.
const unsigned DestAlign =
    std::max(MemSet->getDestAlignment(), MemCpy->getDestAlignment());
if (DestAlign > 1)
  if (ConstantInt *SrcSizeC = dyn_cast<ConstantInt>(SrcSize))
    Align = MinAlign(SrcSizeC->getZExtValue(), DestAlign);

IRBuilder<> Builder(MemCpy);

// If the sizes have different types, zext the smaller one.
if (DestSize->getType() != SrcSize->getType()) {
  if (DestSize->getType()->getIntegerBitWidth() >
      SrcSize->getType()->getIntegerBitWidth())
    SrcSize = Builder.CreateZExt(SrcSize, DestSize->getType());
  else
    DestSize = Builder.CreateZExt(DestSize, SrcSize->getType());
}

Value *Ule = Builder.CreateICmpULE(DestSize, SrcSize);
Value *SizeDiff = Builder.CreateSub(DestSize, SrcSize);
Value *MemsetLen = Builder.CreateSelect(
    Ule, ConstantInt::getNullValue(DestSize->getType()), SizeDiff);
Instruction *NewMemSet = Builder.CreateMemSet(
    Builder.CreateGEP(Dest->getType()->getPointerElementType(), Dest,
                      SrcSize),
    MemSet->getOperand(1), MemsetLen, MaybeAlign(Align));

if (MSSAU) {
  assert(isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy)) &&((isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess
(MemCpy)) && "MemCpy must be a MemoryDef") ? static_cast
<void> (0) : __assert_fail ("isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy)) && \"MemCpy must be a MemoryDef\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 1215, __PRETTY_FUNCTION__))
         "MemCpy must be a MemoryDef")((isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess
(MemCpy)) && "MemCpy must be a MemoryDef") ? static_cast
<void> (0) : __assert_fail ("isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy)) && \"MemCpy must be a MemoryDef\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 1215, __PRETTY_FUNCTION__));
  // The new memset is inserted after the memcpy, but it is known that its
  // defining access is the memset about to be removed which immediately
  // precedes the memcpy.
  auto *LastDef =
      cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy));
  auto *NewAccess = MSSAU->createMemoryAccessBefore(
      NewMemSet, LastDef->getDefiningAccess(), LastDef);
  MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
}

eraseInstruction(MemSet);
return true;
1228}

1230/// Determine whether the instruction has undefined content for the given Size,
1231/// either because it was freshly alloca'd or started its lifetime.
1232static bool hasUndefContents(Instruction *I, ConstantInt *Size) {
if (isa<AllocaInst>(I))
  return true;

if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
  if (II->getIntrinsicID() == Intrinsic::lifetime_start)
    if (ConstantInt *LTSize = dyn_cast<ConstantInt>(II->getArgOperand(0)))
      if (LTSize->getZExtValue() >= Size->getZExtValue())
        return true;

return false;
1243}

1245static bool hasUndefContentsMSSA(MemorySSA *MSSA, AliasAnalysis *AA, Value *V,
                               MemoryDef *Def, ConstantInt *Size) {
if (MSSA->isLiveOnEntryDef(Def))
11
←
Calling 'MemorySSA::isLiveOnEntryDef'→
14
←
Returning from 'MemorySSA::isLiveOnEntryDef'→
15
←
Taking false branch→
  return isa<AllocaInst>(getUnderlyingObject(V));

if (IntrinsicInst *II16.1
'II' is non-null
1
'II' is non-null
1
'II' is non-null
 =
17
←
Taking true branch→
        dyn_cast_or_null<IntrinsicInst>(Def->getMemoryInst())) {
16
←
Assuming the object is a 'IntrinsicInst'→
  if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
18
←
Assuming the condition is true→
19
←
Taking true branch→
    ConstantInt *LTSize = cast<ConstantInt>(II->getArgOperand(0));
    if (AA->isMustAlias(V, II->getArgOperand(1)) &&
20
←
Calling 'AAResults::isMustAlias'→
23
←
Returning from 'AAResults::isMustAlias'→
        LTSize->getZExtValue() >= Size->getZExtValue())
      return true;

    // If the lifetime.start covers a whole alloca (as it almost always does)
    // and we're querying a pointer based on that alloca, then we know the
    // memory is definitely undef, regardless of how exactly we alias. The
    // size also doesn't matter, as an out-of-bounds access would be UB.
    AllocaInst *Alloca = dyn_cast<AllocaInst>(getUnderlyingObject(V));
24
←
Assuming the object is not a 'AllocaInst'→
25
←
'Alloca' initialized to a null pointer value→
    if (getUnderlyingObject(II->getArgOperand(1)) == Alloca) {
26
←
Assuming the condition is true→
27
←
Taking true branch→
      DataLayout DL = Alloca->getModule()->getDataLayout();
28
←
Called C++ object pointer is null
      if (Optional<TypeSize> AllocaSize = Alloca->getAllocationSizeInBits(DL))
        if (*AllocaSize == LTSize->getValue() * 8)
          return true;
    }
  }
}

return false;
1273}

1275/// Transform memcpy to memset when its source was just memset.
1276/// In other words, turn:
1277/// \code
1278///   memset(dst1, c, dst1_size);
1279///   memcpy(dst2, dst1, dst2_size);
1280/// \endcode
1281/// into:
1282/// \code
1283///   memset(dst1, c, dst1_size);
1284///   memset(dst2, c, dst2_size);
1285/// \endcode
1286/// When dst2_size <= dst1_size.
1287///
1288/// The \p MemCpy must have a Constant length.
1289bool MemCpyOptPass::performMemCpyToMemSetOptzn(MemCpyInst *MemCpy,
                                             MemSetInst *MemSet) {
// Make sure that memcpy(..., memset(...), ...), that is we are memsetting and
// memcpying from the same address. Otherwise it is hard to reason about.
if (!AA->isMustAlias(MemSet->getRawDest(), MemCpy->getRawSource()))
1
Taking false branch→
  return false;

// A known memset size is required.
ConstantInt *MemSetSize = dyn_cast<ConstantInt>(MemSet->getLength());
if (!MemSetSize)
2
←
Assuming 'MemSetSize' is non-null→
3
←
Taking false branch→
  return false;

// Make sure the memcpy doesn't read any more than what the memset wrote.
// Don't worry about sizes larger than i64.
ConstantInt *CopySize = cast<ConstantInt>(MemCpy->getLength());
if (CopySize->getZExtValue() > MemSetSize->getZExtValue()) {
4
←
Assuming the condition is true→
5
←
Taking true branch→
  // If the memcpy is larger than the memset, but the memory was undef prior
  // to the memset, we can just ignore the tail. Technically we're only
  // interested in the bytes from MemSetSize..CopySize here, but as we can't
  // easily represent this location, we use the full 0..CopySize range.
  MemoryLocation MemCpyLoc = MemoryLocation::getForSource(MemCpy);
  bool CanReduceSize = false;
  if (EnableMemorySSA) {
6
←
Assuming the condition is true→
7
←
Taking true branch→
    MemoryUseOrDef *MemSetAccess = MSSA->getMemoryAccess(MemSet);
    MemoryAccess *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(
        MemSetAccess->getDefiningAccess(), MemCpyLoc);
    if (auto *MD8.1
'MD' is non-null
1
'MD' is non-null
1
'MD' is non-null
 = dyn_cast<MemoryDef>(Clobber))
8
←
Assuming 'Clobber' is a 'MemoryDef'→
9
←
Taking true branch→
      if (hasUndefContentsMSSA(MSSA, AA, MemCpy->getSource(), MD, CopySize))
10
←
Calling 'hasUndefContentsMSSA'→
        CanReduceSize = true;
  } else {
    MemDepResult DepInfo = MD->getPointerDependencyFrom(
        MemCpyLoc, true, MemSet->getIterator(), MemSet->getParent());
    if (DepInfo.isDef() && hasUndefContents(DepInfo.getInst(), CopySize))
      CanReduceSize = true;
  }

  if (!CanReduceSize)
    return false;
  CopySize = MemSetSize;
}

IRBuilder<> Builder(MemCpy);
Instruction *NewM =
    Builder.CreateMemSet(MemCpy->getRawDest(), MemSet->getOperand(1),
                         CopySize, MaybeAlign(MemCpy->getDestAlignment()));
if (MSSAU) {
  auto *LastDef =
      cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy));
  auto *NewAccess = MSSAU->createMemoryAccessAfter(NewM, LastDef, LastDef);
  MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
}

return true;
1342}

1344/// Perform simplification of memcpy's.  If we have memcpy A
1345/// which copies X to Y, and memcpy B which copies Y to Z, then we can rewrite
1346/// B to be a memcpy from X to Z (or potentially a memmove, depending on
1347/// circumstances). This allows later passes to remove the first memcpy
1348/// altogether.
1349bool MemCpyOptPass::processMemCpy(MemCpyInst *M, BasicBlock::iterator &BBI) {
// We can only optimize non-volatile memcpy's.
if (M->isVolatile()) return false;

// If the source and destination of the memcpy are the same, then zap it.
if (M->getSource() == M->getDest()) {
  ++BBI;
  eraseInstruction(M);
  return true;
}

// If copying from a constant, try to turn the memcpy into a memset.
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getSource()))
  if (GV->isConstant() && GV->hasDefinitiveInitializer())
    if (Value *ByteVal = isBytewiseValue(GV->getInitializer(),
                                         M->getModule()->getDataLayout())) {
      IRBuilder<> Builder(M);
      Instruction *NewM =
          Builder.CreateMemSet(M->getRawDest(), ByteVal, M->getLength(),
                               MaybeAlign(M->getDestAlignment()), false);
      if (MSSAU) {
        auto *LastDef =
            cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(M));
        auto *NewAccess =
            MSSAU->createMemoryAccessAfter(NewM, LastDef, LastDef);
        MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
      }

      eraseInstruction(M);
      ++NumCpyToSet;
      return true;
    }

if (EnableMemorySSA) {
  MemoryUseOrDef *MA = MSSA->getMemoryAccess(M);
  MemoryAccess *AnyClobber = MSSA->getWalker()->getClobberingMemoryAccess(MA);
  MemoryLocation DestLoc = MemoryLocation::getForDest(M);
  const MemoryAccess *DestClobber =
      MSSA->getWalker()->getClobberingMemoryAccess(AnyClobber, DestLoc);

  // Try to turn a partially redundant memset + memcpy into
  // memcpy + smaller memset.  We don't need the memcpy size for this.
  // The memcpy most post-dom the memset, so limit this to the same basic
  // block. A non-local generalization is likely not worthwhile.
  if (auto *MD = dyn_cast<MemoryDef>(DestClobber))
    if (auto *MDep = dyn_cast_or_null<MemSetInst>(MD->getMemoryInst()))
      if (DestClobber->getBlock() == M->getParent())
        if (processMemSetMemCpyDependence(M, MDep))
          return true;

  // The optimizations after this point require the memcpy size.
  ConstantInt *CopySize = dyn_cast<ConstantInt>(M->getLength());
  if (!CopySize) return false;

  MemoryAccess *SrcClobber = MSSA->getWalker()->getClobberingMemoryAccess(
      AnyClobber, MemoryLocation::getForSource(M));

  // There are four possible optimizations we can do for memcpy:
  //   a) memcpy-memcpy xform which exposes redundance for DSE.
  //   b) call-memcpy xform for return slot optimization.
  //   c) memcpy from freshly alloca'd space or space that has just started
  //      its lifetime copies undefined data, and we can therefore eliminate
  //      the memcpy in favor of the data that was already at the destination.
  //   d) memcpy from a just-memset'd source can be turned into memset.
  if (auto *MD = dyn_cast<MemoryDef>(SrcClobber)) {
    if (Instruction *MI = MD->getMemoryInst()) {
      if (auto *C = dyn_cast<CallInst>(MI)) {
        // The memcpy must post-dom the call. Limit to the same block for now.
        // Additionally, we need to ensure that there are no accesses to dest
        // between the call and the memcpy. Accesses to src will be checked
        // by performCallSlotOptzn().
        // TODO: Support non-local call-slot optimization?
        if (C->getParent() == M->getParent() &&
            !accessedBetween(*AA, DestLoc, MD, MA)) {
          // FIXME: Can we pass in either of dest/src alignment here instead
          // of conservatively taking the minimum?
          Align Alignment = std::min(M->getDestAlign().valueOrOne(),
                                     M->getSourceAlign().valueOrOne());
          if (performCallSlotOptzn(M, M, M->getDest(), M->getSource(),
                                   CopySize->getZExtValue(), Alignment, C)) {
            LLVM_DEBUG(dbgs() << "Performed call slot optimization:\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Performed call slot optimization:\n"
 << "    call: " << *C << "\n" << "    memcpy: "
 << *M << "\n"; } } while (false)
                              << "    call: " << *C << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Performed call slot optimization:\n"
 << "    call: " << *C << "\n" << "    memcpy: "
 << *M << "\n"; } } while (false)
                              << "    memcpy: " << *M << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Performed call slot optimization:\n"
 << "    call: " << *C << "\n" << "    memcpy: "
 << *M << "\n"; } } while (false);
            eraseInstruction(M);
            ++NumMemCpyInstr;
            return true;
          }
        }
      }
      if (auto *MDep = dyn_cast<MemCpyInst>(MI))
        return processMemCpyMemCpyDependence(M, MDep);
      if (auto *MDep = dyn_cast<MemSetInst>(MI)) {
        if (performMemCpyToMemSetOptzn(M, MDep)) {
          LLVM_DEBUG(dbgs() << "Converted memcpy to memset\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Converted memcpy to memset\n"
; } } while (false);
          eraseInstruction(M);
          ++NumCpyToSet;
          return true;
        }
      }
    }

    if (hasUndefContentsMSSA(MSSA, AA, M->getSource(), MD, CopySize)) {
      LLVM_DEBUG(dbgs() << "Removed memcpy from undef\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Removed memcpy from undef\n"
; } } while (false);
      eraseInstruction(M);
      ++NumMemCpyInstr;
      return true;
    }
  }
} else {
  MemDepResult DepInfo = MD->getDependency(M);

  // Try to turn a partially redundant memset + memcpy into
  // memcpy + smaller memset.  We don't need the memcpy size for this.
  if (DepInfo.isClobber())
    if (MemSetInst *MDep = dyn_cast<MemSetInst>(DepInfo.getInst()))
      if (processMemSetMemCpyDependence(M, MDep))
        return true;

  // The optimizations after this point require the memcpy size.
  ConstantInt *CopySize = dyn_cast<ConstantInt>(M->getLength());
  if (!CopySize) return false;

  // There are four possible optimizations we can do for memcpy:
  //   a) memcpy-memcpy xform which exposes redundance for DSE.
  //   b) call-memcpy xform for return slot optimization.
  //   c) memcpy from freshly alloca'd space or space that has just started
  //      its lifetime copies undefined data, and we can therefore eliminate
  //      the memcpy in favor of the data that was already at the destination.
  //   d) memcpy from a just-memset'd source can be turned into memset.
  if (DepInfo.isClobber()) {
    if (CallInst *C = dyn_cast<CallInst>(DepInfo.getInst())) {
      // FIXME: Can we pass in either of dest/src alignment here instead
      // of conservatively taking the minimum?
      Align Alignment = std::min(M->getDestAlign().valueOrOne(),
                                 M->getSourceAlign().valueOrOne());
      if (performCallSlotOptzn(M, M, M->getDest(), M->getSource(),
                               CopySize->getZExtValue(), Alignment, C)) {
        eraseInstruction(M);
        ++NumMemCpyInstr;
        return true;
      }
    }
  }

  MemoryLocation SrcLoc = MemoryLocation::getForSource(M);
  MemDepResult SrcDepInfo = MD->getPointerDependencyFrom(
      SrcLoc, true, M->getIterator(), M->getParent());

  if (SrcDepInfo.isClobber()) {
    if (MemCpyInst *MDep = dyn_cast<MemCpyInst>(SrcDepInfo.getInst()))
      return processMemCpyMemCpyDependence(M, MDep);
  } else if (SrcDepInfo.isDef()) {
    if (hasUndefContents(SrcDepInfo.getInst(), CopySize)) {
      eraseInstruction(M);
      ++NumMemCpyInstr;
      return true;
    }
  }

  if (SrcDepInfo.isClobber())
    if (MemSetInst *MDep = dyn_cast<MemSetInst>(SrcDepInfo.getInst()))
      if (performMemCpyToMemSetOptzn(M, MDep)) {
        eraseInstruction(M);
        ++NumCpyToSet;
        return true;
      }
}

return false;
1518}

1520/// Transforms memmove calls to memcpy calls when the src/dst are guaranteed
1521/// not to alias.
1522bool MemCpyOptPass::processMemMove(MemMoveInst *M) {
if (!TLI->has(LibFunc_memmove))
  return false;

// See if the pointers alias.
if (!AA->isNoAlias(MemoryLocation::getForDest(M),
                   MemoryLocation::getForSource(M)))
  return false;

LLVM_DEBUG(dbgs() << "MemCpyOptPass: Optimizing memmove -> memcpy: " << *Mdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "MemCpyOptPass: Optimizing memmove -> memcpy: "
 << *M << "\n"; } } while (false)
                  << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "MemCpyOptPass: Optimizing memmove -> memcpy: "
 << *M << "\n"; } } while (false);

// If not, then we know we can transform this.
Type *ArgTys[3] = { M->getRawDest()->getType(),
                    M->getRawSource()->getType(),
                    M->getLength()->getType() };
M->setCalledFunction(Intrinsic::getDeclaration(M->getModule(),
                                               Intrinsic::memcpy, ArgTys));

// For MemorySSA nothing really changes (except that memcpy may imply stricter
// aliasing guarantees).

// MemDep may have over conservative information about this instruction, just
// conservatively flush it from the cache.
if (MD)
  MD->removeInstruction(M);

++NumMoveToCpy;
return true;
1551}

1553/// This is called on every byval argument in call sites.
1554bool MemCpyOptPass::processByValArgument(CallBase &CB, unsigned ArgNo) {
const DataLayout &DL = CB.getCaller()->getParent()->getDataLayout();
// Find out what feeds this byval argument.
Value *ByValArg = CB.getArgOperand(ArgNo);
Type *ByValTy = cast<PointerType>(ByValArg->getType())->getElementType();
uint64_t ByValSize = DL.getTypeAllocSize(ByValTy);
MemoryLocation Loc(ByValArg, LocationSize::precise(ByValSize));
MemCpyInst *MDep = nullptr;
if (EnableMemorySSA) {
  MemoryUseOrDef *CallAccess = MSSA->getMemoryAccess(&CB);
  if (!CallAccess)
    return false;
  MemoryAccess *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(
      CallAccess->getDefiningAccess(), Loc);
  if (auto *MD = dyn_cast<MemoryDef>(Clobber))
    MDep = dyn_cast_or_null<MemCpyInst>(MD->getMemoryInst());
} else {
  MemDepResult DepInfo = MD->getPointerDependencyFrom(
      Loc, true, CB.getIterator(), CB.getParent());
  if (!DepInfo.isClobber())
    return false;
  MDep = dyn_cast<MemCpyInst>(DepInfo.getInst());
}

// If the byval argument isn't fed by a memcpy, ignore it.  If it is fed by
// a memcpy, see if we can byval from the source of the memcpy instead of the
// result.
if (!MDep || MDep->isVolatile() ||
    ByValArg->stripPointerCasts() != MDep->getDest())
  return false;

// The length of the memcpy must be larger or equal to the size of the byval.
ConstantInt *C1 = dyn_cast<ConstantInt>(MDep->getLength());
if (!C1 || C1->getValue().getZExtValue() < ByValSize)
  return false;

// Get the alignment of the byval.  If the call doesn't specify the alignment,
// then it is some target specific value that we can't know.
MaybeAlign ByValAlign = CB.getParamAlign(ArgNo);
if (!ByValAlign) return false;

// If it is greater than the memcpy, then we check to see if we can force the
// source of the memcpy to the alignment we need.  If we fail, we bail out.
MaybeAlign MemDepAlign = MDep->getSourceAlign();
if ((!MemDepAlign || *MemDepAlign < *ByValAlign) &&
    getOrEnforceKnownAlignment(MDep->getSource(), ByValAlign, DL, &CB, AC,
                               DT) < *ByValAlign)
  return false;

// The address space of the memcpy source must match the byval argument
if (MDep->getSource()->getType()->getPointerAddressSpace() !=
    ByValArg->getType()->getPointerAddressSpace())
  return false;

// Verify that the copied-from memory doesn't change in between the memcpy and
// the byval call.
//    memcpy(a <- b)
//    *b = 42;
//    foo(*a)
// It would be invalid to transform the second memcpy into foo(*b).
if (EnableMemorySSA) {
  if (writtenBetween(MSSA, MemoryLocation::getForSource(MDep),
                     MSSA->getMemoryAccess(MDep), MSSA->getMemoryAccess(&CB)))
    return false;
} else {
  // NOTE: This is conservative, it will stop on any read from the source loc,
  // not just the defining memcpy.
  MemDepResult SourceDep = MD->getPointerDependencyFrom(
      MemoryLocation::getForSource(MDep), false,
      CB.getIterator(), MDep->getParent());
  if (!SourceDep.isClobber() || SourceDep.getInst() != MDep)
    return false;
}

Value *TmpCast = MDep->getSource();
if (MDep->getSource()->getType() != ByValArg->getType()) {
  BitCastInst *TmpBitCast = new BitCastInst(MDep->getSource(), ByValArg->getType(),
                                            "tmpcast", &CB);
  // Set the tmpcast's DebugLoc to MDep's
  TmpBitCast->setDebugLoc(MDep->getDebugLoc());
  TmpCast = TmpBitCast;
}

LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy to byval:\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "MemCpyOptPass: Forwarding memcpy to byval:\n"
 << "  " << *MDep << "\n" << "  " <<
 CB << "\n"; } } while (false)
                  << "  " << *MDep << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "MemCpyOptPass: Forwarding memcpy to byval:\n"
 << "  " << *MDep << "\n" << "  " <<
 CB << "\n"; } } while (false)
                  << "  " << CB << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "MemCpyOptPass: Forwarding memcpy to byval:\n"
 << "  " << *MDep << "\n" << "  " <<
 CB << "\n"; } } while (false);

// Otherwise we're good!  Update the byval argument.
CB.setArgOperand(ArgNo, TmpCast);
++NumMemCpyInstr;
return true;
1645}

1647/// Executes one iteration of MemCpyOptPass.
1648bool MemCpyOptPass::iterateOnFunction(Function &F) {
bool MadeChange = false;

// Walk all instruction in the function.
for (BasicBlock &BB : F) {
  // Skip unreachable blocks. For example processStore assumes that an
  // instruction in a BB can't be dominated by a later instruction in the
  // same BB (which is a scenario that can happen for an unreachable BB that
  // has itself as a predecessor).
  if (!DT->isReachableFromEntry(&BB))
    continue;

  for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) {
      // Avoid invalidating the iterator.
    Instruction *I = &*BI++;

    bool RepeatInstruction = false;

    if (StoreInst *SI = dyn_cast<StoreInst>(I))
      MadeChange |= processStore(SI, BI);
    else if (MemSetInst *M = dyn_cast<MemSetInst>(I))
      RepeatInstruction = processMemSet(M, BI);
    else if (MemCpyInst *M = dyn_cast<MemCpyInst>(I))
      RepeatInstruction = processMemCpy(M, BI);
    else if (MemMoveInst *M = dyn_cast<MemMoveInst>(I))
      RepeatInstruction = processMemMove(M);
    else if (auto *CB = dyn_cast<CallBase>(I)) {
      for (unsigned i = 0, e = CB->arg_size(); i != e; ++i)
        if (CB->isByValArgument(i))
          MadeChange |= processByValArgument(*CB, i);
    }

    // Reprocess the instruction if desired.
    if (RepeatInstruction) {
      if (BI != BB.begin())
        --BI;
      MadeChange = true;
    }
  }
}

return MadeChange;
1690}

1692PreservedAnalyses MemCpyOptPass::run(Function &F, FunctionAnalysisManager &AM) {
auto *MD = !EnableMemorySSA ? &AM.getResult<MemoryDependenceAnalysis>(F)
                            : AM.getCachedResult<MemoryDependenceAnalysis>(F);
auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
auto *AA = &AM.getResult<AAManager>(F);
auto *AC = &AM.getResult<AssumptionAnalysis>(F);
auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
auto *MSSA = EnableMemorySSA ? &AM.getResult<MemorySSAAnalysis>(F)
                             : AM.getCachedResult<MemorySSAAnalysis>(F);

bool MadeChange =
    runImpl(F, MD, &TLI, AA, AC, DT, MSSA ? &MSSA->getMSSA() : nullptr);
if (!MadeChange)
  return PreservedAnalyses::all();

PreservedAnalyses PA;
PA.preserveSet<CFGAnalyses>();
PA.preserve<GlobalsAA>();
if (MD)
  PA.preserve<MemoryDependenceAnalysis>();
if (MSSA)
  PA.preserve<MemorySSAAnalysis>();
return PA;
1715}

1717bool MemCpyOptPass::runImpl(Function &F, MemoryDependenceResults *MD_,
                          TargetLibraryInfo *TLI_, AliasAnalysis *AA_,
                          AssumptionCache *AC_, DominatorTree *DT_,
                          MemorySSA *MSSA_) {
bool MadeChange = false;
MD = MD_;
TLI = TLI_;
AA = AA_;
AC = AC_;
DT = DT_;
MSSA = MSSA_;
MemorySSAUpdater MSSAU_(MSSA_);
MSSAU = MSSA_ ? &MSSAU_ : nullptr;
// If we don't have at least memset and memcpy, there is little point of doing
// anything here.  These are required by a freestanding implementation, so if
// even they are disabled, there is no point in trying hard.
if (!TLI->has(LibFunc_memset) || !TLI->has(LibFunc_memcpy))
  return false;

while (true) {
  if (!iterateOnFunction(F))
    break;
  MadeChange = true;
}

if (MSSA_ && VerifyMemorySSA)
  MSSA_->verifyMemorySSA();

MD = nullptr;
return MadeChange;
1747}

1749/// This is the main transformation entry point for a function.
1750bool MemCpyOptLegacyPass::runOnFunction(Function &F) {
if (skipFunction(F))
  return false;

auto *MDWP = !EnableMemorySSA
    ? &getAnalysis<MemoryDependenceWrapperPass>()
    : getAnalysisIfAvailable<MemoryDependenceWrapperPass>();
auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
auto *MSSAWP = EnableMemorySSA
    ? &getAnalysis<MemorySSAWrapperPass>()
    : getAnalysisIfAvailable<MemorySSAWrapperPass>();

return Impl.runImpl(F, MDWP ? & MDWP->getMemDep() : nullptr, TLI, AA, AC, DT,
                    MSSAWP ? &MSSAWP->getMSSA() : nullptr);
1767}

←

/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h

→

1//===- MemorySSA.h - Build Memory SSA ---------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9/// \file
10/// This file exposes an interface to building/using memory SSA to
11/// walk memory instructions using a use/def graph.
12///
13/// Memory SSA class builds an SSA form that links together memory access
14/// instructions such as loads, stores, atomics, and calls. Additionally, it
15/// does a trivial form of "heap versioning" Every time the memory state changes
16/// in the program, we generate a new heap version. It generates
17/// MemoryDef/Uses/Phis that are overlayed on top of the existing instructions.
18///
19/// As a trivial example,
20/// define i32 @main() #0 {
21/// entry:
22///   %call = call noalias i8* @_Znwm(i64 4) #2
23///   %0 = bitcast i8* %call to i32*
24///   %call1 = call noalias i8* @_Znwm(i64 4) #2
25///   %1 = bitcast i8* %call1 to i32*
26///   store i32 5, i32* %0, align 4
27///   store i32 7, i32* %1, align 4
28///   %2 = load i32* %0, align 4
29///   %3 = load i32* %1, align 4
30///   %add = add nsw i32 %2, %3
31///   ret i32 %add
32/// }
33///
34/// Will become
35/// define i32 @main() #0 {
36/// entry:
37///   ; 1 = MemoryDef(0)
38///   %call = call noalias i8* @_Znwm(i64 4) #3
39///   %2 = bitcast i8* %call to i32*
40///   ; 2 = MemoryDef(1)
41///   %call1 = call noalias i8* @_Znwm(i64 4) #3
42///   %4 = bitcast i8* %call1 to i32*
43///   ; 3 = MemoryDef(2)
44///   store i32 5, i32* %2, align 4
45///   ; 4 = MemoryDef(3)
46///   store i32 7, i32* %4, align 4
47///   ; MemoryUse(3)
48///   %7 = load i32* %2, align 4
49///   ; MemoryUse(4)
50///   %8 = load i32* %4, align 4
51///   %add = add nsw i32 %7, %8
52///   ret i32 %add
53/// }
54///
55/// Given this form, all the stores that could ever effect the load at %8 can be
56/// gotten by using the MemoryUse associated with it, and walking from use to
57/// def until you hit the top of the function.
58///
59/// Each def also has a list of users associated with it, so you can walk from
60/// both def to users, and users to defs. Note that we disambiguate MemoryUses,
61/// but not the RHS of MemoryDefs. You can see this above at %7, which would
62/// otherwise be a MemoryUse(4). Being disambiguated means that for a given
63/// store, all the MemoryUses on its use lists are may-aliases of that store
64/// (but the MemoryDefs on its use list may not be).
65///
66/// MemoryDefs are not disambiguated because it would require multiple reaching
67/// definitions, which would require multiple phis, and multiple memoryaccesses
68/// per instruction.
69//
70//===----------------------------------------------------------------------===//
71 
72#ifndef LLVM_ANALYSIS_MEMORYSSA_H
73#define LLVM_ANALYSIS_MEMORYSSA_H
74 
75#include "llvm/ADT/DenseMap.h"
76#include "llvm/ADT/GraphTraits.h"
77#include "llvm/ADT/SmallPtrSet.h"
78#include "llvm/ADT/SmallVector.h"
79#include "llvm/ADT/ilist.h"
80#include "llvm/ADT/ilist_node.h"
81#include "llvm/ADT/iterator.h"
82#include "llvm/ADT/iterator_range.h"
83#include "llvm/ADT/simple_ilist.h"
84#include "llvm/Analysis/AliasAnalysis.h"
85#include "llvm/Analysis/MemoryLocation.h"
86#include "llvm/Analysis/PHITransAddr.h"
87#include "llvm/IR/BasicBlock.h"
88#include "llvm/IR/DerivedUser.h"
89#include "llvm/IR/Dominators.h"
90#include "llvm/IR/Module.h"
91#include "llvm/IR/Operator.h"
92#include "llvm/IR/Type.h"
93#include "llvm/IR/Use.h"
94#include "llvm/IR/User.h"
95#include "llvm/IR/Value.h"
96#include "llvm/IR/ValueHandle.h"
97#include "llvm/Pass.h"
98#include "llvm/Support/Casting.h"
99#include "llvm/Support/CommandLine.h"
100#include <algorithm>
101#include <cassert>
102#include <cstddef>
103#include <iterator>
104#include <memory>
105#include <utility>
106 
107namespace llvm {
108 
109/// Enables memory ssa as a dependency for loop passes.
110extern cl::opt<bool> EnableMSSALoopDependency;
111 
112class AllocaInst;
113class Function;
114class Instruction;
115class MemoryAccess;
116class MemorySSAWalker;
117class LLVMContext;
118class raw_ostream;
119 
120namespace MSSAHelpers {
121 
122struct AllAccessTag {};
123struct DefsOnlyTag {};
124 
125} // end namespace MSSAHelpers
126 
127enum : unsigned {
128  // Used to signify what the default invalid ID is for MemoryAccess's
129  // getID()
130  INVALID_MEMORYACCESS_ID = -1U
131};
132 
133template <class T> class memoryaccess_def_iterator_base;
134using memoryaccess_def_iterator = memoryaccess_def_iterator_base<MemoryAccess>;
135using const_memoryaccess_def_iterator =
136    memoryaccess_def_iterator_base<const MemoryAccess>;
137 
138// The base for all memory accesses. All memory accesses in a block are
139// linked together using an intrusive list.
140class MemoryAccess
141    : public DerivedUser,
142      public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>,
143      public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>> {
144public:
145  using AllAccessType =
146      ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>;
147  using DefsOnlyType =
148      ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>;
149 
150  MemoryAccess(const MemoryAccess &) = delete;
151  MemoryAccess &operator=(const MemoryAccess &) = delete;
152 
153  void *operator new(size_t) = delete;
154 
155  // Methods for support type inquiry through isa, cast, and
156  // dyn_cast
157  static bool classof(const Value *V) {
158    unsigned ID = V->getValueID();
159    return ID == MemoryUseVal || ID == MemoryPhiVal || ID == MemoryDefVal;
160  }
161 
162  BasicBlock *getBlock() const { return Block; }
163 
164  void print(raw_ostream &OS) const;
165  void dump() const;
166 
167  /// The user iterators for a memory access
168  using iterator = user_iterator;
169  using const_iterator = const_user_iterator;
170 
171  /// This iterator walks over all of the defs in a given
172  /// MemoryAccess. For MemoryPhi nodes, this walks arguments. For
173  /// MemoryUse/MemoryDef, this walks the defining access.
174  memoryaccess_def_iterator defs_begin();
175  const_memoryaccess_def_iterator defs_begin() const;
176  memoryaccess_def_iterator defs_end();
177  const_memoryaccess_def_iterator defs_end() const;
178 
179  /// Get the iterators for the all access list and the defs only list
180  /// We default to the all access list.
181  AllAccessType::self_iterator getIterator() {
182    return this->AllAccessType::getIterator();
183  }
184  AllAccessType::const_self_iterator getIterator() const {
185    return this->AllAccessType::getIterator();
186  }
187  AllAccessType::reverse_self_iterator getReverseIterator() {
188    return this->AllAccessType::getReverseIterator();
189  }
190  AllAccessType::const_reverse_self_iterator getReverseIterator() const {
191    return this->AllAccessType::getReverseIterator();
192  }
193  DefsOnlyType::self_iterator getDefsIterator() {
194    return this->DefsOnlyType::getIterator();
195  }
196  DefsOnlyType::const_self_iterator getDefsIterator() const {
197    return this->DefsOnlyType::getIterator();
198  }
199  DefsOnlyType::reverse_self_iterator getReverseDefsIterator() {
200    return this->DefsOnlyType::getReverseIterator();
201  }
202  DefsOnlyType::const_reverse_self_iterator getReverseDefsIterator() const {
203    return this->DefsOnlyType::getReverseIterator();
204  }
205 
206protected:
207  friend class MemoryDef;
208  friend class MemoryPhi;
209  friend class MemorySSA;
210  friend class MemoryUse;
211  friend class MemoryUseOrDef;
212 
213  /// Used by MemorySSA to change the block of a MemoryAccess when it is
214  /// moved.
215  void setBlock(BasicBlock *BB) { Block = BB; }
216 
217  /// Used for debugging and tracking things about MemoryAccesses.
218  /// Guaranteed unique among MemoryAccesses, no guarantees otherwise.
219  inline unsigned getID() const;
220 
221  MemoryAccess(LLVMContext &C, unsigned Vty, DeleteValueTy DeleteValue,
222               BasicBlock *BB, unsigned NumOperands)
223      : DerivedUser(Type::getVoidTy(C), Vty, nullptr, NumOperands, DeleteValue),
224        Block(BB) {}
225 
226  // Use deleteValue() to delete a generic MemoryAccess.
227  ~MemoryAccess() = default;
228 
229private:
230  BasicBlock *Block;
231};
232 
233template <>
234struct ilist_alloc_traits<MemoryAccess> {
235  static void deleteNode(MemoryAccess *MA) { MA->deleteValue(); }
236};
237 
238inline raw_ostream &operator<<(raw_ostream &OS, const MemoryAccess &MA) {
239  MA.print(OS);
240  return OS;
241}
242 
243/// Class that has the common methods + fields of memory uses/defs. It's
244/// a little awkward to have, but there are many cases where we want either a
245/// use or def, and there are many cases where uses are needed (defs aren't
246/// acceptable), and vice-versa.
247///
248/// This class should never be instantiated directly; make a MemoryUse or
249/// MemoryDef instead.
250class MemoryUseOrDef : public MemoryAccess {
251public:
252  void *operator new(size_t) = delete;
253 
254  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess)public: inline MemoryAccess *getOperand(unsigned) const; inline
 void setOperand(unsigned, MemoryAccess*); inline op_iterator
 op_begin(); inline const_op_iterator op_begin() const; inline
 op_iterator op_end(); inline const_op_iterator op_end() const
; protected: template <int> inline Use &Op(); template
 <int> inline const Use &Op() const; public: inline
 unsigned getNumOperands() const;
255 
256  /// Get the instruction that this MemoryUse represents.
257  Instruction *getMemoryInst() const { return MemoryInstruction; }
258 
259  /// Get the access that produces the memory state used by this Use.
260  MemoryAccess *getDefiningAccess() const { return getOperand(0); }
261 
262  static bool classof(const Value *MA) {
263    return MA->getValueID() == MemoryUseVal || MA->getValueID() == MemoryDefVal;
264  }
265 
266  // Sadly, these have to be public because they are needed in some of the
267  // iterators.
268  inline bool isOptimized() const;
269  inline MemoryAccess *getOptimized() const;
270  inline void setOptimized(MemoryAccess *);
271 
272  // Retrieve AliasResult type of the optimized access. Ideally this would be
273  // returned by the caching walker and may go away in the future.
274  Optional<AliasResult> getOptimizedAccessType() const {
275    return isOptimized() ? OptimizedAccessAlias : None;
276  }
277 
278  /// Reset the ID of what this MemoryUse was optimized to, causing it to
279  /// be rewalked by the walker if necessary.
280  /// This really should only be called by tests.
281  inline void resetOptimized();
282 
283protected:
284  friend class MemorySSA;
285  friend class MemorySSAUpdater;
286 
287  MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,
288                 DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB,
289                 unsigned NumOperands)
290      : MemoryAccess(C, Vty, DeleteValue, BB, NumOperands),
291        MemoryInstruction(MI), OptimizedAccessAlias(AliasResult::MayAlias) {
292    setDefiningAccess(DMA);
293  }
294 
295  // Use deleteValue() to delete a generic MemoryUseOrDef.
296  ~MemoryUseOrDef() = default;
297 
298  void setOptimizedAccessType(Optional<AliasResult> AR) {
299    OptimizedAccessAlias = AR;
300  }
301 
302  void setDefiningAccess(
303      MemoryAccess *DMA, bool Optimized = false,
304      Optional<AliasResult> AR = AliasResult(AliasResult::MayAlias)) {
305    if (!Optimized) {
306      setOperand(0, DMA);
307      return;
308    }
309    setOptimized(DMA);
310    setOptimizedAccessType(AR);
311  }
312 
313private:
314  Instruction *MemoryInstruction;
315  Optional<AliasResult> OptimizedAccessAlias;
316};
317 
318/// Represents read-only accesses to memory
319///
320/// In particular, the set of Instructions that will be represented by
321/// MemoryUse's is exactly the set of Instructions for which
322/// AliasAnalysis::getModRefInfo returns "Ref".
323class MemoryUse final : public MemoryUseOrDef {
324public:
325  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess)public: inline MemoryAccess *getOperand(unsigned) const; inline
 void setOperand(unsigned, MemoryAccess*); inline op_iterator
 op_begin(); inline const_op_iterator op_begin() const; inline
 op_iterator op_end(); inline const_op_iterator op_end() const
; protected: template <int> inline Use &Op(); template
 <int> inline const Use &Op() const; public: inline
 unsigned getNumOperands() const;
326 
327  MemoryUse(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB)
328      : MemoryUseOrDef(C, DMA, MemoryUseVal, deleteMe, MI, BB,
329                       /*NumOperands=*/1) {}
330 
331  // allocate space for exactly one operand
332  void *operator new(size_t s) { return User::operator new(s, 1); }
333 
334  static bool classof(const Value *MA) {
335    return MA->getValueID() == MemoryUseVal;
336  }
337 
338  void print(raw_ostream &OS) const;
339 
340  void setOptimized(MemoryAccess *DMA) {
341    OptimizedID = DMA->getID();
342    setOperand(0, DMA);
343  }
344 
345  bool isOptimized() const {
346    return getDefiningAccess() && OptimizedID == getDefiningAccess()->getID();
347  }
348 
349  MemoryAccess *getOptimized() const {
350    return getDefiningAccess();
351  }
352 
353  void resetOptimized() {
354    OptimizedID = INVALID_MEMORYACCESS_ID;
355  }
356 
357protected:
358  friend class MemorySSA;
359 
360private:
361  static void deleteMe(DerivedUser *Self);
362 
363  unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
364};
365 
366template <>
367struct OperandTraits<MemoryUse> : public FixedNumOperandTraits<MemoryUse, 1> {};
368DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUse, MemoryAccess)MemoryUse::op_iterator MemoryUse::op_begin() { return OperandTraits
<MemoryUse>::op_begin(this); } MemoryUse::const_op_iterator
 MemoryUse::op_begin() const { return OperandTraits<MemoryUse
>::op_begin(const_cast<MemoryUse*>(this)); } MemoryUse
::op_iterator MemoryUse::op_end() { return OperandTraits<MemoryUse
>::op_end(this); } MemoryUse::const_op_iterator MemoryUse::
op_end() const { return OperandTraits<MemoryUse>::op_end
(const_cast<MemoryUse*>(this)); } MemoryAccess *MemoryUse
::getOperand(unsigned i_nocapture) const { ((i_nocapture <
 OperandTraits<MemoryUse>::operands(this) && "getOperand() out of range!"
) ? static_cast<void> (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryUse>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 368, __PRETTY_FUNCTION__)); return cast_or_null<MemoryAccess
>( OperandTraits<MemoryUse>::op_begin(const_cast<
MemoryUse*>(this))[i_nocapture].get()); } void MemoryUse::
setOperand(unsigned i_nocapture, MemoryAccess *Val_nocapture)
 { ((i_nocapture < OperandTraits<MemoryUse>::operands
(this) && "setOperand() out of range!") ? static_cast
<void> (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryUse>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 368, __PRETTY_FUNCTION__)); OperandTraits<MemoryUse>::
op_begin(this)[i_nocapture] = Val_nocapture; } unsigned MemoryUse
::getNumOperands() const { return OperandTraits<MemoryUse>
::operands(this); } template <int Idx_nocapture> Use &
MemoryUse::Op() { return this->OpFrom<Idx_nocapture>
(this); } template <int Idx_nocapture> const Use &MemoryUse
::Op() const { return this->OpFrom<Idx_nocapture>(this
); }
369 
370/// Represents a read-write access to memory, whether it is a must-alias,
371/// or a may-alias.
372///
373/// In particular, the set of Instructions that will be represented by
374/// MemoryDef's is exactly the set of Instructions for which
375/// AliasAnalysis::getModRefInfo returns "Mod" or "ModRef".
376/// Note that, in order to provide def-def chains, all defs also have a use
377/// associated with them. This use points to the nearest reaching
378/// MemoryDef/MemoryPhi.
379class MemoryDef final : public MemoryUseOrDef {
380public:
381  friend class MemorySSA;
382 
383  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess)public: inline MemoryAccess *getOperand(unsigned) const; inline
 void setOperand(unsigned, MemoryAccess*); inline op_iterator
 op_begin(); inline const_op_iterator op_begin() const; inline
 op_iterator op_end(); inline const_op_iterator op_end() const
; protected: template <int> inline Use &Op(); template
 <int> inline const Use &Op() const; public: inline
 unsigned getNumOperands() const;
384 
385  MemoryDef(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB,
386            unsigned Ver)
387      : MemoryUseOrDef(C, DMA, MemoryDefVal, deleteMe, MI, BB,
388                       /*NumOperands=*/2),
389        ID(Ver) {}
390 
391  // allocate space for exactly two operands
392  void *operator new(size_t s) { return User::operator new(s, 2); }
393 
394  static bool classof(const Value *MA) {
395    return MA->getValueID() == MemoryDefVal;
396  }
397 
398  void setOptimized(MemoryAccess *MA) {
399    setOperand(1, MA);
400    OptimizedID = MA->getID();
401  }
402 
403  MemoryAccess *getOptimized() const {
404    return cast_or_null<MemoryAccess>(getOperand(1));
405  }
406 
407  bool isOptimized() const {
408    return getOptimized() && OptimizedID == getOptimized()->getID();
409  }
410 
411  void resetOptimized() {
412    OptimizedID = INVALID_MEMORYACCESS_ID;
413    setOperand(1, nullptr);
414  }
415 
416  void print(raw_ostream &OS) const;
417 
418  unsigned getID() const { return ID; }
419 
420private:
421  static void deleteMe(DerivedUser *Self);
422 
423  const unsigned ID;
424  unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
425};
426 
427template <>
428struct OperandTraits<MemoryDef> : public FixedNumOperandTraits<MemoryDef, 2> {};
429DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryDef, MemoryAccess)MemoryDef::op_iterator MemoryDef::op_begin() { return OperandTraits
<MemoryDef>::op_begin(this); } MemoryDef::const_op_iterator
 MemoryDef::op_begin() const { return OperandTraits<MemoryDef
>::op_begin(const_cast<MemoryDef*>(this)); } MemoryDef
::op_iterator MemoryDef::op_end() { return OperandTraits<MemoryDef
>::op_end(this); } MemoryDef::const_op_iterator MemoryDef::
op_end() const { return OperandTraits<MemoryDef>::op_end
(const_cast<MemoryDef*>(this)); } MemoryAccess *MemoryDef
::getOperand(unsigned i_nocapture) const { ((i_nocapture <
 OperandTraits<MemoryDef>::operands(this) && "getOperand() out of range!"
) ? static_cast<void> (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryDef>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 429, __PRETTY_FUNCTION__)); return cast_or_null<MemoryAccess
>( OperandTraits<MemoryDef>::op_begin(const_cast<
MemoryDef*>(this))[i_nocapture].get()); } void MemoryDef::
setOperand(unsigned i_nocapture, MemoryAccess *Val_nocapture)
 { ((i_nocapture < OperandTraits<MemoryDef>::operands
(this) && "setOperand() out of range!") ? static_cast
<void> (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryDef>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 429, __PRETTY_FUNCTION__)); OperandTraits<MemoryDef>::
op_begin(this)[i_nocapture] = Val_nocapture; } unsigned MemoryDef
::getNumOperands() const { return OperandTraits<MemoryDef>
::operands(this); } template <int Idx_nocapture> Use &
MemoryDef::Op() { return this->OpFrom<Idx_nocapture>
(this); } template <int Idx_nocapture> const Use &MemoryDef
::Op() const { return this->OpFrom<Idx_nocapture>(this
); }
430 
431template <>
432struct OperandTraits<MemoryUseOrDef> {
433  static Use *op_begin(MemoryUseOrDef *MUD) {
434    if (auto *MU = dyn_cast<MemoryUse>(MUD))
435      return OperandTraits<MemoryUse>::op_begin(MU);
436    return OperandTraits<MemoryDef>::op_begin(cast<MemoryDef>(MUD));
437  }
438 
439  static Use *op_end(MemoryUseOrDef *MUD) {
440    if (auto *MU = dyn_cast<MemoryUse>(MUD))
441      return OperandTraits<MemoryUse>::op_end(MU);
442    return OperandTraits<MemoryDef>::op_end(cast<MemoryDef>(MUD));
443  }
444 
445  static unsigned operands(const MemoryUseOrDef *MUD) {
446    if (const auto *MU = dyn_cast<MemoryUse>(MUD))
447      return OperandTraits<MemoryUse>::operands(MU);
448    return OperandTraits<MemoryDef>::operands(cast<MemoryDef>(MUD));
449  }
450};
451DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUseOrDef, MemoryAccess)MemoryUseOrDef::op_iterator MemoryUseOrDef::op_begin() { return
 OperandTraits<MemoryUseOrDef>::op_begin(this); } MemoryUseOrDef
::const_op_iterator MemoryUseOrDef::op_begin() const { return
 OperandTraits<MemoryUseOrDef>::op_begin(const_cast<
MemoryUseOrDef*>(this)); } MemoryUseOrDef::op_iterator MemoryUseOrDef
::op_end() { return OperandTraits<MemoryUseOrDef>::op_end
(this); } MemoryUseOrDef::const_op_iterator MemoryUseOrDef::op_end
() const { return OperandTraits<MemoryUseOrDef>::op_end
(const_cast<MemoryUseOrDef*>(this)); } MemoryAccess *MemoryUseOrDef
::getOperand(unsigned i_nocapture) const { ((i_nocapture <
 OperandTraits<MemoryUseOrDef>::operands(this) &&
 "getOperand() out of range!") ? static_cast<void> (0) :
 __assert_fail ("i_nocapture < OperandTraits<MemoryUseOrDef>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 451, __PRETTY_FUNCTION__)); return cast_or_null<MemoryAccess
>( OperandTraits<MemoryUseOrDef>::op_begin(const_cast
<MemoryUseOrDef*>(this))[i_nocapture].get()); } void MemoryUseOrDef
::setOperand(unsigned i_nocapture, MemoryAccess *Val_nocapture
) { ((i_nocapture < OperandTraits<MemoryUseOrDef>::operands
(this) && "setOperand() out of range!") ? static_cast
<void> (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryUseOrDef>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 451, __PRETTY_FUNCTION__)); OperandTraits<MemoryUseOrDef
>::op_begin(this)[i_nocapture] = Val_nocapture; } unsigned
 MemoryUseOrDef::getNumOperands() const { return OperandTraits
<MemoryUseOrDef>::operands(this); } template <int Idx_nocapture
> Use &MemoryUseOrDef::Op() { return this->OpFrom<
Idx_nocapture>(this); } template <int Idx_nocapture>
 const Use &MemoryUseOrDef::Op() const { return this->
OpFrom<Idx_nocapture>(this); }
452 
453/// Represents phi nodes for memory accesses.
454///
455/// These have the same semantic as regular phi nodes, with the exception that
456/// only one phi will ever exist in a given basic block.
457/// Guaranteeing one phi per block means guaranteeing there is only ever one
458/// valid reaching MemoryDef/MemoryPHI along each path to the phi node.
459/// This is ensured by not allowing disambiguation of the RHS of a MemoryDef or
460/// a MemoryPhi's operands.
461/// That is, given
462/// if (a) {
463///   store %a
464///   store %b
465/// }
466/// it *must* be transformed into
467/// if (a) {
468///    1 = MemoryDef(liveOnEntry)
469///    store %a
470///    2 = MemoryDef(1)
471///    store %b
472/// }
473/// and *not*
474/// if (a) {
475///    1 = MemoryDef(liveOnEntry)
476///    store %a
477///    2 = MemoryDef(liveOnEntry)
478///    store %b
479/// }
480/// even if the two stores do not conflict. Otherwise, both 1 and 2 reach the
481/// end of the branch, and if there are not two phi nodes, one will be
482/// disconnected completely from the SSA graph below that point.
483/// Because MemoryUse's do not generate new definitions, they do not have this
484/// issue.
485class MemoryPhi final : public MemoryAccess {
486  // allocate space for exactly zero operands
487  void *operator new(size_t s) { return User::operator new(s); }
488 
489public:
490  /// Provide fast operand accessors
491  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess)public: inline MemoryAccess *getOperand(unsigned) const; inline
 void setOperand(unsigned, MemoryAccess*); inline op_iterator
 op_begin(); inline const_op_iterator op_begin() const; inline
 op_iterator op_end(); inline const_op_iterator op_end() const
; protected: template <int> inline Use &Op(); template
 <int> inline const Use &Op() const; public: inline
 unsigned getNumOperands() const;
492 
493  MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds = 0)
494      : MemoryAccess(C, MemoryPhiVal, deleteMe, BB, 0), ID(Ver),
495        ReservedSpace(NumPreds) {
496    allocHungoffUses(ReservedSpace);
497  }
498 
499  // Block iterator interface. This provides access to the list of incoming
500  // basic blocks, which parallels the list of incoming values.
501  using block_iterator = BasicBlock **;
502  using const_block_iterator = BasicBlock *const *;
503 
504  block_iterator block_begin() {
505    return reinterpret_cast<block_iterator>(op_begin() + ReservedSpace);
506  }
507 
508  const_block_iterator block_begin() const {
509    return reinterpret_cast<const_block_iterator>(op_begin() + ReservedSpace);
510  }
511 
512  block_iterator block_end() { return block_begin() + getNumOperands(); }
513 
514  const_block_iterator block_end() const {
515    return block_begin() + getNumOperands();
516  }
517 
518  iterator_range<block_iterator> blocks() {
519    return make_range(block_begin(), block_end());
520  }
521 
522  iterator_range<const_block_iterator> blocks() const {
523    return make_range(block_begin(), block_end());
524  }
525 
526  op_range incoming_values() { return operands(); }
527 
528  const_op_range incoming_values() const { return operands(); }
529 
530  /// Return the number of incoming edges
531  unsigned getNumIncomingValues() const { return getNumOperands(); }
532 
533  /// Return incoming value number x
534  MemoryAccess *getIncomingValue(unsigned I) const { return getOperand(I); }
535  void setIncomingValue(unsigned I, MemoryAccess *V) {
536    assert(V && "PHI node got a null value!")((V && "PHI node got a null value!") ? static_cast<
void> (0) : __assert_fail ("V && \"PHI node got a null value!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 536, __PRETTY_FUNCTION__));
537    setOperand(I, V);
538  }
539 
540  static unsigned getOperandNumForIncomingValue(unsigned I) { return I; }
541  static unsigned getIncomingValueNumForOperand(unsigned I) { return I; }
542 
543  /// Return incoming basic block number @p i.
544  BasicBlock *getIncomingBlock(unsigned I) const { return block_begin()[I]; }
545 
546  /// Return incoming basic block corresponding
547  /// to an operand of the PHI.
548  BasicBlock *getIncomingBlock(const Use &U) const {
549    assert(this == U.getUser() && "Iterator doesn't point to PHI's Uses?")((this == U.getUser() && "Iterator doesn't point to PHI's Uses?"
) ? static_cast<void> (0) : __assert_fail ("this == U.getUser() && \"Iterator doesn't point to PHI's Uses?\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 549, __PRETTY_FUNCTION__));
550    return getIncomingBlock(unsigned(&U - op_begin()));
551  }
552 
553  /// Return incoming basic block corresponding
554  /// to value use iterator.
555  BasicBlock *getIncomingBlock(MemoryAccess::const_user_iterator I) const {
556    return getIncomingBlock(I.getUse());
557  }
558 
559  void setIncomingBlock(unsigned I, BasicBlock *BB) {
560    assert(BB && "PHI node got a null basic block!")((BB && "PHI node got a null basic block!") ? static_cast
<void> (0) : __assert_fail ("BB && \"PHI node got a null basic block!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 560, __PRETTY_FUNCTION__));
561    block_begin()[I] = BB;
562  }
563 
564  /// Add an incoming value to the end of the PHI list
565  void addIncoming(MemoryAccess *V, BasicBlock *BB) {
566    if (getNumOperands() == ReservedSpace)
567      growOperands(); // Get more space!
568    // Initialize some new operands.
569    setNumHungOffUseOperands(getNumOperands() + 1);
570    setIncomingValue(getNumOperands() - 1, V);
571    setIncomingBlock(getNumOperands() - 1, BB);
572  }
573 
574  /// Return the first index of the specified basic
575  /// block in the value list for this PHI.  Returns -1 if no instance.
576  int getBasicBlockIndex(const BasicBlock *BB) const {
577    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
578      if (block_begin()[I] == BB)
579        return I;
580    return -1;
581  }
582 
583  MemoryAccess *getIncomingValueForBlock(const BasicBlock *BB) const {
584    int Idx = getBasicBlockIndex(BB);
585    assert(Idx >= 0 && "Invalid basic block argument!")((Idx >= 0 && "Invalid basic block argument!") ? static_cast
<void> (0) : __assert_fail ("Idx >= 0 && \"Invalid basic block argument!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 585, __PRETTY_FUNCTION__));
586    return getIncomingValue(Idx);
587  }
588 
589  // After deleting incoming position I, the order of incoming may be changed.
590  void unorderedDeleteIncoming(unsigned I) {
591    unsigned E = getNumOperands();
592    assert(I < E && "Cannot remove out of bounds Phi entry.")((I < E && "Cannot remove out of bounds Phi entry."
) ? static_cast<void> (0) : __assert_fail ("I < E && \"Cannot remove out of bounds Phi entry.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 592, __PRETTY_FUNCTION__));
593    // MemoryPhi must have at least two incoming values, otherwise the MemoryPhi
594    // itself should be deleted.
595    assert(E >= 2 && "Cannot only remove incoming values in MemoryPhis with "((E >= 2 && "Cannot only remove incoming values in MemoryPhis with "
 "at least 2 values.") ? static_cast<void> (0) : __assert_fail
 ("E >= 2 && \"Cannot only remove incoming values in MemoryPhis with \" \"at least 2 values.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 596, __PRETTY_FUNCTION__))
596                     "at least 2 values.")((E >= 2 && "Cannot only remove incoming values in MemoryPhis with "
 "at least 2 values.") ? static_cast<void> (0) : __assert_fail
 ("E >= 2 && \"Cannot only remove incoming values in MemoryPhis with \" \"at least 2 values.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 596, __PRETTY_FUNCTION__));
597    setIncomingValue(I, getIncomingValue(E - 1));
598    setIncomingBlock(I, block_begin()[E - 1]);
599    setOperand(E - 1, nullptr);
600    block_begin()[E - 1] = nullptr;
601    setNumHungOffUseOperands(getNumOperands() - 1);
602  }
603 
604  // After deleting entries that satisfy Pred, remaining entries may have
605  // changed order.
606  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
607    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
608      if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
609        unorderedDeleteIncoming(I);
610        E = getNumOperands();
611        --I;
612      }
613    assert(getNumOperands() >= 1 &&((getNumOperands() >= 1 && "Cannot remove all incoming blocks in a MemoryPhi."
) ? static_cast<void> (0) : __assert_fail ("getNumOperands() >= 1 && \"Cannot remove all incoming blocks in a MemoryPhi.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 614, __PRETTY_FUNCTION__))
614           "Cannot remove all incoming blocks in a MemoryPhi.")((getNumOperands() >= 1 && "Cannot remove all incoming blocks in a MemoryPhi."
) ? static_cast<void> (0) : __assert_fail ("getNumOperands() >= 1 && \"Cannot remove all incoming blocks in a MemoryPhi.\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 614, __PRETTY_FUNCTION__));
615  }
616 
617  // After deleting incoming block BB, the incoming blocks order may be changed.
618  void unorderedDeleteIncomingBlock(const BasicBlock *BB) {
619    unorderedDeleteIncomingIf(
620        [&](const MemoryAccess *, const BasicBlock *B) { return BB == B; });
621  }
622 
623  // After deleting incoming memory access MA, the incoming accesses order may
624  // be changed.
625  void unorderedDeleteIncomingValue(const MemoryAccess *MA) {
626    unorderedDeleteIncomingIf(
627        [&](const MemoryAccess *M, const BasicBlock *) { return MA == M; });
628  }
629 
630  static bool classof(const Value *V) {
631    return V->getValueID() == MemoryPhiVal;
632  }
633 
634  void print(raw_ostream &OS) const;
635 
636  unsigned getID() const { return ID; }
637 
638protected:
639  friend class MemorySSA;
640 
641  /// this is more complicated than the generic
642  /// User::allocHungoffUses, because we have to allocate Uses for the incoming
643  /// values and pointers to the incoming blocks, all in one allocation.
644  void allocHungoffUses(unsigned N) {
645    User::allocHungoffUses(N, /* IsPhi */ true);
646  }
647 
648private:
649  // For debugging only
650  const unsigned ID;
651  unsigned ReservedSpace;
652 
653  /// This grows the operand list in response to a push_back style of
654  /// operation.  This grows the number of ops by 1.5 times.
655  void growOperands() {
656    unsigned E = getNumOperands();
657    // 2 op PHI nodes are VERY common, so reserve at least enough for that.
658    ReservedSpace = std::max(E + E / 2, 2u);
659    growHungoffUses(ReservedSpace, /* IsPhi */ true);
660  }
661 
662  static void deleteMe(DerivedUser *Self);
663};
664 
665inline unsigned MemoryAccess::getID() const {
666  assert((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&(((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&
 "only memory defs and phis have ids") ? static_cast<void>
 (0) : __assert_fail ("(isa<MemoryDef>(this) || isa<MemoryPhi>(this)) && \"only memory defs and phis have ids\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 667, __PRETTY_FUNCTION__))
667         "only memory defs and phis have ids")(((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&
 "only memory defs and phis have ids") ? static_cast<void>
 (0) : __assert_fail ("(isa<MemoryDef>(this) || isa<MemoryPhi>(this)) && \"only memory defs and phis have ids\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 667, __PRETTY_FUNCTION__));
668  if (const auto *MD = dyn_cast<MemoryDef>(this))
669    return MD->getID();
670  return cast<MemoryPhi>(this)->getID();
671}
672 
673inline bool MemoryUseOrDef::isOptimized() const {
674  if (const auto *MD = dyn_cast<MemoryDef>(this))
675    return MD->isOptimized();
676  return cast<MemoryUse>(this)->isOptimized();
677}
678 
679inline MemoryAccess *MemoryUseOrDef::getOptimized() const {
680  if (const auto *MD = dyn_cast<MemoryDef>(this))
681    return MD->getOptimized();
682  return cast<MemoryUse>(this)->getOptimized();
683}
684 
685inline void MemoryUseOrDef::setOptimized(MemoryAccess *MA) {
686  if (auto *MD = dyn_cast<MemoryDef>(this))
687    MD->setOptimized(MA);
688  else
689    cast<MemoryUse>(this)->setOptimized(MA);
690}
691 
692inline void MemoryUseOrDef::resetOptimized() {
693  if (auto *MD = dyn_cast<MemoryDef>(this))
694    MD->resetOptimized();
695  else
696    cast<MemoryUse>(this)->resetOptimized();
697}
698 
699template <> struct OperandTraits<MemoryPhi> : public HungoffOperandTraits<2> {};
700DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryPhi, MemoryAccess)MemoryPhi::op_iterator MemoryPhi::op_begin() { return OperandTraits
<MemoryPhi>::op_begin(this); } MemoryPhi::const_op_iterator
 MemoryPhi::op_begin() const { return OperandTraits<MemoryPhi
>::op_begin(const_cast<MemoryPhi*>(this)); } MemoryPhi
::op_iterator MemoryPhi::op_end() { return OperandTraits<MemoryPhi
>::op_end(this); } MemoryPhi::const_op_iterator MemoryPhi::
op_end() const { return OperandTraits<MemoryPhi>::op_end
(const_cast<MemoryPhi*>(this)); } MemoryAccess *MemoryPhi
::getOperand(unsigned i_nocapture) const { ((i_nocapture <
 OperandTraits<MemoryPhi>::operands(this) && "getOperand() out of range!"
) ? static_cast<void> (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryPhi>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 700, __PRETTY_FUNCTION__)); return cast_or_null<MemoryAccess
>( OperandTraits<MemoryPhi>::op_begin(const_cast<
MemoryPhi*>(this))[i_nocapture].get()); } void MemoryPhi::
setOperand(unsigned i_nocapture, MemoryAccess *Val_nocapture)
 { ((i_nocapture < OperandTraits<MemoryPhi>::operands
(this) && "setOperand() out of range!") ? static_cast
<void> (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryPhi>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 700, __PRETTY_FUNCTION__)); OperandTraits<MemoryPhi>::
op_begin(this)[i_nocapture] = Val_nocapture; } unsigned MemoryPhi
::getNumOperands() const { return OperandTraits<MemoryPhi>
::operands(this); } template <int Idx_nocapture> Use &
MemoryPhi::Op() { return this->OpFrom<Idx_nocapture>
(this); } template <int Idx_nocapture> const Use &MemoryPhi
::Op() const { return this->OpFrom<Idx_nocapture>(this
); }
701 
702/// Encapsulates MemorySSA, including all data associated with memory
703/// accesses.
704class MemorySSA {
705public:
706  MemorySSA(Function &, AliasAnalysis *, DominatorTree *);
707 
708  // MemorySSA must remain where it's constructed; Walkers it creates store
709  // pointers to it.
710  MemorySSA(MemorySSA &&) = delete;
711 
712  ~MemorySSA();
713 
714  MemorySSAWalker *getWalker();
715  MemorySSAWalker *getSkipSelfWalker();
716 
717  /// Given a memory Mod/Ref'ing instruction, get the MemorySSA
718  /// access associated with it. If passed a basic block gets the memory phi
719  /// node that exists for that block, if there is one. Otherwise, this will get
720  /// a MemoryUseOrDef.
721  MemoryUseOrDef *getMemoryAccess(const Instruction *I) const {
722    return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I));
723  }
724 
725  MemoryPhi *getMemoryAccess(const BasicBlock *BB) const {
726    return cast_or_null<MemoryPhi>(ValueToMemoryAccess.lookup(cast<Value>(BB)));
727  }
728 
729  DominatorTree &getDomTree() const { return *DT; }
730 
731  void dump() const;
732  void print(raw_ostream &) const;
733 
734  /// Return true if \p MA represents the live on entry value
735  ///
736  /// Loads and stores from pointer arguments and other global values may be
737  /// defined by memory operations that do not occur in the current function, so
738  /// they may be live on entry to the function. MemorySSA represents such
739  /// memory state by the live on entry definition, which is guaranteed to occur
740  /// before any other memory access in the function.
741  inline bool isLiveOnEntryDef(const MemoryAccess *MA) const {
742    return MA == LiveOnEntryDef.get();
12
←
Assuming the condition is false→
13
←
Returning zero, which participates in a condition later→
743  }
744 
745  inline MemoryAccess *getLiveOnEntryDef() const {
746    return LiveOnEntryDef.get();
747  }
748 
749  // Sadly, iplists, by default, owns and deletes pointers added to the
750  // list. It's not currently possible to have two iplists for the same type,
751  // where one owns the pointers, and one does not. This is because the traits
752  // are per-type, not per-tag.  If this ever changes, we should make the
753  // DefList an iplist.
754  using AccessList = iplist<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>;
755  using DefsList =
756      simple_ilist<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>;
757 
758  /// Return the list of MemoryAccess's for a given basic block.
759  ///
760  /// This list is not modifiable by the user.
761  const AccessList *getBlockAccesses(const BasicBlock *BB) const {
762    return getWritableBlockAccesses(BB);
763  }
764 
765  /// Return the list of MemoryDef's and MemoryPhi's for a given basic
766  /// block.
767  ///
768  /// This list is not modifiable by the user.
769  const DefsList *getBlockDefs(const BasicBlock *BB) const {
770    return getWritableBlockDefs(BB);
771  }
772 
773  /// Given two memory accesses in the same basic block, determine
774  /// whether MemoryAccess \p A dominates MemoryAccess \p B.
775  bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const;
776 
777  /// Given two memory accesses in potentially different blocks,
778  /// determine whether MemoryAccess \p A dominates MemoryAccess \p B.
779  bool dominates(const MemoryAccess *A, const MemoryAccess *B) const;
780 
781  /// Given a MemoryAccess and a Use, determine whether MemoryAccess \p A
782  /// dominates Use \p B.
783  bool dominates(const MemoryAccess *A, const Use &B) const;
784 
785  /// Verify that MemorySSA is self consistent (IE definitions dominate
786  /// all uses, uses appear in the right places).  This is used by unit tests.
787  void verifyMemorySSA() const;
788 
789  /// Used in various insertion functions to specify whether we are talking
790  /// about the beginning or end of a block.
791  enum InsertionPlace { Beginning, End, BeforeTerminator };
792 
793protected:
794  // Used by Memory SSA annotater, dumpers, and wrapper pass
795  friend class MemorySSAAnnotatedWriter;
796  friend class MemorySSAPrinterLegacyPass;
797  friend class MemorySSAUpdater;
798 
799  void verifyOrderingDominationAndDefUses(Function &F) const;
800  void verifyDominationNumbers(const Function &F) const;
801  void verifyPrevDefInPhis(Function &F) const;
802 
803  // This is used by the use optimizer and updater.
804  AccessList *getWritableBlockAccesses(const BasicBlock *BB) const {
805    auto It = PerBlockAccesses.find(BB);
806    return It == PerBlockAccesses.end() ? nullptr : It->second.get();
807  }
808 
809  // This is used by the use optimizer and updater.
810  DefsList *getWritableBlockDefs(const BasicBlock *BB) const {
811    auto It = PerBlockDefs.find(BB);
812    return It == PerBlockDefs.end() ? nullptr : It->second.get();
813  }
814 
815  // These is used by the updater to perform various internal MemorySSA
816  // machinsations.  They do not always leave the IR in a correct state, and
817  // relies on the updater to fixup what it breaks, so it is not public.
818 
819  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where);
820  void moveTo(MemoryAccess *What, BasicBlock *BB, InsertionPlace Point);
821 
822  // Rename the dominator tree branch rooted at BB.
823  void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal,
824                  SmallPtrSetImpl<BasicBlock *> &Visited) {
825    renamePass(DT->getNode(BB), IncomingVal, Visited, true, true);
826  }
827 
828  void removeFromLookups(MemoryAccess *);
829  void removeFromLists(MemoryAccess *, bool ShouldDelete = true);
830  void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *,
831                               InsertionPlace);
832  void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
833                             AccessList::iterator);
834  MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *,
835                                      const MemoryUseOrDef *Template = nullptr,
836                                      bool CreationMustSucceed = true);
837 
838private:
839  template <class AliasAnalysisType> class ClobberWalkerBase;
840  template <class AliasAnalysisType> class CachingWalker;
841  template <class AliasAnalysisType> class SkipSelfWalker;
842  class OptimizeUses;
843 
844  CachingWalker<AliasAnalysis> *getWalkerImpl();
845  void buildMemorySSA(BatchAAResults &BAA);
846 
847  void prepareForMoveTo(MemoryAccess *, BasicBlock *);
848  void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
849 
850  using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;
851  using DefsMap = DenseMap<const BasicBlock *, std::unique_ptr<DefsList>>;
852 
853  void markUnreachableAsLiveOnEntry(BasicBlock *BB);
854  MemoryPhi *createMemoryPhi(BasicBlock *BB);
855  template <typename AliasAnalysisType>
856  MemoryUseOrDef *createNewAccess(Instruction *, AliasAnalysisType *,
857                                  const MemoryUseOrDef *Template = nullptr);
858  void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &);
859  MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool);
860  void renameSuccessorPhis(BasicBlock *, MemoryAccess *, bool);
861  void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
862                  SmallPtrSetImpl<BasicBlock *> &Visited,
863                  bool SkipVisited = false, bool RenameAllUses = false);
864  AccessList *getOrCreateAccessList(const BasicBlock *);
865  DefsList *getOrCreateDefsList(const BasicBlock *);
866  void renumberBlock(const BasicBlock *) const;
867  AliasAnalysis *AA;
868  DominatorTree *DT;
869  Function &F;
870 
871  // Memory SSA mappings
872  DenseMap<const Value *, MemoryAccess *> ValueToMemoryAccess;
873 
874  // These two mappings contain the main block to access/def mappings for
875  // MemorySSA. The list contained in PerBlockAccesses really owns all the
876  // MemoryAccesses.
877  // Both maps maintain the invariant that if a block is found in them, the
878  // corresponding list is not empty, and if a block is not found in them, the
879  // corresponding list is empty.
880  AccessMap PerBlockAccesses;
881  DefsMap PerBlockDefs;
882  std::unique_ptr<MemoryAccess, ValueDeleter> LiveOnEntryDef;
883 
884  // Domination mappings
885  // Note that the numbering is local to a block, even though the map is
886  // global.
887  mutable SmallPtrSet<const BasicBlock *, 16> BlockNumberingValid;
888  mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering;
889 
890  // Memory SSA building info
891  std::unique_ptr<ClobberWalkerBase<AliasAnalysis>> WalkerBase;
892  std::unique_ptr<CachingWalker<AliasAnalysis>> Walker;
893  std::unique_ptr<SkipSelfWalker<AliasAnalysis>> SkipWalker;
894  unsigned NextID;
895};
896 
897// Internal MemorySSA utils, for use by MemorySSA classes and walkers
898class MemorySSAUtil {
899protected:
900  friend class GVNHoist;
901  friend class MemorySSAWalker;
902 
903  // This function should not be used by new passes.
904  static bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
905                                  AliasAnalysis &AA);
906};
907 
908// This pass does eager building and then printing of MemorySSA. It is used by
909// the tests to be able to build, dump, and verify Memory SSA.
910class MemorySSAPrinterLegacyPass : public FunctionPass {
911public:
912  MemorySSAPrinterLegacyPass();
913 
914  bool runOnFunction(Function &) override;
915  void getAnalysisUsage(AnalysisUsage &AU) const override;
916 
917  static char ID;
918};
919 
920/// An analysis that produces \c MemorySSA for a function.
921///
922class MemorySSAAnalysis : public AnalysisInfoMixin<MemorySSAAnalysis> {
923  friend AnalysisInfoMixin<MemorySSAAnalysis>;
924 
925  static AnalysisKey Key;
926 
927public:
928  // Wrap MemorySSA result to ensure address stability of internal MemorySSA
929  // pointers after construction.  Use a wrapper class instead of plain
930  // unique_ptr<MemorySSA> to avoid build breakage on MSVC.
931  struct Result {
932    Result(std::unique_ptr<MemorySSA> &&MSSA) : MSSA(std::move(MSSA)) {}
933 
934    MemorySSA &getMSSA() { return *MSSA.get(); }
935 
936    std::unique_ptr<MemorySSA> MSSA;
937 
938    bool invalidate(Function &F, const PreservedAnalyses &PA,
939                    FunctionAnalysisManager::Invalidator &Inv);
940  };
941 
942  Result run(Function &F, FunctionAnalysisManager &AM);
943};
944 
945/// Printer pass for \c MemorySSA.
946class MemorySSAPrinterPass : public PassInfoMixin<MemorySSAPrinterPass> {
947  raw_ostream &OS;
948 
949public:
950  explicit MemorySSAPrinterPass(raw_ostream &OS) : OS(OS) {}
951 
952  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
953};
954 
955/// Verifier pass for \c MemorySSA.
956struct MemorySSAVerifierPass : PassInfoMixin<MemorySSAVerifierPass> {
957  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
958};
959 
960/// Legacy analysis pass which computes \c MemorySSA.
961class MemorySSAWrapperPass : public FunctionPass {
962public:
963  MemorySSAWrapperPass();
964 
965  static char ID;
966 
967  bool runOnFunction(Function &) override;
968  void releaseMemory() override;
969  MemorySSA &getMSSA() { return *MSSA; }
970  const MemorySSA &getMSSA() const { return *MSSA; }
971 
972  void getAnalysisUsage(AnalysisUsage &AU) const override;
973 
974  void verifyAnalysis() const override;
975  void print(raw_ostream &OS, const Module *M = nullptr) const override;
976 
977private:
978  std::unique_ptr<MemorySSA> MSSA;
979};
980 
981/// This is the generic walker interface for walkers of MemorySSA.
982/// Walkers are used to be able to further disambiguate the def-use chains
983/// MemorySSA gives you, or otherwise produce better info than MemorySSA gives
984/// you.
985/// In particular, while the def-use chains provide basic information, and are
986/// guaranteed to give, for example, the nearest may-aliasing MemoryDef for a
987/// MemoryUse as AliasAnalysis considers it, a user mant want better or other
988/// information. In particular, they may want to use SCEV info to further
989/// disambiguate memory accesses, or they may want the nearest dominating
990/// may-aliasing MemoryDef for a call or a store. This API enables a
991/// standardized interface to getting and using that info.
992class MemorySSAWalker {
993public:
994  MemorySSAWalker(MemorySSA *);
995  virtual ~MemorySSAWalker() = default;
996 
997  using MemoryAccessSet = SmallVector<MemoryAccess *, 8>;
998 
999  /// Given a memory Mod/Ref/ModRef'ing instruction, calling this
1000  /// will give you the nearest dominating MemoryAccess that Mod's the location
1001  /// the instruction accesses (by skipping any def which AA can prove does not
1002  /// alias the location(s) accessed by the instruction given).
1003  ///
1004  /// Note that this will return a single access, and it must dominate the
1005  /// Instruction, so if an operand of a MemoryPhi node Mod's the instruction,
1006  /// this will return the MemoryPhi, not the operand. This means that
1007  /// given:
1008  /// if (a) {
1009  ///   1 = MemoryDef(liveOnEntry)
1010  ///   store %a
1011  /// } else {
1012  ///   2 = MemoryDef(liveOnEntry)
1013  ///   store %b
1014  /// }
1015  /// 3 = MemoryPhi(2, 1)
1016  /// MemoryUse(3)
1017  /// load %a
1018  ///
1019  /// calling this API on load(%a) will return the MemoryPhi, not the MemoryDef
1020  /// in the if (a) branch.
1021  MemoryAccess *getClobberingMemoryAccess(const Instruction *I) {
1022    MemoryAccess *MA = MSSA->getMemoryAccess(I);
1023    assert(MA && "Handed an instruction that MemorySSA doesn't recognize?")((MA && "Handed an instruction that MemorySSA doesn't recognize?"
) ? static_cast<void> (0) : __assert_fail ("MA && \"Handed an instruction that MemorySSA doesn't recognize?\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 1023, __PRETTY_FUNCTION__));
1024    return getClobberingMemoryAccess(MA);
1025  }
1026 
1027  /// Does the same thing as getClobberingMemoryAccess(const Instruction *I),
1028  /// but takes a MemoryAccess instead of an Instruction.
1029  virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) = 0;
1030 
1031  /// Given a potentially clobbering memory access and a new location,
1032  /// calling this will give you the nearest dominating clobbering MemoryAccess
1033  /// (by skipping non-aliasing def links).
1034  ///
1035  /// This version of the function is mainly used to disambiguate phi translated
1036  /// pointers, where the value of a pointer may have changed from the initial
1037  /// memory access. Note that this expects to be handed either a MemoryUse,
1038  /// or an already potentially clobbering access. Unlike the above API, if
1039  /// given a MemoryDef that clobbers the pointer as the starting access, it
1040  /// will return that MemoryDef, whereas the above would return the clobber
1041  /// starting from the use side of  the memory def.
1042  virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
1043                                                  const MemoryLocation &) = 0;
1044 
1045  /// Given a memory access, invalidate anything this walker knows about
1046  /// that access.
1047  /// This API is used by walkers that store information to perform basic cache
1048  /// invalidation.  This will be called by MemorySSA at appropriate times for
1049  /// the walker it uses or returns.
1050  virtual void invalidateInfo(MemoryAccess *) {}
1051 
1052protected:
1053  friend class MemorySSA; // For updating MSSA pointer in MemorySSA move
1054                          // constructor.
1055  MemorySSA *MSSA;
1056};
1057 
1058/// A MemorySSAWalker that does no alias queries, or anything else. It
1059/// simply returns the links as they were constructed by the builder.
1060class DoNothingMemorySSAWalker final : public MemorySSAWalker {
1061public:
1062  // Keep the overrides below from hiding the Instruction overload of
1063  // getClobberingMemoryAccess.
1064  using MemorySSAWalker::getClobberingMemoryAccess;
1065 
1066  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) override;
1067  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
1068                                          const MemoryLocation &) override;
1069};
1070 
1071using MemoryAccessPair = std::pair<MemoryAccess *, MemoryLocation>;
1072using ConstMemoryAccessPair = std::pair<const MemoryAccess *, MemoryLocation>;
1073 
1074/// Iterator base class used to implement const and non-const iterators
1075/// over the defining accesses of a MemoryAccess.
1076template <class T>
1077class memoryaccess_def_iterator_base
1078    : public iterator_facade_base<memoryaccess_def_iterator_base<T>,
1079                                  std::forward_iterator_tag, T, ptrdiff_t, T *,
1080                                  T *> {
1081  using BaseT = typename memoryaccess_def_iterator_base::iterator_facade_base;
1082 
1083public:
1084  memoryaccess_def_iterator_base(T *Start) : Access(Start) {}
1085  memoryaccess_def_iterator_base() = default;
1086 
1087  bool operator==(const memoryaccess_def_iterator_base &Other) const {
1088    return Access == Other.Access && (!Access || ArgNo == Other.ArgNo);
1089  }
1090 
1091  // This is a bit ugly, but for MemoryPHI's, unlike PHINodes, you can't get the
1092  // block from the operand in constant time (In a PHINode, the uselist has
1093  // both, so it's just subtraction). We provide it as part of the
1094  // iterator to avoid callers having to linear walk to get the block.
1095  // If the operation becomes constant time on MemoryPHI's, this bit of
1096  // abstraction breaking should be removed.
1097  BasicBlock *getPhiArgBlock() const {
1098    MemoryPhi *MP = dyn_cast<MemoryPhi>(Access);
1099    assert(MP && "Tried to get phi arg block when not iterating over a PHI")((MP && "Tried to get phi arg block when not iterating over a PHI"
) ? static_cast<void> (0) : __assert_fail ("MP && \"Tried to get phi arg block when not iterating over a PHI\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 1099, __PRETTY_FUNCTION__));
1100    return MP->getIncomingBlock(ArgNo);
1101  }
1102 
1103  typename std::iterator_traits<BaseT>::pointer operator*() const {
1104    assert(Access && "Tried to access past the end of our iterator")((Access && "Tried to access past the end of our iterator"
) ? static_cast<void> (0) : __assert_fail ("Access && \"Tried to access past the end of our iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 1104, __PRETTY_FUNCTION__));
1105    // Go to the first argument for phis, and the defining access for everything
1106    // else.
1107    if (const MemoryPhi *MP = dyn_cast<MemoryPhi>(Access))
1108      return MP->getIncomingValue(ArgNo);
1109    return cast<MemoryUseOrDef>(Access)->getDefiningAccess();
1110  }
1111 
1112  using BaseT::operator++;
1113  memoryaccess_def_iterator_base &operator++() {
1114    assert(Access && "Hit end of iterator")((Access && "Hit end of iterator") ? static_cast<void
> (0) : __assert_fail ("Access && \"Hit end of iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 1114, __PRETTY_FUNCTION__));
1115    if (const MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) {
1116      if (++ArgNo >= MP->getNumIncomingValues()) {
1117        ArgNo = 0;
1118        Access = nullptr;
1119      }
1120    } else {
1121      Access = nullptr;
1122    }
1123    return *this;
1124  }
1125 
1126private:
1127  T *Access = nullptr;
1128  unsigned ArgNo = 0;
1129};
1130 
1131inline memoryaccess_def_iterator MemoryAccess::defs_begin() {
1132  return memoryaccess_def_iterator(this);
1133}
1134 
1135inline const_memoryaccess_def_iterator MemoryAccess::defs_begin() const {
1136  return const_memoryaccess_def_iterator(this);
1137}
1138 
1139inline memoryaccess_def_iterator MemoryAccess::defs_end() {
1140  return memoryaccess_def_iterator();
1141}
1142 
1143inline const_memoryaccess_def_iterator MemoryAccess::defs_end() const {
1144  return const_memoryaccess_def_iterator();
1145}
1146 
1147/// GraphTraits for a MemoryAccess, which walks defs in the normal case,
1148/// and uses in the inverse case.
1149template <> struct GraphTraits<MemoryAccess *> {
1150  using NodeRef = MemoryAccess *;
1151  using ChildIteratorType = memoryaccess_def_iterator;
1152 
1153  static NodeRef getEntryNode(NodeRef N) { return N; }
1154  static ChildIteratorType child_begin(NodeRef N) { return N->defs_begin(); }
1155  static ChildIteratorType child_end(NodeRef N) { return N->defs_end(); }
1156};
1157 
1158template <> struct GraphTraits<Inverse<MemoryAccess *>> {
1159  using NodeRef = MemoryAccess *;
1160  using ChildIteratorType = MemoryAccess::iterator;
1161 
1162  static NodeRef getEntryNode(NodeRef N) { return N; }
1163  static ChildIteratorType child_begin(NodeRef N) { return N->user_begin(); }
1164  static ChildIteratorType child_end(NodeRef N) { return N->user_end(); }
1165};
1166 
1167/// Provide an iterator that walks defs, giving both the memory access,
1168/// and the current pointer location, updating the pointer location as it
1169/// changes due to phi node translation.
1170///
1171/// This iterator, while somewhat specialized, is what most clients actually
1172/// want when walking upwards through MemorySSA def chains. It takes a pair of
1173/// <MemoryAccess,MemoryLocation>, and walks defs, properly translating the
1174/// memory location through phi nodes for the user.
1175class upward_defs_iterator
1176    : public iterator_facade_base<upward_defs_iterator,
1177                                  std::forward_iterator_tag,
1178                                  const MemoryAccessPair> {
1179  using BaseT = upward_defs_iterator::iterator_facade_base;
1180 
1181public:
1182  upward_defs_iterator(const MemoryAccessPair &Info, DominatorTree *DT,
1183                       bool *PerformedPhiTranslation = nullptr)
1184      : DefIterator(Info.first), Location(Info.second),
1185        OriginalAccess(Info.first), DT(DT),
1186        PerformedPhiTranslation(PerformedPhiTranslation) {
1187    CurrentPair.first = nullptr;
1188 
1189    WalkingPhi = Info.first && isa<MemoryPhi>(Info.first);
1190    fillInCurrentPair();
1191  }
1192 
1193  upward_defs_iterator() { CurrentPair.first = nullptr; }
1194 
1195  bool operator==(const upward_defs_iterator &Other) const {
1196    return DefIterator == Other.DefIterator;
1197  }
1198 
1199  typename std::iterator_traits<BaseT>::reference operator*() const {
1200    assert(DefIterator != OriginalAccess->defs_end() &&((DefIterator != OriginalAccess->defs_end() && "Tried to access past the end of our iterator"
) ? static_cast<void> (0) : __assert_fail ("DefIterator != OriginalAccess->defs_end() && \"Tried to access past the end of our iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 1201, __PRETTY_FUNCTION__))
1201           "Tried to access past the end of our iterator")((DefIterator != OriginalAccess->defs_end() && "Tried to access past the end of our iterator"
) ? static_cast<void> (0) : __assert_fail ("DefIterator != OriginalAccess->defs_end() && \"Tried to access past the end of our iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 1201, __PRETTY_FUNCTION__));
1202    return CurrentPair;
1203  }
1204 
1205  using BaseT::operator++;
1206  upward_defs_iterator &operator++() {
1207    assert(DefIterator != OriginalAccess->defs_end() &&((DefIterator != OriginalAccess->defs_end() && "Tried to access past the end of the iterator"
) ? static_cast<void> (0) : __assert_fail ("DefIterator != OriginalAccess->defs_end() && \"Tried to access past the end of the iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 1208, __PRETTY_FUNCTION__))
1208           "Tried to access past the end of the iterator")((DefIterator != OriginalAccess->defs_end() && "Tried to access past the end of the iterator"
) ? static_cast<void> (0) : __assert_fail ("DefIterator != OriginalAccess->defs_end() && \"Tried to access past the end of the iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 1208, __PRETTY_FUNCTION__));
1209    ++DefIterator;
1210    if (DefIterator != OriginalAccess->defs_end())
1211      fillInCurrentPair();
1212    return *this;
1213  }
1214 
1215  BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); }
1216 
1217private:
1218  /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
1219  /// loop. In particular, this guarantees that it only references a single
1220  /// MemoryLocation during execution of the containing function.
1221  bool IsGuaranteedLoopInvariant(Value *Ptr) const;
1222 
1223  void fillInCurrentPair() {
1224    CurrentPair.first = *DefIterator;
1225    CurrentPair.second = Location;
1226    if (WalkingPhi && Location.Ptr) {
1227      // Mark size as unknown, if the location is not guaranteed to be
1228      // loop-invariant for any possible loop in the function. Setting the size
1229      // to unknown guarantees that any memory accesses that access locations
1230      // after the pointer are considered as clobbers, which is important to
1231      // catch loop carried dependences.
1232      if (Location.Ptr &&
1233          !IsGuaranteedLoopInvariant(const_cast<Value *>(Location.Ptr)))
1234        CurrentPair.second =
1235            Location.getWithNewSize(LocationSize::beforeOrAfterPointer());
1236      PHITransAddr Translator(
1237          const_cast<Value *>(Location.Ptr),
1238          OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr);
1239 
1240      if (!Translator.PHITranslateValue(OriginalAccess->getBlock(),
1241                                        DefIterator.getPhiArgBlock(), DT,
1242                                        true)) {
1243        Value *TransAddr = Translator.getAddr();
1244        if (TransAddr != Location.Ptr) {
1245          CurrentPair.second = CurrentPair.second.getWithNewPtr(TransAddr);
1246 
1247          if (TransAddr &&
1248              !IsGuaranteedLoopInvariant(const_cast<Value *>(TransAddr)))
1249            CurrentPair.second = CurrentPair.second.getWithNewSize(
1250                LocationSize::beforeOrAfterPointer());
1251 
1252          if (PerformedPhiTranslation)
1253            *PerformedPhiTranslation = true;
1254        }
1255      }
1256    }
1257  }
1258 
1259  MemoryAccessPair CurrentPair;
1260  memoryaccess_def_iterator DefIterator;
1261  MemoryLocation Location;
1262  MemoryAccess *OriginalAccess = nullptr;
1263  DominatorTree *DT = nullptr;
1264  bool WalkingPhi = false;
1265  bool *PerformedPhiTranslation = nullptr;
1266};
1267 
1268inline upward_defs_iterator
1269upward_defs_begin(const MemoryAccessPair &Pair, DominatorTree &DT,
1270                  bool *PerformedPhiTranslation = nullptr) {
1271  return upward_defs_iterator(Pair, &DT, PerformedPhiTranslation);
1272}
1273 
1274inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); }
1275 
1276inline iterator_range<upward_defs_iterator>
1277upward_defs(const MemoryAccessPair &Pair, DominatorTree &DT) {
1278  return make_range(upward_defs_begin(Pair, DT), upward_defs_end());
1279}
1280 
1281/// Walks the defining accesses of MemoryDefs. Stops after we hit something that
1282/// has no defining use (e.g. a MemoryPhi or liveOnEntry). Note that, when
1283/// comparing against a null def_chain_iterator, this will compare equal only
1284/// after walking said Phi/liveOnEntry.
1285///
1286/// The UseOptimizedChain flag specifies whether to walk the clobbering
1287/// access chain, or all the accesses.
1288///
1289/// Normally, MemoryDef are all just def/use linked together, so a def_chain on
1290/// a MemoryDef will walk all MemoryDefs above it in the program until it hits
1291/// a phi node.  The optimized chain walks the clobbering access of a store.
1292/// So if you are just trying to find, given a store, what the next
1293/// thing that would clobber the same memory is, you want the optimized chain.
1294template <class T, bool UseOptimizedChain = false>
1295struct def_chain_iterator
1296    : public iterator_facade_base<def_chain_iterator<T, UseOptimizedChain>,
1297                                  std::forward_iterator_tag, MemoryAccess *> {
1298  def_chain_iterator() : MA(nullptr) {}
1299  def_chain_iterator(T MA) : MA(MA) {}
1300 
1301  T operator*() const { return MA; }
1302 
1303  def_chain_iterator &operator++() {
1304    // N.B. liveOnEntry has a null defining access.
1305    if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
1306      if (UseOptimizedChain && MUD->isOptimized())
1307        MA = MUD->getOptimized();
1308      else
1309        MA = MUD->getDefiningAccess();
1310    } else {
1311      MA = nullptr;
1312    }
1313 
1314    return *this;
1315  }
1316 
1317  bool operator==(const def_chain_iterator &O) const { return MA == O.MA; }
1318 
1319private:
1320  T MA;
1321};
1322 
1323template <class T>
1324inline iterator_range<def_chain_iterator<T>>
1325def_chain(T MA, MemoryAccess *UpTo = nullptr) {
1326#ifdef EXPENSIVE_CHECKS
1327  assert((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) &&(((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<
T>()) && "UpTo isn't in the def chain!") ? static_cast
<void> (0) : __assert_fail ("(!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) && \"UpTo isn't in the def chain!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 1328, __PRETTY_FUNCTION__))
1328         "UpTo isn't in the def chain!")(((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<
T>()) && "UpTo isn't in the def chain!") ? static_cast
<void> (0) : __assert_fail ("(!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) && \"UpTo isn't in the def chain!\""
, "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/MemorySSA.h"
, 1328, __PRETTY_FUNCTION__));
1329#endif
1330  return make_range(def_chain_iterator<T>(MA), def_chain_iterator<T>(UpTo));
1331}
1332 
1333template <class T>
1334inline iterator_range<def_chain_iterator<T, true>> optimized_def_chain(T MA) {
1335  return make_range(def_chain_iterator<T, true>(MA),
1336                    def_chain_iterator<T, true>(nullptr));
1337}
1338 
1339} // end namespace llvm
1340 
1341#endif // LLVM_ANALYSIS_MEMORYSSA_H

←

/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/AliasAnalysis.h

1//===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the generic AliasAnalysis interface, which is used as the
10// common interface used by all clients of alias analysis information, and
11// implemented by all alias analysis implementations.  Mod/Ref information is
12// also captured by this interface.
13//
14// Implementations of this interface must implement the various virtual methods,
15// which automatically provides functionality for the entire suite of client
16// APIs.
17//
18// This API identifies memory regions with the MemoryLocation class. The pointer
19// component specifies the base memory address of the region. The Size specifies
20// the maximum size (in address units) of the memory region, or
21// MemoryLocation::UnknownSize if the size is not known. The TBAA tag
22// identifies the "type" of the memory reference; see the
23// TypeBasedAliasAnalysis class for details.
24//
25// Some non-obvious details include:
26//  - Pointers that point to two completely different objects in memory never
27//    alias, regardless of the value of the Size component.
28//  - NoAlias doesn't imply inequal pointers. The most obvious example of this
29//    is two pointers to constant memory. Even if they are equal, constant
30//    memory is never stored to, so there will never be any dependencies.
31//    In this and other situations, the pointers may be both NoAlias and
32//    MustAlias at the same time. The current API can only return one result,
33//    though this is rarely a problem in practice.
34//
35//===----------------------------------------------------------------------===//

37#ifndef LLVM_ANALYSIS_ALIASANALYSIS_H
38#define LLVM_ANALYSIS_ALIASANALYSIS_H

40#include "llvm/ADT/DenseMap.h"
41#include "llvm/ADT/None.h"
42#include "llvm/ADT/Optional.h"
43#include "llvm/ADT/SmallVector.h"
44#include "llvm/Analysis/MemoryLocation.h"
45#include "llvm/IR/PassManager.h"
46#include "llvm/Pass.h"
47#include <cstdint>
48#include <functional>
49#include <memory>
50#include <vector>

52namespace llvm {

54class AnalysisUsage;
55class AtomicCmpXchgInst;
56class BasicAAResult;
57class BasicBlock;
58class CatchPadInst;
59class CatchReturnInst;
60class DominatorTree;
61class FenceInst;
62class Function;
63class InvokeInst;
64class PreservedAnalyses;
65class TargetLibraryInfo;
66class Value;

68/// The possible results of an alias query.
69///
70/// These results are always computed between two MemoryLocation objects as
71/// a query to some alias analysis.
72///
73/// Note that these are unscoped enumerations because we would like to support
74/// implicitly testing a result for the existence of any possible aliasing with
75/// a conversion to bool, but an "enum class" doesn't support this. The
76/// canonical names from the literature are suffixed and unique anyways, and so
77/// they serve as global constants in LLVM for these results.
78///
79/// See docs/AliasAnalysis.html for more information on the specific meanings
80/// of these values.
81class AliasResult {
82private:
static const int OffsetBits = 23;
static const int AliasBits = 8;
static_assert(AliasBits + 1 + OffsetBits <= 32,
              "AliasResult size is intended to be 4 bytes!");

unsigned int Alias : AliasBits;
unsigned int HasOffset : 1;
signed int Offset : OffsetBits;

92public:
enum Result : uint8_t {
  /// The two locations do not alias at all.
  ///
  /// This value is arranged to convert to false, while all other values
  /// convert to true. This allows a boolean context to convert the result to
  /// a binary flag indicating whether there is the possibility of aliasing.
  NoAlias = 0,
  /// The two locations may or may not alias. This is the least precise
  /// result.
  MayAlias,
  /// The two locations alias, but only due to a partial overlap.
  PartialAlias,
  /// The two locations precisely alias each other.
  MustAlias,
};
static_assert(MustAlias < (1 << AliasBits),
              "Not enough bit field size for the enum!");

explicit AliasResult() = delete;
constexpr AliasResult(const Result &Alias)
    : Alias(Alias), HasOffset(false), Offset(0) {}

operator Result() const { return static_cast<Result>(Alias); }

constexpr bool hasOffset() const { return HasOffset; }
constexpr int32_t getOffset() const {
  assert(HasOffset && "No offset!")((HasOffset && "No offset!") ? static_cast<void>
 (0) : __assert_fail ("HasOffset && \"No offset!\"", "/build/llvm-toolchain-snapshot-13~++20210413100635+64c24f493e5f/llvm/include/llvm/Analysis/AliasAnalysis.h"
, 119, __PRETTY_FUNCTION__));
  return Offset;
}
void setOffset(int32_t NewOffset) {
  if (isInt<OffsetBits>(NewOffset)) {
    HasOffset = true;
    Offset = NewOffset;
  }
}

/// Helper for processing AliasResult for swapped memory location pairs.
void swap(bool DoSwap) {
  if (DoSwap && hasOffset())
    setOffset(-getOffset());
}
134};

136static_assert(sizeof(AliasResult) == 4,
            "AliasResult size is intended to be 4 bytes!");

139/// << operator for AliasResult.
140raw_ostream &operator<<(raw_ostream &OS, AliasResult AR);

142/// Flags indicating whether a memory access modifies or references memory.
143///
144/// This is no access at all, a modification, a reference, or both
145/// a modification and a reference. These are specifically structured such that
146/// they form a three bit matrix and bit-tests for 'mod' or 'ref' or 'must'
147/// work with any of the possible values.
148enum class ModRefInfo : uint8_t {
/// Must is provided for completeness, but no routines will return only
/// Must today. See definition of Must below.
Must = 0,
/// The access may reference the value stored in memory,
/// a mustAlias relation was found, and no mayAlias or partialAlias found.
MustRef = 1,
/// The access may modify the value stored in memory,
/// a mustAlias relation was found, and no mayAlias or partialAlias found.
MustMod = 2,
/// The access may reference, modify or both the value stored in memory,
/// a mustAlias relation was found, and no mayAlias or partialAlias found.
MustModRef = MustRef | MustMod,
/// The access neither references nor modifies the value stored in memory.
NoModRef = 4,
/// The access may reference the value stored in memory.
Ref = NoModRef | MustRef,
/// The access may modify the value stored in memory.
Mod = NoModRef | MustMod,
/// The access may reference and may modify the value stored in memory.
ModRef = Ref | Mod,

/// About Must:
/// Must is set in a best effort manner.
/// We usually do not try our best to infer Must, instead it is merely
/// another piece of "free" information that is presented when available.
/// Must set means there was certainly a MustAlias found. For calls,
/// where multiple arguments are checked (argmemonly), this translates to
/// only MustAlias or NoAlias was found.
/// Must is not set for RAR accesses, even if the two locations must
/// alias. The reason is that two read accesses translate to an early return
/// of NoModRef. An additional alias check to set Must may be
/// expensive. Other cases may also not set Must(e.g. callCapturesBefore).
/// We refer to Must being *set* when the most significant bit is *cleared*.
/// Conversely we *clear* Must information by *setting* the Must bit to 1.
183};

185LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isNoModRef(const ModRefInfo MRI) {
return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) ==
       static_cast<int>(ModRefInfo::Must);
188}
189LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isModOrRefSet(const ModRefInfo MRI) {
return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef);
191}
192LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isModAndRefSet(const ModRefInfo MRI) {
return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) ==
       static_cast<int>(ModRefInfo::MustModRef);
195}
196LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isModSet(const ModRefInfo MRI) {
return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustMod);
198}
199LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isRefSet(const ModRefInfo MRI) {
return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustRef);
201}
202LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isMustSet(const ModRefInfo MRI) {
return !(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::NoModRef));
204}

206LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo setMod(const ModRefInfo MRI) {
return ModRefInfo(static_cast<int>(MRI) |
                  static_cast<int>(ModRefInfo::MustMod));
209}
210LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo setRef(const ModRefInfo MRI) {
return ModRefInfo(static_cast<int>(MRI) |
                  static_cast<int>(ModRefInfo::MustRef));
213}
214LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo setMust(const ModRefInfo MRI) {
return ModRefInfo(static_cast<int>(MRI) &
                  static_cast<int>(ModRefInfo::MustModRef));
217}
218LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo setModAndRef(const ModRefInfo MRI) {
return ModRefInfo(static_cast<int>(MRI) |
                  static_cast<int>(ModRefInfo::MustModRef));
221}
222LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo clearMod(const ModRefInfo MRI) {
return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Ref));
224}
225LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo clearRef(const ModRefInfo MRI) {
return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Mod));
227}
228LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo clearMust(const ModRefInfo MRI) {
return ModRefInfo(static_cast<int>(MRI) |
                  static_cast<int>(ModRefInfo::NoModRef));
231}
232LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo unionModRef(const ModRefInfo MRI1,
                                           const ModRefInfo MRI2) {
return ModRefInfo(static_cast<int>(MRI1) | static_cast<int>(MRI2));
235}
236LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo intersectModRef(const ModRefInfo MRI1,
                                               const ModRefInfo MRI2) {
return ModRefInfo(static_cast<int>(MRI1) & static_cast<int>(MRI2));
239}

241/// The locations at which a function might access memory.
242///
243/// These are primarily used in conjunction with the \c AccessKind bits to
244/// describe both the nature of access and the locations of access for a
245/// function call.
246enum FunctionModRefLocation {
/// Base case is no access to memory.
FMRL_Nowhere = 0,
/// Access to memory via argument pointers.
FMRL_ArgumentPointees = 8,
/// Memory that is inaccessible via LLVM IR.
FMRL_InaccessibleMem = 16,
/// Access to any memory.
FMRL_Anywhere = 32 | FMRL_InaccessibleMem | FMRL_ArgumentPointees
255};

257/// Summary of how a function affects memory in the program.
258///
259/// Loads from constant globals are not considered memory accesses for this
260/// interface. Also, functions may freely modify stack space local to their
261/// invocation without having to report it through these interfaces.
262enum FunctionModRefBehavior {
/// This function does not perform any non-local loads or stores to memory.
///
/// This property corresponds to the GCC 'const' attribute.
/// This property corresponds to the LLVM IR 'readnone' attribute.
/// This property corresponds to the IntrNoMem LLVM intrinsic flag.
FMRB_DoesNotAccessMemory =
    FMRL_Nowhere | static_cast<int>(ModRefInfo::NoModRef),

/// The only memory references in this function (if it has any) are
/// non-volatile loads from objects pointed to by its pointer-typed
/// arguments, with arbitrary offsets.
///
/// This property corresponds to the combination of the IntrReadMem
/// and IntrArgMemOnly LLVM intrinsic flags.
FMRB_OnlyReadsArgumentPointees =
    FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::Ref),

/// The only memory references in this function (if it has any) are
/// non-volatile stores from objects pointed to by its pointer-typed
/// arguments, with arbitrary offsets.
///
/// This property corresponds to the combination of the IntrWriteMem
/// and IntrArgMemOnly LLVM intrinsic flags.
FMRB_OnlyWritesArgumentPointees =
    FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::Mod),

/// The only memory references in this function (if it has any) are
/// non-volatile loads and stores from objects pointed to by its
/// pointer-typed arguments, with arbitrary offsets.
///
/// This property corresponds to the IntrArgMemOnly LLVM intrinsic flag.
FMRB_OnlyAccessesArgumentPointees =
    FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::ModRef),

/// The only memory references in this function (if it has any) are
/// reads of memory that is otherwise inaccessible via LLVM IR.
///
/// This property corresponds to the LLVM IR inaccessiblememonly attribute.
FMRB_OnlyReadsInaccessibleMem =
    FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::Ref),

/// The only memory references in this function (if it has any) are
/// writes to memory that is otherwise inaccessible via LLVM IR.
///
/// This property corresponds to the LLVM IR inaccessiblememonly attribute.
FMRB_OnlyWritesInaccessibleMem =
    FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::Mod),

/// The only memory references in this function (if it has any) are
/// references of memory that is otherwise inaccessible via LLVM IR.
///
/// This property corresponds to the LLVM IR inaccessiblememonly attribute.
FMRB_OnlyAccessesInaccessibleMem =
    FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::ModRef),

/// The function may perform non-volatile loads from objects pointed
/// to by its pointer-typed arguments, with arbitrary offsets, and
/// it may also perform loads of memory that is otherwise
/// inaccessible via LLVM IR.
///
/// This property corresponds to the LLVM IR
/// inaccessiblemem_or_argmemonly attribute.
FMRB_OnlyReadsInaccessibleOrArgMem = FMRL_InaccessibleMem |
                                     FMRL_ArgumentPointees |
                                     static_cast<int>(ModRefInfo::Ref),

/// The function may perform non-volatile stores to objects pointed
/// to by its pointer-typed arguments, with arbitrary offsets, and
/// it may also perform stores of memory that is otherwise
/// inaccessible via LLVM IR.
///
/// This property corresponds to the LLVM IR
/// inaccessiblemem_or_argmemonly attribute.
FMRB_OnlyWritesInaccessibleOrArgMem = FMRL_InaccessibleMem |
                                      FMRL_ArgumentPointees |
                                      static_cast<int>(ModRefInfo::Mod),

/// The function may perform non-volatile loads and stores of objects
/// pointed to by its pointer-typed arguments, with arbitrary offsets, and
/// it may also perform loads and stores of memory that is otherwise
/// inaccessible via LLVM IR.
///
/// This property corresponds to the LLVM IR
/// inaccessiblemem_or_argmemonly attribute.
FMRB_OnlyAccessesInaccessibleOrArgMem = FMRL_InaccessibleMem |
                                        FMRL_ArgumentPointees |
                                        static_cast<int>(ModRefInfo::ModRef),

/// This function does not perform any non-local stores or volatile loads,
/// but may read from any memory location.
///
/// This property corresponds to the GCC 'pure' attribute.
/// This property corresponds to the LLVM IR 'readonly' attribute.
/// This property corresponds to the IntrReadMem LLVM intrinsic flag.
FMRB_OnlyReadsMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Ref),

// This function does not read from memory anywhere, but may write to any
// memory location.
//
// This property corresponds to the LLVM IR 'writeonly' attribute.
// This property corresponds to the IntrWriteMem LLVM intrinsic flag.
FMRB_OnlyWritesMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Mod),

/// This indicates that the function could not be classified into one of the
/// behaviors above.
FMRB_UnknownModRefBehavior =
    FMRL_Anywhere | static_cast<int>(ModRefInfo::ModRef)
370};

372// Wrapper method strips bits significant only in FunctionModRefBehavior,
373// to obtain a valid ModRefInfo. The benefit of using the wrapper is that if
374// ModRefInfo enum changes, the wrapper can be updated to & with the new enum
375// entry with all bits set to 1.
376LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo
377createModRefInfo(const FunctionModRefBehavior FMRB) {
return ModRefInfo(FMRB & static_cast<int>(ModRefInfo::ModRef));
379}

381/// Reduced version of MemoryLocation that only stores a pointer and size.
382/// Used for caching AATags independent BasicAA results.
383struct AACacheLoc {
const Value *Ptr;
LocationSize Size;
386};

388template <> struct DenseMapInfo<AACacheLoc> {
static inline AACacheLoc getEmptyKey() {
  return {DenseMapInfo<const Value *>::getEmptyKey(),
          DenseMapInfo<LocationSize>::getEmptyKey()};
}
static inline AACacheLoc getTombstoneKey() {
  return {DenseMapInfo<const Value *>::getTombstoneKey(),
          DenseMapInfo<LocationSize>::getTombstoneKey()};
}
static unsigned getHashValue(const AACacheLoc &Val) {
  return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^
         DenseMapInfo<LocationSize>::getHashValue(Val.Size);
}
static bool isEqual(const AACacheLoc &LHS, const AACacheLoc &RHS) {
  return LHS.Ptr == RHS.Ptr && LHS.Size == RHS.Size;
}
404};

406/// This class stores info we want to provide to or retain within an alias
407/// query. By default, the root query is stateless and starts with a freshly
408/// constructed info object. Specific alias analyses can use this query info to
409/// store per-query state that is important for recursive or nested queries to
410/// avoid recomputing. To enable preserving this state across multiple queries
411/// where safe (due to the IR not changing), use a `BatchAAResults` wrapper.
412/// The information stored in an `AAQueryInfo` is currently limitted to the
413/// caches used by BasicAA, but can further be extended to fit other AA needs.
414class AAQueryInfo {
415public:
using LocPair = std::pair<AACacheLoc, AACacheLoc>;
struct CacheEntry {
  AliasResult Result;
  /// Number of times a NoAlias assumption has been used.
  /// 0 for assumptions that have not been used, -1 for definitive results.
  int NumAssumptionUses;
  /// Whether this is a definitive (non-assumption) result.
  bool isDefinitive() const { return NumAssumptionUses < 0; }
};
using AliasCacheT = SmallDenseMap<LocPair, CacheEntry, 8>;
AliasCacheT AliasCache;

using IsCapturedCacheT = SmallDenseMap<const Value *, bool, 8>;
IsCapturedCacheT IsCapturedCache;

/// Query depth used to distinguish recursive queries.
unsigned Depth = 0;

/// How many active NoAlias assumption uses there are.
int NumAssumptionUses = 0;

/// Location pairs for which an assumption based result is currently stored.
/// Used to remove all potentially incorrect results from the cache if an
/// assumption is disproven.
SmallVector<AAQueryInfo::LocPair, 4> AssumptionBasedResults;

AAQueryInfo() : AliasCache(), IsCapturedCache() {}

/// Create a new AAQueryInfo based on this one, but with the cache cleared.
/// This is used for recursive queries across phis, where cache results may
/// not be valid.
AAQueryInfo withEmptyCache() {
  AAQueryInfo NewAAQI;
  NewAAQI.Depth = Depth;
  return NewAAQI;
}
452};

454class BatchAAResults;

456class AAResults {
457public:
// Make these results default constructable and movable. We have to spell
// these out because MSVC won't synthesize them.
AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {}
AAResults(AAResults &&Arg);
~AAResults();

/// Register a specific AA result.
template <typename AAResultT> void addAAResult(AAResultT &AAResult) {
  // FIXME: We should use a much lighter weight system than the usual
  // polymorphic pattern because we don't own AAResult. It should
  // ideally involve two pointers and no separate allocation.
  AAs.emplace_back(new Model<AAResultT>(AAResult, *this));
}

/// Register a function analysis ID that the results aggregation depends on.
///
/// This is used in the new pass manager to implement the invalidation logic
/// where we must invalidate the results aggregation if any of our component
/// analyses become invalid.
void addAADependencyID(AnalysisKey *ID) { AADeps.push_back(ID); }

/// Handle invalidation events in the new pass manager.
///
/// The aggregation is invalidated if any of the underlying analyses is
/// invalidated.
bool invalidate(Function &F, const PreservedAnalyses &PA,
                FunctionAnalysisManager::Invalidator &Inv);

//===--------------------------------------------------------------------===//
/// \name Alias Queries
/// @{

/// The main low level interface to the alias analysis implementation.
/// Returns an AliasResult indicating whether the two pointers are aliased to
/// each other. This is the interface that must be implemented by specific
/// alias analysis implementations.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);

/// A convenience wrapper around the primary \c alias interface.
AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2,
                  LocationSize V2Size) {
  return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
}

/// A convenience wrapper around the primary \c alias interface.
AliasResult alias(const Value *V1, const Value *V2) {
  return alias(MemoryLocation::getBeforeOrAfter(V1),
               MemoryLocation::getBeforeOrAfter(V2));
}

/// A trivial helper function to check to see if the specified pointers are
/// no-alias.
bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
  return alias(LocA, LocB) == AliasResult::NoAlias;
}

/// A convenience wrapper around the \c isNoAlias helper interface.
bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2,
               LocationSize V2Size) {
  return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
}

/// A convenience wrapper around the \c isNoAlias helper interface.
bool isNoAlias(const Value *V1, const Value *V2) {
  return isNoAlias(MemoryLocation::getBeforeOrAfter(V1),
                   MemoryLocation::getBeforeOrAfter(V2));
}

/// A trivial helper function to check to see if the specified pointers are
/// must-alias.
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
  return alias(LocA, LocB) == AliasResult::MustAlias;
}

/// A convenience wrapper around the \c isMustAlias helper interface.
bool isMustAlias(const Value *V1, const Value *V2) {
  return alias(V1, LocationSize::precise(1), V2, LocationSize::precise(1)) ==
21
←
Assuming the condition is false→
22
←
Returning zero, which participates in a condition later→
         AliasResult::MustAlias;
}

/// Checks whether the given location points to constant memory, or if
/// \p OrLocal is true whether it points to a local alloca.
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false);

/// A convenience wrapper around the primary \c pointsToConstantMemory
/// interface.
bool pointsToConstantMemory(const Value *P, bool OrLocal = false) {
  return pointsToConstantMemory(MemoryLocation::getBeforeOrAfter(P), OrLocal);
}

/// @}
//===--------------------------------------------------------------------===//
/// \name Simple mod/ref information
/// @{

/// Get the ModRef info associated with a pointer argument of a call. The
/// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
/// that these bits do not necessarily account for the overall behavior of
/// the function, but rather only provide additional per-argument
/// information. This never sets ModRefInfo::Must.
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx);

/// Return the behavior of the given call site.
FunctionModRefBehavior getModRefBehavior(const CallBase *Call);

/// Return the behavior when calling the given function.
FunctionModRefBehavior getModRefBehavior(const Function *F);

/// Checks if the specified call is known to never read or write memory.
///
/// Note that if the call only reads from known-constant memory, it is also
/// legal to return true. Also, calls that unwind the stack are legal for
/// this predicate.
///
/// Many optimizations (such as CSE and LICM) can be performed on such calls
/// without worrying about aliasing properties, and many calls have this
/// property (e.g. calls to 'sin' and 'cos').
///
/// This property corresponds to the GCC 'const' attribute.
bool doesNotAccessMemory(const CallBase *Call) {
  return getModRefBehavior(Call) == FMRB_DoesNotAccessMemory;
}

/// Checks if the specified function is known to never read or write memory.
///
/// Note that if the function only reads from known-constant memory, it is
/// also legal to return true. Also, function that unwind the stack are legal
/// for this predicate.
///
/// Many optimizations (such as CSE and LICM) can be performed on such calls
/// to such functions without worrying about aliasing properties, and many
/// functions have this property (e.g. 'sin' and 'cos').
///
/// This property corresponds to the GCC 'const' attribute.
bool doesNotAccessMemory(const Function *F) {
  return getModRefBehavior(F) == FMRB_DoesNotAccessMemory;
}

/// Checks if the specified call is known to only read from non-volatile
/// memory (or not access memory at all).
///
/// Calls that unwind the stack are legal for this predicate.
///
/// This property allows many common optimizations to be performed in the
/// absence of interfering store instructions, such as CSE of strlen calls.
///
/// This property corresponds to the GCC 'pure' attribute.
bool onlyReadsMemory(const CallBase *Call) {
  return onlyReadsMemory(getModRefBehavior(Call));
}

/// Checks if the specified function is known to only read from non-volatile
/// memory (or not access memory at all).
///
/// Functions that unwind the stack are legal for this predicate.
///
/// This property allows many common optimizations to be performed in the
/// absence of interfering store instructions, such as CSE of strlen calls.
///
/// This property corresponds to the GCC 'pure' attribute.
bool onlyReadsMemory(const Function *F) {
  return onlyReadsMemory(getModRefBehavior(F));
}

/// Checks if functions with the specified behavior are known to only read
/// from non-volatile memory (or not access memory at all).
static bool onlyReadsMemory(FunctionModRefBehavior MRB) {
  return !isModSet(createModRefInfo(MRB));
}

/// Checks if functions with the specified behavior are known to only write
/// memory (or not access memory at all).
static bool doesNotReadMemory(FunctionModRefBehavior MRB) {
  return !isRefSet(createModRefInfo(MRB));
}

/// Checks if functions with the specified behavior are known to read and
/// write at most from objects pointed to by their pointer-typed arguments
/// (with arbitrary offsets).
static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB) {
  return !((unsigned)MRB & FMRL_Anywhere & ~FMRL_ArgumentPointees);
}

/// Checks if functions with the specified behavior are known to potentially
/// read or write from objects pointed to be their pointer-typed arguments
/// (with arbitrary offsets).
static bool doesAccessArgPointees(FunctionModRefBehavior MRB) {
  return isModOrRefSet(createModRefInfo(MRB)) &&
         ((unsigned)MRB & FMRL_ArgumentPointees);
}

/// Checks if functions with the specified behavior are known to read and
/// write at most from memory that is inaccessible from LLVM IR.
static bool onlyAccessesInaccessibleMem(FunctionModRefBehavior MRB) {
  return !((unsigned)MRB & FMRL_Anywhere & ~FMRL_InaccessibleMem);
}

/// Checks if functions with the specified behavior are known to potentially
/// read or write from memory that is inaccessible from LLVM IR.
static bool doesAccessInaccessibleMem(FunctionModRefBehavior MRB) {
  return isModOrRefSet(createModRefInfo(MRB)) &&
           ((unsigned)MRB & FMRL_InaccessibleMem);
}

/// Checks if functions with the specified behavior are known to read and
/// write at most from memory that is inaccessible from LLVM IR or objects
/// pointed to by their pointer-typed arguments (with arbitrary offsets).
static bool onlyAccessesInaccessibleOrArgMem(FunctionModRefBehavior MRB) {
  return !((unsigned)MRB & FMRL_Anywhere &
           ~(FMRL_InaccessibleMem | FMRL_ArgumentPointees));
}

/// getModRefInfo (for call sites) - Return information about whether
/// a particular call site modifies or reads the specified memory location.
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc);

/// getModRefInfo (for call sites) - A convenience wrapper.
ModRefInfo getModRefInfo(const CallBase *Call, const Value *P,
                         LocationSize Size) {
  return getModRefInfo(Call, MemoryLocation(P, Size));
}

/// getModRefInfo (for loads) - Return information about whether
/// a particular load modifies or reads the specified memory location.
ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc);

/// getModRefInfo (for loads) - A convenience wrapper.
ModRefInfo getModRefInfo(const LoadInst *L, const Value *P,
                         LocationSize Size) {
  return getModRefInfo(L, MemoryLocation(P, Size));
}

/// getModRefInfo (for stores) - Return information about whether
/// a particular store modifies or reads the specified memory location.
ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc);

/// getModRefInfo (for stores) - A convenience wrapper.
ModRefInfo getModRefInfo(const StoreInst *S, const Value *P,
                         LocationSize Size) {
  return getModRefInfo(S, MemoryLocation(P, Size));
}

/// getModRefInfo (for fences) - Return information about whether
/// a particular store modifies or reads the specified memory location.
ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc);

/// getModRefInfo (for fences) - A convenience wrapper.
ModRefInfo getModRefInfo(const FenceInst *S, const Value *P,
                         LocationSize Size) {
  return getModRefInfo(S, MemoryLocation(P, Size));
}

/// getModRefInfo (for cmpxchges) - Return information about whether
/// a particular cmpxchg modifies or reads the specified memory location.
ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
                         const MemoryLocation &Loc);

/// getModRefInfo (for cmpxchges) - A convenience wrapper.
ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P,
                         LocationSize Size) {
  return getModRefInfo(CX, MemoryLocation(P, Size));
}

/// getModRefInfo (for atomicrmws) - Return information about whether
/// a particular atomicrmw modifies or reads the specified memory location.
ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc);

/// getModRefInfo (for atomicrmws) - A convenience wrapper.
ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P,
                         LocationSize Size) {
  return getModRefInfo(RMW, MemoryLocation(P, Size));
}

/// getModRefInfo (for va_args) - Return information about whether
/// a particular va_arg modifies or reads the specified memory location.
ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc);

/// getModRefInfo (for va_args) - A convenience wrapper.
ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P,
                         LocationSize Size) {
  return getModRefInfo(I, MemoryLocation(P, Size));
}

/// getModRefInfo (for catchpads) - Return information about whether
/// a particular catchpad modifies or reads the specified memory location.
ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc);

/// getModRefInfo (for catchpads) - A convenience wrapper.
ModRefInfo getModRefInfo(const CatchPadInst *I, const Value *P,
                         LocationSize Size) {
  return getModRefInfo(I, MemoryLocation(P, Size));
}

/// getModRefInfo (for catchrets) - Return information about whether
/// a particular catchret modifies or reads the specified memory location.
ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc);

/// getModRefInfo (for catchrets) - A convenience wrapper.
ModRefInfo getModRefInfo(const CatchReturnInst *I, const Value *P,
                         LocationSize Size) {
  return getModRefInfo(I, MemoryLocation(P, Size));
}

/// Check whether or not an instruction may read or write the optionally
/// specified memory location.
///
///
/// An instruction that doesn't read or write memory may be trivially LICM'd
/// for example.
///
/// For function calls, this delegates to the alias-analysis specific
/// call-site mod-ref behavior queries. Otherwise it delegates to the specific
/// helpers above.
ModRefInfo getModRefInfo(const Instruction *I,
                         const Optional<MemoryLocation> &OptLoc) {
  AAQueryInfo AAQIP;
  return getModRefInfo(I, OptLoc, AAQIP);
}

/// A convenience wrapper for constructing the memory location.
ModRefInfo getModRefInfo(const Instruction *I, const Value *P,
                         LocationSize Size) {
  return getModRefInfo(I, MemoryLocation(P, Size));
}

/// Return information about whether a call and an instruction may refer to
/// the same memory locations.
ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call);

/// Return information about whether two call sites may refer to the same set
/// of memory locations. See the AA documentation for details:
///   http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2);

/// Return information about whether a particular call site modifies
/// or reads the specified memory location \p MemLoc before instruction \p I
/// in a BasicBlock.
/// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being
/// set.
ModRefInfo callCapturesBefore(const Instruction *I,
                              const MemoryLocation &MemLoc, DominatorTree *DT);

/// A convenience wrapper to synthesize a memory location.
ModRefInfo callCapturesBefore(const Instruction *I, const Value *P,
                              LocationSize Size, DominatorTree *DT) {
  return callCapturesBefore(I, MemoryLocation(P, Size), DT);
}

/// @}
//===--------------------------------------------------------------------===//
/// \name Higher level methods for querying mod/ref information.
/// @{

/// Check if it is possible for execution of the specified basic block to
/// modify the location Loc.
bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc);

/// A convenience wrapper synthesizing a memory location.
bool canBasicBlockModify(const BasicBlock &BB, const Value *P,
                         LocationSize Size) {
  return canBasicBlockModify(BB, MemoryLocation(P, Size));
}

/// Check if it is possible for the execution of the specified instructions
/// to mod\ref (according to the mode) the location Loc.
///
/// The instructions to consider are all of the instructions in the range of
/// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block.
bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
                               const MemoryLocation &Loc,
                               const ModRefInfo Mode);

/// A convenience wrapper synthesizing a memory location.
bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
                               const Value *Ptr, LocationSize Size,
                               const ModRefInfo Mode) {
  return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode);
}

837private:
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
                  AAQueryInfo &AAQI);
bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
                            bool OrLocal = false);
ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2,
                         AAQueryInfo &AAQIP);
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
                         AAQueryInfo &AAQI);
ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
                         AAQueryInfo &AAQI);
ModRefInfo getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc,
                         AAQueryInfo &AAQI);
ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc,
                         AAQueryInfo &AAQI);
ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc,
                         AAQueryInfo &AAQI);
ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc,
                         AAQueryInfo &AAQI);
ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
                         const MemoryLocation &Loc, AAQueryInfo &AAQI);
ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc,
                         AAQueryInfo &AAQI);
ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc,
                         AAQueryInfo &AAQI);
ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc,
                         AAQueryInfo &AAQI);
ModRefInfo getModRefInfo(const Instruction *I,
                         const Optional<MemoryLocation> &OptLoc,
                         AAQueryInfo &AAQIP);

class Concept;

template <typename T> class Model;

template <typename T> friend class AAResultBase;

const TargetLibraryInfo &TLI;

std::vector<std::unique_ptr<Concept>> AAs;

std::vector<AnalysisKey *> AADeps;

friend class BatchAAResults;
881};

883/// This class is a wrapper over an AAResults, and it is intended to be used
884/// only when there are no IR changes inbetween queries. BatchAAResults is
885/// reusing the same `AAQueryInfo` to preserve the state across queries,
886/// esentially making AA work in "batch mode". The internal state cannot be
887/// cleared, so to go "out-of-batch-mode", the user must either use AAResults,
888/// or create a new BatchAAResults.
889class BatchAAResults {
AAResults &AA;
AAQueryInfo AAQI;

893public:
BatchAAResults(AAResults &AAR) : AA(AAR), AAQI() {}
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
  return AA.alias(LocA, LocB, AAQI);
}
bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) {
  return AA.pointsToConstantMemory(Loc, AAQI, OrLocal);
}
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc) {
  return AA.getModRefInfo(Call, Loc, AAQI);
}
ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2) {
  return AA.getModRefInfo(Call1, Call2, AAQI);
}
ModRefInfo getModRefInfo(const Instruction *I,
                         const Optional<MemoryLocation> &OptLoc) {
  return AA.getModRefInfo(I, OptLoc, AAQI);
}
ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2) {
  return AA.getModRefInfo(I, Call2, AAQI);
}
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
  return AA.getArgModRefInfo(Call, ArgIdx);
}
FunctionModRefBehavior getModRefBehavior(const CallBase *Call) {
  return AA.getModRefBehavior(Call);
}
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
  return alias(LocA, LocB) == AliasResult::MustAlias;
}
bool isMustAlias(const Value *V1, const Value *V2) {
  return alias(MemoryLocation(V1, LocationSize::precise(1)),
               MemoryLocation(V2, LocationSize::precise(1))) ==
         AliasResult::MustAlias;
}
928};

930/// Temporary typedef for legacy code that uses a generic \c AliasAnalysis
931/// pointer or reference.
932using AliasAnalysis = AAResults;

934/// A private abstract base class describing the concept of an individual alias
935/// analysis implementation.
936///
937/// This interface is implemented by any \c Model instantiation. It is also the
938/// interface which a type used to instantiate the model must provide.
939///
940/// All of these methods model methods by the same name in the \c
941/// AAResults class. Only differences and specifics to how the
942/// implementations are called are documented here.
943class AAResults::Concept {
944public:
virtual ~Concept() = 0;

/// An update API used internally by the AAResults to provide
/// a handle back to the top level aggregation.
virtual void setAAResults(AAResults *NewAAR) = 0;

//===--------------------------------------------------------------------===//
/// \name Alias Queries
/// @{

/// The main low level interface to the alias analysis implementation.
/// Returns an AliasResult indicating whether the two pointers are aliased to
/// each other. This is the interface that must be implemented by specific
/// alias analysis implementations.
virtual AliasResult alias(const MemoryLocation &LocA,
                          const MemoryLocation &LocB, AAQueryInfo &AAQI) = 0;

/// Checks whether the given location points to constant memory, or if
/// \p OrLocal is true whether it points to a local alloca.
virtual bool pointsToConstantMemory(const MemoryLocation &Loc,
                                    AAQueryInfo &AAQI, bool OrLocal) = 0;

/// @}
//===--------------------------------------------------------------------===//
/// \name Simple mod/ref information
/// @{

/// Get the ModRef info associated with a pointer argument of a callsite. The
/// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
/// that these bits do not necessarily account for the overall behavior of
/// the function, but rather only provide additional per-argument
/// information.
virtual ModRefInfo getArgModRefInfo(const CallBase *Call,
                                    unsigned ArgIdx) = 0;

/// Return the behavior of the given call site.
virtual FunctionModRefBehavior getModRefBehavior(const CallBase *Call) = 0;

/// Return the behavior when calling the given function.
virtual FunctionModRefBehavior getModRefBehavior(const Function *F) = 0;

/// getModRefInfo (for call sites) - Return information about whether
/// a particular call site modifies or reads the specified memory location.
virtual ModRefInfo getModRefInfo(const CallBase *Call,
                                 const MemoryLocation &Loc,
                                 AAQueryInfo &AAQI) = 0;

/// Return information about whether two call sites may refer to the same set
/// of memory locations. See the AA documentation for details:
///   http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
virtual ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
                                 AAQueryInfo &AAQI) = 0;

/// @}
999};

1001/// A private class template which derives from \c Concept and wraps some other
1002/// type.
1003///
1004/// This models the concept by directly forwarding each interface point to the
1005/// wrapped type which must implement a compatible interface. This provides
1006/// a type erased binding.
1007template <typename AAResultT> class AAResults::Model final : public Concept {
AAResultT &Result;

1010public:
explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) {
  Result.setAAResults(&AAR);
}
~Model() override = default;

void setAAResults(AAResults *NewAAR) override { Result.setAAResults(NewAAR); }

AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
                  AAQueryInfo &AAQI) override {
  return Result.alias(LocA, LocB, AAQI);
}

bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
                            bool OrLocal) override {
  return Result.pointsToConstantMemory(Loc, AAQI, OrLocal);
}

ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) override {
  return Result.getArgModRefInfo(Call, ArgIdx);
}

FunctionModRefBehavior getModRefBehavior(const CallBase *Call) override {
  return Result.getModRefBehavior(Call);
}

FunctionModRefBehavior getModRefBehavior(const Function *F) override {
  return Result.getModRefBehavior(F);
}

ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
                         AAQueryInfo &AAQI) override {
  return Result.getModRefInfo(Call, Loc, AAQI);
}

ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
                         AAQueryInfo &AAQI) override {
  return Result.getModRefInfo(Call1, Call2, AAQI);
}
1049};

1051/// A CRTP-driven "mixin" base class to help implement the function alias
1052/// analysis results concept.
1053///
1054/// Because of the nature of many alias analysis implementations, they often
1055/// only implement a subset of the interface. This base class will attempt to
1056/// implement the remaining portions of the interface in terms of simpler forms
1057/// of the interface where possible, and otherwise provide conservatively
1058/// correct fallback implementations.
1059///
1060/// Implementors of an alias analysis should derive from this CRTP, and then
1061/// override specific methods that they wish to customize. There is no need to
1062/// use virtual anywhere, the CRTP base class does static dispatch to the
1063/// derived type passed into it.
1064template <typename DerivedT> class AAResultBase {
// Expose some parts of the interface only to the AAResults::Model
// for wrapping. Specifically, this allows the model to call our
// setAAResults method without exposing it as a fully public API.
friend class AAResults::Model<DerivedT>;

/// A pointer to the AAResults object that this AAResult is
/// aggregated within. May be null if not aggregated.
AAResults *AAR = nullptr;

/// Helper to dispatch calls back through the derived type.
DerivedT &derived() { return static_cast<DerivedT &>(*this); }

/// A setter for the AAResults pointer, which is used to satisfy the
/// AAResults::Model contract.
void setAAResults(AAResults *NewAAR) { AAR = NewAAR; }

1081protected:
/// This proxy class models a common pattern where we delegate to either the
/// top-level \c AAResults aggregation if one is registered, or to the
/// current result if none are registered.
class AAResultsProxy {
  AAResults *AAR;
  DerivedT &CurrentResult;

public:
  AAResultsProxy(AAResults *AAR, DerivedT &CurrentResult)
      : AAR(AAR), CurrentResult(CurrentResult) {}

  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
                    AAQueryInfo &AAQI) {
    return AAR ? AAR->alias(LocA, LocB, AAQI)
               : CurrentResult.alias(LocA, LocB, AAQI);
  }

  bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
                              bool OrLocal) {
    return AAR ? AAR->pointsToConstantMemory(Loc, AAQI, OrLocal)
               : CurrentResult.pointsToConstantMemory(Loc, AAQI, OrLocal);
  }

  ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
    return AAR ? AAR->getArgModRefInfo(Call, ArgIdx)
               : CurrentResult.getArgModRefInfo(Call, ArgIdx);
  }

  FunctionModRefBehavior getModRefBehavior(const CallBase *Call) {
    return AAR ? AAR->getModRefBehavior(Call)
               : CurrentResult.getModRefBehavior(Call);
  }

  FunctionModRefBehavior getModRefBehavior(const Function *F) {
    return AAR ? AAR->getModRefBehavior(F) : CurrentResult.getModRefBehavior(F);
  }

  ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
                           AAQueryInfo &AAQI) {
    return AAR ? AAR->getModRefInfo(Call, Loc, AAQI)
               : CurrentResult.getModRefInfo(Call, Loc, AAQI);
  }

  ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
                           AAQueryInfo &AAQI) {
    return AAR ? AAR->getModRefInfo(Call1, Call2, AAQI)
               : CurrentResult.getModRefInfo(Call1, Call2, AAQI);
  }
};

explicit AAResultBase() = default;

// Provide all the copy and move constructors so that derived types aren't
// constrained.
AAResultBase(const AAResultBase &Arg) {}
AAResultBase(AAResultBase &&Arg) {}

/// Get a proxy for the best AA result set to query at this time.
///
/// When this result is part of a larger aggregation, this will proxy to that
/// aggregation. When this result is used in isolation, it will just delegate
/// back to the derived class's implementation.
///
/// Note that callers of this need to take considerable care to not cause
/// performance problems when they use this routine, in the case of a large
/// number of alias analyses being aggregated, it can be expensive to walk
/// back across the chain.
AAResultsProxy getBestAAResults() { return AAResultsProxy(AAR, derived()); }

1151public:
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
                  AAQueryInfo &AAQI) {
  return AliasResult::MayAlias;
}

bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
                            bool OrLocal) {
  return false;
}

ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
  return ModRefInfo::ModRef;
}

FunctionModRefBehavior getModRefBehavior(const CallBase *Call) {
  return FMRB_UnknownModRefBehavior;
}

FunctionModRefBehavior getModRefBehavior(const Function *F) {
  return FMRB_UnknownModRefBehavior;
}

ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
                         AAQueryInfo &AAQI) {
  return ModRefInfo::ModRef;
}

ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
                         AAQueryInfo &AAQI) {
  return ModRefInfo::ModRef;
}
1183};

1185/// Return true if this pointer is returned by a noalias function.
1186bool isNoAliasCall(const Value *V);

1188/// Return true if this pointer refers to a distinct and identifiable object.
1189/// This returns true for:
1190///    Global Variables and Functions (but not Global Aliases)
1191///    Allocas
1192///    ByVal and NoAlias Arguments
1193///    NoAlias returns (e.g. calls to malloc)
1194///
1195bool isIdentifiedObject(const Value *V);

1197/// Return true if V is umabigously identified at the function-level.
1198/// Different IdentifiedFunctionLocals can't alias.
1199/// Further, an IdentifiedFunctionLocal can not alias with any function
1200/// arguments other than itself, which is not necessarily true for
1201/// IdentifiedObjects.
1202bool isIdentifiedFunctionLocal(const Value *V);

1204/// A manager for alias analyses.
1205///
1206/// This class can have analyses registered with it and when run, it will run
1207/// all of them and aggregate their results into single AA results interface
1208/// that dispatches across all of the alias analysis results available.
1209///
1210/// Note that the order in which analyses are registered is very significant.
1211/// That is the order in which the results will be aggregated and queried.
1212///
1213/// This manager effectively wraps the AnalysisManager for registering alias
1214/// analyses. When you register your alias analysis with this manager, it will
1215/// ensure the analysis itself is registered with its AnalysisManager.
1216///
1217/// The result of this analysis is only invalidated if one of the particular
1218/// aggregated AA results end up being invalidated. This removes the need to
1219/// explicitly preserve the results of `AAManager`. Note that analyses should no
1220/// longer be registered once the `AAManager` is run.
1221class AAManager : public AnalysisInfoMixin<AAManager> {
1222public:
using Result = AAResults;

/// Register a specific AA result.
template <typename AnalysisT> void registerFunctionAnalysis() {
  ResultGetters.push_back(&getFunctionAAResultImpl<AnalysisT>);
}

/// Register a specific AA result.
template <typename AnalysisT> void registerModuleAnalysis() {
  ResultGetters.push_back(&getModuleAAResultImpl<AnalysisT>);
}

Result run(Function &F, FunctionAnalysisManager &AM);

1237private:
friend AnalysisInfoMixin<AAManager>;

static AnalysisKey Key;

SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM,
                     AAResults &AAResults),
            4> ResultGetters;

template <typename AnalysisT>
static void getFunctionAAResultImpl(Function &F,
                                    FunctionAnalysisManager &AM,
                                    AAResults &AAResults) {
  AAResults.addAAResult(AM.template getResult<AnalysisT>(F));
  AAResults.addAADependencyID(AnalysisT::ID());
}

template <typename AnalysisT>
static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM,
                                  AAResults &AAResults) {
  auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
  if (auto *R =
          MAMProxy.template getCachedResult<AnalysisT>(*F.getParent())) {
    AAResults.addAAResult(*R);
    MAMProxy
        .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>();
  }
}
1265};

1267/// A wrapper pass to provide the legacy pass manager access to a suitably
1268/// prepared AAResults object.
1269class AAResultsWrapperPass : public FunctionPass {
std::unique_ptr<AAResults> AAR;

1272public:
static char ID;

AAResultsWrapperPass();

AAResults &getAAResults() { return *AAR; }
const AAResults &getAAResults() const { return *AAR; }

bool runOnFunction(Function &F) override;

void getAnalysisUsage(AnalysisUsage &AU) const override;
1283};

1285/// A wrapper pass for external alias analyses. This just squirrels away the
1286/// callback used to run any analyses and register their results.
1287struct ExternalAAWrapperPass : ImmutablePass {
using CallbackT = std::function<void(Pass &, Function &, AAResults &)>;

CallbackT CB;

static char ID;

ExternalAAWrapperPass();

explicit ExternalAAWrapperPass(CallbackT CB);

void getAnalysisUsage(AnalysisUsage &AU) const override {
  AU.setPreservesAll();
}
1301};

1303FunctionPass *createAAResultsWrapperPass();

1305/// A wrapper pass around a callback which can be used to populate the
1306/// AAResults in the AAResultsWrapperPass from an external AA.
1307///
1308/// The callback provided here will be used each time we prepare an AAResults
1309/// object, and will receive a reference to the function wrapper pass, the
1310/// function, and the AAResults object to populate. This should be used when
1311/// setting up a custom pass pipeline to inject a hook into the AA results.
1312ImmutablePass *createExternalAAWrapperPass(
  std::function<void(Pass &, Function &, AAResults &)> Callback);

1315/// A helper for the legacy pass manager to create a \c AAResults
1316/// object populated to the best of our ability for a particular function when
1317/// inside of a \c ModulePass or a \c CallGraphSCCPass.
1318///
1319/// If a \c ModulePass or a \c CallGraphSCCPass calls \p
1320/// createLegacyPMAAResults, it also needs to call \p addUsedAAAnalyses in \p
1321/// getAnalysisUsage.
1322AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR);

1324/// A helper for the legacy pass manager to populate \p AU to add uses to make
1325/// sure the analyses required by \p createLegacyPMAAResults are available.
1326void getAAResultsAnalysisUsage(AnalysisUsage &AU);

1328} // end namespace llvm

1330#endif // LLVM_ANALYSIS_ALIASANALYSIS_H