From 3c4d9cc27316669ea803ff468f9f9ae88f181782 Mon Sep 17 00:00:00 2001 From: Noah Goldstein Date: Tue, 18 Apr 2023 01:23:08 -0500 Subject: [PATCH] Revert "[ValueTracking] Apply the isKnownNonZero techniques in `ashr`/`lshl` to `shl` and vice-versa" May be related to PR62175 This reverts commit 57590d1dd47bbe9aa4b79a0f93cc3ec62cc5d060. --- llvm/lib/Analysis/ValueTracking.cpp | 76 +++++++--------------- llvm/test/Analysis/ValueTracking/known-non-zero.ll | 25 +++++-- llvm/test/Transforms/InstCombine/ctpop-pow2.ll | 6 +- 3 files changed, 48 insertions(+), 59 deletions(-) diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp index a5cdfda..2578957 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -2512,57 +2512,6 @@ static bool isNonZeroRecurrence(const PHINode *PN) { } } -static bool isNonZeroShift(const Operator *I, const APInt &DemandedElts, - unsigned Depth, const Query &Q, - const KnownBits &KnownVal) { - auto ShiftOp = [&](const APInt &Lhs, const APInt &Rhs) { - switch (I->getOpcode()) { - case Instruction::Shl: - return Lhs.shl(Rhs); - case Instruction::LShr: - return Lhs.lshr(Rhs); - case Instruction::AShr: - return Lhs.ashr(Rhs); - default: - llvm_unreachable("Unknown Shift Opcode"); - } - }; - - auto InvShiftOp = [&](const APInt &Lhs, const APInt &Rhs) { - switch (I->getOpcode()) { - case Instruction::Shl: - return Lhs.lshr(Rhs); - case Instruction::LShr: - case Instruction::AShr: - return Lhs.shl(Rhs); - default: - llvm_unreachable("Unknown Shift Opcode"); - } - }; - - if (KnownVal.isUnknown()) - return false; - - KnownBits KnownCnt = - computeKnownBits(I->getOperand(1), DemandedElts, Depth, Q); - APInt MaxShift = KnownCnt.getMaxValue(); - unsigned NumBits = KnownVal.getBitWidth(); - if (MaxShift.uge(NumBits)) - return false; - - if (!ShiftOp(KnownVal.One, MaxShift).isZero()) - return true; - - // If all of the bits shifted out are known to be zero, and Val is known - // non-zero then at least one non-zero bit must remain. - if (InvShiftOp(KnownVal.Zero, NumBits - MaxShift) - .eq(InvShiftOp(APInt::getAllOnes(NumBits), NumBits - MaxShift)) && - isKnownNonZero(I->getOperand(0), DemandedElts, Depth, Q)) - return true; - - return false; -} - /// Return true if the given value is known to be non-zero when defined. For /// vectors, return true if every demanded element is known to be non-zero when /// defined. For pointers, if the context instruction and dominator tree are @@ -2733,7 +2682,16 @@ bool isKnownNonZero(const Value *V, const APInt &DemandedElts, unsigned Depth, if (Known.One[0]) return true; - return isNonZeroShift(I, DemandedElts, Depth, Q, Known); + if (!Known.isUnknown()) { + KnownBits KnownCnt = + computeKnownBits(I->getOperand(1), DemandedElts, Depth, Q); + + if (KnownCnt.getMaxValue().ult(Known.getBitWidth()) && + !Known.One.shl(KnownCnt.getMaxValue()).isZero()) + return true; + } + + break; } case Instruction::LShr: case Instruction::AShr: { @@ -2749,7 +2707,19 @@ bool isKnownNonZero(const Value *V, const APInt &DemandedElts, unsigned Depth, if (Known.isNegative()) return true; - return isNonZeroShift(I, DemandedElts, Depth, Q, Known); + // If the shifter operand is a constant, and all of the bits shifted + // out are known to be zero, and X is known non-zero then at least one + // non-zero bit must remain. + if (ConstantInt *Shift = dyn_cast(I->getOperand(1))) { + auto ShiftVal = Shift->getLimitedValue(BitWidth - 1); + // Is there a known one in the portion not shifted out? + if (Known.countMaxLeadingZeros() < BitWidth - ShiftVal) + return true; + // Are all the bits to be shifted out known zero? + if (Known.countMinTrailingZeros() >= ShiftVal) + return isKnownNonZero(I->getOperand(0), DemandedElts, Depth, Q); + } + break; } case Instruction::UDiv: case Instruction::SDiv: diff --git a/llvm/test/Analysis/ValueTracking/known-non-zero.ll b/llvm/test/Analysis/ValueTracking/known-non-zero.ll index 37e0b11..3468795 100644 --- a/llvm/test/Analysis/ValueTracking/known-non-zero.ll +++ b/llvm/test/Analysis/ValueTracking/known-non-zero.ll @@ -261,7 +261,10 @@ define i1 @lshr_nz_bounded_cnt(i32 %cnt, i32 %y) { ; CHECK-LABEL: @lshr_nz_bounded_cnt( ; CHECK-NEXT: [[CNT_ULT4:%.*]] = icmp ult i32 [[CNT:%.*]], 4 ; CHECK-NEXT: call void @llvm.assume(i1 [[CNT_ULT4]]) -; CHECK-NEXT: ret i1 false +; CHECK-NEXT: [[VAL:%.*]] = or i32 [[Y:%.*]], 90 +; CHECK-NEXT: [[SHL:%.*]] = lshr i32 [[VAL]], [[CNT]] +; CHECK-NEXT: [[R:%.*]] = icmp eq i32 [[SHL]], 0 +; CHECK-NEXT: ret i1 [[R]] ; %cnt_ult4 = icmp ult i32 %cnt, 4 call void @llvm.assume(i1 %cnt_ult4) @@ -273,7 +276,11 @@ define i1 @lshr_nz_bounded_cnt(i32 %cnt, i32 %y) { define <2 x i1> @ashr_nz_bounded_cnt_vec(<2 x i32> %x, <2 x i32> %y) { ; CHECK-LABEL: @ashr_nz_bounded_cnt_vec( -; CHECK-NEXT: ret <2 x i1> zeroinitializer +; CHECK-NEXT: [[CNT:%.*]] = and <2 x i32> [[X:%.*]], +; CHECK-NEXT: [[VAL:%.*]] = or <2 x i32> [[Y:%.*]], +; CHECK-NEXT: [[SHL:%.*]] = ashr <2 x i32> [[VAL]], [[CNT]] +; CHECK-NEXT: [[R:%.*]] = icmp eq <2 x i32> [[SHL]], zeroinitializer +; CHECK-NEXT: ret <2 x i1> [[R]] ; %cnt = and <2 x i32> %x, %val = or <2 x i32> %y, @@ -325,7 +332,9 @@ define i1 @lshr_nonzero_and_shift_out_zeros(i32 %cnt, i32 %y) { ; CHECK-NEXT: [[VAL:%.*]] = and i32 [[Y:%.*]], -131072 ; CHECK-NEXT: [[VAL_NZ:%.*]] = icmp ne i32 [[VAL]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[VAL_NZ]]) -; CHECK-NEXT: ret i1 false +; CHECK-NEXT: [[SHL:%.*]] = lshr i32 [[VAL]], [[CNT]] +; CHECK-NEXT: [[R:%.*]] = icmp eq i32 [[SHL]], 0 +; CHECK-NEXT: ret i1 [[R]] ; %cnt_ult = icmp ult i32 %cnt, 4 call void @llvm.assume(i1 %cnt_ult) @@ -343,10 +352,13 @@ define i1 @lshr_nonzero_and_shift_out_zeros(i32 %cnt, i32 %y) { define i1 @ashr_nonzero_and_shift_out_zeros(i32 %ccnt, i32 %y) { ; CHECK-LABEL: @ashr_nonzero_and_shift_out_zeros( +; CHECK-NEXT: [[CNT:%.*]] = and i32 [[CCNT:%.*]], 7 ; CHECK-NEXT: [[VAL:%.*]] = and i32 [[Y:%.*]], -131072 ; CHECK-NEXT: [[VAL_NZ:%.*]] = icmp ne i32 [[VAL]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[VAL_NZ]]) -; CHECK-NEXT: ret i1 false +; CHECK-NEXT: [[SHL:%.*]] = ashr i32 [[VAL]], [[CNT]] +; CHECK-NEXT: [[R:%.*]] = icmp eq i32 [[SHL]], 0 +; CHECK-NEXT: ret i1 [[R]] ; %cnt = and i32 %ccnt, 7 %val = and i32 %y, -131072 @@ -360,10 +372,13 @@ define i1 @ashr_nonzero_and_shift_out_zeros(i32 %ccnt, i32 %y) { define i1 @shl_nonzero_and_shift_out_zeros(i32 %ccnt, i32 %y) { ; CHECK-LABEL: @shl_nonzero_and_shift_out_zeros( +; CHECK-NEXT: [[CNT:%.*]] = and i32 [[CCNT:%.*]], 6 ; CHECK-NEXT: [[VAL:%.*]] = and i32 [[Y:%.*]], 131071 ; CHECK-NEXT: [[VAL_NZ:%.*]] = icmp ne i32 [[VAL]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[VAL_NZ]]) -; CHECK-NEXT: ret i1 false +; CHECK-NEXT: [[SHL:%.*]] = shl i32 [[VAL]], [[CNT]] +; CHECK-NEXT: [[R:%.*]] = icmp eq i32 [[SHL]], 0 +; CHECK-NEXT: ret i1 [[R]] ; %cnt = and i32 %ccnt, 6 %val = and i32 %y, 131071 diff --git a/llvm/test/Transforms/InstCombine/ctpop-pow2.ll b/llvm/test/Transforms/InstCombine/ctpop-pow2.ll index f6757c2..b73aff5 100644 --- a/llvm/test/Transforms/InstCombine/ctpop-pow2.ll +++ b/llvm/test/Transforms/InstCombine/ctpop-pow2.ll @@ -116,7 +116,11 @@ define <2 x i32> @ctpop_lshr_intmin_intmin_plus1_vec_nz(<2 x i32> %x) { define <2 x i32> @ctpop_shl2_1_vec_nz(<2 x i32> %x) { ; CHECK-LABEL: @ctpop_shl2_1_vec_nz( -; CHECK-NEXT: ret <2 x i32> +; CHECK-NEXT: [[AND:%.*]] = and <2 x i32> [[X:%.*]], +; CHECK-NEXT: [[SHL:%.*]] = shl <2 x i32> , [[AND]] +; CHECK-NEXT: [[TMP1:%.*]] = icmp ne <2 x i32> [[SHL]], zeroinitializer +; CHECK-NEXT: [[CNT:%.*]] = zext <2 x i1> [[TMP1]] to <2 x i32> +; CHECK-NEXT: ret <2 x i32> [[CNT]] ; %and = and <2 x i32> %x, %shl = shl <2 x i32> , %and -- 2.7.4