From 8fdac7cb7abbeeaed016ef9eb7a087458e41e33f Mon Sep 17 00:00:00 2001 From: Fangrui Song Date: Mon, 21 Sep 2020 17:18:26 -0700 Subject: [PATCH] Revert D71539 "Recommit "[SCEV] Look through single value PHIs."" This reverts commit 11dccf8d3aa5d55210f8b886fb21926c7a8353ca. A bootstrapped clang crashes (due to ArrayRef::front called on an empty ArrayRef) when compiling some files. Very strangely, this only reproduces with modules. ``` 13 0x0000564d3349e968 llvm::ArrayRef::front() const /proc/self/cwd/llvm/include/llvm/ADT/ArrayRef.h:160:7 14 0x0000564d3349e896 llvm::LoopBase::getHeader() const /proc/self/cwd/llvm/include/llvm/Analysis/LoopInfo.h:104:50 15 0x0000564d3349fd9d llvm::LoopBase::getLoopLatch() const /proc/self/cwd/llvm/include/llvm/Analysis/LoopInfoImpl.h:210:11 16 0x0000564d33593c8a llvm::ScalarEvolution::computeBackedgeTakenCount(llvm::Loop const*, bool) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:6933:15 17 0x0000564d33592ebc llvm::ScalarEvolution::getBackedgeTakenInfo(llvm::Loop const*) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:0:30 18 0x0000564d33593a54 llvm::ScalarEvolution::getBackedgeTakenCount(llvm::Loop const*, llvm::ScalarEvolution::ExitCountKind) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:6487:36 19 0x0000564d32be2402 llvm::ScalarEvolution::getConstantMaxBackedgeTakenCount(llvm::Loop const*) /proc/self/cwd/llvm/include/llvm/Analysis/ScalarEvolution.h:768:5 20 0x0000564d33590807 llvm::ScalarEvolution::getRangeRef(llvm::SCEV const*, llvm::ScalarEvolution::RangeSignHint) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:5495:19 21 0x0000564d320abab7 llvm::ScalarEvolution::getSignedRange(llvm::SCEV const*) /proc/self/cwd/llvm/include/llvm/Analysis/ScalarEvolution.h:840:12 22 0x0000564d335a03aa llvm::ScalarEvolution::isKnownPredicateViaConstantRanges(llvm::CmpInst::Predicate, llvm::SCEV const*, llvm::SCEV const*) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:9239:60 23 0x0000564d33586a80 llvm::ScalarEvolution::isKnownViaNonRecursiveReasoning(llvm::CmpInst::Predicate, llvm::SCEV const*, llvm::SCEV const*) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:10284:60 ``` --- 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, 43 insertions(+), 22 deletions(-) diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 4666419..3bf7f20 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -5114,8 +5114,13 @@ 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})) - return getSCEV(V); + if (LI.replacementPreservesLCSSAForm(PN, 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 1535f81..525b8df 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: --> {3,+,1}<%b1> U: [3,6) S: [3,6) --> 5 U: [5,6) S: [5,6) +; CHECK-NEXT: --> %v7 U: [3,6) S: [3,6) ; CHECK-NEXT: %v8 = phi i16 [ %v3, %b1 ] -; CHECK-NEXT: --> {3,+,4,+,1}<%b1> U: full-set S: full-set --> 12 U: [12,13) S: [12,13) +; CHECK-NEXT: --> %v8 U: full-set S: full-set ; 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 7596e9d..331bf31 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: --> {-1,+,-1}<%b1> U: [-256,0) S: [-256,0) --> -256 U: [-256,-255) S: [-256,-255) +; CHECK-NEXT: --> %v5 U: [-256,0) S: [-256,0) ; CHECK-NEXT: %v6 = phi i16 [ %v3, %b1 ] -; CHECK-NEXT: --> {1,+,3,+,2}<%b1> U: full-set S: full-set --> 0 U: [0,1) S: [0,1) +; CHECK-NEXT: --> %v6 U: full-set S: full-set ; CHECK-NEXT: %v7 = sext i16 %v5 to i32 -; CHECK-NEXT: --> {-1,+,-1}<%b1> U: [-256,0) S: [-256,0) --> -256 U: [-256,-255) S: [-256,-255) +; CHECK-NEXT: --> (sext i16 %v5 to i32) U: [-256,0) S: [-256,0) ; 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 ca0a866..0f725a1 100644 --- a/llvm/test/Transforms/LoopStrengthReduce/funclet.ll +++ b/llvm/test/Transforms/LoopStrengthReduce/funclet.ll @@ -15,21 +15,25 @@ 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 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: [[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: br i1 [[TMP100]], label [[UNWIND_OUT:%.*]], label [[ITER]] ; CHECK: iter: ; CHECK-NEXT: br i1 true, label [[UNWIND_OUT]], label [[LOOP_BODY]] @@ -74,25 +78,29 @@ 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 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: [[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: br i1 [[TMP100]], label [[UNWIND_OUT:%.*]], label [[ITER]] ; CHECK: iter: ; CHECK-NEXT: br i1 true, label [[UNWIND_OUT]], label [[LOOP_BODY]] @@ -138,6 +146,7 @@ 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: @@ -146,17 +155,20 @@ 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 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: [[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: br i1 [[TMP100]], label [[UNWIND_OUT:%.*]], label [[ITER]] ; CHECK: iter: ; CHECK-NEXT: br i1 true, label [[UNWIND_OUT]], label [[LOOP_BODY]] @@ -202,9 +214,11 @@ 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]] [] @@ -213,12 +227,14 @@ 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 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: [[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: br i1 [[TMP100]], label [[UNWIND_OUT:%.*]], label [[ITER]] ; CHECK: iter: ; CHECK-NEXT: br i1 true, label [[UNWIND_OUT]], label [[LOOP_BODY]] -- 2.7.4