Update MemorySSA in Local utils removing blocks.

[asbirlea]

Summary

Extend Local utils to update MemorySSA.

[asbirlea]

Rebase and nit updates.

[george.burgess.iv]

Looks fine to me, though I'd prefer if someone familiar with this code had a look, as well.

[NutshellySima]

Looks like a nice improvement.

lib/Transforms/Utils/Local.cpp

2075

Yes, I think the deletion order doesn't matter.

[asbirlea]

Address comment.

[asbirlea]

lib/Transforms/Utils/Local.cpp

2075

It seems to make sense to use this in the first iteration over the blocks in F that follows, but not the second one doing the erase, since that's better to be iterator based.
Also search DeadBlockSet instead of Reachable, assuming more blocks are live than dead.

[NutshellySima]

Thanks for the improvement! Comments are inline.

lib/Transforms/Utils/Local.cpp

2075

I think maybe you can replace ToDeleteBBs with DeadBlockSet.
For assuming there are

more blocks are live than dead

, if you are interested, you can run CTMarks/have some other benchmarks to see whether there is performance degradation.

[asbirlea]

Address comment.

[NutshellySima]

Thanks for the change.
Please have a look at my new inline comments. (I have a quick glance at the source code of MemorySSA and I think it's fine; but it's better for you to check that).
LGTM.

lib/Transforms/Utils/Local.cpp

2101

We sometimes have BasicBlocks which are pending deletion in the DomTreeUpdater. (like that previously in DeferredDominance).

So, sometimes a same BasicBlock can be passed into MSSAU->removeBlocks multiple times in different calls to removeUnreachableBlocks. You need to be aware of that and check whether it is fine.

[asbirlea]

Thank you for the review!

lib/Transforms/Utils/Local.cpp

2101

I believe that's fine. In MemorySSA, all memory accesses will be deleted for a dead block on the first call, subsequent calls will find an empty list.

include/llvm/Transforms/Utils/Local.h

 class DbgInfoIntrinsic;
 class DbgValueInst;
 class DIBuilder;
 class Function;
 class Instruction;
 class LazyValueInfo;
 class LoadInst;
 class MDNode;
+class MemorySSAUpdater;
 class PHINode;
 class StoreInst;
 class TargetLibraryInfo;
 class TargetTransformInfo;
 
 /// A set of parameters used to control the transforms in the SimplifyCFG pass.
 /// Options may change depending on the position in the optimization pipeline.
 /// For example, canonical form that includes switches and branches may later be

 /// isInstructionTriviallyDead would be true if the use count was 0.
 bool wouldInstructionBeTriviallyDead(Instruction *I,
                                      const TargetLibraryInfo *TLI = nullptr);
 
 /// If the specified value is a trivially dead instruction, delete it.
 /// If that makes any of its operands trivially dead, delete them too,
 /// recursively. Return true if any instructions were deleted.
 bool RecursivelyDeleteTriviallyDeadInstructions(Value *V,
-                                        const TargetLibraryInfo *TLI = nullptr);
+                                        const TargetLibraryInfo *TLI = nullptr,
+                                        MemorySSAUpdater *MSSAUpdater = nullptr);
 
 /// Delete all of the instructions in `DeadInsts`, and all other instructions
 /// that deleting these in turn causes to be trivially dead.
 ///
 /// The initial instructions in the provided vector must all have empty use
 /// lists and satisfy `isInstructionTriviallyDead`.
 ///
 /// `DeadInsts` will be used as scratch storage for this routine and will be
 /// empty afterward.
 void RecursivelyDeleteTriviallyDeadInstructions(
     SmallVectorImpl<Instruction *> &DeadInsts,
-    const TargetLibraryInfo *TLI = nullptr);
+    const TargetLibraryInfo *TLI = nullptr,
+    MemorySSAUpdater *MSSAUpdater = nullptr);
 
 /// If the specified value is an effectively dead PHI node, due to being a
 /// def-use chain of single-use nodes that either forms a cycle or is terminated
 /// by a trivially dead instruction, delete it. If that makes any of its
 /// operands trivially dead, delete them too, recursively. Return true if a
 /// change was made.
 bool RecursivelyDeleteDeadPHINode(PHINode *PN,
                                   const TargetLibraryInfo *TLI = nullptr);

 /// \param BB  Block whose terminator will be replaced.  Its terminator must
 ///            have an unwind successor.
 void removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT = nullptr);
 
 /// Remove all blocks that can not be reached from the function's entry.
 ///
 /// Returns true if any basic block was removed.
 bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr,
-                             DeferredDominance *DDT = nullptr);
+                             DeferredDominance *DDT = nullptr,
+                             MemorySSAUpdater *MSSAUpdater = nullptr);
 
 /// Combine the metadata of two instructions so that K can replace J
 ///
 /// Metadata not listed as known via KnownIDs is removed
 void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs);
 
 /// Combine the metadata of two instructions so that K can replace J. This
 /// specifically handles the case of CSE-like transformations.

lib/Transforms/Utils/Local.cpp

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/CallSite.h"

 }
 
 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
 /// trivially dead instruction, delete it.  If that makes any of its operands
 /// trivially dead, delete them too, recursively.  Return true if any
 /// instructions were deleted.
 bool
 llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V,
-                                                 const TargetLibraryInfo *TLI) {
+                                                 const TargetLibraryInfo *TLI,
+                                                 MemorySSAUpdater *MSSAUpdater) {
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I || !I->use_empty() || !isInstructionTriviallyDead(I, TLI))
     return false;
 
   SmallVector<Instruction*, 16> DeadInsts;
   DeadInsts.push_back(I);
-  RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI);
+  RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAUpdater);
 
   return true;
 }
 
 void llvm::RecursivelyDeleteTriviallyDeadInstructions(
-    SmallVectorImpl<Instruction *> &DeadInsts, const TargetLibraryInfo *TLI) {
+    SmallVectorImpl<Instruction *> &DeadInsts, const TargetLibraryInfo *TLI,
+    MemorySSAUpdater *MSSAUpdater) {
   // Process the dead instruction list until empty.
   while (!DeadInsts.empty()) {
     Instruction &I = *DeadInsts.pop_back_val();
     assert(I.use_empty() && "Instructions with uses are not dead.");
     assert(isInstructionTriviallyDead(&I, TLI) &&
            "Live instruction found in dead worklist!");
 
     // Don't lose the debug info while deleting the instructions.
for (Use &OpU : I.operands()) {
 
       // If the operand is an instruction that became dead as we nulled out the
       // operand, and if it is 'trivially' dead, delete it in a future loop
       // iteration.
       if (Instruction *OpI = dyn_cast<Instruction>(OpV))
         if (isInstructionTriviallyDead(OpI, TLI))
           DeadInsts.push_back(OpI);
     }
+    if (MSSAUpdater)
+      MSSAUpdater->removeMemoryAccess(&I);
 
     I.eraseFromParent();
   }
 }
 
 /// areAllUsesEqual - Check whether the uses of a value are all the same.
 /// This is similar to Instruction::hasOneUse() except this will also return
 /// true when there are no uses or multiple uses that all refer to the same
while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) {
     // iterate to, then our iterator is invalid, restart scanning from the top
     // of the block.
     if (PhiIt != OldPhiIt) PhiIt = &BB->front();
   }
   if (DDT)
     DDT->deleteEdge(Pred, BB);
 }
 
-/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
+/// MergeBasicBlockIntoOnlyPred - DestBB is a blockewith one predecessor and its
 /// predecessor is known to have one successor (DestBB!).  Eliminate the edge
 /// between them, moving the instructions in the predecessor into DestBB and
 /// deleting the predecessor block.
 void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT,
                                        DeferredDominance *DDT) {
   assert(!(DT && DDT) && "Cannot call with both DT and DDT.");
 
   // If BB has single-entry PHI nodes, fold them.
if (DDT)
     DDT->deleteEdge(BB, UnwindDest);
 }
 
 /// removeUnreachableBlocks - Remove blocks that are not reachable, even
 /// if they are in a dead cycle.  Return true if a change was made, false
 /// otherwise. If `LVI` is passed, this function preserves LazyValueInfo
 /// after modifying the CFG.
 bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI,
-                                   DeferredDominance *DDT) {
+                                   DeferredDominance *DDT,
+                                   MemorySSAUpdater *MSSAUpdater) {
   SmallPtrSet<BasicBlock*, 16> Reachable;
   bool Changed = markAliveBlocks(F, Reachable, DDT);
 
   // If there are unreachable blocks in the CFG...
   if (Reachable.size() == F.size())
     return Changed;
 
   assert(Reachable.size() < F.size());
   NumRemoved += F.size()-Reachable.size();
 
+  //FIXME: if the deletion order is important, build a vector, not a set.
+  // Reuse this set/vector in iteration below.
+  // Isn't iterator invalidated below?
+  SmallPtrSet<BasicBlock *, 16> DeadBlockSet;
+  for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ++I) {
+    auto *BB = &*I;
+    if (Reachable.count(BB))
+      continue;
+    DeadBlockSet.insert(BB);
+  }
+
+  if (MSSAUpdater) {
+    MSSAUpdater->removeBlocks(DeadBlockSet);
+  }
+
   // Loop over all of the basic blocks that are not reachable, dropping all of
   // their internal references. Update DDT and LVI if available.
   std::vector <DominatorTree::UpdateType> Updates;
   for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ++I) {
     auto *BB = &*I;
     if (Reachable.count(BB))
       continue;
     for (BasicBlock *Successor : successors(BB)) {
       if (Reachable.count(Successor))
         Successor->removePredecessor(BB);
       if (DDT)
         Updates.push_back({DominatorTree::Delete, BB, Successor});
     }
     if (LVI)
       LVI->eraseBlock(BB);
     BB->dropAllReferences();
   }
 
   for (Function::iterator I = ++F.begin(); I != F.end();) {
     auto *BB = &*I;