[MemorySSA] Add APIs to move memory accesses between blocks, following CFG changes.

[asbirlea]

Summary

The move APIs added in this patch will be used to update MemorySSA when CFG changes merge or split blocks, by moving memory accesses accordingly in MemorySSA's internal data structures.
[Split from D45299 for easier review]

[george.burgess.iv]

Thanks for the patch!

include/llvm/Analysis/MemorySSAUpdater.h

107

s/instructiones/instructions/

123

Were any instructions moved as part of the split, or did we just insert New between Old and all of its predecessors? In the latter case, I'd nitpick this to something more like "BasicBlock Old had New, an empty BasicBlock, added directly before it, making Old's only predecessor New. Move Old's Phi, if present, to New."

202

I'm assuming we have plans to make Where != End in future patches? (If so, that's OK; I'm just checking, since it looks like we're only passing in End right now)

lib/Analysis/MemorySSA.cpp

1483

Would it also be good to assert that BB doesn't currently have a Phi?

(We could get that sort of implicitly if we used insert(...).second instead of operator[] here)

lib/Analysis/MemorySSAUpdater.cpp

438

Prefer early exits if the code inside the if is long like this, please. (And below, at if (FirstInNew))

441

for (Instruction &I : make_range(Start->getIterator(), To->end()) {?

448

s/dyn_cast_or_null/cast/, since we're dereferencing it on the next line.

452

cast, please.

456

Is it possible to fold some of the above code into this loop without losing much in the way of clarity? It looks really similar to this loop body to me.

462

Same nit about cast.

476

Would for (BasicBlock *Succ : successors(To)) work? (and below)

496

Micro style nit:

if (MemoryPhi *Phi = ...)
  MSSA->moveTo(...)

[asbirlea]

include/llvm/Analysis/MemorySSAUpdater.h

202

I don't currently have a use case, so removing. I will add it again if a use case comes up.

lib/Analysis/MemorySSAUpdater.cpp

456

I removed the insertion place so that simplified things. PTAL.

[asbirlea]

Address comments.

[george.burgess.iv]

LGTM with a few comments; thanks again!

lib/Analysis/MemorySSA.cpp

1483

assert(X) compiles to nothing in non-asserting builds, so we probably want something more like:

bool Inserted = ValueToMemoryAccess.insert({BB, What}).second;
(void)Inserted;
assert(Inserted && "Cannot ...");

(the (void)Inserted; suppresses unused variable warnings, and forgetting to put it has tripped me up more times than I can count.)

lib/Analysis/MemorySSAUpdater.cpp

455

Please add a quick comment noting that moveTo might delete Accs, so we need to re-retrieve it here

[asbirlea]

Address comments and remove movePhi API. There is a use case needing something move generic that I will send in a separate patch.

Thank you for the review!

[asbirlea]

Format.

include/llvm/Analysis/MemorySSA.h

DefsList *getWritableBlockDefs(const BasicBlock *BB) const {
     return It == PerBlockDefs.end() ? nullptr : It->second.get();
   }
 
   // These is used by the updater to perform various internal MemorySSA
   // machinsations.  They do not always leave the IR in a correct state, and
   // relies on the updater to fixup what it breaks, so it is not public.
 
   void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where);
-  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, InsertionPlace Point);
+  void moveTo(MemoryAccess *What, BasicBlock *BB, InsertionPlace Point);
 
   // Rename the dominator tree branch rooted at BB.
   void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal,
                   SmallPtrSetImpl<BasicBlock *> &Visited) {
     renamePass(DT->getNode(BB), IncomingVal, Visited, true, true);
   }
 
   void removeFromLookups(MemoryAccess *);

include/llvm/Analysis/MemorySSAUpdater.h

public:
   /// load a
   /// Where a mayalias b, *does* require RenameUses be set to true.
   void insertDef(MemoryDef *Def, bool RenameUses = false);
   void insertUse(MemoryUse *Use);
   void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
   void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
   void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
                    MemorySSA::InsertionPlace Where);
+  /// `From` block was spliced into `From` and `To`.
+  /// Move all accesses from `From` to `To` starting at instruction `Start`.
+  /// `To` is newly created BB, so empty of MemorySSA::MemoryAccesses.
+  /// Edges are already updated, so successors of `To` with MPhi nodes need to
+  /// update incoming block.
+  /// |------|        |------|
+  /// | From |        | From |
+  /// |      |        |------|
+  /// |      |           ||
+  /// |      |   =>      \/
+  /// |      |        |------|  <- Start
+  /// |      |        |  To  |
+  /// |------|        |------|
+  void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To,
+                                Instruction *Start);
+  /// `From` block was merged into `To`. All instructions were moved and
+  /// `From` is an empty block with successor edges; `From` is about to be
+  /// deleted. Move all accesses from `From` to `To` starting at instruction
+  /// `Start`. `To` may have multiple successors, `From` has a single
+  /// predecessor. `From` may have successors with MPhi nodes, replace their
+  /// incoming block with `To`.
+  /// |------|        |------|
+  /// |  To  |        |  To  |
+  /// |------|        |      |
+  ///    ||      =>   |      |
+  ///    \/           |      |
+  /// |------|        |      |  <- Start
+  /// | From |        |      |
+  /// |------|        |------|
+  void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
+                               Instruction *Start);
+  /// BasicBlock Old had New, an empty BasicBlock, added directly before it,
+  /// making Old's only predecessor New. Move Old's Phi, if present, to New.
+  void movePhiToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New);
 
   // The below are utility functions. Other than creation of accesses to pass
   // to insertDef, and removeAccess to remove accesses, you should generally
   // not attempt to update memoryssa yourself. It is very non-trivial to get
   // the edge cases right, and the above calls already operate in near-optimal
   // time bounds.
 
   /// Create a MemoryAccess in MemorySSA at a specified point in a block,
public:
 
   /// Get handle on MemorySSA.
   MemorySSA* getMemorySSA() const { return MSSA; }
 
 private:
   // Move What before Where in the MemorySSA IR.
   template <class WhereType>
   void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where);
+  // Move all memory accesses from `From` to `To` starting at `Start`.
+  // Restrictions apply, see public wrappers of this method.
+  void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start);
   MemoryAccess *getPreviousDef(MemoryAccess *);
   MemoryAccess *getPreviousDefInBlock(MemoryAccess *);
   MemoryAccess *
   getPreviousDefFromEnd(BasicBlock *,
                         DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &);
   MemoryAccess *
   getPreviousDefRecursive(BasicBlock *,
                           DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &);
   MemoryAccess *recursePhi(MemoryAccess *Phi);
   template <class RangeType>
   MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
   void fixupDefs(const SmallVectorImpl<MemoryAccess *> &);
 };
 } // end namespace llvm
 
 #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H

lib/Analysis/MemorySSA.cpp

 void MemorySSA::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
                        AccessList::iterator Where) {
   // Keep it in the lookup tables, remove from the lists
   removeFromLists(What, false);
   What->setBlock(BB);
   insertIntoListsBefore(What, BB, Where);
 }
 
-void MemorySSA::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
+void MemorySSA::moveTo(MemoryAccess *What, BasicBlock *BB,
                        InsertionPlace Point) {
+  if (isa<MemoryPhi>(What)) {
+    assert(Point == Beginning &&
+           "Can only move a Phi at the beginning of the block");
+    // Update lookup table entry
+    ValueToMemoryAccess.erase(What->getBlock());
+    assert(ValueToMemoryAccess.insert({BB, What}).second &&
+           "Cannot move a Phi to a block that already has one");
+  }
+
   removeFromLists(What, false);
   What->setBlock(BB);
   insertIntoListsForBlock(What, BB, Point);
 }
 
 MemoryPhi *MemorySSA::createMemoryPhi(BasicBlock *BB) {
   assert(!getMemoryAccess(BB) && "MemoryPhi already exists for this BB");
   MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++);

lib/Analysis/MemorySSAUpdater.cpp

void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
   moveTo(What, Where->getBlock(), ++Where->getIterator());
 }
 
 void MemorySSAUpdater::moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
                                    MemorySSA::InsertionPlace Where) {
   return moveTo(What, BB, Where);
 }
 
+// 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;
+
+  MemoryAccess *FirstInNew = nullptr;
+  for (Instruction &I : make_range(Start->getIterator(), To->end()))
+    if ((FirstInNew = MSSA->getMemoryAccess(&I)))
+      break;
+  if (!FirstInNew)
+    return;
+
+  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);
+    Accs = MSSA->getWritableBlockAccesses(From);
+    MUD = NextMUD;
+  } while (MUD);
+}
+
+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->getSinglePredecessor() == 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::movePhiToNewImmediatePredecessor(BasicBlock *Old,
+                                                        BasicBlock *New) {
+  assert(MSSA->getWritableBlockAccesses(New) == nullptr &&
+         "Access list should be null for a new block");
+  if (MemoryPhi *Phi = MSSA->getMemoryAccess(Old))
+    MSSA->moveTo(Phi, New, MemorySSA::Beginning);
+}
+
 /// 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;
 }
 
 void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA) {
   assert(!MSSA->isLiveOnEntryDef(MA) &&