[InstCombine] Optimize and of icmps with power-of-2 and contiguous masks

[jmciver]

Summary

Add an instance combine optimization for expressions of the form:

(%arg u< C1) & ((%arg & C2) != C2) -> %arg u< C2

Where C1 is a power-of-2 and C2 is a contiguous mask starting 1 bit below C1.

This commit resolves GitHub missed-optimization issue #54856.

All test have been verified with alive2.

Scalar tests:

• @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_2147483648_1610612736 + swapped
• @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_2147483648_2147483647 + swapped
• @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_2147483648_805306368 + swapped
• @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_1073741824_1073741823 + swapped
• @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_8_7 + swapped
• @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_8_6 + swapped

Vector tests:

• @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_vector_2147483648_2147483647 + swapped
• @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_vector_2147483648_1610612736_2147483647 + swapped
• @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_vector_splat_2147483648_1610612736_2147483647
• @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_vector_128_others + swapped
• @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_vector_64_others + swapped

[jmciver]

All six reported failing tests (due to timeouts) are passing locally in my build/test environment.

[jmciver]

Fix capitzalation of function names containing ICMP

[jmciver]

Based on functionality of the optimization I believe foldLogOpOfMaskedICmps to be a reasonable location. However, it maybe better to create a new function and call it from InstCombinerImpl::foldAndOrOfICmps based on the following.

The placement of the call to foldLogOpOfMaskedICmps_AllZeros_BMask_NotMixed_and_NotAllOnes in the function foldLogOpOfMaskedICmps breaks the consistency of the conditional testing based on the conjunction of left and right mask (see variable Mask line 586). It is possible to place calls to foldLogOpOfMaskedICmps_AllZeros_BMask_NotMixed_and_NotAllOnes in two locations in foldLogOpOfMaskedICmps:

• In function foldLogOpOfMaskedIcmpsAsymmetric called from conditional block Mask == 0 (line 593)
• In conditional block Mask & (Mask_NotAllZeros | BMask_NotAllOnes (line 655)

I opted against this due to readability.

Thanks in advance for any feedback!

[jmciver]

To reduce performance impact I am thinking that the call to foldLogOpOfMaskedICmps_AllZeros_BMask_NotMixed_and_NotAllOnes should be moved into a new function, foldPowerOf2AndWithLesserContinuous, and then call this function from foldAndOrOfICmps. This will help to keep the purpose of foldLogOpOfMaskedICmps clear and reduce the overhead by not testing for a less probable optimization early.

[RKSimon]

Please can you add vector test coverage - uniform / non-uniform cases and cases containing undef / poison elements

[jmciver]

Thanks @RKSimon! I will work on adding the additional tests.

[jmciver]

As per @RKSimon's feedback I have discovered a number of vector deficiencies in my implementation.

From reading https://developers.redhat.com/articles/2022/12/20/how-contribute-llvm# (which is excellent) I have a better understanding of how to structure this patch. I am currently working on further vector test case generation and will post it as a parent to this patch in the next day or so.

[jmciver]

Add support for vectors:

• C1 supports splat vectors with poison/undef.
• C2 supports vectors with unique elements.

[jmciver]

Fix no change test case updated in D143044

[jmciver]

Update icmp-logical.ll test names as per recommendation in D143044

[jmciver]

ping

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

504

Its a bit hard to follow the cases, can you add a comment specifying the transformation being done at each non nullptr return.

587

remove empty line.

[jmciver]

Add comments to each non nullptr conditional.

Refactor leading ones and zeros comparison to use equality operator.

[jmciver]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

504

Thanks for taking the time to review. Let me know if you think the comments help.

[jmciver]

Rebase onto latest main.

[jmciver]

Added Alive2 URLs to patch summary.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

486

Can you be explicit about what you are transforming this into (ult).

Also shouldn't it be (icmp (A & B) == 0) & (icmp (A & D) != E)?

491

C is unused AFAICT.

496

As a TODO (or here if you want to) you could also do:

`(icmp (A & B) == B) & (icmp (A & D) == D)` -> `(icmp (A & (B | D) == (B | D)`

https://alive2.llvm.org/ce/z/sFcvJP

545

Can you add some tests with undef elements.

Also if undef is allowed in the non-vec case as well, this check and the scalar one could be done with a lambda.

[jmciver]

Resolving feedback items identified by @goldstein.w.n

In function foldLogOpOfMaskedICmpsAllZerosBMaskNeqMixedOrContiguous:

• Improved explicitness of target transformation in function comment
• Removed unused function parameter
• Added splat vector test using undef
• Refactored test for compatibility into a lambda function

[jmciver]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

496

This maybe already handled, but let me know if I am missing something:

https://godbolt.org/z/WqnveefxP

https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp#L577

545

I added tests using undef splat vectors.

The conversion to a lambda is much cleaner. I have enabled support for undef/poison support in the scalar case. However, testing of this transformation using scalar undef or poison enables an earlier optimization path:

https://godbolt.org/z/7c87ba45v

The following Alive2 output show the scalar use of undef and poison with this transformation to be correct:

https://alive2.llvm.org/ce/z/9_eQny

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

496

You're right, for some reason thought it wasn't being handled.

537

nit(style): i -> I

545

Thanks. Just FYI, you can do multiple proofs in the same link by postfixing 'src' with either '\d+' or '_<desc>' i.e:
https://godbolt.org/z/M5eK16Ess

551

I think it would be clearer to organize this as follows:

if(IsVec) {
foreach(B, D, E) {
if(!isReducible) { return nullptr; }
}
}
else {
if(!isReducible) { return nullptr; }
}
return ICmpInst(ULT, A, D);

[jmciver]

Refactor scalar and vector tests to emit icmp from one location

Prior to this update foldLogOpOfMaskedICmpsAllZerosBMaskNeqMixedOrContiguous
returned icmp expressions from two locations. Acceptance is now handled at the
end of the function resulting in a single location for icmp emission.

[jmciver]

Refactor scalar and vector tests to emit icmp from one location

Prior to this update foldLogOpOfMaskedICmpsAllZerosBMaskNeqMixedOrContiguous
returned icmp expressions from two locations. Acceptance is now handled at the
end of the function resulting in a single location for icmp emission.

[jmciver]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

545

Thanks for the Godbolt pointer!

551

I agree that is much cleaner. I have refactored accordingly. I added a comment to the function header stating that parameter B supports masking.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

545

nit: maybe:

} 
// Test scalar type arguments for conversion.    
else if (!isReducible(B, D, E)) {
     return nullptr;
}

Although given the LLVM style of '}' and 'else' on the same line its a bit out of place. No strong feelings so update if you see fit.

573

When do we transform to A & X eq/ne Y? I don't see that code.

llvm/test/Transforms/InstCombine/icmp-logical.ll

1731–2099

One more thing. Can you put the "fail" keyword somewhere in the tests that you expect no change in. Think it helps make it crystal clear exact what the is meant to happen.

[jmciver]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

573

That is a great question. The A & X eq/ne Y is emitted by the other transformations in foldLogOpOfMaskedICmps. When I started developing this patch I picked this location as the classifier function getMaskedTypeForICmpPair converted the source to the form:
(icmp ne (A & B), C) | (icmp qe (A & D), E). This is violation of the original intended use foldLogOpOfMaskedICmps at it is targetting ICMPs of the same operator, which fold to (icmp(A & X) ==/!= Y).

My current thinking is to move this fold into one of the other called functions in foldAndOrOfICmps (option 1) or create its own function and then call that from foldAndOrOfICmps (option 2).

Option 1: One possible function is foldIsPowerOf2, but it is specific to ctpop based expressions so I am hesitant to expand functionality.

Option 2: Create a function called foldIsNegativePowerOf2 (open to other names), which will attempt the transform X <u 2^n to (X & ~(2^n-1)) == 0 and then perform the subsequent tests for folding as seen in foldLogOpOfMaskedICmpsAllZerosBMaskNeqMixedOrContiguous. This removes the need for verbose aforementioned function name and provides a concise "does one thing well" function.

I think option 2 is probably the best path. I'll go ahead and implement and see what it looks like. If you have other ideas let me know!

llvm/test/Transforms/InstCombine/icmp-logical.ll

1731–2099

I updated the names of tests that intentionally result in no change with a "_fail" postfix, see D143044.

[jmciver]

Add foldPowerOf2AndShiftedMask(...) and call from InstCombinerImpl::foldAndOrOfICmps(...)

Place the folding of ((icmp X u< P) & (icmp(X & M) != M)) or ((icmp X s> -1) &
(icmp(X & M) != M)) into (icmp X u< M) in foldPowerOf2AndShiftedMask(...). This
function attempts the transform of (X <u 2^n) into (X & ~(2^n-1)) == 0 or (icmp
X s> -1) into (icmp (X & SignMask) == 0) and then performs additional checks in
foldNegativePower2AndShiftedMask(...).

This patch delta removes prior implementation work from
foldLogOpOfMaskedICmps(...).

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

573

Bah, I had left reply unsent. Agree option 2 is better (and looks like thats what you did so great)

[goldstein.w.n]

LGTM. I'm not a maintainer so please wait 1/2 days to push so others may take a look.

[jmciver]

@goldstein.w.n thanks for taking the time to review.

I'll hold for a maintainers approval.

[goldstein.w.n]

In D125717#4358964, @jmciver wrote:

@goldstein.w.n thanks for taking the time to review.

I'll hold for a maintainers approval.

you probably want @nikic, hes the defacto maintainer of instcombine

[jmciver]

@nikic this patch is for #54856, which originated from @erikdesjardins.

This refinment is not triggered by building LLVM or anything of the components of the llvm-test-suite.

What are the appropriate next steps to gain InstCombine maintainer sign off?

Thanks in advance for your feedback.

[goldstein.w.n]

In D125717#4385553, @jmciver wrote:

@nikic this patch is for #54856, which originated from @erikdesjardins.

This refinment is not triggered by building LLVM or anything of the components of the llvm-test-suite.

What are the appropriate next steps to gain InstCombine maintainer sign off?

Thanks in advance for your feedback.

you might try @RKSimon.

Also to be fair I do end-to-end reviews (just not a maintainer) and believe this is okay to go out as is. If you don't hear back
soon I don't think it would be an issue to push.
I can run the zorg buildbot tests on this for you if it would help you feel more comfortable about it, or of course you can
wait as you see fit.

[jmciver]

@goldstein.w.n thanks for the reply.

I'll wait until Monday and then proceed to land the patch.

Is it customary to get approval for preceding NFC patches? If yes, can you please take a look at D143044?

Thanks,
John

[goldstein.w.n]

In D125717#4389718, @jmciver wrote:

@goldstein.w.n thanks for the reply.

I'll wait until Monday and then proceed to land the patch.

Is it customary to get approval for preceding NFC patches? If yes, can you please take a look at D143044?

No (ish). If you have push access I think its generally fine to push them with the implementation unless someone posts feedback on it.

Thanks,
John

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if ((BCst->getValue() & ECst->getValue()) != 0)
     return RHS;
   // Otherwise, LHS and RHS contradict and the whole expression becomes false
   // (or true if negated.) For example,
   // (icmp ne (A & 7), 0) & (icmp eq (A & 15), 8) -> false.
   // (icmp ne (A & 6), 0) & (icmp eq (A & 15), 8) -> false.
   return ConstantInt::get(LHS->getType(), !IsAnd);
 }
 
+/// Try to fold (icmp(A & B) != 0) & (icmp(A & D) == E), where B is a contiguous
+/// set of ones starting from the most significant bit (negative power of 2), D
+/// and E are equal, and D is a contiguous set of ones starting in the position
+/// the most significant zero bit of B.
+static Value *foldLogOpOfMaskedICmps_AllZeros_BMask_NotMixed_Contiguous(
+    ICmpInst *LHS, ICmpInst *RHS, bool IsAnd, Value *A, Value *B, Value *C,
+    Value *D, Value *E, ICmpInst::Predicate PredL, ICmpInst::Predicate PredR,
+    InstCombiner::BuilderTy &Builder) {
+  assert(ICmpInst::isEquality(PredL) && ICmpInst::isEquality(PredR) &&
+         "Expected equality predicates for masked type of icmps.");
+  if (!IsAnd || PredL != ICmpInst::ICMP_EQ || PredR != ICmpInst::ICMP_NE)
+    return nullptr;
+
+  const APInt *BCst, *DCst, *ECst;
+  if (!match(B, m_APInt(BCst)) || !match(D, m_APInt(DCst)) ||
+      !match(E, m_APInt(ECst)))
+    return nullptr;
+  if (*DCst != *ECst)
+    return nullptr;
+  if (!BCst->isNegatedPowerOf2() || !DCst->isShiftedMask())
+    return nullptr;
+  if (BCst->countLeadingOnes() - DCst->countLeadingZeros() == 0u)
+    return Builder.CreateICmp(ICmpInst::ICMP_ULT, A, D);
+
+  return nullptr;
+}
+
+/// Try to fold (icmp(A & B) != C) & (icmp(A & D) == E) where C is zero and the
+/// BMask is not mixed and not all ones.
+static Value *foldLogOpOfMaskedICmps_AllZeros_BMask_NotMixed_and_NotAllOnes(
+    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, InstCombiner::BuilderTy &Builder) {
+  assert(ICmpInst::isEquality(PredL) && ICmpInst::isEquality(PredR) &&
+         "Expected equality predicates for masked type of icmps.");
+
+  const auto compareBMask = BMask_NotMixed | BMask_NotAllOnes;
+  // Handle Mask_AllZeros-(BMask_NotMixed|BMask_NotAllOnes) cases.
+  if ((LHSMask & Mask_AllZeros) && (RHSMask == compareBMask)) {
+    if (Value *V = foldLogOpOfMaskedICmps_AllZeros_BMask_NotMixed_Contiguous(
+            LHS, RHS, IsAnd, A, B, C, D, E, PredL, PredR, Builder)) {
+      return V;
+    }
+  } else if ((LHSMask == compareBMask) && (RHSMask & Mask_AllZeros)) {
+    if (Value *V = foldLogOpOfMaskedICmps_AllZeros_BMask_NotMixed_Contiguous(
+            RHS, LHS, IsAnd, A, D, E, B, C, PredR, PredL, Builder)) {
+      return V;
+    }
+  }
+  return nullptr;
+}
+
 /// Try to fold (icmp(A & B) ==/!= 0) &/| (icmp(A & D) ==/!= E) into a single
 /// (icmp(A & X) ==/!= Y), where the left-hand side and the right hand side
 /// aren't of the common mask pattern type.
 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, InstCombiner::BuilderTy &Builder) {
   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, Builder)) {
       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, Builder)) {
       return V;
     }
   }
   return nullptr;
 }
 
 /// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
-/// into a single (icmp(A & X) ==/!= Y).
+/// into a single (icmp(A & X) ==/!= Y) or (icmp A u< Y).
 static Value *foldLogOpOfMaskedICmps(ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
                                      InstCombiner::BuilderTy &Builder) {
   Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr, *E = nullptr;
   ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
   Optional<std::pair<unsigned, unsigned>> MaskPair =
       getMaskedTypeForICmpPair(A, B, C, D, E, LHS, RHS, PredL, PredR);
   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 (Value *V = foldLogOpOfMaskedICmps_AllZeros_BMask_NotMixed_and_NotAllOnes(
+          LHS, RHS, IsAnd, A, B, C, D, E, PredL, PredR, LHSMask, RHSMask,
+          Builder))
+    return V;
+
   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,
             Builder))
       return V;
     return nullptr;

llvm/test/Transforms/InstCombine/icmp-logical.ll

 ; CHECK-NEXT:    ret i1 true
 ;
   %t1 = and i32 %x, 6
   %t2 = icmp eq i32 %t1, 0
   %t3 = and i32 %x, 15
   %t4 = icmp ne i32 %t3, 8
   %t5 = select i1 %t4, i1 true, i1 %t2
   ret i1 %t5
 }
+
+; ((X u< 8) & ((X & 7) != 7)) -> X u< 7
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_1(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_1(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 7
+; CHECK-NEXT:    ret i1 [[T1]]
+;
+  %t1 = icmp ult i32 %x, 8
+  %t2 = and i32 %x, 7
+  %t3 = icmp ne i32 %t2, 7
+  %t4 = and i1 %t1, %t3
+  ret i1 %t4
+}
+
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_1flip(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_1flip(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 7
+; CHECK-NEXT:    ret i1 [[T1]]
+;
+  %t1 = icmp ult i32 %x, 8
+  %t2 = and i32 %x, 7
+  %t3 = icmp ne i32 %t2, 7
+  %t4 = and i1 %t3, %t1
+  ret i1 %t4
+}
+
+; ((X u< 8) & ((X & 6) != 6)) -> X u< 6
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_2(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_2(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 6
+; CHECK-NEXT:    ret i1 [[T1]]
+;
+  %t1 = icmp ult i32 %x, 8
+  %t2 = and i32 %x, 6
+  %t3 = icmp ne i32 %t2, 6
+  %t4 = and i1 %t1, %t3
+  ret i1 %t4
+}
+
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_2flip(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_2flip(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 6
+; CHECK-NEXT:    ret i1 [[T1]]
+;
+  %t1 = icmp ult i32 %x, 8
+  %t2 = and i32 %x, 6
+  %t3 = icmp ne i32 %t2, 6
+  %t4 = and i1 %t3, %t1
+  ret i1 %t4
+}
+
+; ((X u< 0x4000000) & ((X & 0x30000000) != 0x30000000)) -> X u< 0x30000000
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_3(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_3(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 805306368
+; CHECK-NEXT:    ret i1 [[T1]]
+;
+  %t1 = icmp ult i32 %x, 1073741824
+  %t2 = and i32 %x, 805306368
+  %t3 = icmp ne i32 %t2, 805306368
+  %t4 = and i1 %t1, %t3
+  ret i1 %t4
+}
+
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_3flip(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_3flip(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 805306368
+; CHECK-NEXT:    ret i1 [[T1]]
+;
+  %t1 = icmp ult i32 %x, 1073741824
+  %t2 = and i32 %x, 805306368
+  %t3 = icmp ne i32 %t2, 805306368
+  %t4 = and i1 %t3, %t1
+  ret i1 %t4
+}
+
+; ((X u< 0x40000000) & ((X & 0x3FFFFFFF) != 0x3FFFFFFF)) -> X u< 0x3FFFFFFF
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_4(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_4(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 1073741823
+; CHECK-NEXT:    ret i1 [[T1]]
+;
+  %t1 = icmp ult i32 %x, 1073741824
+  %t2 = and i32 %x, 1073741823
+  %t3 = icmp ne i32 %t2, 1073741823
+  %t4 = and i1 %t1, %t3
+  ret i1 %t4
+}
+
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_4flip(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_4flip(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 1073741823
+; CHECK-NEXT:    ret i1 [[T1]]
+;
+  %t1 = icmp ult i32 %x, 1073741824
+  %t2 = and i32 %x, 1073741823
+  %t3 = icmp ne i32 %t2, 1073741823
+  %t4 = and i1 %t3, %t1
+  ret i1 %t4
+}
+
+; ((X u< 0x8000000) & ((X & 0x60000000) != 0x60000000)) -> X u< 0x60000000
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_5(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_5(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 1610612736
+; CHECK-NEXT:    ret i1 [[T1]]
+;
+  %t1 = icmp ult i32 %x, 2147483648
+  %t2 = and i32 %x, 1610612736
+  %t3 = icmp ne i32 %t2, 1610612736
+  %t4 = and i1 %t1, %t3
+  ret i1 %t4
+}
+
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_5flip(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_5flip(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 1610612736
+; CHECK-NEXT:    ret i1 [[T1]]
+;
+  %t1 = icmp ult i32 %x, 2147483648
+  %t2 = and i32 %x, 1610612736
+  %t3 = icmp ne i32 %t2, 1610612736
+  %t4 = and i1 %t3, %t1
+  ret i1 %t4
+}
+
+; ((X u< 0x8000000) & ((X & 0x7FFFFFFF) != 0x7FFFFFFF)) -> X u< 0x7FFFFFFF
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_6(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_6(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 2147483647
+; CHECK-NEXT:    ret i1 [[T1]]
+;
+  %t1 = icmp ult i32 %x, 2147483648
+  %t2 = and i32 %x, 2147483647
+  %t3 = icmp ne i32 %t2, 2147483647
+  %t4 = and i1 %t1, %t3
+  ret i1 %t4
+}
+
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_6flip(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_6flip(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 2147483647
+; CHECK-NEXT:    ret i1 [[T1]]
+;
+  %t1 = icmp ult i32 %x, 2147483648
+  %t2 = and i32 %x, 2147483647
+  %t3 = icmp ne i32 %t2, 2147483647
+  %t4 = and i1 %t3, %t1
+  ret i1 %t4
+}
+
+
+; ((X u< 8) & ((X & 5) != 5)) -> no change
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_7(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_7(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 8
+; CHECK-NEXT:    [[T2:%.*]] = and i32 %x, 5
+; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 %t2, 5
+; CHECK-NEXT:    [[T4:%.*]] = and i1 %t1, %t3
+; CHECK-NEXT:    ret i1 [[T4]]
+;
+  %t1 = icmp ult i32 %x, 8
+  %t2 = and i32 %x, 5
+  %t3 = icmp ne i32 %t2, 5
+  %t4 = and i1 %t1, %t3
+  ret i1 %t4
+}
+
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_7flip(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_7flip(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 8
+; CHECK-NEXT:    [[T2:%.*]] = and i32 %x, 5
+; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 %t2, 5
+; CHECK-NEXT:    [[T4:%.*]] = and i1 %t3, %t1
+; CHECK-NEXT:    ret i1 [[T4]]
+;
+  %t1 = icmp ult i32 %x, 8
+  %t2 = and i32 %x, 5
+  %t3 = icmp ne i32 %t2, 5
+  %t4 = and i1 %t3, %t1
+  ret i1 %t4
+}
+
+; ((X u< 8) & ((X & 3) != 3)) -> no change
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_8(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_8(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 8
+; CHECK-NEXT:    [[T2:%.*]] = and i32 %x, 3
+; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 %t2, 3
+; CHECK-NEXT:    [[T4:%.*]] = and i1 %t1, %t3
+; CHECK-NEXT:    ret i1 [[T4]]
+;
+  %t1 = icmp ult i32 %x, 8
+  %t2 = and i32 %x, 3
+  %t3 = icmp ne i32 %t2, 3
+  %t4 = and i1 %t1, %t3
+  ret i1 %t4
+}
+
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_8flip(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_8flip(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 8
+; CHECK-NEXT:    [[T2:%.*]] = and i32 %x, 3
+; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 %t2, 3
+; CHECK-NEXT:    [[T4:%.*]] = and i1 %t3, %t1
+; CHECK-NEXT:    ret i1 [[T4]]
+;
+  %t1 = icmp ult i32 %x, 8
+  %t2 = and i32 %x, 3
+  %t3 = icmp ne i32 %t2, 3
+  %t4 = and i1 %t3, %t1
+  ret i1 %t4
+}
+
+; ((X u< 256) & ((X & 239) != 239)) -> no change
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_9(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_9(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 256
+; CHECK-NEXT:    [[T2:%.*]] = and i32 %x, 239
+; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 %t2, 239
+; CHECK-NEXT:    [[T4:%.*]] = and i1 %t1, %t3
+; CHECK-NEXT:    ret i1 [[T4]]
+;
+  %t1 = icmp ult i32 %x, 256
+  %t2 = and i32 %x, 239
+  %t3 = icmp ne i32 %t2, 239
+  %t4 = and i1 %t1, %t3
+  ret i1 %t4
+}
+
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_9flip(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_9flip(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 256
+; CHECK-NEXT:    [[T2:%.*]] = and i32 %x, 239
+; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 %t2, 239
+; CHECK-NEXT:    [[T4:%.*]] = and i1 %t3, %t1
+; CHECK-NEXT:    ret i1 [[T4]]
+;
+  %t1 = icmp ult i32 %x, 256
+  %t2 = and i32 %x, 239
+  %t3 = icmp ne i32 %t2, 239
+  %t4 = and i1 %t3, %t1
+  ret i1 %t4
+}
+
+; ((X u< 8) & ((X & 112) != 112)) -> no change
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_10(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_10(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 8
+; CHECK-NEXT:    [[T2:%.*]] = and i32 %x, 112
+; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 %t2, 112
+; CHECK-NEXT:    [[T4:%.*]] = and i1 %t1, %t3
+; CHECK-NEXT:    ret i1 [[T4]]
+;
+  %t1 = icmp ult i32 %x, 8
+  %t2 = and i32 %x, 112
+  %t3 = icmp ne i32 %t2, 112
+  %t4 = and i1 %t1, %t3
+  ret i1 %t4
+}
+
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_10flip(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_10flip(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 8
+; CHECK-NEXT:    [[T2:%.*]] = and i32 %x, 112
+; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 %t2, 112
+; CHECK-NEXT:    [[T4:%.*]] = and i1 %t3, %t1
+; CHECK-NEXT:    ret i1 [[T4]]
+;
+  %t1 = icmp ult i32 %x, 8
+  %t2 = and i32 %x, 112
+  %t3 = icmp ne i32 %t2, 112
+  %t4 = and i1 %t3, %t1
+  ret i1 %t4
+}
+
+; ((X u< 8) & ((X & 56) != 56)) -> no change
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_11(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_11(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 8
+; CHECK-NEXT:    [[T2:%.*]] = and i32 %x, 56
+; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 %t2, 56
+; CHECK-NEXT:    [[T4:%.*]] = and i1 %t1, %t3
+; CHECK-NEXT:    ret i1 [[T4]]
+;
+  %t1 = icmp ult i32 %x, 8
+  %t2 = and i32 %x, 56
+  %t3 = icmp ne i32 %t2, 56
+  %t4 = and i1 %t1, %t3
+  ret i1 %t4
+}
+
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_11flip(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_11flip(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 8
+; CHECK-NEXT:    [[T2:%.*]] = and i32 %x, 56
+; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 %t2, 56
+; CHECK-NEXT:    [[T4:%.*]] = and i1 %t3, %t1
+; CHECK-NEXT:    ret i1 [[T4]]
+;
+  %t1 = icmp ult i32 %x, 8
+  %t2 = and i32 %x, 56
+  %t3 = icmp ne i32 %t2, 56
+  %t4 = and i1 %t3, %t1
+  ret i1 %t4
+}
+
+; ((X u< 8) & ((X & 24) != 24)) -> no change
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_12(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_12(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 8
+; CHECK-NEXT:    [[T2:%.*]] = and i32 %x, 24
+; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 %t2, 24
+; CHECK-NEXT:    [[T4:%.*]] = and i1 %t1, %t3
+; CHECK-NEXT:    ret i1 [[T4]]
+;
+  %t1 = icmp ult i32 %x, 8
+  %t2 = and i32 %x, 24
+  %t3 = icmp ne i32 %t2, 24
+  %t4 = and i1 %t1, %t3
+  ret i1 %t4
+}
+
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_12flip(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_12flip(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 8
+; CHECK-NEXT:    [[T2:%.*]] = and i32 %x, 24
+; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 %t2, 24
+; CHECK-NEXT:    [[T4:%.*]] = and i1 %t3, %t1
+; CHECK-NEXT:    ret i1 [[T4]]
+;
+  %t1 = icmp ult i32 %x, 8
+  %t2 = and i32 %x, 24
+  %t3 = icmp ne i32 %t2, 24
+  %t4 = and i1 %t3, %t1
+  ret i1 %t4
+}
+
+; ((X u< 8) & ((X & 12) != 12)) -> no change
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_13(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_13(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 8
+; CHECK-NEXT:    [[T2:%.*]] = and i32 %x, 12
+; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 %t2, 12
+; CHECK-NEXT:    [[T4:%.*]] = and i1 %t1, %t3
+; CHECK-NEXT:    ret i1 [[T4]]
+;
+  %t1 = icmp ult i32 %x, 8
+  %t2 = and i32 %x, 12
+  %t3 = icmp ne i32 %t2, 12
+  %t4 = and i1 %t1, %t3
+  ret i1 %t4
+}
+
+define i1 @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_13flip(i32 %x) {
+; CHECK-LABEL: @masked_icmps_mask_allzeros_bmask_notmixed_and_notallones_13flip(
+; CHECK-NEXT:    [[T1:%.*]] = icmp ult i32 %x, 8
+; CHECK-NEXT:    [[T2:%.*]] = and i32 %x, 12
+; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 %t2, 12
+; CHECK-NEXT:    [[T4:%.*]] = and i1 %t3, %t1
+; CHECK-NEXT:    ret i1 [[T4]]
+;
+  %t1 = icmp ult i32 %x, 8
+  %t2 = and i32 %x, 12
+  %t3 = icmp ne i32 %t2, 12
+  %t4 = and i1 %t3, %t1
+  ret i1 %t4
+}