xref: /llvm-project-15.0.7/llvm/lib/Analysis/MemorySSAUpdater.cpp (revision ef2cdfe3)

//===-- MemorySSAUpdater.cpp - Memory SSA Updater--------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------===//
//
// This file implements the MemorySSAUpdater class.
//
//===----------------------------------------------------------------===//
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/IteratedDominanceFrontier.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/FormattedStream.h"
#include <algorithm>

#define DEBUG_TYPE "memoryssa"
using namespace llvm;

// This is the marker algorithm from "Simple and Efficient Construction of
// Static Single Assignment Form"
// The simple, non-marker algorithm places phi nodes at any join
// Here, we place markers, and only place phi nodes if they end up necessary.
// They are only necessary if they break a cycle (IE we recursively visit
// ourselves again), or we discover, while getting the value of the operands,
// that there are two or more definitions needing to be merged.
// This still will leave non-minimal form in the case of irreducible control
// flow, where phi nodes may be in cycles with themselves, but unnecessary.
MemoryAccess *MemorySSAUpdater::getPreviousDefRecursive(
    BasicBlock *BB,
    DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
  // First, do a cache lookup. Without this cache, certain CFG structures
  // (like a series of if statements) take exponential time to visit.
  auto Cached = CachedPreviousDef.find(BB);
  if (Cached != CachedPreviousDef.end())
    return Cached->second;

  // If this method is called from an unreachable block, return LoE.
  if (!MSSA->DT->isReachableFromEntry(BB))
    return MSSA->getLiveOnEntryDef();

  if (BasicBlock *Pred = BB->getUniquePredecessor()) {
    VisitedBlocks.insert(BB);
    // Single predecessor case, just recurse, we can only have one definition.
    MemoryAccess *Result = getPreviousDefFromEnd(Pred, CachedPreviousDef);
    CachedPreviousDef.insert({BB, Result});
    return Result;
  }

  if (VisitedBlocks.count(BB)) {
    // We hit our node again, meaning we had a cycle, we must insert a phi
    // node to break it so we have an operand. The only case this will
    // insert useless phis is if we have irreducible control flow.
    MemoryAccess *Result = MSSA->createMemoryPhi(BB);
    CachedPreviousDef.insert({BB, Result});
    return Result;
  }

  if (VisitedBlocks.insert(BB).second) {
    // Mark us visited so we can detect a cycle
    SmallVector<TrackingVH<MemoryAccess>, 8> PhiOps;

    // Recurse to get the values in our predecessors for placement of a
    // potential phi node. This will insert phi nodes if we cycle in order to
    // break the cycle and have an operand.
    bool UniqueIncomingAccess = true;
    MemoryAccess *SingleAccess = nullptr;
    for (auto *Pred : predecessors(BB)) {
      if (MSSA->DT->isReachableFromEntry(Pred)) {
        auto *IncomingAccess = getPreviousDefFromEnd(Pred, CachedPreviousDef);
        if (!SingleAccess)
          SingleAccess = IncomingAccess;
        else if (IncomingAccess != SingleAccess)
          UniqueIncomingAccess = false;
        PhiOps.push_back(IncomingAccess);
      } else
        PhiOps.push_back(MSSA->getLiveOnEntryDef());
    }

    // Now try to simplify the ops to avoid placing a phi.
    // This may return null if we never created a phi yet, that's okay
    MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MSSA->getMemoryAccess(BB));

    // See if we can avoid the phi by simplifying it.
    auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);
    // If we couldn't simplify, we may have to create a phi
    if (Result == Phi && UniqueIncomingAccess && SingleAccess) {
      // A concrete Phi only exists if we created an empty one to break a cycle.
      if (Phi) {
        assert(Phi->operands().empty() && "Expected empty Phi");
        Phi->replaceAllUsesWith(SingleAccess);
        removeMemoryAccess(Phi);
      }
      Result = SingleAccess;
    } else if (Result == Phi && !(UniqueIncomingAccess && SingleAccess)) {
      if (!Phi)
        Phi = MSSA->createMemoryPhi(BB);

      // See if the existing phi operands match what we need.
      // Unlike normal SSA, we only allow one phi node per block, so we can't just
      // create a new one.
      if (Phi->getNumOperands() != 0) {
        // FIXME: Figure out whether this is dead code and if so remove it.
        if (!std::equal(Phi->op_begin(), Phi->op_end(), PhiOps.begin())) {
          // These will have been filled in by the recursive read we did above.
          llvm::copy(PhiOps, Phi->op_begin());
          std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());
        }
      } else {
        unsigned i = 0;
        for (auto *Pred : predecessors(BB))
          Phi->addIncoming(&*PhiOps[i++], Pred);
        InsertedPHIs.push_back(Phi);
      }
      Result = Phi;
    }

    // Set ourselves up for the next variable by resetting visited state.
    VisitedBlocks.erase(BB);
    CachedPreviousDef.insert({BB, Result});
    return Result;
  }
  llvm_unreachable("Should have hit one of the three cases above");
}

// This starts at the memory access, and goes backwards in the block to find the
// previous definition. If a definition is not found the block of the access,
// it continues globally, creating phi nodes to ensure we have a single
// definition.
MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) {
  if (auto *LocalResult = getPreviousDefInBlock(MA))
    return LocalResult;
  DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;
  return getPreviousDefRecursive(MA->getBlock(), CachedPreviousDef);
}

// This starts at the memory access, and goes backwards in the block to the find
// the previous definition. If the definition is not found in the block of the
// access, it returns nullptr.
MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) {
  auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock());

  // It's possible there are no defs, or we got handed the first def to start.
  if (Defs) {
    // If this is a def, we can just use the def iterators.
    if (!isa<MemoryUse>(MA)) {
      auto Iter = MA->getReverseDefsIterator();
      ++Iter;
      if (Iter != Defs->rend())
        return &*Iter;
    } else {
      // Otherwise, have to walk the all access iterator.
      auto End = MSSA->getWritableBlockAccesses(MA->getBlock())->rend();
      for (auto &U : make_range(++MA->getReverseIterator(), End))
        if (!isa<MemoryUse>(U))
          return cast<MemoryAccess>(&U);
      // Note that if MA comes before Defs->begin(), we won't hit a def.
      return nullptr;
    }
  }
  return nullptr;
}

// This starts at the end of block
MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(
    BasicBlock *BB,
    DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
  auto *Defs = MSSA->getWritableBlockDefs(BB);

  if (Defs) {
    CachedPreviousDef.insert({BB, &*Defs->rbegin()});
    return &*Defs->rbegin();
  }

  return getPreviousDefRecursive(BB, CachedPreviousDef);
}
// Recurse over a set of phi uses to eliminate the trivial ones
MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) {
  if (!Phi)
    return nullptr;
  TrackingVH<MemoryAccess> Res(Phi);
  SmallVector<TrackingVH<Value>, 8> Uses;
  std::copy(Phi->user_begin(), Phi->user_end(), std::back_inserter(Uses));
  for (auto &U : Uses)
    if (MemoryPhi *UsePhi = dyn_cast<MemoryPhi>(&*U))
      tryRemoveTrivialPhi(UsePhi);
  return Res;
}

// Eliminate trivial phis
// Phis are trivial if they are defined either by themselves, or all the same
// argument.
// IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c)
// We recursively try to remove them.
MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi) {
  assert(Phi && "Can only remove concrete Phi.");
  auto OperRange = Phi->operands();
  return tryRemoveTrivialPhi(Phi, OperRange);
}
template <class RangeType>
MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
                                                    RangeType &Operands) {
  // Bail out on non-opt Phis.
  if (NonOptPhis.count(Phi))
    return Phi;

  // Detect equal or self arguments
  MemoryAccess *Same = nullptr;
  for (auto &Op : Operands) {
    // If the same or self, good so far
    if (Op == Phi || Op == Same)
      continue;
    // not the same, return the phi since it's not eliminatable by us
    if (Same)
      return Phi;
    Same = cast<MemoryAccess>(&*Op);
  }
  // Never found a non-self reference, the phi is undef
  if (Same == nullptr)
    return MSSA->getLiveOnEntryDef();
  if (Phi) {
    Phi->replaceAllUsesWith(Same);
    removeMemoryAccess(Phi);
  }

  // We should only end up recursing in case we replaced something, in which
  // case, we may have made other Phis trivial.
  return recursePhi(Same);
}

void MemorySSAUpdater::insertUse(MemoryUse *MU, bool RenameUses) {
  InsertedPHIs.clear();
  MU->setDefiningAccess(getPreviousDef(MU));

  // In cases without unreachable blocks, because uses do not create new
  // may-defs, there are only two cases:
  // 1. There was a def already below us, and therefore, we should not have
  // created a phi node because it was already needed for the def.
  //
  // 2. There is no def below us, and therefore, there is no extra renaming work
  // to do.

  // In cases with unreachable blocks, where the unnecessary Phis were
  // optimized out, adding the Use may re-insert those Phis. Hence, when
  // inserting Uses outside of the MSSA creation process, and new Phis were
  // added, rename all uses if we are asked.

  if (!RenameUses && !InsertedPHIs.empty()) {
    auto *Defs = MSSA->getBlockDefs(MU->getBlock());
    (void)Defs;
    assert((!Defs || (++Defs->begin() == Defs->end())) &&
           "Block may have only a Phi or no defs");
  }

  if (RenameUses && InsertedPHIs.size()) {
    SmallPtrSet<BasicBlock *, 16> Visited;
    BasicBlock *StartBlock = MU->getBlock();

    if (auto *Defs = MSSA->getWritableBlockDefs(StartBlock)) {
      MemoryAccess *FirstDef = &*Defs->begin();
      // Convert to incoming value if it's a memorydef. A phi *is* already an
      // incoming value.
      if (auto *MD = dyn_cast<MemoryDef>(FirstDef))
        FirstDef = MD->getDefiningAccess();

      MSSA->renamePass(MU->getBlock(), FirstDef, Visited);
    }
    // We just inserted a phi into this block, so the incoming value will
    // become the phi anyway, so it does not matter what we pass.
    for (auto &MP : InsertedPHIs)
      if (MemoryPhi *Phi = cast_or_null<MemoryPhi>(MP))
        MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
  }
}

// Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef.
static void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB,
                                      MemoryAccess *NewDef) {
  // Replace any operand with us an incoming block with the new defining
  // access.
  int i = MP->getBasicBlockIndex(BB);
  assert(i != -1 && "Should have found the basic block in the phi");
  // We can't just compare i against getNumOperands since one is signed and the
  // other not. So use it to index into the block iterator.
  for (auto BBIter = MP->block_begin() + i; BBIter != MP->block_end();
       ++BBIter) {
    if (*BBIter != BB)
      break;
    MP->setIncomingValue(i, NewDef);
    ++i;
  }
}

// A brief description of the algorithm:
// First, we compute what should define the new def, using the SSA
// construction algorithm.
// Then, we update the defs below us (and any new phi nodes) in the graph to
// point to the correct new defs, to ensure we only have one variable, and no
// disconnected stores.
void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {
  InsertedPHIs.clear();

  // See if we had a local def, and if not, go hunting.
  MemoryAccess *DefBefore = getPreviousDef(MD);
  bool DefBeforeSameBlock = false;
  if (DefBefore->getBlock() == MD->getBlock() &&
      !(isa<MemoryPhi>(DefBefore) &&
        llvm::is_contained(InsertedPHIs, DefBefore)))
    DefBeforeSameBlock = true;

  // There is a def before us, which means we can replace any store/phi uses
  // of that thing with us, since we are in the way of whatever was there
  // before.
  // We now define that def's memorydefs and memoryphis
  if (DefBeforeSameBlock) {
    DefBefore->replaceUsesWithIf(MD, [MD](Use &U) {
      // Leave the MemoryUses alone.
      // Also make sure we skip ourselves to avoid self references.
      User *Usr = U.getUser();
      return !isa<MemoryUse>(Usr) && Usr != MD;
      // Defs are automatically unoptimized when the user is set to MD below,
      // because the isOptimized() call will fail to find the same ID.
    });
  }

  // and that def is now our defining access.
  MD->setDefiningAccess(DefBefore);

  SmallVector<WeakVH, 8> FixupList(InsertedPHIs.begin(), InsertedPHIs.end());

  SmallSet<WeakVH, 8> ExistingPhis;

  // Remember the index where we may insert new phis.
  unsigned NewPhiIndex = InsertedPHIs.size();
  if (!DefBeforeSameBlock) {
    // If there was a local def before us, we must have the same effect it
    // did. Because every may-def is the same, any phis/etc we would create, it
    // would also have created.  If there was no local def before us, we
    // performed a global update, and have to search all successors and make
    // sure we update the first def in each of them (following all paths until
    // we hit the first def along each path). This may also insert phi nodes.
    // TODO: There are other cases we can skip this work, such as when we have a
    // single successor, and only used a straight line of single pred blocks
    // backwards to find the def.  To make that work, we'd have to track whether
    // getDefRecursive only ever used the single predecessor case.  These types
    // of paths also only exist in between CFG simplifications.

    // If this is the first def in the block and this insert is in an arbitrary
    // place, compute IDF and place phis.
    SmallPtrSet<BasicBlock *, 2> DefiningBlocks;

    // If this is the last Def in the block, we may need additional Phis.
    // Compute IDF in all cases, as renaming needs to be done even when MD is
    // not the last access, because it can introduce a new access past which a
    // previous access was optimized; that access needs to be reoptimized.
    DefiningBlocks.insert(MD->getBlock());
    for (const auto &VH : InsertedPHIs)
      if (const auto *RealPHI = cast_or_null<MemoryPhi>(VH))
        DefiningBlocks.insert(RealPHI->getBlock());
    ForwardIDFCalculator IDFs(*MSSA->DT);
    SmallVector<BasicBlock *, 32> IDFBlocks;
    IDFs.setDefiningBlocks(DefiningBlocks);
    IDFs.calculate(IDFBlocks);
    SmallVector<AssertingVH<MemoryPhi>, 4> NewInsertedPHIs;
    for (auto *BBIDF : IDFBlocks) {
      auto *MPhi = MSSA->getMemoryAccess(BBIDF);
      if (!MPhi) {
        MPhi = MSSA->createMemoryPhi(BBIDF);
        NewInsertedPHIs.push_back(MPhi);
      } else {
        ExistingPhis.insert(MPhi);
      }
      // Add the phis created into the IDF blocks to NonOptPhis, so they are not
      // optimized out as trivial by the call to getPreviousDefFromEnd below.
      // Once they are complete, all these Phis are added to the FixupList, and
      // removed from NonOptPhis inside fixupDefs(). Existing Phis in IDF may
      // need fixing as well, and potentially be trivial before this insertion,
      // hence add all IDF Phis. See PR43044.
      NonOptPhis.insert(MPhi);
    }
    for (auto &MPhi : NewInsertedPHIs) {
      auto *BBIDF = MPhi->getBlock();
      for (auto *Pred : predecessors(BBIDF)) {
        DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;
        MPhi->addIncoming(getPreviousDefFromEnd(Pred, CachedPreviousDef), Pred);
      }
    }

    // Re-take the index where we're adding the new phis, because the above call
    // to getPreviousDefFromEnd, may have inserted into InsertedPHIs.
    NewPhiIndex = InsertedPHIs.size();
    for (auto &MPhi : NewInsertedPHIs) {
      InsertedPHIs.push_back(&*MPhi);
      FixupList.push_back(&*MPhi);
    }

    FixupList.push_back(MD);
  }

  // Remember the index where we stopped inserting new phis above, since the
  // fixupDefs call in the loop below may insert more, that are already minimal.
  unsigned NewPhiIndexEnd = InsertedPHIs.size();

  while (!FixupList.empty()) {
    unsigned StartingPHISize = InsertedPHIs.size();
    fixupDefs(FixupList);
    FixupList.clear();
    // Put any new phis on the fixup list, and process them
    FixupList.append(InsertedPHIs.begin() + StartingPHISize, InsertedPHIs.end());
  }

  // Optimize potentially non-minimal phis added in this method.
  unsigned NewPhiSize = NewPhiIndexEnd - NewPhiIndex;
  if (NewPhiSize)
    tryRemoveTrivialPhis(ArrayRef<WeakVH>(&InsertedPHIs[NewPhiIndex], NewPhiSize));

  // Now that all fixups are done, rename all uses if we are asked. Skip
  // renaming for defs in unreachable blocks.
  BasicBlock *StartBlock = MD->getBlock();
  if (RenameUses && MSSA->getDomTree().getNode(StartBlock)) {
    SmallPtrSet<BasicBlock *, 16> Visited;
    // We are guaranteed there is a def in the block, because we just got it
    // handed to us in this function.
    MemoryAccess *FirstDef = &*MSSA->getWritableBlockDefs(StartBlock)->begin();
    // Convert to incoming value if it's a memorydef. A phi *is* already an
    // incoming value.
    if (auto *MD = dyn_cast<MemoryDef>(FirstDef))
      FirstDef = MD->getDefiningAccess();

    MSSA->renamePass(MD->getBlock(), FirstDef, Visited);
    // We just inserted a phi into this block, so the incoming value will become
    // the phi anyway, so it does not matter what we pass.
    for (auto &MP : InsertedPHIs) {
      MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MP);
      if (Phi)
        MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
    }
    // Existing Phi blocks may need renaming too, if an access was previously
    // optimized and the inserted Defs "covers" the Optimized value.
    for (auto &MP : ExistingPhis) {
      MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MP);
      if (Phi)
        MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
    }
  }
}

void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<WeakVH> &Vars) {
  SmallPtrSet<const BasicBlock *, 8> Seen;
  SmallVector<const BasicBlock *, 16> Worklist;
  for (auto &Var : Vars) {
    MemoryAccess *NewDef = dyn_cast_or_null<MemoryAccess>(Var);
    if (!NewDef)
      continue;
    // First, see if there is a local def after the operand.
    auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock());
    auto DefIter = NewDef->getDefsIterator();

    // The temporary Phi is being fixed, unmark it for not to optimize.
    if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(NewDef))
      NonOptPhis.erase(Phi);

    // If there is a local def after us, we only have to rename that.
    if (++DefIter != Defs->end()) {
      cast<MemoryDef>(DefIter)->setDefiningAccess(NewDef);
      continue;
    }

    // Otherwise, we need to search down through the CFG.
    // For each of our successors, handle it directly if their is a phi, or
    // place on the fixup worklist.
    for (const auto *S : successors(NewDef->getBlock())) {
      if (auto *MP = MSSA->getMemoryAccess(S))
        setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef);
      else
        Worklist.push_back(S);
    }

    while (!Worklist.empty()) {
      const BasicBlock *FixupBlock = Worklist.back();
      Worklist.pop_back();

      // Get the first def in the block that isn't a phi node.
      if (auto *Defs = MSSA->getWritableBlockDefs(FixupBlock)) {
        auto *FirstDef = &*Defs->begin();
        // The loop above and below should have taken care of phi nodes
        assert(!isa<MemoryPhi>(FirstDef) &&
               "Should have already handled phi nodes!");
        // We are now this def's defining access, make sure we actually dominate
        // it
        assert(MSSA->dominates(NewDef, FirstDef) &&
               "Should have dominated the new access");

        // This may insert new phi nodes, because we are not guaranteed the
        // block we are processing has a single pred, and depending where the
        // store was inserted, it may require phi nodes below it.
        cast<MemoryDef>(FirstDef)->setDefiningAccess(getPreviousDef(FirstDef));
        return;
      }
      // We didn't find a def, so we must continue.
      for (const auto *S : successors(FixupBlock)) {
        // If there is a phi node, handle it.
        // Otherwise, put the block on the worklist
        if (auto *MP = MSSA->getMemoryAccess(S))
          setMemoryPhiValueForBlock(MP, FixupBlock, NewDef);
        else {
          // If we cycle, we should have ended up at a phi node that we already
          // processed.  FIXME: Double check this
          if (!Seen.insert(S).second)
            continue;
          Worklist.push_back(S);
        }
      }
    }
  }
}

void MemorySSAUpdater::removeEdge(BasicBlock *From, BasicBlock *To) {
  if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
    MPhi->unorderedDeleteIncomingBlock(From);
    tryRemoveTrivialPhi(MPhi);
  }
}

void MemorySSAUpdater::removeDuplicatePhiEdgesBetween(const BasicBlock *From,
                                                      const BasicBlock *To) {
  if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
    bool Found = false;
    MPhi->unorderedDeleteIncomingIf([&](const MemoryAccess *, BasicBlock *B) {
      if (From != B)
        return false;
      if (Found)
        return true;
      Found = true;
      return false;
    });
    tryRemoveTrivialPhi(MPhi);
  }
}

/// If all arguments of a MemoryPHI are defined by the same incoming
/// argument, return that argument.
static MemoryAccess *onlySingleValue(MemoryPhi *MP) {
  MemoryAccess *MA = nullptr;

  for (auto &Arg : MP->operands()) {
    if (!MA)
      MA = cast<MemoryAccess>(Arg);
    else if (MA != Arg)
      return nullptr;
  }
  return MA;
}

static MemoryAccess *getNewDefiningAccessForClone(MemoryAccess *MA,
                                                  const ValueToValueMapTy &VMap,
                                                  PhiToDefMap &MPhiMap,
                                                  bool CloneWasSimplified,
                                                  MemorySSA *MSSA) {
  MemoryAccess *InsnDefining = MA;
  if (MemoryDef *DefMUD = dyn_cast<MemoryDef>(InsnDefining)) {
    if (!MSSA->isLiveOnEntryDef(DefMUD)) {
      Instruction *DefMUDI = DefMUD->getMemoryInst();
      assert(DefMUDI && "Found MemoryUseOrDef with no Instruction.");
      if (Instruction *NewDefMUDI =
              cast_or_null<Instruction>(VMap.lookup(DefMUDI))) {
        InsnDefining = MSSA->getMemoryAccess(NewDefMUDI);
        if (!CloneWasSimplified)
          assert(InsnDefining && "Defining instruction cannot be nullptr.");
        else if (!InsnDefining || isa<MemoryUse>(InsnDefining)) {
          // The clone was simplified, it's no longer a MemoryDef, look up.
          auto DefIt = DefMUD->getDefsIterator();
          // Since simplified clones only occur in single block cloning, a
          // previous definition must exist, otherwise NewDefMUDI would not
          // have been found in VMap.
          assert(DefIt != MSSA->getBlockDefs(DefMUD->getBlock())->begin() &&
                 "Previous def must exist");
          InsnDefining = getNewDefiningAccessForClone(
              &*(--DefIt), VMap, MPhiMap, CloneWasSimplified, MSSA);
        }
      }
    }
  } else {
    MemoryPhi *DefPhi = cast<MemoryPhi>(InsnDefining);
    if (MemoryAccess *NewDefPhi = MPhiMap.lookup(DefPhi))
      InsnDefining = NewDefPhi;
  }
  assert(InsnDefining && "Defining instruction cannot be nullptr.");
  return InsnDefining;
}

void MemorySSAUpdater::cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
                                        const ValueToValueMapTy &VMap,
                                        PhiToDefMap &MPhiMap,
                                        bool CloneWasSimplified) {
  const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
  if (!Acc)
    return;
  for (const MemoryAccess &MA : *Acc) {
    if (const MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&MA)) {
      Instruction *Insn = MUD->getMemoryInst();
      // Entry does not exist if the clone of the block did not clone all
      // instructions. This occurs in LoopRotate when cloning instructions
      // from the old header to the old preheader. The cloned instruction may
      // also be a simplified Value, not an Instruction (see LoopRotate).
      // Also in LoopRotate, even when it's an instruction, due to it being
      // simplified, it may be a Use rather than a Def, so we cannot use MUD as
      // template. Calls coming from updateForClonedBlockIntoPred, ensure this.
      if (Instruction *NewInsn =
              dyn_cast_or_null<Instruction>(VMap.lookup(Insn))) {
        MemoryAccess *NewUseOrDef = MSSA->createDefinedAccess(
            NewInsn,
            getNewDefiningAccessForClone(MUD->getDefiningAccess(), VMap,
                                         MPhiMap, CloneWasSimplified, MSSA),
            /*Template=*/CloneWasSimplified ? nullptr : MUD,
            /*CreationMustSucceed=*/CloneWasSimplified ? false : true);
        if (NewUseOrDef)
          MSSA->insertIntoListsForBlock(NewUseOrDef, NewBB, MemorySSA::End);
      }
    }
  }
}

void MemorySSAUpdater::updatePhisWhenInsertingUniqueBackedgeBlock(
    BasicBlock *Header, BasicBlock *Preheader, BasicBlock *BEBlock) {
  auto *MPhi = MSSA->getMemoryAccess(Header);
  if (!MPhi)
    return;

  // Create phi node in the backedge block and populate it with the same
  // incoming values as MPhi. Skip incoming values coming from Preheader.
  auto *NewMPhi = MSSA->createMemoryPhi(BEBlock);
  bool HasUniqueIncomingValue = true;
  MemoryAccess *UniqueValue = nullptr;
  for (unsigned I = 0, E = MPhi->getNumIncomingValues(); I != E; ++I) {
    BasicBlock *IBB = MPhi->getIncomingBlock(I);
    MemoryAccess *IV = MPhi->getIncomingValue(I);
    if (IBB != Preheader) {
      NewMPhi->addIncoming(IV, IBB);
      if (HasUniqueIncomingValue) {
        if (!UniqueValue)
          UniqueValue = IV;
        else if (UniqueValue != IV)
          HasUniqueIncomingValue = false;
      }
    }
  }

  // Update incoming edges into MPhi. Remove all but the incoming edge from
  // Preheader. Add an edge from NewMPhi
  auto *AccFromPreheader = MPhi->getIncomingValueForBlock(Preheader);
  MPhi->setIncomingValue(0, AccFromPreheader);
  MPhi->setIncomingBlock(0, Preheader);
  for (unsigned I = MPhi->getNumIncomingValues() - 1; I >= 1; --I)
    MPhi->unorderedDeleteIncoming(I);
  MPhi->addIncoming(NewMPhi, BEBlock);

  // If NewMPhi is a trivial phi, remove it. Its use in the header MPhi will be
  // replaced with the unique value.
  tryRemoveTrivialPhi(NewMPhi);
}

void MemorySSAUpdater::updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
                                           ArrayRef<BasicBlock *> ExitBlocks,
                                           const ValueToValueMapTy &VMap,
                                           bool IgnoreIncomingWithNoClones) {
  PhiToDefMap MPhiMap;

  auto FixPhiIncomingValues = [&](MemoryPhi *Phi, MemoryPhi *NewPhi) {
    assert(Phi && NewPhi && "Invalid Phi nodes.");
    BasicBlock *NewPhiBB = NewPhi->getBlock();
    SmallPtrSet<BasicBlock *, 4> NewPhiBBPreds(pred_begin(NewPhiBB),
                                               pred_end(NewPhiBB));
    for (unsigned It = 0, E = Phi->getNumIncomingValues(); It < E; ++It) {
      MemoryAccess *IncomingAccess = Phi->getIncomingValue(It);
      BasicBlock *IncBB = Phi->getIncomingBlock(It);

      if (BasicBlock *NewIncBB = cast_or_null<BasicBlock>(VMap.lookup(IncBB)))
        IncBB = NewIncBB;
      else if (IgnoreIncomingWithNoClones)
        continue;

      // Now we have IncBB, and will need to add incoming from it to NewPhi.

      // If IncBB is not a predecessor of NewPhiBB, then do not add it.
      // NewPhiBB was cloned without that edge.
      if (!NewPhiBBPreds.count(IncBB))
        continue;

      // Determine incoming value and add it as incoming from IncBB.
      if (MemoryUseOrDef *IncMUD = dyn_cast<MemoryUseOrDef>(IncomingAccess)) {
        if (!MSSA->isLiveOnEntryDef(IncMUD)) {
          Instruction *IncI = IncMUD->getMemoryInst();
          assert(IncI && "Found MemoryUseOrDef with no Instruction.");
          if (Instruction *NewIncI =
                  cast_or_null<Instruction>(VMap.lookup(IncI))) {
            IncMUD = MSSA->getMemoryAccess(NewIncI);
            assert(IncMUD &&
                   "MemoryUseOrDef cannot be null, all preds processed.");
          }
        }
        NewPhi->addIncoming(IncMUD, IncBB);
      } else {
        MemoryPhi *IncPhi = cast<MemoryPhi>(IncomingAccess);
        if (MemoryAccess *NewDefPhi = MPhiMap.lookup(IncPhi))
          NewPhi->addIncoming(NewDefPhi, IncBB);
        else
          NewPhi->addIncoming(IncPhi, IncBB);
      }
    }
    if (auto *SingleAccess = onlySingleValue(NewPhi)) {
      MPhiMap[Phi] = SingleAccess;
      removeMemoryAccess(NewPhi);
    }
  };

  auto ProcessBlock = [&](BasicBlock *BB) {
    BasicBlock *NewBlock = cast_or_null<BasicBlock>(VMap.lookup(BB));
    if (!NewBlock)
      return;

    assert(!MSSA->getWritableBlockAccesses(NewBlock) &&
           "Cloned block should have no accesses");

    // Add MemoryPhi.
    if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) {
      MemoryPhi *NewPhi = MSSA->createMemoryPhi(NewBlock);
      MPhiMap[MPhi] = NewPhi;
    }
    // Update Uses and Defs.
    cloneUsesAndDefs(BB, NewBlock, VMap, MPhiMap);
  };

  for (auto BB : llvm::concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
    ProcessBlock(BB);

  for (auto BB : llvm::concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
    if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
      if (MemoryAccess *NewPhi = MPhiMap.lookup(MPhi))
        FixPhiIncomingValues(MPhi, cast<MemoryPhi>(NewPhi));
}

void MemorySSAUpdater::updateForClonedBlockIntoPred(
    BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM) {
  // All defs/phis from outside BB that are used in BB, are valid uses in P1.
  // Since those defs/phis must have dominated BB, and also dominate P1.
  // Defs from BB being used in BB will be replaced with the cloned defs from
  // VM. The uses of BB's Phi (if it exists) in BB will be replaced by the
  // incoming def into the Phi from P1.
  // Instructions cloned into the predecessor are in practice sometimes
  // simplified, so disable the use of the template, and create an access from
  // scratch.
  PhiToDefMap MPhiMap;
  if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
    MPhiMap[MPhi] = MPhi->getIncomingValueForBlock(P1);
  cloneUsesAndDefs(BB, P1, VM, MPhiMap, /*CloneWasSimplified=*/true);
}

template <typename Iter>
void MemorySSAUpdater::privateUpdateExitBlocksForClonedLoop(
    ArrayRef<BasicBlock *> ExitBlocks, Iter ValuesBegin, Iter ValuesEnd,
    DominatorTree &DT) {
  SmallVector<CFGUpdate, 4> Updates;
  // Update/insert phis in all successors of exit blocks.
  for (auto *Exit : ExitBlocks)
    for (const ValueToValueMapTy *VMap : make_range(ValuesBegin, ValuesEnd))
      if (BasicBlock *NewExit = cast_or_null<BasicBlock>(VMap->lookup(Exit))) {
        BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
        Updates.push_back({DT.Insert, NewExit, ExitSucc});
      }
  applyInsertUpdates(Updates, DT);
}

void MemorySSAUpdater::updateExitBlocksForClonedLoop(
    ArrayRef<BasicBlock *> ExitBlocks, const ValueToValueMapTy &VMap,
    DominatorTree &DT) {
  const ValueToValueMapTy *const Arr[] = {&VMap};
  privateUpdateExitBlocksForClonedLoop(ExitBlocks, std::begin(Arr),
                                       std::end(Arr), DT);
}

void MemorySSAUpdater::updateExitBlocksForClonedLoop(
    ArrayRef<BasicBlock *> ExitBlocks,
    ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT) {
  auto GetPtr = [&](const std::unique_ptr<ValueToValueMapTy> &I) {
    return I.get();
  };
  using MappedIteratorType =
      mapped_iterator<const std::unique_ptr<ValueToValueMapTy> *,
                      decltype(GetPtr)>;
  auto MapBegin = MappedIteratorType(VMaps.begin(), GetPtr);
  auto MapEnd = MappedIteratorType(VMaps.end(), GetPtr);
  privateUpdateExitBlocksForClonedLoop(ExitBlocks, MapBegin, MapEnd, DT);
}

void MemorySSAUpdater::applyUpdates(ArrayRef<CFGUpdate> Updates,
                                    DominatorTree &DT, bool UpdateDT) {
  SmallVector<CFGUpdate, 4> DeleteUpdates;
  SmallVector<CFGUpdate, 4> RevDeleteUpdates;
  SmallVector<CFGUpdate, 4> InsertUpdates;
  for (auto &Update : Updates) {
    if (Update.getKind() == DT.Insert)
      InsertUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
    else {
      DeleteUpdates.push_back({DT.Delete, Update.getFrom(), Update.getTo()});
      RevDeleteUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
    }
  }

  if (!DeleteUpdates.empty()) {
    if (!InsertUpdates.empty()) {
      if (!UpdateDT) {
        SmallVector<CFGUpdate, 0> Empty;
        // Deletes are reversed applied, because this CFGView is pretending the
        // deletes did not happen yet, hence the edges still exist.
        DT.applyUpdates(Empty, RevDeleteUpdates);
      } else {
        // Apply all updates, with the RevDeleteUpdates as PostCFGView.
        DT.applyUpdates(Updates, RevDeleteUpdates);
      }

      // Note: the MSSA update below doesn't distinguish between a GD with
      // (RevDelete,false) and (Delete, true), but this matters for the DT
      // updates above; for "children" purposes they are equivalent; but the
      // updates themselves convey the desired update, used inside DT only.
      GraphDiff<BasicBlock *> GD(RevDeleteUpdates);
      applyInsertUpdates(InsertUpdates, DT, &GD);
      // Update DT to redelete edges; this matches the real CFG so we can
      // perform the standard update without a postview of the CFG.
      DT.applyUpdates(DeleteUpdates);
    } else {
      if (UpdateDT)
        DT.applyUpdates(DeleteUpdates);
    }
  } else {
    if (UpdateDT)
      DT.applyUpdates(Updates);
    GraphDiff<BasicBlock *> GD;
    applyInsertUpdates(InsertUpdates, DT, &GD);
  }

  // Update for deleted edges
  for (auto &Update : DeleteUpdates)
    removeEdge(Update.getFrom(), Update.getTo());
}

void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
                                          DominatorTree &DT) {
  GraphDiff<BasicBlock *> GD;
  applyInsertUpdates(Updates, DT, &GD);
}

void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
                                          DominatorTree &DT,
                                          const GraphDiff<BasicBlock *> *GD) {
  // Get recursive last Def, assuming well formed MSSA and updated DT.
  auto GetLastDef = [&](BasicBlock *BB) -> MemoryAccess * {
    while (true) {
      MemorySSA::DefsList *Defs = MSSA->getWritableBlockDefs(BB);
      // Return last Def or Phi in BB, if it exists.
      if (Defs)
        return &*(--Defs->end());

      // Check number of predecessors, we only care if there's more than one.
      unsigned Count = 0;
      BasicBlock *Pred = nullptr;
      for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BB)) {
        Pred = Pi;
        Count++;
        if (Count == 2)
          break;
      }

      // If BB has multiple predecessors, get last definition from IDom.
      if (Count != 1) {
        // [SimpleLoopUnswitch] If BB is a dead block, about to be deleted, its
        // DT is invalidated. Return LoE as its last def. This will be added to
        // MemoryPhi node, and later deleted when the block is deleted.
        if (!DT.getNode(BB))
          return MSSA->getLiveOnEntryDef();
        if (auto *IDom = DT.getNode(BB)->getIDom())
          if (IDom->getBlock() != BB) {
            BB = IDom->getBlock();
            continue;
          }
        return MSSA->getLiveOnEntryDef();
      } else {
        // Single predecessor, BB cannot be dead. GetLastDef of Pred.
        assert(Count == 1 && Pred && "Single predecessor expected.");
        // BB can be unreachable though, return LoE if that is the case.
        if (!DT.getNode(BB))
          return MSSA->getLiveOnEntryDef();
        BB = Pred;
      }
    };
    llvm_unreachable("Unable to get last definition.");
  };

  // Get nearest IDom given a set of blocks.
  // TODO: this can be optimized by starting the search at the node with the
  // lowest level (highest in the tree).
  auto FindNearestCommonDominator =
      [&](const SmallSetVector<BasicBlock *, 2> &BBSet) -> BasicBlock * {
    BasicBlock *PrevIDom = *BBSet.begin();
    for (auto *BB : BBSet)
      PrevIDom = DT.findNearestCommonDominator(PrevIDom, BB);
    return PrevIDom;
  };

  // Get all blocks that dominate PrevIDom, stop when reaching CurrIDom. Do not
  // include CurrIDom.
  auto GetNoLongerDomBlocks =
      [&](BasicBlock *PrevIDom, BasicBlock *CurrIDom,
          SmallVectorImpl<BasicBlock *> &BlocksPrevDom) {
        if (PrevIDom == CurrIDom)
          return;
        BlocksPrevDom.push_back(PrevIDom);
        BasicBlock *NextIDom = PrevIDom;
        while (BasicBlock *UpIDom =
                   DT.getNode(NextIDom)->getIDom()->getBlock()) {
          if (UpIDom == CurrIDom)
            break;
          BlocksPrevDom.push_back(UpIDom);
          NextIDom = UpIDom;
        }
      };

  // Map a BB to its predecessors: added + previously existing. To get a
  // deterministic order, store predecessors as SetVectors. The order in each
  // will be defined by the order in Updates (fixed) and the order given by
  // children<> (also fixed). Since we further iterate over these ordered sets,
  // we lose the information of multiple edges possibly existing between two
  // blocks, so we'll keep and EdgeCount map for that.
  // An alternate implementation could keep unordered set for the predecessors,
  // traverse either Updates or children<> each time to get  the deterministic
  // order, and drop the usage of EdgeCount. This alternate approach would still
  // require querying the maps for each predecessor, and children<> call has
  // additional computation inside for creating the snapshot-graph predecessors.
  // As such, we favor using a little additional storage and less compute time.
  // This decision can be revisited if we find the alternative more favorable.

  struct PredInfo {
    SmallSetVector<BasicBlock *, 2> Added;
    SmallSetVector<BasicBlock *, 2> Prev;
  };
  SmallDenseMap<BasicBlock *, PredInfo> PredMap;

  for (auto &Edge : Updates) {
    BasicBlock *BB = Edge.getTo();
    auto &AddedBlockSet = PredMap[BB].Added;
    AddedBlockSet.insert(Edge.getFrom());
  }

  // Store all existing predecessor for each BB, at least one must exist.
  SmallDenseMap<std::pair<BasicBlock *, BasicBlock *>, int> EdgeCountMap;
  SmallPtrSet<BasicBlock *, 2> NewBlocks;
  for (auto &BBPredPair : PredMap) {
    auto *BB = BBPredPair.first;
    const auto &AddedBlockSet = BBPredPair.second.Added;
    auto &PrevBlockSet = BBPredPair.second.Prev;
    for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BB)) {
      if (!AddedBlockSet.count(Pi))
        PrevBlockSet.insert(Pi);
      EdgeCountMap[{Pi, BB}]++;
    }

    if (PrevBlockSet.empty()) {
      assert(pred_size(BB) == AddedBlockSet.size() && "Duplicate edges added.");
      LLVM_DEBUG(
          dbgs()
          << "Adding a predecessor to a block with no predecessors. "
             "This must be an edge added to a new, likely cloned, block. "
             "Its memory accesses must be already correct, assuming completed "
             "via the updateExitBlocksForClonedLoop API. "
             "Assert a single such edge is added so no phi addition or "
             "additional processing is required.\n");
      assert(AddedBlockSet.size() == 1 &&
             "Can only handle adding one predecessor to a new block.");
      // Need to remove new blocks from PredMap. Remove below to not invalidate
      // iterator here.
      NewBlocks.insert(BB);
    }
  }
  // Nothing to process for new/cloned blocks.
  for (auto *BB : NewBlocks)
    PredMap.erase(BB);

  SmallVector<BasicBlock *, 16> BlocksWithDefsToReplace;
  SmallVector<WeakVH, 8> InsertedPhis;

  // First create MemoryPhis in all blocks that don't have one. Create in the
  // order found in Updates, not in PredMap, to get deterministic numbering.
  for (auto &Edge : Updates) {
    BasicBlock *BB = Edge.getTo();
    if (PredMap.count(BB) && !MSSA->getMemoryAccess(BB))
      InsertedPhis.push_back(MSSA->createMemoryPhi(BB));
  }

  // Now we'll fill in the MemoryPhis with the right incoming values.
  for (auto &BBPredPair : PredMap) {
    auto *BB = BBPredPair.first;
    const auto &PrevBlockSet = BBPredPair.second.Prev;
    const auto &AddedBlockSet = BBPredPair.second.Added;
    assert(!PrevBlockSet.empty() &&
           "At least one previous predecessor must exist.");

    // TODO: if this becomes a bottleneck, we can save on GetLastDef calls by
    // keeping this map before the loop. We can reuse already populated entries
    // if an edge is added from the same predecessor to two different blocks,
    // and this does happen in rotate. Note that the map needs to be updated
    // when deleting non-necessary phis below, if the phi is in the map by
    // replacing the value with DefP1.
    SmallDenseMap<BasicBlock *, MemoryAccess *> LastDefAddedPred;
    for (auto *AddedPred : AddedBlockSet) {
      auto *DefPn = GetLastDef(AddedPred);
      assert(DefPn != nullptr && "Unable to find last definition.");
      LastDefAddedPred[AddedPred] = DefPn;
    }

    MemoryPhi *NewPhi = MSSA->getMemoryAccess(BB);
    // If Phi is not empty, add an incoming edge from each added pred. Must
    // still compute blocks with defs to replace for this block below.
    if (NewPhi->getNumOperands()) {
      for (auto *Pred : AddedBlockSet) {
        auto *LastDefForPred = LastDefAddedPred[Pred];
        for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
          NewPhi->addIncoming(LastDefForPred, Pred);
      }
    } else {
      // Pick any existing predecessor and get its definition. All other
      // existing predecessors should have the same one, since no phi existed.
      auto *P1 = *PrevBlockSet.begin();
      MemoryAccess *DefP1 = GetLastDef(P1);

      // Check DefP1 against all Defs in LastDefPredPair. If all the same,
      // nothing to add.
      bool InsertPhi = false;
      for (auto LastDefPredPair : LastDefAddedPred)
        if (DefP1 != LastDefPredPair.second) {
          InsertPhi = true;
          break;
        }
      if (!InsertPhi) {
        // Since NewPhi may be used in other newly added Phis, replace all uses
        // of NewPhi with the definition coming from all predecessors (DefP1),
        // before deleting it.
        NewPhi->replaceAllUsesWith(DefP1);
        removeMemoryAccess(NewPhi);
        continue;
      }

      // Update Phi with new values for new predecessors and old value for all
      // other predecessors. Since AddedBlockSet and PrevBlockSet are ordered
      // sets, the order of entries in NewPhi is deterministic.
      for (auto *Pred : AddedBlockSet) {
        auto *LastDefForPred = LastDefAddedPred[Pred];
        for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
          NewPhi->addIncoming(LastDefForPred, Pred);
      }
      for (auto *Pred : PrevBlockSet)
        for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
          NewPhi->addIncoming(DefP1, Pred);
    }

    // Get all blocks that used to dominate BB and no longer do after adding
    // AddedBlockSet, where PrevBlockSet are the previously known predecessors.
    assert(DT.getNode(BB)->getIDom() && "BB does not have valid idom");
    BasicBlock *PrevIDom = FindNearestCommonDominator(PrevBlockSet);
    assert(PrevIDom && "Previous IDom should exists");
    BasicBlock *NewIDom = DT.getNode(BB)->getIDom()->getBlock();
    assert(NewIDom && "BB should have a new valid idom");
    assert(DT.dominates(NewIDom, PrevIDom) &&
           "New idom should dominate old idom");
    GetNoLongerDomBlocks(PrevIDom, NewIDom, BlocksWithDefsToReplace);
  }

  tryRemoveTrivialPhis(InsertedPhis);
  // Create the set of blocks that now have a definition. We'll use this to
  // compute IDF and add Phis there next.
  SmallVector<BasicBlock *, 8> BlocksToProcess;
  for (auto &VH : InsertedPhis)
    if (auto *MPhi = cast_or_null<MemoryPhi>(VH))
      BlocksToProcess.push_back(MPhi->getBlock());

  // Compute IDF and add Phis in all IDF blocks that do not have one.
  SmallVector<BasicBlock *, 32> IDFBlocks;
  if (!BlocksToProcess.empty()) {
    ForwardIDFCalculator IDFs(DT, GD);
    SmallPtrSet<BasicBlock *, 16> DefiningBlocks(BlocksToProcess.begin(),
                                                 BlocksToProcess.end());
    IDFs.setDefiningBlocks(DefiningBlocks);
    IDFs.calculate(IDFBlocks);

    SmallSetVector<MemoryPhi *, 4> PhisToFill;
    // First create all needed Phis.
    for (auto *BBIDF : IDFBlocks)
      if (!MSSA->getMemoryAccess(BBIDF)) {
        auto *IDFPhi = MSSA->createMemoryPhi(BBIDF);
        InsertedPhis.push_back(IDFPhi);
        PhisToFill.insert(IDFPhi);
      }
    // Then update or insert their correct incoming values.
    for (auto *BBIDF : IDFBlocks) {
      auto *IDFPhi = MSSA->getMemoryAccess(BBIDF);
      assert(IDFPhi && "Phi must exist");
      if (!PhisToFill.count(IDFPhi)) {
        // Update existing Phi.
        // FIXME: some updates may be redundant, try to optimize and skip some.
        for (unsigned I = 0, E = IDFPhi->getNumIncomingValues(); I < E; ++I)
          IDFPhi->setIncomingValue(I, GetLastDef(IDFPhi->getIncomingBlock(I)));
      } else {
        for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BBIDF))
          IDFPhi->addIncoming(GetLastDef(Pi), Pi);
      }
    }
  }

  // Now for all defs in BlocksWithDefsToReplace, if there are uses they no
  // longer dominate, replace those with the closest dominating def.
  // This will also update optimized accesses, as they're also uses.
  for (auto *BlockWithDefsToReplace : BlocksWithDefsToReplace) {
    if (auto DefsList = MSSA->getWritableBlockDefs(BlockWithDefsToReplace)) {
      for (auto &DefToReplaceUses : *DefsList) {
        BasicBlock *DominatingBlock = DefToReplaceUses.getBlock();
        Value::use_iterator UI = DefToReplaceUses.use_begin(),
                            E = DefToReplaceUses.use_end();
        for (; UI != E;) {
          Use &U = *UI;
          ++UI;
          MemoryAccess *Usr = cast<MemoryAccess>(U.getUser());
          if (MemoryPhi *UsrPhi = dyn_cast<MemoryPhi>(Usr)) {
            BasicBlock *DominatedBlock = UsrPhi->getIncomingBlock(U);
            if (!DT.dominates(DominatingBlock, DominatedBlock))
              U.set(GetLastDef(DominatedBlock));
          } else {
            BasicBlock *DominatedBlock = Usr->getBlock();
            if (!DT.dominates(DominatingBlock, DominatedBlock)) {
              if (auto *DomBlPhi = MSSA->getMemoryAccess(DominatedBlock))
                U.set(DomBlPhi);
              else {
                auto *IDom = DT.getNode(DominatedBlock)->getIDom();
                assert(IDom && "Block must have a valid IDom.");
                U.set(GetLastDef(IDom->getBlock()));
              }
              cast<MemoryUseOrDef>(Usr)->resetOptimized();
            }
          }
        }
      }
    }
  }
  tryRemoveTrivialPhis(InsertedPhis);
}

// Move What before Where in the MemorySSA IR.
template <class WhereType>
void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
                              WhereType Where) {
  // Mark MemoryPhi users of What not to be optimized.
  for (auto *U : What->users())
    if (MemoryPhi *PhiUser = dyn_cast<MemoryPhi>(U))
      NonOptPhis.insert(PhiUser);

  // Replace all our users with our defining access.
  What->replaceAllUsesWith(What->getDefiningAccess());

  // Let MemorySSA take care of moving it around in the lists.
  MSSA->moveTo(What, BB, Where);

  // Now reinsert it into the IR and do whatever fixups needed.
  if (auto *MD = dyn_cast<MemoryDef>(What))
    insertDef(MD, /*RenameUses=*/true);
  else
    insertUse(cast<MemoryUse>(What), /*RenameUses=*/true);

  // Clear dangling pointers. We added all MemoryPhi users, but not all
  // of them are removed by fixupDefs().
  NonOptPhis.clear();
}

// Move What before Where in the MemorySSA IR.
void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
  moveTo(What, Where->getBlock(), Where->getIterator());
}

// Move What after Where in the MemorySSA IR.
void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
  moveTo(What, Where->getBlock(), ++Where->getIterator());
}

void MemorySSAUpdater::moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
                                   MemorySSA::InsertionPlace Where) {
  if (Where != MemorySSA::InsertionPlace::BeforeTerminator)
    return moveTo(What, BB, Where);

  if (auto *Where = MSSA->getMemoryAccess(BB->getTerminator()))
    return moveBefore(What, Where);
  else
    return moveTo(What, BB, MemorySSA::InsertionPlace::End);
}

// All accesses in To used to be in From. Move to end and update access lists.
void MemorySSAUpdater::moveAllAccesses(BasicBlock *From, BasicBlock *To,
                                       Instruction *Start) {

  MemorySSA::AccessList *Accs = MSSA->getWritableBlockAccesses(From);
  if (!Accs)
    return;

  assert(Start->getParent() == To && "Incorrect Start instruction");
  MemoryAccess *FirstInNew = nullptr;
  for (Instruction &I : make_range(Start->getIterator(), To->end()))
    if ((FirstInNew = MSSA->getMemoryAccess(&I)))
      break;
  if (FirstInNew) {
    auto *MUD = cast<MemoryUseOrDef>(FirstInNew);
    do {
      auto NextIt = ++MUD->getIterator();
      MemoryUseOrDef *NextMUD = (!Accs || NextIt == Accs->end())
                                    ? nullptr
                                    : cast<MemoryUseOrDef>(&*NextIt);
      MSSA->moveTo(MUD, To, MemorySSA::End);
      // Moving MUD from Accs in the moveTo above, may delete Accs, so we need
      // to retrieve it again.
      Accs = MSSA->getWritableBlockAccesses(From);
      MUD = NextMUD;
    } while (MUD);
  }

  // If all accesses were moved and only a trivial Phi remains, we try to remove
  // that Phi. This is needed when From is going to be deleted.
  auto *Defs = MSSA->getWritableBlockDefs(From);
  if (Defs && !Defs->empty())
    if (auto *Phi = dyn_cast<MemoryPhi>(&*Defs->begin()))
      tryRemoveTrivialPhi(Phi);
}

void MemorySSAUpdater::moveAllAfterSpliceBlocks(BasicBlock *From,
                                                BasicBlock *To,
                                                Instruction *Start) {
  assert(MSSA->getBlockAccesses(To) == nullptr &&
         "To block is expected to be free of MemoryAccesses.");
  moveAllAccesses(From, To, Start);
  for (BasicBlock *Succ : successors(To))
    if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))
      MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);
}

void MemorySSAUpdater::moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
                                               Instruction *Start) {
  assert(From->getUniquePredecessor() == To &&
         "From block is expected to have a single predecessor (To).");
  moveAllAccesses(From, To, Start);
  for (BasicBlock *Succ : successors(From))
    if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))
      MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);
}

void MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor(
    BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
    bool IdenticalEdgesWereMerged) {
  assert(!MSSA->getWritableBlockAccesses(New) &&
         "Access list should be null for a new block.");
  MemoryPhi *Phi = MSSA->getMemoryAccess(Old);
  if (!Phi)
    return;
  if (Old->hasNPredecessors(1)) {
    assert(pred_size(New) == Preds.size() &&
           "Should have moved all predecessors.");
    MSSA->moveTo(Phi, New, MemorySSA::Beginning);
  } else {
    assert(!Preds.empty() && "Must be moving at least one predecessor to the "
                             "new immediate predecessor.");
    MemoryPhi *NewPhi = MSSA->createMemoryPhi(New);
    SmallPtrSet<BasicBlock *, 16> PredsSet(Preds.begin(), Preds.end());
    // Currently only support the case of removing a single incoming edge when
    // identical edges were not merged.
    if (!IdenticalEdgesWereMerged)
      assert(PredsSet.size() == Preds.size() &&
             "If identical edges were not merged, we cannot have duplicate "
             "blocks in the predecessors");
    Phi->unorderedDeleteIncomingIf([&](MemoryAccess *MA, BasicBlock *B) {
      if (PredsSet.count(B)) {
        NewPhi->addIncoming(MA, B);
        if (!IdenticalEdgesWereMerged)
          PredsSet.erase(B);
        return true;
      }
      return false;
    });
    Phi->addIncoming(NewPhi, New);
    tryRemoveTrivialPhi(NewPhi);
  }
}

void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA, bool OptimizePhis) {
  assert(!MSSA->isLiveOnEntryDef(MA) &&
         "Trying to remove the live on entry def");
  // We can only delete phi nodes if they have no uses, or we can replace all
  // uses with a single definition.
  MemoryAccess *NewDefTarget = nullptr;
  if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
    // Note that it is sufficient to know that all edges of the phi node have
    // the same argument.  If they do, by the definition of dominance frontiers
    // (which we used to place this phi), that argument must dominate this phi,
    // and thus, must dominate the phi's uses, and so we will not hit the assert
    // below.
    NewDefTarget = onlySingleValue(MP);
    assert((NewDefTarget || MP->use_empty()) &&
           "We can't delete this memory phi");
  } else {
    NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
  }

  SmallSetVector<MemoryPhi *, 4> PhisToCheck;

  // Re-point the uses at our defining access
  if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
    // Reset optimized on users of this store, and reset the uses.
    // A few notes:
    // 1. This is a slightly modified version of RAUW to avoid walking the
    // uses twice here.
    // 2. If we wanted to be complete, we would have to reset the optimized
    // flags on users of phi nodes if doing the below makes a phi node have all
    // the same arguments. Instead, we prefer users to removeMemoryAccess those
    // phi nodes, because doing it here would be N^3.
    if (MA->hasValueHandle())
      ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
    // Note: We assume MemorySSA is not used in metadata since it's not really
    // part of the IR.

    assert(NewDefTarget != MA && "Going into an infinite loop");
    while (!MA->use_empty()) {
      Use &U = *MA->use_begin();
      if (auto *MUD = dyn_cast<MemoryUseOrDef>(U.getUser()))
        MUD->resetOptimized();
      if (OptimizePhis)
        if (MemoryPhi *MP = dyn_cast<MemoryPhi>(U.getUser()))
          PhisToCheck.insert(MP);
      U.set(NewDefTarget);
    }
  }

  // The call below to erase will destroy MA, so we can't change the order we
  // are doing things here
  MSSA->removeFromLookups(MA);
  MSSA->removeFromLists(MA);

  // Optionally optimize Phi uses. This will recursively remove trivial phis.
  if (!PhisToCheck.empty()) {
    SmallVector<WeakVH, 16> PhisToOptimize{PhisToCheck.begin(),
                                           PhisToCheck.end()};
    PhisToCheck.clear();

    unsigned PhisSize = PhisToOptimize.size();
    while (PhisSize-- > 0)
      if (MemoryPhi *MP =
              cast_or_null<MemoryPhi>(PhisToOptimize.pop_back_val()))
        tryRemoveTrivialPhi(MP);
  }
}

void MemorySSAUpdater::removeBlocks(
    const SmallSetVector<BasicBlock *, 8> &DeadBlocks) {
  // First delete all uses of BB in MemoryPhis.
  for (BasicBlock *BB : DeadBlocks) {
    Instruction *TI = BB->getTerminator();
    assert(TI && "Basic block expected to have a terminator instruction");
    for (BasicBlock *Succ : successors(TI))
      if (!DeadBlocks.count(Succ))
        if (MemoryPhi *MP = MSSA->getMemoryAccess(Succ)) {
          MP->unorderedDeleteIncomingBlock(BB);
          tryRemoveTrivialPhi(MP);
        }
    // Drop all references of all accesses in BB
    if (MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB))
      for (MemoryAccess &MA : *Acc)
        MA.dropAllReferences();
  }

  // Next, delete all memory accesses in each block
  for (BasicBlock *BB : DeadBlocks) {
    MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB);
    if (!Acc)
      continue;
    for (MemoryAccess &MA : llvm::make_early_inc_range(*Acc)) {
      MSSA->removeFromLookups(&MA);
      MSSA->removeFromLists(&MA);
    }
  }
}

void MemorySSAUpdater::tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs) {
  for (auto &VH : UpdatedPHIs)
    if (auto *MPhi = cast_or_null<MemoryPhi>(VH))
      tryRemoveTrivialPhi(MPhi);
}

void MemorySSAUpdater::changeToUnreachable(const Instruction *I) {
  const BasicBlock *BB = I->getParent();
  // Remove memory accesses in BB for I and all following instructions.
  auto BBI = I->getIterator(), BBE = BB->end();
  // FIXME: If this becomes too expensive, iterate until the first instruction
  // with a memory access, then iterate over MemoryAccesses.
  while (BBI != BBE)
    removeMemoryAccess(&*(BBI++));
  // Update phis in BB's successors to remove BB.
  SmallVector<WeakVH, 16> UpdatedPHIs;
  for (const BasicBlock *Successor : successors(BB)) {
    removeDuplicatePhiEdgesBetween(BB, Successor);
    if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Successor)) {
      MPhi->unorderedDeleteIncomingBlock(BB);
      UpdatedPHIs.push_back(MPhi);
    }
  }
  // Optimize trivial phis.
  tryRemoveTrivialPhis(UpdatedPHIs);
}

MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB(
    Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
    MemorySSA::InsertionPlace Point) {
  MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
  MSSA->insertIntoListsForBlock(NewAccess, BB, Point);
  return NewAccess;
}

MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessBefore(
    Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) {
  assert(I->getParent() == InsertPt->getBlock() &&
         "New and old access must be in the same block");
  MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
  MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
                              InsertPt->getIterator());
  return NewAccess;
}

MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessAfter(
    Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) {
  assert(I->getParent() == InsertPt->getBlock() &&
         "New and old access must be in the same block");
  MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
  MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
                              ++InsertPt->getIterator());
  return NewAccess;
}