Index: lib/Transforms/InstCombine/InstCombine.h =================================================================== --- lib/Transforms/InstCombine/InstCombine.h +++ lib/Transforms/InstCombine/InstCombine.h @@ -191,6 +191,8 @@ ConstantInt *DivRHS); Instruction *FoldICmpCstShrCst(ICmpInst &I, Value *Op, Value *A, ConstantInt *CI1, ConstantInt *CI2); + Instruction *FoldUICmpCstShrCst(ICmpInst &I, Value *Op, Value *A, + ConstantInt *CI1, ConstantInt *CI2); Instruction *FoldICmpCstShlCst(ICmpInst &I, Value *Op, Value *A, ConstantInt *CI1, ConstantInt *CI2); Instruction *FoldICmpAddOpCst(Instruction &ICI, Value *X, ConstantInt *CI, Index: lib/Transforms/InstCombine/InstCombineCompares.cpp =================================================================== --- lib/Transforms/InstCombine/InstCombineCompares.cpp +++ lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -1090,6 +1090,103 @@ return getConstant(false); } +Instruction *InstCombiner::FoldUICmpCstShrCst(ICmpInst &I, Value *Op, Value *A, + ConstantInt *CI1, + ConstantInt *CI2) { + + auto getConstantIfGreater = [&I, this](bool IsTrue) { + if (I.getPredicate() == I.ICMP_ULT || I.getPredicate() == I.ICMP_ULE) + IsTrue = !IsTrue; + return ReplaceInstUsesWith(I, ConstantInt::get(I.getType(), IsTrue)); + }; + + Instruction *Result = nullptr; + + APInt AP1 = CI1->getValue(); + APInt AP2 = CI2->getValue(); + + bool IsAShr = isa(Op); + + // Both AP1, AP2 are non-zero + if (!AP1 || !AP2) { + return Result; + } + + if (AP1 == AP2) { + if (AP1.isNegative() && IsAShr) { + if (I.getPredicate() == I.ICMP_ULE) { + Result = + new ICmpInst(I.ICMP_EQ, A, ConstantInt::getNullValue(A->getType())); + } else if (I.getPredicate() == I.ICMP_UGT) { + Result = + new ICmpInst(I.ICMP_NE, A, ConstantInt::getNullValue(A->getType())); + } else { + Result = getConstantIfGreater(true); + } + } else if (I.getPredicate() == I.ICMP_ULT) { + Result = + new ICmpInst(I.ICMP_UGT, A, ConstantInt::getNullValue(A->getType())); + } else if (I.getPredicate() == I.ICMP_UGE) { + Result = + new ICmpInst(I.ICMP_EQ, A, ConstantInt::getNullValue(A->getType())); + } else { + Result = getConstantIfGreater(false); + } + } else if (IsAShr && AP1.isNegative()) { + int Shift = (~AP2).logBase2() - (~AP1).logBase2(); + if (AP2.slt(AP1)) { + if (AP2.ashr(Shift) == AP1) { + Result = new ICmpInst(I.getPredicate(), A, + ConstantInt::get(A->getType(), Shift)); + } else { + if (AP2.ashr(Shift).ugt(AP1)) + Shift--; + if (I.getPredicate() == I.ICMP_ULT || I.getPredicate() == I.ICMP_ULE) { + Result = new ICmpInst(I.ICMP_ULT, A, + ConstantInt::get(A->getType(), Shift + 1)); + } else { + Result = new ICmpInst(I.ICMP_UGT, A, + ConstantInt::get(A->getType(), Shift)); + } + } + } + } else if (!IsAShr || !AP1.isNegative()) { + if (AP1.ugt(AP2)) { + Result = getConstantIfGreater(false); + } else { + int Shift = AP1.countLeadingZeros() - AP2.countLeadingZeros(); + if (AP1 == AP2.lshr(Shift)) { + if (I.getPredicate() == I.ICMP_ULT) { + Result = new ICmpInst(I.ICMP_UGT, A, + ConstantInt::get(A->getType(), Shift)); + } else if (I.getPredicate() == I.ICMP_ULE) { + Result = new ICmpInst(I.ICMP_UGE, A, + ConstantInt::get(A->getType(), Shift)); + } else if (I.getPredicate() == I.ICMP_UGT) { + Result = new ICmpInst(I.ICMP_ULT, A, + ConstantInt::get(A->getType(), Shift)); + } else { + Result = new ICmpInst(I.ICMP_ULE, A, + ConstantInt::get(A->getType(), Shift)); + } + } else { + if (AP1.ugt(AP2.lshr(Shift))) { + Shift--; + } + if (I.getPredicate() == I.ICMP_ULT || I.getPredicate() == I.ICMP_ULE) { + Result = new ICmpInst(I.ICMP_UGT, A, + ConstantInt::get(A->getType(), Shift)); + } else { + Result = new ICmpInst(I.ICMP_ULE, A, + ConstantInt::get(A->getType(), Shift)); + } + } + } + } + + return Result; +} + /// FoldICmpCstShlCst - Handle "(icmp eq/ne (shl const2, A), const1)" -> /// (icmp eq/ne A, TrailingZeros(const1) - TrailingZeros(const2)). Instruction *InstCombiner::FoldICmpCstShlCst(ICmpInst &I, Value *Op, Value *A, @@ -1311,7 +1408,7 @@ cast(ConstantExpr::getShl(AndCst, ShAmt)); ConstantInt *ShiftedRHSCst = cast(ConstantExpr::getShl(RHS, ShAmt)); - + if (!ShiftedAndCst->isNegative() && !ShiftedRHSCst->isNegative()) CanFold = true; } @@ -2591,15 +2688,20 @@ Builder->getInt(CI->getValue()-1)); } - 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)))) { + ConstantInt *CI2; + if (match(Op0, m_AShr(m_ConstantInt(CI2), m_Value(A))) || + match(Op0, m_LShr(m_ConstantInt(CI2), m_Value(A)))) { + if (I.isEquality()) { // (icmp eq/ne (ashr/lshr const2, A), const1) if (Instruction *Inst = FoldICmpCstShrCst(I, Op0, A, CI, CI2)) return Inst; + } else if (I.isUnsigned()) { + // (icmp ugt/uge/ult/ule (ashr/lshr const2, A), const1) + if (Instruction *Inst = FoldUICmpCstShrCst(I, Op0, A, CI, CI2)) + return Inst; } - if (match(Op0, m_Shl(m_ConstantInt(CI2), m_Value(A)))) { + } else if (match(Op0, m_Shl(m_ConstantInt(CI2), m_Value(A)))) { + if (I.isEquality()) { // (icmp eq/ne (shl const2, A), const1) if (Instruction *Inst = FoldICmpCstShlCst(I, Op0, A, CI, CI2)) return Inst; Index: test/Transforms/InstCombine/icmp-shr.ll =================================================================== --- test/Transforms/InstCombine/icmp-shr.ll +++ test/Transforms/InstCombine/icmp-shr.ll @@ -376,3 +376,219 @@ %cmp = icmp eq i32 %shr, -2 ret i1 %cmp } + +define i1 @ashr_ult_ap1_equal_ap2(i8 %a) { +; CHECK-LABEL: @ashr_ult_ap1_equal_ap2( +; CHECK-NEXT: %cmp = icmp ne i8 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = ashr i8 13, %a + %cmp = icmp ult i8 %shr, 13 + ret i1 %cmp +} + +define i1 @ashr_uge_ap1_equal_ap2(i8 %a) { +; CHECK-LABEL: @ashr_uge_ap1_equal_ap2( +; CHECK-NEXT: %cmp = icmp eq i8 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = ashr i8 13, %a + %cmp = icmp uge i8 %shr, 13 + ret i1 %cmp +} + +define i1 @lshr_ult_ap1_equal_ap2(i8 %a) { +; CHECK-LABEL: @lshr_ult_ap1_equal_ap2( +; CHECK-NEXT: %cmp = icmp ne i8 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = lshr i8 13, %a + %cmp = icmp ult i8 %shr, 13 + ret i1 %cmp +} + +define i1 @lshr_uge_ap1_equal_ap2(i8 %a) { +; CHECK-LABEL: @lshr_uge_ap1_equal_ap2( +; CHECK-NEXT: %cmp = icmp eq i8 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = lshr i8 13, %a + %cmp = icmp uge i8 %shr, 13 + ret i1 %cmp +} + +define i1 @ashr_ugt_ap1_equal_ap2_negative(i8 %a) { +; CHECK-LABEL: @ashr_ugt_ap1_equal_ap2_negative( +; CHECK-NEXT: %cmp = icmp ne i8 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = ashr i8 -13, %a + %cmp = icmp ugt i8 %shr, -13 + ret i1 %cmp +} + +define i1 @ashr_ule_ap1_equal_ap2_negative(i8 %a) { +; CHECK-LABEL: @ashr_ule_ap1_equal_ap2_negative( +; CHECK-NEXT: %cmp = icmp eq i8 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = ashr i8 -13, %a + %cmp = icmp ule i8 %shr, -13 + ret i1 %cmp +} + +define i1 @lshr_uge_ap1_equal_ap2_negative(i8 %a) { +; CHECK-LABEL: @lshr_uge_ap1_equal_ap2_negative( +; CHECK-NEXT: %cmp = icmp eq i8 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = lshr i8 -13, %a + %cmp = icmp uge i8 %shr, -13 + ret i1 %cmp +} + +define i1 @lshr_ult_ap1_equal_ap2_negative(i8 %a) { +; CHECK-LABEL: @lshr_ult_ap1_equal_ap2_negative( +; CHECK-NEXT: %cmp = icmp ne i8 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = lshr i8 -13, %a + %cmp = icmp ult i8 %shr, -13 + ret i1 %cmp +} + +define i1 @ashr_ugt_ap1_negative_ap2_negative_ap1(i32 %a) { +; CHECK-LABEL: @ashr_ugt_ap1_negative_ap2_negative_ap1( +; CHECK-NEXT: %cmp = icmp ne i32 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = ashr i32 -22, %a + %cmp = icmp ugt i32 %shr, -14 + ret i1 %cmp +} + +define i1 @ashr_ult_ap1_negative_ap2_negative_ap1(i32 %a) { +; CHECK-LABEL: @ashr_ult_ap1_negative_ap2_negative_ap1( +; CHECK-NEXT: %cmp = icmp eq i32 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = ashr i32 -22, %a + %cmp = icmp ult i32 %shr, -14 + ret i1 %cmp +} + +define i1 @ashr_uge_ap1_negative_ap2_negative_ap1(i32 %a) { +; CHECK-LABEL: @ashr_uge_ap1_negative_ap2_negative_ap1( +; CHECK-NEXT: %cmp = icmp ne i32 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = ashr i32 -22, %a + %cmp = icmp uge i32 %shr, -14 + ret i1 %cmp +} + +define i1 @ashr_ule_ap1_negative_ap2_negative_ap1(i32 %a) { +; CHECK-LABEL: @ashr_ule_ap1_negative_ap2_negative_ap1( +; CHECK-NEXT: %cmp = icmp eq i32 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = ashr i32 -22, %a + %cmp = icmp ule i32 %shr, -14 + ret i1 %cmp +} + +define i1 @lshr_ugt_ap1_negative_ap2_negative_ap2(i32 %a) { +; CHECK-LABEL: @lshr_ugt_ap1_negative_ap2_negative_ap2( +; CHECK-NEXT: %cmp = icmp eq i32 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = lshr i32 -14, %a + %cmp = icmp ugt i32 %shr, -22 + ret i1 %cmp +} + +define i1 @lshr_ult_ap1_negative_ap2_negative_ap2(i32 %a) { +; CHECK-LABEL: @lshr_ult_ap1_negative_ap2_negative_ap2( +; CHECK-NEXT: %cmp = icmp ne i32 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = lshr i32 -14, %a + %cmp = icmp ult i32 %shr, -22 + ret i1 %cmp +} + +define i1 @lshr_uge_ap1_negative_ap2_negative_ap2(i32 %a) { +; CHECK-LABEL: @lshr_uge_ap1_negative_ap2_negative_ap2( +; CHECK-NEXT: %cmp = icmp eq i32 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = lshr i32 -14, %a + %cmp = icmp uge i32 %shr, -22 + ret i1 %cmp +} + +define i1 @lshr_ule_ap1_negative_ap2_negative_ap2(i32 %a) { +; CHECK-LABEL: @lshr_ule_ap1_negative_ap2_negative_ap2( +; CHECK-NEXT: %cmp = icmp ne i32 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = lshr i32 -14, %a + %cmp = icmp ule i32 %shr, -22 + ret i1 %cmp +} + +define i1 @lshr_ugt_ap1_positive_ap2_positive_ap2(i32 %a) { +; CHECK-LABEL: @lshr_ugt_ap1_positive_ap2_positive_ap2( +; CHECK-NEXT: %cmp = icmp eq i32 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = lshr i32 14, %a + %cmp = icmp ugt i32 %shr, 7 + ret i1 %cmp +} + +define i1 @lshr_ult_ap1_positive_ap2_positive_ap2(i32 %a) { +; CHECK-LABEL: @lshr_ult_ap1_positive_ap2_positive_ap2( +; CHECK-NEXT: %cmp = icmp ugt i32 %a, 1 +; CHECK-NEXT: ret i1 %cmp + %shr = lshr i32 14, %a + %cmp = icmp ult i32 %shr, 7 + ret i1 %cmp +} + +define i1 @lshr_uge_ap1_positive_ap2_positive_ap2(i32 %a) { +; CHECK-LABEL: @lshr_uge_ap1_positive_ap2_positive_ap2( +; CHECK-NEXT: %cmp = icmp ult i32 %a, 2 +; CHECK-NEXT: ret i1 %cmp + %shr = lshr i32 14, %a + %cmp = icmp uge i32 %shr, 7 + ret i1 %cmp +} + +define i1 @lshr_ule_ap1_positive_ap2_positive_ap2(i32 %a) { +; CHECK-LABEL: @lshr_ule_ap1_positive_ap2_positive_ap2( +; CHECK-NEXT: %cmp = icmp ne i32 %a, 0 +; CHECK-NEXT: ret i1 %cmp + %shr = lshr i32 14, %a + %cmp = icmp ule i32 %shr, 7 + ret i1 %cmp +} + +define i1 @lshr_ugt_ap1_positive_ap2_negative(i32 %a) { +; CHECK-LABEL: @lshr_ugt_ap1_positive_ap2_negative( +; CHECK-NEXT: %cmp = icmp ult i32 %a, 29 +; CHECK-NEXT: ret i1 %cmp + %shr = lshr i32 -14, %a + %cmp = icmp ugt i32 %shr, 7 + ret i1 %cmp +} + +define i1 @lshr_ult_ap1_positive_ap2_negative(i32 %a) { +; CHECK-LABEL: @lshr_ult_ap1_positive_ap2_negative( +; CHECK-NEXT: %cmp = icmp ugt i32 %a, 29 +; CHECK-NEXT: ret i1 %cmp + %shr = lshr i32 -14, %a + %cmp = icmp ult i32 %shr, 7 + ret i1 %cmp +} + +define i1 @lshr_uge_ap1_positive_ap2_negative(i32 %a) { +; CHECK-LABEL: @lshr_uge_ap1_positive_ap2_negative( +; CHECK-NEXT: %cmp = icmp ult i32 %a, 30 +; CHECK-NEXT: ret i1 %cmp + %shr = lshr i32 -14, %a + %cmp = icmp uge i32 %shr, 7 + ret i1 %cmp +} + +define i1 @lshr_ule_ap1_positive_ap2_negative(i32 %a) { +; CHECK-LABEL: @lshr_ule_ap1_positive_ap2_negative( +; CHECK-NEXT: %cmp = icmp ugt i32 %a, 28 +; CHECK-NEXT: ret i1 %cmp + %shr = lshr i32 -14, %a + %cmp = icmp ule i32 %shr, 7 + ret i1 %cmp +}