From fff1363ba0ae50da3f8f7b732c90e47e504f18a9 Mon Sep 17 00:00:00 2001 From: Max Kazantsev Date: Fri, 19 Mar 2021 11:29:48 +0700 Subject: [PATCH] [SCEV] Add false->any implication By definition of Implication operator, `false -> true` and `false -> false`. It means that `false` implies any predicate, no matter true or false. We don't need to go any further trying to prove the statement we need and just always say that `false` implies it in this case. In practice it means that we are trying to prove something guarded by `false` condition, which means that this code is unreachable, and we can safely prove any fact or perform any transform in this code. Differential Revision: https://reviews.llvm.org/D98706 Reviewed By: lebedev.ri --- llvm/lib/Analysis/ScalarEvolution.cpp | 5 +++++ .../max-backedge-taken-count-guard-info.ll | 10 +++++----- .../Transforms/IndVarSimplify/2011-10-27-lftrnull.ll | 5 +---- llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll | 20 +++++++------------- llvm/test/Transforms/IndVarSimplify/trivial-guard.ll | 12 +++--------- 5 files changed, 21 insertions(+), 31 deletions(-) diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index ecf0033..7dd05d0 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -10137,6 +10137,11 @@ bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Value *FoundCondValue, bool Inverse, const Instruction *Context) { + // False conditions implies anything. Do not bother analyzing it further. + if (FoundCondValue == + ConstantInt::getBool(FoundCondValue->getContext(), Inverse)) + return true; + if (!PendingLoopPredicates.insert(FoundCondValue).second) return false; diff --git a/llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll b/llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll index 98b4dc3..28723ed 100644 --- a/llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll +++ b/llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll @@ -531,16 +531,16 @@ define void @crash(i8* %ptr) { ; CHECK-LABEL: 'crash' ; CHECK-NEXT: Classifying expressions for: @crash ; CHECK-NEXT: %text.addr.5 = phi i8* [ %incdec.ptr112, %while.cond111 ], [ null, %while.body ] -; CHECK-NEXT: --> {null,+,-1}<%while.cond111> U: full-set S: full-set Exits: <> LoopDispositions: { %while.cond111: Computable, %while.body: Variant } +; CHECK-NEXT: --> {null,+,-1}<%while.cond111> U: full-set S: full-set Exits: <> LoopDispositions: { %while.cond111: Computable, %while.body: Variant } ; CHECK-NEXT: %incdec.ptr112 = getelementptr inbounds i8, i8* %text.addr.5, i64 -1 -; CHECK-NEXT: --> {(-1 + null),+,-1}<%while.cond111> U: full-set S: full-set Exits: <> LoopDispositions: { %while.cond111: Computable, %while.body: Variant } +; CHECK-NEXT: --> {(-1 + null),+,-1}<%while.cond111> U: full-set S: full-set Exits: <> LoopDispositions: { %while.cond111: Computable, %while.body: Variant } ; CHECK-NEXT: %lastout.2271 = phi i8* [ %incdec.ptr126, %while.body125 ], [ %ptr, %while.end117 ] -; CHECK-NEXT: --> {%ptr,+,1}<%while.body125> U: full-set S: full-set Exits: {(-2 + null),+,-1}<%while.cond111> LoopDispositions: { %while.body125: Computable } +; CHECK-NEXT: --> {%ptr,+,1}<%while.body125> U: full-set S: full-set Exits: {(-2 + null),+,-1}<%while.cond111> LoopDispositions: { %while.body125: Computable } ; CHECK-NEXT: %incdec.ptr126 = getelementptr inbounds i8, i8* %lastout.2271, i64 1 -; CHECK-NEXT: --> {(1 + %ptr),+,1}<%while.body125> U: [1,0) S: [1,0) Exits: {(-1 + null),+,-1}<%while.cond111> LoopDispositions: { %while.body125: Computable } +; CHECK-NEXT: --> {(1 + %ptr),+,1}<%while.body125> U: [1,0) S: [1,0) Exits: {(-1 + null),+,-1}<%while.cond111> LoopDispositions: { %while.body125: Computable } ; CHECK-NEXT: Determining loop execution counts for: @crash ; CHECK-NEXT: Loop %while.body125: backedge-taken count is {(-2 + (-1 * %ptr) + null),+,-1}<%while.cond111> -; CHECK-NEXT: Loop %while.body125: max backedge-taken count is -1 +; CHECK-NEXT: Loop %while.body125: max backedge-taken count is -2 ; CHECK-NEXT: Loop %while.body125: Predicated backedge-taken count is {(-2 + (-1 * %ptr) + null),+,-1}<%while.cond111> ; CHECK-NEXT: Predicates: ; CHECK: Loop %while.body125: Trip multiple is 1 diff --git a/llvm/test/Transforms/IndVarSimplify/2011-10-27-lftrnull.ll b/llvm/test/Transforms/IndVarSimplify/2011-10-27-lftrnull.ll index d56e985..ed2b874 100644 --- a/llvm/test/Transforms/IndVarSimplify/2011-10-27-lftrnull.ll +++ b/llvm/test/Transforms/IndVarSimplify/2011-10-27-lftrnull.ll @@ -28,16 +28,13 @@ define void @test() nounwind { ; CHECK-NEXT: br label [[FOR_BODY21_I:%.*]] ; CHECK: for.body21.i: ; CHECK-NEXT: [[DESTYPIXELPTR_010_I:%.*]] = phi i8* [ null, [[FOR_BODY21_LR_PH_I]] ], [ [[INCDEC_PTR_I:%.*]], [[IF_END_I126:%.*]] ] -; CHECK-NEXT: [[X_09_I:%.*]] = phi i32 [ 0, [[FOR_BODY21_LR_PH_I]] ], [ [[INC_I125:%.*]], [[IF_END_I126]] ] ; CHECK-NEXT: br i1 undef, label [[IF_END_I126]], label [[IF_ELSE_I124:%.*]] ; CHECK: if.else.i124: ; CHECK-NEXT: store i8 undef, i8* [[DESTYPIXELPTR_010_I]], align 1 ; CHECK-NEXT: br label [[IF_END_I126]] ; CHECK: if.end.i126: ; CHECK-NEXT: [[INCDEC_PTR_I]] = getelementptr inbounds i8, i8* [[DESTYPIXELPTR_010_I]], i32 1 -; CHECK-NEXT: [[INC_I125]] = add nuw i32 [[X_09_I]], 1 -; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i32 [[INC_I125]], undef -; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_BODY21_I]], label [[FOR_END_I129_LOOPEXIT:%.*]] +; CHECK-NEXT: br i1 true, label [[FOR_BODY21_I]], label [[FOR_END_I129_LOOPEXIT:%.*]] ; CHECK: for.end.i129.loopexit: ; CHECK-NEXT: br label [[FOR_END_I129]] ; CHECK: for.end.i129: diff --git a/llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll b/llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll index e51ee24..6d7bbce 100644 --- a/llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll +++ b/llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll @@ -9,8 +9,8 @@ define i32 @testDiv(i8* %p, i64* %p1) { ; CHECK-NEXT: br label [[LOOP1:%.*]] ; CHECK: loop1: ; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP2_EXIT:%.*]] ], [ 8, [[ENTRY:%.*]] ] -; CHECK-NEXT: [[EXITCOND3:%.*]] = icmp eq i64 [[INDVARS_IV]], 15 -; CHECK-NEXT: br i1 [[EXITCOND3]], label [[EXIT:%.*]], label [[GENERAL_CASE24:%.*]] +; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV]], 15 +; CHECK-NEXT: br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[GENERAL_CASE24:%.*]] ; CHECK: general_case24: ; CHECK-NEXT: br i1 false, label [[LOOP2_PREHEADER:%.*]], label [[LOOP2_EXIT]] ; CHECK: loop2.preheader: @@ -19,14 +19,11 @@ define i32 @testDiv(i8* %p, i64* %p1) { ; CHECK-NEXT: br label [[LOOP2:%.*]] ; CHECK: loop2: ; CHECK-NEXT: [[INDVARS_IV1:%.*]] = phi i64 [ [[TMP1]], [[LOOP2_PREHEADER]] ], [ [[INDVARS_IV_NEXT2:%.*]], [[LOOP2]] ] -; CHECK-NEXT: [[LOCAL_2_57:%.*]] = phi i32 [ [[I7:%.*]], [[LOOP2]] ], [ 1, [[LOOP2_PREHEADER]] ] -; CHECK-NEXT: [[INDVARS_IV_NEXT2]] = add nsw i64 [[INDVARS_IV1]], -1 +; CHECK-NEXT: [[INDVARS_IV_NEXT2]] = add nuw nsw i64 [[INDVARS_IV1]], -1 ; CHECK-NEXT: [[I4:%.*]] = load atomic i64, i64* [[P1:%.*]] unordered, align 8 ; CHECK-NEXT: [[I6:%.*]] = sub i64 [[I4]], [[INDVARS_IV_NEXT2]] ; CHECK-NEXT: store atomic i64 [[I6]], i64* [[P1]] unordered, align 8 -; CHECK-NEXT: [[I7]] = add nuw nsw i32 [[LOCAL_2_57]], 1 -; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i32 [[I7]], 9 -; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP2_EXIT_LOOPEXIT:%.*]], label [[LOOP2]] +; CHECK-NEXT: br i1 false, label [[LOOP2_EXIT_LOOPEXIT:%.*]], label [[LOOP2]] ; CHECK: loop2.exit.loopexit: ; CHECK-NEXT: br label [[LOOP2_EXIT]] ; CHECK: loop2.exit: @@ -79,8 +76,8 @@ define i32 @testRem(i8* %p, i64* %p1) { ; CHECK-NEXT: br label [[LOOP1:%.*]] ; CHECK: loop1: ; CHECK-NEXT: [[LOCAL_0_:%.*]] = phi i32 [ 8, [[ENTRY:%.*]] ], [ [[I9:%.*]], [[LOOP2_EXIT:%.*]] ] -; CHECK-NEXT: [[EXITCOND1:%.*]] = icmp eq i32 [[LOCAL_0_]], 15 -; CHECK-NEXT: br i1 [[EXITCOND1]], label [[EXIT:%.*]], label [[GENERAL_CASE24:%.*]] +; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i32 [[LOCAL_0_]], 15 +; CHECK-NEXT: br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[GENERAL_CASE24:%.*]] ; CHECK: general_case24: ; CHECK-NEXT: br i1 false, label [[LOOP2_PREHEADER:%.*]], label [[LOOP2_EXIT]] ; CHECK: loop2.preheader: @@ -93,14 +90,11 @@ define i32 @testRem(i8* %p, i64* %p1) { ; CHECK-NEXT: br label [[LOOP2:%.*]] ; CHECK: loop2: ; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[TMP5]], [[LOOP2_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[LOOP2]] ] -; CHECK-NEXT: [[LOCAL_2_57:%.*]] = phi i32 [ [[I7:%.*]], [[LOOP2]] ], [ 1, [[LOOP2_PREHEADER]] ] ; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1 ; CHECK-NEXT: [[I4:%.*]] = load atomic i64, i64* [[P1:%.*]] unordered, align 8 ; CHECK-NEXT: [[I6:%.*]] = sub i64 [[I4]], [[INDVARS_IV_NEXT]] ; CHECK-NEXT: store atomic i64 [[I6]], i64* [[P1]] unordered, align 8 -; CHECK-NEXT: [[I7]] = add nuw nsw i32 [[LOCAL_2_57]], 1 -; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i32 [[I7]], 9 -; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP2_EXIT_LOOPEXIT:%.*]], label [[LOOP2]] +; CHECK-NEXT: br i1 false, label [[LOOP2_EXIT_LOOPEXIT:%.*]], label [[LOOP2]] ; CHECK: loop2.exit.loopexit: ; CHECK-NEXT: br label [[LOOP2_EXIT]] ; CHECK: loop2.exit: diff --git a/llvm/test/Transforms/IndVarSimplify/trivial-guard.ll b/llvm/test/Transforms/IndVarSimplify/trivial-guard.ll index 7506259..60a0c2a 100644 --- a/llvm/test/Transforms/IndVarSimplify/trivial-guard.ll +++ b/llvm/test/Transforms/IndVarSimplify/trivial-guard.ll @@ -21,11 +21,8 @@ define void @test_01(i32 %x) { ; CHECK-NEXT: [[LOOP_COND_1:%.*]] = call i1 @cond() ; CHECK-NEXT: br i1 [[LOOP_COND_1]], label [[LOOP_1]], label [[EXIT_LOOPEXIT:%.*]] ; CHECK: loop.2: -; CHECK-NEXT: [[IV_2:%.*]] = phi i32 [ [[IV_NEXT_2:%.*]], [[GUARDED_2:%.*]] ], [ 0, [[LOOP_2_PREHEADER]] ] -; CHECK-NEXT: [[CHECK_2:%.*]] = icmp slt i32 [[IV_2]], [[X]] -; CHECK-NEXT: br i1 [[CHECK_2]], label [[GUARDED_2]], label [[FAIL_LOOPEXIT1:%.*]] +; CHECK-NEXT: br i1 true, label [[GUARDED_2:%.*]], label [[FAIL_LOOPEXIT1:%.*]] ; CHECK: guarded.2: -; CHECK-NEXT: [[IV_NEXT_2]] = add nuw i32 [[IV_2]], 1 ; CHECK-NEXT: [[LOOP_COND_2:%.*]] = call i1 @cond() ; CHECK-NEXT: br i1 [[LOOP_COND_2]], label [[LOOP_2]], label [[EXIT_LOOPEXIT2:%.*]] ; CHECK: exit.loopexit: @@ -80,16 +77,13 @@ define void @test_02(i32 %x) { ; CHECK: loop.1.preheader: ; CHECK-NEXT: br label [[LOOP_1:%.*]] ; CHECK: loop.1: -; CHECK-NEXT: [[IV_1:%.*]] = phi i32 [ [[IV_NEXT_1:%.*]], [[GUARDED_1:%.*]] ], [ 0, [[LOOP_1_PREHEADER]] ] -; CHECK-NEXT: [[CHECK_1:%.*]] = icmp slt i32 [[IV_1]], [[X:%.*]] -; CHECK-NEXT: br i1 [[CHECK_1]], label [[GUARDED_1]], label [[FAIL_LOOPEXIT:%.*]] +; CHECK-NEXT: br i1 true, label [[GUARDED_1:%.*]], label [[FAIL_LOOPEXIT:%.*]] ; CHECK: guarded.1: -; CHECK-NEXT: [[IV_NEXT_1]] = add nuw i32 [[IV_1]], 1 ; CHECK-NEXT: [[LOOP_COND_1:%.*]] = call i1 @cond() ; CHECK-NEXT: br i1 [[LOOP_COND_1]], label [[LOOP_1]], label [[EXIT_LOOPEXIT:%.*]] ; CHECK: loop.2: ; CHECK-NEXT: [[IV_2:%.*]] = phi i32 [ [[IV_NEXT_2:%.*]], [[GUARDED_2:%.*]] ], [ 0, [[LOOP_2_PREHEADER]] ] -; CHECK-NEXT: [[CHECK_2:%.*]] = icmp slt i32 [[IV_2]], [[X]] +; CHECK-NEXT: [[CHECK_2:%.*]] = icmp slt i32 [[IV_2]], [[X:%.*]] ; CHECK-NEXT: br i1 [[CHECK_2]], label [[GUARDED_2]], label [[FAIL_LOOPEXIT1:%.*]] ; CHECK: guarded.2: ; CHECK-NEXT: [[IV_NEXT_2]] = add nuw i32 [[IV_2]], 1 -- 2.7.4