[InstCombine,InstSimplify] Optimize select followed by and/or/xor

[aqjune]

Summary

This patch adds A & (A && B) -> A && B (similarly for or + logical or)

Also, this patch adds ~(select C, (icmp pred X, Y), const) -> select C, (icmp pred' X, Y), ~const.

Alive2 proof:
merge_and: https://alive2.llvm.org/ce/z/teMR97
merge_or: https://alive2.llvm.org/ce/z/b4yZUp
xor_and: https://alive2.llvm.org/ce/z/_-TXHi
xor_or: https://alive2.llvm.org/ce/z/2uYx_a

[aqjune]

After applying D94859 + D94860 + this patch, the diff looks like this:
https://gist.github.com/aqjune/39bcc99bf7339bef74652597c9e57122 (@nikic thanks for creating the _logical functions!)
I think the majority of sound transformations are now supported.

A few missing cases:

 define i1 @test7_logical(i32 %i, i1 %b) {
 ; CHECK-LABEL: @test7_logical(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[I:%.*]], 0
-; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[TMP1]], [[B:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[I:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[I]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = select i1 [[CMP1]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    [[AND2:%.*]] = and i1 [[AND1]], [[CMP2]]
+; CHECK-NEXT:    ret i1 [[AND2]]
 ;
   %cmp1 = icmp slt i32 %i, 1
   %cmp2 = icmp sgt i32 %i, -1

as well as llvm.umul.with.overflow.i64 , llvm.ctpop.i32 .

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3463

I find the conditions here hard to understand. Can we write it like this?

bool InvertibleT = (CmpT && CmptT->hasOneUse()) || isa<ConstantInt>(TV);
bool InvertibleF = (CmpF && CmptF->hasOneUse()) || isa<ConstantInt>(FV);
if (InvertibleT && InvertibleF)

This does not explicitly exclude the ? true : false case, but that shouldn't be a problem.

Though checking for isa<Constant> here means that this transform will not work for vectors I think. It would be good to add a test for that and use a more general predicate.

[aqjune]

Address the comment

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3469

You can use ConstantExpr::getNot() instead.

[aqjune]

Use ConstantExpr::getNot

llvm/lib/Analysis/InstructionSimplify.cpp

if (Value *V = expandCommutativeBinOp(Instruction::And, Op0, Op1,
                                         Instruction::Or, Q, MaxRecurse))
     return V;
 
   // And distributes over Xor.  Try some generic simplifications based on this.
   if (Value *V = expandCommutativeBinOp(Instruction::And, Op0, Op1,
                                         Instruction::Xor, Q, MaxRecurse))
     return V;
 
-  // If the operation is with the result of a select instruction, check whether
-  // operating on either branch of the select always yields the same value.
-  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
+  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) {
+    if (Op0->getType()->isIntOrIntVectorTy(1)) {
+      // A & (A && B) -> A && B
+      if (match(Op1, m_Select(m_Specific(Op0), m_Value(), m_Zero())))
+        return Op1;
+      else if (match(Op0, m_Select(m_Specific(Op1), m_Value(), m_Zero())))
+        return Op0;
+    }
+    // If the operation is with the result of a select instruction, check
+    // whether operating on either branch of the select always yields the same
+    // value.
     if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, Q,
                                          MaxRecurse))
       return V;
+  }
 
   // If the operation is with the result of a phi instruction, check whether
   // operating on all incoming values of the phi always yields the same value.
   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
     if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, Q,
                                       MaxRecurse))
       return V;
 
if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q,
                                           MaxRecurse))
     return V;
 
   // Or distributes over And.  Try some generic simplifications based on this.
   if (Value *V = expandCommutativeBinOp(Instruction::Or, Op0, Op1,
                                         Instruction::And, Q, MaxRecurse))
     return V;
 
-  // If the operation is with the result of a select instruction, check whether
-  // operating on either branch of the select always yields the same value.
-  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
+  if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) {
+    if (Op0->getType()->isIntOrIntVectorTy(1)) {
+      // A | (A || B) -> A || B
+      if (match(Op1, m_Select(m_Specific(Op0), m_One(), m_Value())))
+        return Op1;
+      else if (match(Op0, m_Select(m_Specific(Op1), m_One(), m_Value())))
+        return Op0;
+    }
+    // If the operation is with the result of a select instruction, check
+    // whether operating on either branch of the select always yields the same
+    // value.
     if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q,
                                          MaxRecurse))
       return V;
+  }
 
   // (A & C1)|(B & C2)
   const APInt *C1, *C2;
   if (match(Op0, m_And(m_Value(A), m_APInt(C1))) &&
       match(Op1, m_And(m_Value(B), m_APInt(C2)))) {
     if (*C1 == ~*C2) {
       // (A & C1)|(B & C2)
       // If we have: ((V + N) & C1) | (V & C2)

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (SelectPatternResult::isMinOrMax(SPF)) {
         Value *NotLHS = Builder.CreateNot(LHS);
         Value *NotRHS = Builder.CreateNot(RHS);
         return SelectInst::Create(
             Builder.CreateICmp(getInverseMinMaxPred(SPF), NotLHS, NotRHS),
             NotLHS, NotRHS);
       }
     }
 
-    // Pull 'not' into operands of select if both operands are one-use compares.
+    // Pull 'not' into operands of select if both operands are one-use compares
+    // or one is one-use compare and the other one is a constant.
     // Inverting the predicates eliminates the 'not' operation.
     // Example:
-    //     not (select ?, (cmp TPred, ?, ?), (cmp FPred, ?, ?) -->
+    //   not (select ?, (cmp TPred, ?, ?), (cmp FPred, ?, ?) -->
     //     select ?, (cmp InvTPred, ?, ?), (cmp InvFPred, ?, ?)
-    // TODO: Canonicalize by hoisting 'not' into an arm of the select if only
-    //       1 select operand is a cmp?
+    //   not (select ?, (cmp TPred, ?, ?), true -->
+    //     select ?, (cmp InvTPred, ?, ?), false
     if (auto *Sel = dyn_cast<SelectInst>(Op0)) {
-      auto *CmpT = dyn_cast<CmpInst>(Sel->getTrueValue());
-      auto *CmpF = dyn_cast<CmpInst>(Sel->getFalseValue());
-      if (CmpT && CmpF && CmpT->hasOneUse() && CmpF->hasOneUse()) {
+      Value *TV = Sel->getTrueValue();
+      Value *FV = Sel->getFalseValue();
+      auto *CmpT = dyn_cast<CmpInst>(TV);
+      auto *CmpF = dyn_cast<CmpInst>(FV);
+      bool InvertibleT = (CmpT && CmpT->hasOneUse()) || isa<Constant>(TV);
+      bool InvertibleF = (CmpF && CmpF->hasOneUse()) || isa<Constant>(FV);
+      if (InvertibleT && InvertibleF) {
+        Constant *One = cast<Constant>(Op1);
+
+        if (CmpT)
           CmpT->setPredicate(CmpT->getInversePredicate());
+        else
+          Sel->setTrueValue(ConstantExpr::getNot(cast<Constant>(TV)));
+        if (CmpF)
           CmpF->setPredicate(CmpF->getInversePredicate());
+        else
+          Sel->setFalseValue(ConstantExpr::getNot(cast<Constant>(FV)));
         return replaceInstUsesWith(I, Sel);
       }
     }
   }
 
   if (Instruction *NewXor = sinkNotIntoXor(I, Builder))
     return NewXor;
 

llvm/test/Transforms/InstCombine/select-safe-transforms.ll

;
   %lhs = icmp ult i8 %X, %Y
   %res = select i1 %cond, i1 true, i1 %lhs
   ret i1 %res
 }
 
 define i1 @merge_and(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_and(
 ; CHECK-NEXT:    [[C:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 false
-; CHECK-NEXT:    [[RES:%.*]] = and i1 [[C]], [[X]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[C]]
 ;
   %c = select i1 %X, i1 %Y, i1 false
   %res = and i1 %X, %c
   ret i1 %res
 }
 
 define i1 @merge_or(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_or(
 ; CHECK-NEXT:    [[C:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = or i1 [[C]], [[X]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[C]]
 ;
   %c = select i1 %X, i1 true, i1 %Y
   %res = or i1 %X, %c
   ret i1 %res
 }
 
 define i1 @xor_and(i1 %c, i32 %X, i32 %Y) {
 ; CHECK-LABEL: @xor_and(
-; CHECK-NEXT:    [[COMP:%.*]] = icmp ult i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C:%.*]], i1 [[COMP]], i1 false
-; CHECK-NEXT:    [[RES:%.*]] = xor i1 [[SEL]], true
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    [[COMP:%.*]] = icmp uge i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[NOT_C:%.*]] = xor i1 [[C:%.*]], true
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[NOT_C]], i1 true, i1 [[COMP]]
+; CHECK-NEXT:    ret i1 [[SEL]]
 ;
   %comp = icmp ult i32 %X, %Y
   %sel = select i1 %c, i1 %comp, i1 false
   %res = xor i1 %sel, true
   ret i1 %res
 }
 
 define <2 x i1> @xor_and2(<2 x i1> %c, <2 x i32> %X, <2 x i32> %Y) {
 ; CHECK-LABEL: @xor_and2(
-; CHECK-NEXT:    [[COMP:%.*]] = icmp ult <2 x i32> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select <2 x i1> [[C:%.*]], <2 x i1> [[COMP]], <2 x i1> <i1 true, i1 false>
-; CHECK-NEXT:    [[RES:%.*]] = xor <2 x i1> [[SEL]], <i1 true, i1 true>
-; CHECK-NEXT:    ret <2 x i1> [[RES]]
+; CHECK-NEXT:    [[COMP:%.*]] = icmp uge <2 x i32> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[SEL:%.*]] = select <2 x i1> [[C:%.*]], <2 x i1> [[COMP]], <2 x i1> <i1 false, i1 true>
+; CHECK-NEXT:    ret <2 x i1> [[SEL]]
 ;
   %comp = icmp ult <2 x i32> %X, %Y
   %sel = select <2 x i1> %c, <2 x i1> %comp, <2 x i1> <i1 true, i1 false>
   %res = xor <2 x i1> %sel, <i1 true, i1 true>
   ret <2 x i1> %res
 }
 
 @glb = global i8 0
 
 define <2 x i1> @xor_and3(<2 x i1> %c, <2 x i32> %X, <2 x i32> %Y) {
 ; CHECK-LABEL: @xor_and3(
-; CHECK-NEXT:    [[COMP:%.*]] = icmp ult <2 x i32> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select <2 x i1> [[C:%.*]], <2 x i1> [[COMP]], <2 x i1> <i1 icmp eq (i8* inttoptr (i64 1234 to i8*), i8* @glb), i1 false>
-; CHECK-NEXT:    [[RES:%.*]] = xor <2 x i1> [[SEL]], <i1 true, i1 true>
-; CHECK-NEXT:    ret <2 x i1> [[RES]]
+; CHECK-NEXT:    [[COMP:%.*]] = icmp uge <2 x i32> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[SEL:%.*]] = select <2 x i1> [[C:%.*]], <2 x i1> [[COMP]], <2 x i1> <i1 icmp ne (i8* inttoptr (i64 1234 to i8*), i8* @glb), i1 true>
+; CHECK-NEXT:    ret <2 x i1> [[SEL]]
 ;
   %comp = icmp ult <2 x i32> %X, %Y
   %sel = select <2 x i1> %c, <2 x i1> %comp, <2 x i1> <i1 icmp eq (i8* @glb, i8* inttoptr (i64 1234 to i8*)), i1 false>
   %res = xor <2 x i1> %sel, <i1 true, i1 true>
   ret <2 x i1> %res
 }
 
 define i1 @xor_or(i1 %c, i32 %X, i32 %Y) {
 ; CHECK-LABEL: @xor_or(
-; CHECK-NEXT:    [[COMP:%.*]] = icmp ult i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C:%.*]], i1 true, i1 [[COMP]]
-; CHECK-NEXT:    [[RES:%.*]] = xor i1 [[SEL]], true
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    [[COMP:%.*]] = icmp uge i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[NOT_C:%.*]] = xor i1 [[C:%.*]], true
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[NOT_C]], i1 [[COMP]], i1 false
+; CHECK-NEXT:    ret i1 [[SEL]]
 ;
   %comp = icmp ult i32 %X, %Y
   %sel = select i1 %c, i1 true, i1 %comp
   %res = xor i1 %sel, true
   ret i1 %res
 }
 
 define <2 x i1> @xor_or2(<2 x i1> %c, <2 x i32> %X, <2 x i32> %Y) {
 ; CHECK-LABEL: @xor_or2(
-; CHECK-NEXT:    [[COMP:%.*]] = icmp ult <2 x i32> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select <2 x i1> [[C:%.*]], <2 x i1> <i1 true, i1 false>, <2 x i1> [[COMP]]
-; CHECK-NEXT:    [[RES:%.*]] = xor <2 x i1> [[SEL]], <i1 true, i1 true>
-; CHECK-NEXT:    ret <2 x i1> [[RES]]
+; CHECK-NEXT:    [[COMP:%.*]] = icmp uge <2 x i32> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[SEL:%.*]] = select <2 x i1> [[C:%.*]], <2 x i1> <i1 false, i1 true>, <2 x i1> [[COMP]]
+; CHECK-NEXT:    ret <2 x i1> [[SEL]]
 ;
   %comp = icmp ult <2 x i32> %X, %Y
   %sel = select <2 x i1> %c, <2 x i1> <i1 true, i1 false>, <2 x i1> %comp
   %res = xor <2 x i1> %sel, <i1 true, i1 true>
   ret <2 x i1> %res
 }
 
 define <2 x i1> @xor_or3(<2 x i1> %c, <2 x i32> %X, <2 x i32> %Y) {
 ; CHECK-LABEL: @xor_or3(
-; CHECK-NEXT:    [[COMP:%.*]] = icmp ult <2 x i32> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[SEL:%.*]] = select <2 x i1> [[C:%.*]], <2 x i1> <i1 icmp eq (i8* inttoptr (i64 1234 to i8*), i8* @glb), i1 false>, <2 x i1> [[COMP]]
-; CHECK-NEXT:    [[RES:%.*]] = xor <2 x i1> [[SEL]], <i1 true, i1 true>
-; CHECK-NEXT:    ret <2 x i1> [[RES]]
+; CHECK-NEXT:    [[COMP:%.*]] = icmp uge <2 x i32> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[SEL:%.*]] = select <2 x i1> [[C:%.*]], <2 x i1> <i1 icmp ne (i8* inttoptr (i64 1234 to i8*), i8* @glb), i1 true>, <2 x i1> [[COMP]]
+; CHECK-NEXT:    ret <2 x i1> [[SEL]]
 ;
   %comp = icmp ult <2 x i32> %X, %Y
   %sel = select <2 x i1> %c, <2 x i1> <i1 icmp eq (i8* @glb, i8* inttoptr (i64 1234 to i8*)), i1 false>, <2 x i1> %comp
   %res = xor <2 x i1> %sel, <i1 true, i1 true>
   ret <2 x i1> %res
 }