[MemorySSA] Add APIs to MemoryPhis to delete incoming blocks/values, and an updater API to remove blocks.

[asbirlea]

Summary

MemoryPhis now have APIs analogous to BB Phis to remove an incoming value/block.
The MemorySSAUpdater uses the above APIs when updating MemorySSA given a set of dead blocks about to be deleted.

[george.burgess.iv]

Thanks for this!

include/llvm/Analysis/MemorySSA.h

566

nit: I don't think we encourage const on value params

566

Naming nit: do you think it would be good to call out that these methods don't preserve the Phi's operand ordering? If so, please add either an unordered prefix/suffix to these.

(I've no issue with the swap-and-pop_back idiom; I just want it to be obvious at each callsite that the order might be changed)

568

Nit: The parens around (I < E) are unnecessary (and on line 569 + 585 + 597)

570

Please add a comment explaining why (I'm assuming it's something like "otherwise, we should just be deleting the Phi outright")

lib/Analysis/MemorySSAUpdater.cpp

501

nit: if (TerminatorInst *TI = BB->getTerminator()).

Do we expect to see broken IR here, though? It's my impression that BBs should always have a terminator when they're in a complete-enough state.

If yes, please add a comment explaining how broken we expect our IR to be when this method is called. :)

514

Do we need to look this up on every iteration?

519

This is already done in Value::~Value(), which should be called by MemorySSA::removeFromLists. Does it need to be repeated here? (Especially given that we skip this extra check for Uses.)

524

cast<MemoryAccess>

531

Can we set this to nullptr instead, like Value::dropAllReferences does? (I also think this could be simplified a fair amount if we swapped to dropAllReferences in the loop above + a deletion pass after that, but if that's inferior to this somehow, I'm happy to accept this approach. Value's dtor should cover the "User must be deleted too." assert for us)

538

In the interest of getting rid of soon-to-be-dangling pointers, we should probably remove all of DeadBlocks from MemorySSA::BlockNumberingValid, too.

I think that would fit best in MemorySSA::removeFromLists, though

[asbirlea]

Address comments.

[asbirlea]

lib/Analysis/MemorySSAUpdater.cpp

501

TI should be null for empty blocks. I don't have a use case, but it seemed a reasonable safety check. I can remove it if you think it's unnecessary.
I extended the header comment with the amount of "broken-ness" to be expected :).

531

Added dropAllReferences above, only updating lists here.

538

Added in MemorySSA::removeFromLookups where BlockNumbering is also updated.

[asbirlea]

nit: format.

[george.burgess.iv]

include/llvm/Analysis/MemorySSAUpdater.h

153

Did you mean "predecessor edges"?

lib/Analysis/MemorySSA.cpp

1576 ↗

(On Diff #152551)

The numbering is still valid even if we remove MA, though :)

We don't really care if the numbering has gaps. We only care that the block numbers increase as you iterate through an AccessList.

lib/Analysis/MemorySSAUpdater.cpp

501

Personally, I have a slight preference for asserting that the IR is well-formed until we know that we can't, but if you'd prefer to have a check here, I'm OK with that.

[asbirlea]

Address comments.

lib/Analysis/MemorySSA.cpp

1576 ↗

(On Diff #152551)

You're right :). Moved to removeFromLists.

lib/Analysis/MemorySSAUpdater.cpp

501

Ack, adding an assert. If I find a usecase later, I'll change it to a check.

[george.burgess.iv]

LGTM with one remaining nit. Thanks again!

lib/Analysis/MemorySSA.cpp

1623 ↗

(On Diff #152962)

Nit: can we put this in the if (Accesses->empty()) block?

I think the purpose is just to guard us from dangling pointers, and the only time we should (reasonably) carry a dangling pointer here is if we're removing the last access from this block.

[asbirlea]

Address comment. Thank you for the review!

include/llvm/Analysis/MemorySSA.h

public:
   }
 
   MemoryAccess *getIncomingValueForBlock(const BasicBlock *BB) const {
     int Idx = getBasicBlockIndex(BB);
     assert(Idx >= 0 && "Invalid basic block argument!");
     return getIncomingValue(Idx);
   }
 
+  void deleteIncoming(const unsigned I) {
+    unsigned E = getNumOperands();
+    assert((I < E) && "Cannot remove out of bounds Phi entry.");
+    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);
+  }
+
+  void deleteIncomingBlock(const BasicBlock *BB) {
+    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
+      if (block_begin()[I] == BB) {
+        deleteIncoming(I);
+        E = getNumOperands();
+        --I;
+      }
+    assert((getNumOperands() >= 1) &&
+           "Cannot remove all incoming blocks in a MemoryPhi.");
+  }
+
+  void deleteIncomingValue(const MemoryAccess *MA) {
+    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
+      if (getIncomingValue(I) == MA) {
+        deleteIncoming(I);
+        E = getNumOperands();
+        --I;
+      }
+    assert((getNumOperands() >= 1) &&
+           "Cannot remove all incoming values in a MemoryPhi.");
+  }
+
   static bool classof(const Value *V) {
     return V->getValueID() == MemoryPhiVal;
   }
 
   void print(raw_ostream &OS) const;
 
   unsigned getID() const { return ID; }
 

include/llvm/Analysis/MemorySSAUpdater.h

public:
   /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
   /// This should be called when an instruction (load/store) is deleted from
   /// the program.
   void removeMemoryAccess(const Instruction *I) {
     if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
       removeMemoryAccess(MA);
   }
 
+  /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
+  /// Assumption we make here: all uses of deleted defs and phi must either
+  /// occur in blocks about to be deleted (thus will be deleted as well), or
+  /// they occur in phis that will simply lose an incoming value.
+  void removeBlocks(const SmallPtrSetImpl<BasicBlock *> &DeadBlocks);
+
   /// 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);
   MemoryAccess *getPreviousDef(MemoryAccess *);

lib/Analysis/MemorySSAUpdater.cpp

void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA) {
   }
 
   // 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);
 }
 
+void MemorySSAUpdater::removeBlocks(
+    const SmallPtrSetImpl<BasicBlock *> &DeadBlocks) {
+
+  // First delete all uses of BB in MemoryPhis.
+  for (BasicBlock *BB : DeadBlocks) {
+    TerminatorInst *TI = BB->getTerminator();
+    if (TI)
+      for (BasicBlock *Succ : TI->successors()) {
+        if (!DeadBlocks.count(Succ))
+          if (MemoryPhi *MP = MSSA->getMemoryAccess(Succ)) {
+            MP->deleteIncomingBlock(BB);
+            if (MP->getNumIncomingValues() == 1)
+              removeMemoryAccess(MP);
+          }
+      }
+  }
+
+  // Next, delete all memory accesses in each block (and their uses)
+  for (BasicBlock *BB : DeadBlocks) {
+    while (MemorySSA::AccessList *Accesses =
+               MSSA->getWritableBlockAccesses(BB)) {
+      MemoryAccess *MA = &*Accesses->begin();
+      // Not special casing MemoryPhis.
+      if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
+        if (MA->hasValueHandle())
+          ValueHandleBase::ValueIsDeleted(MA);
+
+        while (!MA->use_empty()) {
+          Use &U = *MA->use_begin();
+          MemoryAccess *User = dyn_cast<MemoryAccess>(U.getUser());
+          // If user won't be deleted, it must be a MemoryPhi losing a value.
+          // We should have addressed that in the pass above.
+          assert(DeadBlocks.count(User->getBlock()) &&
+                 "User must be deleted too.");
+          // So, the access using MA will be deleted anyway, replace use with
+          // LoE to clear MA's uses.
+          U.set(MSSA->getLiveOnEntryDef());
+        }
+      }
+      MSSA->removeFromLookups(MA);
+      MSSA->removeFromLists(MA);
+    }
+  }
+}
+
 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;
 }