[InstCombine] Fold (!iszero(A & K1) & !iszero(A & K2)) -> (A & (K1 | K2)) == (K1 | K2) if K1 and K2 are a 1-bit mask

[craig.topper]

Summary

This is the demorganed version of the case we already handle for the OR of iszero.

[spatel]

Nice! I was wondering if that was missing.

Can you make a helper function to avoid the code duplication?
Add the tests as a pre-commit, so we just get the diffs?

[craig.topper]

Will do.

Can I change foldOrOfIcmps to take CxtI by reference so we discourage anyone from passing nullptr.

[spatel]

In D34244#781501, @craig.topper wrote:

Will do.

Can I change foldOrOfIcmps to take CxtI by reference so we discourage anyone from passing nullptr.

I have no objections. I'd go full-strength and fix all of the params to be refs in all of the related functions, so everything is uniform. :)
I'd really like to refactor (And/Or)OfICmps, so we have the deMorgan'd versions of each fold together or adjacent. That way, we'll more easily know what's missing from either side.

[craig.topper]

Move to helper method. Make test diffs relative.

[spatel]

LGTM.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (*C1 == *C2 - 1) {
     auto NewPred = JoinedByAnd ? ICmpInst::ICMP_UGT : ICmpInst::ICMP_ULE;
     return Builder->CreateICmp(NewPred, Add, ConstantInt::get(X->getType(), 1));
   }
 
   return nullptr;
 }
 
 /// Fold (icmp)&(icmp) if possible.
-Value *InstCombiner::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS) {
+Value *InstCombiner::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS,
+                                    Instruction *CxtI) {
   ICmpInst::Predicate PredL = LHS->getPredicate(), PredR = RHS->getPredicate();
 
+  // Fold (!iszero(A & K1) & !iszero(A & K2)) ->  (A & (K1 | K2)) == (K1 | K2)
+  // if K1 and K2 are a one-bit mask.
+  ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1));
+  ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS->getOperand(1));
+
+  // TODO support vector splats
+  if (LHS->getPredicate() == ICmpInst::ICMP_NE && LHSC && LHSC->isZero() &&
+      RHS->getPredicate() == ICmpInst::ICMP_NE && RHSC && RHSC->isZero()) {
+
+    Value *A, *B, *C, *D;
+    if (match(LHS->getOperand(0), m_And(m_Value(A), m_Value(B))) &&
+        match(RHS->getOperand(0), m_And(m_Value(C), m_Value(D)))) {
+      if (A == D || B == D)
+        std::swap(C, D);
+      if (B == C)
+        std::swap(A, B);
+
+      if (A == C &&
+          isKnownToBeAPowerOfTwo(B, false, 0, CxtI) &&
+          isKnownToBeAPowerOfTwo(D, false, 0, CxtI)) {
+        Value *Mask = Builder->CreateOr(B, D);
+        Value *Masked = Builder->CreateAnd(A, Mask);
+        return Builder->CreateICmp(ICmpInst::ICMP_EQ, Masked, Mask);
+      }
+    }
+  }
+
   // (icmp1 A, B) & (icmp2 A, B) --> (icmp3 A, B)
   if (PredicatesFoldable(PredL, PredR)) {
     if (LHS->getOperand(0) == RHS->getOperand(1) &&
         LHS->getOperand(1) == RHS->getOperand(0))
       LHS->swapOperands();
     if (LHS->getOperand(0) == RHS->getOperand(0) &&
         LHS->getOperand(1) == RHS->getOperand(1)) {
       Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
Value *InstCombiner::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS,
   if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/false))
     return V;
 
   if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, true, Builder))
     return V;
 
   // This only handles icmp of constants: (icmp1 A, C1) & (icmp2 B, C2).
   Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
-  ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1));
-  ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS->getOperand(1));
   if (!LHSC || !RHSC)
     return nullptr;
 
   if (LHSC == RHSC && PredL == PredR) {
     // (icmp ult A, C) & (icmp ult B, C) --> (icmp ult (A|B), C)
     // where C is a power of 2 or
     // (icmp eq A, 0) & (icmp eq B, 0) --> (icmp eq (A|B), 0)
     if ((PredL == ICmpInst::ICMP_ULT && LHSC->getValue().isPowerOf2()) ||
Instruction *InstCombiner::foldCastedBitwiseLogic(BinaryOperator &I) {
   if (LogicOpc == Instruction::Xor)
     return nullptr;
 
   // If this is logic(cast(icmp), cast(icmp)), try to fold this even if the
   // cast is otherwise not optimizable.  This happens for vector sexts.
   ICmpInst *ICmp0 = dyn_cast<ICmpInst>(Cast0Src);
   ICmpInst *ICmp1 = dyn_cast<ICmpInst>(Cast1Src);
   if (ICmp0 && ICmp1) {
-    Value *Res = LogicOpc == Instruction::And ? foldAndOfICmps(ICmp0, ICmp1)
+    Value *Res = LogicOpc == Instruction::And ? foldAndOfICmps(ICmp0, ICmp1, &I)
                                               : foldOrOfICmps(ICmp0, ICmp1, &I);
     if (Res)
       return CastInst::Create(CastOpcode, Res, DestTy);
     return nullptr;
   }
 
   // If this is logic(cast(fcmp), cast(fcmp)), try to fold this even if the
   // cast is otherwise not optimizable.  This happens for vector sexts.
if (match(Op0, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
         match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
       return BinaryOperator::CreateAnd(A, B);
   }
 
   {
     ICmpInst *LHS = dyn_cast<ICmpInst>(Op0);
     ICmpInst *RHS = dyn_cast<ICmpInst>(Op1);
     if (LHS && RHS)
-      if (Value *Res = foldAndOfICmps(LHS, RHS))
+      if (Value *Res = foldAndOfICmps(LHS, RHS, &I))
         return replaceInstUsesWith(I, Res);
 
     // TODO: Make this recursive; it's a little tricky because an arbitrary
     // number of 'and' instructions might have to be created.
     Value *X, *Y;
     if (LHS && match(Op1, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
       if (auto *Cmp = dyn_cast<ICmpInst>(X))
-        if (Value *Res = foldAndOfICmps(LHS, Cmp))
+        if (Value *Res = foldAndOfICmps(LHS, Cmp, &I))
           return replaceInstUsesWith(I, Builder->CreateAnd(Res, Y));
       if (auto *Cmp = dyn_cast<ICmpInst>(Y))
-        if (Value *Res = foldAndOfICmps(LHS, Cmp))
+        if (Value *Res = foldAndOfICmps(LHS, Cmp, &I))
           return replaceInstUsesWith(I, Builder->CreateAnd(Res, X));
     }
     if (RHS && match(Op0, m_OneUse(m_And(m_Value(X), m_Value(Y))))) {
       if (auto *Cmp = dyn_cast<ICmpInst>(X))
-        if (Value *Res = foldAndOfICmps(Cmp, RHS))
+        if (Value *Res = foldAndOfICmps(Cmp, RHS, &I))
           return replaceInstUsesWith(I, Builder->CreateAnd(Res, Y));
       if (auto *Cmp = dyn_cast<ICmpInst>(Y))
-        if (Value *Res = foldAndOfICmps(Cmp, RHS))
+        if (Value *Res = foldAndOfICmps(Cmp, RHS, &I))
           return replaceInstUsesWith(I, Builder->CreateAnd(Res, X));
     }
   }
 
   // If and'ing two fcmp, try combine them into one.
   if (FCmpInst *LHS = dyn_cast<FCmpInst>(I.getOperand(0)))
     if (FCmpInst *RHS = dyn_cast<FCmpInst>(I.getOperand(1)))
       if (Value *Res = foldAndOfFCmps(LHS, RHS))

lib/Transforms/InstCombine/InstCombineInternal.h

private:
   /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
   /// Instruction::CastOps value for a cast that can replace the pair, casting
   /// CI1->getSrcTy() to CI2->getDstTy().
   ///
   /// \see CastInst::isEliminableCastPair
   Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
                                             const CastInst *CI2);
 
-  Value *foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS);
+  Value *foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction *CxtI);
   Value *foldAndOfFCmps(FCmpInst *LHS, FCmpInst *RHS);
   Value *foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction *CxtI);
   Value *foldOrOfFCmps(FCmpInst *LHS, FCmpInst *RHS);
   Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS);
 
 public:
   /// \brief Inserts an instruction \p New before instruction \p Old
   ///

test/Transforms/InstCombine/onehot_merge.ll

;
   %tmp1 = and i32 %k2, %tmp
   %tmp2 = icmp eq i32 %tmp1, 0
   %tmp5 = and i32 %tmp4, %k2
   %tmp6 = icmp eq i32 %tmp5, 0
   %or = or i1 %tmp2, %tmp6
   ret i1 %or
 }
 
+define i1 @or_consts(i32 %k, i32 %c1, i32 %c2) {
+; CHECK-LABEL: @or_consts(
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[K:%.*]], 12
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 12
+; CHECK-NEXT:    ret i1 [[TMP2]]
+;
+  %tmp1 = and i32 4, %k
+  %tmp2 = icmp ne i32 %tmp1, 0
+  %tmp5 = and i32 8, %k
+  %tmp6 = icmp ne i32 %tmp5, 0
+  %or = and i1 %tmp2, %tmp6
+  ret i1 %or
+}
+
+define i1 @foo1_or(i32 %k, i32 %c1, i32 %c2) {
+; CHECK-LABEL: @foo1_or(
+; CHECK-NEXT:    [[TMP:%.*]] = shl i32 1, [[C1:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = lshr i32 -2147483648, [[C2:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[TMP]], [[TMP4]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[K:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP3]]
+;
+  %tmp = shl i32 1, %c1
+  %tmp4 = lshr i32 -2147483648, %c2
+  %tmp1 = and i32 %tmp, %k
+  %tmp2 = icmp ne i32 %tmp1, 0
+  %tmp5 = and i32 %tmp4, %k
+  %tmp6 = icmp ne i32 %tmp5, 0
+  %or = and i1 %tmp2, %tmp6
+  ret i1 %or
+}
+
+; Same as above but with operands commuted one of the ors, but not the other.
+define i1 @foo1_or_commuted(i32 %k, i32 %c1, i32 %c2) {
+; CHECK-LABEL: @foo1_or_commuted(
+; CHECK-NEXT:    [[K2:%.*]] = mul i32 [[K:%.*]], [[K]]
+; CHECK-NEXT:    [[TMP:%.*]] = shl i32 1, [[C1:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = lshr i32 -2147483648, [[C2:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[TMP]], [[TMP4]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[K2]], [[TMP1]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP3]]
+;
+  %k2 = mul i32 %k, %k ; to trick the complexity sorting
+  %tmp = shl i32 1, %c1
+  %tmp4 = lshr i32 -2147483648, %c2
+  %tmp1 = and i32 %k2, %tmp
+  %tmp2 = icmp ne i32 %tmp1, 0
+  %tmp5 = and i32 %tmp4, %k2
+  %tmp6 = icmp ne i32 %tmp5, 0
+  %or = and i1 %tmp2, %tmp6
+  ret i1 %or
+}