From 4d0c0e6cc250e0637548f8a8519a95f15b6fab2e Mon Sep 17 00:00:00 2001 From: Roman Lebedev Date: Fri, 11 Feb 2022 15:48:36 +0300 Subject: [PATCH] [SCEV] `createNodeForSelectOrPHIInstWithICmpInstCond()`: generalize eq handling The current logic was: https://alive2.llvm.org/ce/z/j8muXk but in reality the offset to the Y in the 'true' hand does not need to exist: https://alive2.llvm.org/ce/z/MNQ7DZ https://alive2.llvm.org/ce/z/S2pMQD To catch that, instead of computing the Y's in both hands and checking their equality, compute Y and C, and check that C is 0 or 1. --- llvm/lib/Analysis/ScalarEvolution.cpp | 19 +++++++++---------- .../Analysis/ScalarEvolution/logical-operations.ll | 4 ++-- llvm/test/Analysis/ScalarEvolution/min-max-exprs.ll | 2 +- polly/test/ForwardOpTree/changed-kind.ll | 9 +-------- 4 files changed, 13 insertions(+), 21 deletions(-) diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 8b479da..84680ff 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -5952,21 +5952,20 @@ const SCEV *ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond( } break; case ICmpInst::ICMP_NE: - // n != 0 ? n+x : 1+x -> n == 0 ? 1+x : n+x + // x != 0 ? x+y : C+y -> x == 0 ? C+y : x+y std::swap(TrueVal, FalseVal); LLVM_FALLTHROUGH; case ICmpInst::ICMP_EQ: - // n == 0 ? 1+x : n+x -> umax(n, 1)+x + // x == 0 ? C+y : x+y -> umax(x, C)+y iff C u<= 1 if (getTypeSizeInBits(LHS->getType()) <= getTypeSizeInBits(I->getType()) && isa(RHS) && cast(RHS)->isZero()) { - const SCEV *One = getOne(I->getType()); - const SCEV *LS = getNoopOrZeroExtend(getSCEV(LHS), I->getType()); - const SCEV *LA = getSCEV(TrueVal); - const SCEV *RA = getSCEV(FalseVal); - const SCEV *LDiff = getMinusSCEV(LA, One); - const SCEV *RDiff = getMinusSCEV(RA, LS); - if (LDiff == RDiff) - return getAddExpr(getUMaxExpr(One, LS), LDiff); + const SCEV *X = getNoopOrZeroExtend(getSCEV(LHS), I->getType()); + const SCEV *TrueValExpr = getSCEV(TrueVal); // C+y + const SCEV *FalseValExpr = getSCEV(FalseVal); // x+y + const SCEV *Y = getMinusSCEV(FalseValExpr, X); // y = (x+y)-x + const SCEV *C = getMinusSCEV(TrueValExpr, Y); // C = (C+y)-y + if (isa(C) && cast(C)->getAPInt().ule(1)) + return getAddExpr(getUMaxExpr(X, C), Y); } break; default: diff --git a/llvm/test/Analysis/ScalarEvolution/logical-operations.ll b/llvm/test/Analysis/ScalarEvolution/logical-operations.ll index a7a9413f..8f04e02 100644 --- a/llvm/test/Analysis/ScalarEvolution/logical-operations.ll +++ b/llvm/test/Analysis/ScalarEvolution/logical-operations.ll @@ -478,7 +478,7 @@ define i32 @umin_seq_x_y_tautological(i32 %x, i32 %y) { ; CHECK-NEXT: %umin = call i32 @llvm.umin.i32(i32 %y, i32 %x) ; CHECK-NEXT: --> (%x umin %y) U: full-set S: full-set ; CHECK-NEXT: %r = select i1 %umin.is.zero, i32 0, i32 %umin -; CHECK-NEXT: --> %r U: full-set S: full-set +; CHECK-NEXT: --> (%x umin %y) U: full-set S: full-set ; CHECK-NEXT: Determining loop execution counts for: @umin_seq_x_y_tautological ; %umin = call i32 @llvm.umin(i32 %y, i32 %x) @@ -492,7 +492,7 @@ define i32 @umin_seq_x_y_tautological_wrongtype(i32 %x, i32 %y) { ; CHECK-NEXT: %umax = call i32 @llvm.umax.i32(i32 %y, i32 %x) ; CHECK-NEXT: --> (%x umax %y) U: full-set S: full-set ; CHECK-NEXT: %r = select i1 %umax.is.zero, i32 0, i32 %umax -; CHECK-NEXT: --> %r U: full-set S: full-set +; CHECK-NEXT: --> (%x umax %y) U: full-set S: full-set ; CHECK-NEXT: Determining loop execution counts for: @umin_seq_x_y_tautological_wrongtype ; %umax = call i32 @llvm.umax(i32 %y, i32 %x) diff --git a/llvm/test/Analysis/ScalarEvolution/min-max-exprs.ll b/llvm/test/Analysis/ScalarEvolution/min-max-exprs.ll index d0339ec..208f369 100644 --- a/llvm/test/Analysis/ScalarEvolution/min-max-exprs.ll +++ b/llvm/test/Analysis/ScalarEvolution/min-max-exprs.ll @@ -127,7 +127,7 @@ define i8 @umax_basic_eq_off0(i8 %x, i8 %y) { ; CHECK-NEXT: %rhs = add i8 %x, %y ; CHECK-NEXT: --> (%x + %y) U: full-set S: full-set ; CHECK-NEXT: %r = select i1 %x.is.zero, i8 %lhs, i8 %rhs -; CHECK-NEXT: --> %r U: full-set S: full-set +; CHECK-NEXT: --> (%x + %y) U: full-set S: full-set ; CHECK-NEXT: Determining loop execution counts for: @umax_basic_eq_off0 ; %x.is.zero = icmp eq i8 %x, 0 diff --git a/polly/test/ForwardOpTree/changed-kind.ll b/polly/test/ForwardOpTree/changed-kind.ll index a66ba55..bf81f51 100644 --- a/polly/test/ForwardOpTree/changed-kind.ll +++ b/polly/test/ForwardOpTree/changed-kind.ll @@ -43,12 +43,5 @@ lor.end93: ; CHECK: Statistics { -; CHECK: Reloads: 1 -; CHECK: } - -; CHECK: After statements { -; CHECK: Stmt_lor_end93 -; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 1] -; CHECK-NEXT: { Stmt_lor_end93[] -> MemRef3[] }; -; CHECK-NEXT: new: { Stmt_lor_end93[] -> MemRef_c[0] }; +; CHECK: Reloads: 0 ; CHECK: } -- 2.7.4