Index: llvm/lib/Transforms/Scalar/ConstraintElimination.cpp =================================================================== --- llvm/lib/Transforms/Scalar/ConstraintElimination.cpp +++ llvm/lib/Transforms/Scalar/ConstraintElimination.cpp @@ -113,8 +113,10 @@ ConstraintTy() = default; - ConstraintTy(SmallVector Coefficients, bool IsSigned, bool IsEq) - : Coefficients(Coefficients), IsSigned(IsSigned), IsEq(IsEq) {} + ConstraintTy(SmallVector Coefficients, bool IsSigned, bool IsEq, + bool IsNe) + : Coefficients(Coefficients), IsSigned(IsSigned), IsEq(IsEq), IsNe(IsNe) { + } unsigned size() const { return Coefficients.size(); } @@ -135,6 +137,7 @@ private: bool IsEq = false; + bool IsNe = false; }; /// Wrapper encapsulating separate constraint systems and corresponding value @@ -423,6 +426,8 @@ SmallVectorImpl &NewVariables) const { assert(NewVariables.empty() && "NewVariables must be empty when passed in"); bool IsEq = false; + bool IsNe = false; + // Try to convert Pred to one of ULE/SLT/SLE/SLT. switch (Pred) { case CmpInst::ICMP_UGT: @@ -442,10 +447,13 @@ } break; case CmpInst::ICMP_NE: - if (!match(Op1, m_Zero())) - return {}; - Pred = CmpInst::getSwappedPredicate(CmpInst::ICMP_UGT); - std::swap(Op0, Op1); + if (match(Op1, m_Zero())) { + Pred = CmpInst::getSwappedPredicate(CmpInst::ICMP_UGT); + std::swap(Op0, Op1); + } else { + IsNe = true; + Pred = CmpInst::ICMP_ULE; + } break; default: break; @@ -492,7 +500,7 @@ // subtracting all coefficients from B. ConstraintTy Res( SmallVector(Value2Index.size() + NewVariables.size() + 1, 0), - IsSigned, IsEq); + IsSigned, IsEq, IsNe); // Collect variables that are known to be positive in all uses in the // constraint. DenseMap KnownNonNegativeVariables; @@ -574,7 +582,7 @@ ConstraintTy::isImpliedBy(const ConstraintSystem &CS) const { bool IsConditionImplied = CS.isConditionImplied(Coefficients); - if (IsEq) { + if (IsEq || IsNe) { auto NegatedOrEqual = ConstraintSystem::negateOrEqual(Coefficients); bool IsNegatedOrEqualImplied = !NegatedOrEqual.empty() && CS.isConditionImplied(NegatedOrEqual); @@ -582,7 +590,7 @@ // In order to check that `%a == %b` is true, we want to check that `%a >= // %b` and `%a <= %b` must hold. if (IsConditionImplied && IsNegatedOrEqualImplied) - return true; + return IsEq; auto Negated = ConstraintSystem::negate(Coefficients); bool IsNegatedImplied = !Negated.empty() && CS.isConditionImplied(Negated); @@ -594,7 +602,7 @@ // In order to check that `%a == %b` is false, we want to check whether // either `%a > %b` or `%a < %b` holds. if (IsNegatedImplied || IsStrictLessThanImplied) - return false; + return IsNe; return std::nullopt; } Index: llvm/test/Transforms/ConstraintElimination/constants-unsigned-predicates.ll =================================================================== --- llvm/test/Transforms/ConstraintElimination/constants-unsigned-predicates.ll +++ llvm/test/Transforms/ConstraintElimination/constants-unsigned-predicates.ll @@ -94,9 +94,9 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: [[T_0:%.*]] = icmp ne i8 10, 11 ; CHECK-NEXT: [[F_0:%.*]] = icmp ne i8 10, 10 -; CHECK-NEXT: [[RES_1:%.*]] = xor i1 [[T_0]], [[F_0]] +; CHECK-NEXT: [[RES_1:%.*]] = xor i1 true, false ; CHECK-NEXT: [[T_1:%.*]] = icmp ne i8 10, 9 -; CHECK-NEXT: [[RES_2:%.*]] = xor i1 [[RES_1]], [[T_1]] +; CHECK-NEXT: [[RES_2:%.*]] = xor i1 [[RES_1]], true ; CHECK-NEXT: ret i1 [[RES_2]] ; entry: Index: llvm/test/Transforms/ConstraintElimination/eq.ll =================================================================== --- llvm/test/Transforms/ConstraintElimination/eq.ll +++ llvm/test/Transforms/ConstraintElimination/eq.ll @@ -32,11 +32,11 @@ ; CHECK-NEXT: [[C_3:%.*]] = icmp uge i8 [[A]], [[B]] ; CHECK-NEXT: [[RES_9:%.*]] = xor i1 [[RES_8]], [[C_3]] ; CHECK-NEXT: [[C_4:%.*]] = icmp ule i8 [[A]], [[B]] -; CHECK-NEXT: [[RES_10:%.*]] = xor i1 [[RES_9]], [[C_4]] +; CHECK-NEXT: [[RES_10:%.*]] = xor i1 [[RES_9]], true ; CHECK-NEXT: [[C_5:%.*]] = icmp ugt i8 [[B]], [[A]] ; CHECK-NEXT: [[RES_11:%.*]] = xor i1 [[RES_10]], [[C_5]] ; CHECK-NEXT: [[C_6:%.*]] = icmp ult i8 [[B]], [[A]] -; CHECK-NEXT: [[RES_12:%.*]] = xor i1 [[RES_11]], [[C_6]] +; CHECK-NEXT: [[RES_12:%.*]] = xor i1 [[RES_11]], false ; CHECK-NEXT: ret i1 [[RES_12]] ; entry: Index: llvm/test/Transforms/ConstraintElimination/geps-128-bit-pointers.ll =================================================================== --- llvm/test/Transforms/ConstraintElimination/geps-128-bit-pointers.ll +++ llvm/test/Transforms/ConstraintElimination/geps-128-bit-pointers.ll @@ -13,7 +13,7 @@ ; CHECK-NEXT: call void @llvm.assume(i1 [[NE]]) ; CHECK-NEXT: [[CMP_ULE:%.*]] = icmp ule ptr [[GEP_1]], [[GEP_2]] ; CHECK-NEXT: [[CMP_UGE:%.*]] = icmp uge ptr [[GEP_1]], [[GEP_2]] -; CHECK-NEXT: [[RES:%.*]] = xor i1 [[CMP_ULE]], [[CMP_ULE]] +; CHECK-NEXT: [[RES:%.*]] = xor i1 true, true ; CHECK-NEXT: ret i1 [[RES]] ; entry: @@ -36,7 +36,7 @@ ; CHECK-NEXT: call void @llvm.assume(i1 [[NE]]) ; CHECK-NEXT: [[CMP_ULE:%.*]] = icmp ule ptr [[GEP_1]], [[GEP_2]] ; CHECK-NEXT: [[CMP_UGE:%.*]] = icmp uge ptr [[GEP_1]], [[GEP_2]] -; CHECK-NEXT: [[RES:%.*]] = xor i1 [[CMP_ULE]], [[CMP_UGE]] +; CHECK-NEXT: [[RES:%.*]] = xor i1 true, [[CMP_UGE]] ; CHECK-NEXT: ret i1 [[RES]] ; entry: Index: llvm/test/Transforms/ConstraintElimination/loops-header-tested-pointer-cmps.ll =================================================================== --- llvm/test/Transforms/ConstraintElimination/loops-header-tested-pointer-cmps.ll +++ llvm/test/Transforms/ConstraintElimination/loops-header-tested-pointer-cmps.ll @@ -493,7 +493,7 @@ ; CHECK-NEXT: [[GEP_IV:%.*]] = getelementptr inbounds i8, ptr [[PTR]], i16 [[IV]] ; CHECK-NEXT: [[CMP_IV_LOWER:%.*]] = icmp ugt ptr [[LOWER]], [[GEP_IV]] ; CHECK-NEXT: [[CMP_IV_UPPER:%.*]] = icmp ule ptr [[UPPER]], [[GEP_IV]] -; CHECK-NEXT: [[OR:%.*]] = or i1 [[CMP_IV_LOWER]], [[CMP_IV_UPPER]] +; CHECK-NEXT: [[OR:%.*]] = or i1 [[CMP_IV_LOWER]], false ; CHECK-NEXT: br i1 [[OR]], label [[TRAP]], label [[FOR_BODY_1:%.*]] ; CHECK: for.body.1: ; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 [[IV]], 1 @@ -579,7 +579,7 @@ ; CHECK-NEXT: [[GEP_IV:%.*]] = getelementptr inbounds i8, ptr [[PTR]], i16 [[IV]] ; CHECK-NEXT: [[CMP_IV_LOWER:%.*]] = icmp ugt ptr [[LOWER]], [[GEP_IV]] ; CHECK-NEXT: [[CMP_IV_UPPER:%.*]] = icmp ule ptr [[UPPER]], [[GEP_IV]] -; CHECK-NEXT: [[OR:%.*]] = or i1 [[CMP_IV_LOWER]], [[CMP_IV_UPPER]] +; CHECK-NEXT: [[OR:%.*]] = or i1 [[CMP_IV_LOWER]], false ; CHECK-NEXT: br i1 [[OR]], label [[TRAP]], label [[FOR_BODY_1:%.*]] ; CHECK: for.body.1: ; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 [[IV]], 1 Index: llvm/test/Transforms/ConstraintElimination/monotonic-int-phis.ll =================================================================== --- llvm/test/Transforms/ConstraintElimination/monotonic-int-phis.ll +++ llvm/test/Transforms/ConstraintElimination/monotonic-int-phis.ll @@ -22,7 +22,7 @@ ; CHECK: for.body: ; CHECK-NEXT: [[T_1:%.*]] = icmp uge i16 [[IV]], 0 ; CHECK-NEXT: [[T_2:%.*]] = icmp ult i16 [[IV]], [[A]] -; CHECK-NEXT: [[AND:%.*]] = and i1 [[T_1]], [[T_2]] +; CHECK-NEXT: [[AND:%.*]] = and i1 [[T_1]], true ; CHECK-NEXT: br i1 [[AND]], label [[LOOP_LATCH]], label [[EXIT]] ; CHECK: loop.latch: ; CHECK-NEXT: call void @use(i16 [[IV]]) @@ -114,7 +114,7 @@ ; CHECK: for.body: ; CHECK-NEXT: [[T_1:%.*]] = icmp uge i16 [[IV]], 0 ; CHECK-NEXT: [[T_2:%.*]] = icmp ult i16 [[IV]], [[A]] -; CHECK-NEXT: [[AND:%.*]] = and i1 [[T_1]], [[T_2]] +; CHECK-NEXT: [[AND:%.*]] = and i1 [[T_1]], true ; CHECK-NEXT: br i1 [[AND]], label [[LOOP_LATCH]], label [[EXIT]] ; CHECK: loop.latch: ; CHECK-NEXT: call void @use(i16 [[IV]]) @@ -168,7 +168,7 @@ ; CHECK: for.body: ; CHECK-NEXT: [[T_1:%.*]] = icmp uge i16 [[IV]], 0 ; CHECK-NEXT: [[T_2:%.*]] = icmp ult i16 [[IV]], [[A]] -; CHECK-NEXT: [[AND:%.*]] = and i1 [[T_1]], [[T_2]] +; CHECK-NEXT: [[AND:%.*]] = and i1 [[T_1]], true ; CHECK-NEXT: br i1 [[AND]], label [[LOOP_LATCH]], label [[EXIT]] ; CHECK: loop.latch: ; CHECK-NEXT: call void @use(i16 [[IV]]) Index: llvm/test/Transforms/ConstraintElimination/ne.ll =================================================================== --- llvm/test/Transforms/ConstraintElimination/ne.ll +++ llvm/test/Transforms/ConstraintElimination/ne.ll @@ -1,6 +1,8 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --check-attributes ; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s +declare void @llvm.assume(i1) + define i1 @test_eq_ne_0(i8 %a, i8 %b) { ; CHECK-LABEL: @test_eq_ne_0( ; CHECK-NEXT: entry: @@ -10,7 +12,7 @@ ; CHECK-NEXT: [[F_1:%.*]] = icmp ne i8 [[A]], 0 ; CHECK-NEXT: [[C_1:%.*]] = icmp ne i8 [[A]], 1 ; CHECK-NEXT: [[C_2:%.*]] = icmp ne i8 [[A]], [[B:%.*]] -; CHECK-NEXT: [[RES_1:%.*]] = xor i1 false, [[C_1]] +; CHECK-NEXT: [[RES_1:%.*]] = xor i1 false, true ; CHECK-NEXT: [[RES_2:%.*]] = xor i1 [[RES_1]], [[C_2]] ; CHECK-NEXT: ret i1 [[RES_2]] ; CHECK: else: @@ -69,7 +71,7 @@ ; CHECK: else: ; CHECK-NEXT: [[F_1:%.*]] = icmp ne i8 [[A]], 0 ; CHECK-NEXT: [[C_7:%.*]] = icmp ne i8 [[A]], 1 -; CHECK-NEXT: [[RES_9:%.*]] = xor i1 false, [[C_7]] +; CHECK-NEXT: [[RES_9:%.*]] = xor i1 false, true ; CHECK-NEXT: [[C_8:%.*]] = icmp ne i8 [[A]], [[B]] ; CHECK-NEXT: [[RES_10:%.*]] = xor i1 [[RES_9]], [[C_8]] ; CHECK-NEXT: [[C_9:%.*]] = icmp eq i8 [[A]], [[B]] @@ -156,7 +158,7 @@ ; CHECK-NEXT: [[F_1:%.*]] = icmp ne i8 [[A]], 0 ; CHECK-NEXT: [[C_1:%.*]] = icmp ne i8 [[A]], 1 ; CHECK-NEXT: [[C_2:%.*]] = icmp ne i8 [[A]], [[B:%.*]] -; CHECK-NEXT: [[RES_1:%.*]] = xor i1 true, [[C_1]] +; CHECK-NEXT: [[RES_1:%.*]] = xor i1 true, false ; CHECK-NEXT: [[RES_2:%.*]] = xor i1 [[RES_1]], [[C_2]] ; CHECK-NEXT: ret i1 [[RES_2]] ; CHECK: else: @@ -215,7 +217,7 @@ ; CHECK: else: ; CHECK-NEXT: [[T_2:%.*]] = icmp ne i8 [[A]], 0 ; CHECK-NEXT: [[C_9:%.*]] = icmp ne i8 [[A]], 1 -; CHECK-NEXT: [[RES_9:%.*]] = xor i1 true, [[C_9]] +; CHECK-NEXT: [[RES_9:%.*]] = xor i1 true, false ; CHECK-NEXT: [[C_10:%.*]] = icmp ne i8 [[A]], [[B]] ; CHECK-NEXT: [[RES_10:%.*]] = xor i1 [[RES_9]], [[C_10]] ; CHECK-NEXT: [[C_11:%.*]] = icmp eq i8 [[A]], [[B]] @@ -292,3 +294,52 @@ ret i1 %res.16 } + +define i1 @assume_b_plus_1_ult_a(i64 %a, i64 %b) { +; CHECK-LABEL: @assume_b_plus_1_ult_a( +; CHECK-NEXT: [[TMP1:%.*]] = add nuw i64 [[B:%.*]], 1 +; CHECK-NEXT: [[TMP2:%.*]] = icmp ult i64 [[TMP1]], [[A:%.*]] +; CHECK-NEXT: tail call void @llvm.assume(i1 [[TMP2]]) +; CHECK-NEXT: [[TMP3:%.*]] = icmp ne i64 [[A]], [[B]] +; CHECK-NEXT: ret i1 true +; + %1 = add nuw i64 %b, 1 + %2 = icmp ult i64 %1, %a + tail call void @llvm.assume(i1 %2) + %3 = icmp ne i64 %a, %b + ret i1 %3 +} + +define i1 @assume_a_gt_b_and_b_ge_c(i64 %a, i64 %b, i64 %c) { +; CHECK-LABEL: @assume_a_gt_b_and_b_ge_c( +; CHECK-NEXT: [[TMP1:%.*]] = icmp ugt i64 [[A:%.*]], [[B:%.*]] +; CHECK-NEXT: tail call void @llvm.assume(i1 [[TMP1]]) +; CHECK-NEXT: [[TMP2:%.*]] = icmp uge i64 [[B]], [[C:%.*]] +; CHECK-NEXT: tail call void @llvm.assume(i1 [[TMP2]]) +; CHECK-NEXT: [[TMP3:%.*]] = icmp ne i64 [[A]], [[C]] +; CHECK-NEXT: ret i1 true +; + %1 = icmp ugt i64 %a, %b + tail call void @llvm.assume(i1 %1) + %2 = icmp uge i64 %b, %c + tail call void @llvm.assume(i1 %2) + %3 = icmp ne i64 %a, %c + ret i1 %3 +} + +define i1 @assume_a_ne_b_and_b_ne_c(i64 %a, i64 %b, i64 %c) { +; CHECK-LABEL: @assume_a_ne_b_and_b_ne_c( +; CHECK-NEXT: [[TMP1:%.*]] = icmp ne i64 [[A:%.*]], [[B:%.*]] +; CHECK-NEXT: tail call void @llvm.assume(i1 [[TMP1]]) +; CHECK-NEXT: [[TMP2:%.*]] = icmp ne i64 [[B]], [[C:%.*]] +; CHECK-NEXT: tail call void @llvm.assume(i1 [[TMP2]]) +; CHECK-NEXT: [[TMP3:%.*]] = icmp ne i64 [[A]], [[C]] +; CHECK-NEXT: ret i1 [[TMP3]] +; + %1 = icmp ne i64 %a, %b + tail call void @llvm.assume(i1 %1) + %2 = icmp ne i64 %b, %c + tail call void @llvm.assume(i1 %2) + %3 = icmp ne i64 %a, %c + ret i1 %3 +}