Index: lib/Transforms/InstCombine/InstCombineCompares.cpp =================================================================== --- lib/Transforms/InstCombine/InstCombineCompares.cpp +++ lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -2459,6 +2459,91 @@ return new ICmpInst(I.getPredicate(), A, B); } + // PR19753: + // (icmp eq/ne (ashr/lshr const2, A), const1) -> + // (icmp eq/ne A, Log2(const2/const1)) -> + // (icmp eq/ne A, Log2(const2) - Log2(const1)). + // TODO : Handle this for other icmp instructions. + if (I.isEquality()) { + ConstantInt *CI2; + if (match(Op0, m_AShr(m_ConstantInt(CI2), m_Value(A))) || + match(Op0, m_LShr(m_ConstantInt(CI2), m_Value(A)))) { + APInt AP1 = CI->getValue(); + APInt AP2 = CI2->getValue(); + int Shift; + if (!AP1) { + // if const1 = const2 = 0, return true. + if (!AP2) + return ReplaceInstUsesWith(I, ConstantInt::getTrue(I.getType())); + // if const1 = 0, const2 !=0 and right shift is 'exact', + // return false. + if (cast(Op0)->isExact()) + return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); + // if const1 = 0, right shift is non-exact and const2 is -ve, + // return false. + if (AP2.isNegative()) + return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); + // if const1 = 0, shift is non-exact and const2 is +ve -> + // icmp ugt A, Log2(const2). + Shift = AP2.logBase2(); + return new ICmpInst(I.ICMP_UGT, A, + ConstantInt::get(A->getType(), Shift)); + } + + // Shifting 0 by any value gives 0. + if (!AP2) + return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); + + // if const1 = const2 -> icmp eq/ne A, 0 + if (AP1 == AP2) + return new ICmpInst(I.getPredicate(), A, + ConstantInt::getNullValue(A->getType())); + + if (isa(Op0)) { + // const1 and const2 are sign opposite, arithmatic shift will retain + // sign and hence const2 will never equal const1. + if (AP1.isNegative() != AP2.isNegative()) + return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); + // Both the constants are negative, take their positive to calculate + // log. + if (AP1.isNegative()) { + AP1 = -AP1; + AP2 = -AP2; + } + } + + if (isa(Op0)) { + // logical shift of const2 will be +ve which will not be equal + // to -ve const1. + if (AP1.isNegative()) + return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); + // const1 is +ve and const2 is -ve, logical shift of const2 may + // equal const1, hence take abs(AP2) to calculate log. + if (AP2.isNegative()) + AP2 = -AP2; + } + + // Now we have const1 = abs(const1) and const2 = abs(const2). + // If const1 is greater than const2, + // right shifting const2 will never equal to const1. + if (AP1.ugt(AP2)) + return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); + + Shift = AP2.logBase2() - AP1.logBase2(); + + // if shift is 'exact', then use shl to check equality. + if ((cast(Op0)->isExact()) && (AP1.shl(Shift) == AP2)) + return new ICmpInst(I.getPredicate(), A, + ConstantInt::get(A->getType(), Shift)); + // Use lshr here, since we've canonicalized to +ve numbers. + if (AP1 == AP2.lshr(Shift)) + return new ICmpInst(I.getPredicate(), A, + ConstantInt::get(A->getType(), Shift)); + // Shifting const2 will never be equal to const1, return false. + return ReplaceInstUsesWith(I, ConstantInt::getFalse(I.getType())); + } + } + // If we have an icmp le or icmp ge instruction, turn it into the // appropriate icmp lt or icmp gt instruction. This allows us to rely on // them being folded in the code below. The SimplifyICmpInst code has Index: test/Transforms/InstCombine/icmp.ll =================================================================== --- test/Transforms/InstCombine/icmp.ll +++ test/Transforms/InstCombine/icmp.ll @@ -1424,3 +1424,205 @@ %2 = icmp slt i32 %1, -10 ret i1 %2 } + +; CHECK-LABEL: @exact_lshr_both_zero +; CHECK-NEXT: ret i1 true +define i1 @exact_lshr_both_zero(i32 %a) { + %shr = lshr exact i32 0, %a + %cmp = icmp eq i32 %shr, 0 + ret i1 %cmp +} + +; CHECK-LABEL: @exact_ashr_both_zero +; CHECK-NEXT: ret i1 true +define i1 @exact_ashr_both_zero(i32 %a) { + %shr = ashr exact i32 0, %a + %cmp = icmp eq i32 %shr, 0 + ret i1 %cmp +} + +; CHECK-LABEL: @nonexact_lshr_both_zero +; CHECK-NEXT: ret i1 true +define i1 @nonexact_lshr_both_zero(i32 %a) { + %shr = lshr i32 0, %a + %cmp = icmp eq i32 %shr, 0 + ret i1 %cmp +} + +; CHECK-LABEL: @nonexact_ashr_both_zero +; CHECK-NEXT: ret i1 true +define i1 @nonexact_ashr_both_zero(i32 %a) { + %shr = ashr i32 0, %a + %cmp = icmp eq i32 %shr, 0 + ret i1 %cmp +} + +; CHECK-LABEL: @exact_lshr_last_zero +; CHECK-NEXT: ret i1 false +define i1 @exact_lshr_last_zero(i32 %a) { + %shr = lshr exact i32 64, %a + %cmp = icmp eq i32 %shr, 0 + ret i1 %cmp +} + +; CHECK-LABEL: @exact_ashr_last_zero +; CHECK-NEXT: ret i1 false +define i1 @exact_ashr_last_zero(i32 %a) { + %shr = ashr exact i32 -2147483648, %a + %cmp = icmp eq i32 %shr, 0 + ret i1 %cmp +} + +; CHECK-LABEL: @nonexact_lshr_last_zero +; CHECK-NEXT: ret i1 false +define i1 @nonexact_lshr_last_zero(i32 %a) { + %shr = lshr i32 -2147483648, %a + %cmp = icmp eq i32 %shr, 0 + ret i1 %cmp +} + +; CHECK-LABEL: @nonexact_ashr_last_zero +; CHECK-NEXT: ret i1 false +define i1 @nonexact_ashr_last_zero(i32 %a) { + %shr = ashr i32 -2147483648, %a + %cmp = icmp eq i32 %shr, 0 + ret i1 %cmp +} + +; CHECK-LABEL: @lshr_first_positive_last_zero +; CHECK-NEXT: icmp ugt i32 %a, 30 +define i1 @lshr_first_positive_last_zero(i32 %a) { + %shr = lshr i32 1073741824, %a + %cmp = icmp eq i32 %shr, 0 + ret i1 %cmp +} + +; CHECK-LABEL: @ashr_first_positive_second_zero +; CHECK-NEXT: icmp ugt i32 %a, 30 +define i1 @ashr_first_positive_second_zero(i32 %a) { + %shr = ashr i32 1073741824, %a + %cmp = icmp eq i32 %shr, 0 + ret i1 %cmp +} + +; CHECK-LABEL: @lshr_first_zero +; CHECK-NEXT: ret i1 false +define i1 @lshr_first_zero(i32 %a) { + %shr = lshr i32 0, %a + %cmp = icmp eq i32 %shr, 2 + ret i1 %cmp +} + +; CHECK-LABEL: @exact_ashr_both_equal +; CHECK-NEXT: icmp ne i32 %a, 0 +define i1 @exact_ashr_both_equal(i32 %a) { + %shr = ashr exact i32 -2147483648, %a + %cmp = icmp ne i32 %shr, -2147483648 + ret i1 %cmp +} + +; CHECK-LABEL: @exact_lshr_both_equal +; CHECK-NEXT: icmp eq i32 %a, 0 +define i1 @exact_lshr_both_equal(i32 %a) { + %shr = lshr exact i32 1073741824, %a + %cmp = icmp eq i32 %shr, 1073741824 + ret i1 %cmp +} + +; CHECK-LABEL: @exact_ashr_opposite_sign +; CHECK-NEXT: ret i1 false +define i1 @exact_ashr_opposite_sign(i32 %a) { + %shr = ashr exact i32 -2147483648, %a + %cmp = icmp eq i32 %shr, 1 + ret i1 %cmp +} + +; CHECK-LABEL: @ashr_opposite_sign +; CHECK-NEXT: ret i1 false +define i1 @ashr_opposite_sign(i32 %a) { + %shr = ashr i32 -2147483648, %a + %cmp = icmp eq i32 %shr, 1 + ret i1 %cmp +} + +; CHECK-LABEL: @exact_lshr_opposite_sign +; CHECK-NEXT: icmp eq i32 %a, 31 +define i1 @exact_lshr_opposite_sign(i32 %a) { + %shr = lshr exact i32 -2147483648, %a + %cmp = icmp eq i32 %shr, 1 + ret i1 %cmp +} + +; CHECK-LABEL: @lshr_opposite_sign +; CHECK-NEXT: icmp eq i32 %a, 31 +define i1 @lshr_opposite_sign(i32 %a) { + %shr = lshr i32 -2147483648, %a + %cmp = icmp eq i32 %shr, 1 + ret i1 %cmp +} + +; CHECK-LABEL: @exact_ashr_eq +; CHECK-NEXT: icmp eq i32 %a, 31 +define i1 @exact_ashr_eq(i32 %a) { + %shr = ashr exact i32 -2147483648, %a + %cmp = icmp eq i32 %shr, -1 + ret i1 %cmp +} + +; CHECK-LABEL: @exact_ashr_ne +; CHECK-NEXT: icmp ne i32 %a, 31 +define i1 @exact_ashr_ne(i32 %a) { + %shr = ashr exact i32 -2147483648, %a + %cmp = icmp ne i32 %shr, -1 + ret i1 %cmp +} + +; CHECK-LABEL: @exact_lshr_eq +; CHECK-NEXT: icmp eq i32 %a, 30 +define i1 @exact_lshr_eq(i32 %a) { + %shr = lshr exact i32 1073741824, %a + %cmp = icmp eq i32 %shr, 1 + ret i1 %cmp +} + +; CHECK-LABEL: @exact_lshr_ne +; CHECK-NEXT: icmp ne i32 %a, 30 +define i1 @exact_lshr_ne(i32 %a) { + %shr = lshr exact i32 1073741824, %a + %cmp = icmp ne i32 %shr, 1 + ret i1 %cmp +} + +; CHECK-LABEL: @exact_lshr_ne_noexactdiv +; CHECK-NEXT: ret i1 false +define i1 @exact_lshr_ne_noexactdiv(i32 %a) { + %shr = lshr exact i32 80, %a + %cmp = icmp ne i32 %shr, 31 + ret i1 %cmp +} + +; CHECK-LABEL: @exact_ashr_ne_noexactdiv +; CHECK-NEXT: ret i1 false +define i1 @exact_ashr_ne_noexactdiv(i32 %a) { + %shr = ashr exact i32 -80, %a + %cmp = icmp ne i32 %shr, -41 + ret i1 %cmp +} + +; CHECK-LABEL: @exact_ashr_no_neeq +; CHECK-NEXT: ashr exact i32 -30, %a +; CHECK-NEXT: icmp ult i32 %shr, -15 +define i1 @exact_ashr_no_neeq(i32 %a) { + %shr = ashr exact i32 -30, %a + %cmp = icmp ult i32 %shr, -15 + ret i1 %cmp +} + +; CHECK-LABEL: @exact_lshr_no_neeq +; CHECK-NEXT: lshr exact i32 1073741824, %a +; CHECK-NEXT: icmp ugt i32 %shr, 1 +define i1 @exact_lshr_no_neeq(i32 %a) { + %shr = lshr exact i32 1073741824, %a + %cmp = icmp ugt i32 %shr, 1 + ret i1 %cmp +}