GVN-hoist: fix store past load dependence analysis (PR30216, PR30499)

This is a refreshed version of a patch that was reverted: it fixes
the problems reported in both PR30216 and PR30499, and
contains all the test-cases from both bugs.

To hoist stores past loads, we used to search for potential
conflicting loads on the hoisting path by following a MemorySSA
def-def link from the store to be hoisted to the previous
defining memory access, and from there we followed the def-use
chains to all the uses that occur on the hoisting path. The
problem is that the def-def link may point to a store that does
not alias with the store to be hoisted, and so the loads that are
walked may not alias with the store to be hoisted, and even as in
the testcase of PR30216, the loads that may alias with the store
to be hoisted are not visited.

The current patch visits all loads on the path from the store to
be hoisted to the hoisting position and uses the alias analysis
to ask whether the store may alias the load. I was not able to
use the MemorySSA functionality to ask for whether load and
store are clobbered: I'm not sure which function to call, so I
used a call to AA->isNoAlias().

Store past store is still working as before using a MemorySSA
query: I added an extra test to pr30216.ll to make sure store
past store does not regress.

Tested on x86_64-linux with check and a test-suite run.

Differential Revision: https://reviews.llvm.org/D25476

llvm-svn: 283965

2 files changed, 82 insertions, 0 deletions

diff --git a/llvm/test/Transforms/GVNHoist/pr30216.ll b/llvm/test/Transforms/GVNHoist/pr30216.ll
new file mode 100644
index 00000000000..a13efdb9d76
--- /dev/null
+++ b/llvm/test/Transforms/GVNHoist/pr30216.ll
@@ -0,0 +1,52 @@
+; RUN: opt -S -gvn-hoist < %s | FileCheck %s
+
+; Make sure the two stores @B do not get hoisted past the load @B.
+
+; CHECK-LABEL: define i8* @Foo
+; CHECK: store
+; CHECK: store
+; CHECK: load
+; CHECK: store
+
+@A = external global i8
+@B = external global i8*
+
+define i8* @Foo() {
+  store i8 0, i8* @A
+  br i1 undef, label %if.then, label %if.else
+
+if.then:
+  store i8* null, i8** @B
+  ret i8* null
+
+if.else:
+  %1 = load i8*, i8** @B
+  store i8* null, i8** @B
+  ret i8* %1
+}
+
+; Make sure the two stores @B do not get hoisted past the store @GlobalVar.
+
+; CHECK-LABEL: define i8* @Fun
+; CHECK: store
+; CHECK: store
+; CHECK: store
+; CHECK: store
+; CHECK: load
+
+@GlobalVar = internal global i8 0
+
+define i8* @Fun() {
+  store i8 0, i8* @A
+  br i1 undef, label %if.then, label %if.else
+
+if.then:
+  store i8* null, i8** @B
+  ret i8* null
+
+if.else:
+  store i8 0, i8* @GlobalVar
+  store i8* null, i8** @B
+  %1 = load i8*, i8** @B
+  ret i8* %1
+}
diff --git a/llvm/test/Transforms/GVNHoist/pr30499.ll b/llvm/test/Transforms/GVNHoist/pr30499.ll
new file mode 100644
index 00000000000..591e0e4bdd0
--- /dev/null
+++ b/llvm/test/Transforms/GVNHoist/pr30499.ll
@@ -0,0 +1,30 @@
+; RUN: opt -S -gvn-hoist < %s
+
+define void @_Z3fn2v() #0 {
+entry:
+  %a = alloca i8*, align 8
+  %b = alloca i32, align 4
+  %0 = load i8*, i8** %a, align 8
+  store i8 0, i8* %0, align 1
+  %1 = load i32, i32* %b, align 4
+  %tobool = icmp ne i32 %1, 0
+  br i1 %tobool, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call = call i64 @_Z3fn1v() #2
+  %conv = trunc i64 %call to i32
+  store i32 %conv, i32* %b, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  %2 = load i8*, i8** %a, align 8
+  store i8 0, i8* %2, align 1
+  ret void
+}
+
+; Function Attrs: nounwind readonly
+declare i64 @_Z3fn1v() #1
+
+attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { nounwind readonly "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { nounwind readonly }