[Instcombine] fold logic ops to select

[bcl5980]

Summary

(C & X) | ~(C | Y) -> C ? X : ~Y

https://alive2.llvm.org/ce/z/4yLh_i

[bcl5980]

code rebase

[bcl5980]

rebase code after precommit

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2479–2481

Rename AisB ? It seems to suggest that A is known to be equivalent to B.

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

367–369

Explain the purposes of NeedNotD and AisB

[bcl5980]

address comments.

[bcl5980]

Ping.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2973–2974

This is more general than needed. Complexity canonicalization guarantees that the 'not' is operand 1.

We could also check for the common operand out here for efficiency?

if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
    match(Op1, m_Not(m_Or(m_Value(B), m_Value(D)))) &&
    hasCommonOperand(A, C, B, D) && (Op0->hasOneUse() || Op1->hasOneUse())) {

[bcl5980]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2973–2974

If we use hasCommonOperand we needn't call matchSelectFromAndOr I think.
matchSelectFromAndOr will peek through the bitcast. And getSelectCondition consider more about the pattern with constant. For now I haven't add the support of these complex patterns. But maybe we can add them in the future. So I prefer to reuse the current code.

[bcl5980]

rebase code

[spatel]

LGTM - see inline comment for a minor adjustment.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2565

The name "SelectNotFalseVal" is confusing to me. I would prefer to name this "InvertFalseVal". Then adjust the code comment above to say:

/// When InvertFalseVal is set to true, we try to match the pattern
/// where we have peeked through a 'not' op and A and B are the same:
/// (A & C) | ~(A | D) --> (A & C) | (~A & ~D) --> A' ? C : ~D

[bcl5980]

address comments.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (!((match(EltC1, m_Zero()) && match(EltC2, m_AllOnes())) ||
       return false;
   }
   return true;
 }
 
 /// We have an expression of the form (A & C) | (B & D). If A is a scalar or
 /// vector composed of all-zeros or all-ones values and is the bitwise 'not' of
 /// B, it can be used as the condition operand of a select instruction.
-Value *InstCombinerImpl::getSelectCondition(Value *A, Value *B) {
+/// We will detect (A & C) | ~(B | D) when the flag ABIsTheSame enabled.
+Value *InstCombinerImpl::getSelectCondition(Value *A, Value *B,
+                                            bool ABIsTheSame) {
   // We may have peeked through bitcasts in the caller.
   // Exit immediately if we don't have (vector) integer types.
   Type *Ty = A->getType();
   if (!Ty->isIntOrIntVectorTy() || !B->getType()->isIntOrIntVectorTy())
     return nullptr;
 
   // If A is the 'not' operand of B and has enough signbits, we have our answer.
-  if (match(B, m_Not(m_Specific(A)))) {
+  if (ABIsTheSame ? (A == B) : match(B, m_Not(m_Specific(A)))) {
     // If these are scalars or vectors of i1, A can be used directly.
     if (Ty->isIntOrIntVectorTy(1))
       return A;
 
     // If we look through a vector bitcast, the caller will bitcast the operands
     // to match the condition's number of bits (N x i1).
     // To make this poison-safe, disallow bitcast from wide element to narrow
     // element. That could allow poison in lanes where it was not present in the
     // original code.
     A = peekThroughBitcast(A);
     if (A->getType()->isIntOrIntVectorTy()) {
       unsigned NumSignBits = ComputeNumSignBits(A);
       if (NumSignBits == A->getType()->getScalarSizeInBits() &&
           NumSignBits <= Ty->getScalarSizeInBits())
         return Builder.CreateTrunc(A, CmpInst::makeCmpResultType(A->getType()));
     }
     return nullptr;
   }
 
+  // TODO: add support for sext and constant case
+  if (ABIsTheSame)
+    return nullptr;
+
   // If both operands are constants, see if the constants are inverse bitmasks.
   Constant *AConst, *BConst;
   if (match(A, m_Constant(AConst)) && match(B, m_Constant(BConst)))
     if (AConst == ConstantExpr::getNot(BConst) &&
         ComputeNumSignBits(A) == Ty->getScalarSizeInBits())
       return Builder.CreateZExtOrTrunc(A, CmpInst::makeCmpResultType(Ty));
 
   // Look for more complex patterns. The 'not' op may be hidden behind various
if (match(A, (m_Xor(m_SExt(m_Value(Cond)), m_Constant(AConst)))) &&
     AConst = ConstantExpr::getTrunc(AConst, CmpInst::makeCmpResultType(Ty));
     return Builder.CreateXor(Cond, AConst);
   }
   return nullptr;
 }
 
 /// We have an expression of the form (A & C) | (B & D). Try to simplify this
 /// to "A' ? C : D", where A' is a boolean or vector of booleans.
+/// When SelectNotFalseVal set to true, we will match the pattern:
+/// (C && X) || ~(C || Y) --> C ? X : (~Y)
 Value *InstCombinerImpl::matchSelectFromAndOr(Value *A, Value *C, Value *B,
-                                              Value *D) {
+                                              Value *D,
+                                              bool SelectNotFalseVal) {
   // The potential condition of the select may be bitcasted. In that case, look
   // through its bitcast and the corresponding bitcast of the 'not' condition.
   Type *OrigType = A->getType();
   A = peekThroughBitcast(A, true);
   B = peekThroughBitcast(B, true);
-  if (Value *Cond = getSelectCondition(A, B)) {
+  if (Value *Cond = getSelectCondition(A, B, SelectNotFalseVal)) {
     // ((bc Cond) & C) | ((bc ~Cond) & D) --> bc (select Cond, (bc C), (bc D))
     // If this is a vector, we may need to cast to match the condition's length.
     // The bitcasts will either all exist or all not exist. The builder will
     // not create unnecessary casts if the types already match.
     Type *SelTy = A->getType();
     if (auto *VecTy = dyn_cast<VectorType>(Cond->getType())) {
       // For a fixed or scalable vector get N from <{vscale x} N x iM>
       unsigned Elts = VecTy->getElementCount().getKnownMinValue();
       // For a fixed or scalable vector, get the size in bits of N x iM; for a
       // scalar this is just M.
       unsigned SelEltSize = SelTy->getPrimitiveSizeInBits().getKnownMinSize();
       Type *EltTy = Builder.getIntNTy(SelEltSize / Elts);
       SelTy = VectorType::get(EltTy, VecTy->getElementCount());
     }
     Value *BitcastC = Builder.CreateBitCast(C, SelTy);
+    if (SelectNotFalseVal)
+      D = Builder.CreateNot(D);
     Value *BitcastD = Builder.CreateBitCast(D, SelTy);
     Value *Select = Builder.CreateSelect(Cond, BitcastC, BitcastD);
     return Builder.CreateBitCast(Select, OrigType);
   }
 
   return nullptr;
 }
 
if (Op0->hasOneUse() || Op1->hasOneUse()) {
         return replaceInstUsesWith(I, V);
       if (Value *V = matchSelectFromAndOr(D, B, A, C))
         return replaceInstUsesWith(I, V);
       if (Value *V = matchSelectFromAndOr(D, B, C, A))
         return replaceInstUsesWith(I, V);
     }
   }
 
+  if (match(&I, m_c_BinOp(m_And(m_Value(A), m_Value(C)),
+                          m_Not(m_Or(m_Value(B), m_Value(D)))))) {
+    if (Op0->hasOneUse() || Op1->hasOneUse()) {
+      // (Cond & C) | ~(Cond | D) -> Cond ? C : ~D
+      if (Value *V = matchSelectFromAndOr(A, C, B, D, true))
+        return replaceInstUsesWith(I, V);
+      if (Value *V = matchSelectFromAndOr(A, C, D, B, true))
+        return replaceInstUsesWith(I, V);
+      if (Value *V = matchSelectFromAndOr(C, A, B, D, true))
+        return replaceInstUsesWith(I, V);
+      if (Value *V = matchSelectFromAndOr(C, A, D, B, true))
+        return replaceInstUsesWith(I, V);
+    }
+  }
+
   // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
   if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
     if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
       return BinaryOperator::CreateOr(Op0, C);
 
   // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C
   if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
     if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

private:
   /// NOTE: Unlike most of instcombine, this returns a Value which should
   /// already be inserted into the function.
   Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd,
                           bool IsLogicalSelect = false);
 
   Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
                                        Instruction *CxtI, bool IsAnd,
                                        bool IsLogical = false);
-  Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D);
-  Value *getSelectCondition(Value *A, Value *B);
+  Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D,
+                              bool SelectNotFalseVal = false);
+  Value *getSelectCondition(Value *A, Value *B, bool ABIsTheSame);
 
   Instruction *foldExtractOfOverflowIntrinsic(ExtractValueInst &EV);
   Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
   Instruction *foldFPSignBitOps(BinaryOperator &I);
   Instruction *foldFDivConstantDivisor(BinaryOperator &I);
 
   // Optimize one of these forms:
   //   and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)

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

;
   %or = select <2 x i1> %y, <2 x i1> <i1 true, i1 true>, <2 x i1> %x
   %nand = xor <2 x i1> %and, <i1 true, i1 true>
   %and2 = select <2 x i1> %or, <2 x i1> %nand, <2 x i1> <i1 false, i1 false>
   ret <2 x i1> %and2
 }
 
 define i1 @not_d_bools_commute00(i1 %c, i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_d_bools_commute00(
-; CHECK-NEXT:    [[Y_C:%.*]] = or i1 [[C:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = xor i1 [[Y_C]], true
-; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[C]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[AND1]], [[AND2]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[Y:%.*]], true
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[C:%.*]], i1 [[X:%.*]], i1 [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %y_c = or i1 %c, %y
   %and2 = xor i1 %y_c, true
   %and1 = and i1 %c, %x
   %r = or i1 %and1, %and2
   ret i1 %r
 }
 
 define i1 @not_d_bools_commute01(i1 %c, i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_d_bools_commute01(
-; CHECK-NEXT:    [[Y_C:%.*]] = or i1 [[Y:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = xor i1 [[Y_C]], true
-; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[C]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[AND1]], [[AND2]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[Y:%.*]], true
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[C:%.*]], i1 [[X:%.*]], i1 [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %y_c = or i1 %y, %c
   %and2 = xor i1 %y_c, true
   %and1 = and i1 %c, %x
   %r = or i1 %and1, %and2
   ret i1 %r
 }
 
 define i1 @not_d_bools_commute10(i1 %c, i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_d_bools_commute10(
-; CHECK-NEXT:    [[Y_C:%.*]] = or i1 [[C:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = xor i1 [[Y_C]], true
-; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[X:%.*]], [[C]]
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[AND1]], [[AND2]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[Y:%.*]], true
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[C:%.*]], i1 [[X:%.*]], i1 [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %y_c = or i1 %c, %y
   %and2 = xor i1 %y_c, true
   %and1 = and i1 %x, %c
   %r = or i1 %and1, %and2
   ret i1 %r
 }
 
 define i1 @not_d_bools_commute11(i1 %c, i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_d_bools_commute11(
-; CHECK-NEXT:    [[Y_C:%.*]] = or i1 [[Y:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = xor i1 [[Y_C]], true
-; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[X:%.*]], [[C]]
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[AND1]], [[AND2]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[Y:%.*]], true
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[C:%.*]], i1 [[X:%.*]], i1 [[TMP1]]
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %y_c = or i1 %y, %c
   %and2 = xor i1 %y_c, true
   %and1 = and i1 %x, %c
   %r = or i1 %and1, %and2
   ret i1 %r
 }
 
 define <2 x i1> @not_d_bools_vector(<2 x i1> %c, <2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @not_d_bools_vector(
-; CHECK-NEXT:    [[Y_C:%.*]] = or <2 x i1> [[Y:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = xor <2 x i1> [[Y_C]], <i1 true, i1 true>
-; CHECK-NEXT:    [[AND1:%.*]] = and <2 x i1> [[X:%.*]], [[C]]
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i1> [[AND1]], [[AND2]]
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i1> [[Y:%.*]], <i1 true, i1 true>
+; CHECK-NEXT:    [[TMP2:%.*]] = select <2 x i1> [[C:%.*]], <2 x i1> [[X:%.*]], <2 x i1> [[TMP1]]
+; CHECK-NEXT:    ret <2 x i1> [[TMP2]]
 ;
   %y_c = or <2 x i1> %y, %c
   %and2 = xor <2 x i1> %y_c, <i1 true, i1 true>
   %and1 = and <2 x i1> %x, %c
   %r = or <2 x i1> %and1, %and2
   ret <2 x i1> %r
 }
 
 define <2 x i1> @not_d_bools_vector_poison(<2 x i1> %c, <2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @not_d_bools_vector_poison(
-; CHECK-NEXT:    [[Y_C:%.*]] = or <2 x i1> [[Y:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = xor <2 x i1> [[Y_C]], <i1 poison, i1 true>
-; CHECK-NEXT:    [[AND1:%.*]] = and <2 x i1> [[X:%.*]], [[C]]
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i1> [[AND1]], [[AND2]]
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i1> [[Y:%.*]], <i1 true, i1 true>
+; CHECK-NEXT:    [[TMP2:%.*]] = select <2 x i1> [[C:%.*]], <2 x i1> [[X:%.*]], <2 x i1> [[TMP1]]
+; CHECK-NEXT:    ret <2 x i1> [[TMP2]]
 ;
   %y_c = or <2 x i1> %y, %c
   %and2 = xor <2 x i1> %y_c, <i1 poison, i1 true>
   %and1 = and <2 x i1> %x, %c
   %r = or <2 x i1> %and1, %and2
   ret <2 x i1> %r
 }
 
 define i32 @not_d_allSignBits(i32 %cond, i32 %tval, i32 %fval) {
 ; CHECK-LABEL: @not_d_allSignBits(
-; CHECK-NEXT:    [[BITMASK:%.*]] = ashr i32 [[COND:%.*]], 31
-; CHECK-NEXT:    [[A1:%.*]] = and i32 [[BITMASK]], [[TVAL:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[BITMASK]], [[FVAL:%.*]]
-; CHECK-NEXT:    [[A2:%.*]] = xor i32 [[OR]], -1
-; CHECK-NEXT:    [[SEL:%.*]] = or i32 [[A1]], [[A2]]
-; CHECK-NEXT:    ret i32 [[SEL]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[FVAL:%.*]], -1
+; CHECK-NEXT:    [[DOTNOT2:%.*]] = icmp slt i32 [[COND:%.*]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[DOTNOT2]], i32 [[TVAL:%.*]], i32 [[TMP1]]
+; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %bitmask = ashr i32 %cond, 31
   %a1 = and i32 %tval, %bitmask
   %or = or i32 %bitmask, %fval
   %a2 = xor i32 %or, -1
   %sel = or i32 %a1, %a2
   ret i32 %sel
 }
 
 define i1 @not_d_bools_use2(i1 %c, i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_d_bools_use2(
 ; CHECK-NEXT:    [[Y_C:%.*]] = or i1 [[C:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = xor i1 [[Y_C]], true
 ; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[C]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[AND1]], [[AND2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[Y]], true
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[C]], i1 [[X]], i1 [[TMP1]]
 ; CHECK-NEXT:    call void @use1(i1 [[AND1]])
 ; CHECK-NEXT:    call void @use1(i1 [[Y_C]])
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %y_c = or i1 %c, %y
   %and2 = xor i1 %y_c, true
   %and1 = and i1 %c, %x
   %r = or i1 %and1, %and2
   call void @use1(i1 %and1)
   call void @use1(i1 %y_c)
   ret i1 %r
 }
 
+; negative test: both op is not one-use
+
 define i1 @not_d_bools_negative_use2(i1 %c, i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_d_bools_negative_use2(
 ; CHECK-NEXT:    [[Y_C:%.*]] = or i1 [[C:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[AND2:%.*]] = xor i1 [[Y_C]], true
 ; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[C]], [[X:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = or i1 [[AND1]], [[AND2]]
 ; CHECK-NEXT:    call void @use1(i1 [[AND2]])
 ; CHECK-NEXT:    call void @use1(i1 [[AND1]])