[MemorySSA] Change how the walker views/walks visited phis.

This patch teaches the caching MemorySSA walker a few things:

1. Not to walk Phis we've walked before. It seems that we tried to do
   this before, but it didn't work so well in cases like:

define void @foo() {
  %1 = alloca i8
  %2 = alloca i8
  br label %begin

begin:
  ; 3 = MemoryPhi({%0,liveOnEntry},{%end,2})
  ; 1 = MemoryDef(3)
  store i8 0, i8* %2
  br label %end

end:
  ; MemoryUse(?)
  load i8, i8* %1
  ; 2 = MemoryDef(1)
  store i8 0, i8* %2
  br label %begin
}

Because we wouldn't put Phis in Q.Visited until we tried to visit them.
So, when trying to optimize MemoryUse(?):
  - We would visit 3 above
    - ...Which would make us put {%0,liveOnEntry} in Q.Visited
    - ...Which would make us visit {%0,liveOnEntry}
    - ...Which would make us put {%end,2} in Q.Visited
    - ...Which would make us visit {%end,2}
      - ...Which would make us visit 3
        - ...Which would realize we've already visited everything in 3
        - ...Which would make us conservatively return 3.

In the added test-case, (@looped_visitedonlyonce) this behavior would
cause us to give incorrect results. Specifically, we'd visit 4 twice
in the same query, but on the second visit, we'd skip while.cond because
it had been visited, visit if.then/if.then2, and cache "1" as the
clobbering def on the way back.

2. If we try to walk the defs of a {Phi,MemLoc} and see it has been
   visited before, just hand back the Phi we're trying to optimize.

I promise this isn't as terrible as it seems. :)

We now insert {Phi,MemLoc} pairs just before walking the Phi's upward
defs. So, we check the cache for the {Phi,MemLoc} pair before checking
if we've already walked the Phi.

The {Phi,MemLoc} pair is (almost?) always guaranteed to have a cache
entry if we've already fully walked it, because we cache as we go.

So, if the {Phi,MemLoc} pair isn't in cache, either:
 (a) we must be in the process of visiting it (in which case, we can't
     give a better answer in a cache-as-we-go DFS walker)

 (b) we visited it, but didn't cache it on the way back (...which seems
     to require `ModifyingAccess` to not dominate `StartingAccess`,
     so I'm 99% sure that would be an error. If it's not an error, I
     haven't been able to get it to happen locally, so I suspect it's
     rare.)

- - - - -

As a consequence of this change, we no longer skip upward defs of phis,
so we can kill the `VisitedOnlyOne` check. This gives us better accuracy
than we had before, at the cost of potentially doing a bit more work
when we have a loop.

llvm-svn: 264814

3 files changed, 49 insertions, 27 deletions

diff --git a/llvm/lib/Transforms/Utils/MemorySSA.cpp b/llvm/lib/Transforms/Utils/MemorySSA.cpp
index f667bce04e3..b71c1945a0e 100644
--- a/llvm/lib/Transforms/Utils/MemorySSA.cpp
+++ b/llvm/lib/Transforms/Utils/MemorySSA.cpp
@@ -910,18 +910,20 @@ MemoryAccessPair CachingMemorySSAWalker::UpwardsDFSWalk(
            "Skipping phi's children doesn't end the DFS?");
 #endif
 
+    const MemoryAccessPair PHIPair(CurrAccess, Loc);
+
+    // Don't try to optimize this phi again if we've already tried to do so.
+    if (!Q.Visited.insert(PHIPair).second) {
+      ModifyingAccess = CurrAccess;
+      break;
+    }
+
     // Recurse on PHI nodes, since we need to change locations.
     // TODO: Allow graphtraits on pairs, which would turn this whole function
     // into a normal single depth first walk.
     MemoryAccess *FirstDef = nullptr;
-    const MemoryAccessPair PHIPair(CurrAccess, Loc);
-    bool VisitedOnlyOne = true;
     for (auto MPI = upward_defs_begin(PHIPair), MPE = upward_defs_end();
          MPI != MPE; ++MPI) {
-      // Don't follow this path again if we've followed it once
-      if (!Q.Visited.insert(*MPI).second)
-        continue;
-
       bool Backedge =
           !FollowingBackedge &&
           DT->dominates(CurrAccess->getBlock(), MPI.getPhiArgBlock());
@@ -939,26 +941,12 @@ MemoryAccessPair CachingMemorySSAWalker::UpwardsDFSWalk(
 
       if (!FirstDef)
         FirstDef = CurrentPair.first;
-      else
-        VisitedOnlyOne = false;
     }
 
     // If we exited the loop early, go with the result it gave us.
     if (!ModifyingAccess) {
-      // The above loop determines if all arguments of the phi node reach the
-      // same place. However we skip arguments that are cyclically dependent
-      // only on the value of this phi node. This means in some cases, we may
-      // only visit one argument of the phi node, and the above loop will
-      // happily say that all the arguments are the same. However, in that case,
-      // we still can't walk past the phi node, because that argument still
-      // kills the access unless we hit the top of the function when walking
-      // that argument.
-      if (VisitedOnlyOne && !(FirstDef && MSSA->isLiveOnEntryDef(FirstDef))) {
-        ModifyingAccess = CurrAccess;
-      } else {
-        assert(FirstDef && "Visited multiple phis, but FirstDef isn't set?");
-        ModifyingAccess = FirstDef;
-      }
+      assert(FirstDef && "Found a Phi with no upward defs?");
+      ModifyingAccess = FirstDef;
     }
     break;
   }
diff --git a/llvm/test/Transforms/Util/MemorySSA/cyclicphi.ll b/llvm/test/Transforms/Util/MemorySSA/cyclicphi.ll
index 55ec1abfefc..6367f6b7329 100644
--- a/llvm/test/Transforms/Util/MemorySSA/cyclicphi.ll
+++ b/llvm/test/Transforms/Util/MemorySSA/cyclicphi.ll
@@ -56,7 +56,7 @@ bb68:                                             ; preds = %bb26
 bb77:                                             ; preds = %bb68, %bb26
 ; CHECK: 2 = MemoryPhi({bb26,3},{bb68,1})
 ; FIXME: This should be MemoryUse(liveOnEntry)
-; CHECK: MemoryUse(2)
+; CHECK: MemoryUse(3)
 ; CHECK-NEXT: %tmp78 = load i64*, i64** %tmp25, align 8
   %tmp78 = load i64*, i64** %tmp25, align 8
   br label %bb26
diff --git a/llvm/test/Transforms/Util/MemorySSA/phi-translation.ll b/llvm/test/Transforms/Util/MemorySSA/phi-translation.ll
index a2cba18dcf4..f0f5da99617 100644
--- a/llvm/test/Transforms/Util/MemorySSA/phi-translation.ll
+++ b/llvm/test/Transforms/Util/MemorySSA/phi-translation.ll
@@ -61,8 +61,7 @@ phi.1:
 ; Order matters here; phi.2 needs to come before phi.3, because that's the order
 ; they're visited in.
 ; CHECK: 7 = MemoryPhi({phi.2,4},{phi.3,3})
-; FIXME: This should be MemoryUse(1)
-; CHECK: MemoryUse(7)
+; CHECK: MemoryUse(1)
 ; CHECK-NEXT: load i8, i8* %local
   load i8, i8* %local
   ret void
@@ -106,8 +105,7 @@ d:
 
 e:
 ; 8 = MemoryPhi({c,4},{d,5})
-; FIXME: This should be MemoryUse(1)
-; CHECK: MemoryUse(8)
+; CHECK: MemoryUse(1)
 ; CHECK-NEXT: load i8, i8* %p1
   load i8, i8* %p1
   ret void
@@ -145,3 +143,39 @@ loop.3:
   load i8, i8* %p1
   br i1 undef, label %loop.2, label %loop.1
 }
+
+; CHECK-LABEL: define void @looped_visitedonlyonce
+define void @looped_visitedonlyonce(i8* noalias %p1, i8* noalias %p2) {
+  br label %while.cond
+
+while.cond:
+; CHECK: 5 = MemoryPhi({%0,liveOnEntry},{if.end,3})
+; CHECK-NEXT: br i1 undef, label %if.then, label %if.end
+  br i1 undef, label %if.then, label %if.end
+
+if.then:
+; CHECK: 1 = MemoryDef(5)
+; CHECK-NEXT: store i8 0, i8* %p1
+  store i8 0, i8* %p1
+  br i1 undef, label %if.end, label %if.then2
+
+if.then2:
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: store i8 1, i8* %p2
+  store i8 1, i8* %p2
+  br label %if.end
+
+if.end:
+; CHECK: 4 = MemoryPhi({while.cond,5},{if.then,1},{if.then2,2})
+; CHECK: MemoryUse(4)
+; CHECK-NEXT: load i8, i8* %p1
+  load i8, i8* %p1
+; CHECK: 3 = MemoryDef(4)
+; CHECK-NEXT: store i8 2, i8* %p2
+  store i8 2, i8* %p2
+; CHECK: MemoryUse(4)
+; CHECK-NEXT: load i8, i8* %p1
+  load i8, i8* %p1
+  br label %while.cond
+}
+