Fix bugs in the MemorySSA walker.

There are a few bugs in the walker that this patch addresses.
Primarily:
- Caching can break when we have multiple BBs without phis
- We weren't optimizing some phis properly
- Because of how the DFS iterator works, there were times where we
  wouldn't cache any results of our DFS

I left the test cases with FIXMEs in, because I'm not sure how much
effort it will take to get those to work (read: We'll probably
ultimately have to end up redoing the walker, or we'll have to come up
with some creative caching tricks), and more test coverage = better.

Differential Revision: http://reviews.llvm.org/D18065

llvm-svn: 264180

1 files changed, 147 insertions, 0 deletions

diff --git a/llvm/test/Transforms/Util/MemorySSA/phi-translation.ll b/llvm/test/Transforms/Util/MemorySSA/phi-translation.ll
new file mode 100644
index 00000000000..a2cba18dcf4
--- /dev/null
+++ b/llvm/test/Transforms/Util/MemorySSA/phi-translation.ll
@@ -0,0 +1,147 @@
+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+
+; %ptr can't alias %local, so we should be able to optimize the use of %local to
+; point to the store to %local.
+; CHECK-LABEL: define void @check
+define void @check(i8* %ptr, i1 %bool) {
+entry:
+  %local = alloca i8, align 1
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i8 0, i8* %local, align 1
+  store i8 0, i8* %local, align 1
+  br i1 %bool, label %if.then, label %if.end
+
+if.then:
+  %p2 = getelementptr inbounds i8, i8* %ptr, i32 1
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: store i8 0, i8* %p2, align 1
+  store i8 0, i8* %p2, align 1
+  br label %if.end
+
+if.end:
+; CHECK: 3 = MemoryPhi({entry,1},{if.then,2})
+; CHECK: MemoryUse(1)
+; CHECK-NEXT: load i8, i8* %local, align 1
+  load i8, i8* %local, align 1
+  ret void
+}
+
+; CHECK-LABEL: define void @check2
+define void @check2(i1 %val1, i1 %val2, i1 %val3) {
+entry:
+  %local = alloca i8, align 1
+  %local2 = alloca i8, align 1
+
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i8 0, i8* %local
+  store i8 0, i8* %local
+  br i1 %val1, label %if.then, label %phi.3
+
+if.then:
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: store i8 2, i8* %local2
+  store i8 2, i8* %local2
+  br i1 %val2, label %phi.2, label %phi.3
+
+phi.3:
+; CHECK: 6 = MemoryPhi({entry,1},{if.then,2})
+; CHECK: 3 = MemoryDef(6)
+; CHECK-NEXT: store i8 3, i8* %local2
+  store i8 3, i8* %local2
+  br i1 %val3, label %phi.2, label %phi.1
+
+phi.2:
+; CHECK: 5 = MemoryPhi({if.then,2},{phi.3,3})
+; CHECK: 4 = MemoryDef(5)
+; CHECK-NEXT: store i8 4, i8* %local2
+  store i8 4, i8* %local2
+  br label %phi.1
+
+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-NEXT: load i8, i8* %local
+  load i8, i8* %local
+  ret void
+}
+
+; CHECK-LABEL: define void @cross_phi
+define void @cross_phi(i8* noalias %p1, i8* noalias %p2) {
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i8 0, i8* %p1
+  store i8 0, i8* %p1
+; CHECK: MemoryUse(1)
+; CHECK-NEXT: load i8, i8* %p1
+  load i8, i8* %p1
+  br i1 undef, label %a, label %b
+
+a:
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: store i8 0, i8* %p2
+  store i8 0, i8* %p2
+  br i1 undef, label %c, label %d
+
+b:
+; CHECK: 3 = MemoryDef(1)
+; CHECK-NEXT: store i8 1, i8* %p2
+  store i8 1, i8* %p2
+  br i1 undef, label %c, label %d
+
+c:
+; CHECK: 6 = MemoryPhi({a,2},{b,3})
+; CHECK: 4 = MemoryDef(6)
+; CHECK-NEXT: store i8 2, i8* %p2
+  store i8 2, i8* %p2
+  br label %e
+
+d:
+; CHECK: 7 = MemoryPhi({a,2},{b,3})
+; CHECK: 5 = MemoryDef(7)
+; CHECK-NEXT: store i8 3, i8* %p2
+  store i8 3, i8* %p2
+  br label %e
+
+e:
+; 8 = MemoryPhi({c,4},{d,5})
+; FIXME: This should be MemoryUse(1)
+; CHECK: MemoryUse(8)
+; CHECK-NEXT: load i8, i8* %p1
+  load i8, i8* %p1
+  ret void
+}
+
+; CHECK-LABEL: define void @looped
+define void @looped(i8* noalias %p1, i8* noalias %p2) {
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i8 0, i8* %p1
+  store i8 0, i8* %p1
+  br label %loop.1
+
+loop.1:
+; CHECK: 7 = MemoryPhi({%0,1},{loop.3,4})
+; CHECK: 2 = MemoryDef(7)
+; CHECK-NEXT: store i8 0, i8* %p2
+  store i8 0, i8* %p2
+  br i1 undef, label %loop.2, label %loop.3
+
+loop.2:
+; CHECK: 6 = MemoryPhi({loop.1,2},{loop.3,4})
+; CHECK: 3 = MemoryDef(6)
+; CHECK-NEXT: store i8 1, i8* %p2
+  store i8 1, i8* %p2
+  br label %loop.3
+
+loop.3:
+; CHECK: 5 = MemoryPhi({loop.1,2},{loop.2,3})
+; CHECK: 4 = MemoryDef(5)
+; CHECK-NEXT: store i8 2, i8* %p2
+  store i8 2, i8* %p2
+; FIXME: This should be MemoryUse(1)
+; CHECK: MemoryUse(5)
+; CHECK-NEXT: load i8, i8* %p1
+  load i8, i8* %p1
+  br i1 undef, label %loop.2, label %loop.1
+}