[ValueTracking] add UGT/UGE and SGT/SGE in `isImpliedCondOperands`

[floatshadow]

Summary

partially fix https://github.com/llvm/llvm-project/issues/62441

the ugt/uge and sgt/sge icmp is not fold as isImpliedCondOperands only handles less cases

alive2 proof: https://alive2.llvm.org/ce/z/jLFDAv and https://alive2.llvm.org/ce/z/Z8idUd

[floatshadow]

update test cases

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

8004

nit: fmt.

[floatshadow]

address comments

llvm/lib/Analysis/ValueTracking.cpp

8004

got aligned.

[goldstein.w.n]

LGTM. I'm not a maintainer to please wait a day or so to push so other have a chance to see.

[floatshadow]

In D149510#4307842, @goldstein.w.n wrote:

LGTM. I'm not a maintainer to please wait a day or so to push so other have a chance to see.

Thanks. I am not sure why isImpliedCondOperands handles less case only. Do we expect instcombine will canonicalize this?

[goldstein.w.n]

In D149510#4308323, @floatshadow wrote:

In D149510#4307842, @goldstein.w.n wrote:

LGTM. I'm not a maintainer to please wait a day or so to push so other have a chance to see.

Thanks. I am not surely why isImpliedCondOperands handles less case only. Do we expect instcombine will canonicalize this?

I'm not really sure. I think probably alot of the patterns are scattered around instcombine + instsimplify but
probably also alot of holes that just havent been filled in yet and could use patches.

Maybe @nikic knows.

[floatshadow]

ping

I have no commit access

[nikic]

The extension to isImpliedCondOperands seems pretty reasonable to me. However, I think we should also handle the sgt/sge case at the same time, otherwise we're still going to leave this incomplete. We can test this part using variations of the existing patterns in the test, e.g. https://alive2.llvm.org/ce/z/Z8idUd.

The new check in isTruePredicate I'm somewhat skeptical about. It adds support for one special case, but there are many other cases where we could determine that the predicate is true. This is essentially what the purpose of simplifyICmpInst is, and which presumably would already handle this pattern. However, there are likely compile-time concerns with just calling into InstSimplify here.

[floatshadow]

In D149510#4315073, @nikic wrote:

The extension to isImpliedCondOperands seems pretty reasonable to me. However, I think we should also handle the sgt/sge case at the same time, otherwise we're still going to leave this incomplete. We can test this part using variations of the existing patterns in the test, e.g. https://alive2.llvm.org/ce/z/Z8idUd.

The new check in isTruePredicate I'm somewhat skeptical about. It adds support for one special case, but there are many other cases where we could determine that the predicate is true. This is essentially what the purpose of simplifyICmpInst is, and which presumably would already handle this pattern. However, there are likely compile-time concerns with just calling into InstSimplify here.

I'd like to split the patch into smaller pieces, and this revision for isImpliedCondOperands only.
Yes, I found that contraint elimination pass and icmp imply called by simplifyICmpInst have handle the simple case. But the former failed on the eq checks (issue 61393) and the latter only checks X + C like pattern (issue 62441)

[floatshadow]

test case for extension to isImpliedCondOperands with SGT/SGE check

[floatshadow]

split the patch

[nikic]

Could you please also add tests for the other variations? sge/ugt/uge?

[floatshadow]

update sge/sgt/uge/ugt case

[nikic]

Could you please also add some negative tests, e.g. where for unsigned predicate the nuw is missing? To make sure the correct implication check is done.

[floatshadow]

rebase

[nikic]

LGTM. Could you please share the Name <email> to use for the commit?

[floatshadow]

In D149510#4316644, @nikic wrote:

LGTM. Could you please share the Name <email> to use for the commit?

Siyuan Zhu, [e-mail]

llvm/lib/Analysis/ValueTracking.cpp

 
   case CmpInst::ICMP_SLT:
   case CmpInst::ICMP_SLE:
     if (isTruePredicate(CmpInst::ICMP_SLE, BLHS, ALHS, DL, Depth) &&
         isTruePredicate(CmpInst::ICMP_SLE, ARHS, BRHS, DL, Depth))
       return true;
     return std::nullopt;
 
+  case CmpInst::ICMP_SGT:
+  case CmpInst::ICMP_SGE:
+    if (isTruePredicate(CmpInst::ICMP_SLE, ALHS, BLHS, DL, Depth) &&
+        isTruePredicate(CmpInst::ICMP_SLE, BRHS, ARHS, DL, Depth))
+      return true;
+    return std::nullopt;
+
   case CmpInst::ICMP_ULT:
   case CmpInst::ICMP_ULE:
     if (isTruePredicate(CmpInst::ICMP_ULE, BLHS, ALHS, DL, Depth) &&
         isTruePredicate(CmpInst::ICMP_ULE, ARHS, BRHS, DL, Depth))
       return true;
     return std::nullopt;
+
+  case CmpInst::ICMP_UGT:
+  case CmpInst::ICMP_UGE:
+    if (isTruePredicate(CmpInst::ICMP_ULE, ALHS, BLHS, DL, Depth) &&
+        isTruePredicate(CmpInst::ICMP_ULE, BRHS, ARHS, DL, Depth))
+      return true;
+    return std::nullopt;
   }
 }
 
 /// Return true if the operands of two compares (expanded as "L0 pred L1" and
 /// "R0 pred R1") match. IsSwappedOps is true when the operands match, but are
 /// swapped.
 static bool areMatchingOperands(const Value *L0, const Value *L1, const Value *R0,
                            const Value *R1, bool &AreSwappedOps) {

llvm/test/Transforms/InstSimplify/implies.ll

   %var30 = icmp ult i32 %iplus1, %length.i
   %res = icmp sle i1 %var29, %var30
   ret i1 %res
 }
 
 ; X +_{nsw} 1 <(s) Y ==> X <(s) Y
 define i1 @test_sgt_icmp(i32 %length.i, i32 %i) {
 ; CHECK-LABEL: @test_sgt_icmp(
-; CHECK-NEXT:    [[IPLUS1:%.*]] = add nsw i32 [[I:%.*]], 1
-; CHECK-NEXT:    [[VAR29:%.*]] = icmp sgt i32 [[LENGTH_I:%.*]], [[I]]
-; CHECK-NEXT:    [[VAR30:%.*]] = icmp sgt i32 [[LENGTH_I]], [[IPLUS1]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[VAR30]], [[VAR29]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %iplus1 = add nsw i32 %i, 1
   %var29 = icmp sgt i32 %length.i, %i
   %var30 = icmp sgt i32 %length.i, %iplus1
   %res = icmp ule i1 %var30, %var29
   ret i1 %res
 }
 
 ; X +_{nsw} 1 <=(s) Y ==> X <=(s) Y
 define i1 @test_sge_icmp(i32 %length.i, i32 %i) {
 ; CHECK-LABEL: @test_sge_icmp(
-; CHECK-NEXT:    [[IPLUS1:%.*]] = add nsw i32 [[I:%.*]], 1
-; CHECK-NEXT:    [[VAR29:%.*]] = icmp sge i32 [[LENGTH_I:%.*]], [[I]]
-; CHECK-NEXT:    [[VAR30:%.*]] = icmp sge i32 [[LENGTH_I]], [[IPLUS1]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[VAR30]], [[VAR29]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %iplus1 = add nsw i32 %i, 1
   %var29 = icmp sge i32 %length.i, %i
   %var30 = icmp sge i32 %length.i, %iplus1
   %res = icmp ule i1 %var30, %var29
   ret i1 %res
 }
 
 ; X +_{nuw} 1 <(u) Y ==> X <(u) Y
 define i1 @test_ugt_icmp(i32 %length.i, i32 %i) {
 ; CHECK-LABEL: @test_ugt_icmp(
-; CHECK-NEXT:    [[IPLUS1:%.*]] = add nuw i32 [[I:%.*]], 1
-; CHECK-NEXT:    [[VAR29:%.*]] = icmp ugt i32 [[LENGTH_I:%.*]], [[I]]
-; CHECK-NEXT:    [[VAR30:%.*]] = icmp ugt i32 [[LENGTH_I]], [[IPLUS1]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[VAR30]], [[VAR29]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %iplus1 = add nuw i32 %i, 1
   %var29 = icmp ugt i32 %length.i, %i
   %var30 = icmp ugt i32 %length.i, %iplus1
   %res = icmp ule i1 %var30, %var29
   ret i1 %res
 }
 
 ; X +_{nuw} 1 <=(u) Y ==> X <=(u) Y
 define i1 @test_uge_icmp(i32 %length.i, i32 %i) {
 ; CHECK-LABEL: @test_uge_icmp(
-; CHECK-NEXT:    [[IPLUS1:%.*]] = add nuw i32 [[I:%.*]], 1
-; CHECK-NEXT:    [[VAR29:%.*]] = icmp uge i32 [[LENGTH_I:%.*]], [[I]]
-; CHECK-NEXT:    [[VAR30:%.*]] = icmp uge i32 [[LENGTH_I]], [[IPLUS1]]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ule i1 [[VAR30]], [[VAR29]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 true
 ;
   %iplus1 = add nuw i32 %i, 1
   %var29 = icmp uge i32 %length.i, %i
   %var30 = icmp uge i32 %length.i, %iplus1
   %res = icmp ule i1 %var30, %var29
   ret i1 %res
 }