[SCEV] Look through single value PHIs.
Now that SCEVExpander can preserve LCSSA form,
we do not have to worry about LCSSA form when
trying to look through PHIs. SCEVExpander will take
care of inserting LCSSA PHI nodes as required.
This increases precision of the analysis in some cases.
Reviewed By: mkazantsev, bmahjour
Differential Revision: https://reviews.llvm.org/D71539
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 75d2d39..43571e4 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -5112,13 +5112,8 @@
if (const SCEV *S = createNodeFromSelectLikePHI(PN))
return S;
- // If the PHI has a single incoming value, follow that value, unless the
- // PHI's incoming blocks are in a different loop, in which case doing so
- // risks breaking LCSSA form. Instcombine would normally zap these, but
- // it doesn't have DominatorTree information, so it may miss cases.
if (Value *V = SimplifyInstruction(PN, {getDataLayout(), &TLI, &DT, &AC}))
- if (LI.replacementPreservesLCSSAForm(PN, V))
- return getSCEV(V);
+ return getSCEV(V);
// If it's not a loop phi, we can't handle it yet.
return getUnknown(PN);
diff --git a/llvm/test/Analysis/ScalarEvolution/solve-quadratic-i1.ll b/llvm/test/Analysis/ScalarEvolution/solve-quadratic-i1.ll
index 525b8df..1535f81 100644
--- a/llvm/test/Analysis/ScalarEvolution/solve-quadratic-i1.ll
+++ b/llvm/test/Analysis/ScalarEvolution/solve-quadratic-i1.ll
@@ -58,9 +58,9 @@
; CHECK-NEXT: %v6 = add nuw nsw i32 %v1, 1
; CHECK-NEXT: --> {4,+,1}<nuw><nsw><%b1> U: [4,7) S: [4,7) Exits: 6 LoopDispositions: { %b1: Computable }
; CHECK-NEXT: %v7 = phi i32 [ %v1, %b1 ]
-; CHECK-NEXT: --> %v7 U: [3,6) S: [3,6)
+; CHECK-NEXT: --> {3,+,1}<nuw><nsw><%b1> U: [3,6) S: [3,6) --> 5 U: [5,6) S: [5,6)
; CHECK-NEXT: %v8 = phi i16 [ %v3, %b1 ]
-; CHECK-NEXT: --> %v8 U: full-set S: full-set
+; CHECK-NEXT: --> {3,+,4,+,1}<%b1> U: full-set S: full-set --> 12 U: [12,13) S: [12,13)
; CHECK-NEXT: Determining loop execution counts for: @f1
; CHECK-NEXT: Loop %b3: <multiple exits> Unpredictable backedge-taken count.
; CHECK-NEXT: Loop %b3: Unpredictable max backedge-taken count.
diff --git a/llvm/test/Analysis/ScalarEvolution/solve-quadratic-overflow.ll b/llvm/test/Analysis/ScalarEvolution/solve-quadratic-overflow.ll
index 331bf31..7596e9d 100644
--- a/llvm/test/Analysis/ScalarEvolution/solve-quadratic-overflow.ll
+++ b/llvm/test/Analysis/ScalarEvolution/solve-quadratic-overflow.ll
@@ -13,11 +13,11 @@
; CHECK-NEXT: %v3 = mul i16 %v2, %v2
; CHECK-NEXT: --> {1,+,3,+,2}<%b1> U: full-set S: full-set Exits: 0 LoopDispositions: { %b1: Computable }
; CHECK-NEXT: %v5 = phi i16 [ %v2, %b1 ]
-; CHECK-NEXT: --> %v5 U: [-256,0) S: [-256,0)
+; CHECK-NEXT: --> {-1,+,-1}<%b1> U: [-256,0) S: [-256,0) --> -256 U: [-256,-255) S: [-256,-255)
; CHECK-NEXT: %v6 = phi i16 [ %v3, %b1 ]
-; CHECK-NEXT: --> %v6 U: full-set S: full-set
+; CHECK-NEXT: --> {1,+,3,+,2}<%b1> U: full-set S: full-set --> 0 U: [0,1) S: [0,1)
; CHECK-NEXT: %v7 = sext i16 %v5 to i32
-; CHECK-NEXT: --> (sext i16 %v5 to i32) U: [-256,0) S: [-256,0)
+; CHECK-NEXT: --> {-1,+,-1}<nsw><%b1> U: [-256,0) S: [-256,0) --> -256 U: [-256,-255) S: [-256,-255)
; CHECK-NEXT: Determining loop execution counts for: @f0
; CHECK-NEXT: Loop %b1: backedge-taken count is 255
; CHECK-NEXT: Loop %b1: max backedge-taken count is 255
diff --git a/llvm/test/Transforms/LoopStrengthReduce/funclet.ll b/llvm/test/Transforms/LoopStrengthReduce/funclet.ll
index 0f725a1..ca0a866 100644
--- a/llvm/test/Transforms/LoopStrengthReduce/funclet.ll
+++ b/llvm/test/Transforms/LoopStrengthReduce/funclet.ll
@@ -15,25 +15,21 @@
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[THROW:%.*]]
; CHECK: throw:
-; CHECK-NEXT: [[TMP96:%.*]] = getelementptr inbounds i8, i8* undef, i32 1
; CHECK-NEXT: invoke void @reserve()
; CHECK-NEXT: to label [[THROW]] unwind label [[PAD:%.*]]
; CHECK: pad:
-; CHECK-NEXT: [[PHI2:%.*]] = phi i8* [ [[TMP96]], [[THROW]] ]
; CHECK-NEXT: [[CS:%.*]] = catchswitch within none [label %unreachable] unwind label [[BLAH2:%.*]]
; CHECK: unreachable:
; CHECK-NEXT: [[TMP0:%.*]] = catchpad within [[CS]] []
; CHECK-NEXT: unreachable
; CHECK: blah2:
; CHECK-NEXT: [[CLEANUPPADI4_I_I_I:%.*]] = cleanuppad within none []
-; CHECK-NEXT: [[PHI21:%.*]] = ptrtoint i8* [[PHI2]] to i32
-; CHECK-NEXT: [[TMP1:%.*]] = sub i32 1, [[PHI21]]
-; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, i8* undef, i32 [[TMP1]]
; CHECK-NEXT: br label [[LOOP_BODY:%.*]]
; CHECK: loop_body:
-; CHECK-NEXT: [[LSR_IV:%.*]] = phi i8* [ [[SCEVGEP2:%.*]], [[ITER:%.*]] ], [ [[SCEVGEP]], [[BLAH2]] ]
-; CHECK-NEXT: [[SCEVGEP2]] = getelementptr i8, i8* [[LSR_IV]], i32 -1
-; CHECK-NEXT: [[TMP100:%.*]] = icmp eq i8* [[SCEVGEP2]], null
+; CHECK-NEXT: [[LSR_IV:%.*]] = phi i32 [ [[LSR_IV_NEXT:%.*]], [[ITER:%.*]] ], [ 0, [[BLAH2]] ]
+; CHECK-NEXT: [[LSR_IV_NEXT]] = add nuw nsw i32 [[LSR_IV]], -1
+; CHECK-NEXT: [[LSR_IV_NEXT1:%.*]] = inttoptr i32 [[LSR_IV_NEXT]] to i8*
+; CHECK-NEXT: [[TMP100:%.*]] = icmp eq i8* [[LSR_IV_NEXT1]], null
; CHECK-NEXT: br i1 [[TMP100]], label [[UNWIND_OUT:%.*]], label [[ITER]]
; CHECK: iter:
; CHECK-NEXT: br i1 true, label [[UNWIND_OUT]], label [[LOOP_BODY]]
@@ -78,29 +74,25 @@
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[THROW:%.*]]
; CHECK: throw:
-; CHECK-NEXT: [[TMP96:%.*]] = getelementptr inbounds i8, i8* undef, i32 1
; CHECK-NEXT: invoke void @reserve()
; CHECK-NEXT: to label [[THROW]] unwind label [[PAD:%.*]]
; CHECK: pad:
-; CHECK-NEXT: [[PHI2:%.*]] = phi i8* [ [[TMP96]], [[THROW]] ]
; CHECK-NEXT: [[CS:%.*]] = catchswitch within none [label [[UNREACHABLE:%.*]], label %blah] unwind to caller
; CHECK: unreachable:
; CHECK-NEXT: [[TMP0:%.*]] = catchpad within [[CS]] []
; CHECK-NEXT: unreachable
; CHECK: blah:
; CHECK-NEXT: [[CATCHPAD:%.*]] = catchpad within [[CS]] []
-; CHECK-NEXT: [[PHI21:%.*]] = ptrtoint i8* [[PHI2]] to i32
-; CHECK-NEXT: [[TMP1:%.*]] = sub i32 1, [[PHI21]]
-; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, i8* undef, i32 [[TMP1]]
; CHECK-NEXT: br label [[LOOP_BODY:%.*]]
; CHECK: unwind_out:
; CHECK-NEXT: catchret from [[CATCHPAD]] to label [[LEAVE:%.*]]
; CHECK: leave:
; CHECK-NEXT: ret void
; CHECK: loop_body:
-; CHECK-NEXT: [[LSR_IV:%.*]] = phi i8* [ [[SCEVGEP2:%.*]], [[ITER:%.*]] ], [ [[SCEVGEP]], [[BLAH:%.*]] ]
-; CHECK-NEXT: [[SCEVGEP2]] = getelementptr i8, i8* [[LSR_IV]], i32 -1
-; CHECK-NEXT: [[TMP100:%.*]] = icmp eq i8* [[SCEVGEP2]], null
+; CHECK-NEXT: [[LSR_IV:%.*]] = phi i32 [ [[LSR_IV_NEXT:%.*]], [[ITER:%.*]] ], [ 0, [[BLAH:%.*]] ]
+; CHECK-NEXT: [[LSR_IV_NEXT]] = add nuw nsw i32 [[LSR_IV]], -1
+; CHECK-NEXT: [[LSR_IV_NEXT1:%.*]] = inttoptr i32 [[LSR_IV_NEXT]] to i8*
+; CHECK-NEXT: [[TMP100:%.*]] = icmp eq i8* [[LSR_IV_NEXT1]], null
; CHECK-NEXT: br i1 [[TMP100]], label [[UNWIND_OUT:%.*]], label [[ITER]]
; CHECK: iter:
; CHECK-NEXT: br i1 true, label [[UNWIND_OUT]], label [[LOOP_BODY]]
@@ -146,7 +138,6 @@
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[THROW:%.*]]
; CHECK: throw:
-; CHECK-NEXT: [[TMP96:%.*]] = getelementptr inbounds i8, i8* undef, i32 1
; CHECK-NEXT: invoke void @reserve()
; CHECK-NEXT: to label [[THROW]] unwind label [[PAD:%.*]]
; CHECK: pad:
@@ -155,20 +146,17 @@
; CHECK-NEXT: [[TMP0:%.*]] = catchpad within [[CS]] []
; CHECK-NEXT: unreachable
; CHECK: blug:
-; CHECK-NEXT: [[PHI2:%.*]] = phi i8* [ [[TMP96]], [[PAD]] ]
; CHECK-NEXT: [[CATCHPAD:%.*]] = catchpad within [[CS]] []
-; CHECK-NEXT: [[PHI21:%.*]] = ptrtoint i8* [[PHI2]] to i32
-; CHECK-NEXT: [[TMP1:%.*]] = sub i32 1, [[PHI21]]
-; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, i8* undef, i32 [[TMP1]]
; CHECK-NEXT: br label [[LOOP_BODY:%.*]]
; CHECK: unwind_out:
; CHECK-NEXT: catchret from [[CATCHPAD]] to label [[LEAVE:%.*]]
; CHECK: leave:
; CHECK-NEXT: ret void
; CHECK: loop_body:
-; CHECK-NEXT: [[LSR_IV:%.*]] = phi i8* [ [[SCEVGEP2:%.*]], [[ITER:%.*]] ], [ [[SCEVGEP]], [[BLUG:%.*]] ]
-; CHECK-NEXT: [[SCEVGEP2]] = getelementptr i8, i8* [[LSR_IV]], i32 -1
-; CHECK-NEXT: [[TMP100:%.*]] = icmp eq i8* [[SCEVGEP2]], null
+; CHECK-NEXT: [[LSR_IV:%.*]] = phi i32 [ [[LSR_IV_NEXT:%.*]], [[ITER:%.*]] ], [ 0, [[BLUG:%.*]] ]
+; CHECK-NEXT: [[LSR_IV_NEXT]] = add nuw nsw i32 [[LSR_IV]], -1
+; CHECK-NEXT: [[LSR_IV_NEXT1:%.*]] = inttoptr i32 [[LSR_IV_NEXT]] to i8*
+; CHECK-NEXT: [[TMP100:%.*]] = icmp eq i8* [[LSR_IV_NEXT1]], null
; CHECK-NEXT: br i1 [[TMP100]], label [[UNWIND_OUT:%.*]], label [[ITER]]
; CHECK: iter:
; CHECK-NEXT: br i1 true, label [[UNWIND_OUT]], label [[LOOP_BODY]]
@@ -214,11 +202,9 @@
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[THROW:%.*]]
; CHECK: throw:
-; CHECK-NEXT: [[TMP96:%.*]] = getelementptr inbounds i8, i8* undef, i32 1
; CHECK-NEXT: invoke void @reserve()
; CHECK-NEXT: to label [[THROW]] unwind label [[CATCHPAD:%.*]]
; CHECK: catchpad:
-; CHECK-NEXT: [[PHI2:%.*]] = phi i8* [ [[TMP96]], [[THROW]] ]
; CHECK-NEXT: [[CS:%.*]] = catchswitch within none [label %cp_body] unwind label [[CLEANUPPAD:%.*]]
; CHECK: cp_body:
; CHECK-NEXT: [[TMP0:%.*]] = catchpad within [[CS]] []
@@ -227,14 +213,12 @@
; CHECK-NEXT: [[TMP1:%.*]] = cleanuppad within none []
; CHECK-NEXT: br label [[LOOP_HEAD]]
; CHECK: loop_head:
-; CHECK-NEXT: [[PHI21:%.*]] = ptrtoint i8* [[PHI2]] to i32
-; CHECK-NEXT: [[TMP2:%.*]] = sub i32 1, [[PHI21]]
-; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, i8* undef, i32 [[TMP2]]
; CHECK-NEXT: br label [[LOOP_BODY:%.*]]
; CHECK: loop_body:
-; CHECK-NEXT: [[LSR_IV:%.*]] = phi i8* [ [[SCEVGEP2:%.*]], [[ITER:%.*]] ], [ [[SCEVGEP]], [[LOOP_HEAD]] ]
-; CHECK-NEXT: [[SCEVGEP2]] = getelementptr i8, i8* [[LSR_IV]], i32 -1
-; CHECK-NEXT: [[TMP100:%.*]] = icmp eq i8* [[SCEVGEP2]], null
+; CHECK-NEXT: [[LSR_IV:%.*]] = phi i32 [ [[LSR_IV_NEXT:%.*]], [[ITER:%.*]] ], [ 0, [[LOOP_HEAD]] ]
+; CHECK-NEXT: [[LSR_IV_NEXT]] = add nuw nsw i32 [[LSR_IV]], -1
+; CHECK-NEXT: [[LSR_IV_NEXT1:%.*]] = inttoptr i32 [[LSR_IV_NEXT]] to i8*
+; CHECK-NEXT: [[TMP100:%.*]] = icmp eq i8* [[LSR_IV_NEXT1]], null
; CHECK-NEXT: br i1 [[TMP100]], label [[UNWIND_OUT:%.*]], label [[ITER]]
; CHECK: iter:
; CHECK-NEXT: br i1 true, label [[UNWIND_OUT]], label [[LOOP_BODY]]
