[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

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

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

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);
   }
 
+  // After deleting incoming position I, the order of incoming may be changed.
+  void unorderedDeleteIncoming(unsigned I) {
+    unsigned E = getNumOperands();
+    assert(I < E && "Cannot remove out of bounds Phi entry.");
+    // MemoryPhi must have at least two incoming values, otherwise the MemoryPhi
+    // itself should be deleted.
+    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) {
+    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
+      if (block_begin()[I] == BB) {
+        unorderedDeleteIncoming(I);
+        E = getNumOperands();
+        --I;
+      }
+    assert(getNumOperands() >= 1 &&
+           "Cannot remove all incoming blocks in a MemoryPhi.");
+  }
+
+  // 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.");
+  }
+
   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.
+  /// Deleted blocks still have successor info, but their predecessor edges and
+  /// Phi nodes may already be updated. Instructions in DeadBlocks should be
+  /// deleted after this call.
+  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/MemorySSA.cpp

bool MemorySSA::dominatesUse(const MemoryAccess *Replacer,
   return true;
 }
 
 /// Properly remove \p MA from all of MemorySSA's lookup tables.
 void MemorySSA::removeFromLookups(MemoryAccess *MA) {
   assert(MA->use_empty() &&
          "Trying to remove memory access that still has uses");
   BlockNumbering.erase(MA);
   if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
     MUD->setDefiningAccess(nullptr);
   // Invalidate our walker's cache if necessary
   if (!isa<MemoryUse>(MA))
     Walker->invalidateInfo(MA);
 
   Value *MemoryInst;
   if (const auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
     MemoryInst = MUD->getMemoryInst();
   else
     MemoryInst = MA->getBlock();
 
   auto VMA = ValueToMemoryAccess.find(MemoryInst);
   if (VMA->second == MA)
     ValueToMemoryAccess.erase(VMA);
 }
 
 /// Properly remove \p MA from all of MemorySSA's lists.
 ///
 /// Because of the way the intrusive list and use lists work, it is important to
 /// do removal in the right order.
 /// ShouldDelete defaults to true, and will cause the memory access to also be
 /// deleted, not just removed.
 void MemorySSA::removeFromLists(MemoryAccess *MA, bool ShouldDelete) {
+  BasicBlock *BB = MA->getBlock();
   // The access list owns the reference, so we erase it from the non-owning list
   // first.
   if (!isa<MemoryUse>(MA)) {
-    auto DefsIt = PerBlockDefs.find(MA->getBlock());
+    auto DefsIt = PerBlockDefs.find(BB);
     std::unique_ptr<DefsList> &Defs = DefsIt->second;
     Defs->remove(*MA);
     if (Defs->empty())
       PerBlockDefs.erase(DefsIt);
   }
 
   // The erase call here will delete it. If we don't want it deleted, we call
   // remove instead.
-  auto AccessIt = PerBlockAccesses.find(MA->getBlock());
+  auto AccessIt = PerBlockAccesses.find(BB);
   std::unique_ptr<AccessList> &Accesses = AccessIt->second;
   if (ShouldDelete)
     Accesses->erase(MA);
   else
     Accesses->remove(MA);
 
-  if (Accesses->empty())
+  if (Accesses->empty()) {
     PerBlockAccesses.erase(AccessIt);
+    BlockNumberingValid.erase(BB);
+  }
 }
 
 void MemorySSA::print(raw_ostream &OS) const {
   MemorySSAAnnotatedWriter Writer(this);
   F.print(OS, &Writer);
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

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();
+    assert(TI && "Basic block expected to have a terminator instruction");
+    for (BasicBlock *Succ : TI->successors())
+      if (!DeadBlocks.count(Succ))
+        if (MemoryPhi *MP = MSSA->getMemoryAccess(Succ)) {
+          MP->unorderedDeleteIncomingBlock(BB);
+          if (MP->getNumIncomingValues() == 1)
+            removeMemoryAccess(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 (auto AB = Acc->begin(), AE = Acc->end(); AB != AE;) {
+      MemoryAccess *MA = &*AB;
+      ++AB;
+      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;
 }
 
 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;
 }