diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -580,6 +580,11 @@ return false; } +// TODO: cmpExcludesZero misses many cases where `RHS` is non-constant but +// we still have enough information about `RHS` to conclude non-zero. For +// example Pred=EQ, RHS=isKnownNonZero. cmpExcludesZero is called in loops +// so the extra compile time may not be worth it, but possible a second API +// should be created for use outside of loops. static bool cmpExcludesZero(CmpInst::Predicate Pred, const Value *RHS) { // v u> y implies v != 0. if (Pred == ICmpInst::ICMP_UGT) @@ -2764,12 +2769,48 @@ return true; break; } - case Instruction::Select: + case Instruction::Select: { // (C ? X : Y) != 0 if X != 0 and Y != 0. - if (isKnownNonZero(I->getOperand(1), DemandedElts, Depth, Q) && - isKnownNonZero(I->getOperand(2), DemandedElts, Depth, Q)) + bool Op1NonZero = isKnownNonZero(I->getOperand(1), DemandedElts, Depth, Q); + bool Op2NonZero = isKnownNonZero(I->getOperand(2), DemandedElts, Depth, Q); + if (Op1NonZero && Op2NonZero) + return true; + + // The condition of the select dominates the true/false arm. Check if the + // condition implies that a given arm is non-zero. + auto SelectCondImpliesNonZero = [&](bool IsTrueArm) { + Value *X, *Op; + CmpInst::Predicate Pred; + + Op = IsTrueArm ? I->getOperand(1) : I->getOperand(2); + // TODO: We currently only check if the exact value used in the `icmp` + // matches one of the arms. We could go further and see if the value used + // in the condition being non-zero implies one of the arm's is non-zero + // (through a use). + if (match(I->getOperand(0), m_ICmp(Pred, m_Specific(Op), m_Value(X)))) { + // pass + } else if (match(I->getOperand(0), + m_ICmp(Pred, m_Value(X), m_Specific(Op)))) { + Pred = ICmpInst::getSwappedPredicate(Pred); + } else { + return false; + } + + if (!IsTrueArm) + Pred = ICmpInst::getInversePredicate(Pred); + + // TODO: cmpExcludesZero misses many cases where `X` is non-constant but + // we still have enough information about `X` to conclude `Op` is nonzero. + // If a better API ever comes about, update this use. + return cmpExcludesZero(Pred, X); + }; + + if (Op2NonZero && SelectCondImpliesNonZero(/* IsTrueArm */ true)) + return true; + if (Op1NonZero && SelectCondImpliesNonZero(/* IsTrueArm */ false)) return true; break; + } case Instruction::PHI: { auto *PN = cast(I); if (Q.IIQ.UseInstrInfo && isNonZeroRecurrence(PN)) diff --git a/llvm/test/Analysis/ValueTracking/select-known-non-zero-const.ll b/llvm/test/Analysis/ValueTracking/select-known-non-zero-const.ll --- a/llvm/test/Analysis/ValueTracking/select-known-non-zero-const.ll +++ b/llvm/test/Analysis/ValueTracking/select-known-non-zero-const.ll @@ -4,11 +4,7 @@ declare void @llvm.assume(i1) define <2 x i1> @select_v_ne_z(<2 x i8> %v, <2 x i8> %yy) { ; CHECK-LABEL: @select_v_ne_z( -; CHECK-NEXT: [[Y:%.*]] = or <2 x i8> [[YY:%.*]], -; CHECK-NEXT: [[CMP:%.*]] = icmp ne <2 x i8> [[V:%.*]], zeroinitializer -; CHECK-NEXT: [[S:%.*]] = select <2 x i1> [[CMP]], <2 x i8> [[V]], <2 x i8> [[Y]] -; CHECK-NEXT: [[R:%.*]] = icmp eq <2 x i8> [[S]], zeroinitializer -; CHECK-NEXT: ret <2 x i1> [[R]] +; CHECK-NEXT: ret <2 x i1> zeroinitializer ; %y = or <2 x i8> %yy, %cmp = icmp ne <2 x i8> %v, zeroinitializer @@ -38,10 +34,7 @@ ; CHECK-LABEL: @select_v_eq_nz( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 44, [[V:%.*]] -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[V]], i8 [[Y]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -55,10 +48,7 @@ ; CHECK-LABEL: @inv_select_v_ugt_nz( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp ugt i8 14, [[V:%.*]] -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[Y]], i8 [[V]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -72,10 +62,7 @@ ; CHECK-LABEL: @inv_select_v_ugt_fail( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp ugt i8 -2, [[V:%.*]] -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[Y]], i8 [[V]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -87,11 +74,7 @@ define <2 x i1> @select_v_ult(<2 x i8> %v, <2 x i8> %C, <2 x i8> %yy) { ; CHECK-LABEL: @select_v_ult( -; CHECK-NEXT: [[Y:%.*]] = or <2 x i8> [[YY:%.*]], -; CHECK-NEXT: [[CMP:%.*]] = icmp ult <2 x i8> [[C:%.*]], [[V:%.*]] -; CHECK-NEXT: [[S:%.*]] = select <2 x i1> [[CMP]], <2 x i8> [[V]], <2 x i8> [[Y]] -; CHECK-NEXT: [[R:%.*]] = icmp eq <2 x i8> [[S]], zeroinitializer -; CHECK-NEXT: ret <2 x i1> [[R]] +; CHECK-NEXT: ret <2 x i1> zeroinitializer ; %y = or <2 x i8> %yy, %cmp = icmp ult <2 x i8> %C, %v @@ -102,11 +85,7 @@ define <2 x i1> @select_v_uge_nz(<2 x i8> %v, <2 x i8> %yy) { ; CHECK-LABEL: @select_v_uge_nz( -; CHECK-NEXT: [[Y:%.*]] = or <2 x i8> [[YY:%.*]], -; CHECK-NEXT: [[CMP:%.*]] = icmp uge <2 x i8> [[V:%.*]], -; CHECK-NEXT: [[S:%.*]] = select <2 x i1> [[CMP]], <2 x i8> [[V]], <2 x i8> [[Y]] -; CHECK-NEXT: [[R:%.*]] = icmp eq <2 x i8> [[S]], zeroinitializer -; CHECK-NEXT: ret <2 x i1> [[R]] +; CHECK-NEXT: ret <2 x i1> zeroinitializer ; %y = or <2 x i8> %yy, %cmp = icmp uge <2 x i8> %v, @@ -119,10 +98,7 @@ ; CHECK-LABEL: @inv_select_v_ule( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp ule i8 [[V:%.*]], 4 -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[Y]], i8 [[V]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -136,10 +112,7 @@ ; CHECK-LABEL: @select_v_sgt_nonneg( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i8 [[V:%.*]], 0 -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[V]], i8 [[Y]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -170,10 +143,7 @@ ; CHECK-LABEL: @inv_select_v_sgt_neg( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i8 [[V:%.*]], -1 -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[Y]], i8 [[V]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -187,10 +157,7 @@ ; CHECK-LABEL: @inv_select_v_sgt_nonneg_nz( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i8 99, [[V:%.*]] -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[Y]], i8 [[V]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -204,10 +171,7 @@ ; CHECK-LABEL: @select_v_slt_nonneg( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp slt i8 0, [[V:%.*]] -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[V]], i8 [[Y]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -238,10 +202,7 @@ ; CHECK-LABEL: @select_v_slt_neg( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp slt i8 [[V:%.*]], -1 -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[V]], i8 [[Y]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -255,10 +216,7 @@ ; CHECK-LABEL: @select_v_sge_nonneg_nz( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp sge i8 [[V:%.*]], 1 -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[V]], i8 [[Y]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -272,10 +230,7 @@ ; CHECK-LABEL: @select_v_sge_neg( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp sge i8 -3, [[V:%.*]] -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[V]], i8 [[Y]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -289,10 +244,7 @@ ; CHECK-LABEL: @inv_select_v_sge_z( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp sge i8 [[V:%.*]], 0 -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[Y]], i8 [[V]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -306,10 +258,7 @@ ; CHECK-LABEL: @inv_select_v_sge_fail( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp sge i8 [[V:%.*]], -44 -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[Y]], i8 [[V]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -323,10 +272,7 @@ ; CHECK-LABEL: @select_v_sle_neg( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp sle i8 [[V:%.*]], -1 -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[V]], i8 [[Y]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -340,10 +286,7 @@ ; CHECK-LABEL: @select_v_sle_nonneg_nz( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp sle i8 1, [[V:%.*]] -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[V]], i8 [[Y]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -374,10 +317,7 @@ ; CHECK-LABEL: @inv_select_v_sle_nonneg( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp sle i8 [[V:%.*]], 0 -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[Y]], i8 [[V]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) diff --git a/llvm/test/Analysis/ValueTracking/select-known-non-zero.ll b/llvm/test/Analysis/ValueTracking/select-known-non-zero.ll --- a/llvm/test/Analysis/ValueTracking/select-known-non-zero.ll +++ b/llvm/test/Analysis/ValueTracking/select-known-non-zero.ll @@ -6,10 +6,7 @@ ; CHECK-LABEL: @select_v_ne_z( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp ne i8 [[V:%.*]], 0 -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[V]], i8 [[Y]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -103,10 +100,7 @@ ; CHECK-LABEL: @select_v_ult( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp ult i8 [[C:%.*]], [[V:%.*]] -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[V]], i8 [[Y]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -141,10 +135,7 @@ ; CHECK-LABEL: @inv_select_v_ule( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp ule i8 [[V:%.*]], [[C:%.*]] -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[Y]], i8 [[V]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) @@ -347,10 +338,7 @@ ; CHECK-LABEL: @inv_select_v_sge_z( ; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp sge i8 [[V:%.*]], 0 -; CHECK-NEXT: [[S:%.*]] = select i1 [[CMP]], i8 [[Y]], i8 [[V]] -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[S]], 0 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ynz = icmp ne i8 %y, 0 call void @llvm.assume(i1 %ynz) diff --git a/llvm/test/Transforms/InstSimplify/compare.ll b/llvm/test/Transforms/InstSimplify/compare.ll --- a/llvm/test/Transforms/InstSimplify/compare.ll +++ b/llvm/test/Transforms/InstSimplify/compare.ll @@ -729,10 +729,7 @@ define i1 @select6(i32 %x) { ; CHECK-LABEL: @select6( -; CHECK-NEXT: [[C:%.*]] = icmp sgt i32 [[X:%.*]], 0 -; CHECK-NEXT: [[S:%.*]] = select i1 [[C]], i32 [[X]], i32 4 -; CHECK-NEXT: [[C2:%.*]] = icmp eq i32 [[S]], 0 -; CHECK-NEXT: ret i1 [[C2]] +; CHECK-NEXT: ret i1 false ; %c = icmp sgt i32 %x, 0 %s = select i1 %c, i32 %x, i32 4