[SCEV] Try to reuse existing value during SCEV expansion

Current SCEV expansion will expand SCEV as a sequence of operations
and doesn't utilize the value already existed. This will introduce
redundent computation which may not be cleaned up throughly by
following optimizations.

This patch introduces an ExprValueMap which is a map from SCEV to the
set of equal values with the same SCEV. When a SCEV is expanded, the
set of values is checked and reused whenever possible before generating
a sequence of operations.

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

llvm-svn: 259662

6 files changed, 11 insertions, 20 deletions

diff --git a/llvm/test/Transforms/IRCE/decrementing-loop.ll b/llvm/test/Transforms/IRCE/decrementing-loop.ll
index 6ff3e76c754..a3a03b182a5 100644
--- a/llvm/test/Transforms/IRCE/decrementing-loop.ll
+++ b/llvm/test/Transforms/IRCE/decrementing-loop.ll
@@ -28,7 +28,6 @@ define void @decrementing_loop(i32 *%arr, i32 *%a_len_ptr, i32 %n) {
   ret void
 
 ; CHECK: loop.preheader:
-; CHECK:   [[indvar_start:[^ ]+]] = add i32 %n, -1
 ; CHECK:   [[not_len:[^ ]+]] = sub i32 -1, %len
 ; CHECK:   [[not_n:[^ ]+]] = sub i32 -1, %n
 ; CHECK:   [[not_len_hiclamp_cmp:[^ ]+]] = icmp sgt i32 [[not_len]], [[not_n]]
diff --git a/llvm/test/Transforms/IndVarSimplify/lftr-address-space-pointers.ll b/llvm/test/Transforms/IndVarSimplify/lftr-address-space-pointers.ll
index feb4b35a20a..52743073d55 100644
--- a/llvm/test/Transforms/IndVarSimplify/lftr-address-space-pointers.ll
+++ b/llvm/test/Transforms/IndVarSimplify/lftr-address-space-pointers.ll
@@ -11,7 +11,7 @@ entry:
   br i1 %cmp1, label %for.body, label %for.end
 
 ; Make sure the added GEP has the right index type
-; CHECK: %lftr.limit = getelementptr i8, i8 addrspace(2)* %base, i8 %0
+; CHECK: %lftr.limit = getelementptr i8, i8 addrspace(2)* %base, i8 %idx.trunc
 
 ; CHECK: for.body:
 ; CHECK: phi i8 addrspace(2)*
@@ -43,7 +43,7 @@ entry:
   br i1 %cmp1, label %for.body, label %for.end
 
 ; Make sure the added GEP has the right index type
-; CHECK: %lftr.limit = getelementptr i8, i8 addrspace(3)* %base, i16 %0
+; CHECK: %lftr.limit = getelementptr i8, i8 addrspace(3)* %base, i16 %idx.trunc
 
 ; CHECK: for.body:
 ; CHECK: phi i8 addrspace(3)*
diff --git a/llvm/test/Transforms/IndVarSimplify/pr24783.ll b/llvm/test/Transforms/IndVarSimplify/pr24783.ll
index 637cb1e196c..2c19aada35e 100644
--- a/llvm/test/Transforms/IndVarSimplify/pr24783.ll
+++ b/llvm/test/Transforms/IndVarSimplify/pr24783.ll
@@ -6,9 +6,6 @@ target triple = "powerpc64-unknown-linux-gnu"
 define void @f(i32* %end.s, i8** %loc, i32 %p) {
 ; CHECK-LABEL: @f(
 entry:
-; CHECK:  [[P_SEXT:%[0-9a-z]+]] = sext i32 %p to i64
-; CHECK:  [[END:%[0-9a-z]+]] = getelementptr i32, i32* %end.s, i64 [[P_SEXT]]
-
   %end = getelementptr inbounds i32, i32* %end.s, i32 %p
   %init = bitcast i32* %end.s to i8*
   br label %while.body.i
@@ -22,7 +19,7 @@ while.body.i:
 
 loop.exit:
 ; CHECK: loop.exit:
-; CHECK: [[END_BCASTED:%[a-z0-9]+]] = bitcast i32* %scevgep to i8*
+; CHECK: [[END_BCASTED:%[a-z0-9]+]] = bitcast i32* %end to i8*
 ; CHECK: store i8* [[END_BCASTED]], i8** %loc
   %ptr.inc.lcssa = phi i8* [ %ptr.inc, %while.body.i ]
   store i8* %ptr.inc.lcssa, i8** %loc
diff --git a/llvm/test/Transforms/IndVarSimplify/udiv.ll b/llvm/test/Transforms/IndVarSimplify/udiv.ll
index 45c703c99dd..b3f2c2a6a66 100644
--- a/llvm/test/Transforms/IndVarSimplify/udiv.ll
+++ b/llvm/test/Transforms/IndVarSimplify/udiv.ll
@@ -127,12 +127,12 @@ declare i32 @atoi(i8* nocapture) nounwind readonly
 
 declare i32 @printf(i8* nocapture, ...) nounwind
 
-; IndVars shouldn't be afraid to emit a udiv here, since there's a udiv in
-; the original code.
+; IndVars doesn't emit a udiv in for.body.preheader since SCEVExpander::expand will
+; find out there's already a udiv in the original code.
 
 ; CHECK-LABEL: @foo(
 ; CHECK: for.body.preheader:
-; CHECK-NEXT: udiv
+; CHECK-NOT: udiv
 
 define void @foo(double* %p, i64 %n) nounwind {
 entry:
diff --git a/llvm/test/Transforms/IndVarSimplify/ult-sub-to-eq.ll b/llvm/test/Transforms/IndVarSimplify/ult-sub-to-eq.ll
index 7272ef1ec13..30dcbf50088 100644
--- a/llvm/test/Transforms/IndVarSimplify/ult-sub-to-eq.ll
+++ b/llvm/test/Transforms/IndVarSimplify/ult-sub-to-eq.ll
@@ -32,15 +32,9 @@ for.end:                                          ; preds = %for.body, %entry
 
 ; CHECK-LABEL: @test1(
 
-; First check that we move the sub into the preheader, it doesn't have to be
-; executed if %cmp4 == false
-; CHECK: for.body.preheader:
-; CHECK: sub i32 %data_len, %sample
-; CHECK: br label %for.body
-
-; Second, check that we turn the IV test into an eq.
+; check that we turn the IV test into an eq.
 ; CHECK: %lftr.wideiv = trunc i64 %indvars.iv.next to i32
-; CHECK: %exitcond = icmp ne i32 %lftr.wideiv, %0
+; CHECK: %exitcond = icmp ne i32 %lftr.wideiv, %sub
 ; CHECK: br i1 %exitcond, label %for.body, label %for.end.loopexit
 }
 
diff --git a/llvm/test/Transforms/LoopStrengthReduce/post-inc-icmpzero.ll b/llvm/test/Transforms/LoopStrengthReduce/post-inc-icmpzero.ll
index 466566ed8a0..fbf55fd81d2 100644
--- a/llvm/test/Transforms/LoopStrengthReduce/post-inc-icmpzero.ll
+++ b/llvm/test/Transforms/LoopStrengthReduce/post-inc-icmpzero.ll
@@ -4,8 +4,9 @@
 ; LSR should properly handle the post-inc offset when folding the
 ; non-IV operand of an icmp into the IV.
 
-; CHECK:   [[r1:%[a-z0-9]+]] = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
-; CHECK:   [[r2:%[a-z0-9]+]] = lshr i64 [[r1]], 1
+; CHECK:   [[r1:%[a-z0-9\.]+]] = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
+; CHECK:   [[r2:%[a-z0-9\.]+]] = lshr exact i64 [[r1]], 1
+; CHECK: for.body.lr.ph:
 ; CHECK:   [[r3:%[a-z0-9]+]] = shl i64 [[r2]], 1
 ; CHECK:   br label %for.body
 ; CHECK: for.body: