[InstCombine] (icmp eq A, -1) & (icmp eq B, -1) --> (icmp eq (A&B), -1)

[xgupta]

Summary

This patch add another icmp fold for -1 case.

This fixes https://github.com/llvm/llvm-project/issues/62311,
where we want instcombine to merge all compare intructions together so
later passes like simplifycfg and slpvectorize can better optimize this
chained comparison.

[xgupta]

Add C++ version test case in llvm lit test case.

[xgupta]

corrected diff

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2955

m_ConstantInt<-1>() -> m_AllOnes()

llvm/test/Transforms/InstCombine/pr62311.ll

75 ↗

(On Diff #526474)

This single test isn't really sufficient.

Can you add a few more simple tests covering the following cases:

1. (x == -1 && y == -1)
2. (x != -1) || (y != -1)
3. (x == -1) || (y == -1) -- failure case
4. (x == -1) && (y != -1) -- failure case

maybe a few more failure cases using other constants / mismatched constants.
Something in the style of icmp-add.ll should be fine.

Can you also split the patch with the tests so we can more easily see the diff generated by this patch.

I.e

Patch1: Test Cases
Patch2: Implementation

Then match patch2 the parent of patch1.

[xgupta]

address comment for m_ConstantInt<-1>() -> m_AllOnes()

[hnrklssn]

llvm/test/Transforms/InstCombine/pr62311.ll

75 ↗

(On Diff #526474)

For the success cases, could you also add a second run line to show that this transformation is enough to do the vectorisation asked for in https://github.com/llvm/llvm-project/issues/62311?
Something like:

; RUN: opt < %s -passes=instcombine -S | FileCheck %s
; RUN: opt < %s -passes=instcombine,simplify-cfg,<some-vectoriser-pass> -S | FileCheck --check-prefix INTEGRATED %s

[fhahn]

llvm/test/Transforms/InstCombine/pr62311.ll

75 ↗

(On Diff #526474)

To check the end-to-end result it would probably be better to add a test in PhaseOrdering that just runs -passes='default<O2>' (or something) rather than having the InstCombine tests depend on other passes

[xgupta]

llvm/test/Transforms/InstCombine/pr62311.ll

75 ↗

(On Diff #526474)

Thanks, Updated the test case RUN line here - https://reviews.llvm.org/D151694.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2952

Is there why this patch adds this new functionality and doesn't juist update foldLogOpOfMaskedICmps to handle undefs? Is it alot of work?

2958

ConstantInt::get(LHS0->getType(), -1) -> Constant::getAllOnesValue(LHS0->getType())

[xgupta]

Address comment

[xgupta]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2952

I have not thought about that, I will try to explore that.
I wrote this as similar to a few line above for (icmp eq A, 0) & (icmp eq B, 0) --> (icmp eq (A|B), 0)"

2958

Thanks, updated.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2952

well I'm just wondering what the todo is about.

[xgupta]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2952

OK, seems @nikic added that TODO in https://github.com/llvm/llvm-project/commit/84e273cced851075df46c78362ad3507a4de61d0.

[xgupta]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2952

@nikic shall we keep TODO or remove it or do you have any suggestion how to make foldLogOpOfMaskedICmps handle undefs.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2952

I don't understanding, the TODO is new with your code? If you are just copy pasting the comment please drop it.

[xgupta]

Remove TODO

[xgupta]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2952

Dropped it.

[goldstein.w.n]

We should see diffs in the tests caused by this patch.

[xgupta]

Add updated test case

[xgupta]

Updated test cases

[goldstein.w.n]

LGTM.

Do you need me to push this for you? If so can you please reply with your name/email?

[xgupta]

In D151660#4404597, @goldstein.w.n wrote:

LGTM.

Do you need me to push this for you? If so can you please reply with your name/email?

Thank you for the review. I do have commit access. Will push it.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (Value *X = foldUnsignedUnderflowCheck(RHS, LHS, IsAnd, Q, Builder))
       return X;
   }
 
   if (Value *X = foldEqOfParts(LHS, RHS, IsAnd))
     return X;
 
   // (icmp ne A, 0) | (icmp ne B, 0) --> (icmp ne (A|B), 0)
   // (icmp eq A, 0) & (icmp eq B, 0) --> (icmp eq (A|B), 0)
-  // TODO: Remove this when foldLogOpOfMaskedICmps can handle undefs.
+  // TODO: Remove this and below when foldLogOpOfMaskedICmps can handle undefs.
   if (!IsLogical && PredL == (IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE) &&
       PredL == PredR && match(LHS1, m_ZeroInt()) && match(RHS1, m_ZeroInt()) &&
       LHS0->getType() == RHS0->getType()) {
     Value *NewOr = Builder.CreateOr(LHS0, RHS0);
     return Builder.CreateICmp(PredL, NewOr,
                               Constant::getNullValue(NewOr->getType()));
   }
 
+  // (icmp ne A, -1) | (icmp ne B, -1) --> (icmp ne (A&B), -1)
+  // (icmp eq A, -1) & (icmp eq B, -1) --> (icmp eq (A&B), -1)
+  if (!IsLogical && PredL == (IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE) &&
+      PredL == PredR && match(LHS1, m_AllOnes()) && match(RHS1, m_AllOnes()) &&
+      LHS0->getType() == RHS0->getType()) {
+    Value *NewAnd = Builder.CreateAnd(LHS0, RHS0);
+    return Builder.CreateICmp(PredL, NewAnd,
+                              Constant::getAllOnesValue(LHS0->getType()));
+  }
+
   // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2).
   if (!LHSC || !RHSC)
     return nullptr;
 
   // (trunc x) == C1 & (and x, CA) == C2 -> (and x, CA|CMAX) == C1|C2
   // (trunc x) != C1 | (and x, CA) != C2 -> (and x, CA|CMAX) != C1|C2
   // where CMAX is the all ones value for the truncated type,
   // iff the lower bits of C2 and CA are zero.

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

;
   %o = or i32 %x, %y
   %lt = icmp slt i32 %o, 0
   %r = and i1 %gt, %lt
   ret i1 %r
 }
 
 define <2 x i1> @icmp_eq_m1_and_eq_m1(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @icmp_eq_m1_and_eq_m1(
-; CHECK-NEXT:    [[RX:%.*]] = icmp eq <2 x i8> [[X:%.*]], <i8 -1, i8 undef>
-; CHECK-NEXT:    [[RY:%.*]] = icmp eq <2 x i8> [[Y:%.*]], <i8 -1, i8 undef>
-; CHECK-NEXT:    [[R:%.*]] = and <2 x i1> [[RX]], [[RY]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i8> [[TMP1]], <i8 -1, i8 -1>
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %rx = icmp eq <2 x i8> %x, <i8 -1, i8 undef>
   %ry = icmp eq <2 x i8> %y, <i8 -1, i8 undef>
   %r = and <2 x i1> %rx, %ry
   ret <2 x i1> %r
 }
 
 define <2 x i1> @icmp_eq_m1_and_eq_undef_m1(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @icmp_eq_m1_and_eq_undef_m1(
-; CHECK-NEXT:    [[RX:%.*]] = icmp eq <2 x i8> [[X:%.*]], <i8 -1, i8 undef>
-; CHECK-NEXT:    [[RY:%.*]] = icmp eq <2 x i8> [[Y:%.*]], <i8 undef, i8 -1>
-; CHECK-NEXT:    [[R:%.*]] = and <2 x i1> [[RX]], [[RY]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i8> [[TMP1]], <i8 -1, i8 -1>
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %rx = icmp eq <2 x i8> %x, <i8 -1, i8 undef>
   %ry = icmp eq <2 x i8> %y, <i8 undef, i8 -1>
   %r = and <2 x i1> %rx, %ry
   ret <2 x i1> %r
 }
 
;
   %ry = icmp eq <2 x i8> %y, <i8 -1, i8 undef>
   %r = or <2 x i1> %rx, %ry
   ret <2 x i1> %r
 }
 
 
 define <2 x i1> @icmp_ne_m1_or_ne_m1(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @icmp_ne_m1_or_ne_m1(
-; CHECK-NEXT:    [[RX:%.*]] = icmp ne <2 x i8> [[X:%.*]], <i8 -1, i8 -1>
-; CHECK-NEXT:    [[RY:%.*]] = icmp ne <2 x i8> [[Y:%.*]], <i8 -1, i8 undef>
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i1> [[RX]], [[RY]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ne <2 x i8> [[TMP1]], <i8 -1, i8 -1>
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %rx = icmp ne <2 x i8> %x, <i8 -1, i8 -1>
   %ry = icmp ne <2 x i8> %y, <i8 -1, i8 undef>
   %r = or <2 x i1> %rx, %ry
   ret <2 x i1> %r
 }

llvm/test/Transforms/PhaseOrdering/pr62311.ll

 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Function Attrs: mustprogress nounwind uwtable
 define noundef zeroext i1 @allones(<8 x i64> noundef %x) {
 ; CHECK-LABEL: @allones(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[VECEXT:%.*]] = extractelement <8 x i64> [[X:%.*]], i64 0
-; CHECK-NEXT:    [[VECEXT1:%.*]] = extractelement <8 x i64> [[X]], i64 1
-; CHECK-NEXT:    [[TMP0:%.*]] = and i64 [[VECEXT]], [[VECEXT1]]
-; CHECK-NEXT:    [[OR_COND:%.*]] = icmp eq i64 [[TMP0]], -1
-; CHECK-NEXT:    [[VECEXT4:%.*]] = extractelement <8 x i64> [[X]], i64 2
-; CHECK-NEXT:    [[VECEXT7:%.*]] = extractelement <8 x i64> [[X]], i64 3
-; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[VECEXT4]], [[VECEXT7]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[TMP1]], -1
-; CHECK-NEXT:    [[OR_COND21:%.*]] = and i1 [[OR_COND]], [[TMP2]]
-; CHECK-NEXT:    [[VECEXT10:%.*]] = extractelement <8 x i64> [[X]], i64 4
-; CHECK-NEXT:    [[VECEXT13:%.*]] = extractelement <8 x i64> [[X]], i64 5
-; CHECK-NEXT:    [[TMP3:%.*]] = and i64 [[VECEXT10]], [[VECEXT13]]
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i64 [[TMP3]], -1
-; CHECK-NEXT:    [[OR_COND23:%.*]] = and i1 [[TMP4]], [[OR_COND21]]
-; CHECK-NEXT:    [[VECEXT16:%.*]] = extractelement <8 x i64> [[X]], i64 6
-; CHECK-NEXT:    [[CMP17:%.*]] = icmp eq i64 [[VECEXT16]], -1
-; CHECK-NEXT:    [[OR_COND24:%.*]] = and i1 [[CMP17]], [[OR_COND23]]
-; CHECK-NEXT:    br i1 [[OR_COND24]], label [[LAND_RHS:%.*]], label [[LAND_END:%.*]]
-; CHECK:       land.rhs:
-; CHECK-NEXT:    [[VECEXT18:%.*]] = extractelement <8 x i64> [[X]], i64 7
-; CHECK-NEXT:    [[CMP19:%.*]] = icmp eq i64 [[VECEXT18]], -1
-; CHECK-NEXT:    br label [[LAND_END]]
-; CHECK:       land.end:
-; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ false, [[ENTRY:%.*]] ], [ [[CMP19]], [[LAND_RHS]] ]
-; CHECK-NEXT:    ret i1 [[TMP5]]
+; CHECK-NEXT:    [[TMP0:%.*]] = tail call i64 @llvm.vector.reduce.and.v8i64(<8 x i64> [[X:%.*]])
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[TMP0]], -1
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
 entry:
   %vecext = extractelement <8 x i64> %x, i32 0
   %cmp = icmp eq i64 %vecext, -1
   %vecext1 = extractelement <8 x i64> %x, i32 1
   %cmp2 = icmp eq i64 %vecext1, -1
   %or.cond = select i1 %cmp, i1 %cmp2, i1 false
   %vecext4 = extractelement <8 x i64> %x, i32 2