brintos / llvm-project-archived public Read only

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-exception6//7//===----------------------------------------------------------------------===//8//9// This pass performs various transformations related to eliminating memcpy10// calls, or transforming sets of stores into memset's.11//12//===----------------------------------------------------------------------===//13 14#include "llvm/Transforms/Scalar/MemCpyOptimizer.h"15#include "llvm/ADT/DenseSet.h"16#include "llvm/ADT/STLExtras.h"17#include "llvm/ADT/ScopeExit.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/CFG.h"24#include "llvm/Analysis/CaptureTracking.h"25#include "llvm/Analysis/GlobalsModRef.h"26#include "llvm/Analysis/InstructionSimplify.h"27#include "llvm/Analysis/Loads.h"28#include "llvm/Analysis/MemoryLocation.h"29#include "llvm/Analysis/MemorySSA.h"30#include "llvm/Analysis/MemorySSAUpdater.h"31#include "llvm/Analysis/PostDominators.h"32#include "llvm/Analysis/TargetLibraryInfo.h"33#include "llvm/Analysis/ValueTracking.h"34#include "llvm/IR/BasicBlock.h"35#include "llvm/IR/Constants.h"36#include "llvm/IR/DataLayout.h"37#include "llvm/IR/DerivedTypes.h"38#include "llvm/IR/Dominators.h"39#include "llvm/IR/Function.h"40#include "llvm/IR/GlobalVariable.h"41#include "llvm/IR/IRBuilder.h"42#include "llvm/IR/InstrTypes.h"43#include "llvm/IR/Instruction.h"44#include "llvm/IR/Instructions.h"45#include "llvm/IR/IntrinsicInst.h"46#include "llvm/IR/Intrinsics.h"47#include "llvm/IR/LLVMContext.h"48#include "llvm/IR/Module.h"49#include "llvm/IR/PassManager.h"50#include "llvm/IR/ProfDataUtils.h"51#include "llvm/IR/Type.h"52#include "llvm/IR/User.h"53#include "llvm/IR/Value.h"54#include "llvm/Support/Casting.h"55#include "llvm/Support/Debug.h"56#include "llvm/Support/raw_ostream.h"57#include "llvm/Transforms/Utils/Local.h"58#include <algorithm>59#include <cassert>60#include <cstdint>61#include <optional>62 63using namespace llvm;64 65#define DEBUG_TYPE "memcpyopt"66 67static cl::opt<bool> EnableMemCpyOptWithoutLibcalls(68    "enable-memcpyopt-without-libcalls", cl::Hidden,69    cl::desc("Enable memcpyopt even when libcalls are disabled"));70 71STATISTIC(NumMemCpyInstr, "Number of memcpy instructions deleted");72STATISTIC(NumMemMoveInstr, "Number of memmove instructions deleted");73STATISTIC(NumMemSetInfer, "Number of memsets inferred");74STATISTIC(NumMoveToCpy, "Number of memmoves converted to memcpy");75STATISTIC(NumCpyToSet, "Number of memcpys converted to memset");76STATISTIC(NumCallSlot, "Number of call slot optimizations performed");77STATISTIC(NumStackMove, "Number of stack-move optimizations performed");78 79namespace {80 81/// Represents a range of memset'd bytes with the ByteVal value.82/// This allows us to analyze stores like:83///   store 0 -> P+184///   store 0 -> P+085///   store 0 -> P+386///   store 0 -> P+287/// which sometimes happens with stores to arrays of structs etc.  When we see88/// the first store, we make a range [1, 2).  The second store extends the range89/// to [0, 2).  The third makes a new range [2, 3).  The fourth store joins the90/// two ranges into [0, 3) which is memset'able.91struct MemsetRange {92  // Start/End - A semi range that describes the span that this range covers.93  // The range is closed at the start and open at the end: [Start, End).94  int64_t Start, End;95 96  /// StartPtr - The getelementptr instruction that points to the start of the97  /// range.98  Value *StartPtr;99 100  /// Alignment - The known alignment of the first store.101  MaybeAlign Alignment;102 103  /// TheStores - The actual stores that make up this range.104  SmallVector<Instruction *, 16> TheStores;105 106  bool isProfitableToUseMemset(const DataLayout &DL) const;107};108 109} // end anonymous namespace110 111static bool overreadUndefContents(MemorySSA *MSSA, MemCpyInst *MemCpy,112                                  MemIntrinsic *MemSrc, BatchAAResults &BAA);113 114bool MemsetRange::isProfitableToUseMemset(const DataLayout &DL) const {115  // If we found more than 4 stores to merge or 16 bytes, use memset.116  if (TheStores.size() >= 4 || End - Start >= 16)117    return true;118 119  // If there is nothing to merge, don't do anything.120  if (TheStores.size() < 2)121    return false;122 123  // If any of the stores are a memset, then it is always good to extend the124  // memset.125  for (Instruction *SI : TheStores)126    if (!isa<StoreInst>(SI))127      return true;128 129  // Assume that the code generator is capable of merging pairs of stores130  // together if it wants to.131  if (TheStores.size() == 2)132    return false;133 134  // If we have fewer than 8 stores, it can still be worthwhile to do this.135  // For example, merging 4 i8 stores into an i32 store is useful almost always.136  // However, merging 2 32-bit stores isn't useful on a 32-bit architecture (the137  // memset will be split into 2 32-bit stores anyway) and doing so can138  // pessimize the llvm optimizer.139  //140  // Since we don't have perfect knowledge here, make some assumptions: assume141  // the maximum GPR width is the same size as the largest legal integer142  // size. If so, check to see whether we will end up actually reducing the143  // number of stores used.144  unsigned Bytes = unsigned(End - Start);145  unsigned MaxIntSize = DL.getLargestLegalIntTypeSizeInBits() / 8;146  if (MaxIntSize == 0)147    MaxIntSize = 1;148  unsigned NumPointerStores = Bytes / MaxIntSize;149 150  // Assume the remaining bytes if any are done a byte at a time.151  unsigned NumByteStores = Bytes % MaxIntSize;152 153  // If we will reduce the # stores (according to this heuristic), do the154  // transformation.  This encourages merging 4 x i8 -> i32 and 2 x i16 -> i32155  // etc.156  return TheStores.size() > NumPointerStores + NumByteStores;157}158 159namespace {160 161class MemsetRanges {162  using range_iterator = SmallVectorImpl<MemsetRange>::iterator;163 164  /// A sorted list of the memset ranges.165  SmallVector<MemsetRange, 8> Ranges;166 167  const DataLayout &DL;168 169public:170  MemsetRanges(const DataLayout &DL) : DL(DL) {}171 172  using const_iterator = SmallVectorImpl<MemsetRange>::const_iterator;173 174  const_iterator begin() const { return Ranges.begin(); }175  const_iterator end() const { return Ranges.end(); }176  bool empty() const { return Ranges.empty(); }177 178  void addInst(int64_t OffsetFromFirst, Instruction *Inst) {179    if (auto *SI = dyn_cast<StoreInst>(Inst))180      addStore(OffsetFromFirst, SI);181    else182      addMemSet(OffsetFromFirst, cast<MemSetInst>(Inst));183  }184 185  void addStore(int64_t OffsetFromFirst, StoreInst *SI) {186    TypeSize StoreSize = DL.getTypeStoreSize(SI->getOperand(0)->getType());187    assert(!StoreSize.isScalable() && "Can't track scalable-typed stores");188    addRange(OffsetFromFirst, StoreSize.getFixedValue(),189             SI->getPointerOperand(), SI->getAlign(), SI);190  }191 192  void addMemSet(int64_t OffsetFromFirst, MemSetInst *MSI) {193    int64_t Size = cast<ConstantInt>(MSI->getLength())->getZExtValue();194    addRange(OffsetFromFirst, Size, MSI->getDest(), MSI->getDestAlign(), MSI);195  }196 197  void addRange(int64_t Start, int64_t Size, Value *Ptr, MaybeAlign Alignment,198                Instruction *Inst);199};200 201} // end anonymous namespace202 203/// Add a new store to the MemsetRanges data structure.  This adds a204/// new range for the specified store at the specified offset, merging into205/// existing ranges as appropriate.206void MemsetRanges::addRange(int64_t Start, int64_t Size, Value *Ptr,207                            MaybeAlign Alignment, Instruction *Inst) {208  int64_t End = Start + Size;209 210  range_iterator I = partition_point(211      Ranges, [=](const MemsetRange &O) { return O.End < Start; });212 213  // We now know that I == E, in which case we didn't find anything to merge214  // with, or that Start <= I->End.  If End < I->Start or I == E, then we need215  // to insert a new range.  Handle this now.216  if (I == Ranges.end() || End < I->Start) {217    MemsetRange &R = *Ranges.insert(I, MemsetRange());218    R.Start = Start;219    R.End = End;220    R.StartPtr = Ptr;221    R.Alignment = Alignment;222    R.TheStores.push_back(Inst);223    return;224  }225 226  // This store overlaps with I, add it.227  I->TheStores.push_back(Inst);228 229  // At this point, we may have an interval that completely contains our store.230  // If so, just add it to the interval and return.231  if (I->Start <= Start && I->End >= End)232    return;233 234  // Now we know that Start <= I->End and End >= I->Start so the range overlaps235  // but is not entirely contained within the range.236 237  // See if the range extends the start of the range.  In this case, it couldn't238  // possibly cause it to join the prior range, because otherwise we would have239  // stopped on *it*.240  if (Start < I->Start) {241    I->Start = Start;242    I->StartPtr = Ptr;243    I->Alignment = Alignment;244  }245 246  // Now we know that Start <= I->End and Start >= I->Start (so the startpoint247  // is in or right at the end of I), and that End >= I->Start.  Extend I out to248  // End.249  if (End > I->End) {250    I->End = End;251    range_iterator NextI = I;252    while (++NextI != Ranges.end() && End >= NextI->Start) {253      // Merge the range in.254      I->TheStores.append(NextI->TheStores.begin(), NextI->TheStores.end());255      if (NextI->End > I->End)256        I->End = NextI->End;257      Ranges.erase(NextI);258      NextI = I;259    }260  }261}262 263//===----------------------------------------------------------------------===//264//                         MemCpyOptLegacyPass Pass265//===----------------------------------------------------------------------===//266 267// Check that V is either not accessible by the caller, or unwinding cannot268// occur between Start and End.269static bool mayBeVisibleThroughUnwinding(Value *V, Instruction *Start,270                                         Instruction *End) {271  assert(Start->getParent() == End->getParent() && "Must be in same block");272  // Function can't unwind, so it also can't be visible through unwinding.273  if (Start->getFunction()->doesNotThrow())274    return false;275 276  // Object is not visible on unwind.277  // TODO: Support RequiresNoCaptureBeforeUnwind case.278  bool RequiresNoCaptureBeforeUnwind;279  if (isNotVisibleOnUnwind(getUnderlyingObject(V),280                           RequiresNoCaptureBeforeUnwind) &&281      !RequiresNoCaptureBeforeUnwind)282    return false;283 284  // Check whether there are any unwinding instructions in the range.285  return any_of(make_range(Start->getIterator(), End->getIterator()),286                [](const Instruction &I) { return I.mayThrow(); });287}288 289void MemCpyOptPass::eraseInstruction(Instruction *I) {290  MSSAU->removeMemoryAccess(I);291  EEA->removeInstruction(I);292  I->eraseFromParent();293}294 295// Check for mod or ref of Loc between Start and End, excluding both boundaries.296// Start and End must be in the same block.297// If SkippedLifetimeStart is provided, skip over one clobbering lifetime.start298// intrinsic and store it inside SkippedLifetimeStart.299static bool accessedBetween(BatchAAResults &AA, MemoryLocation Loc,300                            const MemoryUseOrDef *Start,301                            const MemoryUseOrDef *End,302                            Instruction **SkippedLifetimeStart = nullptr) {303  assert(Start->getBlock() == End->getBlock() && "Only local supported");304  for (const MemoryAccess &MA :305       make_range(++Start->getIterator(), End->getIterator())) {306    Instruction *I = cast<MemoryUseOrDef>(MA).getMemoryInst();307    if (isModOrRefSet(AA.getModRefInfo(I, Loc))) {308      auto *II = dyn_cast<IntrinsicInst>(I);309      if (II && II->getIntrinsicID() == Intrinsic::lifetime_start &&310          SkippedLifetimeStart && !*SkippedLifetimeStart) {311        *SkippedLifetimeStart = I;312        continue;313      }314 315      return true;316    }317  }318  return false;319}320 321// Check for mod of Loc between Start and End, excluding both boundaries.322// Start and End can be in different blocks.323static bool writtenBetween(MemorySSA *MSSA, BatchAAResults &AA,324                           MemoryLocation Loc, const MemoryUseOrDef *Start,325                           const MemoryUseOrDef *End) {326  if (isa<MemoryUse>(End)) {327    // For MemoryUses, getClobberingMemoryAccess may skip non-clobbering writes.328    // Manually check read accesses between Start and End, if they are in the329    // same block, for clobbers. Otherwise assume Loc is clobbered.330    return Start->getBlock() != End->getBlock() ||331           any_of(332               make_range(std::next(Start->getIterator()), End->getIterator()),333               [&AA, Loc](const MemoryAccess &Acc) {334                 if (isa<MemoryUse>(&Acc))335                   return false;336                 Instruction *AccInst =337                     cast<MemoryUseOrDef>(&Acc)->getMemoryInst();338                 return isModSet(AA.getModRefInfo(AccInst, Loc));339               });340  }341 342  // TODO: Only walk until we hit Start.343  MemoryAccess *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(344      End->getDefiningAccess(), Loc, AA);345  return !MSSA->dominates(Clobber, Start);346}347 348/// When scanning forward over instructions, we look for some other patterns to349/// fold away. In particular, this looks for stores to neighboring locations of350/// memory. If it sees enough consecutive ones, it attempts to merge them351/// together into a memcpy/memset.352Instruction *MemCpyOptPass::tryMergingIntoMemset(Instruction *StartInst,353                                                 Value *StartPtr,354                                                 Value *ByteVal) {355  const DataLayout &DL = StartInst->getDataLayout();356 357  // We can't track scalable types358  if (auto *SI = dyn_cast<StoreInst>(StartInst))359    if (DL.getTypeStoreSize(SI->getOperand(0)->getType()).isScalable())360      return nullptr;361 362  // Okay, so we now have a single store that can be splatable.  Scan to find363  // all subsequent stores of the same value to offset from the same pointer.364  // Join these together into ranges, so we can decide whether contiguous blocks365  // are stored.366  MemsetRanges Ranges(DL);367 368  BasicBlock::iterator BI(StartInst);369 370  // Keeps track of the last memory use or def before the insertion point for371  // the new memset. The new MemoryDef for the inserted memsets will be inserted372  // after MemInsertPoint.373  MemoryUseOrDef *MemInsertPoint = nullptr;374  for (++BI; !BI->isTerminator(); ++BI) {375    auto *CurrentAcc =376        cast_or_null<MemoryUseOrDef>(MSSA->getMemoryAccess(&*BI));377    if (CurrentAcc)378      MemInsertPoint = CurrentAcc;379 380    // Calls that only access inaccessible memory do not block merging381    // accessible stores.382    if (auto *CB = dyn_cast<CallBase>(BI)) {383      if (CB->onlyAccessesInaccessibleMemory())384        continue;385    }386 387    if (!isa<StoreInst>(BI) && !isa<MemSetInst>(BI)) {388      // If the instruction is readnone, ignore it, otherwise bail out.  We389      // don't even allow readonly here because we don't want something like:390      // A[1] = 2; strlen(A); A[2] = 2; -> memcpy(A, ...); strlen(A).391      if (BI->mayWriteToMemory() || BI->mayReadFromMemory())392        break;393      continue;394    }395 396    if (auto *NextStore = dyn_cast<StoreInst>(BI)) {397      // If this is a store, see if we can merge it in.398      if (!NextStore->isSimple())399        break;400 401      Value *StoredVal = NextStore->getValueOperand();402 403      // Don't convert stores of non-integral pointer types to memsets (which404      // stores integers).405      if (DL.isNonIntegralPointerType(StoredVal->getType()->getScalarType()))406        break;407 408      // We can't track ranges involving scalable types.409      if (DL.getTypeStoreSize(StoredVal->getType()).isScalable())410        break;411 412      // Check to see if this stored value is of the same byte-splattable value.413      Value *StoredByte = isBytewiseValue(StoredVal, DL);414      if (isa<UndefValue>(ByteVal) && StoredByte)415        ByteVal = StoredByte;416      if (ByteVal != StoredByte)417        break;418 419      // Check to see if this store is to a constant offset from the start ptr.420      std::optional<int64_t> Offset =421          NextStore->getPointerOperand()->getPointerOffsetFrom(StartPtr, DL);422      if (!Offset)423        break;424 425      Ranges.addStore(*Offset, NextStore);426    } else {427      auto *MSI = cast<MemSetInst>(BI);428 429      if (MSI->isVolatile() || ByteVal != MSI->getValue() ||430          !isa<ConstantInt>(MSI->getLength()))431        break;432 433      // Check to see if this store is to a constant offset from the start ptr.434      std::optional<int64_t> Offset =435          MSI->getDest()->getPointerOffsetFrom(StartPtr, DL);436      if (!Offset)437        break;438 439      Ranges.addMemSet(*Offset, MSI);440    }441  }442 443  // If we have no ranges, then we just had a single store with nothing that444  // could be merged in.  This is a very common case of course.445  if (Ranges.empty())446    return nullptr;447 448  // If we had at least one store that could be merged in, add the starting449  // store as well.  We try to avoid this unless there is at least something450  // interesting as a small compile-time optimization.451  Ranges.addInst(0, StartInst);452 453  // If we create any memsets, we put it right before the first instruction that454  // isn't part of the memset block.  This ensure that the memset is dominated455  // by any addressing instruction needed by the start of the block.456  IRBuilder<> Builder(&*BI);457 458  // Now that we have full information about ranges, loop over the ranges and459  // emit memset's for anything big enough to be worthwhile.460  Instruction *AMemSet = nullptr;461  for (const MemsetRange &Range : Ranges) {462    if (Range.TheStores.size() == 1)463      continue;464 465    // If it is profitable to lower this range to memset, do so now.466    if (!Range.isProfitableToUseMemset(DL))467      continue;468 469    // Otherwise, we do want to transform this!  Create a new memset.470    // Get the starting pointer of the block.471    StartPtr = Range.StartPtr;472 473    AMemSet = Builder.CreateMemSet(StartPtr, ByteVal, Range.End - Range.Start,474                                   Range.Alignment);475    AMemSet->mergeDIAssignID(Range.TheStores);476 477    LLVM_DEBUG(dbgs() << "Replace stores:\n"; for (Instruction *SI478                                                   : Range.TheStores) dbgs()479                                              << *SI << '\n';480               dbgs() << "With: " << *AMemSet << '\n');481    if (!Range.TheStores.empty())482      AMemSet->setDebugLoc(Range.TheStores[0]->getDebugLoc());483 484    auto *NewDef = cast<MemoryDef>(485        MemInsertPoint->getMemoryInst() == &*BI486            ? MSSAU->createMemoryAccessBefore(AMemSet, nullptr, MemInsertPoint)487            : MSSAU->createMemoryAccessAfter(AMemSet, nullptr, MemInsertPoint));488    MSSAU->insertDef(NewDef, /*RenameUses=*/true);489    MemInsertPoint = NewDef;490 491    // Zap all the stores.492    for (Instruction *SI : Range.TheStores)493      eraseInstruction(SI);494 495    ++NumMemSetInfer;496  }497 498  return AMemSet;499}500 501// This method try to lift a store instruction before position P.502// It will lift the store and its argument + that anything that503// may alias with these.504// The method returns true if it was successful.505bool MemCpyOptPass::moveUp(StoreInst *SI, Instruction *P, const LoadInst *LI) {506  // If the store alias this position, early bail out.507  MemoryLocation StoreLoc = MemoryLocation::get(SI);508  if (isModOrRefSet(AA->getModRefInfo(P, StoreLoc)))509    return false;510 511  // Keep track of the arguments of all instruction we plan to lift512  // so we can make sure to lift them as well if appropriate.513  DenseSet<Instruction *> Args;514  auto AddArg = [&](Value *Arg) {515    auto *I = dyn_cast<Instruction>(Arg);516    if (I && I->getParent() == SI->getParent()) {517      // Cannot hoist user of P above P518      if (I == P)519        return false;520      Args.insert(I);521    }522    return true;523  };524  if (!AddArg(SI->getPointerOperand()))525    return false;526 527  // Instruction to lift before P.528  SmallVector<Instruction *, 8> ToLift{SI};529 530  // Memory locations of lifted instructions.531  SmallVector<MemoryLocation, 8> MemLocs{StoreLoc};532 533  // Lifted calls.534  SmallVector<const CallBase *, 8> Calls;535 536  const MemoryLocation LoadLoc = MemoryLocation::get(LI);537 538  for (auto I = --SI->getIterator(), E = P->getIterator(); I != E; --I) {539    auto *C = &*I;540 541    // Make sure hoisting does not perform a store that was not guaranteed to542    // happen.543    if (!isGuaranteedToTransferExecutionToSuccessor(C))544      return false;545 546    bool MayAlias = isModOrRefSet(AA->getModRefInfo(C, std::nullopt));547 548    bool NeedLift = false;549    if (Args.erase(C))550      NeedLift = true;551    else if (MayAlias) {552      NeedLift = llvm::any_of(MemLocs, [C, this](const MemoryLocation &ML) {553        return isModOrRefSet(AA->getModRefInfo(C, ML));554      });555 556      if (!NeedLift)557        NeedLift = llvm::any_of(Calls, [C, this](const CallBase *Call) {558          return isModOrRefSet(AA->getModRefInfo(C, Call));559        });560    }561 562    if (!NeedLift)563      continue;564 565    if (MayAlias) {566      // Since LI is implicitly moved downwards past the lifted instructions,567      // none of them may modify its source.568      if (isModSet(AA->getModRefInfo(C, LoadLoc)))569        return false;570      else if (const auto *Call = dyn_cast<CallBase>(C)) {571        // If we can't lift this before P, it's game over.572        if (isModOrRefSet(AA->getModRefInfo(P, Call)))573          return false;574 575        Calls.push_back(Call);576      } else if (isa<LoadInst>(C) || isa<StoreInst>(C) || isa<VAArgInst>(C)) {577        // If we can't lift this before P, it's game over.578        auto ML = MemoryLocation::get(C);579        if (isModOrRefSet(AA->getModRefInfo(P, ML)))580          return false;581 582        MemLocs.push_back(ML);583      } else584        // We don't know how to lift this instruction.585        return false;586    }587 588    ToLift.push_back(C);589    for (Value *Op : C->operands())590      if (!AddArg(Op))591        return false;592  }593 594  // Find MSSA insertion point. Normally P will always have a corresponding595  // memory access before which we can insert. However, with non-standard AA596  // pipelines, there may be a mismatch between AA and MSSA, in which case we597  // will scan for a memory access before P. In either case, we know for sure598  // that at least the load will have a memory access.599  // TODO: Simplify this once P will be determined by MSSA, in which case the600  // discrepancy can no longer occur.601  MemoryUseOrDef *MemInsertPoint = nullptr;602  if (MemoryUseOrDef *MA = MSSA->getMemoryAccess(P)) {603    MemInsertPoint = cast<MemoryUseOrDef>(--MA->getIterator());604  } else {605    const Instruction *ConstP = P;606    for (const Instruction &I : make_range(++ConstP->getReverseIterator(),607                                           ++LI->getReverseIterator())) {608      if (MemoryUseOrDef *MA = MSSA->getMemoryAccess(&I)) {609        MemInsertPoint = MA;610        break;611      }612    }613  }614 615  // We made it, we need to lift.616  for (auto *I : llvm::reverse(ToLift)) {617    LLVM_DEBUG(dbgs() << "Lifting " << *I << " before " << *P << "\n");618    I->moveBefore(P->getIterator());619    assert(MemInsertPoint && "Must have found insert point");620    if (MemoryUseOrDef *MA = MSSA->getMemoryAccess(I)) {621      MSSAU->moveAfter(MA, MemInsertPoint);622      MemInsertPoint = MA;623    }624  }625 626  return true;627}628 629bool MemCpyOptPass::processStoreOfLoad(StoreInst *SI, LoadInst *LI,630                                       const DataLayout &DL,631                                       BasicBlock::iterator &BBI) {632  if (!LI->isSimple() || !LI->hasOneUse() || LI->getParent() != SI->getParent())633    return false;634 635  BatchAAResults BAA(*AA, EEA);636  auto *T = LI->getType();637  // Don't introduce calls to memcpy/memmove intrinsics out of thin air if638  // the corresponding libcalls are not available.639  // TODO: We should really distinguish between libcall availability and640  // our ability to introduce intrinsics.641  if (T->isAggregateType() &&642      (EnableMemCpyOptWithoutLibcalls ||643       (TLI->has(LibFunc_memcpy) && TLI->has(LibFunc_memmove)))) {644    MemoryLocation LoadLoc = MemoryLocation::get(LI);645 646    // We use alias analysis to check if an instruction may store to647    // the memory we load from in between the load and the store. If648    // such an instruction is found, we try to promote there instead649    // of at the store position.650    // TODO: Can use MSSA for this.651    Instruction *P = SI;652    for (auto &I : make_range(++LI->getIterator(), SI->getIterator())) {653      if (isModSet(BAA.getModRefInfo(&I, LoadLoc))) {654        P = &I;655        break;656      }657    }658 659    // If we found an instruction that may write to the loaded memory,660    // we can try to promote at this position instead of the store661    // position if nothing aliases the store memory after this and the store662    // destination is not in the range.663    if (P == SI || moveUp(SI, P, LI)) {664      // If we load from memory that may alias the memory we store to,665      // memmove must be used to preserve semantic. If not, memcpy can666      // be used. Also, if we load from constant memory, memcpy can be used667      // as the constant memory won't be modified.668      bool UseMemMove = false;669      if (isModSet(AA->getModRefInfo(SI, LoadLoc)))670        UseMemMove = true;671 672      IRBuilder<> Builder(P);673      Value *Size =674          Builder.CreateTypeSize(Builder.getInt64Ty(), DL.getTypeStoreSize(T));675      Instruction *M;676      if (UseMemMove)677        M = Builder.CreateMemMove(SI->getPointerOperand(), SI->getAlign(),678                                  LI->getPointerOperand(), LI->getAlign(),679                                  Size);680      else681        M = Builder.CreateMemCpy(SI->getPointerOperand(), SI->getAlign(),682                                 LI->getPointerOperand(), LI->getAlign(), Size);683      M->copyMetadata(*SI, LLVMContext::MD_DIAssignID);684 685      LLVM_DEBUG(dbgs() << "Promoting " << *LI << " to " << *SI << " => " << *M686                        << "\n");687 688      auto *LastDef = cast<MemoryDef>(MSSA->getMemoryAccess(SI));689      auto *NewAccess = MSSAU->createMemoryAccessAfter(M, nullptr, LastDef);690      MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);691 692      eraseInstruction(SI);693      eraseInstruction(LI);694      ++NumMemCpyInstr;695 696      // Make sure we do not invalidate the iterator.697      BBI = M->getIterator();698      return true;699    }700  }701 702  // Detect cases where we're performing call slot forwarding, but703  // happen to be using a load-store pair to implement it, rather than704  // a memcpy.705  auto GetCall = [&]() -> CallInst * {706    // We defer this expensive clobber walk until the cheap checks707    // have been done on the source inside performCallSlotOptzn.708    if (auto *LoadClobber = dyn_cast<MemoryUseOrDef>(709            MSSA->getWalker()->getClobberingMemoryAccess(LI, BAA)))710      return dyn_cast_or_null<CallInst>(LoadClobber->getMemoryInst());711    return nullptr;712  };713 714  bool Changed = performCallSlotOptzn(715      LI, SI, SI->getPointerOperand()->stripPointerCasts(),716      LI->getPointerOperand()->stripPointerCasts(),717      DL.getTypeStoreSize(SI->getOperand(0)->getType()),718      std::min(SI->getAlign(), LI->getAlign()), BAA, GetCall);719  if (Changed) {720    eraseInstruction(SI);721    eraseInstruction(LI);722    ++NumMemCpyInstr;723    return true;724  }725 726  // If this is a load-store pair from a stack slot to a stack slot, we727  // might be able to perform the stack-move optimization just as we do for728  // memcpys from an alloca to an alloca.729  if (auto *DestAlloca = dyn_cast<AllocaInst>(SI->getPointerOperand())) {730    if (auto *SrcAlloca = dyn_cast<AllocaInst>(LI->getPointerOperand())) {731      if (performStackMoveOptzn(LI, SI, DestAlloca, SrcAlloca,732                                DL.getTypeStoreSize(T), BAA)) {733        // Avoid invalidating the iterator.734        BBI = SI->getNextNode()->getIterator();735        eraseInstruction(SI);736        eraseInstruction(LI);737        ++NumMemCpyInstr;738        return true;739      }740    }741  }742 743  return false;744}745 746bool MemCpyOptPass::processStore(StoreInst *SI, BasicBlock::iterator &BBI) {747  if (!SI->isSimple())748    return false;749 750  // Avoid merging nontemporal stores since the resulting751  // memcpy/memset would not be able to preserve the nontemporal hint.752  // In theory we could teach how to propagate the !nontemporal metadata to753  // memset calls. However, that change would force the backend to754  // conservatively expand !nontemporal memset calls back to sequences of755  // store instructions (effectively undoing the merging).756  if (SI->getMetadata(LLVMContext::MD_nontemporal))757    return false;758 759  const DataLayout &DL = SI->getDataLayout();760 761  Value *StoredVal = SI->getValueOperand();762 763  // Not all the transforms below are correct for non-integral pointers, bail764  // until we've audited the individual pieces.765  if (DL.isNonIntegralPointerType(StoredVal->getType()->getScalarType()))766    return false;767 768  // Load to store forwarding can be interpreted as memcpy.769  if (auto *LI = dyn_cast<LoadInst>(StoredVal))770    return processStoreOfLoad(SI, LI, DL, BBI);771 772  // The following code creates memset intrinsics out of thin air. Don't do773  // this if the corresponding libfunc is not available.774  // TODO: We should really distinguish between libcall availability and775  // our ability to introduce intrinsics.776  if (!(TLI->has(LibFunc_memset) || EnableMemCpyOptWithoutLibcalls))777    return false;778 779  // There are two cases that are interesting for this code to handle: memcpy780  // and memset.  Right now we only handle memset.781 782  // Ensure that the value being stored is something that can be memset'able a783  // byte at a time like "0" or "-1" or any width, as well as things like784  // 0xA0A0A0A0 and 0.0.785  Value *V = SI->getOperand(0);786  Value *ByteVal = isBytewiseValue(V, DL);787  if (!ByteVal)788    return false;789 790  if (Instruction *I =791          tryMergingIntoMemset(SI, SI->getPointerOperand(), ByteVal)) {792    BBI = I->getIterator(); // Don't invalidate iterator.793    return true;794  }795 796  // If we have an aggregate, we try to promote it to memset regardless797  // of opportunity for merging as it can expose optimization opportunities798  // in subsequent passes.799  auto *T = V->getType();800  if (!T->isAggregateType())801    return false;802 803  TypeSize Size = DL.getTypeStoreSize(T);804  if (Size.isScalable())805    return false;806 807  IRBuilder<> Builder(SI);808  auto *M = Builder.CreateMemSet(SI->getPointerOperand(), ByteVal, Size,809                                 SI->getAlign());810  M->copyMetadata(*SI, LLVMContext::MD_DIAssignID);811 812  LLVM_DEBUG(dbgs() << "Promoting " << *SI << " to " << *M << "\n");813 814  // The newly inserted memset is immediately overwritten by the original815  // store, so we do not need to rename uses.816  auto *StoreDef = cast<MemoryDef>(MSSA->getMemoryAccess(SI));817  auto *NewAccess = MSSAU->createMemoryAccessBefore(M, nullptr, StoreDef);818  MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/false);819 820  eraseInstruction(SI);821  NumMemSetInfer++;822 823  // Make sure we do not invalidate the iterator.824  BBI = M->getIterator();825  return true;826}827 828bool MemCpyOptPass::processMemSet(MemSetInst *MSI, BasicBlock::iterator &BBI) {829  // See if there is another memset or store neighboring this memset which830  // allows us to widen out the memset to do a single larger store.831  if (isa<ConstantInt>(MSI->getLength()) && !MSI->isVolatile())832    if (Instruction *I =833            tryMergingIntoMemset(MSI, MSI->getDest(), MSI->getValue())) {834      BBI = I->getIterator(); // Don't invalidate iterator.835      return true;836    }837  return false;838}839 840/// Takes a memcpy and a call that it depends on,841/// and checks for the possibility of a call slot optimization by having842/// the call write its result directly into the destination of the memcpy.843bool MemCpyOptPass::performCallSlotOptzn(Instruction *cpyLoad,844                                         Instruction *cpyStore, Value *cpyDest,845                                         Value *cpySrc, TypeSize cpySize,846                                         Align cpyDestAlign,847                                         BatchAAResults &BAA,848                                         std::function<CallInst *()> GetC) {849  // The general transformation to keep in mind is850  //851  //   call @func(..., src, ...)852  //   memcpy(dest, src, ...)853  //854  // ->855  //856  //   memcpy(dest, src, ...)857  //   call @func(..., dest, ...)858  //859  // Since moving the memcpy is technically awkward, we additionally check that860  // src only holds uninitialized values at the moment of the call, meaning that861  // the memcpy can be discarded rather than moved.862 863  // We can't optimize scalable types.864  if (cpySize.isScalable())865    return false;866 867  // Require that src be an alloca.  This simplifies the reasoning considerably.868  auto *srcAlloca = dyn_cast<AllocaInst>(cpySrc);869  if (!srcAlloca)870    return false;871 872  ConstantInt *srcArraySize = dyn_cast<ConstantInt>(srcAlloca->getArraySize());873  if (!srcArraySize)874    return false;875 876  const DataLayout &DL = cpyLoad->getDataLayout();877  TypeSize SrcAllocaSize = DL.getTypeAllocSize(srcAlloca->getAllocatedType());878  // We can't optimize scalable types.879  if (SrcAllocaSize.isScalable())880    return false;881  uint64_t srcSize = SrcAllocaSize * srcArraySize->getZExtValue();882 883  if (cpySize < srcSize)884    return false;885 886  CallInst *C = GetC();887  if (!C)888    return false;889 890  // Lifetime marks shouldn't be operated on.891  if (Function *F = C->getCalledFunction())892    if (F->isIntrinsic() && F->getIntrinsicID() == Intrinsic::lifetime_start)893      return false;894 895  if (C->getParent() != cpyStore->getParent()) {896    LLVM_DEBUG(dbgs() << "Call Slot: block local restriction\n");897    return false;898  }899 900  MemoryLocation DestLoc =901      isa<StoreInst>(cpyStore)902          ? MemoryLocation::get(cpyStore)903          : MemoryLocation::getForDest(cast<MemCpyInst>(cpyStore));904 905  // Check that nothing touches the dest of the copy between906  // the call and the store/memcpy.907  Instruction *SkippedLifetimeStart = nullptr;908  if (accessedBetween(BAA, DestLoc, MSSA->getMemoryAccess(C),909                      MSSA->getMemoryAccess(cpyStore), &SkippedLifetimeStart)) {910    LLVM_DEBUG(dbgs() << "Call Slot: Dest pointer modified after call\n");911    return false;912  }913 914  // If we need to move a lifetime.start above the call, make sure that we can915  // actually do so. If the argument is bitcasted for example, we would have to916  // move the bitcast as well, which we don't handle.917  if (SkippedLifetimeStart) {918    auto *LifetimeArg =919        dyn_cast<Instruction>(SkippedLifetimeStart->getOperand(0));920    if (LifetimeArg && LifetimeArg->getParent() == C->getParent() &&921        C->comesBefore(LifetimeArg))922      return false;923  }924 925  // Check that storing to the first srcSize bytes of dest will not cause a926  // trap or data race.927  bool ExplicitlyDereferenceableOnly;928  if (!isWritableObject(getUnderlyingObject(cpyDest),929                        ExplicitlyDereferenceableOnly) ||930      !isDereferenceableAndAlignedPointer(cpyDest, Align(1), APInt(64, cpySize),931                                          DL, C, AC, DT)) {932    LLVM_DEBUG(dbgs() << "Call Slot: Dest pointer not dereferenceable\n");933    return false;934  }935 936  // Make sure that nothing can observe cpyDest being written early. There are937  // a number of cases to consider:938  //  1. cpyDest cannot be accessed between C and cpyStore as a precondition of939  //     the transform.940  //  2. C itself may not access cpyDest (prior to the transform). This is941  //     checked further below.942  //  3. If cpyDest is accessible to the caller of this function (potentially943  //     captured and not based on an alloca), we need to ensure that we cannot944  //     unwind between C and cpyStore. This is checked here.945  //  4. If cpyDest is potentially captured, there may be accesses to it from946  //     another thread. In this case, we need to check that cpyStore is947  //     guaranteed to be executed if C is. As it is a non-atomic access, it948  //     renders accesses from other threads undefined.949  //     TODO: This is currently not checked.950  if (mayBeVisibleThroughUnwinding(cpyDest, C, cpyStore)) {951    LLVM_DEBUG(dbgs() << "Call Slot: Dest may be visible through unwinding\n");952    return false;953  }954 955  // Check that dest points to memory that is at least as aligned as src.956  Align srcAlign = srcAlloca->getAlign();957  bool isDestSufficientlyAligned = srcAlign <= cpyDestAlign;958  // If dest is not aligned enough and we can't increase its alignment then959  // bail out.960  if (!isDestSufficientlyAligned && !isa<AllocaInst>(cpyDest)) {961    LLVM_DEBUG(dbgs() << "Call Slot: Dest not sufficiently aligned\n");962    return false;963  }964 965  // Check that src is not accessed except via the call and the memcpy.  This966  // guarantees that it holds only undefined values when passed in (so the final967  // memcpy can be dropped), that it is not read or written between the call and968  // the memcpy, and that writing beyond the end of it is undefined.969  SmallVector<User *, 8> srcUseList(srcAlloca->users());970  while (!srcUseList.empty()) {971    User *U = srcUseList.pop_back_val();972 973    if (isa<AddrSpaceCastInst>(U)) {974      append_range(srcUseList, U->users());975      continue;976    }977    if (isa<LifetimeIntrinsic>(U))978      continue;979 980    if (U != C && U != cpyLoad) {981      LLVM_DEBUG(dbgs() << "Call slot: Source accessed by " << *U << "\n");982      return false;983    }984  }985 986  // Check whether src is captured by the called function, in which case there987  // may be further indirect uses of src.988  bool SrcIsCaptured = any_of(C->args(), [&](Use &U) {989    return U->stripPointerCasts() == cpySrc &&990           !C->doesNotCapture(C->getArgOperandNo(&U));991  });992 993  // If src is captured, then check whether there are any potential uses of994  // src through the captured pointer before the lifetime of src ends, either995  // due to a lifetime.end or a return from the function.996  if (SrcIsCaptured) {997    // Check that dest is not captured before/at the call. We have already998    // checked that src is not captured before it. If either had been captured,999    // then the call might be comparing the argument against the captured dest1000    // or src pointer.1001    Value *DestObj = getUnderlyingObject(cpyDest);1002    if (!isIdentifiedFunctionLocal(DestObj) ||1003        PointerMayBeCapturedBefore(DestObj, /* ReturnCaptures */ true, C, DT,1004                                   /* IncludeI */ true))1005      return false;1006 1007    MemoryLocation SrcLoc =1008        MemoryLocation(srcAlloca, LocationSize::precise(srcSize));1009    for (Instruction &I :1010         make_range(++C->getIterator(), C->getParent()->end())) {1011      // Lifetime of srcAlloca ends at lifetime.end.1012      if (auto *II = dyn_cast<IntrinsicInst>(&I)) {1013        if (II->getIntrinsicID() == Intrinsic::lifetime_end &&1014            II->getArgOperand(0) == srcAlloca)1015          break;1016      }1017 1018      // Lifetime of srcAlloca ends at return.1019      if (isa<ReturnInst>(&I))1020        break;1021 1022      // Ignore the direct read of src in the load.1023      if (&I == cpyLoad)1024        continue;1025 1026      // Check whether this instruction may mod/ref src through the captured1027      // pointer (we have already any direct mod/refs in the loop above).1028      // Also bail if we hit a terminator, as we don't want to scan into other1029      // blocks.1030      if (isModOrRefSet(BAA.getModRefInfo(&I, SrcLoc)) || I.isTerminator())1031        return false;1032    }1033  }1034 1035  // Since we're changing the parameter to the callsite, we need to make sure1036  // that what would be the new parameter dominates the callsite.1037  bool NeedMoveGEP = false;1038  if (!DT->dominates(cpyDest, C)) {1039    // Support moving a constant index GEP before the call.1040    auto *GEP = dyn_cast<GetElementPtrInst>(cpyDest);1041    if (GEP && GEP->hasAllConstantIndices() &&1042        DT->dominates(GEP->getPointerOperand(), C))1043      NeedMoveGEP = true;1044    else1045      return false;1046  }1047 1048  // In addition to knowing that the call does not access src in some1049  // unexpected manner, for example via a global, which we deduce from1050  // the use analysis, we also need to know that it does not sneakily1051  // access dest.  We rely on AA to figure this out for us.1052  MemoryLocation DestWithSrcSize(cpyDest, LocationSize::precise(srcSize));1053  ModRefInfo MR = BAA.getModRefInfo(C, DestWithSrcSize);1054  // If necessary, perform additional analysis.1055  if (isModOrRefSet(MR))1056    MR = BAA.callCapturesBefore(C, DestWithSrcSize, DT);1057  if (isModOrRefSet(MR))1058    return false;1059 1060  // We can't create address space casts here because we don't know if they're1061  // safe for the target.1062  if (cpySrc->getType() != cpyDest->getType())1063    return false;1064  for (unsigned ArgI = 0; ArgI < C->arg_size(); ++ArgI)1065    if (C->getArgOperand(ArgI)->stripPointerCasts() == cpySrc &&1066        cpySrc->getType() != C->getArgOperand(ArgI)->getType())1067      return false;1068 1069  // All the checks have passed, so do the transformation.1070  bool changedArgument = false;1071  for (unsigned ArgI = 0; ArgI < C->arg_size(); ++ArgI)1072    if (C->getArgOperand(ArgI)->stripPointerCasts() == cpySrc) {1073      changedArgument = true;1074      C->setArgOperand(ArgI, cpyDest);1075    }1076 1077  if (!changedArgument)1078    return false;1079 1080  // If the destination wasn't sufficiently aligned then increase its alignment.1081  if (!isDestSufficientlyAligned) {1082    assert(isa<AllocaInst>(cpyDest) && "Can only increase alloca alignment!");1083    cast<AllocaInst>(cpyDest)->setAlignment(srcAlign);1084  }1085 1086  if (NeedMoveGEP) {1087    auto *GEP = dyn_cast<GetElementPtrInst>(cpyDest);1088    GEP->moveBefore(C->getIterator());1089  }1090 1091  if (SkippedLifetimeStart) {1092    SkippedLifetimeStart->moveBefore(C->getIterator());1093    MSSAU->moveBefore(MSSA->getMemoryAccess(SkippedLifetimeStart),1094                      MSSA->getMemoryAccess(C));1095  }1096 1097  combineAAMetadata(C, cpyLoad);1098  if (cpyLoad != cpyStore)1099    combineAAMetadata(C, cpyStore);1100 1101  ++NumCallSlot;1102  return true;1103}1104 1105/// We've found that the (upward scanning) memory dependence of memcpy 'M' is1106/// the memcpy 'MDep'. Try to simplify M to copy from MDep's input if we can.1107bool MemCpyOptPass::processMemCpyMemCpyDependence(MemCpyInst *M,1108                                                  MemCpyInst *MDep,1109                                                  BatchAAResults &BAA) {1110  // We can only optimize non-volatile memcpy's.1111  if (MDep->isVolatile())1112    return false;1113 1114  // If dep instruction is reading from our current input, then it is a noop1115  // transfer and substituting the input won't change this instruction. Just1116  // ignore the input and let someone else zap MDep. This handles cases like:1117  //    memcpy(a <- a)1118  //    memcpy(b <- a)1119  // This also avoids infinite loops.1120  if (BAA.isMustAlias(MDep->getDest(), MDep->getSource()))1121    return false;1122 1123  int64_t MForwardOffset = 0;1124  const DataLayout &DL = M->getModule()->getDataLayout();1125  // We can only transforms memcpy's where the dest of one is the source of the1126  // other, or they have an offset in a range.1127  if (M->getSource() != MDep->getDest()) {1128    std::optional<int64_t> Offset =1129        M->getSource()->getPointerOffsetFrom(MDep->getDest(), DL);1130    if (!Offset || *Offset < 0)1131      return false;1132    MForwardOffset = *Offset;1133  }1134 1135  Value *CopyLength = M->getLength();1136 1137  // The length of the memcpy's must be the same, or the preceding one must be1138  // larger than the following one, or the contents of the overread must be1139  // undefined bytes of a defined size.1140  if (MForwardOffset != 0 || MDep->getLength() != CopyLength) {1141    auto *MDepLen = dyn_cast<ConstantInt>(MDep->getLength());1142    auto *MLen = dyn_cast<ConstantInt>(CopyLength);1143    // This could be converted to a runtime test (%CopyLength =1144    // min(max(0, MDepLen - MForwardOffset), MLen)), but it is1145    // unclear if that is useful1146    if (!MDepLen || !MLen)1147      return false;1148    if (MDepLen->getZExtValue() < MLen->getZExtValue() + MForwardOffset) {1149      if (!overreadUndefContents(MSSA, M, MDep, BAA))1150        return false;1151      if (MDepLen->getZExtValue() <= (uint64_t)MForwardOffset)1152        return false; // Should not reach here (there is obviously no aliasing1153                      // with MDep), so just bail in case it had incomplete info1154                      // somehow1155      CopyLength = ConstantInt::get(CopyLength->getType(),1156                                    MDepLen->getZExtValue() - MForwardOffset);1157    }1158  }1159 1160  IRBuilder<> Builder(M);1161  auto *CopySource = MDep->getSource();1162  Instruction *NewCopySource = nullptr;1163  auto CleanupOnRet = llvm::make_scope_exit([&] {1164    if (NewCopySource && NewCopySource->use_empty())1165      // Safety: It's safe here because we will only allocate more instructions1166      // after finishing all BatchAA queries, but we have to be careful if we1167      // want to do something like this in another place. Then we'd probably1168      // have to delay instruction removal until all transforms on an1169      // instruction finished.1170      eraseInstruction(NewCopySource);1171  });1172  MaybeAlign CopySourceAlign = MDep->getSourceAlign();1173  auto MCopyLoc = MemoryLocation::getForSource(MDep);1174  // Truncate the size of the MDep access to just the bytes read1175  if (MDep->getLength() != CopyLength) {1176    auto *ConstLength = cast<ConstantInt>(CopyLength);1177    MCopyLoc = MCopyLoc.getWithNewSize(1178        LocationSize::precise(ConstLength->getZExtValue()));1179  }1180 1181  // When the forwarding offset is greater than 0, we transform1182  //    memcpy(d1 <- s1)1183  //    memcpy(d2 <- d1+o)1184  // to1185  //    memcpy(d2 <- s1+o)1186  if (MForwardOffset > 0) {1187    // The copy destination of `M` maybe can serve as the source of copying.1188    std::optional<int64_t> MDestOffset =1189        M->getRawDest()->getPointerOffsetFrom(MDep->getRawSource(), DL);1190    if (MDestOffset == MForwardOffset)1191      CopySource = M->getDest();1192    else {1193      CopySource = Builder.CreateInBoundsPtrAdd(1194          CopySource, Builder.getInt64(MForwardOffset));1195      NewCopySource = dyn_cast<Instruction>(CopySource);1196    }1197    // We need to update `MCopyLoc` if an offset exists.1198    MCopyLoc = MCopyLoc.getWithNewPtr(CopySource);1199    if (CopySourceAlign)1200      CopySourceAlign = commonAlignment(*CopySourceAlign, MForwardOffset);1201  }1202 1203  // Verify that the copied-from memory doesn't change in between the two1204  // transfers.  For example, in:1205  //    memcpy(a <- b)1206  //    *b = 42;1207  //    memcpy(c <- a)1208  // It would be invalid to transform the second memcpy into memcpy(c <- b).1209  //1210  // TODO: If the code between M and MDep is transparent to the destination "c",1211  // then we could still perform the xform by moving M up to the first memcpy.1212  if (writtenBetween(MSSA, BAA, MCopyLoc, MSSA->getMemoryAccess(MDep),1213                     MSSA->getMemoryAccess(M)))1214    return false;1215 1216  // No need to create `memcpy(a <- a)`.1217  if (BAA.isMustAlias(M->getDest(), CopySource)) {1218    // Remove the instruction we're replacing.1219    eraseInstruction(M);1220    ++NumMemCpyInstr;1221    return true;1222  }1223 1224  // If the dest of the second might alias the source of the first, then the1225  // source and dest might overlap. In addition, if the source of the first1226  // points to constant memory, they won't overlap by definition. Otherwise, we1227  // still want to eliminate the intermediate value, but we have to generate a1228  // memmove instead of memcpy.1229  bool UseMemMove = false;1230  if (isModSet(BAA.getModRefInfo(M, MemoryLocation::getForSource(MDep)))) {1231    // Don't convert llvm.memcpy.inline into memmove because memmove can be1232    // lowered as a call, and that is not allowed for llvm.memcpy.inline (and1233    // there is no inline version of llvm.memmove)1234    if (M->isForceInlined())1235      return false;1236    UseMemMove = true;1237  }1238 1239  // If all checks passed, then we can transform M.1240  LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy->memcpy src:\n"1241                    << *MDep << '\n'1242                    << *M << '\n');1243 1244  // TODO: Is this worth it if we're creating a less aligned memcpy? For1245  // example we could be moving from movaps -> movq on x86.1246  Instruction *NewM;1247  if (UseMemMove)1248    NewM = Builder.CreateMemMove(M->getDest(), M->getDestAlign(), CopySource,1249                                 CopySourceAlign, CopyLength, M->isVolatile());1250  else if (M->isForceInlined())1251    // llvm.memcpy may be promoted to llvm.memcpy.inline, but the converse is1252    // never allowed since that would allow the latter to be lowered as a call1253    // to an external function.1254    NewM = Builder.CreateMemCpyInline(M->getDest(), M->getDestAlign(),1255                                      CopySource, CopySourceAlign, CopyLength,1256                                      M->isVolatile());1257  else1258    NewM = Builder.CreateMemCpy(M->getDest(), M->getDestAlign(), CopySource,1259                                CopySourceAlign, CopyLength, M->isVolatile());1260 1261  NewM->copyMetadata(*M, LLVMContext::MD_DIAssignID);1262 1263  assert(isa<MemoryDef>(MSSA->getMemoryAccess(M)));1264  auto *LastDef = cast<MemoryDef>(MSSA->getMemoryAccess(M));1265  auto *NewAccess = MSSAU->createMemoryAccessAfter(NewM, nullptr, LastDef);1266  MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);1267 1268  // Remove the instruction we're replacing.1269  eraseInstruction(M);1270  ++NumMemCpyInstr;1271  return true;1272}1273 1274/// We've found that the (upward scanning) memory dependence of \p MemCpy is1275/// \p MemSet.  Try to simplify \p MemSet to only set the trailing bytes that1276/// weren't copied over by \p MemCpy.1277///1278/// In other words, transform:1279/// \code1280///   memset(dst, c, dst_size);1281///   ...1282///   memcpy(dst, src, src_size);1283/// \endcode1284/// into:1285/// \code1286///   ...1287///   memset(dst + src_size, c, dst_size <= src_size ? 0 : dst_size - src_size);1288///   memcpy(dst, src, src_size);1289/// \endcode1290///1291/// The memset is sunk to just before the memcpy to ensure that src_size is1292/// present when emitting the simplified memset.1293bool MemCpyOptPass::processMemSetMemCpyDependence(MemCpyInst *MemCpy,1294                                                  MemSetInst *MemSet,1295                                                  BatchAAResults &BAA) {1296  // We can only transform memset/memcpy with the same destination.1297  if (!BAA.isMustAlias(MemSet->getDest(), MemCpy->getDest()))1298    return false;1299 1300  // Don't perform the transform if src_size may be zero. In that case, the1301  // transform is essentially a complex no-op and may lead to an infinite1302  // loop if BasicAA is smart enough to understand that dst and dst + src_size1303  // are still MustAlias after the transform.1304  Value *SrcSize = MemCpy->getLength();1305  if (!isKnownNonZero(SrcSize,1306                      SimplifyQuery(MemCpy->getDataLayout(), DT, AC, MemCpy)))1307    return false;1308 1309  // Check that src and dst of the memcpy aren't the same. While memcpy1310  // operands cannot partially overlap, exact equality is allowed.1311  if (isModSet(BAA.getModRefInfo(MemCpy, MemoryLocation::getForSource(MemCpy))))1312    return false;1313 1314  // We know that dst up to src_size is not written. We now need to make sure1315  // that dst up to dst_size is not accessed. (If we did not move the memset,1316  // checking for reads would be sufficient.)1317  if (accessedBetween(BAA, MemoryLocation::getForDest(MemSet),1318                      MSSA->getMemoryAccess(MemSet),1319                      MSSA->getMemoryAccess(MemCpy)))1320    return false;1321 1322  // Use the same i8* dest as the memcpy, killing the memset dest if different.1323  Value *Dest = MemCpy->getRawDest();1324  Value *DestSize = MemSet->getLength();1325 1326  if (mayBeVisibleThroughUnwinding(Dest, MemSet, MemCpy))1327    return false;1328 1329  // If the sizes are the same, simply drop the memset instead of generating1330  // a replacement with zero size.1331  if (DestSize == SrcSize) {1332    eraseInstruction(MemSet);1333    return true;1334  }1335 1336  // By default, create an unaligned memset.1337  Align Alignment = Align(1);1338  // If Dest is aligned, and SrcSize is constant, use the minimum alignment1339  // of the sum.1340  const Align DestAlign = std::max(MemSet->getDestAlign().valueOrOne(),1341                                   MemCpy->getDestAlign().valueOrOne());1342  if (DestAlign > 1)1343    if (auto *SrcSizeC = dyn_cast<ConstantInt>(SrcSize))1344      Alignment = commonAlignment(DestAlign, SrcSizeC->getZExtValue());1345 1346  IRBuilder<> Builder(MemCpy);1347 1348  // Preserve the debug location of the old memset for the code emitted here1349  // related to the new memset. This is correct according to the rules in1350  // https://llvm.org/docs/HowToUpdateDebugInfo.html about "when to preserve an1351  // instruction location", given that we move the memset within the basic1352  // block.1353  assert(MemSet->getParent() == MemCpy->getParent() &&1354         "Preserving debug location based on moving memset within BB.");1355  Builder.SetCurrentDebugLocation(MemSet->getDebugLoc());1356 1357  // If the sizes have different types, zext the smaller one.1358  if (DestSize->getType() != SrcSize->getType()) {1359    if (DestSize->getType()->getIntegerBitWidth() >1360        SrcSize->getType()->getIntegerBitWidth())1361      SrcSize = Builder.CreateZExt(SrcSize, DestSize->getType());1362    else1363      DestSize = Builder.CreateZExt(DestSize, SrcSize->getType());1364  }1365 1366  Value *Ule = Builder.CreateICmpULE(DestSize, SrcSize);1367  Value *SizeDiff = Builder.CreateSub(DestSize, SrcSize);1368  Value *MemsetLen = Builder.CreateSelect(1369      Ule, ConstantInt::getNullValue(DestSize->getType()), SizeDiff);1370  // FIXME (#167968): we could explore estimating the branch_weights based on1371  // value profiling data about the 2 sizes.1372  if (auto *SI = dyn_cast<SelectInst>(MemsetLen))1373    setExplicitlyUnknownBranchWeightsIfProfiled(*SI, DEBUG_TYPE);1374  Instruction *NewMemSet =1375      Builder.CreateMemSet(Builder.CreatePtrAdd(Dest, SrcSize),1376                           MemSet->getOperand(1), MemsetLen, Alignment);1377 1378  assert(isa<MemoryDef>(MSSA->getMemoryAccess(MemCpy)) &&1379         "MemCpy must be a MemoryDef");1380  // The new memset is inserted before the memcpy, and it is known that the1381  // memcpy's defining access is the memset about to be removed.1382  auto *LastDef = cast<MemoryDef>(MSSA->getMemoryAccess(MemCpy));1383  auto *NewAccess =1384      MSSAU->createMemoryAccessBefore(NewMemSet, nullptr, LastDef);1385  MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);1386 1387  eraseInstruction(MemSet);1388  return true;1389}1390 1391/// Determine whether the pointer V had only undefined content (due to Def),1392/// either because it was freshly alloca'd or started its lifetime.1393static bool hasUndefContents(MemorySSA *MSSA, BatchAAResults &AA, Value *V,1394                             MemoryDef *Def) {1395  if (MSSA->isLiveOnEntryDef(Def))1396    return isa<AllocaInst>(getUnderlyingObject(V));1397 1398  if (auto *II = dyn_cast_or_null<IntrinsicInst>(Def->getMemoryInst()))1399    if (II->getIntrinsicID() == Intrinsic::lifetime_start)1400      if (auto *Alloca = dyn_cast<AllocaInst>(getUnderlyingObject(V)))1401        return II->getArgOperand(0) == Alloca;1402 1403  return false;1404}1405 1406// If the memcpy is larger than the previous, but the memory was undef prior to1407// that, we can just ignore the tail. Technically we're only interested in the1408// bytes from 0..MemSrcOffset and MemSrcLength+MemSrcOffset..CopySize here, but1409// as we can't easily represent this location (hasUndefContents uses mustAlias1410// which cannot deal with offsets), we use the full 0..CopySize range.1411static bool overreadUndefContents(MemorySSA *MSSA, MemCpyInst *MemCpy,1412                                  MemIntrinsic *MemSrc, BatchAAResults &BAA) {1413  MemoryLocation MemCpyLoc = MemoryLocation::getForSource(MemCpy);1414  MemoryUseOrDef *MemSrcAccess = MSSA->getMemoryAccess(MemSrc);1415  MemoryAccess *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(1416      MemSrcAccess->getDefiningAccess(), MemCpyLoc, BAA);1417  if (auto *MD = dyn_cast<MemoryDef>(Clobber))1418    if (hasUndefContents(MSSA, BAA, MemCpy->getSource(), MD))1419      return true;1420  return false;1421}1422 1423/// Transform memcpy to memset when its source was just memset.1424/// In other words, turn:1425/// \code1426///   memset(dst1, c, dst1_size);1427///   memcpy(dst2, dst1, dst2_size);1428/// \endcode1429/// into:1430/// \code1431///   memset(dst1, c, dst1_size);1432///   memset(dst2, c, dst2_size);1433/// \endcode1434/// When dst2_size <= dst1_size.1435bool MemCpyOptPass::performMemCpyToMemSetOptzn(MemCpyInst *MemCpy,1436                                               MemSetInst *MemSet,1437                                               BatchAAResults &BAA) {1438  Value *MemSetSize = MemSet->getLength();1439  Value *CopySize = MemCpy->getLength();1440 1441  int64_t MOffset = 0;1442  const DataLayout &DL = MemCpy->getModule()->getDataLayout();1443  // We can only transforms memcpy's where the dest of one is the source of the1444  // other, or they have a known offset.1445  if (MemCpy->getSource() != MemSet->getDest()) {1446    std::optional<int64_t> Offset =1447        MemCpy->getSource()->getPointerOffsetFrom(MemSet->getDest(), DL);1448    if (!Offset || *Offset < 0)1449      return false;1450    MOffset = *Offset;1451  }1452 1453  if (MOffset != 0 || MemSetSize != CopySize) {1454    // Make sure the memcpy doesn't read any more than what the memset wrote,1455    // other than undef. Don't worry about sizes larger than i64.1456    auto *CMemSetSize = dyn_cast<ConstantInt>(MemSetSize);1457    auto *CCopySize = dyn_cast<ConstantInt>(CopySize);1458    if (!CMemSetSize || !CCopySize ||1459        CCopySize->getZExtValue() + MOffset > CMemSetSize->getZExtValue()) {1460      if (!overreadUndefContents(MSSA, MemCpy, MemSet, BAA))1461        return false;1462 1463      if (CMemSetSize && CCopySize) {1464        // If both have constant sizes and offsets, clip the memcpy to the1465        // bounds of the memset if applicable.1466        assert(CCopySize->getZExtValue() + MOffset >1467               CMemSetSize->getZExtValue());1468        if (MOffset == 0)1469          CopySize = MemSetSize;1470        else1471          CopySize =1472              ConstantInt::get(CopySize->getType(),1473                               CMemSetSize->getZExtValue() <= (uint64_t)MOffset1474                                   ? 01475                                   : CMemSetSize->getZExtValue() - MOffset);1476      }1477    }1478  }1479 1480  IRBuilder<> Builder(MemCpy);1481  Instruction *NewM =1482      Builder.CreateMemSet(MemCpy->getRawDest(), MemSet->getOperand(1),1483                           CopySize, MemCpy->getDestAlign());1484  auto *LastDef = cast<MemoryDef>(MSSA->getMemoryAccess(MemCpy));1485  auto *NewAccess = MSSAU->createMemoryAccessAfter(NewM, nullptr, LastDef);1486  MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);1487 1488  return true;1489}1490 1491// Attempts to optimize the pattern whereby memory is copied from an alloca to1492// another alloca, where the two allocas don't have conflicting mod/ref. If1493// successful, the two allocas can be merged into one and the transfer can be1494// deleted. This pattern is generated frequently in Rust, due to the ubiquity of1495// move operations in that language.1496//1497// Once we determine that the optimization is safe to perform, we replace all1498// uses of the destination alloca with the source alloca. We also "shrink wrap"1499// the lifetime markers of the single merged alloca to before the first use1500// and after the last use. Note that the "shrink wrapping" procedure is a safe1501// transformation only because we restrict the scope of this optimization to1502// allocas that aren't captured.1503bool MemCpyOptPass::performStackMoveOptzn(Instruction *Load, Instruction *Store,1504                                          AllocaInst *DestAlloca,1505                                          AllocaInst *SrcAlloca, TypeSize Size,1506                                          BatchAAResults &BAA) {1507  LLVM_DEBUG(dbgs() << "Stack Move: Attempting to optimize:\n"1508                    << *Store << "\n");1509 1510  // Make sure the two allocas are in the same address space.1511  if (SrcAlloca->getAddressSpace() != DestAlloca->getAddressSpace()) {1512    LLVM_DEBUG(dbgs() << "Stack Move: Address space mismatch\n");1513    return false;1514  }1515 1516  // Check that copy is full with static size.1517  const DataLayout &DL = DestAlloca->getDataLayout();1518  std::optional<TypeSize> SrcSize = SrcAlloca->getAllocationSize(DL);1519  if (!SrcSize || Size != *SrcSize) {1520    LLVM_DEBUG(dbgs() << "Stack Move: Source alloca size mismatch\n");1521    return false;1522  }1523  std::optional<TypeSize> DestSize = DestAlloca->getAllocationSize(DL);1524  if (!DestSize || Size != *DestSize) {1525    LLVM_DEBUG(dbgs() << "Stack Move: Destination alloca size mismatch\n");1526    return false;1527  }1528 1529  if (!SrcAlloca->isStaticAlloca() || !DestAlloca->isStaticAlloca())1530    return false;1531 1532  // Check that src and dest are never captured, unescaped allocas. Also1533  // find the nearest common dominator and postdominator for all users in1534  // order to shrink wrap the lifetimes, and instructions with noalias metadata1535  // to remove them.1536 1537  SmallVector<Instruction *, 4> LifetimeMarkers;1538  SmallPtrSet<Instruction *, 4> AAMetadataInstrs;1539  bool SrcNotDom = false;1540 1541  auto CaptureTrackingWithModRef =1542      [&](Instruction *AI, function_ref<bool(Instruction *)> ModRefCallback,1543          bool &AddressCaptured) -> bool {1544    SmallVector<Instruction *, 8> Worklist;1545    Worklist.push_back(AI);1546    unsigned MaxUsesToExplore = getDefaultMaxUsesToExploreForCaptureTracking();1547    Worklist.reserve(MaxUsesToExplore);1548    SmallPtrSet<const Use *, 20> Visited;1549    while (!Worklist.empty()) {1550      Instruction *I = Worklist.pop_back_val();1551      for (const Use &U : I->uses()) {1552        auto *UI = cast<Instruction>(U.getUser());1553        // If any use that isn't dominated by SrcAlloca exists, we move src1554        // alloca to the entry before the transformation.1555        if (!DT->dominates(SrcAlloca, UI))1556          SrcNotDom = true;1557 1558        if (Visited.size() >= MaxUsesToExplore) {1559          LLVM_DEBUG(1560              dbgs()1561              << "Stack Move: Exceeded max uses to see ModRef, bailing\n");1562          return false;1563        }1564        if (!Visited.insert(&U).second)1565          continue;1566        UseCaptureInfo CI = DetermineUseCaptureKind(U, AI);1567        if (capturesAnyProvenance(CI.UseCC))1568          return false;1569        AddressCaptured |= capturesAddress(CI.UseCC);1570 1571        if (UI->mayReadOrWriteMemory()) {1572          if (UI->isLifetimeStartOrEnd()) {1573            // We note the locations of these intrinsic calls so that we can1574            // delete them later if the optimization succeeds, this is safe1575            // since both llvm.lifetime.start and llvm.lifetime.end intrinsics1576            // practically fill all the bytes of the alloca with an undefined1577            // value, although conceptually marked as alive/dead.1578            LifetimeMarkers.push_back(UI);1579            continue;1580          }1581          AAMetadataInstrs.insert(UI);1582 1583          if (!ModRefCallback(UI))1584            return false;1585        }1586 1587        if (capturesAnything(CI.ResultCC)) {1588          Worklist.push_back(UI);1589          continue;1590        }1591      }1592    }1593    return true;1594  };1595 1596  // Check that dest has no Mod/Ref, from the alloca to the Store. And collect1597  // modref inst for the reachability check.1598  ModRefInfo DestModRef = ModRefInfo::NoModRef;1599  MemoryLocation DestLoc(DestAlloca, LocationSize::precise(Size));1600  SmallVector<BasicBlock *, 8> ReachabilityWorklist;1601  auto DestModRefCallback = [&](Instruction *UI) -> bool {1602    // We don't care about the store itself.1603    if (UI == Store)1604      return true;1605    ModRefInfo Res = BAA.getModRefInfo(UI, DestLoc);1606    DestModRef |= Res;1607    if (isModOrRefSet(Res)) {1608      // Instructions reachability checks.1609      // FIXME: adding the Instruction version isPotentiallyReachableFromMany on1610      // lib/Analysis/CFG.cpp (currently only for BasicBlocks) might be helpful.1611      if (UI->getParent() == Store->getParent()) {1612        // The same block case is special because it's the only time we're1613        // looking within a single block to see which instruction comes first.1614        // Once we start looking at multiple blocks, the first instruction of1615        // the block is reachable, so we only need to determine reachability1616        // between whole blocks.1617        BasicBlock *BB = UI->getParent();1618 1619        // If A comes before B, then B is definitively reachable from A.1620        if (UI->comesBefore(Store))1621          return false;1622 1623        // If the user's parent block is entry, no predecessor exists.1624        if (BB->isEntryBlock())1625          return true;1626 1627        // Otherwise, continue doing the normal per-BB CFG walk.1628        ReachabilityWorklist.append(succ_begin(BB), succ_end(BB));1629      } else {1630        ReachabilityWorklist.push_back(UI->getParent());1631      }1632    }1633    return true;1634  };1635 1636  bool DestAddressCaptured = false;1637  if (!CaptureTrackingWithModRef(DestAlloca, DestModRefCallback,1638                                 DestAddressCaptured))1639    return false;1640  // Bailout if Dest may have any ModRef before Store.1641  if (!ReachabilityWorklist.empty() &&1642      isPotentiallyReachableFromMany(ReachabilityWorklist, Store->getParent(),1643                                     nullptr, DT, nullptr))1644    return false;1645 1646  // Check that, from after the Load to the end of the BB,1647  //   - if the dest has any Mod, src has no Ref, and1648  //   - if the dest has any Ref, src has no Mod except full-sized lifetimes.1649  MemoryLocation SrcLoc(SrcAlloca, LocationSize::precise(Size));1650 1651  auto SrcModRefCallback = [&](Instruction *UI) -> bool {1652    // Any ModRef post-dominated by Load doesn't matter, also Load and Store1653    // themselves can be ignored.1654    if (PDT->dominates(Load, UI) || UI == Load || UI == Store)1655      return true;1656    ModRefInfo Res = BAA.getModRefInfo(UI, SrcLoc);1657    if ((isModSet(DestModRef) && isRefSet(Res)) ||1658        (isRefSet(DestModRef) && isModSet(Res)))1659      return false;1660 1661    return true;1662  };1663 1664  bool SrcAddressCaptured = false;1665  if (!CaptureTrackingWithModRef(SrcAlloca, SrcModRefCallback,1666                                 SrcAddressCaptured))1667    return false;1668 1669  // If both the source and destination address are captured, the fact that they1670  // are no longer two separate allocations may be observed.1671  if (DestAddressCaptured && SrcAddressCaptured)1672    return false;1673 1674  // We can do the transformation. First, move the SrcAlloca to the start of the1675  // BB.1676  if (SrcNotDom)1677    SrcAlloca->moveBefore(*SrcAlloca->getParent(),1678                          SrcAlloca->getParent()->getFirstInsertionPt());1679  // Align the allocas appropriately.1680  SrcAlloca->setAlignment(1681      std::max(SrcAlloca->getAlign(), DestAlloca->getAlign()));1682 1683  // Merge the two allocas.1684  DestAlloca->replaceAllUsesWith(SrcAlloca);1685  eraseInstruction(DestAlloca);1686 1687  // Drop metadata on the source alloca.1688  SrcAlloca->dropUnknownNonDebugMetadata();1689 1690  // TODO: Reconstruct merged lifetime markers.1691  // Remove all other lifetime markers. if the original lifetime intrinsics1692  // exists.1693  if (!LifetimeMarkers.empty()) {1694    for (Instruction *I : LifetimeMarkers)1695      eraseInstruction(I);1696  }1697 1698  // As this transformation can cause memory accesses that didn't previously1699  // alias to begin to alias one another, we remove !alias.scope, !noalias,1700  // !tbaa and !tbaa_struct metadata from any uses of either alloca.1701  // This is conservative, but more precision doesn't seem worthwhile1702  // right now.1703  for (Instruction *I : AAMetadataInstrs) {1704    I->setMetadata(LLVMContext::MD_alias_scope, nullptr);1705    I->setMetadata(LLVMContext::MD_noalias, nullptr);1706    I->setMetadata(LLVMContext::MD_tbaa, nullptr);1707    I->setMetadata(LLVMContext::MD_tbaa_struct, nullptr);1708  }1709 1710  LLVM_DEBUG(dbgs() << "Stack Move: Performed staack-move optimization\n");1711  NumStackMove++;1712  return true;1713}1714 1715static bool isZeroSize(Value *Size) {1716  if (auto *I = dyn_cast<Instruction>(Size))1717    if (auto *Res = simplifyInstruction(I, I->getDataLayout()))1718      Size = Res;1719  // Treat undef/poison size like zero.1720  if (auto *C = dyn_cast<Constant>(Size))1721    return isa<UndefValue>(C) || C->isNullValue();1722  return false;1723}1724 1725/// Perform simplification of memcpy's.  If we have memcpy A1726/// which copies X to Y, and memcpy B which copies Y to Z, then we can rewrite1727/// B to be a memcpy from X to Z (or potentially a memmove, depending on1728/// circumstances). This allows later passes to remove the first memcpy1729/// altogether.1730bool MemCpyOptPass::processMemCpy(MemCpyInst *M, BasicBlock::iterator &BBI) {1731  // We can only optimize non-volatile memcpy's.1732  if (M->isVolatile())1733    return false;1734 1735  // If the source and destination of the memcpy are the same, then zap it.1736  if (M->getSource() == M->getDest()) {1737    ++BBI;1738    eraseInstruction(M);1739    return true;1740  }1741 1742  // If the size is zero, remove the memcpy.1743  if (isZeroSize(M->getLength())) {1744    ++BBI;1745    eraseInstruction(M);1746    return true;1747  }1748 1749  MemoryUseOrDef *MA = MSSA->getMemoryAccess(M);1750  if (!MA)1751    // Degenerate case: memcpy marked as not accessing memory.1752    return false;1753 1754  // If copying from a constant, try to turn the memcpy into a memset.1755  if (auto *GV = dyn_cast<GlobalVariable>(M->getSource()))1756    if (GV->isConstant() && GV->hasDefinitiveInitializer())1757      if (Value *ByteVal = isBytewiseValue(GV->getInitializer(),1758                                           M->getDataLayout())) {1759        IRBuilder<> Builder(M);1760        Instruction *NewM = Builder.CreateMemSet(1761            M->getRawDest(), ByteVal, M->getLength(), M->getDestAlign(), false);1762        auto *LastDef = cast<MemoryDef>(MA);1763        auto *NewAccess =1764            MSSAU->createMemoryAccessAfter(NewM, nullptr, LastDef);1765        MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);1766 1767        eraseInstruction(M);1768        ++NumCpyToSet;1769        return true;1770      }1771 1772  BatchAAResults BAA(*AA, EEA);1773  // FIXME: Not using getClobberingMemoryAccess() here due to PR54682.1774  MemoryAccess *AnyClobber = MA->getDefiningAccess();1775  MemoryLocation DestLoc = MemoryLocation::getForDest(M);1776  const MemoryAccess *DestClobber =1777      MSSA->getWalker()->getClobberingMemoryAccess(AnyClobber, DestLoc, BAA);1778 1779  // Try to turn a partially redundant memset + memcpy into1780  // smaller memset + memcpy.  We don't need the memcpy size for this.1781  // The memcpy must post-dom the memset, so limit this to the same basic1782  // block. A non-local generalization is likely not worthwhile.1783  if (auto *MD = dyn_cast<MemoryDef>(DestClobber))1784    if (auto *MDep = dyn_cast_or_null<MemSetInst>(MD->getMemoryInst()))1785      if (DestClobber->getBlock() == M->getParent())1786        if (processMemSetMemCpyDependence(M, MDep, BAA))1787          return true;1788 1789  MemoryAccess *SrcClobber = MSSA->getWalker()->getClobberingMemoryAccess(1790      AnyClobber, MemoryLocation::getForSource(M), BAA);1791 1792  // There are five possible optimizations we can do for memcpy:1793  //   a) memcpy-memcpy xform which exposes redundance for DSE.1794  //   b) call-memcpy xform for return slot optimization.1795  //   c) memcpy from freshly alloca'd space or space that has just started1796  //      its lifetime copies undefined data, and we can therefore eliminate1797  //      the memcpy in favor of the data that was already at the destination.1798  //   d) memcpy from a just-memset'd source can be turned into memset.1799  //   e) elimination of memcpy via stack-move optimization.1800  if (auto *MD = dyn_cast<MemoryDef>(SrcClobber)) {1801    if (Instruction *MI = MD->getMemoryInst()) {1802      if (auto *CopySize = dyn_cast<ConstantInt>(M->getLength())) {1803        if (auto *C = dyn_cast<CallInst>(MI)) {1804          if (performCallSlotOptzn(M, M, M->getDest(), M->getSource(),1805                                   TypeSize::getFixed(CopySize->getZExtValue()),1806                                   M->getDestAlign().valueOrOne(), BAA,1807                                   [C]() -> CallInst * { return C; })) {1808            LLVM_DEBUG(dbgs() << "Performed call slot optimization:\n"1809                              << "    call: " << *C << "\n"1810                              << "    memcpy: " << *M << "\n");1811            eraseInstruction(M);1812            ++NumMemCpyInstr;1813            return true;1814          }1815        }1816      }1817      if (auto *MDep = dyn_cast<MemCpyInst>(MI))1818        if (processMemCpyMemCpyDependence(M, MDep, BAA))1819          return true;1820      if (auto *MDep = dyn_cast<MemSetInst>(MI)) {1821        if (performMemCpyToMemSetOptzn(M, MDep, BAA)) {1822          LLVM_DEBUG(dbgs() << "Converted memcpy to memset\n");1823          eraseInstruction(M);1824          ++NumCpyToSet;1825          return true;1826        }1827      }1828    }1829 1830    if (hasUndefContents(MSSA, BAA, M->getSource(), MD)) {1831      LLVM_DEBUG(dbgs() << "Removed memcpy from undef\n");1832      eraseInstruction(M);1833      ++NumMemCpyInstr;1834      return true;1835    }1836  }1837 1838  // If the transfer is from a stack slot to a stack slot, then we may be able1839  // to perform the stack-move optimization. See the comments in1840  // performStackMoveOptzn() for more details.1841  auto *DestAlloca = dyn_cast<AllocaInst>(M->getDest());1842  if (!DestAlloca)1843    return false;1844  auto *SrcAlloca = dyn_cast<AllocaInst>(M->getSource());1845  if (!SrcAlloca)1846    return false;1847  ConstantInt *Len = dyn_cast<ConstantInt>(M->getLength());1848  if (Len == nullptr)1849    return false;1850  if (performStackMoveOptzn(M, M, DestAlloca, SrcAlloca,1851                            TypeSize::getFixed(Len->getZExtValue()), BAA)) {1852    // Avoid invalidating the iterator.1853    BBI = M->getNextNode()->getIterator();1854    eraseInstruction(M);1855    ++NumMemCpyInstr;1856    return true;1857  }1858 1859  return false;1860}1861 1862/// Memmove calls with overlapping src/dest buffers that come after a memset may1863/// be removed.1864bool MemCpyOptPass::isMemMoveMemSetDependency(MemMoveInst *M) {1865  const auto &DL = M->getDataLayout();1866  MemoryUseOrDef *MemMoveAccess = MSSA->getMemoryAccess(M);1867  if (!MemMoveAccess)1868    return false;1869 1870  // The memmove is of form memmove(x, x + A, B).1871  MemoryLocation SourceLoc = MemoryLocation::getForSource(M);1872  auto *MemMoveSourceOp = M->getSource();1873  auto *Source = dyn_cast<GEPOperator>(MemMoveSourceOp);1874  if (!Source)1875    return false;1876 1877  APInt Offset(DL.getIndexTypeSizeInBits(Source->getType()), 0);1878  LocationSize MemMoveLocSize = SourceLoc.Size;1879  if (Source->getPointerOperand() != M->getDest() ||1880      !MemMoveLocSize.hasValue() ||1881      !Source->accumulateConstantOffset(DL, Offset) || Offset.isNegative()) {1882    return false;1883  }1884 1885  uint64_t MemMoveSize = MemMoveLocSize.getValue();1886  LocationSize TotalSize =1887      LocationSize::precise(Offset.getZExtValue() + MemMoveSize);1888  MemoryLocation CombinedLoc(M->getDest(), TotalSize);1889 1890  // The first dominating clobbering MemoryAccess for the combined location1891  // needs to be a memset.1892  BatchAAResults BAA(*AA);1893  MemoryAccess *FirstDef = MemMoveAccess->getDefiningAccess();1894  auto *DestClobber = dyn_cast<MemoryDef>(1895      MSSA->getWalker()->getClobberingMemoryAccess(FirstDef, CombinedLoc, BAA));1896  if (!DestClobber)1897    return false;1898 1899  auto *MS = dyn_cast_or_null<MemSetInst>(DestClobber->getMemoryInst());1900  if (!MS)1901    return false;1902 1903  // Memset length must be sufficiently large.1904  auto *MemSetLength = dyn_cast<ConstantInt>(MS->getLength());1905  if (!MemSetLength || MemSetLength->getZExtValue() < MemMoveSize)1906    return false;1907 1908  // The destination buffer must have been memset'd.1909  if (!BAA.isMustAlias(MS->getDest(), M->getDest()))1910    return false;1911 1912  return true;1913}1914 1915/// Transforms memmove calls to memcpy calls when the src/dst are guaranteed1916/// not to alias.1917bool MemCpyOptPass::processMemMove(MemMoveInst *M, BasicBlock::iterator &BBI) {1918  // See if the source could be modified by this memmove potentially.1919  if (isModSet(AA->getModRefInfo(M, MemoryLocation::getForSource(M)))) {1920    // On the off-chance the memmove clobbers src with previously memset'd1921    // bytes, the memmove may be redundant.1922    if (!M->isVolatile() && isMemMoveMemSetDependency(M)) {1923      LLVM_DEBUG(dbgs() << "Removed redundant memmove.\n");1924      ++BBI;1925      eraseInstruction(M);1926      ++NumMemMoveInstr;1927      return true;1928    }1929    return false;1930  }1931 1932  LLVM_DEBUG(dbgs() << "MemCpyOptPass: Optimizing memmove -> memcpy: " << *M1933                    << "\n");1934 1935  // If not, then we know we can transform this.1936  Type *ArgTys[3] = {M->getRawDest()->getType(), M->getRawSource()->getType(),1937                     M->getLength()->getType()};1938  M->setCalledFunction(Intrinsic::getOrInsertDeclaration(1939      M->getModule(), Intrinsic::memcpy, ArgTys));1940 1941  // For MemorySSA nothing really changes (except that memcpy may imply stricter1942  // aliasing guarantees).1943 1944  ++NumMoveToCpy;1945  return true;1946}1947 1948/// This is called on every byval argument in call sites.1949bool MemCpyOptPass::processByValArgument(CallBase &CB, unsigned ArgNo) {1950  const DataLayout &DL = CB.getDataLayout();1951  // Find out what feeds this byval argument.1952  Value *ByValArg = CB.getArgOperand(ArgNo);1953  Type *ByValTy = CB.getParamByValType(ArgNo);1954  TypeSize ByValSize = DL.getTypeAllocSize(ByValTy);1955  MemoryLocation Loc(ByValArg, LocationSize::precise(ByValSize));1956  MemoryUseOrDef *CallAccess = MSSA->getMemoryAccess(&CB);1957  if (!CallAccess)1958    return false;1959  MemCpyInst *MDep = nullptr;1960  BatchAAResults BAA(*AA, EEA);1961  MemoryAccess *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(1962      CallAccess->getDefiningAccess(), Loc, BAA);1963  if (auto *MD = dyn_cast<MemoryDef>(Clobber))1964    MDep = dyn_cast_or_null<MemCpyInst>(MD->getMemoryInst());1965 1966  // If the byval argument isn't fed by a memcpy, ignore it.  If it is fed by1967  // a memcpy, see if we can byval from the source of the memcpy instead of the1968  // result.1969  if (!MDep || MDep->isVolatile() ||1970      ByValArg->stripPointerCasts() != MDep->getDest())1971    return false;1972 1973  // The length of the memcpy must be larger or equal to the size of the byval.1974  auto *C1 = dyn_cast<ConstantInt>(MDep->getLength());1975  if (!C1 || !TypeSize::isKnownGE(1976                 TypeSize::getFixed(C1->getValue().getZExtValue()), ByValSize))1977    return false;1978 1979  // Get the alignment of the byval.  If the call doesn't specify the alignment,1980  // then it is some target specific value that we can't know.1981  MaybeAlign ByValAlign = CB.getParamAlign(ArgNo);1982  if (!ByValAlign)1983    return false;1984 1985  // If it is greater than the memcpy, then we check to see if we can force the1986  // source of the memcpy to the alignment we need.  If we fail, we bail out.1987  MaybeAlign MemDepAlign = MDep->getSourceAlign();1988  if ((!MemDepAlign || *MemDepAlign < *ByValAlign) &&1989      getOrEnforceKnownAlignment(MDep->getSource(), ByValAlign, DL, &CB, AC,1990                                 DT) < *ByValAlign)1991    return false;1992 1993  // The type of the memcpy source must match the byval argument1994  if (MDep->getSource()->getType() != ByValArg->getType())1995    return false;1996 1997  // Verify that the copied-from memory doesn't change in between the memcpy and1998  // the byval call.1999  //    memcpy(a <- b)2000  //    *b = 42;2001  //    foo(*a)2002  // It would be invalid to transform the second memcpy into foo(*b).2003  if (writtenBetween(MSSA, BAA, MemoryLocation::getForSource(MDep),2004                     MSSA->getMemoryAccess(MDep), CallAccess))2005    return false;2006 2007  LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy to byval:\n"2008                    << "  " << *MDep << "\n"2009                    << "  " << CB << "\n");2010 2011  // Otherwise we're good!  Update the byval argument.2012  combineAAMetadata(&CB, MDep);2013  CB.setArgOperand(ArgNo, MDep->getSource());2014  ++NumMemCpyInstr;2015  return true;2016}2017 2018/// This is called on memcpy dest pointer arguments attributed as immutable2019/// during call. Try to use memcpy source directly if all of the following2020/// conditions are satisfied.2021/// 1. The memcpy dst is neither modified during the call nor captured by the2022/// call.2023/// 2. The memcpy dst is an alloca with known alignment & size.2024///     2-1. The memcpy length == the alloca size which ensures that the new2025///     pointer is dereferenceable for the required range2026///     2-2. The src pointer has alignment >= the alloca alignment or can be2027///     enforced so.2028/// 3. The memcpy dst and src is not modified between the memcpy and the call.2029/// (if MSSA clobber check is safe.)2030/// 4. The memcpy src is not modified during the call. (ModRef check shows no2031/// Mod.)2032bool MemCpyOptPass::processImmutArgument(CallBase &CB, unsigned ArgNo) {2033  BatchAAResults BAA(*AA, EEA);2034  Value *ImmutArg = CB.getArgOperand(ArgNo);2035 2036  // 1. Ensure passed argument is immutable during call.2037  if (!CB.doesNotCapture(ArgNo))2038    return false;2039 2040  // We know that the argument is readonly at this point, but the function2041  // might still modify the same memory through a different pointer. Exclude2042  // this either via noalias, or alias analysis.2043  if (!CB.paramHasAttr(ArgNo, Attribute::NoAlias) &&2044      isModSet(2045          BAA.getModRefInfo(&CB, MemoryLocation::getBeforeOrAfter(ImmutArg))))2046    return false;2047 2048  const DataLayout &DL = CB.getDataLayout();2049 2050  // 2. Check that arg is alloca2051  // TODO: Even if the arg gets back to branches, we can remove memcpy if all2052  // the alloca alignments can be enforced to source alignment.2053  auto *AI = dyn_cast<AllocaInst>(ImmutArg->stripPointerCasts());2054  if (!AI)2055    return false;2056 2057  std::optional<TypeSize> AllocaSize = AI->getAllocationSize(DL);2058  // Can't handle unknown size alloca.2059  // (e.g. Variable Length Array, Scalable Vector)2060  if (!AllocaSize || AllocaSize->isScalable())2061    return false;2062  MemoryLocation Loc(ImmutArg, LocationSize::precise(*AllocaSize));2063  MemoryUseOrDef *CallAccess = MSSA->getMemoryAccess(&CB);2064  if (!CallAccess)2065    return false;2066 2067  MemCpyInst *MDep = nullptr;2068  MemoryAccess *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(2069      CallAccess->getDefiningAccess(), Loc, BAA);2070  if (auto *MD = dyn_cast<MemoryDef>(Clobber))2071    MDep = dyn_cast_or_null<MemCpyInst>(MD->getMemoryInst());2072 2073  // If the immut argument isn't fed by a memcpy, ignore it.  If it is fed by2074  // a memcpy, check that the arg equals the memcpy dest.2075  if (!MDep || MDep->isVolatile() || AI != MDep->getDest())2076    return false;2077 2078  // The type of the memcpy source must match the immut argument2079  if (MDep->getSource()->getType() != ImmutArg->getType())2080    return false;2081 2082  // 2-1. The length of the memcpy must be equal to the size of the alloca.2083  auto *MDepLen = dyn_cast<ConstantInt>(MDep->getLength());2084  if (!MDepLen || AllocaSize != MDepLen->getValue())2085    return false;2086 2087  // 2-2. the memcpy source align must be larger than or equal the alloca's2088  // align. If not so, we check to see if we can force the source of the memcpy2089  // to the alignment we need. If we fail, we bail out.2090  Align MemDepAlign = MDep->getSourceAlign().valueOrOne();2091  Align AllocaAlign = AI->getAlign();2092  if (MemDepAlign < AllocaAlign &&2093      getOrEnforceKnownAlignment(MDep->getSource(), AllocaAlign, DL, &CB, AC,2094                                 DT) < AllocaAlign)2095    return false;2096 2097  // 3. Verify that the source doesn't change in between the memcpy and2098  // the call.2099  //    memcpy(a <- b)2100  //    *b = 42;2101  //    foo(*a)2102  // It would be invalid to transform the second memcpy into foo(*b).2103  if (writtenBetween(MSSA, BAA, MemoryLocation::getForSource(MDep),2104                     MSSA->getMemoryAccess(MDep), CallAccess))2105    return false;2106 2107  // 4. The memcpy src must not be modified during the call.2108  if (isModSet(BAA.getModRefInfo(&CB, MemoryLocation::getForSource(MDep))))2109    return false;2110 2111  LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy to Immut src:\n"2112                    << "  " << *MDep << "\n"2113                    << "  " << CB << "\n");2114 2115  // Otherwise we're good!  Update the immut argument.2116  combineAAMetadata(&CB, MDep);2117  CB.setArgOperand(ArgNo, MDep->getSource());2118  ++NumMemCpyInstr;2119  return true;2120}2121 2122/// Executes one iteration of MemCpyOptPass.2123bool MemCpyOptPass::iterateOnFunction(Function &F) {2124  bool MadeChange = false;2125 2126  // Walk all instruction in the function.2127  for (BasicBlock &BB : F) {2128    // Skip unreachable blocks. For example processStore assumes that an2129    // instruction in a BB can't be dominated by a later instruction in the2130    // same BB (which is a scenario that can happen for an unreachable BB that2131    // has itself as a predecessor).2132    if (!DT->isReachableFromEntry(&BB))2133      continue;2134 2135    for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) {2136      // Avoid invalidating the iterator.2137      Instruction *I = &*BI++;2138 2139      bool RepeatInstruction = false;2140 2141      if (auto *SI = dyn_cast<StoreInst>(I))2142        MadeChange |= processStore(SI, BI);2143      else if (auto *M = dyn_cast<MemSetInst>(I))2144        RepeatInstruction = processMemSet(M, BI);2145      else if (auto *M = dyn_cast<MemCpyInst>(I))2146        RepeatInstruction = processMemCpy(M, BI);2147      else if (auto *M = dyn_cast<MemMoveInst>(I))2148        RepeatInstruction = processMemMove(M, BI);2149      else if (auto *CB = dyn_cast<CallBase>(I)) {2150        for (unsigned i = 0, e = CB->arg_size(); i != e; ++i) {2151          if (CB->isByValArgument(i))2152            MadeChange |= processByValArgument(*CB, i);2153          else if (CB->onlyReadsMemory(i))2154            MadeChange |= processImmutArgument(*CB, i);2155        }2156      }2157 2158      // Reprocess the instruction if desired.2159      if (RepeatInstruction) {2160        if (BI != BB.begin())2161          --BI;2162        MadeChange = true;2163      }2164    }2165  }2166 2167  return MadeChange;2168}2169 2170PreservedAnalyses MemCpyOptPass::run(Function &F, FunctionAnalysisManager &AM) {2171  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);2172  auto *AA = &AM.getResult<AAManager>(F);2173  auto *AC = &AM.getResult<AssumptionAnalysis>(F);2174  auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);2175  auto *PDT = &AM.getResult<PostDominatorTreeAnalysis>(F);2176  auto *MSSA = &AM.getResult<MemorySSAAnalysis>(F);2177 2178  bool MadeChange = runImpl(F, &TLI, AA, AC, DT, PDT, &MSSA->getMSSA());2179  if (!MadeChange)2180    return PreservedAnalyses::all();2181 2182  PreservedAnalyses PA;2183  PA.preserveSet<CFGAnalyses>();2184  PA.preserve<MemorySSAAnalysis>();2185  return PA;2186}2187 2188bool MemCpyOptPass::runImpl(Function &F, TargetLibraryInfo *TLI_,2189                            AliasAnalysis *AA_, AssumptionCache *AC_,2190                            DominatorTree *DT_, PostDominatorTree *PDT_,2191                            MemorySSA *MSSA_) {2192  bool MadeChange = false;2193  TLI = TLI_;2194  AA = AA_;2195  AC = AC_;2196  DT = DT_;2197  PDT = PDT_;2198  MSSA = MSSA_;2199  MemorySSAUpdater MSSAU_(MSSA_);2200  MSSAU = &MSSAU_;2201  EarliestEscapeAnalysis EEA_(*DT);2202  EEA = &EEA_;2203 2204  while (true) {2205    if (!iterateOnFunction(F))2206      break;2207    MadeChange = true;2208  }2209 2210  if (VerifyMemorySSA)2211    MSSA_->verifyMemorySSA();2212 2213  return MadeChange;2214}2215