From e441b7a7a0a72c28daf5a8e594559c667e5b4534 Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Wed, 12 Aug 2020 08:46:07 +0100 Subject: [PATCH] [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 --- llvm/lib/Analysis/ScalarEvolution.cpp | 7 +--- .../Analysis/ScalarEvolution/solve-quadratic-i1.ll | 4 +- .../ScalarEvolution/solve-quadratic-overflow.ll | 6 +-- llvm/test/Transforms/LoopStrengthReduce/funclet.ll | 48 ++++++++-------------- 4 files changed, 22 insertions(+), 43 deletions(-) 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 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { 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 @@ b2: ; preds = %b1 ; CHECK-NEXT: %v6 = add nuw nsw i32 %v1, 1 ; CHECK-NEXT: --> {4,+,1}<%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}<%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: 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}<%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 @@ define void @f() personality i32 (...)* @_except_handler3 { ; 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 @@ define void @g() personality i32 (...)* @_except_handler3 { ; 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 @@ define void @h() personality i32 (...)* @_except_handler3 { ; 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 @@ define void @h() personality i32 (...)* @_except_handler3 { ; 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 @@ define void @i() personality i32 (...)* @_except_handler3 { ; 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 @@ define void @i() personality i32 (...)* @_except_handler3 { ; 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]] -- 2.7.4