[InstCombine] Simplify more cases of logical ops of masked icmps.

[shawnl]

Summary

Example:

(A & 14) != 0 and (A & 1) != 0 => ((cttz (A ^ 8)) - 1) > 3

[shawnl]

increase context (-U9999)

[shawnl]

Fix test case.

[shawnl]

Fix patch after initial test case did not actually exercise code.

[lebedev.ri]

As discussed in IRC, this needs a bit of work (tests are miscompiled)

[shawnl]

Note to self: If you get the logic reversed in the example, you will get it reversed in the code.

Remove dead code.

[nikic]

Could you please upload the diff with more context? This is done by passing -U99999 to git diff or whichever command you're using.

[shawnl]

There is a bunch of work to be done here, but here is a patch to get started

[shawnl]

fix bug and additional test

[nikic]

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

263 ↗

(On Diff #194909)

This transform already happens prior to your changes (-instsimplify is sufficient).

277 ↗

(On Diff #194909)

This transform already happens prior to your changes (-instcombine).

[shawnl]

[InstCombine] Simplify more cases of logical ops of masked icmps.

Generalizing the work by Hiroshi Yamauchi in
b80dd9b569808cd1d4e672fde77500890edfe446
https://reviews.llvm.org/D43835

Example:

(A & 3) == 3 and (A & 4) == 0 => (A & 7) == 3

[shawnl]

handle or properly

[shawnl]

fshl/fshr and cttz/ctlz need alot of work

[nikic]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

768

This transform doesn't make any sense to me. (icmp eq (A & 3), 0) && (icmp ne (A & 4), 0) is the same as (icmp eq (A & 7) == 4). Which is exactly the expansion we produce for a cttz equality check in https://github.com/llvm-mirror/llvm/blob/3f5d54bc7b3a850a2df14a6f7b7d8661423d824f/lib/Transforms/InstCombine/InstCombineCompares.cpp#L2851-L2866. Using a mask is more efficient and analyzable than using cttz.

[shawnl]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

768

Yes, it only makes sense when the range being matched is !=, or the condition is an or.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (Value *V = foldLogOpOfMaskedICmps_NotAllZeros_BMask_Mixed(
       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();
-  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;
+static Value *foldLogOpOfMaskedICmpsSimple(
+    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,
   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,
             Builder))
       return V;
if (Mask & BMask_Mixed) {
     Value *NewOr2 = ConstantExpr::getOr(CCst, ECst);
     Value *NewAnd = Builder.CreateAnd(A, NewOr1);
     return Builder.CreateICmp(NewCC, NewAnd, NewOr2);
   }
 
   return nullptr;
 }
 
+/// Fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
+/// into (icmp((xor A, Z) & X) ==/!= 0)
+static Value *foldLogOpOfMaskedICmpsXorMask(
+    ICmpInst *LHS, ICmpInst *RHS, bool IsAnd,
+    Value *A, ConstantInt *BCst, ConstantInt *CCst,
+    ConstantInt *DCst, ConstantInt *ECst,
+    ICmpInst::Predicate PredL, ICmpInst::Predicate PredR,
+    llvm::InstCombiner::BuilderTy &Builder) {
+  // Use an Xor mask to compare full range against zero
+  // (icmp(A & 4) == 4) && (icmp(A & 3) == 2)
+  // => (icmp((xor A, 6), 7) == 0)
+  // icmp(A & 4) == 4) || (icmp(A & 3) == 2)
+  // => (icmp((xor A, 1), 7) != 0)
+  APInt BAndD = BCst->getValue() & DCst->getValue();
+  Value *X = ConstantExpr::getOr(BCst, DCst);
+  APInt Z = APInt(), B = BCst->getValue(), C = CCst->getValue(),
+    D = DCst->getValue(), E = ECst->getValue();
+  bool LIsEq = (PredL == ICmpInst::ICMP_EQ);
+  bool RIsEq = (PredR == ICmpInst::ICMP_EQ);
+
+  // We have already tested for contradictions in the B & D overlap
+  Z |= LIsEq ? C & B : ~(C & B);
+  Z |= RIsEq ? E & D : ~(E & D);
+
+  if (!IsAnd)
+    Z ^= BAndD;
+
+  Value *NewXor = Builder.CreateXor(A, ConstantInt::get(A->getContext(), Z));
+  Value *NewAnd = Builder.CreateAnd(X, NewXor);
+  return Builder.CreateICmp(IsAnd ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
+    A, NewAnd);
+}
+
+/// Try to fold (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E)
+/// into a single (icmp(A & X) ==/!= Y).
+/// or into (icmp((xor A, Z) & 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();
+  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;
+
+  // B, C, D, and E must be constants for this optimization
+  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;
+
+  // If B and D intersect, ie. (B & D) != 0, test if they contradict each other
+  // and if so simplify to false (or true if this is an Or).
+  // For example,
+  // (icmp (A & 14), 2) and (icmp (A & 3), 1) -> false.
+  APInt Intersection = BCst->getValue() & DCst->getValue();
+  if (Intersection != 0 &&
+    ((Intersection & CCst->getValue()) != (Intersection & ECst->getValue())))
+      return ConstantInt::get(LHS->getType(), !IsAnd);
+
+  // => (icmp(A & X) ==/!= Y)
+  if (Value *V = foldLogOpOfMaskedICmpsSimple(
+          LHS, RHS, IsAnd, A, B, C, D, E, PredL, PredR, LHSMask, RHSMask,
+          Builder))
+    return V;
+
+  // => (icmp((xor A, Z) & X) ==/!= 0)
+  return foldLogOpOfMaskedICmpsXorMask(
+          LHS, RHS, IsAnd, A, BCst, CCst, DCst, ECst, PredL, PredR, Builder);
+}
+
 /// Try to fold a signed range checked with lower bound 0 to an unsigned icmp.
 /// Example: (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
 /// If \p Inverted is true then the check is for the inverted range, e.g.
 /// (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
 Value *InstCombiner::simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1,
                                         bool Inverted) {
   // Check the lower range comparison, e.g. x >= 0
   // InstCombine already ensured that if there is a constant it's on the RHS.

test/Transforms/InstSimplify/AndOrXor.ll

 ;
   %tmp1 = zext <2 x i16> %a to <2 x i32>
   %tmp2 = zext <2 x i16> %b to <2 x i32>
   %tmp3 = shl nuw <2 x i32> %tmp1, <i32 16, i32 16>
   %tmp4 = or <2 x i32> %tmp2, %tmp3
   %tmp5 = and <2 x i32> %tmp4, <i32 4294901761, i32 4294901761> ; mask with 0xFFFF0001
   ret <2 x i32> %tmp5
 }
+
+define i1 @icmp_set_and_unset_bits(i32 %a) {
+; CHECK-LABEL: @icmp_set_and_unset_bits(
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], 5
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[TMP1]], 4
+; CHECK-NEXT:    ret i1 [[TMP2]]
+;
+  %tmp1 = and i32 %a, 1
+  %tmp2 = icmp eq i32 %tmp1, 0
+  %tmp3 = and i32 %a, 4
+  %tmp4 = icmp ne i32 %tmp3, 0
+  %tmp5 = and i1 %tmp2, %tmp4
+  ret i1 %tmp5
+}