/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

Bug Summary

File:	llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp
Warning:	line 1288, column 32 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 -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~++20210726100616+dead50d4427c/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~++20210726100616+dead50d4427c/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/build-llvm/include -I /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-13/lib/clang/13.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c=. -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-07-26-235520-9401-1 -x c++ /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/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")(static_cast <bool> (Start->getParent() == End->getParent
() && "Must be in same block") ? void (0) : __assert_fail
 ("Start->getParent() == End->getParent() && \"Must be in same block\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 319, __extension__ __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")(static_cast <bool> (Start->getBlock() == End->getBlock
() && "Only local supported") ? void (0) : __assert_fail
 ("Start->getBlock() == End->getBlock() && \"Only local supported\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 344, __extension__ __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;
    }
  }

  // Calls that only access inaccessible memory do not block merging
  // accessible stores.
  if (auto *CB = dyn_cast<CallBase>(BI)) {
    if (CB->onlyAccessesInaccessibleMemory())
      continue;
  }

  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 &&(static_cast <bool> (LastMemDef && MemInsertPoint
 && "Both LastMemDef and MemInsertPoint need to be set"
) ? void (0) : __assert_fail ("LastMemDef && MemInsertPoint && \"Both LastMemDef and MemInsertPoint need to be set\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 499, __extension__ __PRETTY_FUNCTION__))
           "Both LastMemDef and MemInsertPoint need to be set")(static_cast <bool> (LastMemDef && MemInsertPoint
 && "Both LastMemDef and MemInsertPoint need to be set"
) ? void (0) : __assert_fail ("LastMemDef && MemInsertPoint && \"Both LastMemDef and MemInsertPoint need to be set\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 499, __extension__ __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;
519}

521// This method try to lift a store instruction before position P.
522// It will lift the store and its argument + that anything that
523// may alias with these.
524// The method returns true if it was successful.
525bool 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")(static_cast <bool> (MemInsertPoint && "Must have found insert point"
) ? void (0) : __assert_fail ("MemInsertPoint && \"Must have found insert point\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 638, __extension__ __PRETTY_FUNCTION__));
    if (MemoryUseOrDef *MA = MSSAU->getMemorySSA()->getMemoryAccess(I)) {
      MSSAU->moveAfter(MA, MemInsertPoint);
      MemInsertPoint = MA;
    }
  }
}

return true;
647}

649bool 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 aliases 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)))(static_cast <bool> (isa<MemoryDef>(MSSAU->getMemorySSA
()->getMemoryAccess(SI))) ? void (0) : __assert_fail ("isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(SI))"
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 826, __extension__ __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;
843}

845bool 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;
855}

857/// Takes a memcpy and a call that it depends on,
858/// and checks for the possibility of a call slot optimization by having
859/// the call write its result directly into the destination of the memcpy.
860bool 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!")(static_cast <bool> (isa<AllocaInst>(cpyDest) &&
 "Can only increase alloca alignment!") ? void (0) : __assert_fail
 ("isa<AllocaInst>(cpyDest) && \"Can only increase alloca alignment!\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 1019, __extension__ __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;
1039}

1041/// We've found that the (upward scanning) memory dependence of memcpy 'M' is
1042/// the memcpy 'MDep'. Try to simplify M to copy from MDep's input if we can.
1043bool 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.
if (MDep->getLength() != M->getLength()) {
  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 if (isa<MemCpyInlineInst>(M)) {
  // llvm.memcpy may be promoted to llvm.memcpy.inline, but the converse is
  // never allowed since that would allow the latter to be lowered as a call
  // to an external function.
  NewM = Builder.CreateMemCpyInline(
      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)))(static_cast <bool> (isa<MemoryDef>(MSSAU->getMemorySSA
()->getMemoryAccess(M))) ? void (0) : __assert_fail ("isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(M))"
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 1125, __extension__ __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;
1135}

1137/// We've found that the (upward scanning) memory dependence of \p MemCpy is
1138/// \p MemSet.  Try to simplify \p MemSet to only set the trailing bytes that
1139/// weren't copied over by \p MemCpy.
1140///
1141/// In other words, transform:
1142/// \code
1143///   memset(dst, c, dst_size);
1144///   memcpy(dst, src, src_size);
1145/// \endcode
1146/// into:
1147/// \code
1148///   memcpy(dst, src, src_size);
1149///   memset(dst + src_size, c, dst_size <= src_size ? 0 : dst_size - src_size);
1150/// \endcode
1151bool 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);
unsigned DestAS = Dest->getType()->getPointerAddressSpace();
Instruction *NewMemSet = Builder.CreateMemSet(
    Builder.CreateGEP(Builder.getInt8Ty(),
                      Builder.CreatePointerCast(Dest,
                                                Builder.getInt8PtrTy(DestAS)),
                      SrcSize),
    MemSet->getOperand(1), MemsetLen, MaybeAlign(Align));

if (MSSAU) {
  assert(isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy)) &&(static_cast <bool> (isa<MemoryDef>(MSSAU->getMemorySSA
()->getMemoryAccess(MemCpy)) && "MemCpy must be a MemoryDef"
) ? void (0) : __assert_fail ("isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy)) && \"MemCpy must be a MemoryDef\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 1234, __extension__ __PRETTY_FUNCTION__))
         "MemCpy must be a MemoryDef")(static_cast <bool> (isa<MemoryDef>(MSSAU->getMemorySSA
()->getMemoryAccess(MemCpy)) && "MemCpy must be a MemoryDef"
) ? void (0) : __assert_fail ("isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy)) && \"MemCpy must be a MemoryDef\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 1234, __extension__ __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;
1247}

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

if (ConstantInt *CSize = dyn_cast<ConstantInt>(Size)) {
  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() >= CSize->getZExtValue())
          return true;
}

return false;
1264}

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

if (IntrinsicInst *II19.1
'II' is non-null
1
'II' is non-null
1
'II' is non-null
 =
20
←
Taking true branch→
        dyn_cast_or_null<IntrinsicInst>(Def->getMemoryInst())) {
19
←
Assuming the object is a 'IntrinsicInst'→
  if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
21
←
Assuming the condition is true→
22
←
Taking true branch→
    ConstantInt *LTSize = cast<ConstantInt>(II->getArgOperand(0));

    if (ConstantInt *CSize23.1
'CSize' is non-null
1
'CSize' is non-null
1
'CSize' is non-null
 = dyn_cast<ConstantInt>(Size)) {
23
←
'Size' is a 'ConstantInt'→
24
←
Taking true branch→
      if (AA->isMustAlias(V, II->getArgOperand(1)) &&
25
←
Calling 'AAResults::isMustAlias'→
28
←
Returning from 'AAResults::isMustAlias'→
          LTSize->getZExtValue() >= CSize->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));
29
←
Assuming the object is not a 'AllocaInst'→
30
←
'Alloca' initialized to a null pointer value→
    if (getUnderlyingObject(II->getArgOperand(1)) == Alloca) {
31
←
Assuming the condition is true→
32
←
Taking true branch→
      const DataLayout &DL = Alloca->getModule()->getDataLayout();
33
←
Called C++ object pointer is null
      if (Optional<TypeSize> AllocaSize = Alloca->getAllocationSizeInBits(DL))
        if (*AllocaSize == LTSize->getValue() * 8)
          return true;
    }
  }
}

return false;
1297}

1299/// Transform memcpy to memset when its source was just memset.
1300/// In other words, turn:
1301/// \code
1302///   memset(dst1, c, dst1_size);
1303///   memcpy(dst2, dst1, dst2_size);
1304/// \endcode
1305/// into:
1306/// \code
1307///   memset(dst1, c, dst1_size);
1308///   memset(dst2, c, dst2_size);
1309/// \endcode
1310/// When dst2_size <= dst1_size.
1311bool 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;

Value *MemSetSize = MemSet->getLength();
Value *CopySize = MemCpy->getLength();

if (MemSetSize1.1
'MemSetSize' is not equal to 'CopySize'
1
'MemSetSize' is not equal to 'CopySize'
1
'MemSetSize' is not equal to 'CopySize'
 != CopySize) {
2
←
Taking true branch→
  // Make sure the memcpy doesn't read any more than what the memset wrote.
  // Don't worry about sizes larger than i64.

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

  // A known memcpy size is also required.
  ConstantInt *CCopySize = dyn_cast<ConstantInt>(CopySize);
5
←
Assuming 'CopySize' is a 'ConstantInt'→
  if (!CCopySize5.1
'CCopySize' is non-null
1
'CCopySize' is non-null
1
'CCopySize' is non-null
)
6
←
Taking false branch→
    return false;
  if (CCopySize->getZExtValue() > CMemSetSize->getZExtValue()) {
7
←
Assuming the condition is true→
8
←
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) {
9
←
Assuming the condition is true→
10
←
Taking true branch→
      MemoryUseOrDef *MemSetAccess = MSSA->getMemoryAccess(MemSet);
      MemoryAccess *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(
          MemSetAccess->getDefiningAccess(), MemCpyLoc);
      if (auto *MD11.1
'MD' is non-null
1
'MD' is non-null
1
'MD' is non-null
 = dyn_cast<MemoryDef>(Clobber))
11
←
Assuming 'Clobber' is a 'MemoryDef'→
12
←
Taking true branch→
        if (hasUndefContentsMSSA(MSSA, AA, MemCpy->getSource(), MD, CopySize))
13
←
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;
1373}

1375/// Perform simplification of memcpy's.  If we have memcpy A
1376/// which copies X to Y, and memcpy B which copies Y to Z, then we can rewrite
1377/// B to be a memcpy from X to Z (or potentially a memmove, depending on
1378/// circumstances). This allows later passes to remove the first memcpy
1379/// altogether.
1380bool 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;

  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 (ConstantInt *CopySize = dyn_cast<ConstantInt>(M->getLength())) {
        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, M->getLength())) {
      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;

  // 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 (ConstantInt *CopySize = dyn_cast<ConstantInt>(M->getLength())) {
    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(), M->getLength())) {
      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;
1546}

1548/// Transforms memmove calls to memcpy calls when the src/dst are guaranteed
1549/// not to alias.
1550bool 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;
1579}

1581/// This is called on every byval argument in call sites.
1582bool 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 = CB.getParamByValType(ArgNo);
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;
1673}

1675/// Executes one iteration of MemCpyOptPass.
1676bool 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;
1718}

1720PreservedAnalyses 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>();
if (MD)
  PA.preserve<MemoryDependenceAnalysis>();
if (MSSA)
  PA.preserve<MemorySSAAnalysis>();
return PA;
1742}

1744bool 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;
1774}

1776/// This is the main transformation entry point for a function.
1777bool 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);
1794}

←

/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/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  void operator delete(void *Ptr) { User::operator delete(Ptr); }
334 
335  static bool classof(const Value *MA) {
336    return MA->getValueID() == MemoryUseVal;
337  }
338 
339  void print(raw_ostream &OS) const;
340 
341  void setOptimized(MemoryAccess *DMA) {
342    OptimizedID = DMA->getID();
343    setOperand(0, DMA);
344  }
345 
346  bool isOptimized() const {
347    return getDefiningAccess() && OptimizedID == getDefiningAccess()->getID();
348  }
349 
350  MemoryAccess *getOptimized() const {
351    return getDefiningAccess();
352  }
353 
354  void resetOptimized() {
355    OptimizedID = INVALID_MEMORYACCESS_ID;
356  }
357 
358protected:
359  friend class MemorySSA;
360 
361private:
362  static void deleteMe(DerivedUser *Self);
363 
364  unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
365};
366 
367template <>
368struct OperandTraits<MemoryUse> : public FixedNumOperandTraits<MemoryUse, 1> {};
369DEFINE_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 { (static_cast <bool
> (i_nocapture < OperandTraits<MemoryUse>::operands
(this) && "getOperand() out of range!") ? void (0) : __assert_fail
 ("i_nocapture < OperandTraits<MemoryUse>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 369, __extension__ __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
) { (static_cast <bool> (i_nocapture < OperandTraits
<MemoryUse>::operands(this) && "setOperand() out of range!"
) ? void (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryUse>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 369, __extension__ __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); }
370 
371/// Represents a read-write access to memory, whether it is a must-alias,
372/// or a may-alias.
373///
374/// In particular, the set of Instructions that will be represented by
375/// MemoryDef's is exactly the set of Instructions for which
376/// AliasAnalysis::getModRefInfo returns "Mod" or "ModRef".
377/// Note that, in order to provide def-def chains, all defs also have a use
378/// associated with them. This use points to the nearest reaching
379/// MemoryDef/MemoryPhi.
380class MemoryDef final : public MemoryUseOrDef {
381public:
382  friend class MemorySSA;
383 
384  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;
385 
386  MemoryDef(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB,
387            unsigned Ver)
388      : MemoryUseOrDef(C, DMA, MemoryDefVal, deleteMe, MI, BB,
389                       /*NumOperands=*/2),
390        ID(Ver) {}
391 
392  // allocate space for exactly two operands
393  void *operator new(size_t S) { return User::operator new(S, 2); }
394  void operator delete(void *Ptr) { User::operator delete(Ptr); }
395 
396  static bool classof(const Value *MA) {
397    return MA->getValueID() == MemoryDefVal;
398  }
399 
400  void setOptimized(MemoryAccess *MA) {
401    setOperand(1, MA);
402    OptimizedID = MA->getID();
403  }
404 
405  MemoryAccess *getOptimized() const {
406    return cast_or_null<MemoryAccess>(getOperand(1));
407  }
408 
409  bool isOptimized() const {
410    return getOptimized() && OptimizedID == getOptimized()->getID();
411  }
412 
413  void resetOptimized() {
414    OptimizedID = INVALID_MEMORYACCESS_ID;
415    setOperand(1, nullptr);
416  }
417 
418  void print(raw_ostream &OS) const;
419 
420  unsigned getID() const { return ID; }
421 
422private:
423  static void deleteMe(DerivedUser *Self);
424 
425  const unsigned ID;
426  unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
427};
428 
429template <>
430struct OperandTraits<MemoryDef> : public FixedNumOperandTraits<MemoryDef, 2> {};
431DEFINE_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 { (static_cast <bool
> (i_nocapture < OperandTraits<MemoryDef>::operands
(this) && "getOperand() out of range!") ? void (0) : __assert_fail
 ("i_nocapture < OperandTraits<MemoryDef>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 431, __extension__ __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
) { (static_cast <bool> (i_nocapture < OperandTraits
<MemoryDef>::operands(this) && "setOperand() out of range!"
) ? void (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryDef>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 431, __extension__ __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); }
432 
433template <>
434struct OperandTraits<MemoryUseOrDef> {
435  static Use *op_begin(MemoryUseOrDef *MUD) {
436    if (auto *MU = dyn_cast<MemoryUse>(MUD))
437      return OperandTraits<MemoryUse>::op_begin(MU);
438    return OperandTraits<MemoryDef>::op_begin(cast<MemoryDef>(MUD));
439  }
440 
441  static Use *op_end(MemoryUseOrDef *MUD) {
442    if (auto *MU = dyn_cast<MemoryUse>(MUD))
443      return OperandTraits<MemoryUse>::op_end(MU);
444    return OperandTraits<MemoryDef>::op_end(cast<MemoryDef>(MUD));
445  }
446 
447  static unsigned operands(const MemoryUseOrDef *MUD) {
448    if (const auto *MU = dyn_cast<MemoryUse>(MUD))
449      return OperandTraits<MemoryUse>::operands(MU);
450    return OperandTraits<MemoryDef>::operands(cast<MemoryDef>(MUD));
451  }
452};
453DEFINE_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 { (static_cast <bool
> (i_nocapture < OperandTraits<MemoryUseOrDef>::operands
(this) && "getOperand() out of range!") ? void (0) : __assert_fail
 ("i_nocapture < OperandTraits<MemoryUseOrDef>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 453, __extension__ __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) { (static_cast <bool> (i_nocapture <
 OperandTraits<MemoryUseOrDef>::operands(this) &&
 "setOperand() out of range!") ? void (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryUseOrDef>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 453, __extension__ __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); }
454 
455/// Represents phi nodes for memory accesses.
456///
457/// These have the same semantic as regular phi nodes, with the exception that
458/// only one phi will ever exist in a given basic block.
459/// Guaranteeing one phi per block means guaranteeing there is only ever one
460/// valid reaching MemoryDef/MemoryPHI along each path to the phi node.
461/// This is ensured by not allowing disambiguation of the RHS of a MemoryDef or
462/// a MemoryPhi's operands.
463/// That is, given
464/// if (a) {
465///   store %a
466///   store %b
467/// }
468/// it *must* be transformed into
469/// if (a) {
470///    1 = MemoryDef(liveOnEntry)
471///    store %a
472///    2 = MemoryDef(1)
473///    store %b
474/// }
475/// and *not*
476/// if (a) {
477///    1 = MemoryDef(liveOnEntry)
478///    store %a
479///    2 = MemoryDef(liveOnEntry)
480///    store %b
481/// }
482/// even if the two stores do not conflict. Otherwise, both 1 and 2 reach the
483/// end of the branch, and if there are not two phi nodes, one will be
484/// disconnected completely from the SSA graph below that point.
485/// Because MemoryUse's do not generate new definitions, they do not have this
486/// issue.
487class MemoryPhi final : public MemoryAccess {
488  // allocate space for exactly zero operands
489  void *operator new(size_t S) { return User::operator new(S); }
490 
491public:
492  void operator delete(void *Ptr) { User::operator delete(Ptr); }
493 
494  /// Provide fast operand accessors
495  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;
496 
497  MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds = 0)
498      : MemoryAccess(C, MemoryPhiVal, deleteMe, BB, 0), ID(Ver),
499        ReservedSpace(NumPreds) {
500    allocHungoffUses(ReservedSpace);
501  }
502 
503  // Block iterator interface. This provides access to the list of incoming
504  // basic blocks, which parallels the list of incoming values.
505  using block_iterator = BasicBlock **;
506  using const_block_iterator = BasicBlock *const *;
507 
508  block_iterator block_begin() {
509    return reinterpret_cast<block_iterator>(op_begin() + ReservedSpace);
510  }
511 
512  const_block_iterator block_begin() const {
513    return reinterpret_cast<const_block_iterator>(op_begin() + ReservedSpace);
514  }
515 
516  block_iterator block_end() { return block_begin() + getNumOperands(); }
517 
518  const_block_iterator block_end() const {
519    return block_begin() + getNumOperands();
520  }
521 
522  iterator_range<block_iterator> blocks() {
523    return make_range(block_begin(), block_end());
524  }
525 
526  iterator_range<const_block_iterator> blocks() const {
527    return make_range(block_begin(), block_end());
528  }
529 
530  op_range incoming_values() { return operands(); }
531 
532  const_op_range incoming_values() const { return operands(); }
533 
534  /// Return the number of incoming edges
535  unsigned getNumIncomingValues() const { return getNumOperands(); }
536 
537  /// Return incoming value number x
538  MemoryAccess *getIncomingValue(unsigned I) const { return getOperand(I); }
539  void setIncomingValue(unsigned I, MemoryAccess *V) {
540    assert(V && "PHI node got a null value!")(static_cast <bool> (V && "PHI node got a null value!"
) ? void (0) : __assert_fail ("V && \"PHI node got a null value!\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 540, __extension__ __PRETTY_FUNCTION__));
541    setOperand(I, V);
542  }
543 
544  static unsigned getOperandNumForIncomingValue(unsigned I) { return I; }
545  static unsigned getIncomingValueNumForOperand(unsigned I) { return I; }
546 
547  /// Return incoming basic block number @p i.
548  BasicBlock *getIncomingBlock(unsigned I) const { return block_begin()[I]; }
549 
550  /// Return incoming basic block corresponding
551  /// to an operand of the PHI.
552  BasicBlock *getIncomingBlock(const Use &U) const {
553    assert(this == U.getUser() && "Iterator doesn't point to PHI's Uses?")(static_cast <bool> (this == U.getUser() && "Iterator doesn't point to PHI's Uses?"
) ? void (0) : __assert_fail ("this == U.getUser() && \"Iterator doesn't point to PHI's Uses?\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 553, __extension__ __PRETTY_FUNCTION__));
554    return getIncomingBlock(unsigned(&U - op_begin()));
555  }
556 
557  /// Return incoming basic block corresponding
558  /// to value use iterator.
559  BasicBlock *getIncomingBlock(MemoryAccess::const_user_iterator I) const {
560    return getIncomingBlock(I.getUse());
561  }
562 
563  void setIncomingBlock(unsigned I, BasicBlock *BB) {
564    assert(BB && "PHI node got a null basic block!")(static_cast <bool> (BB && "PHI node got a null basic block!"
) ? void (0) : __assert_fail ("BB && \"PHI node got a null basic block!\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 564, __extension__ __PRETTY_FUNCTION__));
565    block_begin()[I] = BB;
566  }
567 
568  /// Add an incoming value to the end of the PHI list
569  void addIncoming(MemoryAccess *V, BasicBlock *BB) {
570    if (getNumOperands() == ReservedSpace)
571      growOperands(); // Get more space!
572    // Initialize some new operands.
573    setNumHungOffUseOperands(getNumOperands() + 1);
574    setIncomingValue(getNumOperands() - 1, V);
575    setIncomingBlock(getNumOperands() - 1, BB);
576  }
577 
578  /// Return the first index of the specified basic
579  /// block in the value list for this PHI.  Returns -1 if no instance.
580  int getBasicBlockIndex(const BasicBlock *BB) const {
581    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
582      if (block_begin()[I] == BB)
583        return I;
584    return -1;
585  }
586 
587  MemoryAccess *getIncomingValueForBlock(const BasicBlock *BB) const {
588    int Idx = getBasicBlockIndex(BB);
589    assert(Idx >= 0 && "Invalid basic block argument!")(static_cast <bool> (Idx >= 0 && "Invalid basic block argument!"
) ? void (0) : __assert_fail ("Idx >= 0 && \"Invalid basic block argument!\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 589, __extension__ __PRETTY_FUNCTION__));
590    return getIncomingValue(Idx);
591  }
592 
593  // After deleting incoming position I, the order of incoming may be changed.
594  void unorderedDeleteIncoming(unsigned I) {
595    unsigned E = getNumOperands();
596    assert(I < E && "Cannot remove out of bounds Phi entry.")(static_cast <bool> (I < E && "Cannot remove out of bounds Phi entry."
) ? void (0) : __assert_fail ("I < E && \"Cannot remove out of bounds Phi entry.\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 596, __extension__ __PRETTY_FUNCTION__));
597    // MemoryPhi must have at least two incoming values, otherwise the MemoryPhi
598    // itself should be deleted.
599    assert(E >= 2 && "Cannot only remove incoming values in MemoryPhis with "(static_cast <bool> (E >= 2 && "Cannot only remove incoming values in MemoryPhis with "
 "at least 2 values.") ? void (0) : __assert_fail ("E >= 2 && \"Cannot only remove incoming values in MemoryPhis with \" \"at least 2 values.\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 600, __extension__ __PRETTY_FUNCTION__))
600                     "at least 2 values.")(static_cast <bool> (E >= 2 && "Cannot only remove incoming values in MemoryPhis with "
 "at least 2 values.") ? void (0) : __assert_fail ("E >= 2 && \"Cannot only remove incoming values in MemoryPhis with \" \"at least 2 values.\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 600, __extension__ __PRETTY_FUNCTION__));
601    setIncomingValue(I, getIncomingValue(E - 1));
602    setIncomingBlock(I, block_begin()[E - 1]);
603    setOperand(E - 1, nullptr);
604    block_begin()[E - 1] = nullptr;
605    setNumHungOffUseOperands(getNumOperands() - 1);
606  }
607 
608  // After deleting entries that satisfy Pred, remaining entries may have
609  // changed order.
610  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
611    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
612      if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
613        unorderedDeleteIncoming(I);
614        E = getNumOperands();
615        --I;
616      }
617    assert(getNumOperands() >= 1 &&(static_cast <bool> (getNumOperands() >= 1 &&
 "Cannot remove all incoming blocks in a MemoryPhi.") ? void (
0) : __assert_fail ("getNumOperands() >= 1 && \"Cannot remove all incoming blocks in a MemoryPhi.\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 618, __extension__ __PRETTY_FUNCTION__))
618           "Cannot remove all incoming blocks in a MemoryPhi.")(static_cast <bool> (getNumOperands() >= 1 &&
 "Cannot remove all incoming blocks in a MemoryPhi.") ? void (
0) : __assert_fail ("getNumOperands() >= 1 && \"Cannot remove all incoming blocks in a MemoryPhi.\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 618, __extension__ __PRETTY_FUNCTION__));
619  }
620 
621  // After deleting incoming block BB, the incoming blocks order may be changed.
622  void unorderedDeleteIncomingBlock(const BasicBlock *BB) {
623    unorderedDeleteIncomingIf(
624        [&](const MemoryAccess *, const BasicBlock *B) { return BB == B; });
625  }
626 
627  // After deleting incoming memory access MA, the incoming accesses order may
628  // be changed.
629  void unorderedDeleteIncomingValue(const MemoryAccess *MA) {
630    unorderedDeleteIncomingIf(
631        [&](const MemoryAccess *M, const BasicBlock *) { return MA == M; });
632  }
633 
634  static bool classof(const Value *V) {
635    return V->getValueID() == MemoryPhiVal;
636  }
637 
638  void print(raw_ostream &OS) const;
639 
640  unsigned getID() const { return ID; }
641 
642protected:
643  friend class MemorySSA;
644 
645  /// this is more complicated than the generic
646  /// User::allocHungoffUses, because we have to allocate Uses for the incoming
647  /// values and pointers to the incoming blocks, all in one allocation.
648  void allocHungoffUses(unsigned N) {
649    User::allocHungoffUses(N, /* IsPhi */ true);
650  }
651 
652private:
653  // For debugging only
654  const unsigned ID;
655  unsigned ReservedSpace;
656 
657  /// This grows the operand list in response to a push_back style of
658  /// operation.  This grows the number of ops by 1.5 times.
659  void growOperands() {
660    unsigned E = getNumOperands();
661    // 2 op PHI nodes are VERY common, so reserve at least enough for that.
662    ReservedSpace = std::max(E + E / 2, 2u);
663    growHungoffUses(ReservedSpace, /* IsPhi */ true);
664  }
665 
666  static void deleteMe(DerivedUser *Self);
667};
668 
669inline unsigned MemoryAccess::getID() const {
670  assert((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&(static_cast <bool> ((isa<MemoryDef>(this) || isa
<MemoryPhi>(this)) && "only memory defs and phis have ids"
) ? void (0) : __assert_fail ("(isa<MemoryDef>(this) || isa<MemoryPhi>(this)) && \"only memory defs and phis have ids\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 671, __extension__ __PRETTY_FUNCTION__))
671         "only memory defs and phis have ids")(static_cast <bool> ((isa<MemoryDef>(this) || isa
<MemoryPhi>(this)) && "only memory defs and phis have ids"
) ? void (0) : __assert_fail ("(isa<MemoryDef>(this) || isa<MemoryPhi>(this)) && \"only memory defs and phis have ids\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 671, __extension__ __PRETTY_FUNCTION__));
672  if (const auto *MD = dyn_cast<MemoryDef>(this))
673    return MD->getID();
674  return cast<MemoryPhi>(this)->getID();
675}
676 
677inline bool MemoryUseOrDef::isOptimized() const {
678  if (const auto *MD = dyn_cast<MemoryDef>(this))
679    return MD->isOptimized();
680  return cast<MemoryUse>(this)->isOptimized();
681}
682 
683inline MemoryAccess *MemoryUseOrDef::getOptimized() const {
684  if (const auto *MD = dyn_cast<MemoryDef>(this))
685    return MD->getOptimized();
686  return cast<MemoryUse>(this)->getOptimized();
687}
688 
689inline void MemoryUseOrDef::setOptimized(MemoryAccess *MA) {
690  if (auto *MD = dyn_cast<MemoryDef>(this))
691    MD->setOptimized(MA);
692  else
693    cast<MemoryUse>(this)->setOptimized(MA);
694}
695 
696inline void MemoryUseOrDef::resetOptimized() {
697  if (auto *MD = dyn_cast<MemoryDef>(this))
698    MD->resetOptimized();
699  else
700    cast<MemoryUse>(this)->resetOptimized();
701}
702 
703template <> struct OperandTraits<MemoryPhi> : public HungoffOperandTraits<2> {};
704DEFINE_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 { (static_cast <bool
> (i_nocapture < OperandTraits<MemoryPhi>::operands
(this) && "getOperand() out of range!") ? void (0) : __assert_fail
 ("i_nocapture < OperandTraits<MemoryPhi>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 704, __extension__ __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
) { (static_cast <bool> (i_nocapture < OperandTraits
<MemoryPhi>::operands(this) && "setOperand() out of range!"
) ? void (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryPhi>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 704, __extension__ __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); }
705 
706/// Encapsulates MemorySSA, including all data associated with memory
707/// accesses.
708class MemorySSA {
709public:
710  MemorySSA(Function &, AliasAnalysis *, DominatorTree *);
711 
712  // MemorySSA must remain where it's constructed; Walkers it creates store
713  // pointers to it.
714  MemorySSA(MemorySSA &&) = delete;
715 
716  ~MemorySSA();
717 
718  MemorySSAWalker *getWalker();
719  MemorySSAWalker *getSkipSelfWalker();
720 
721  /// Given a memory Mod/Ref'ing instruction, get the MemorySSA
722  /// access associated with it. If passed a basic block gets the memory phi
723  /// node that exists for that block, if there is one. Otherwise, this will get
724  /// a MemoryUseOrDef.
725  MemoryUseOrDef *getMemoryAccess(const Instruction *I) const {
726    return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I));
727  }
728 
729  MemoryPhi *getMemoryAccess(const BasicBlock *BB) const {
730    return cast_or_null<MemoryPhi>(ValueToMemoryAccess.lookup(cast<Value>(BB)));
731  }
732 
733  DominatorTree &getDomTree() const { return *DT; }
734 
735  void dump() const;
736  void print(raw_ostream &) const;
737 
738  /// Return true if \p MA represents the live on entry value
739  ///
740  /// Loads and stores from pointer arguments and other global values may be
741  /// defined by memory operations that do not occur in the current function, so
742  /// they may be live on entry to the function. MemorySSA represents such
743  /// memory state by the live on entry definition, which is guaranteed to occur
744  /// before any other memory access in the function.
745  inline bool isLiveOnEntryDef(const MemoryAccess *MA) const {
746    return MA == LiveOnEntryDef.get();
15
←
Assuming the condition is false→
16
←
Returning zero, which participates in a condition later→
747  }
748 
749  inline MemoryAccess *getLiveOnEntryDef() const {
750    return LiveOnEntryDef.get();
751  }
752 
753  // Sadly, iplists, by default, owns and deletes pointers added to the
754  // list. It's not currently possible to have two iplists for the same type,
755  // where one owns the pointers, and one does not. This is because the traits
756  // are per-type, not per-tag.  If this ever changes, we should make the
757  // DefList an iplist.
758  using AccessList = iplist<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>;
759  using DefsList =
760      simple_ilist<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>;
761 
762  /// Return the list of MemoryAccess's for a given basic block.
763  ///
764  /// This list is not modifiable by the user.
765  const AccessList *getBlockAccesses(const BasicBlock *BB) const {
766    return getWritableBlockAccesses(BB);
767  }
768 
769  /// Return the list of MemoryDef's and MemoryPhi's for a given basic
770  /// block.
771  ///
772  /// This list is not modifiable by the user.
773  const DefsList *getBlockDefs(const BasicBlock *BB) const {
774    return getWritableBlockDefs(BB);
775  }
776 
777  /// Given two memory accesses in the same basic block, determine
778  /// whether MemoryAccess \p A dominates MemoryAccess \p B.
779  bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const;
780 
781  /// Given two memory accesses in potentially different blocks,
782  /// determine whether MemoryAccess \p A dominates MemoryAccess \p B.
783  bool dominates(const MemoryAccess *A, const MemoryAccess *B) const;
784 
785  /// Given a MemoryAccess and a Use, determine whether MemoryAccess \p A
786  /// dominates Use \p B.
787  bool dominates(const MemoryAccess *A, const Use &B) const;
788 
789  /// Verify that MemorySSA is self consistent (IE definitions dominate
790  /// all uses, uses appear in the right places).  This is used by unit tests.
791  void verifyMemorySSA() const;
792 
793  /// Used in various insertion functions to specify whether we are talking
794  /// about the beginning or end of a block.
795  enum InsertionPlace { Beginning, End, BeforeTerminator };
796 
797protected:
798  // Used by Memory SSA annotater, dumpers, and wrapper pass
799  friend class MemorySSAAnnotatedWriter;
800  friend class MemorySSAPrinterLegacyPass;
801  friend class MemorySSAUpdater;
802 
803  void verifyOrderingDominationAndDefUses(Function &F) const;
804  void verifyDominationNumbers(const Function &F) const;
805  void verifyPrevDefInPhis(Function &F) const;
806 
807  // This is used by the use optimizer and updater.
808  AccessList *getWritableBlockAccesses(const BasicBlock *BB) const {
809    auto It = PerBlockAccesses.find(BB);
810    return It == PerBlockAccesses.end() ? nullptr : It->second.get();
811  }
812 
813  // This is used by the use optimizer and updater.
814  DefsList *getWritableBlockDefs(const BasicBlock *BB) const {
815    auto It = PerBlockDefs.find(BB);
816    return It == PerBlockDefs.end() ? nullptr : It->second.get();
817  }
818 
819  // These is used by the updater to perform various internal MemorySSA
820  // machinsations.  They do not always leave the IR in a correct state, and
821  // relies on the updater to fixup what it breaks, so it is not public.
822 
823  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where);
824  void moveTo(MemoryAccess *What, BasicBlock *BB, InsertionPlace Point);
825 
826  // Rename the dominator tree branch rooted at BB.
827  void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal,
828                  SmallPtrSetImpl<BasicBlock *> &Visited) {
829    renamePass(DT->getNode(BB), IncomingVal, Visited, true, true);
830  }
831 
832  void removeFromLookups(MemoryAccess *);
833  void removeFromLists(MemoryAccess *, bool ShouldDelete = true);
834  void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *,
835                               InsertionPlace);
836  void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
837                             AccessList::iterator);
838  MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *,
839                                      const MemoryUseOrDef *Template = nullptr,
840                                      bool CreationMustSucceed = true);
841 
842private:
843  template <class AliasAnalysisType> class ClobberWalkerBase;
844  template <class AliasAnalysisType> class CachingWalker;
845  template <class AliasAnalysisType> class SkipSelfWalker;
846  class OptimizeUses;
847 
848  CachingWalker<AliasAnalysis> *getWalkerImpl();
849  void buildMemorySSA(BatchAAResults &BAA);
850 
851  void prepareForMoveTo(MemoryAccess *, BasicBlock *);
852  void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
853 
854  using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;
855  using DefsMap = DenseMap<const BasicBlock *, std::unique_ptr<DefsList>>;
856 
857  void markUnreachableAsLiveOnEntry(BasicBlock *BB);
858  MemoryPhi *createMemoryPhi(BasicBlock *BB);
859  template <typename AliasAnalysisType>
860  MemoryUseOrDef *createNewAccess(Instruction *, AliasAnalysisType *,
861                                  const MemoryUseOrDef *Template = nullptr);
862  void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &);
863  MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool);
864  void renameSuccessorPhis(BasicBlock *, MemoryAccess *, bool);
865  void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
866                  SmallPtrSetImpl<BasicBlock *> &Visited,
867                  bool SkipVisited = false, bool RenameAllUses = false);
868  AccessList *getOrCreateAccessList(const BasicBlock *);
869  DefsList *getOrCreateDefsList(const BasicBlock *);
870  void renumberBlock(const BasicBlock *) const;
871  AliasAnalysis *AA;
872  DominatorTree *DT;
873  Function &F;
874 
875  // Memory SSA mappings
876  DenseMap<const Value *, MemoryAccess *> ValueToMemoryAccess;
877 
878  // These two mappings contain the main block to access/def mappings for
879  // MemorySSA. The list contained in PerBlockAccesses really owns all the
880  // MemoryAccesses.
881  // Both maps maintain the invariant that if a block is found in them, the
882  // corresponding list is not empty, and if a block is not found in them, the
883  // corresponding list is empty.
884  AccessMap PerBlockAccesses;
885  DefsMap PerBlockDefs;
886  std::unique_ptr<MemoryAccess, ValueDeleter> LiveOnEntryDef;
887 
888  // Domination mappings
889  // Note that the numbering is local to a block, even though the map is
890  // global.
891  mutable SmallPtrSet<const BasicBlock *, 16> BlockNumberingValid;
892  mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering;
893 
894  // Memory SSA building info
895  std::unique_ptr<ClobberWalkerBase<AliasAnalysis>> WalkerBase;
896  std::unique_ptr<CachingWalker<AliasAnalysis>> Walker;
897  std::unique_ptr<SkipSelfWalker<AliasAnalysis>> SkipWalker;
898  unsigned NextID;
899};
900 
901// Internal MemorySSA utils, for use by MemorySSA classes and walkers
902class MemorySSAUtil {
903protected:
904  friend class GVNHoist;
905  friend class MemorySSAWalker;
906 
907  // This function should not be used by new passes.
908  static bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
909                                  AliasAnalysis &AA);
910};
911 
912// This pass does eager building and then printing of MemorySSA. It is used by
913// the tests to be able to build, dump, and verify Memory SSA.
914class MemorySSAPrinterLegacyPass : public FunctionPass {
915public:
916  MemorySSAPrinterLegacyPass();
917 
918  bool runOnFunction(Function &) override;
919  void getAnalysisUsage(AnalysisUsage &AU) const override;
920 
921  static char ID;
922};
923 
924/// An analysis that produces \c MemorySSA for a function.
925///
926class MemorySSAAnalysis : public AnalysisInfoMixin<MemorySSAAnalysis> {
927  friend AnalysisInfoMixin<MemorySSAAnalysis>;
928 
929  static AnalysisKey Key;
930 
931public:
932  // Wrap MemorySSA result to ensure address stability of internal MemorySSA
933  // pointers after construction.  Use a wrapper class instead of plain
934  // unique_ptr<MemorySSA> to avoid build breakage on MSVC.
935  struct Result {
936    Result(std::unique_ptr<MemorySSA> &&MSSA) : MSSA(std::move(MSSA)) {}
937 
938    MemorySSA &getMSSA() { return *MSSA.get(); }
939 
940    std::unique_ptr<MemorySSA> MSSA;
941 
942    bool invalidate(Function &F, const PreservedAnalyses &PA,
943                    FunctionAnalysisManager::Invalidator &Inv);
944  };
945 
946  Result run(Function &F, FunctionAnalysisManager &AM);
947};
948 
949/// Printer pass for \c MemorySSA.
950class MemorySSAPrinterPass : public PassInfoMixin<MemorySSAPrinterPass> {
951  raw_ostream &OS;
952 
953public:
954  explicit MemorySSAPrinterPass(raw_ostream &OS) : OS(OS) {}
955 
956  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
957};
958 
959/// Verifier pass for \c MemorySSA.
960struct MemorySSAVerifierPass : PassInfoMixin<MemorySSAVerifierPass> {
961  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
962};
963 
964/// Legacy analysis pass which computes \c MemorySSA.
965class MemorySSAWrapperPass : public FunctionPass {
966public:
967  MemorySSAWrapperPass();
968 
969  static char ID;
970 
971  bool runOnFunction(Function &) override;
972  void releaseMemory() override;
973  MemorySSA &getMSSA() { return *MSSA; }
974  const MemorySSA &getMSSA() const { return *MSSA; }
975 
976  void getAnalysisUsage(AnalysisUsage &AU) const override;
977 
978  void verifyAnalysis() const override;
979  void print(raw_ostream &OS, const Module *M = nullptr) const override;
980 
981private:
982  std::unique_ptr<MemorySSA> MSSA;
983};
984 
985/// This is the generic walker interface for walkers of MemorySSA.
986/// Walkers are used to be able to further disambiguate the def-use chains
987/// MemorySSA gives you, or otherwise produce better info than MemorySSA gives
988/// you.
989/// In particular, while the def-use chains provide basic information, and are
990/// guaranteed to give, for example, the nearest may-aliasing MemoryDef for a
991/// MemoryUse as AliasAnalysis considers it, a user mant want better or other
992/// information. In particular, they may want to use SCEV info to further
993/// disambiguate memory accesses, or they may want the nearest dominating
994/// may-aliasing MemoryDef for a call or a store. This API enables a
995/// standardized interface to getting and using that info.
996class MemorySSAWalker {
997public:
998  MemorySSAWalker(MemorySSA *);
999  virtual ~MemorySSAWalker() = default;
1000 
1001  using MemoryAccessSet = SmallVector<MemoryAccess *, 8>;
1002 
1003  /// Given a memory Mod/Ref/ModRef'ing instruction, calling this
1004  /// will give you the nearest dominating MemoryAccess that Mod's the location
1005  /// the instruction accesses (by skipping any def which AA can prove does not
1006  /// alias the location(s) accessed by the instruction given).
1007  ///
1008  /// Note that this will return a single access, and it must dominate the
1009  /// Instruction, so if an operand of a MemoryPhi node Mod's the instruction,
1010  /// this will return the MemoryPhi, not the operand. This means that
1011  /// given:
1012  /// if (a) {
1013  ///   1 = MemoryDef(liveOnEntry)
1014  ///   store %a
1015  /// } else {
1016  ///   2 = MemoryDef(liveOnEntry)
1017  ///   store %b
1018  /// }
1019  /// 3 = MemoryPhi(2, 1)
1020  /// MemoryUse(3)
1021  /// load %a
1022  ///
1023  /// calling this API on load(%a) will return the MemoryPhi, not the MemoryDef
1024  /// in the if (a) branch.
1025  MemoryAccess *getClobberingMemoryAccess(const Instruction *I) {
1026    MemoryAccess *MA = MSSA->getMemoryAccess(I);
1027    assert(MA && "Handed an instruction that MemorySSA doesn't recognize?")(static_cast <bool> (MA && "Handed an instruction that MemorySSA doesn't recognize?"
) ? void (0) : __assert_fail ("MA && \"Handed an instruction that MemorySSA doesn't recognize?\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 1027, __extension__ __PRETTY_FUNCTION__));
1028    return getClobberingMemoryAccess(MA);
1029  }
1030 
1031  /// Does the same thing as getClobberingMemoryAccess(const Instruction *I),
1032  /// but takes a MemoryAccess instead of an Instruction.
1033  virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) = 0;
1034 
1035  /// Given a potentially clobbering memory access and a new location,
1036  /// calling this will give you the nearest dominating clobbering MemoryAccess
1037  /// (by skipping non-aliasing def links).
1038  ///
1039  /// This version of the function is mainly used to disambiguate phi translated
1040  /// pointers, where the value of a pointer may have changed from the initial
1041  /// memory access. Note that this expects to be handed either a MemoryUse,
1042  /// or an already potentially clobbering access. Unlike the above API, if
1043  /// given a MemoryDef that clobbers the pointer as the starting access, it
1044  /// will return that MemoryDef, whereas the above would return the clobber
1045  /// starting from the use side of  the memory def.
1046  virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
1047                                                  const MemoryLocation &) = 0;
1048 
1049  /// Given a memory access, invalidate anything this walker knows about
1050  /// that access.
1051  /// This API is used by walkers that store information to perform basic cache
1052  /// invalidation.  This will be called by MemorySSA at appropriate times for
1053  /// the walker it uses or returns.
1054  virtual void invalidateInfo(MemoryAccess *) {}
1055 
1056protected:
1057  friend class MemorySSA; // For updating MSSA pointer in MemorySSA move
1058                          // constructor.
1059  MemorySSA *MSSA;
1060};
1061 
1062/// A MemorySSAWalker that does no alias queries, or anything else. It
1063/// simply returns the links as they were constructed by the builder.
1064class DoNothingMemorySSAWalker final : public MemorySSAWalker {
1065public:
1066  // Keep the overrides below from hiding the Instruction overload of
1067  // getClobberingMemoryAccess.
1068  using MemorySSAWalker::getClobberingMemoryAccess;
1069 
1070  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) override;
1071  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
1072                                          const MemoryLocation &) override;
1073};
1074 
1075using MemoryAccessPair = std::pair<MemoryAccess *, MemoryLocation>;
1076using ConstMemoryAccessPair = std::pair<const MemoryAccess *, MemoryLocation>;
1077 
1078/// Iterator base class used to implement const and non-const iterators
1079/// over the defining accesses of a MemoryAccess.
1080template <class T>
1081class memoryaccess_def_iterator_base
1082    : public iterator_facade_base<memoryaccess_def_iterator_base<T>,
1083                                  std::forward_iterator_tag, T, ptrdiff_t, T *,
1084                                  T *> {
1085  using BaseT = typename memoryaccess_def_iterator_base::iterator_facade_base;
1086 
1087public:
1088  memoryaccess_def_iterator_base(T *Start) : Access(Start) {}
1089  memoryaccess_def_iterator_base() = default;
1090 
1091  bool operator==(const memoryaccess_def_iterator_base &Other) const {
1092    return Access == Other.Access && (!Access || ArgNo == Other.ArgNo);
1093  }
1094 
1095  // This is a bit ugly, but for MemoryPHI's, unlike PHINodes, you can't get the
1096  // block from the operand in constant time (In a PHINode, the uselist has
1097  // both, so it's just subtraction). We provide it as part of the
1098  // iterator to avoid callers having to linear walk to get the block.
1099  // If the operation becomes constant time on MemoryPHI's, this bit of
1100  // abstraction breaking should be removed.
1101  BasicBlock *getPhiArgBlock() const {
1102    MemoryPhi *MP = dyn_cast<MemoryPhi>(Access);
1103    assert(MP && "Tried to get phi arg block when not iterating over a PHI")(static_cast <bool> (MP && "Tried to get phi arg block when not iterating over a PHI"
) ? void (0) : __assert_fail ("MP && \"Tried to get phi arg block when not iterating over a PHI\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 1103, __extension__ __PRETTY_FUNCTION__));
1104    return MP->getIncomingBlock(ArgNo);
1105  }
1106 
1107  typename std::iterator_traits<BaseT>::pointer operator*() const {
1108    assert(Access && "Tried to access past the end of our iterator")(static_cast <bool> (Access && "Tried to access past the end of our iterator"
) ? void (0) : __assert_fail ("Access && \"Tried to access past the end of our iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 1108, __extension__ __PRETTY_FUNCTION__));
1109    // Go to the first argument for phis, and the defining access for everything
1110    // else.
1111    if (const MemoryPhi *MP = dyn_cast<MemoryPhi>(Access))
1112      return MP->getIncomingValue(ArgNo);
1113    return cast<MemoryUseOrDef>(Access)->getDefiningAccess();
1114  }
1115 
1116  using BaseT::operator++;
1117  memoryaccess_def_iterator_base &operator++() {
1118    assert(Access && "Hit end of iterator")(static_cast <bool> (Access && "Hit end of iterator"
) ? void (0) : __assert_fail ("Access && \"Hit end of iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 1118, __extension__ __PRETTY_FUNCTION__));
1119    if (const MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) {
1120      if (++ArgNo >= MP->getNumIncomingValues()) {
1121        ArgNo = 0;
1122        Access = nullptr;
1123      }
1124    } else {
1125      Access = nullptr;
1126    }
1127    return *this;
1128  }
1129 
1130private:
1131  T *Access = nullptr;
1132  unsigned ArgNo = 0;
1133};
1134 
1135inline memoryaccess_def_iterator MemoryAccess::defs_begin() {
1136  return memoryaccess_def_iterator(this);
1137}
1138 
1139inline const_memoryaccess_def_iterator MemoryAccess::defs_begin() const {
1140  return const_memoryaccess_def_iterator(this);
1141}
1142 
1143inline memoryaccess_def_iterator MemoryAccess::defs_end() {
1144  return memoryaccess_def_iterator();
1145}
1146 
1147inline const_memoryaccess_def_iterator MemoryAccess::defs_end() const {
1148  return const_memoryaccess_def_iterator();
1149}
1150 
1151/// GraphTraits for a MemoryAccess, which walks defs in the normal case,
1152/// and uses in the inverse case.
1153template <> struct GraphTraits<MemoryAccess *> {
1154  using NodeRef = MemoryAccess *;
1155  using ChildIteratorType = memoryaccess_def_iterator;
1156 
1157  static NodeRef getEntryNode(NodeRef N) { return N; }
1158  static ChildIteratorType child_begin(NodeRef N) { return N->defs_begin(); }
1159  static ChildIteratorType child_end(NodeRef N) { return N->defs_end(); }
1160};
1161 
1162template <> struct GraphTraits<Inverse<MemoryAccess *>> {
1163  using NodeRef = MemoryAccess *;
1164  using ChildIteratorType = MemoryAccess::iterator;
1165 
1166  static NodeRef getEntryNode(NodeRef N) { return N; }
1167  static ChildIteratorType child_begin(NodeRef N) { return N->user_begin(); }
1168  static ChildIteratorType child_end(NodeRef N) { return N->user_end(); }
1169};
1170 
1171/// Provide an iterator that walks defs, giving both the memory access,
1172/// and the current pointer location, updating the pointer location as it
1173/// changes due to phi node translation.
1174///
1175/// This iterator, while somewhat specialized, is what most clients actually
1176/// want when walking upwards through MemorySSA def chains. It takes a pair of
1177/// <MemoryAccess,MemoryLocation>, and walks defs, properly translating the
1178/// memory location through phi nodes for the user.
1179class upward_defs_iterator
1180    : public iterator_facade_base<upward_defs_iterator,
1181                                  std::forward_iterator_tag,
1182                                  const MemoryAccessPair> {
1183  using BaseT = upward_defs_iterator::iterator_facade_base;
1184 
1185public:
1186  upward_defs_iterator(const MemoryAccessPair &Info, DominatorTree *DT,
1187                       bool *PerformedPhiTranslation = nullptr)
1188      : DefIterator(Info.first), Location(Info.second),
1189        OriginalAccess(Info.first), DT(DT),
1190        PerformedPhiTranslation(PerformedPhiTranslation) {
1191    CurrentPair.first = nullptr;
1192 
1193    WalkingPhi = Info.first && isa<MemoryPhi>(Info.first);
1194    fillInCurrentPair();
1195  }
1196 
1197  upward_defs_iterator() { CurrentPair.first = nullptr; }
1198 
1199  bool operator==(const upward_defs_iterator &Other) const {
1200    return DefIterator == Other.DefIterator;
1201  }
1202 
1203  typename std::iterator_traits<BaseT>::reference operator*() const {
1204    assert(DefIterator != OriginalAccess->defs_end() &&(static_cast <bool> (DefIterator != OriginalAccess->
defs_end() && "Tried to access past the end of our iterator"
) ? void (0) : __assert_fail ("DefIterator != OriginalAccess->defs_end() && \"Tried to access past the end of our iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 1205, __extension__ __PRETTY_FUNCTION__))
1205           "Tried to access past the end of our iterator")(static_cast <bool> (DefIterator != OriginalAccess->
defs_end() && "Tried to access past the end of our iterator"
) ? void (0) : __assert_fail ("DefIterator != OriginalAccess->defs_end() && \"Tried to access past the end of our iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 1205, __extension__ __PRETTY_FUNCTION__));
1206    return CurrentPair;
1207  }
1208 
1209  using BaseT::operator++;
1210  upward_defs_iterator &operator++() {
1211    assert(DefIterator != OriginalAccess->defs_end() &&(static_cast <bool> (DefIterator != OriginalAccess->
defs_end() && "Tried to access past the end of the iterator"
) ? void (0) : __assert_fail ("DefIterator != OriginalAccess->defs_end() && \"Tried to access past the end of the iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 1212, __extension__ __PRETTY_FUNCTION__))
1212           "Tried to access past the end of the iterator")(static_cast <bool> (DefIterator != OriginalAccess->
defs_end() && "Tried to access past the end of the iterator"
) ? void (0) : __assert_fail ("DefIterator != OriginalAccess->defs_end() && \"Tried to access past the end of the iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 1212, __extension__ __PRETTY_FUNCTION__));
1213    ++DefIterator;
1214    if (DefIterator != OriginalAccess->defs_end())
1215      fillInCurrentPair();
1216    return *this;
1217  }
1218 
1219  BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); }
1220 
1221private:
1222  /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
1223  /// loop. In particular, this guarantees that it only references a single
1224  /// MemoryLocation during execution of the containing function.
1225  bool IsGuaranteedLoopInvariant(Value *Ptr) const;
1226 
1227  void fillInCurrentPair() {
1228    CurrentPair.first = *DefIterator;
1229    CurrentPair.second = Location;
1230    if (WalkingPhi && Location.Ptr) {
1231      // Mark size as unknown, if the location is not guaranteed to be
1232      // loop-invariant for any possible loop in the function. Setting the size
1233      // to unknown guarantees that any memory accesses that access locations
1234      // after the pointer are considered as clobbers, which is important to
1235      // catch loop carried dependences.
1236      if (Location.Ptr &&
1237          !IsGuaranteedLoopInvariant(const_cast<Value *>(Location.Ptr)))
1238        CurrentPair.second =
1239            Location.getWithNewSize(LocationSize::beforeOrAfterPointer());
1240      PHITransAddr Translator(
1241          const_cast<Value *>(Location.Ptr),
1242          OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr);
1243 
1244      if (!Translator.PHITranslateValue(OriginalAccess->getBlock(),
1245                                        DefIterator.getPhiArgBlock(), DT,
1246                                        true)) {
1247        Value *TransAddr = Translator.getAddr();
1248        if (TransAddr != Location.Ptr) {
1249          CurrentPair.second = CurrentPair.second.getWithNewPtr(TransAddr);
1250 
1251          if (TransAddr &&
1252              !IsGuaranteedLoopInvariant(const_cast<Value *>(TransAddr)))
1253            CurrentPair.second = CurrentPair.second.getWithNewSize(
1254                LocationSize::beforeOrAfterPointer());
1255 
1256          if (PerformedPhiTranslation)
1257            *PerformedPhiTranslation = true;
1258        }
1259      }
1260    }
1261  }
1262 
1263  MemoryAccessPair CurrentPair;
1264  memoryaccess_def_iterator DefIterator;
1265  MemoryLocation Location;
1266  MemoryAccess *OriginalAccess = nullptr;
1267  DominatorTree *DT = nullptr;
1268  bool WalkingPhi = false;
1269  bool *PerformedPhiTranslation = nullptr;
1270};
1271 
1272inline upward_defs_iterator
1273upward_defs_begin(const MemoryAccessPair &Pair, DominatorTree &DT,
1274                  bool *PerformedPhiTranslation = nullptr) {
1275  return upward_defs_iterator(Pair, &DT, PerformedPhiTranslation);
1276}
1277 
1278inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); }
1279 
1280inline iterator_range<upward_defs_iterator>
1281upward_defs(const MemoryAccessPair &Pair, DominatorTree &DT) {
1282  return make_range(upward_defs_begin(Pair, DT), upward_defs_end());
1283}
1284 
1285/// Walks the defining accesses of MemoryDefs. Stops after we hit something that
1286/// has no defining use (e.g. a MemoryPhi or liveOnEntry). Note that, when
1287/// comparing against a null def_chain_iterator, this will compare equal only
1288/// after walking said Phi/liveOnEntry.
1289///
1290/// The UseOptimizedChain flag specifies whether to walk the clobbering
1291/// access chain, or all the accesses.
1292///
1293/// Normally, MemoryDef are all just def/use linked together, so a def_chain on
1294/// a MemoryDef will walk all MemoryDefs above it in the program until it hits
1295/// a phi node.  The optimized chain walks the clobbering access of a store.
1296/// So if you are just trying to find, given a store, what the next
1297/// thing that would clobber the same memory is, you want the optimized chain.
1298template <class T, bool UseOptimizedChain = false>
1299struct def_chain_iterator
1300    : public iterator_facade_base<def_chain_iterator<T, UseOptimizedChain>,
1301                                  std::forward_iterator_tag, MemoryAccess *> {
1302  def_chain_iterator() : MA(nullptr) {}
1303  def_chain_iterator(T MA) : MA(MA) {}
1304 
1305  T operator*() const { return MA; }
1306 
1307  def_chain_iterator &operator++() {
1308    // N.B. liveOnEntry has a null defining access.
1309    if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
1310      if (UseOptimizedChain && MUD->isOptimized())
1311        MA = MUD->getOptimized();
1312      else
1313        MA = MUD->getDefiningAccess();
1314    } else {
1315      MA = nullptr;
1316    }
1317 
1318    return *this;
1319  }
1320 
1321  bool operator==(const def_chain_iterator &O) const { return MA == O.MA; }
1322 
1323private:
1324  T MA;
1325};
1326 
1327template <class T>
1328inline iterator_range<def_chain_iterator<T>>
1329def_chain(T MA, MemoryAccess *UpTo = nullptr) {
1330#ifdef EXPENSIVE_CHECKS
1331  assert((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) &&(static_cast <bool> ((!UpTo || find(def_chain(MA), UpTo
) != def_chain_iterator<T>()) && "UpTo isn't in the def chain!"
) ? 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~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 1332, __extension__ __PRETTY_FUNCTION__))
1332         "UpTo isn't in the def chain!")(static_cast <bool> ((!UpTo || find(def_chain(MA), UpTo
) != def_chain_iterator<T>()) && "UpTo isn't in the def chain!"
) ? 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~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/MemorySSA.h"
, 1332, __extension__ __PRETTY_FUNCTION__));
1333#endif
1334  return make_range(def_chain_iterator<T>(MA), def_chain_iterator<T>(UpTo));
1335}
1336 
1337template <class T>
1338inline iterator_range<def_chain_iterator<T, true>> optimized_def_chain(T MA) {
1339  return make_range(def_chain_iterator<T, true>(MA),
1340                    def_chain_iterator<T, true>(nullptr));
1341}
1342 
1343} // end namespace llvm
1344 
1345#endif // LLVM_ANALYSIS_MEMORYSSA_H

←

/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/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 Kind : 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 Kind &Alias)
    : Alias(Alias), HasOffset(false), Offset(0) {}

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

constexpr bool hasOffset() const { return HasOffset; }
constexpr int32_t getOffset() const {
  assert(HasOffset && "No offset!")(static_cast <bool> (HasOffset && "No offset!")
 ? void (0) : __assert_fail ("HasOffset && \"No offset!\""
, "/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include/llvm/Analysis/AliasAnalysis.h"
, 119, __extension__ __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 = true) {
  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)) ==
26
←
Assuming the condition is false→
27
←
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) {
  AAQueryInfo AAQIP;
  return callCapturesBefore(I, MemLoc, DT, AAQIP);
}

/// 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);
}

841private:
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);
ModRefInfo callCapturesBefore(const Instruction *I,
                              const MemoryLocation &MemLoc, DominatorTree *DT,
                              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;
888};

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

900public:
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;
}
ModRefInfo callCapturesBefore(const Instruction *I,
                              const MemoryLocation &MemLoc,
                              DominatorTree *DT) {
  return AA.callCapturesBefore(I, MemLoc, DT, AAQI);
}
940};

942/// Temporary typedef for legacy code that uses a generic \c AliasAnalysis
943/// pointer or reference.
944using AliasAnalysis = AAResults;

946/// A private abstract base class describing the concept of an individual alias
947/// analysis implementation.
948///
949/// This interface is implemented by any \c Model instantiation. It is also the
950/// interface which a type used to instantiate the model must provide.
951///
952/// All of these methods model methods by the same name in the \c
953/// AAResults class. Only differences and specifics to how the
954/// implementations are called are documented here.
955class AAResults::Concept {
956public:
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;

/// @}
1011};

1013/// A private class template which derives from \c Concept and wraps some other
1014/// type.
1015///
1016/// This models the concept by directly forwarding each interface point to the
1017/// wrapped type which must implement a compatible interface. This provides
1018/// a type erased binding.
1019template <typename AAResultT> class AAResults::Model final : public Concept {
AAResultT &Result;

1022public:
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);
}
1061};

1063/// A CRTP-driven "mixin" base class to help implement the function alias
1064/// analysis results concept.
1065///
1066/// Because of the nature of many alias analysis implementations, they often
1067/// only implement a subset of the interface. This base class will attempt to
1068/// implement the remaining portions of the interface in terms of simpler forms
1069/// of the interface where possible, and otherwise provide conservatively
1070/// correct fallback implementations.
1071///
1072/// Implementors of an alias analysis should derive from this CRTP, and then
1073/// override specific methods that they wish to customize. There is no need to
1074/// use virtual anywhere, the CRTP base class does static dispatch to the
1075/// derived type passed into it.
1076template <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; }

1093protected:
/// 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()); }

1163public:
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;
}
1195};

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

1200/// Return true if this pointer refers to a distinct and identifiable object.
1201/// This returns true for:
1202///    Global Variables and Functions (but not Global Aliases)
1203///    Allocas
1204///    ByVal and NoAlias Arguments
1205///    NoAlias returns (e.g. calls to malloc)
1206///
1207bool isIdentifiedObject(const Value *V);

1209/// Return true if V is umabigously identified at the function-level.
1210/// Different IdentifiedFunctionLocals can't alias.
1211/// Further, an IdentifiedFunctionLocal can not alias with any function
1212/// arguments other than itself, which is not necessarily true for
1213/// IdentifiedObjects.
1214bool isIdentifiedFunctionLocal(const Value *V);

1216/// A manager for alias analyses.
1217///
1218/// This class can have analyses registered with it and when run, it will run
1219/// all of them and aggregate their results into single AA results interface
1220/// that dispatches across all of the alias analysis results available.
1221///
1222/// Note that the order in which analyses are registered is very significant.
1223/// That is the order in which the results will be aggregated and queried.
1224///
1225/// This manager effectively wraps the AnalysisManager for registering alias
1226/// analyses. When you register your alias analysis with this manager, it will
1227/// ensure the analysis itself is registered with its AnalysisManager.
1228///
1229/// The result of this analysis is only invalidated if one of the particular
1230/// aggregated AA results end up being invalidated. This removes the need to
1231/// explicitly preserve the results of `AAManager`. Note that analyses should no
1232/// longer be registered once the `AAManager` is run.
1233class AAManager : public AnalysisInfoMixin<AAManager> {
1234public:
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);

1249private:
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>();
  }
}
1277};

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

1284public:
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;
1295};

1297/// A wrapper pass for external alias analyses. This just squirrels away the
1298/// callback used to run any analyses and register their results.
1299struct 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();
}
1313};

1315FunctionPass *createAAResultsWrapperPass();

1317/// A wrapper pass around a callback which can be used to populate the
1318/// AAResults in the AAResultsWrapperPass from an external AA.
1319///
1320/// The callback provided here will be used each time we prepare an AAResults
1321/// object, and will receive a reference to the function wrapper pass, the
1322/// function, and the AAResults object to populate. This should be used when
1323/// setting up a custom pass pipeline to inject a hook into the AA results.
1324ImmutablePass *createExternalAAWrapperPass(
  std::function<void(Pass &, Function &, AAResults &)> Callback);

1327/// A helper for the legacy pass manager to create a \c AAResults
1328/// object populated to the best of our ability for a particular function when
1329/// inside of a \c ModulePass or a \c CallGraphSCCPass.
1330///
1331/// If a \c ModulePass or a \c CallGraphSCCPass calls \p
1332/// createLegacyPMAAResults, it also needs to call \p addUsedAAAnalyses in \p
1333/// getAnalysisUsage.
1334AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR);

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

1340} // end namespace llvm

1342#endif // LLVM_ANALYSIS_ALIASANALYSIS_H