Remove pruning of phi nodes in MemorySSA - it makes updating harder

[george.burgess.iv]

LGTM, thanks for the patch!

llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h

private:
   void computeDomLevels(DenseMap<DomTreeNode *, unsigned> &DomLevels);
   void markUnreachableAsLiveOnEntry(BasicBlock *BB);
   bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const;
   MemoryUseOrDef *createNewAccess(Instruction *);
   MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *);
   MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace);
   void removeFromLookups(MemoryAccess *);
 
-  void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &,
-                     const SmallPtrSetImpl<BasicBlock *> &);
+  void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &);
   MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *);
   void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
                   SmallPtrSet<BasicBlock *, 16> &Visited);
   AccessList *getOrCreateAccessList(const BasicBlock *);
   void renumberBlock(const BasicBlock *) const;
 
   AliasAnalysis *AA;
   DominatorTree *DT;

llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp

if (LocInfo.PopEpoch != PopEpoch) {
       // XXX: This is non-optimal, but only is slower cases with heavily
       // branching dominator trees.  To get the optimal number of queries would
       // be to make lowerbound and lastkill a per-loc stack, and pop it until
       // the top of that stack dominates us.  This does not seem worth it ATM.
       // A much cheaper optimization would be to always explore the deepest
       // branch of the dominator tree first. This will guarantee this resets on
       // the smallest set of blocks.
       if (LocInfo.LowerBoundBlock && LocInfo.LowerBoundBlock != BB &&
-          !DT->dominates(LocInfo.LowerBoundBlock, BB)){
+          !DT->dominates(LocInfo.LowerBoundBlock, BB)) {
         // Reset the lower bound of things to check.
         // TODO: Some day we should be able to reset to last kill, rather than
         // 0.
         LocInfo.LowerBound = 0;
         LocInfo.LowerBoundBlock = VersionStack[0]->getBlock();
         LocInfo.LastKillValid = false;
       }
     } else if (LocInfo.StackEpoch != StackEpoch) {
void MemorySSA::OptimizeUses::optimizeUses() {
   unsigned long StackEpoch = 1;
   unsigned long PopEpoch = 1;
   for (const auto *DomNode : depth_first(DT->getRootNode()))
     optimizeUsesInBlock(DomNode->getBlock(), StackEpoch, PopEpoch, VersionStack,
                         LocStackInfo);
 }
 
 void MemorySSA::placePHINodes(
-    const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks,
-    const SmallPtrSetImpl<BasicBlock *> &LiveInBlocks) {
+    const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks) {
   // Determine where our MemoryPhi's should go
   ForwardIDFCalculator IDFs(*DT);
   IDFs.setDefiningBlocks(DefiningBlocks);
-  IDFs.setLiveInBlocks(LiveInBlocks);
   SmallVector<BasicBlock *, 32> IDFBlocks;
   IDFs.calculate(IDFBlocks);
 
   // Now place MemoryPhi nodes.
   for (auto &BB : IDFBlocks) {
     // Insert phi node
     AccessList *Accesses = getOrCreateAccessList(BB);
     MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++);
for (Instruction &I : B) {
         Accesses = getOrCreateAccessList(&B);
       Accesses->push_back(MUD);
     }
     if (InsertIntoDef)
       DefiningBlocks.insert(&B);
     if (Accesses)
       DefUseBlocks.insert(&B);
   }
-
-  // Compute live-in.
-  // Live in is normally defined as "all the blocks on the path from each def to
-  // each of it's uses".
-  // MemoryDef's are implicit uses of previous state, so they are also uses.
-  // This means we don't really have def-only instructions.  The only
-  // MemoryDef's that are not really uses are those that are of the LiveOnEntry
-  // variable (because LiveOnEntry can reach anywhere, and every def is a
-  // must-kill of LiveOnEntry).
-  // In theory, you could precisely compute live-in by using alias-analysis to
-  // disambiguate defs and uses to see which really pair up with which.
-  // In practice, this would be really expensive and difficult. So we simply
-  // assume all defs are also uses that need to be kept live.
-  // Because of this, the end result of this live-in computation will be "the
-  // entire set of basic blocks that reach any use".
-
-  SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
-  SmallVector<BasicBlock *, 64> LiveInBlockWorklist(DefUseBlocks.begin(),
-                                                    DefUseBlocks.end());
-  // Now that we have a set of blocks where a value is live-in, recursively add
-  // predecessors until we find the full region the value is live.
-  while (!LiveInBlockWorklist.empty()) {
-    BasicBlock *BB = LiveInBlockWorklist.pop_back_val();
-
-    // The block really is live in here, insert it into the set.  If already in
-    // the set, then it has already been processed.
-    if (!LiveInBlocks.insert(BB).second)
-      continue;
-
-    // Since the value is live into BB, it is either defined in a predecessor or
-    // live into it to.
-    LiveInBlockWorklist.append(pred_begin(BB), pred_end(BB));
-  }
-  placePHINodes(DefiningBlocks, LiveInBlocks);
+  placePHINodes(DefiningBlocks);
 
   // Now do regular SSA renaming on the MemoryDef/MemoryUse. Visited will get
   // filled in with all blocks.
   SmallPtrSet<BasicBlock *, 16> Visited;
   renamePass(DT->getRootNode(), LiveOnEntryDef.get(), Visited);
 
   CachingWalker *Walker = getWalkerImpl();
 
bool MemorySSAPrinterLegacyPass::runOnFunction(Function &F) {
   MSSA.print(dbgs());
   if (VerifyMemorySSA)
     MSSA.verifyMemorySSA();
   return false;
 }
 
 char MemorySSAAnalysis::PassID;
 
-MemorySSAAnalysis::Result
-MemorySSAAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
+MemorySSAAnalysis::Result MemorySSAAnalysis::run(Function &F,
+                                                 FunctionAnalysisManager &AM) {
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &AA = AM.getResult<AAManager>(F);
   return MemorySSAAnalysis::Result(make_unique<MemorySSA>(F, &AA, &DT));
 }
 
 PreservedAnalyses MemorySSAPrinterPass::run(Function &F,
                                             FunctionAnalysisManager &AM) {
   OS << "MemorySSA for function: " << F.getName() << "\n";

llvm/trunk/test/Transforms/Util/MemorySSA/livein.ll

-; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
-; RUN: opt -aa-pipeline=basic-aa -passes='print<memoryssa>,verify<memoryssa>' -disable-output < %s 2>&1 | FileCheck %s
-define void @F(i8*) {
-  br i1 true, label %left, label %right
-left:
-; CHECK: 1 = MemoryDef(liveOnEntry)
-  store i8 16, i8* %0
-  br label %merge
-right:
-  br label %merge
-
-merge:
-; CHECK-NOT: 2 = MemoryPhi
-ret void 
-}
-
-define void @F2(i8*) {
-  br i1 true, label %left, label %right
-left:
-; CHECK: 1 = MemoryDef(liveOnEntry)
-  store i8 16, i8* %0
-  br label %merge
-right:
-  br label %merge
-
-merge:
-; CHECK: 2 = MemoryPhi({left,1},{right,liveOnEntry})
-%c = load i8, i8* %0
-ret void 
-}
-
-; Ensure we treat def-only blocks as though they have uses for phi placement.
-; CHECK-LABEL: define void @F3
-define void @F3() {
-  %a = alloca i8
-; CHECK: 1 = MemoryDef(liveOnEntry)
-; CHECK-NEXT: store i8 0, i8* %a
-  store i8 0, i8* %a
-  br i1 undef, label %if.then, label %if.end
-
-if.then:
-; CHECK: 2 = MemoryDef(1)
-; CHECK-NEXT: store i8 1, i8* %a
-  store i8 1, i8* %a
-  br label %if.end
-
-if.end:
-; CHECK: 4 = MemoryPhi({%0,1},{if.then,2})
-; CHECK: 3 = MemoryDef(4)
-; CHECK-NEXT: store i8 2, i8* %a
-  store i8 2, i8* %a
-  ret void
-}