[ConstantRange] Sign-flipping of signedness-invariant comparisons

[lebedev.ri]

Summary

For certain combination of LHS and RHS constant ranges,
the signedness of the relational comparison predicate is irrelevant.

This implements complete and precise model for all predicates, as confirmed by the brute-force tests.
(although i've conjured this some time ago, so unless i'm not seeing why the test is misleading)

In a follow-up, CVP will make use of this.

Not sure how to generalize ConstantRange::areInsensitiveToSignednessOfSwappedICmpPredicate()

[lebedev.ri]

Ok, doesn't seem useful for SCEV.
Not sure if CVP-based fold is useful, so not really looking for review i guess.

[lebedev.ri]

As discussed/motivated by D111836, let's at least land the ConstantRange support.
I'd be fine landing this as-is, not sure if there is much to review here.

[nikic]

llvm/unittests/IR/ConstantRangeTest.cpp

2448

As a drive-by note without having looked at the rest yet: I'd love to have this publicly available somewhere. Could be used in https://github.com/llvm/llvm-project/blob/2c4a9e830cbb3b91a57902f7ecd508c544701819/llvm/lib/IR/ConstantFold.cpp#L1795-L1807 and I've wanted this on other occasions as well. Not sure where, maybe it could be a static method directly on ICmpInst?

[lebedev.ri]

Consolidated ICmpInst::compare().

[nikic]

llvm/lib/IR/ConstantRange.cpp

171

This implementation reads really confused to me. You should be able to reduce it to just:

if (CR1.isEmptySet() || CR2.isEmptySet())
  return true;

return (CR1.isAllNonNegative() && CR2.isAllNonNegative()) ||
       (CR1.isAllNegative() && CR2.isAllNegative());

I checked that this still passes your tests.

llvm/unittests/IR/ConstantRangeTest.cpp

2449

Use seq_inclusive() to avoid the back and forth casts?

[lebedev.ri]

Nits.

[nikic]

llvm/lib/IR/ConstantRange.cpp

159

Personally I'd convert this to areInsensitiveToSignednessOfInvertedICmpPredicate(), in which case the implementation would be the direct conjugate of the above, i.e.

if (CR1.isEmptySet() || CR2.isEmptySet())
  return true;
      
return (CR1.isAllNonNegative() && CR2.isAllNegative()) ||
       (CR1.isAllNegative() && CR2.isAllNonNegative());

I believe the only difference would be in the treatment of ranges that have a single element intersection (in which case the right canonicalization is probably towards an equality comparison rather than a different sign).

llvm/unittests/IR/ConstantRangeTest.cpp

2449

Isn't it possible to drop the (ICmpInst::Predicate) casts if seq_inclusive is used?

[lebedev.ri]

Thank you for taking a look!
Improved areInsensitiveToSignednessOfICmpPredicate().

llvm/lib/IR/ConstantRange.cpp

159

Hmm, tests suggest that said implementation is (also) precise.
I'm not seeing any obvious bugs in exhaustive test coverage,
so let's do that instead. Again, i don't really recall why this was
the way it it, perhaps i just got discouraged in non-applicability
of this in SCEV, and didn't get it fully cleaned up.

171

Hmm, indeed. I don't really recall why i ended up with that,
i was looking for a complex solution, so i didn't end up
converging on the simplest one.

[lebedev.ri]

Do not pass around srcpred in tests, NFC.

[nikic]

LGTM, thanks!

llvm/include/llvm/IR/ConstantRange.h

142

nit: "maybe inverted" now

Might be worth mentioning that BAD_ICMP_PREDICATE is returned on failure.

145

I find it slightly odd that the other two are static methods but this one is an instance method -- any particular reason for that choice?

[lebedev.ri]

Nits.

[lebedev.ri]

llvm/include/llvm/IR/ConstantRange.h

145

Nothing particular, but i think we are consistently inconsistent with this.
Let's go with static.

llvm/include/llvm/IR/ConstantRange.h

public:
   /// returns the exact answer when the superset of 'union over all y in Other
   /// is exactly same as the subset of intersection over all y in Other.
   /// { x : icmp op x y is true}'.
   ///
   /// Example: Pred = ult and Other = i8 3 returns [0, 3)
   static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred,
                                            const APInt &Other);
 
+  /// Return true iff CR1 ult CR2 is equivalent to CR1 slt CR2.
+  /// Does not depend on strictness/direction of the predicate.
+  static bool
+  areInsensitiveToSignednessOfICmpPredicate(const ConstantRange &CR1,
+                                            const ConstantRange &CR2);
+
+  /// Return true iff CR1 ult CR2 is equivalent to CR1 sgt CR2.
+  static bool
+  areInsensitiveToSignednessOfSwappedICmpPredicate(const ConstantRange &CR1,
+                                                   const ConstantRange &CR2);
+
+  /// If the comparison between constant ranges this and Other
+  /// is insensitive to the signedness of the comparison predicate,
+  /// return a predicate equivalent to \p Pred, with flipped signedness
+  /// (i.e. unsigned instead of signed or vice versa), and maybe swapped.
+  CmpInst::Predicate
+  getEquivalentPredWithFlippedSignedness(CmpInst::Predicate Pred,
+                                         const ConstantRange &Other) const;
+
   /// Produce the largest range containing all X such that "X BinOp Y" is
   /// guaranteed not to wrap (overflow) for *all* Y in Other. However, there may
   /// be *some* Y in Other for which additional X not contained in the result
   /// also do not overflow.
   ///
   /// NoWrapKind must be one of OBO::NoUnsignedWrap or OBO::NoSignedWrap.
   ///
   /// Examples:

llvm/lib/Analysis/ScalarEvolution.cpp

assert(getTypeSizeInBits(LHS->getType()) ==
          "LHS and RHS have different sizes?");
   assert(getTypeSizeInBits(FoundLHS->getType()) ==
              getTypeSizeInBits(FoundRHS->getType()) &&
          "FoundLHS and FoundRHS have different sizes?");
   // We want to avoid hurting the compile time with analysis of too big trees.
   if (Depth > MaxSCEVOperationsImplicationDepth)
     return false;
 
+//   // We want signed comparisons, so if it's and unsigned one,
+//   // see if it can be just replaced with a signed one..
+//   if (ICmpInst::isUnsigned(Pred)) {
+//     ICmpInst::Predicate SignedPred =
+//         getSignedRange(LHS).getEquivalentPredWithFlippedSignedness(
+//             Pred, getSignedRange(RHS));
+//     if (SignedPred != CmpInst::Predicate::BAD_ICMP_PREDICATE)
+//       Pred = SignedPred;
+//   }
+
   // We only want to work with GT comparison so far.
-  if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_SLT) {
+  if (ICmpInst::isLT(Pred)) {
     Pred = CmpInst::getSwappedPredicate(Pred);
     std::swap(LHS, RHS);
     std::swap(FoundLHS, FoundRHS);
   }
-
+/*
    // For unsigned, try to reduce it to corresponding signed comparison.
    if (Pred == ICmpInst::ICMP_UGT)
      // We can replace unsigned predicate with its signed counterpart if all
      // involved values are non-negative.
      // TODO: We could have better support for unsigned.
      if (isKnownNonNegative(FoundLHS) && isKnownNonNegative(FoundRHS)) {
        // Knowing that both FoundLHS and FoundRHS are non-negative, and knowing
        // FoundLHS >u FoundRHS, we also know that FoundLHS >s FoundRHS. Let us
        // use this fact to prove that LHS and RHS are non-negative.
        const SCEV *MinusOne = getMinusOne(LHS->getType());
        if (isImpliedCondOperands(ICmpInst::ICMP_SGT, LHS, MinusOne, FoundLHS,
                                  FoundRHS) &&
            isImpliedCondOperands(ICmpInst::ICMP_SGT, RHS, MinusOne, FoundLHS,
                                  FoundRHS))
          Pred = ICmpInst::ICMP_SGT;
-    }
+     }*/
 
   if (Pred != ICmpInst::ICMP_SGT)
     return false;
 
   auto GetOpFromSExt = [&](const SCEV *S) {
     if (auto *Ext = dyn_cast<SCEVSignExtendExpr>(S))
       return Ext->getOperand();
     // TODO: If S is a SCEVConstant then you can cheaply "strip" the sext off

llvm/lib/IR/ConstantRange.cpp

ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred,
   // when RHS is a singleton such as an APInt and so the assert is valid.
   // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
   // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
   //
   assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C));
   return makeAllowedICmpRegion(Pred, C);
 }
 
+bool ConstantRange::areInsensitiveToSignednessOfICmpPredicate(
+    const ConstantRange &CR1, const ConstantRange &CR2) {
+  if (CR1.isEmptySet() || CR2.isEmptySet())
+    return true;
+
+  if (CR1.isFullSet() || CR2.isFullSet())
+    return false;
+  if (CR1.isWrappedSet() || CR2.isWrappedSet())
+    return false;
+  if (CR1.isSignWrappedSet() || CR2.isSignWrappedSet())
+    return false;
+
+  if (CR1.contains(CR2) || CR2.contains(CR1))
+    return true;
+
+  if (CR1.isAllNonNegative() && CR2.isAllNonNegative())
+    return true;
+
+  if (CR1.isAllNegative() && CR2.isAllNegative())
+    return !CR1.isUpperWrapped() || !CR2.isUpperWrapped();
+
+  return false;
+};
+
+bool ConstantRange::areInsensitiveToSignednessOfSwappedICmpPredicate(
+    const ConstantRange &CR1, const ConstantRange &CR2) {
+  if (CR1.isEmptySet() || CR2.isEmptySet())
+    return true;
+  if (CR1.isFullSet() || CR2.isFullSet())
+    return false;
+
+  bool TrulyEquivalent = true;
+
+  for (auto N1 : {CR1.getUnsignedMin(), CR1.getUnsignedMax(),
+                  CR1.getSignedMin(), CR1.getSignedMax()})
+    for (auto N2 : {CR2.getUnsignedMin(), CR2.getUnsignedMax(),
+                    CR2.getSignedMin(), CR2.getSignedMax()})
+      TrulyEquivalent &= N1.slt(N2) == N1.ugt(N2);
+
+  return TrulyEquivalent;
+};
+
+CmpInst::Predicate ConstantRange::getEquivalentPredWithFlippedSignedness(
+    CmpInst::Predicate Pred, const ConstantRange &Other) const {
+  assert(CmpInst::isIntPredicate(Pred) && CmpInst::isRelational(Pred) &&
+         "Only for relational integer predicates!");
+
+  CmpInst::Predicate FlippedSignednessPred =
+      CmpInst::getFlippedSignednessPredicate(Pred);
+
+  if (areInsensitiveToSignednessOfICmpPredicate(*this, Other))
+    return FlippedSignednessPred;
+
+  if (areInsensitiveToSignednessOfSwappedICmpPredicate(*this, Other))
+    return CmpInst::getSwappedPredicate(FlippedSignednessPred);
+
+  return CmpInst::Predicate::BAD_ICMP_PREDICATE;
+}
+
 bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
                                       APInt &RHS) const {
   bool Success = false;
 
   if (isFullSet() || isEmptySet()) {
     Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
     RHS = APInt(getBitWidth(), 0);
     Success = true;

llvm/test/Transforms/CorrelatedValuePropagation/basic.ll

 ; CHECK-LABEL: @smin(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A:%.*]], 5
 ; CHECK-NEXT:    br i1 [[CMP]], label [[A_GUARD:%.*]], label [[OUT:%.*]]
 ; CHECK:       a_guard:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[B:%.*]], 20
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[B_GUARD:%.*]], label [[OUT]]
 ; CHECK:       b_guard:
-; CHECK-NEXT:    [[SEL_CMP:%.*]] = icmp sle i32 [[A]], [[B]]
-; CHECK-NEXT:    [[MIN:%.*]] = select i1 [[SEL_CMP]], i32 [[A]], i32 [[B]]
+; CHECK-NEXT:    [[SEL_CMP1:%.*]] = icmp ule i32 [[A]], [[B]]
+; CHECK-NEXT:    [[MIN:%.*]] = select i1 [[SEL_CMP1]], i32 [[A]], i32 [[B]]
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       out:
 ; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %cmp = icmp ult i32 %a, 5
   br i1 %cmp, label %a_guard, label %out
 

 ; CHECK-LABEL: @smax(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[A:%.*]], 5
 ; CHECK-NEXT:    br i1 [[CMP]], label [[A_GUARD:%.*]], label [[OUT:%.*]]
 ; CHECK:       a_guard:
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[B:%.*]], 20
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[B_GUARD:%.*]], label [[OUT]]
 ; CHECK:       b_guard:
-; CHECK-NEXT:    [[SEL_CMP:%.*]] = icmp sge i32 [[A]], [[B]]
-; CHECK-NEXT:    [[MAX:%.*]] = select i1 [[SEL_CMP]], i32 [[A]], i32 [[B]]
+; CHECK-NEXT:    [[SEL_CMP1:%.*]] = icmp uge i32 [[A]], [[B]]
+; CHECK-NEXT:    [[MAX:%.*]] = select i1 [[SEL_CMP1]], i32 [[A]], i32 [[B]]
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       out:
 ; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %cmp = icmp sgt i32 %a, 5
   br i1 %cmp, label %a_guard, label %out
 

 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[A]], -20
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[CMP1]], [[CMP2]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[GUARD:%.*]], label [[EXIT:%.*]]
 ; CHECK:       guard:
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 0, [[A]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[A]], 0
 ; CHECK-NEXT:    [[ABS:%.*]] = select i1 [[CMP]], i32 [[SUB]], i32 [[A]]
 ; CHECK-NEXT:    store i1 true, i1* [[P:%.*]], align 1
-; CHECK-NEXT:    [[C2:%.*]] = icmp slt i32 [[ABS]], 19
-; CHECK-NEXT:    store i1 [[C2]], i1* [[P]], align 1
+; CHECK-NEXT:    [[C21:%.*]] = icmp ult i32 [[ABS]], 19
+; CHECK-NEXT:    store i1 [[C21]], i1* [[P]], align 1
 ; CHECK-NEXT:    store i1 true, i1* [[P]], align 1
-; CHECK-NEXT:    [[C4:%.*]] = icmp sge i32 [[ABS]], 1
-; CHECK-NEXT:    store i1 [[C4]], i1* [[P]], align 1
+; CHECK-NEXT:    [[C42:%.*]] = icmp uge i32 [[ABS]], 1
+; CHECK-NEXT:    store i1 [[C42]], i1* [[P]], align 1
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cmp1 = icmp slt i32 %a, 10
   %cmp2 = icmp sgt i32 %a, -20
   %and = and i1 %cmp1, %cmp2

 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[A]], -20
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[CMP1]], [[CMP2]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[GUARD:%.*]], label [[EXIT:%.*]]
 ; CHECK:       guard:
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 0, [[A]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i32 [[A]], 0
 ; CHECK-NEXT:    [[ABS:%.*]] = select i1 [[CMP]], i32 [[A]], i32 [[SUB]]
 ; CHECK-NEXT:    store i1 true, i1* [[P:%.*]], align 1
-; CHECK-NEXT:    [[C2:%.*]] = icmp slt i32 [[ABS]], 19
-; CHECK-NEXT:    store i1 [[C2]], i1* [[P]], align 1
+; CHECK-NEXT:    [[C21:%.*]] = icmp ult i32 [[ABS]], 19
+; CHECK-NEXT:    store i1 [[C21]], i1* [[P]], align 1
 ; CHECK-NEXT:    store i1 true, i1* [[P]], align 1
-; CHECK-NEXT:    [[C4:%.*]] = icmp sge i32 [[ABS]], 1
-; CHECK-NEXT:    store i1 [[C4]], i1* [[P]], align 1
+; CHECK-NEXT:    [[C42:%.*]] = icmp uge i32 [[ABS]], 1
+; CHECK-NEXT:    store i1 [[C42]], i1* [[P]], align 1
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cmp1 = icmp slt i32 %a, 10
   %cmp2 = icmp sgt i32 %a, -20
   %and = and i1 %cmp1, %cmp2

llvm/test/Transforms/CorrelatedValuePropagation/deopt.ll

taken:
   ret void
 untaken:
   ret void
 }
 define void @test3(i1 %c, i1 %c2) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C:%.*]], i64 0, i64 1
 ; CHECK-NEXT:    [[SEL2:%.*]] = select i1 [[C2:%.*]], i64 [[SEL]], i64 2
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i64 [[SEL2]], 1
-; CHECK-NEXT:    br i1 [[CMP]], label [[TAKEN:%.*]], label [[UNTAKEN:%.*]]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ugt i64 [[SEL2]], 1
+; CHECK-NEXT:    br i1 [[CMP1]], label [[TAKEN:%.*]], label [[UNTAKEN:%.*]]
 ; CHECK:       taken:
 ; CHECK-NEXT:    call void @use() [ "deopt"(i64 2) ]
 ; CHECK-NEXT:    ret void
 ; CHECK:       untaken:
 ; CHECK-NEXT:    ret void
 ;
   %sel = select i1 %c, i64 0, i64 1
   %sel2 = select i1 %c2, i64 %sel, i64 2
   %cmp = icmp sgt i64 %sel2, 1
   br i1 %cmp, label %taken, label %untaken
 taken:
   call void @use() ["deopt" (i64 %sel2)]
   ret void
 untaken:
   ret void
 }
 
 define void @test4(i1 %c, i1 %c2) {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C:%.*]], i64 0, i64 1
 ; CHECK-NEXT:    [[SEL2:%.*]] = select i1 [[C2:%.*]], i64 0, i64 1
 ; CHECK-NEXT:    [[ADD1:%.*]] = add nuw nsw i64 0, [[SEL]]
 ; CHECK-NEXT:    [[ADD2:%.*]] = add nuw nsw i64 [[ADD1]], [[SEL2]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i64 [[ADD2]], 1
-; CHECK-NEXT:    br i1 [[CMP]], label [[TAKEN:%.*]], label [[UNTAKEN:%.*]]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ugt i64 [[ADD2]], 1
+; CHECK-NEXT:    br i1 [[CMP1]], label [[TAKEN:%.*]], label [[UNTAKEN:%.*]]
 ; CHECK:       taken:
 ; CHECK-NEXT:    call void @use() [ "deopt"(i64 2) ]
 ; CHECK-NEXT:    ret void
 ; CHECK:       untaken:
 ; CHECK-NEXT:    ret void
 ;
   %sel = select i1 %c, i64 0, i64 1
   %sel2 = select i1 %c2, i64 0, i64 1

llvm/test/Transforms/CorrelatedValuePropagation/minmaxabs.ll

;
   call void @use(i1 %c2)
   ret void
 }
 
 define void @test_smax(i32 %x) {
 ; CHECK-LABEL: @test_smax(
 ; CHECK-NEXT:    [[M:%.*]] = call i32 @llvm.smax.i32(i32 [[X:%.*]], i32 10)
 ; CHECK-NEXT:    call void @use(i1 true)
-; CHECK-NEXT:    [[C2:%.*]] = icmp sgt i32 [[M]], 10
-; CHECK-NEXT:    call void @use(i1 [[C2]])
+; CHECK-NEXT:    [[C21:%.*]] = icmp ugt i32 [[M]], 10
+; CHECK-NEXT:    call void @use(i1 [[C21]])
 ; CHECK-NEXT:    ret void
 ;
   %m = call i32 @llvm.smax.i32(i32 %x, i32 10)
   %c1 = icmp sge i32 %m, 10
   call void @use(i1 %c1)
   %c2 = icmp sgt i32 %m, 10
   call void @use(i1 %c2)
   ret void
;
   call void @use(i1 %c2)
   ret void
 }
 
 define void @test_abs3(i32 %x) {
 ; CHECK-LABEL: @test_abs3(
 ; CHECK-NEXT:    [[A:%.*]] = call i32 @llvm.abs.i32(i32 [[X:%.*]], i1 true)
 ; CHECK-NEXT:    call void @use(i1 true)
-; CHECK-NEXT:    [[C2:%.*]] = icmp sgt i32 [[A]], 0
-; CHECK-NEXT:    call void @use(i1 [[C2]])
+; CHECK-NEXT:    [[C21:%.*]] = icmp ugt i32 [[A]], 0
+; CHECK-NEXT:    call void @use(i1 [[C21]])
 ; CHECK-NEXT:    ret void
 ;
   %a = call i32 @llvm.abs.i32(i32 %x, i1 true)
   %c1 = icmp sge i32 %a, 0
   call void @use(i1 %c1)
   %c2 = icmp sgt i32 %a, 0
   call void @use(i1 %c2)
   ret void
 }

llvm/test/Transforms/CorrelatedValuePropagation/overflow_predicate.ll

 define i1 @sadd_ov_true(i8 %x, i8* %px, i1* %pc) {
 ; CHECK-LABEL: @sadd_ov_true(
 ; CHECK-NEXT:    [[VAL_OV:%.*]] = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[X:%.*]], i8 100)
 ; CHECK-NEXT:    [[VAL:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 0
 ; CHECK-NEXT:    store i8 [[VAL]], i8* [[PX:%.*]], align 1
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[OVERFLOW:%.*]], label [[TRAP:%.*]]
 ; CHECK:       overflow:
-; CHECK-NEXT:    [[C1:%.*]] = icmp sgt i8 [[X]], 28
-; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]], align 1
+; CHECK-NEXT:    [[C11:%.*]] = icmp ugt i8 [[X]], 28
+; CHECK-NEXT:    store i1 [[C11]], i1* [[PC:%.*]], align 1
 ; CHECK-NEXT:    ret i1 true
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ;
   %val_ov = call {i8, i1} @llvm.sadd.with.overflow(i8 %x, i8 100)
   %val = extractvalue {i8, i1} %val_ov, 0
   store i8 %val, i8* %px

 define i1 @ssub_ov_true(i8 %x, i8* %px, i1* %pc) {
 ; CHECK-LABEL: @ssub_ov_true(
 ; CHECK-NEXT:    [[VAL_OV:%.*]] = call { i8, i1 } @llvm.ssub.with.overflow.i8(i8 [[X:%.*]], i8 100)
 ; CHECK-NEXT:    [[VAL:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 0
 ; CHECK-NEXT:    store i8 [[VAL]], i8* [[PX:%.*]], align 1
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[OVERFLOW:%.*]], label [[TRAP:%.*]]
 ; CHECK:       overflow:
-; CHECK-NEXT:    [[C1:%.*]] = icmp slt i8 [[X]], -29
-; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]], align 1
+; CHECK-NEXT:    [[C11:%.*]] = icmp ult i8 [[X]], -29
+; CHECK-NEXT:    store i1 [[C11]], i1* [[PC:%.*]], align 1
 ; CHECK-NEXT:    ret i1 true
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ;
   %val_ov = call {i8, i1} @llvm.ssub.with.overflow(i8 %x, i8 100)
   %val = extractvalue {i8, i1} %val_ov, 0
   store i8 %val, i8* %px

llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll

 ; CHECK:       trap:
 ; CHECK-NEXT:    tail call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont:
 ; CHECK-NEXT:    [[TMP3:%.*]] = extractvalue { i32, i1 } [[TMP1]], 0
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[TMP3]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP1]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
 ; CHECK:       lor.lhs.false:
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[Y]], 0
-; CHECK-NEXT:    br i1 [[CMP2]], label [[LAND_LHS_TRUE3:%.*]], label [[COND_FALSE]]
+; CHECK-NEXT:    [[CMP21:%.*]] = icmp ugt i32 [[Y]], 0
+; CHECK-NEXT:    br i1 [[CMP21]], label [[LAND_LHS_TRUE3:%.*]], label [[COND_FALSE]]
 ; CHECK:       land.lhs.true3:
 ; CHECK-NEXT:    [[TMP4:%.*]] = sub nsw i32 -2147483648, [[Y]]
 ; CHECK-NEXT:    [[TMP5:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[TMP4]], 0
 ; CHECK-NEXT:    [[TMP6:%.*]] = extractvalue { i32, i1 } [[TMP5]], 1
 ; CHECK-NEXT:    br i1 [[TMP6]], label [[TRAP]], label [[CONT4:%.*]]
 ; CHECK:       cont4:
 ; CHECK-NEXT:    [[TMP7:%.*]] = extractvalue { i32, i1 } [[TMP5]], 0
 ; CHECK-NEXT:    [[CMP5:%.*]] = icmp sgt i32 [[TMP7]], [[X]]

llvm/test/Transforms/CorrelatedValuePropagation/range.ll

 
 define i32 @test3(i32 %c) nounwind {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[C:%.*]], 2
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    ret i32 1
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[C]], 3
-; CHECK-NEXT:    br i1 [[CMP1]], label [[IF_THEN2:%.*]], label [[IF_END8:%.*]]
+; CHECK-NEXT:    [[CMP11:%.*]] = icmp ult i32 [[C]], 3
+; CHECK-NEXT:    br i1 [[CMP11]], label [[IF_THEN2:%.*]], label [[IF_END8:%.*]]
 ; CHECK:       if.then2:
 ; CHECK-NEXT:    br i1 true, label [[IF_THEN4:%.*]], label [[IF_END6:%.*]]
 ; CHECK:       if.end6:
 ; CHECK-NEXT:    ret i32 2
 ; CHECK:       if.then4:
 ; CHECK-NEXT:    ret i32 3
 ; CHECK:       if.end8:
 ; CHECK-NEXT:    ret i32 4

llvm/test/Transforms/CorrelatedValuePropagation/sdiv.ll

 ; same test as above with assume instead of guard.
 declare void @llvm.assume(i1)
 define void @test5(i32 %n) {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[A:%.*]] = phi i32 [ [[N]], [[ENTRY:%.*]] ], [ [[DIV1:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[COND:%.*]] = icmp sgt i32 [[A]], 4
-; CHECK-NEXT:    call void @llvm.assume(i1 [[COND]])
-; CHECK-NEXT:    [[DIV1]] = udiv i32 [[A]], 6
-; CHECK-NEXT:    [[LOOPCOND:%.*]] = icmp sgt i32 [[DIV1]], 8
-; CHECK-NEXT:    br i1 [[LOOPCOND]], label [[LOOP]], label [[EXIT]]
+; CHECK-NEXT:    [[A:%.*]] = phi i32 [ [[N]], [[ENTRY:%.*]] ], [ [[DIV2:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[COND1:%.*]] = icmp ugt i32 [[A]], 4
+; CHECK-NEXT:    call void @llvm.assume(i1 [[COND1]])
+; CHECK-NEXT:    [[DIV2]] = udiv i32 [[A]], 6
+; CHECK-NEXT:    [[LOOPCOND3:%.*]] = icmp ugt i32 [[DIV2]], 8
+; CHECK-NEXT:    br i1 [[LOOPCOND3]], label [[LOOP]], label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cmp = icmp sgt i32 %n, 0
   br i1 %cmp, label %loop, label %exit
 
 loop:

llvm/test/Transforms/CorrelatedValuePropagation/srem.ll

 ; because of the assume before it, so we can transform it to urem.
 declare void @llvm.assume(i1)
 define void @test4(i32 %n) {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[A:%.*]] = phi i32 [ [[N]], [[ENTRY:%.*]] ], [ [[REM1:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[COND:%.*]] = icmp sgt i32 [[A]], 4
-; CHECK-NEXT:    call void @llvm.assume(i1 [[COND]])
-; CHECK-NEXT:    [[REM1]] = urem i32 [[A]], 17
-; CHECK-NEXT:    [[LOOPCOND:%.*]] = icmp sgt i32 [[REM1]], 8
-; CHECK-NEXT:    br i1 [[LOOPCOND]], label [[LOOP]], label [[EXIT]]
+; CHECK-NEXT:    [[A:%.*]] = phi i32 [ [[N]], [[ENTRY:%.*]] ], [ [[REM2:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[COND1:%.*]] = icmp ugt i32 [[A]], 4
+; CHECK-NEXT:    call void @llvm.assume(i1 [[COND1]])
+; CHECK-NEXT:    [[REM2]] = urem i32 [[A]], 17
+; CHECK-NEXT:    [[LOOPCOND3:%.*]] = icmp ugt i32 [[REM2]], 8
+; CHECK-NEXT:    br i1 [[LOOPCOND3]], label [[LOOP]], label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cmp = icmp sgt i32 %n, 0
   br i1 %cmp, label %loop, label %exit
 
 loop:

llvm/unittests/IR/ConstantRangeTest.cpp

 //===- ConstantRangeTest.cpp - ConstantRange tests ------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/ADT/BitVector.h"
 #include "llvm/IR/ConstantRange.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/Sequence.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/Support/KnownBits.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
TEST_F(ConstantRangeTest, binaryNot) {
   TestUnsignedUnaryOpExhaustive(
       [](const ConstantRange &CR) {
         return ConstantRange(APInt::getAllOnesValue(CR.getBitWidth()))
             .binaryXor(CR);
       },
       [](const APInt &N) { return ~N; });
 }
 
-}  // anonymous namespace
+bool compare(const APInt &LHS, const APInt &RHS, ICmpInst::Predicate Pred) {
+  assert(ICmpInst::isIntPredicate(Pred) && "Only for integer predicates!");
+  switch (Pred) {
+  case ICmpInst::Predicate::ICMP_EQ:
+    return LHS.eq(RHS);
+  case ICmpInst::Predicate::ICMP_NE:
+    return LHS.ne(RHS);
+  case ICmpInst::Predicate::ICMP_UGT:
+    return LHS.ugt(RHS);
+  case ICmpInst::Predicate::ICMP_UGE:
+    return LHS.uge(RHS);
+  case ICmpInst::Predicate::ICMP_ULT:
+    return LHS.ult(RHS);
+  case ICmpInst::Predicate::ICMP_ULE:
+    return LHS.ule(RHS);
+  case ICmpInst::Predicate::ICMP_SGT:
+    return LHS.sgt(RHS);
+  case ICmpInst::Predicate::ICMP_SGE:
+    return LHS.sge(RHS);
+  case ICmpInst::Predicate::ICMP_SLT:
+    return LHS.slt(RHS);
+  case ICmpInst::Predicate::ICMP_SLE:
+    return LHS.sle(RHS);
+  default:
+    llvm_unreachable("Unexpected non-integer predicate.");
+  };
+}
+
+template <typename T>
+void testConstantRangeICmpPredEquivalence(ICmpInst::Predicate SrcPred, T Func) {
+  unsigned Bits = 4;
+  EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
+                                       const ConstantRange &CR2) {
+    ICmpInst::Predicate TgtPred;
+    bool ExpectedEquivalent;
+    std::tie(TgtPred, ExpectedEquivalent) = Func(CR1, CR2, SrcPred);
+    if (TgtPred == CmpInst::Predicate::BAD_ICMP_PREDICATE)
+      return;
+    bool TrulyEquivalent = true;
+    ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
+      if (!TrulyEquivalent)
+        return;
+      ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
+        if (!TrulyEquivalent)
+          return;
+        TrulyEquivalent &= compare(N1, N2, SrcPred) == compare(N1, N2, TgtPred);
+      });
+    });
+    ASSERT_EQ(TrulyEquivalent, ExpectedEquivalent);
+  });
+}
+
+TEST_F(ConstantRangeTest, areInsensitiveToSignednessOfICmpPredicate) {
+  for (auto Pred : seq((unsigned)ICmpInst::Predicate::FIRST_ICMP_PREDICATE,
+                       ICmpInst::Predicate::LAST_ICMP_PREDICATE + 1)) {
+    if (ICmpInst::isEquality((ICmpInst::Predicate)Pred))
+      continue;
+    ICmpInst::Predicate FlippedSignednessPred =
+        ICmpInst::getFlippedSignednessPredicate((ICmpInst::Predicate)Pred);
+    testConstantRangeICmpPredEquivalence(
+        (ICmpInst::Predicate)Pred,
+        [FlippedSignednessPred](const ConstantRange &CR1,
+                                const ConstantRange &CR2,
+                                ICmpInst::Predicate SrcPred) {
+          return std::make_pair(
+              FlippedSignednessPred,
+              ConstantRange::areInsensitiveToSignednessOfICmpPredicate(CR1,
+                                                                       CR2));
+        });
+  }
+}
+
+TEST_F(ConstantRangeTest, areInsensitiveToSignednessOfSwappedICmpPredicate) {
+  for (auto Pred : seq((unsigned)ICmpInst::Predicate::FIRST_ICMP_PREDICATE,
+                       ICmpInst::Predicate::LAST_ICMP_PREDICATE + 1)) {
+    if (ICmpInst::isEquality((ICmpInst::Predicate)Pred))
+      continue;
+    ICmpInst::Predicate FlippedSignednessPred =
+        ICmpInst::getFlippedSignednessPredicate((ICmpInst::Predicate)Pred);
+    ICmpInst::Predicate SwappedFlippedSignednessPred =
+        ICmpInst::getSwappedPredicate(FlippedSignednessPred);
+    testConstantRangeICmpPredEquivalence(
+        (ICmpInst::Predicate)Pred,
+        [SwappedFlippedSignednessPred](const ConstantRange &CR1,
+                                       const ConstantRange &CR2,
+                                       ICmpInst::Predicate SrcPred) {
+          return std::make_pair(
+              SwappedFlippedSignednessPred,
+              ConstantRange::areInsensitiveToSignednessOfSwappedICmpPredicate(
+                  CR1, CR2));
+        });
+  }
+}
+
+TEST_F(ConstantRangeTest, getEquivalentPredWithFlippedSignedness) {
+  for (auto Pred : seq((unsigned)ICmpInst::Predicate::FIRST_ICMP_PREDICATE,
+                       ICmpInst::Predicate::LAST_ICMP_PREDICATE + 1)) {
+    if (ICmpInst::isEquality((ICmpInst::Predicate)Pred))
+      continue;
+    testConstantRangeICmpPredEquivalence(
+        (ICmpInst::Predicate)Pred,
+        [](const ConstantRange &CR1, const ConstantRange &CR2,
+           ICmpInst::Predicate SrcPred) {
+          return std::make_pair(
+              CR1.getEquivalentPredWithFlippedSignedness(SrcPred, CR2), true);
+        });
+  }
+}
+
+} // anonymous namespace