[MemorySSA] Add API to update MemoryPhis, following CFG changes.

[asbirlea]

Summary

When splitting predecessors in BasicBlockUtils, we create a new block as an immediate predecessor of the original BB, then we connect a given set of predecessors to the new block.
The API in this patch will be used to update MemoryPhis for this CFG change.
If all predecessors are being moved, we move the MemoryPhi directly. Otherwise we create a new MemoryPhi in the NewBB and populate its incoming values, while deleting them from BB's Phi.
[Split from D45299 for easier review]

[asbirlea]

Format.

[asbirlea]

Consider multiple edges between blocks. MemoryPhis have an entry for each edge in this case. Move all edges to the new phi to preserve number of edges equal to number of phi entries.

[george.burgess.iv]

lib/Analysis/MemorySSAUpdater.cpp

499 ↗

(On Diff #154899)

nit: Please just use ! instead of == nullptr, for consistency

504 ↗

(On Diff #154899)

Doesn't pred_size(Old) == 1 imply that pred_size(New) == Preds.size() must be true? Or is there a case I'm missing?

507 ↗

(On Diff #154899)

nit: s/Preds.size() > 0/!Preds.empty()/

517 ↗

(On Diff #154899)

Looks like we could do this in O(Preds.size() + Phi->getNumOperands()) time if we instead used a SmallPtrSet for Preds and did a single walk over the operands list, querying the SmallPtrSet for whether $current_operand is something we could remove.

If we made a general utility for Phis similar in spirit to llvm::erase_if for this, looks like we could even make unorderedDeleteIncomingBlock and unorderedDeleteIncomingValue tiny wrappers around that.

It would arguably be mildly awkward to have the addIncoming side-effect from the lambda there, but I'd imagine it would be cleaner on the whole. WDYT?

[asbirlea]

Address comments.

[asbirlea]

lib/Analysis/MemorySSAUpdater.cpp

517 ↗

(On Diff #154899)

I think I like this more than the alternatives I thought about. So here goes :)

[george.burgess.iv]

include/llvm/Analysis/MemorySSA.h

581 ↗

(On Diff #155273)

s/entried/entries

lib/Analysis/MemorySSAUpdater.cpp

516 ↗

(On Diff #155273)

Can we replace Phi->getIncomingValueForBlock(B) with the MemoryAccess * we're passed in (if we make it non-const)?

517 ↗

(On Diff #154899)

Did making a SmallPtrSet of Preds not work?

[asbirlea]

Right, updated now.

[george.burgess.iv]

Thanks again!

[asbirlea]

Thank you for the review!

[sanjoy]

llvm/trunk/include/llvm/Analysis/MemorySSAUpdater.h

133

I was trying to understand this comment in the context of https://reviews.llvm.org/D45300 and I think it can be improved slightly. Instead of saying "before" and "point to" we should use more specific "branches to" terminology. I.e. something like:

Old now has New, an empty BasicBlock, branching directly to it, and the predecessors in Preds that used to branch to Old, now branch to New. If New is the only predecessor, move Old's Phi, if present, to New.  Otherwise, add a new Phi in New with appropriate incoming values, and update the incoming values in Old's Phi node too, if present.

[asbirlea]

llvm/trunk/include/llvm/Analysis/MemorySSAUpdater.h

133

Thanks! Updated in r340192.

llvm/trunk/include/llvm/Analysis/MemorySSA.h

assert(E >= 2 && "Cannot only remove incoming values in MemoryPhis with "
                      "at least 2 values.");
     setIncomingValue(I, getIncomingValue(E - 1));
     setIncomingBlock(I, block_begin()[E - 1]);
     setOperand(E - 1, nullptr);
     block_begin()[E - 1] = nullptr;
     setNumHungOffUseOperands(getNumOperands() - 1);
   }
 
-  // After deleting incoming block BB, the incoming blocks order may be changed.
-  void unorderedDeleteIncomingBlock(const BasicBlock *BB) {
+  // After deleting entries that satisfy Pred, remaining entries may have
+  // changed order.
+  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
     for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
-      if (block_begin()[I] == BB) {
+      if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
         unorderedDeleteIncoming(I);
         E = getNumOperands();
         --I;
       }
     assert(getNumOperands() >= 1 &&
            "Cannot remove all incoming blocks in a MemoryPhi.");
   }
 
+  // After deleting incoming block BB, the incoming blocks order may be changed.
+  void unorderedDeleteIncomingBlock(const BasicBlock *BB) {
+    unorderedDeleteIncomingIf(
+        [&](const MemoryAccess *, const BasicBlock *B) { return BB == B; });
+  }
+
   // After deleting incoming memory access MA, the incoming accesses order may
   // be changed.
   void unorderedDeleteIncomingValue(const MemoryAccess *MA) {
-    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
-      if (getIncomingValue(I) == MA) {
-        unorderedDeleteIncoming(I);
-        E = getNumOperands();
-        --I;
-      }
-    assert(getNumOperands() >= 1 &&
-           "Cannot remove all incoming values in a MemoryPhi.");
+    unorderedDeleteIncomingIf(
+        [&](const MemoryAccess *M, const BasicBlock *) { return MA == M; });
   }
 
   static bool classof(const Value *V) {
     return V->getValueID() == MemoryPhiVal;
   }
 
   void print(raw_ostream &OS) const;
 

llvm/trunk/include/llvm/Analysis/MemorySSAUpdater.h

public:
   /// |------|        |      |
   ///    ||      =>   |      |
   ///    \/           |      |
   /// |------|        |      |  <- Start
   /// | From |        |      |
   /// |------|        |------|
   void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
                                Instruction *Start);
+  /// BasicBlock Old had New, an empty BasicBlock, added directly before it,
+  /// and the predecessors in Preds that used to point to Old, now point to
+  /// New. If New is the only predecessor, move Old's Phi, if present, to New.
+  /// Otherwise, add a new Phi in New with appropriate incoming values, and
+  /// update the incoming values in Old's Phi node too, if present.
+  void
+  wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New,
+                                               ArrayRef<BasicBlock *> Preds);
 
   // 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,

llvm/trunk/lib/Analysis/MemorySSAUpdater.cpp

for (auto &Arg : MP->operands()) {
     if (!MA)
       MA = cast<MemoryAccess>(Arg);
     else if (MA != Arg)
       return nullptr;
   }
   return MA;
 }
 
+void MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor(
+    BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds) {
+  assert(!MSSA->getWritableBlockAccesses(New) &&
+         "Access list should be null for a new block.");
+  MemoryPhi *Phi = MSSA->getMemoryAccess(Old);
+  if (!Phi)
+    return;
+  if (pred_size(Old) == 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());
+    Phi->unorderedDeleteIncomingIf([&](MemoryAccess *MA, BasicBlock *B) {
+      if (PredsSet.count(B)) {
+        NewPhi->addIncoming(MA, B);
+        return true;
+      }
+      return false;
+    });
+    Phi->addIncoming(NewPhi, New);
+    if (onlySingleValue(NewPhi))
+      removeMemoryAccess(NewPhi);
+  }
+}
+
 void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA) {
   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