Author: Nikita Popov Date: 2021-01-17T16:02:55+01:00 New Revision: a13c0f62c38131ef2656b06de02d82110abaf272
URL: https://github.com/llvm/llvm-project/commit/a13c0f62c38131ef2656b06de02d82110abaf272 DIFF: https://github.com/llvm/llvm-project/commit/a13c0f62c38131ef2656b06de02d82110abaf272.diff LOG: [InstSimplify] Fold x*C1/C2 <= x (PR48744) We can fold x*C1/C2 <= x to true if C1 <= C2. This is valid even if the multiplication is not nuw: https://alive2.llvm.org/ce/z/vULors The multiplication or division can be replaced by shifts. We don't handle the case where both are shifts, as that should get folded away by InstCombine. Added: Modified: llvm/lib/Analysis/InstructionSimplify.cpp llvm/test/Transforms/InstSimplify/icmp.ll Removed: ################################################################################ diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp index b672798aaffc..3cab06079a87 100644 --- a/llvm/lib/Analysis/InstructionSimplify.cpp +++ b/llvm/lib/Analysis/InstructionSimplify.cpp @@ -2901,6 +2901,28 @@ static Value *simplifyICmpWithBinOpOnLHS( return getTrue(ITy); } + // (x*C1)/C2 <= x for C1 <= C2. + // This holds even if the multiplication overflows: Assume that x != 0 and + // arithmetic is modulo M. For overflow to occur we must have C1 >= M/x and + // thus C2 >= M/x. It follows that (x*C1)/C2 <= (M-1)/C2 <= ((M-1)*x)/M < x. + // + // Additionally, either the multiplication and division might be represented + // as shifts: + // (x*C1)>>C2 <= x for C1 < 2**C2. + // (x<<C1)/C2 <= x for 2**C1 < C2. + const APInt *C1, *C2; + if ((match(LBO, m_UDiv(m_Mul(m_Specific(RHS), m_APInt(C1)), m_APInt(C2))) && + C1->ule(*C2)) || + (match(LBO, m_LShr(m_Mul(m_Specific(RHS), m_APInt(C1)), m_APInt(C2))) && + C1->ule(APInt(C2->getBitWidth(), 1) << *C2)) || + (match(LBO, m_UDiv(m_Shl(m_Specific(RHS), m_APInt(C1)), m_APInt(C2))) && + (APInt(C1->getBitWidth(), 1) << *C1).ule(*C2))) { + if (Pred == ICmpInst::ICMP_UGT) + return getFalse(ITy); + if (Pred == ICmpInst::ICMP_ULE) + return getTrue(ITy); + } + return nullptr; } diff --git a/llvm/test/Transforms/InstSimplify/icmp.ll b/llvm/test/Transforms/InstSimplify/icmp.ll index ad39725889c8..1d4e954256a0 100644 --- a/llvm/test/Transforms/InstSimplify/icmp.ll +++ b/llvm/test/Transforms/InstSimplify/icmp.ll @@ -39,10 +39,7 @@ define i1 @poison2(i32 %x) { define i1 @mul_div_cmp_smaller(i8 %x) { ; CHECK-LABEL: @mul_div_cmp_smaller( -; CHECK-NEXT: [[MUL:%.*]] = mul i8 [[X:%.*]], 3 -; CHECK-NEXT: [[DIV:%.*]] = udiv i8 [[MUL]], 4 -; CHECK-NEXT: [[CMP:%.*]] = icmp ule i8 [[DIV]], [[X]] -; CHECK-NEXT: ret i1 [[CMP]] +; CHECK-NEXT: ret i1 true ; %mul = mul i8 %x, 3 %div = udiv i8 %mul, 4 @@ -52,10 +49,7 @@ define i1 @mul_div_cmp_smaller(i8 %x) { define i1 @mul_div_cmp_equal(i8 %x) { ; CHECK-LABEL: @mul_div_cmp_equal( -; CHECK-NEXT: [[MUL:%.*]] = mul i8 [[X:%.*]], 3 -; CHECK-NEXT: [[DIV:%.*]] = udiv i8 [[MUL]], 3 -; CHECK-NEXT: [[CMP:%.*]] = icmp ule i8 [[DIV]], [[X]] -; CHECK-NEXT: ret i1 [[CMP]] +; CHECK-NEXT: ret i1 true ; %mul = mul i8 %x, 3 %div = udiv i8 %mul, 3 @@ -78,10 +72,7 @@ define i1 @mul_div_cmp_greater(i8 %x) { } define i1 @mul_div_cmp_ugt(i8 %x) { ; CHECK-LABEL: @mul_div_cmp_ugt( -; CHECK-NEXT: [[MUL:%.*]] = mul i8 [[X:%.*]], 3 -; CHECK-NEXT: [[DIV:%.*]] = udiv i8 [[MUL]], 4 -; CHECK-NEXT: [[CMP:%.*]] = icmp ugt i8 [[DIV]], [[X]] -; CHECK-NEXT: ret i1 [[CMP]] +; CHECK-NEXT: ret i1 false ; %mul = mul i8 %x, 3 %div = udiv i8 %mul, 4 @@ -133,10 +124,7 @@ define i1 @mul_div_cmp_wrong_operand(i8 %x, i8 %y) { define i1 @mul_lshr_cmp_smaller(i8 %x) { ; CHECK-LABEL: @mul_lshr_cmp_smaller( -; CHECK-NEXT: [[MUL:%.*]] = mul i8 [[X:%.*]], 3 -; CHECK-NEXT: [[DIV:%.*]] = lshr i8 [[MUL]], 2 -; CHECK-NEXT: [[CMP:%.*]] = icmp ule i8 [[DIV]], [[X]] -; CHECK-NEXT: ret i1 [[CMP]] +; CHECK-NEXT: ret i1 true ; %mul = mul i8 %x, 3 %div = lshr i8 %mul, 2 @@ -146,10 +134,7 @@ define i1 @mul_lshr_cmp_smaller(i8 %x) { define i1 @mul_lshr_cmp_equal(i8 %x) { ; CHECK-LABEL: @mul_lshr_cmp_equal( -; CHECK-NEXT: [[MUL:%.*]] = mul i8 [[X:%.*]], 4 -; CHECK-NEXT: [[DIV:%.*]] = lshr i8 [[MUL]], 2 -; CHECK-NEXT: [[CMP:%.*]] = icmp ule i8 [[DIV]], [[X]] -; CHECK-NEXT: ret i1 [[CMP]] +; CHECK-NEXT: ret i1 true ; %mul = mul i8 %x, 4 %div = lshr i8 %mul, 2 @@ -172,10 +157,7 @@ define i1 @mul_lshr_cmp_greater(i8 %x) { define i1 @shl_div_cmp_smaller(i8 %x) { ; CHECK-LABEL: @shl_div_cmp_smaller( -; CHECK-NEXT: [[MUL:%.*]] = shl i8 [[X:%.*]], 2 -; CHECK-NEXT: [[DIV:%.*]] = udiv i8 [[MUL]], 5 -; CHECK-NEXT: [[CMP:%.*]] = icmp ule i8 [[DIV]], [[X]] -; CHECK-NEXT: ret i1 [[CMP]] +; CHECK-NEXT: ret i1 true ; %mul = shl i8 %x, 2 %div = udiv i8 %mul, 5 @@ -185,10 +167,7 @@ define i1 @shl_div_cmp_smaller(i8 %x) { define i1 @shl_div_cmp_equal(i8 %x) { ; CHECK-LABEL: @shl_div_cmp_equal( -; CHECK-NEXT: [[MUL:%.*]] = shl i8 [[X:%.*]], 2 -; CHECK-NEXT: [[DIV:%.*]] = udiv i8 [[MUL]], 4 -; CHECK-NEXT: [[CMP:%.*]] = icmp ule i8 [[DIV]], [[X]] -; CHECK-NEXT: ret i1 [[CMP]] +; CHECK-NEXT: ret i1 true ; %mul = shl i8 %x, 2 %div = udiv i8 %mul, 4 _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits