[InstCombine] Add transforms for `(icmp spred (or X, Y), X)`

[goldstein.w.n]

Summary

If we know the sign of Y or the value of Y we can either evaluate or
simplify the condition.

icmp (X | MinInt) s> X --> false

• https://alive2.llvm.org/ce/z/mpd-Yj

icmp (X | MinInt) s<= X --> true

• https://alive2.llvm.org/ce/z/E4aynv

icmp (X | MinInt) s>= X --> X s< 0

• https://alive2.llvm.org/ce/z/ThZkSV

icmp (X | MinInt) s< X --> X s>= 0

• https://alive2.llvm.org/ce/z/sNx2VB

icmp (X | Pos_Y) s> X --> (X | Pos_Y) != X

• https://alive2.llvm.org/ce/z/n-XM6N

icmp (X | Pos_Y) s<= X --> (X | Pos_Y) == X

• https://alive2.llvm.org/ce/z/1FQZM-

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4137

Maybe move this into the if() to reduce scope

if (auto KnownSign = getKnownSign(A, &I, Q.DL, Q.AC, Q.DT))

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

getKnownSign(Value *Op, Instruction *CxtI, const DataLayout &DL,
   Value *X, *Y;
   if (match(Op, m_NSWSub(m_Value(X), m_Value(Y))))
     return isImpliedByDomCondition(ICmpInst::ICMP_SLT, X, Y, CxtI, DL);
 
   return isImpliedByDomCondition(
       ICmpInst::ICMP_SLT, Op, Constant::getNullValue(Op->getType()), CxtI, DL);
 }
 
+static std::optional<bool> getKnownSign(Value *Op, Instruction *CxtI,
+                                        const DataLayout &DL,
+                                        AssumptionCache *AC,
+                                        const DominatorTree *DT) {
+  KnownBits Known;
+  return getKnownSign(Op, CxtI, DL, AC, DT, Known);
+}
+
 static Instruction *foldICmpOrXX(ICmpInst &I, const SimplifyQuery &Q,
                                  InstCombinerImpl &IC) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1), *A;
   bool Op0IsOr = false;
   if (match(Op0, m_c_Or(m_Specific(Op1), m_Value(A))))
     Op0IsOr = true;
   else if (!match(Op1, m_c_Or(m_Specific(Op0), m_Value(A))))
     return nullptr;
 
   Value *OrOp = Op0IsOr ? Op0 : Op1;
   Value *X = Op0IsOr ? Op1 : Op0;
   const CmpInst::Predicate Pred = I.getPredicate();
 
   // icmp (X | Y) u<= X --> (X | Y) == X
   if (Op0IsOr ? Pred == ICmpInst::ICMP_ULE : Pred == ICmpInst::ICMP_UGE)
     return new ICmpInst(ICmpInst::ICMP_EQ, Op0, Op1);
 
   // icmp (X | Y) u> X --> (X | Y) != X
   else if (Op0IsOr ? Pred == ICmpInst::ICMP_UGT : Pred == ICmpInst::ICMP_ULT)
     return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
 
   // icmp (X | noundef Y) eq/ne X
   //    if (X | noundef Y).hasOneUse()
   //        --> (X & noundef Y) eq/ne noundef Y
   if (ICmpInst::isEquality(Pred) && OrOp->hasOneUse() &&
       isGuaranteedNotToBeUndefOrPoison(A, Q.AC, Q.CxtI, Q.DT,
                                        /*Depth*/ 0))
     return new ICmpInst(Pred, IC.Builder.CreateAnd(X, A), A);
 
+  if (ICmpInst::isEquality(Pred) || ICmpInst::getSignedPredicate(Pred) != Pred)
+    return nullptr;
+
+  auto KnownSign = getKnownSign(A, &I, Q.DL, Q.AC, Q.DT);
+  if (KnownSign != std::nullopt) {
+    // icmp (X | MinInt) s> X --> false
+    // icmp (X | MinInt) s<= X --> true
+    // icmp (X | MinInt) s>= X --> X s< 0
+    // icmp (X | MinInt) s< X --> X s>= 0
+    if (*KnownSign /* true is Signed. */ &&
+        IC.isKnownToBeAPowerOfTwo(A, /*OrZero*/ true, 0, &I)) {
+      if (Op0IsOr && (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLE))
+        return IC.replaceInstUsesWith(
+            I, ConstantInt::get(I.getType(), Pred == ICmpInst::ICMP_SLE));
+      else if (!Op0IsOr &&
+               (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE))
+        return IC.replaceInstUsesWith(
+            I, ConstantInt::get(I.getType(), Pred == ICmpInst::ICMP_SGE));
+      else if (Op0IsOr ? Pred == ICmpInst::ICMP_SGE
+                       : Pred == ICmpInst::ICMP_SLE)
+        return new ICmpInst(ICmpInst::ICMP_SLT, X,
+                            Constant::getNullValue(Op0->getType()));
+      else
+        return new ICmpInst(ICmpInst::ICMP_SGE, X,
+                            Constant::getNullValue(Op0->getType()));
+    }
+    // icmp (X | Pos_Y) s> X --> (X | Pos_Y) != X
+    // icmp (X | Pos_Y) s<= X --> (X | Pos_Y) == X
+    else if (!*KnownSign) {
+      if (Op0IsOr ? Pred == ICmpInst::ICMP_SGT : Pred == ICmpInst::ICMP_SLT)
+        return new ICmpInst(ICmpInst::ICMP_NE, Op0, Op1);
+      else if (Op0IsOr ? Pred == ICmpInst::ICMP_SLE
+                       : Pred == ICmpInst::ICMP_SGE)
+        return new ICmpInst(ICmpInst::ICMP_EQ, Op0, Op1);
+    }
+  }
+
   return nullptr;
 }
 
 static Instruction *foldICmpXorXX(ICmpInst &I, const SimplifyQuery &Q,
                                   InstCombinerImpl &IC) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1), *A;
   bool Op0IsXor = false;
   if (match(Op0, m_c_Xor(m_Specific(Op1), m_Value(A))))

llvm/test/Transforms/InstCombine/icmp-of-or-x.ll

;
   ret <2 x i1> %r
 }
 
 define <2 x i1> @or_slt_pos(<2 x i8> %xx, <2 x i8> %yy, <2 x i8> %z) {
 ; CHECK-LABEL: @or_slt_pos(
 ; CHECK-NEXT:    [[X:%.*]] = add <2 x i8> [[XX:%.*]], [[Z:%.*]]
 ; CHECK-NEXT:    [[Y:%.*]] = and <2 x i8> [[YY:%.*]], <i8 127, i8 127>
 ; CHECK-NEXT:    [[XN1:%.*]] = or <2 x i8> [[X]], [[Y]]
-; CHECK-NEXT:    [[R:%.*]] = icmp slt <2 x i8> [[X]], [[XN1]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ne <2 x i8> [[X]], [[XN1]]
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %x = add <2 x i8> %xx, %z
   %y = and <2 x i8> %yy, <i8 127, i8 127>
   %xn1 = or <2 x i8> %x, %y
   %r = icmp slt <2 x i8> %x, %xn1
   ret <2 x i1> %r
 }
 
 define i1 @or_sle_pos(i8 %x, i8 %y) {
 ; CHECK-LABEL: @or_sle_pos(
 ; CHECK-NEXT:    [[NS:%.*]] = icmp sgt i8 [[Y:%.*]], -1
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NS]])
 ; CHECK-NEXT:    [[XN1:%.*]] = or i8 [[X:%.*]], [[Y]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sle i8 [[XN1]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[XN1]], [[X]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %ns = icmp sge i8 %y, 0
   call void @llvm.assume(i1 %ns)
   %xn1 = or i8 %x, %y
   %r = icmp sle i8 %xn1, %x
   ret i1 %r
 }
;
   %xn1 = or <2 x i8> %x, %y
   %r = icmp ne <2 x i8> %xn1, %x
   call void @use.v2i8(<2 x i8> %xn1)
   ret <2 x i1> %r
 }
 
 define i1 @or_slt_intmin(i8 %x) {
 ; CHECK-LABEL: @or_slt_intmin(
-; CHECK-NEXT:    [[XN1:%.*]] = or i8 [[X:%.*]], -128
-; CHECK-NEXT:    [[R:%.*]] = icmp slt i8 [[XN1]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[X:%.*]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %xn1 = or i8 %x, 128
   %r = icmp slt i8 %xn1, %x
   ret i1 %r
 }
 
 define <2 x i1> @or_slt_intmin_2(<2 x i8> %xx, <2 x i8> %z) {
 ; CHECK-LABEL: @or_slt_intmin_2(
-; CHECK-NEXT:    [[X:%.*]] = add <2 x i8> [[XX:%.*]], [[Z:%.*]]
-; CHECK-NEXT:    [[XN1:%.*]] = or <2 x i8> [[X]], <i8 -128, i8 -128>
-; CHECK-NEXT:    [[R:%.*]] = icmp slt <2 x i8> [[X]], [[XN1]]
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %x = add <2 x i8> %xx, %z
   %xn1 = or <2 x i8> %x, <i8 128, i8 128>
   %r = icmp slt <2 x i8> %x, %xn1
   ret <2 x i1> %r
 }
 
 define i1 @or_sle_intmin_indirect_2(i8 %xx, i8 %C, i8 %z) {
neg:
   ret i1 %r
 pos:
   call void @barrier()
   ret i1 0
 }
 
 define i1 @or_sge_intmin(i8 %x) {
 ; CHECK-LABEL: @or_sge_intmin(
-; CHECK-NEXT:    [[XN1:%.*]] = or i8 [[X:%.*]], -128
-; CHECK-NEXT:    [[R:%.*]] = icmp sge i8 [[XN1]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i8 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %xn1 = or i8 %x, 128
   %r = icmp sge i8 %xn1, %x
   ret i1 %r
 }
 
 define i1 @or_sgt_intmin_indirect(i8 %x, i8 %C) {

 pos:
   call void @barrier()
   ret i1 0
 }
 
 define <2 x i1> @or_sgt_intmin_2(<2 x i8> %xx, <2 x i8> %z) {
 ; CHECK-LABEL: @or_sgt_intmin_2(
 ; CHECK-NEXT:    [[X:%.*]] = add <2 x i8> [[XX:%.*]], [[Z:%.*]]
-; CHECK-NEXT:    [[XN1:%.*]] = or <2 x i8> [[X]], <i8 -128, i8 -128>
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt <2 x i8> [[X]], [[XN1]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt <2 x i8> [[X]], <i8 -1, i8 -1>
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %x = add <2 x i8> %xx, %z
   %xn1 = or <2 x i8> %x, <i8 128, i8 128>
   %r = icmp sgt <2 x i8> %x, %xn1
   ret <2 x i1> %r
 }