diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp --- a/llvm/lib/Analysis/InstructionSimplify.cpp +++ b/llvm/lib/Analysis/InstructionSimplify.cpp @@ -3627,6 +3627,53 @@ return nullptr; } +static Value *simplifyICmpLShiftedValues(CmpInst::Predicate Predicate, + Value *LHS, Value *RHS, + const SimplifyQuery &Q) { + ConstantInt *ShiftAmountL, *ShiftAmountR; + Value *V; + if (!match(LHS, m_Shl(m_Value(V), m_ConstantInt(ShiftAmountL))) || + !match(RHS, m_Shl(m_Deferred(V), m_ConstantInt(ShiftAmountR))) || + LHS->getType() != RHS->getType() || !isKnownNonZero(V, Q.DL)) + return nullptr; + + auto ShiftL = cast(LHS); + auto ShiftR = cast(RHS); + auto TrySimplify = [&](bool IsSignedPredicate, + std::function Condition) -> Value * { + BinaryOperator *LargestShift = + ShiftAmountL > ShiftAmountR ? ShiftL : ShiftR; + if (IsSignedPredicate && (!LargestShift->hasNoUnsignedWrap() || + !LargestShift->hasNoSignedWrap())) + return nullptr; + if (!IsSignedPredicate && !LargestShift->hasNoUnsignedWrap()) + return nullptr; + return Condition() ? getTrue(getCompareTy(ShiftAmountL)) + : getFalse(getCompareTy(ShiftAmountL)); + }; + + switch (Predicate) { + case CmpInst::ICMP_ULT: + return TrySimplify(false, [&]() { return ShiftAmountL < ShiftAmountR; }); + case CmpInst::ICMP_SLT: + return TrySimplify(true, [&]() { return ShiftAmountL < ShiftAmountR; }); + case CmpInst::ICMP_UGT: + return TrySimplify(false, [&]() { return ShiftAmountL > ShiftAmountR; }); + case CmpInst::ICMP_SGT: + return TrySimplify(true, [&]() { return ShiftAmountL > ShiftAmountR; }); + case CmpInst::ICMP_ULE: + return TrySimplify(false, [&]() { return ShiftAmountL <= ShiftAmountR; }); + case CmpInst::ICMP_SLE: + return TrySimplify(true, [&]() { return ShiftAmountL <= ShiftAmountR; }); + case CmpInst::ICMP_UGE: + return TrySimplify(false, [&]() { return ShiftAmountL >= ShiftAmountR; }); + case CmpInst::ICMP_SGE: + return TrySimplify(true, [&]() { return ShiftAmountL >= ShiftAmountR; }); + default: + return nullptr; + }; +} + static Value *simplifyICmpWithDominatingAssume(CmpInst::Predicate Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q) { @@ -3940,6 +3987,9 @@ if (Value *V = threadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse)) return V; + if (Value *V = simplifyICmpLShiftedValues(Pred, LHS, RHS, Q)) + return V; + return nullptr; } 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 @@ -2812,6 +2812,142 @@ ret i1 %res } +define i1 @neg_icmp_lshr_unknown_value(i8 %x) { +; CHECK-LABEL: @neg_icmp_lshr_unknown_value( +; CHECK-NEXT: [[X1:%.*]] = shl nuw i8 [[X:%.*]], 2 +; CHECK-NEXT: [[X2:%.*]] = shl nuw i8 [[X]], 1 +; CHECK-NEXT: [[CMP:%.*]] = icmp ugt i8 [[X1]], [[X2]] +; CHECK-NEXT: ret i1 [[CMP]] +; + %x1 = shl nuw i8 %x, 2 + %x2 = shl nuw i8 %x, 1 + %cmp = icmp ugt i8 %x1, %x2 + ret i1 %cmp +} + +define i1 @neg_icmp_lshr_unknown_shift(i8 %x, i8 %C1) { +; CHECK-LABEL: @neg_icmp_lshr_unknown_shift( +; CHECK-NEXT: [[OR:%.*]] = or i8 [[X:%.*]], 1 +; CHECK-NEXT: [[X1:%.*]] = shl nuw i8 [[OR]], 2 +; CHECK-NEXT: [[X2:%.*]] = shl nuw i8 [[OR]], [[C1:%.*]] +; CHECK-NEXT: [[CMP:%.*]] = icmp ugt i8 [[X1]], [[X2]] +; CHECK-NEXT: ret i1 [[CMP]] +; + %or = or i8 %x, 1 + %x1 = shl nuw i8 %or, 2 + %x2 = shl nuw i8 %or, %C1 + %cmp = icmp ugt i8 %x1, %x2 + ret i1 %cmp +} + +define i1 @icmp_lshr_known_non_zero_ult_true(i8 %x) { +; CHECK-LABEL: @icmp_lshr_known_non_zero_ult_true( +; CHECK-NEXT: ret i1 true +; + %or = or i8 %x, 1 + %x1 = shl nuw i8 %or, 1 + %x2 = shl nuw i8 %or, 2 + %cmp = icmp ult i8 %x1, %x2 + ret i1 %cmp +} + +define i1 @icmp_lshr_known_non_zero_ult_false(i8 %x) { +; CHECK-LABEL: @icmp_lshr_known_non_zero_ult_false( +; CHECK-NEXT: ret i1 false +; + %or = or i8 %x, 1 + %x1 = shl nuw i8 %or, 1 + %x2 = shl nuw i8 %or, 2 + %cmp = icmp ugt i8 %x1, %x2 + ret i1 %cmp +} + +define i1 @icmp_lshr_known_non_zero_slt_true(i8 %x) { +; CHECK-LABEL: @icmp_lshr_known_non_zero_slt_true( +; CHECK-NEXT: ret i1 true +; + %or = or i8 %x, 1 + %x1 = shl i8 %or, 1 + %x2 = shl nuw nsw i8 %or, 2 + %cmp = icmp slt i8 %x1, %x2 + ret i1 %cmp +} + +define i1 @icmp_lshr_known_non_zero_slt_false(i8 %x) { +; CHECK-LABEL: @icmp_lshr_known_non_zero_slt_false( +; CHECK-NEXT: ret i1 false +; + %or = or i8 %x, 1 + %x1 = shl nuw nsw i8 %or, 2 + %x2 = shl i8 %or, 1 + %cmp = icmp slt i8 %x1, %x2 + ret i1 %cmp +} + +define i1 @neg_icmp_lshr_known_non_zero_sgt_missing_nuw(i8 %x) { +; CHECK-LABEL: @neg_icmp_lshr_known_non_zero_sgt_missing_nuw( +; CHECK-NEXT: [[OR:%.*]] = or i8 [[X:%.*]], 1 +; CHECK-NEXT: [[X1:%.*]] = shl nsw i8 [[OR]], 2 +; CHECK-NEXT: [[X2:%.*]] = shl i8 [[OR]], 1 +; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i8 [[X1]], [[X2]] +; CHECK-NEXT: ret i1 [[CMP]] +; + %or = or i8 %x, 1 + %x1 = shl nsw i8 %or, 2 + %x2 = shl i8 %or, 1 + %cmp = icmp sgt i8 %x1, %x2 + ret i1 %cmp +} + +define i1 @neg_icmp_lshr_known_non_zero_sgt_missing_nsw(i8 %x) { +; CHECK-LABEL: @neg_icmp_lshr_known_non_zero_sgt_missing_nsw( +; CHECK-NEXT: [[OR:%.*]] = or i8 [[X:%.*]], 1 +; CHECK-NEXT: [[X1:%.*]] = shl nuw i8 [[OR]], 2 +; CHECK-NEXT: [[X2:%.*]] = shl i8 [[OR]], 1 +; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i8 [[X1]], [[X2]] +; CHECK-NEXT: ret i1 [[CMP]] +; + %or = or i8 %x, 1 + %x1 = shl nuw i8 %or, 2 + %x2 = shl i8 %or, 1 + %cmp = icmp sgt i8 %x1, %x2 + ret i1 %cmp +} + +define i1 @neg_icmp_lshr_known_non_zero_sgt_nuw_nsw_smallest_shift(i8 %x) { +; CHECK-LABEL: @neg_icmp_lshr_known_non_zero_sgt_nuw_nsw_smallest_shift( +; CHECK-NEXT: [[OR:%.*]] = or i8 [[X:%.*]], 1 +; CHECK-NEXT: [[X1:%.*]] = shl nuw nsw i8 [[OR]], 1 +; CHECK-NEXT: [[X2:%.*]] = shl i8 [[OR]], 2 +; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i8 [[X1]], [[X2]] +; CHECK-NEXT: ret i1 [[CMP]] +; + %or = or i8 %x, 1 + %x1 = shl nuw nsw i8 %or, 1 + %x2 = shl i8 %or, 2 + %cmp = icmp sgt i8 %x1, %x2 + ret i1 %cmp +} + +define i1 @neg_icmp_lshr_different_shift_values() { +; CHECK-LABEL: @neg_icmp_lshr_different_shift_values( +; CHECK-NEXT: [[VSCALE:%.*]] = call i64 @llvm.vscale.i64() +; CHECK-NEXT: [[VSCALE2:%.*]] = call i64 @llvm.vscale.i64() +; CHECK-NEXT: [[VSCALEX2:%.*]] = shl nuw nsw i64 [[VSCALE]], 1 +; CHECK-NEXT: [[VSCALEX4:%.*]] = shl nuw nsw i64 [[VSCALE2]], 2 +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i64 [[VSCALEX2]], [[VSCALEX4]] +; CHECK-NEXT: ret i1 [[CMP]] +; + %vscale = call i64 @llvm.vscale.i64() + %vscale2 = call i64 @llvm.vscale.i64() + %vscalex2 = shl nuw nsw i64 %vscale, 1 + %vscalex4 = shl nuw nsw i64 %vscale2, 2 + %cmp = icmp ult i64 %vscalex2, %vscalex4 + ret i1 %cmp +} + +declare i64 @llvm.vscale.i64() + ; TODO: Add coverage for global aliases, link once, etc..