Simplify more cases of logical ops of masked icmps.

[hjyamauchi]

Summary

For example,

((X & 255) != 0) && ((X & 15) == 8) -> ((X & 15) == 8).
((X & 7) != 0) && ((X & 15) == 8) -> false.

[hjyamauchi]

I found a bug in the first revision. Please hold off reviews. Will update.

[hjyamauchi]

Fixed bugs in the previous revision.

[hjyamauchi]

Ok, ready for reviews.

[davidxl]

test/Transforms/InstCombine/icmp-logical.ll

332

This one should be simplified to x & 15 != 9 // aka 1001

364

This one should be simplified to x & 15 != 8

430

perhaps also add a case of (x&6) == 0) || (x&15)!= 8 ==> true

[hjyamauchi]

Addressed comments.

[davidxl]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

309–310

Update the comment since return type changes. Also document parameters LHS, RHS, PredL and PredR.

438

Document this method with a small example.

444

&& -> &

448

->

551

Add function documentation.

test/Transforms/InstCombine/icmp-logical.ll

204

x&&15 --> x&15

341

&& --> &

Similarly, || --> | in other places.

[hjyamauchi]

Addressed comments.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

448

What does this comment mean?

[hjyamauchi]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

448

Now I see what you meant. Done. It was formatted as a table :)

[davidxl]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

438

icmp(A&B) ==/!= C

448

Do you have test case cover this when LSH and RHS are swapped?

(icmp eq (A &D), E) & (icmp ne (A & B, 0))

452

replace 0 with 'C' in the example.

460

Do you need to check CCst is Zero?

472

It seems to me, it is sufficient to do the following check:

1. check if mask B is a subset of mask D
2. check if (E & B) != 0 is true

If both 1) and 2) are satisfied, the simplification is legal.

[hjyamauchi]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

452

LHS being of type Mask_NotAllZeroes means that LHS is or can be converted into the form "(icmp ne (A & B), 0)". I think 0 would be better here because the right hand side of the LHS isn't necessarily C. Note the case of Mask_NotAllZeroes where B==C and B is a power of two (see lines 216 and 269 above) where we get "(icmp eq (A & B), C)" (B==C) but interpret it as (equivalent) "(icmp ne (A & B), 0)".

460

Similarly, C isn't necessarily zero if Mask_NotAllZeroes is due to the case for B==C and B is a power of two. So, no.

472

I need a clarification on this.

I think the case you are referring to, which is an important one, is covered by lines 552-553 below. But there are several other cases of simplifications below. There are simplifications we can do even when B isn't a subset of D below, eg. (icmp ne (A & 255), 0) & (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8).

Do you mean we can drop the other cases?

[hjyamauchi]

Addressed comments.

[hjyamauchi]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

448

Added swapped tests.

[davidxl]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

497

This check can probably be extended:

1. B's bitset subtracts the intersection of B and D contains only one bit
2. B and D's intersection have zero values

In other words, D does not need to be power of 2

528

Can you introduce a small lambda here to be reused here and other places?

auto IsSubset = [](Value *V1, Value *V2) {

....

};

if (IsSubset(BCst, DCst)) ....

534

Can you split the comment here for case in line 548 and line 552?

[hjyamauchi]

Addressed comments.

[hjyamauchi]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

497

Is there a chance that those two conditions you are referring to *are* what the current code is already checking here?

To be more specific,

Isn't the condition 1 equivalent to "(B & (B ^ D)).isPowerOf2()" that the current code checks?

(I meant "(B & (B ^ D))" as the bits that are 1 in B but 0 in D.)

For example, suppose B = 1100 and D = 0101. The condition 1 would say 1100 - (1100 & 0101) = 1100 - 0100 = 1000 while (B & (B ^ D)) = (1100 & (1100 ^ 0101)) = (1100 & 1001) = 1000.

Also, isn't the condition 2 equivalent to "((B & D) & E) == 0" that the current code checks?

(Note that in the current code, it's not D, but (B & (B ^ D)) that needs to be a power of 2.)

Do you have an example that isn't handled by the current code but is handled by the suggested extension?

[davidxl]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

497

You are right. Perhaps add a comment just before the condition to document the semantics of the check.

[hjyamauchi]

Addressed comments.

[davidxl]

lgtm

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

static bool decomposeBitTestICmp(Value *LHS, Value *RHS, CmpInst::Predicate &Pred,
 
   Y = ConstantInt::get(X->getType(), Mask);
   Z = ConstantInt::get(X->getType(), 0);
   return true;
 }
 
 /// Handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E).
 /// Return the set of pattern classes (from MaskedICmpType) that both LHS and
 /// RHS satisfy.
-static unsigned getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C,
-                                         Value *&D, Value *&E, ICmpInst *LHS,
-                                         ICmpInst *RHS,
-                                         ICmpInst::Predicate &PredL,
-                                         ICmpInst::Predicate &PredR) {
+static
+Optional<std::pair<unsigned, unsigned>>
+getMaskedTypeForICmpPair(Value *&A, Value *&B, Value *&C,
   // vectors are not (yet?) supported. Don't support pointers either.
   if (!LHS->getOperand(0)->getType()->isIntegerTy() ||
       !RHS->getOperand(0)->getType()->isIntegerTy())
-    return 0;
+    return None;
 
   // Here comes the tricky part:
   // LHS might be of the form L11 & L12 == X, X == L21 & L22,
   // and L11 & L12 == L21 & L22. The same goes for RHS.
   // Now we must find those components L** and R**, that are equal, so
   // that we can extract the parameters A, B, C, D, and E for the canonical
   // above.
   Value *L1 = LHS->getOperand(0);
if (decomposeBitTestICmp(L1, L2, PredL, L11, L12, L2)) {
     if (!match(L2, m_And(m_Value(L21), m_Value(L22)))) {
       L21 = L2;
       L22 = Constant::getAllOnesValue(L2->getType());
     }
   }
 
   // Bail if LHS was a icmp that can't be decomposed into an equality.
   if (!ICmpInst::isEquality(PredL))
-    return 0;
+    return None;
 
   Value *R1 = RHS->getOperand(0);
   Value *R2 = RHS->getOperand(1);
   Value *R11, *R12;
   bool Ok = false;
   if (decomposeBitTestICmp(R1, R2, PredR, R11, R12, R2)) {
     if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
       A = R11;
       D = R12;
     } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
       A = R12;
       D = R11;
     } else {
-      return 0;
+      return None;
     }
     E = R2;
     R1 = nullptr;
     Ok = true;
   } else {
     if (!match(R1, m_And(m_Value(R11), m_Value(R12)))) {
       // As before, model no mask as a trivial mask if it'll let us do an
       // optimization.
if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
       D = R11;
       E = R2;
       Ok = true;
     }
   }
 
   // Bail if RHS was a icmp that can't be decomposed into an equality.
   if (!ICmpInst::isEquality(PredR))
-    return 0;
+    return None;
 
   // Look for ANDs on the right side of the RHS icmp.
   if (!Ok) {
     if (!match(R2, m_And(m_Value(R11), m_Value(R12)))) {
       R11 = R2;
       R12 = Constant::getAllOnesValue(R2->getType());
     }
 
     if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) {
       A = R11;
       D = R12;
       E = R1;
       Ok = true;
     } else if (R12 == L11 || R12 == L12 || R12 == L21 || R12 == L22) {
       A = R12;
       D = R11;
       E = R1;
       Ok = true;
     } else {
-      return 0;
+      return None;
     }
   }
   if (!Ok)
-    return 0;
+    return None;
 
   if (L11 == A) {
     B = L12;
     C = L2;
   } else if (L12 == A) {
     B = L11;
     C = L2;
   } else if (L21 == A) {
     B = L22;
     C = L1;
   } else if (L22 == A) {
     B = L21;
     C = L1;
   }
 
   unsigned LeftType = getMaskedICmpType(A, B, C, PredL);
   unsigned RightType = getMaskedICmpType(A, D, E, PredR);
-  return LeftType & RightType;
+  return Optional<std::pair<unsigned, unsigned>>(std::make_pair(LeftType, RightType));
+}
+
+static Value * foldLogOpOfMaskedICmps_NotAllZeros_BMask_Mixed(
+    ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
+    Value *A, Value *B, Value *C, Value *D, Value *E,
+    ICmpInst::Predicate PredL, ICmpInst::Predicate PredR,
+    unsigned LHSMask, unsigned RHSMask) {
+  // We are given the canonical form:
+  //   (icmp ne (A & B), 0) && (icmp eq (A & D), E).
+  // where D & E == E.
+  //
+  // If IsAnd is false, we get it in negated form:
+  //   (icmp eq (A & B), 0) || (icmp ne (A & D), E) ->
+  //      !((icmp ne (A & B), 0) && (icmp eq (A & D), E)).
+  //
+  // We currently handle the case of B, C, D, E are constant.
+  //
+  // If there's no contradiction, ((B & D) & E) != 0, then RHS implies LHS, so
+  // (LHS && RHS) == RHS. Otherwise, the whole expression becomes false (or true
+  // if negated.)
+  //
+  // For example,
+  // (icmp ne (A & 255), 0) && (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8).
+  // (icmp ne (A & 7), 0) && (icmp eq (A & 15), 8) -> false.
+  // (icmp ne (A & 12), 0) && (icmp eq (A & 15), 8) -> (icmp eq (A & 15), 8).
+  ConstantInt *BCst = dyn_cast<ConstantInt>(B);
+  if (!BCst)
+    return nullptr;
+  ConstantInt *CCst = dyn_cast<ConstantInt>(C);
+  if (!CCst)
+    return nullptr;
+  ConstantInt *DCst = dyn_cast<ConstantInt>(D);
+  if (!DCst)
+    return nullptr;
+  ConstantInt *ECst = dyn_cast<ConstantInt>(E);
+  if (!ECst)
+    return nullptr;
+
+  // Update E to the canonical form when D is a power of two and RHS is
+  // canonicalized as,
+  // (icmp ne (A & D), 0) -> (icmp eq (A & D), D) or
+  // (icmp ne (A & D), D) -> (icmp eq (A & D, 0).
+  if (PredR != (IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE))
+    ECst = cast<ConstantInt>(ConstantExpr::getXor(DCst, ECst));
+
+  if (ConstantExpr::getAnd(ConstantExpr::getAnd(BCst, DCst), ECst) !=
+      ConstantInt::get(BCst->getType(), 0))
+    return RHS;
+  return ConstantInt::get(LHS->getType(), !IsAnd);
+}
+
+static Value *foldLogOpOfMaskedICmpsAsymmetric(
+    ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
+    Value *A, Value *B, Value *C, Value *D, Value *E,
+    ICmpInst::Predicate PredL, ICmpInst::Predicate PredR,
+    unsigned LHSMask, unsigned RHSMask) {
+  assert(ICmpInst::isEquality(PredL) && ICmpInst::isEquality(PredR) &&
+         "Expected equality predicates for masked type of icmps.");
+  // Handle Mask_NotAllZeros-BMask_Mixed cases.
+  // (icmp ne/eq (A & B), C) &&/|| (icmp eq/ne (A & D), E), or
+  // (icmp eq/ne (A & B), C) &&/|| (icmp ne/eq (A & D), E)
+  //    which gets swapped to
+  //    (icmp ne/eq (A & D), E) &&/|| (icmp eq/ne (A & B), C).
+  if (!IsAnd) {
+    LHSMask = conjugateICmpMask(LHSMask);
+    RHSMask = conjugateICmpMask(RHSMask);
+  }
+  if ((LHSMask & Mask_NotAllZeros) && (RHSMask & BMask_Mixed)) {
+    if (Value *V = foldLogOpOfMaskedICmps_NotAllZeros_BMask_Mixed(
+            LHS, RHS, IsAnd, A, B, C, D, E,
+            PredL, PredR, LHSMask, RHSMask)) {
+      return V;
+    }
+  } else if ((LHSMask & BMask_Mixed) && (RHSMask & Mask_NotAllZeros)) {
+    if (Value *V = foldLogOpOfMaskedICmps_NotAllZeros_BMask_Mixed(
+            RHS, LHS, IsAnd, A, D, E, B, C,
+            PredR, PredL, RHSMask, LHSMask)) {
+      return V;
+    }
+  }
+  return nullptr;
 }
 
 /// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
 /// into a single (icmp(A & X) ==/!= Y).
 static Value *foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
                                      llvm::InstCombiner::BuilderTy &Builder) {
   Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr, *E = nullptr;
   ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
-  unsigned Mask =
+  Optional<std::pair<unsigned, unsigned>> MaskPair =
       getMaskedTypeForICmpPair(A, B, C, D, E, LHS, RHS, PredL, PredR);
-  if (Mask == 0)
+  if (!MaskPair)
     return nullptr;
-
   assert(ICmpInst::isEquality(PredL) && ICmpInst::isEquality(PredR) &&
          "Expected equality predicates for masked type of icmps.");
+  unsigned LHSMask = MaskPair->first;
+  unsigned RHSMask = MaskPair->second;
+  unsigned Mask = LHSMask & RHSMask;
+  if (Mask == 0) {
+    // Even if the two sides don't share a common pattern, check if folding can
+    // still happen.
+    if (Value *V = foldLogOpOfMaskedICmpsAsymmetric(
+            LHS, RHS, IsAnd, A, B, C, D, E, PredL, PredR, LHSMask, RHSMask))
+      return V;
+    return nullptr;
+  }
 
   // In full generality:
   //     (icmp (A & B) Op C) | (icmp (A & D) Op E)
   // ==  ![ (icmp (A & B) !Op C) & (icmp (A & D) !Op E) ]
   //
   // If the latter can be converted into (icmp (A & X) Op Y) then the former is
   // equivalent to (icmp (A & X) !Op Y).
   //
   // Therefore, we can pretend for the rest of this function that we're dealing
   // with the conjunction, provided we flip the sense of any comparisons (both
   // input and output).
 
   // In most cases we're going to produce an EQ for the "&&" case.
   ICmpInst::Predicate NewCC = IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE;
   if (!IsAnd) {
     // Convert the masking analysis into its equivalent with negated
     // comparisons.
     Mask = conjugateICmpMask(Mask);

test/Transforms/InstCombine/icmp-logical.ll

 ;
   %xor1 = xor <2 x i64> %a, %b
   %xor2 = xor <2 x i64> %c, %d
   %or = or <2 x i64> %xor1, %xor2
   %cmp = icmp ne <2 x i64> %or, zeroinitializer
   ret <2 x i1> %cmp
 }
 
+; ((X & 15) != 0 && (X & 15) == 8) -> (X & 15) == 8
+define i1 @and_masked_icmps_mask_notallzeros_bmask_mixed_0(i32 %x) {
+; CHECK-LABEL: @and_masked_icmps_mask_notallzeros_bmask_mixed_0(
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 %x, 15
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[AND1]], 8
+; CHECK-NEXT:    ret i1 [[CMP1]]
+;
+  %1 = and i32 %x, 15
+  %2 = icmp ne i32 %1, 0
+  %3 = and i32 %x, 15
+  %4 = icmp eq i32 %3, 8
+  %5 = and i1 %2, %4
+  ret i1 %5
+}
+
+; ((X & 255) != 0 && (X & 15) == 8) -> (X & 15) == 8
+define i1 @and_masked_icmps_mask_notallzeros_bmask_mixed_1(i32 %x) {
+; CHECK-LABEL: @and_masked_icmps_mask_notallzeros_bmask_mixed_1(
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 %x, 15
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[AND1]], 8
+; CHECK-NEXT:    ret i1 [[CMP1]]
+;
+  %1 = and i32 %x, 255
+  %2 = icmp ne i32 %1, 0
+  %3 = and i32 %x, 15
+  %4 = icmp eq i32 %3, 8
+  %5 = and i1 %2, %4
+  ret i1 %5
+}
+
+; ((X & 7) != 0 && (X & 15) == 8) -> false
+define i1 @and_masked_icmps_mask_notallzeros_bmask_mixed_2(i32 %x) {
+; CHECK-LABEL: @and_masked_icmps_mask_notallzeros_bmask_mixed_2(
+; CHECK-NEXT:    ret i1 false
+;
+  %1 = and i32 %x, 7
+  %2 = icmp ne i32 %1, 0
+  %3 = and i32 %x, 15
+  %4 = icmp eq i32 %3, 8
+  %5 = and i1 %2, %4
+  ret i1 %5
+}
+
+; ((X & 12) != 0 && (X & 15) == 8) -> (X & 15) == 8
+define i1 @and_masked_icmps_mask_notallzeros_bmask_mixed_3(i32 %x) {
+; CHECK-LABEL: @and_masked_icmps_mask_notallzeros_bmask_mixed_3(
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 %x, 15
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[AND1]], 8
+; CHECK-NEXT:    ret i1 [[CMP1]]
+;
+  %1 = and i32 %x, 12
+  %2 = icmp ne i32 %1, 0
+  %3 = and i32 %x, 15
+  %4 = icmp eq i32 %3, 8
+  %5 = and i1 %2, %4
+  ret i1 %5
+}
+
+; ((X & 15) == 0 || (X & 15) != 8) -> !((X & 15) != 0 && (X & 15) == 8)) ->
+; !((X & 15) == 8) -> (X & 15) != 8
+define i1 @or_masked_icmps_mask_notallzeros_bmask_mixed_0(i32 %x) {
+; CHECK-LABEL: @or_masked_icmps_mask_notallzeros_bmask_mixed_0(
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 %x, 15
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[AND1]], 8
+; CHECK-NEXT:    ret i1 [[CMP1]]
+;
+  %1 = and i32 %x, 15
+  %2 = icmp eq i32 %1, 0
+  %3 = and i32 %x, 15
+  %4 = icmp ne i32 %3, 8
+  %5 = or i1 %2, %4
+  ret i1 %5
+}
+
+; ((X & 255) == 0 || (X & 15) != 8) -> !((X & 255) != 0 && (X & 15) == 8) ->
+; !((X & 15) == 8) -> (X & 15) != 8
+define i1 @or_masked_icmps_mask_notallzeros_bmask_mixed_1(i32 %x) {
+; CHECK-LABEL: @or_masked_icmps_mask_notallzeros_bmask_mixed_1(
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 %x, 15
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[AND1]], 8
+; CHECK-NEXT:    ret i1 [[CMP1]]
+;
+  %1 = and i32 %x, 255
+  %2 = icmp eq i32 %1, 0
+  %3 = and i32 %x, 15
+  %4 = icmp ne i32 %3, 8
+  %5 = or i1 %2, %4
+  ret i1 %5
+}
+
+; ((X & 7) == 0 || (X & 15) != 8) -> !((X & 7) != 0 && (X & 15) == 8) ->
+; !(false) -> true
+define i1 @or_masked_icmps_mask_notallzeros_bmask_mixed_2(i32 %x) {
+; CHECK-LABEL: @or_masked_icmps_mask_notallzeros_bmask_mixed_2(
+; CHECK-NEXT:    ret i1 true
+;
+  %1 = and i32 %x, 7
+  %2 = icmp eq i32 %1, 0
+  %3 = and i32 %x, 15
+  %4 = icmp ne i32 %3, 8
+  %5 = or i1 %2, %4
+  ret i1 %5
+}
+
+; ((X & 12) == 0 || (X & 15) != 8) -> !((X & 12) != 0 && (X & 15) == 8) ->
+; !((X & 15) == 8) -> (X & 15) != 8
+define i1 @or_masked_icmps_mask_notallzeros_bmask_mixed_3(i32 %x) {
+; CHECK-LABEL: @or_masked_icmps_mask_notallzeros_bmask_mixed_3(
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 %x, 15
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[AND1]], 8
+; CHECK-NEXT:    ret i1 [[CMP1]]
+;
+  %1 = and i32 %x, 12
+  %2 = icmp eq i32 %1, 0
+  %3 = and i32 %x, 15
+  %4 = icmp ne i32 %3, 8
+  %5 = or i1 %2, %4
+  ret i1 %5
+}