[InstCombine] Teach foldOrOfICmps to allow icmp eq MIN_INT/MAX to be part of a range comparision. Similar for foldAndOfICmps

[craig.topper]

Summary

We can treat icmp eq X, MIN_UINT as icmp ule X, MIN_UINT and allow
it to merge with icmp ugt X, C. Similar for the other constants.

We can do simliar for icmp ne X, (U)INT_MIN/MAX in foldAndOfICmps. And we already handled UINT_MIN there.

Fixes PR42691.

[craig.topper]

Rebase with the tests pre-commited

[craig.topper]

Rebase after making one of the tests better

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2262

ULE -> SLE

llvm/test/Transforms/InstCombine/and-or-icmps.ll

257

This seems like a weird choice that the range check code is making. We could also generate

%x.off = add i32 %x, 1
%c = icmp ult i32 %x.off, -2147483646

with smaller constants.

[craig.topper]

Fix copy/paste mistake in comment

[craig.topper]

Also update foldAndOfICmps to handle not equal (U)INT_MIN/MAX

[craig.topper]

llvm/test/Transforms/InstCombine/and-or-icmps.ll

257

Is this something this patch should address?

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1208–1209

Ok, https://rise4fun.com/Alive/VUp
Comment does not specify the precondition that C != INT_MIN
I'm guessing that case is handled elsewhere?

1221–1224

Update comment please: X u> 13 & X != UINT_MAX -> (X-(C+1)) u< UINT_MAX-(C+1)
https://rise4fun.com/Alive/qt2, ok
Comment does not specify the precondition that C != UINT_MAX
I'm guessing that case is handled elsewhere?

1234–1237

Fix comment please: X s> 13 & X != INT_MAX -> (X-(C+1))) u< INT_MAX-(C+1)
https://rise4fun.com/Alive/hZlO, ok
Comment does not specify the precondition that C != INT_MAX
I'm guessing that case is handled elsewhere?

2255–2295

Can you please add actual formulas here as comments?

llvm/test/Transforms/InstCombine/and-or-icmps.ll

257

Is this something this patch should address?

I'm going to go with no. That is a separate fold.

[craig.topper]

Clean up comments in the new code. And a few minor fixes to the comments in the existing code. Probably should rewrite them to use C instead of specific numbers, but for now I just fixed them to not be completely incorrect about what insertRangeTest does.

[craig.topper]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1221–1224

There's an earlier assert above this switch that says LHSC != RHSC which would ensure C can't be UINT_MAX.

[lebedev.ri]

Ok, LGTM, thank you.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2255–2258

https://rise4fun.com/Alive/3RLT ok

2262–2265

https://rise4fun.com/Alive/1ri ok

2275–2278

https://rise4fun.com/Alive/zq4 ok

2290–2296

https://rise4fun.com/Alive/xb2 ok

llvm/test/Transforms/InstCombine/and-or-icmps.ll

257

This might warrant filing an issue to track though.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

case ICmpInst::ICMP_ULT:
         return Builder.CreateICmpULT(LHS0, LHSC);
       if (LHSC->isZero()) // (X !=  0 & X u< 14) -> X-1 u< 13
         return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
                                false, true);
       break; // (X != 13 & X u< 15) -> no change
     case ICmpInst::ICMP_SLT:
       if (LHSC == SubOne(RHSC)) // (X != 13 & X s< 14) -> X < 13
         return Builder.CreateICmpSLT(LHS0, LHSC);
       break;                 // (X != 13 & X s< 15) -> no change
     case ICmpInst::ICMP_NE:
       // Potential folds for this case should already be handled.
       break;
     }
     break;
   case ICmpInst::ICMP_UGT:
     switch (PredR) {
     default:
       llvm_unreachable("Unknown integer condition code!");
     case ICmpInst::ICMP_NE:
       if (RHSC == AddOne(LHSC)) // (X u> 13 & X != 14) -> X u> 14
         return Builder.CreateICmp(PredL, LHS0, RHSC);
       break;                 // (X u> 13 & X != 15) -> no change
     case ICmpInst::ICMP_ULT: // (X u> 13 & X u< 15) -> (X-14) <u 1
       return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(),
                              false, true);
     }
     break;
   case ICmpInst::ICMP_SGT:
     switch (PredR) {
     default:
       llvm_unreachable("Unknown integer condition code!");
     case ICmpInst::ICMP_NE:
       if (RHSC == AddOne(LHSC)) // (X s> 13 & X != 14) -> X s> 14
         return Builder.CreateICmp(PredL, LHS0, RHSC);
       break;                 // (X s> 13 & X != 15) -> no change
     case ICmpInst::ICMP_SLT: // (X s> 13 & X s< 15) -> (X-14) s< 1
       return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue(), true,
                              true);
     }
     break;
   }
 
   return nullptr;
 }
 
 Value *InstCombiner::foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd) {
default:
     llvm_unreachable("Unknown integer condition code!");
   case ICmpInst::ICMP_EQ:
     switch (PredR) {
     default:
       llvm_unreachable("Unknown integer condition code!");
     case ICmpInst::ICMP_EQ:
       // Potential folds for this case should already be handled.
       break;
-    case ICmpInst::ICMP_UGT: // (X == 13 | X u> 14) -> no change
-    case ICmpInst::ICMP_SGT: // (X == 13 | X s> 14) -> no change
+    case ICmpInst::ICMP_UGT:
+      // We can treat equality of MIN_UINT as being ULE MIN_UINT.
+      if (LHSC->isMinValue(false))
+        return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue() + 1,
+                               false, false);
+      // (X == 13 | X u> 14) -> no change
+      break;
+    case ICmpInst::ICMP_SGT:
+      // We can treat equality of MIN_SINT as being ULE MIN_SINT.
+      if (LHSC->isMinValue(true))
+        return insertRangeTest(LHS0, LHSC->getValue() + 1, RHSC->getValue() + 1,
+                               true, false);
+      // (X == 13 | X s> 14) -> no change
       break;
     }
     break;
   case ICmpInst::ICMP_ULT:
     switch (PredR) {
     default:
       llvm_unreachable("Unknown integer condition code!");
     case ICmpInst::ICMP_EQ: // (X u< 13 | X == 14) -> no change
+      // We can treat equality of MAX_UINT as being UGE MAX_UINT.
+      if (RHSC->isMaxValue(false))
+        return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue(),
+                               false, false);
       break;
     case ICmpInst::ICMP_UGT: // (X u< 13 | X u> 15) -> (X-13) u> 2
       assert(!RHSC->isMaxValue(false) && "Missed icmp simplification");
       return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1,
                              false, false);
     }
     break;
   case ICmpInst::ICMP_SLT:
     switch (PredR) {
     default:
       llvm_unreachable("Unknown integer condition code!");
-    case ICmpInst::ICMP_EQ: // (X s< 13 | X == 14) -> no change
+    case ICmpInst::ICMP_EQ:
+      // We can treat equality of MAX_SINT as being SGE MAX_SINT.
+      if (RHSC->isMaxValue(true))
+        return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue(),
+                               true, false);
+      // (X s< 13 | X == 14) -> no change
       break;
     case ICmpInst::ICMP_SGT: // (X s< 13 | X s> 15) -> (X-13) s> 2
       assert(!RHSC->isMaxValue(true) && "Missed icmp simplification");
       return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1, true,
                              false);
     }
     break;
   }
   return nullptr;

llvm/test/Transforms/InstCombine/and-or-icmps.ll

;
   %C18 = icmp ule i1 %C10, %C7
   %G26 = getelementptr i1, i1* null, i1 %C3
   store i16 %B33, i16* undef
   store i1 %C18, i1* undef
   store i1* %G26, i1** undef
   ret void
 }
 
+define i1 @PR42691_1(i32 %x) {
+; CHECK-LABEL: @PR42691_1(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 %x, 2147483646
+; CHECK-NEXT:    ret i1 [[TMP1]]
+;
+  %c1 = icmp slt i32 %x, 0
+  %c2 = icmp eq i32 %x, 2147483647
+  %c = or i1 %c1, %c2
+  ret i1 %c
+}
+
+define i1 @PR42691_2(i32 %x) {
+; CHECK-LABEL: @PR42691_2(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 %x, -2
+; CHECK-NEXT:    ret i1 [[TMP1]]
+;
+  %c1 = icmp ult i32 %x, 2147483648
+  %c2 = icmp eq i32 %x, 4294967295
+  %c = or i1 %c1, %c2
+  ret i1 %c
+}
+
+define i1 @PR42691_3(i32 %x) {
+; CHECK-LABEL: @PR42691_3(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 %x, -2147483647
+; CHECK-NEXT:    ret i1 [[TMP1]]
+;
+  %c1 = icmp sge i32 %x, 0
+  %c2 = icmp eq i32 %x, -2147483648
+  %c = or i1 %c1, %c2
+  ret i1 %c
+}
+
+define i1 @PR42691_4(i32 %x) {
+; CHECK-LABEL: @PR42691_4(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 %x, 1
+; CHECK-NEXT:    ret i1 [[TMP1]]
+;
+  %c1 = icmp uge i32 %x, 2147483648
+  %c2 = icmp eq i32 %x, 0
+  %c = or i1 %c1, %c2
+  ret i1 %c
+}
+
+define i1 @PR42691_5(i32 %x) {
+; CHECK-LABEL: @PR42691_5(
+; CHECK-NEXT:    [[X_OFF:%.*]] = add i32 %x, -1
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[X_OFF]], 2147483645
+; CHECK-NEXT:    ret i1 [[TMP1]]
+;
+  %c1 = icmp slt i32 %x, 1
+  %c2 = icmp eq i32 %x, 2147483647
+  %c = or i1 %c1, %c2
+  ret i1 %c
+}
+
+define i1 @PR42691_6(i32 %x) {
+; CHECK-LABEL: @PR42691_6(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 %x, -2
+; CHECK-NEXT:    ret i1 [[TMP1]]
+;
+  %c1 = icmp ult i32 %x, 2147483648
+  %c2 = icmp eq i32 %x, 4294967295
+  %c = or i1 %c1, %c2
+  ret i1 %c
+}
+
+define i1 @PR42691_7(i32 %x) {
+; CHECK-LABEL: @PR42691_7(
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 %x, -1
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i32 [[TMP1]], 0
+; CHECK-NEXT:    ret i1 [[TMP2]]
+;
+  %c1 = icmp uge i32 %x, 2147483649
+  %c2 = icmp eq i32 %x, 0
+  %c = or i1 %c1, %c2
+  ret i1 %c
+}