[InstCombine] icmp(X | OrC, C) --> icmp(X, 0)

[junaire]

Summary

We can eliminate the or operation based on the predicate and the
relation between OrC and C.

sge: X | OrC s>= C --> X s>= 0 iff OrC s>= C s>= 0
sgt: X | OrC s> C --> X s>= 0 iff OrC s> C s>= 0
sle: X | OrC s<= C --> X s< 0 iff OrC s> C s>= 0
slt: X | OrC s< C --> X s< 0 iff OrC s>= C s>= 0

Alive2 links:
sge: https://alive2.llvm.org/ce/z/W-6FHE
sgt: https://alive2.llvm.org/ce/z/TKK2yJ
sle: https://alive2.llvm.org/ce/z/vURQGM
slt: https://alive2.llvm.org/ce/z/JAsVfw

Related issue: https://github.com/llvm/llvm-project/issues/61538

Signed-off-by: Jun Zhang <[e-mail]>

[junaire]

Dummy update

[junaire]

Update

[junaire]

Simplify

[junaire]

WIP

[junaire]

Rework

[junaire]

LHS s> RHS

[junaire]

Update with vector tests

[goldstein.w.n]

I think the title should be: 'icmp(bin(X, Y) | Positive)' (seems to be or, not add).

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1350

I don't think this matches the alive2 link you have. You only verify for RHS == 0, but here you seem to take any positive value.

Can you update the alive2 link (or the code). Also the alive2 link seems to have spurious nsw flags on the mul. Verifies w.o the nsw flags so nbd.

llvm/test/Transforms/InstCombine/icmp.ll

4637

Remove?

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1354

Can this just be return new ICmpInst(Pred, X, ConstantInt::getNullValue(X->getType())?

[junaire]

Move code to foldICmporConstant

[junaire]

Update tests

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1959

I think the BinOp aspect of the transform is meaningless:
https://alive2.llvm.org/ce/z/cbWvv7

Also you're alive2 links still don't match the logic (you are only do C == 0).
You can create the constraints you need with @llvm.assume(i1)
I tried to implement here: https://alive2.llvm.org/ce/z/rmBJXx
but it doesn't verify.

[junaire]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1959

I agree we should remove the binop match, but the alive2 link you provided is not what the patch trying to transform. It should be https://alive2.llvm.org/ce/z/ybKpxy (in tgt we compare with 0, not RHS)

[junaire]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1959

Sorry, I think the binop match is necessary?

[junaire]

Hi @goldstein.w.n, please discard all my previous comments (sorry Phab doesn't allow me to delete inline comments :(

So I agree with you with m_BinOp is unnecessary and the transform is correct. Please take a look at https://alive2.llvm.org/ce/z/97gSUu
In fact, I guess we can add more generalized patterns based on the relation between LHS and RHS?

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1959

That wouldn't make sense, the binop includes things like or %x, 0 which is just %x.

It verifies for:
sge: https://alive2.llvm.org/ce/z/w35F7q
but not for
sle: https://alive2.llvm.org/ce/z/2ocRSw

[goldstein.w.n]

In D147597#4251580, @junaire wrote:

Hi @goldstein.w.n, please discard all my previous comments (sorry Phab doesn't allow me to delete inline comments :(

So I agree with you with m_BinOp is unnecessary and the transform is correct. Please take a look at https://alive2.llvm.org/ce/z/97gSUu
In fact, I guess we can add more generalized patterns based on the relation between LHS and RHS?

Ah, so sle -> slt. I missed that.

Since this is a bit complicated can you do two things.

1. make alive2 links for all cases (sgt, slt, sge, sle)
2. Comment in the code the exact transformations that are taking place (in the switch would make sense).

[junaire]

Add some comments

[junaire]

Fix tiny nit

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1961

' X | RHS s<= C --> X s< C'
->
' X | RHS s<= C --> X s< 0'

[junaire]

Fix comments

[junaire]

Add more tests

[junaire]

I screw it up with arc, again :(

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1959

nit: Can you make it:

if (C.isNonNegative() && match(Or, m_c_Or(m_Value(X), m_APInt(LHS))))

Otherwise LGTM.

[goldstein.w.n]

LGTM.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1958

nit: Your comments below use RHS but the variable is LHS. Can one of those be changed for consistencies sake?

1959

nit: Can you make it:

if (C.isNonNegative() && match(Or, m_c_Or(m_Value(X), m_APInt(LHS))))

Otherwise LGTM.

A few other nits as well.

1984

The sge/slt and the sgt/sle cases are indentical. Can you merge them i.e:

// X | RHS s<= C --> X s< 0 iff LHS s> C s>= 0
case ICmpInst::ICMP_SLE:
// X | RHS s> C --> X s>= 0 iff LHS s> C s>= 0
case ICmpInst::ICMP_SGT:
  if (LHS->sgt(C))
    return new ICmpInst(Pred, X,
                        ConstantInt::getNullValue(X->getType()));
  break;
// X | RHS s< C --> X s< 0 iff LHS s>= C s>= 0
case ICmpInst::ICMP_SLT:
// X | RHS s>= C --> X s>= 0 iff LHS s>= C s>= 0
case ICmpInst::ICMP_SGE:
  if (LHS->sge(C))
    return new ICmpInst(Pred, X,
                        ConstantInt::getNullValue(X->getType()));
  break;

[goldstein.w.n]

Can you only use LHS and C in comments/code/summary. You use RHS to both reference LHS and C variable.

[junaire]

Address comments, thx.

[junaire]

use ICmpInst::getFlippedStrictnessPredicate

[goldstein.w.n]

llvm/test/Transforms/InstCombine/icmp.ll

4634

Can you add negative tests where 1) C is negative. and 2) where C >= LHS.

[junaire]

llvm/test/Transforms/InstCombine/icmp.ll

4634

Hi, I've added negative tests in D147597, do you have more comments? :)

[junaire]

llvm/test/Transforms/InstCombine/icmp.ll

4634

Oops, I mean D147596

[junaire]

Rebase

[junaire]

Rebase

[goldstein.w.n]

LGTM.

I'm not a maintainer so please wait a day or so before pushing
to give others a chance to look this over.

[bcl5980]

Maybe we need two more tests here:

1. Not one-use test .
2. Vector test with poison constant.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1958

Do we really need c_or here? APInt should be always second operator.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1957

Why is a constant that occurs on the RHS called LHS?

llvm/test/Transforms/InstCombine/icmp.ll

4633–4634

What's the purpose of the mul instruction in all these tests? It doesn't seem related?

[junaire]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1957

Naming is hard. C here should really be the RHS but in foldICmpOrConstant it's called C so it's kinda confusing. Maybe rename it to RHS?

1958

Thanks, I'm uncertain if it's already been canonicalized when I first wrote this, will drop it.

llvm/test/Transforms/InstCombine/icmp.ll

4633–4634

Sorry, the patch has changed several times so I forgot to update the tests.

[junaire]

Add m_OneUse & m_c_Or -> m_Or

[junaire]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1957

I'm still unsure about what should I call it, can you suggest one?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1957

C2, OrC, MaskC would all work.

[junaire]

Rebase

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1958

I don't think this one-use check is necessary, as we're only creating one insturction. I believe @bcl5980's point was just to add a multi-use test, not that it needs to be restricted to one-use.

[junaire]

Address @nikic's comments, thx.

[junaire]

Remove oneuse check

[junaire]

Rebase

[junaire]

Do you have more comments to address? or can I land it? @nikic

[bcl5980]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1958

Yeah, what I mean is only add a test for multi-use case. We needn't restrict one-use here.

[nikic]

llvm/test/Transforms/InstCombine/icmp.ll

4779

Not a negative test.

[junaire]

Thanks everyone!

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombinerImpl::foldICmpWithConstant(ICmpInst &Cmp) {
   Constant *C = dyn_cast<Constant>(Op1);
   if (!C)
     return nullptr;
 
   if (auto *Phi = dyn_cast<PHINode>(Op0))
     if (all_of(Phi->operands(), [](Value *V) { return isa<Constant>(V); })) {
       Type *Ty = Cmp.getType();
       Builder.SetInsertPoint(Phi);
       PHINode *NewPhi =
           Builder.CreatePHI(Ty, Phi->getNumOperands());
       for (BasicBlock *Predecessor : predecessors(Phi->getParent())) {
         auto *Input =
             cast<Constant>(Phi->getIncomingValueForBlock(Predecessor));
         auto *BoolInput = ConstantExpr::getCompare(Pred, Input, C);
         NewPhi->addIncoming(BoolInput, Predecessor);
       }
       NewPhi->takeName(&Cmp);
       return replaceInstUsesWith(Cmp, NewPhi);
     }
 
   return nullptr;
Instruction *InstCombinerImpl::foldICmpOrConstant(ICmpInst &Cmp,
   bool TrueIfSigned;
   if (isSignBitCheck(Pred, C, TrueIfSigned) &&
       match(Or, m_c_Or(m_Add(m_Value(X), m_AllOnes()), m_Deferred(X)))) {
     auto NewPred = TrueIfSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_SGT;
     Constant *NewC = ConstantInt::get(X->getType(), TrueIfSigned ? 1 : 0);
     return new ICmpInst(NewPred, X, NewC);
   }
 
+  const APInt *LHS;
+  // icmp(X | LHS, C) --> icmp(X, 0)
+  if (match(Or, m_c_Or(m_Value(X), m_APInt(LHS)))) {
+    if (C.isNonNegative()) {
+      switch (Pred) {
+      // X | RHS s<= C --> X s< 0 iff LHS s> C s>= 0
+      case ICmpInst::ICMP_SLE:
+        if (LHS->sgt(C))
+          return new ICmpInst(ICmpInst::ICMP_SLT, X,
+                              ConstantInt::getNullValue(X->getType()));
+        break;
+      // X | RHS s< C --> X s< 0 iff LHS s>= C s>= 0
+      case ICmpInst::ICMP_SLT:
+        if (LHS->sge(C))
+          return new ICmpInst(ICmpInst::ICMP_SLT, X,
+                              ConstantInt::getNullValue(X->getType()));
+        break;
+      // X | RHS s>= C --> X s>= 0 iff LHS s>= C s>= 0
+      case ICmpInst::ICMP_SGE:
+        if (LHS->sge(C))
+          return new ICmpInst(ICmpInst::ICMP_SGE, X,
+                              ConstantInt::getNullValue(X->getType()));
+        break;
+      // X | RHS s> C --> X s>= 0 iff LHS s> C s>= 0
+      case ICmpInst::ICMP_SGT:
+        if (LHS->sgt(C))
+          return new ICmpInst(ICmpInst::ICMP_SGE, X,
+                              ConstantInt::getNullValue(X->getType()));
+        break;
+      default:
+        break;
+      }
+    }
+  }
+
   if (!Cmp.isEquality() || !C.isZero() || !Or->hasOneUse())
     return nullptr;
 
   Value *P, *Q;
   if (match(Or, m_Or(m_PtrToInt(m_Value(P)), m_PtrToInt(m_Value(Q))))) {
     // Simplify icmp eq (or (ptrtoint P), (ptrtoint Q)), 0
     // -> and (icmp eq P, null), (icmp eq Q, null).
     Value *CmpP =

llvm/test/Transforms/InstCombine/icmp.ll

;
   %zx = zext i2 %x to i8
   %a = and i8 %zx, %y
   %r = icmp ne i8 %a, 0
   ret i1 %r
 }
 
 define i1 @mul_or_positive_sgt_zero(i8 %a, i8 %b) {
 ; CHECK-LABEL: @mul_or_positive_sgt_zero(
 ; CHECK-NEXT:    [[MUL1:%.*]] = mul i8 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[MUL1]], 24
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[ADD]], 0
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[MUL1]], -1
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %mul1 = mul i8 %a, %b
   %add = or i8 %mul1, 24
   %cmp = icmp sgt i8 %add, 0
   ret i1 %cmp
 }
 
 define <2 x i1> @mul_or_postive_sgt_zero_vec(<2 x i8> %a, <2 x i8> %b) {
 ; CHECK-LABEL: @mul_or_postive_sgt_zero_vec(
 ; CHECK-NEXT:    [[MUL1:%.*]] = mul <2 x i8> [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = or <2 x i8> [[MUL1]], <i8 24, i8 24>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <2 x i8> [[ADD]], zeroinitializer
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <2 x i8> [[MUL1]], <i8 -1, i8 -1>
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
 
   %mul1 = mul <2 x i8> %a, %b
   %add = or <2 x i8> %mul1, <i8 24, i8 24>
   %cmp = icmp sgt <2 x i8> %add, <i8 0, i8 0>
   ret <2 x i1> %cmp
 }
;
   %add = or <2 x i8> %mul1, <i8 24, i8 24>
   %cmp = icmp sge <2 x i8> %add, <i8 0, i8 0>
   ret <2 x i1> %cmp
 }
 
 define i1 @mul_or_positive_sge_postive(i8 %a, i8 %b) {
 ; CHECK-LABEL: @mul_or_positive_sge_postive(
 ; CHECK-NEXT:    [[MUL1:%.*]] = mul i8 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[MUL1]], 24
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[ADD]], 23
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[MUL1]], -1
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %mul1 = mul i8 %a, %b
   %add = or i8 %mul1, 24
   %cmp = icmp sge i8 %add, 24
   ret i1 %cmp
 }
 
 define <2 x i1> @mul_or_postive_sge_positive_vec(<2 x i8> %a, <2 x i8> %b) {
 ; CHECK-LABEL: @mul_or_postive_sge_positive_vec(
 ; CHECK-NEXT:    [[MUL1:%.*]] = mul <2 x i8> [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = or <2 x i8> [[MUL1]], <i8 24, i8 24>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <2 x i8> [[ADD]], <i8 23, i8 23>
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <2 x i8> [[MUL1]], <i8 -1, i8 -1>
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
 
   %mul1 = mul <2 x i8> %a, %b
   %add = or <2 x i8> %mul1, <i8 24, i8 24>
   %cmp = icmp sge <2 x i8> %add, <i8 24, i8 24>
   ret <2 x i1> %cmp
 }
 
 define i1 @mul_or_positive_sle_zero(i8 %a, i8 %b) {
 ; CHECK-LABEL: @mul_or_positive_sle_zero(
 ; CHECK-NEXT:    [[MUL1:%.*]] = mul i8 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[MUL1]], 24
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[ADD]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[MUL1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %mul1 = mul i8 %a, %b
   %add = or i8 %mul1, 24
   %cmp = icmp sle i8 %add, 0
   ret i1 %cmp
 }
 
 define <2 x i1> @mul_or_postive_sle_zero_vec(<2 x i8> %a, <2 x i8> %b) {
 ; CHECK-LABEL: @mul_or_postive_sle_zero_vec(
 ; CHECK-NEXT:    [[MUL1:%.*]] = mul <2 x i8> [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = or <2 x i8> [[MUL1]], <i8 24, i8 24>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <2 x i8> [[ADD]], <i8 1, i8 1>
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <2 x i8> [[MUL1]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
 
   %mul1 = mul <2 x i8> %a, %b
   %add = or <2 x i8> %mul1, <i8 24, i8 24>
   %cmp = icmp sle <2 x i8> %add, <i8 0, i8 0>
   ret <2 x i1> %cmp
 }
;
   %add = or <2 x i8> %mul1, <i8 24, i8 24>
   %cmp = icmp slt <2 x i8> %add, <i8 0, i8 0>
   ret <2 x i1> %cmp
 }
 
 define i1 @mul_or_positive_slt_postive(i8 %a, i8 %b) {
 ; CHECK-LABEL: @mul_or_positive_slt_postive(
 ; CHECK-NEXT:    [[MUL1:%.*]] = mul i8 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[MUL1]], 24
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[ADD]], 24
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[MUL1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %mul1 = mul i8 %a, %b
   %add = or i8 %mul1, 24
   %cmp = icmp slt i8 %add, 24
   ret i1 %cmp
 }
 
 define <2 x i1> @mul_or_postive_slt_positive_vec(<2 x i8> %a, <2 x i8> %b) {
 ; CHECK-LABEL: @mul_or_postive_slt_positive_vec(
 ; CHECK-NEXT:    [[MUL1:%.*]] = mul <2 x i8> [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[ADD:%.*]] = or <2 x i8> [[MUL1]], <i8 24, i8 24>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <2 x i8> [[ADD]], <i8 24, i8 24>
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <2 x i8> [[MUL1]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
 
   %mul1 = mul <2 x i8> %a, %b
   %add = or <2 x i8> %mul1, <i8 24, i8 24>
   %cmp = icmp slt <2 x i8> %add, <i8 24, i8 24>
   ret <2 x i1> %cmp
 }