[InstCombine][WIP] Don't canonicalize select of bools if it costs an instruction

[goldstein.w.n]

Summary

Proofs for new transforms: https://alive2.llvm.org/ce/z/j9o0D3

We current canonicalize true to the TrueVal operand and false to
the FalseVal operand in selects. This makes recognizing LogicalAnd /
LogicalOr patterns easier but often costs an instruction.

[goldstein.w.n]

Rebase

[nikic]

I don't think we can do this. Logical and/or is a canonical form that lots of passes rely on, not just InstCombine. We would have to teach all passes that use LogicalAnd/LogicalOr matchers to also support the inverted forms. I don't think that would be worthwhile.

[goldstein.w.n]

In D159328#4645746, @nikic wrote:

I don't think we can do this. Logical and/or is a canonical form that lots of passes rely on, not just InstCombine. We would have to teach all passes that use LogicalAnd/LogicalOr matchers to also support the inverted forms. I don't think that would be worthwhile.

In D159328#4645746, @nikic wrote:

I don't think we can do this. Logical and/or is a canonical form that lots of passes rely on, not just InstCombine. We would have to teach all passes that use LogicalAnd/LogicalOr matchers to also support the inverted forms. I don't think that would be worthwhile.

I'm happy to drop this. It was mostly motivated by wanting to fix the regression caused by expanding isFreeToInvert.
I'll see if there is another better way to go about it.

[goldstein.w.n]

Abandoning and resubmitting on GH

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

Value *getOrCreateValue(InstCombiner::BuilderTy &Builder) const {
         return OrigCmp_;
       return Builder.CreateCmp(Pred_, Op0_, Op1_);
     }
 
     CmpComponents() = default;
     CmpComponents(CmpType *Cmp)
         : Pred_(Cmp->getPredicate()), Op0_(Cmp->getOperand(0)),
           Op1_(Cmp->getOperand(1)), OrigCmp_(Cmp) {}
+    CmpComponents(PredType Pred, Value *Op0, Value *Op1, CmpType *Cmp)
+        : Pred_(Pred), Op0_(Op0), Op1_(Op1), OrigCmp_(Cmp) {}
   };
 
   using FCmpComponents = CmpComponents<FCmpInst>;
   using ICmpComponents = CmpComponents<ICmpInst>;
 
   Value *simplifyRangeCheck(ICmpComponents Cmp0, ICmpComponents Cmp1,
                             bool Inverted);
 

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

Value *SelInner = Builder.CreateSelect(
       AltCond, IsAndVariant ? OuterSel.TrueVal : InnerSel.FalseVal,
       IsAndVariant ? InnerSel.TrueVal : OuterSel.FalseVal);
   SelInner->takeName(InnerSelVal);
   return SelectInst::Create(InnerSel.Cond,
                             IsAndVariant ? SelInner : InnerSel.TrueVal,
                             !IsAndVariant ? SelInner : InnerSel.FalseVal);
 }
 
+static bool canFreelyInvert(InstCombiner &IC, Value *Op,
+                            Instruction *IgnoredUser = nullptr) {
+  auto *I = dyn_cast<Instruction>(Op);
+  return I && IC.isFreeToInvert(I, /*WillInvertAllUses=*/true) &&
+         InstCombiner::canFreelyInvertAllUsersOf(I, IgnoredUser);
+}
+
+static Value *freelyInvert(InstCombinerImpl &IC, Value *Op,
+                           Instruction *IgnoredUser) {
+  auto *I = cast<Instruction>(Op);
+  IC.Builder.SetInsertPoint(&*I->getInsertionPointAfterDef());
+  Value *NotOp = IC.Builder.CreateNot(Op, Op->getName() + ".not");
+  Op->replaceUsesWithIf(NotOp,
+                        [NotOp](Use &U) { return U.getUser() != NotOp; });
+  IC.freelyInvertAllUsersOf(NotOp, IgnoredUser);
+  return NotOp;
+}
+
 Instruction *InstCombinerImpl::foldSelectOfBools(SelectInst &SI) {
   Value *CondVal = SI.getCondition();
   Value *TrueVal = SI.getTrueValue();
   Value *FalseVal = SI.getFalseValue();
   Type *SelType = SI.getType();
 
   // Avoid potential infinite loops by checking for non-constant condition.
   // TODO: Can we assert instead by improving canonicalizeSelectToShuffle()?
   //       Scalar select must have simplified?
   if (!SelType->isIntOrIntVectorTy(1) || isa<Constant>(CondVal) ||
       TrueVal->getType() != CondVal->getType())
     return nullptr;
 
   auto *One = ConstantInt::getTrue(SelType);
   auto *Zero = ConstantInt::getFalse(SelType);
   Value *A, *B, *C, *D;
 
+  // Some very basic simplifcations to get out of the way first.
+  if (match(TrueVal, m_Zero()) && match(FalseVal, m_One()))
+    return BinaryOperator::CreateNot(CondVal);
+
+  if (TrueVal == CondVal)
+    return SelectInst::Create(CondVal, One, FalseVal);
+
+  if (match(TrueVal, m_Not(m_Specific(CondVal))))
+    return SelectInst::Create(CondVal, Zero, FalseVal);
+
+  if (FalseVal == CondVal)
+    return SelectInst::Create(CondVal, TrueVal, Zero);
+
+  if (match(FalseVal, m_Not(m_Specific(CondVal))))
+    return SelectInst::Create(CondVal, TrueVal, One);
+
+  // Try our best to canonicalize to `select c, true, false` starting from
+  // `select c, A, true` or `select c, false, B`.
+  // First try to just invert the condition and swap trueval/falseval.
+  // If we can't invert the condition try to invert the select as a whole.
+  if (match(TrueVal, m_Specific(Zero)) || match(FalseVal, m_Specific(One))) {
+    if (canFreelyInvert(*this, CondVal, &SI)) {
+      Value *NotCond = freelyInvert(*this, CondVal, &SI);
+      return SelectInst::Create(NotCond, FalseVal, TrueVal);
+    }
+    if (canFreelyInvert(*this, &SI)) {
+      Value *NotSelect = Builder.CreateSelect(
+          CondVal, Builder.CreateNot(TrueVal), Builder.CreateNot(FalseVal));
+      Instruction *R = replaceInstUsesWith(SI, NotSelect);
+      freelyInvertAllUsersOf(NotSelect);
+      return R;
+    }
+  }
+
+
   // Folding select to and/or i1 isn't poison safe in general. impliesPoison
   // checks whether folding it does not convert a well-defined value into
   // poison.
   if (match(TrueVal, m_One())) {
     if (impliesPoison(FalseVal, CondVal)) {
       // Change: A = select B, true, C --> A = or B, C
       return BinaryOperator::CreateOr(CondVal, FalseVal);
     }
if (match(CondVal, m_LogicalAnd(m_Value(A), m_Value(B))) &&
         return AndFactorization(A, B, C);
       if (B == C)
         return AndFactorization(B, A, D);
       if (B == D)
         return AndFactorization(B, A, C, CondLogicAnd && FalseLogicAnd);
     }
   }
 
+  if (match(TrueVal, m_Zero())) {
+    if (auto *LHS = dyn_cast<FCmpInst>(CondVal)) {
+      if (auto *RHS = dyn_cast<FCmpInst>(FalseVal)) {
+        InstCombinerImpl::FCmpComponents LHSComponents{
+            LHS->getInversePredicate(), LHS->getOperand(0), LHS->getOperand(1),
+            LHS};
+        if (Value *V = foldLogicOfFCmps(LHSComponents, RHS, /*IsAnd*/ true,
+                                        /*IsSelectLogical*/ true))
+          return replaceInstUsesWith(SI, V);
+      }
+    }
+
+    // !(A || B) && (C || B) --> !(A || B) && C
+    if (match(CondVal, m_LogicalOr(m_Value(A), m_Value(B))) &&
+        match(FalseVal, m_LogicalOr(m_Value(C), m_Value(D)))) {
+      if (A == C || B == C)
+        return SelectInst::Create(CondVal, Zero, D);
+      if (A == D || B == D)
+        return SelectInst::Create(CondVal, Zero, C);
+    }
+  }
+
   if (match(FalseVal, m_Zero())) {
     if (impliesPoison(TrueVal, CondVal)) {
       // Change: A = select B, C, false --> A = and B, C
       return BinaryOperator::CreateAnd(CondVal, TrueVal);
     }
 
     if (auto *LHS = dyn_cast<FCmpInst>(CondVal))
       if (auto *RHS = dyn_cast<FCmpInst>(TrueVal))
if (match(CondVal, m_LogicalOr(m_Value(A), m_Value(B))) &&
         return OrFactorization(A, B, C);
       if (B == C)
         return OrFactorization(B, A, D);
       if (B == D)
         return OrFactorization(B, A, C, CondLogicOr && TrueLogicOr);
     }
   }
 
-  // We match the "full" 0 or 1 constant here to avoid a potential infinite
-  // loop with vectors that may have undefined/poison elements.
-  // select a, false, b -> select !a, b, false
-  if (match(TrueVal, m_Specific(Zero))) {
-    Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
-    return SelectInst::Create(NotCond, FalseVal, Zero);
+  if (match(FalseVal, m_One())) {
+    if (auto *LHS = dyn_cast<FCmpInst>(CondVal)) {
+      if (auto *RHS = dyn_cast<FCmpInst>(TrueVal)) {
+        InstCombinerImpl::FCmpComponents LHSComponents{
+            LHS->getInversePredicate(), LHS->getOperand(0), LHS->getOperand(1),
+            LHS};
+        if (Value *V = foldLogicOfFCmps(LHSComponents, RHS, /*IsAnd*/ false,
+                                        /*IsSelectLogical*/ true))
+          return replaceInstUsesWith(SI, V);
+      }
+    }
+    // !(A && B) || (C && B) --> !(A && B) || C
+    if (match(CondVal, m_LogicalAnd(m_Value(A), m_Value(B))) &&
+        match(TrueVal, m_LogicalAnd(m_Value(C), m_Value(D)))) {
+      if (A == C || B == C)
+        return SelectInst::Create(CondVal, D, One);
+      if (A == D || B == D)
+        return SelectInst::Create(CondVal, C, One);
     }
-  // select a, b, true -> select !a, true, b
-  if (match(FalseVal, m_Specific(One))) {
-    Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
-    return SelectInst::Create(NotCond, One, TrueVal);
   }
 
   // DeMorgan in select form: !a && !b --> !(a || b)
   // select !a, !b, false --> not (select a, true, b)
   if (match(&SI, m_LogicalAnd(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
       (CondVal->hasOneUse() || TrueVal->hasOneUse()) &&
       !match(A, m_ConstantExpr()) && !match(B, m_ConstantExpr()))
     return BinaryOperator::CreateNot(Builder.CreateSelect(A, One, B));
 
   // DeMorgan in select form: !a || !b --> !(a && b)
   // select !a, true, !b --> not (select a, b, false)
   if (match(&SI, m_LogicalOr(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
       (CondVal->hasOneUse() || FalseVal->hasOneUse()) &&
       !match(A, m_ConstantExpr()) && !match(B, m_ConstantExpr()))
     return BinaryOperator::CreateNot(Builder.CreateSelect(A, B, Zero));
 
   // select (select a, true, b), true, b -> select a, true, b
   if (match(CondVal, m_Select(m_Value(A), m_One(), m_Value(B))) &&
       match(TrueVal, m_One()) && match(FalseVal, m_Specific(B)))
     return replaceOperand(SI, 0, A);
+
+  // select (select a, b, true), b, true -> select a, true, b
+  if (match(CondVal, m_Select(m_Value(A), m_Value(B), m_One())) &&
+      match(FalseVal, m_One()) && match(TrueVal, m_Specific(B)))
+    return SelectInst::Create(A, One, B);
+
   // select (select a, b, false), b, false -> select a, b, false
   if (match(CondVal, m_Select(m_Value(A), m_Value(B), m_Zero())) &&
       match(TrueVal, m_Specific(B)) && match(FalseVal, m_Zero()))
     return replaceOperand(SI, 0, A);
+
+  // select (select a, false, b), false, b -> select a, b, false
+  if (match(CondVal, m_Select(m_Value(A), m_Zero(), m_Value(B))) &&
+      match(TrueVal, m_Zero()) && match(FalseVal, m_Specific(B)))
+    return SelectInst::Create(A, B, Zero);
+
   // select a, (select ~a, true, b), false -> select a, b, false
   if (match(TrueVal, m_c_LogicalOr(m_Not(m_Specific(CondVal)), m_Value(B))) &&
       match(FalseVal, m_Zero()))
     return replaceOperand(SI, 1, B);
   // select a, true, (select ~a, b, false) -> select a, true, b
   if (match(FalseVal, m_c_LogicalAnd(m_Not(m_Specific(CondVal)), m_Value(B))) &&
       match(TrueVal, m_One()))
     return replaceOperand(SI, 2, B);
Instruction *InstCombinerImpl::foldSelectOfBools(SelectInst &SI) {
   }
   // select (~c & b), a, b -> and b, (or freeze(a), c)
   if (match(CondVal, m_c_And(m_Not(m_Value(C)), m_Specific(FalseVal))) &&
       CondVal->hasOneUse()) {
     TrueVal = Builder.CreateFreeze(TrueVal);
     return BinaryOperator::CreateAnd(FalseVal, Builder.CreateOr(C, TrueVal));
   }
 
+
   if (match(FalseVal, m_Zero()) || match(TrueVal, m_One())) {
     Use *Y = nullptr;
     bool IsAnd = match(FalseVal, m_Zero()) ? true : false;
     Value *Op1 = IsAnd ? TrueVal : FalseVal;
     if (isCheckForZeroAndMulWithOverflow(CondVal, Op1, IsAnd, Y)) {
       auto *FI = new FreezeInst(*Y, (*Y)->getName() + ".fr");
       InsertNewInstBefore(FI, *cast<Instruction>(Y->getUser()));
       replaceUse(*Y, FI);
       return replaceInstUsesWith(SI, Op1);
     }
 
     if (auto *Op1SI = dyn_cast<SelectInst>(Op1))
       if (auto *I = foldAndOrOfSelectUsingImpliedCond(CondVal, *Op1SI,
                                                       /* IsAnd */ IsAnd))
         return I;
 
     if (auto *ICmp0 = dyn_cast<ICmpInst>(CondVal))
       if (auto *ICmp1 = dyn_cast<ICmpInst>(Op1))
         if (auto *V = foldAndOrOfICmps(ICmp0, ICmp1, SI, IsAnd,
                                        /* IsLogical */ true))
           return replaceInstUsesWith(SI, V);
   }
 
+  if (match(FalseVal, m_One()) || match(TrueVal, m_Zero())) {
+    bool IsAnd = match(TrueVal, m_Zero());
+    Value *Op1 = IsAnd ? FalseVal : TrueVal;
+    if (auto *Op1SI = dyn_cast<SelectInst>(Op1))
+      if (auto *I = foldAndOrOfSelectUsingImpliedCond(CondVal, *Op1SI,
+                                                      /* IsAnd */ IsAnd,
+                                                      /*NotSICond*/ true))
+        return I;
+
+    if (auto *ICmp0 = dyn_cast<ICmpInst>(CondVal)) {
+      if (auto *ICmp1 = dyn_cast<ICmpInst>(Op1)) {
+        InstCombinerImpl::ICmpComponents ICmp0Components{
+            ICmp0->getInversePredicate(), ICmp0->getOperand(0),
+            ICmp0->getOperand(1), ICmp0};
+        if (auto *V = foldAndOrOfICmps(ICmp0Components, ICmp1, SI, IsAnd,
+                                       /* IsLogical */ true))
+          return replaceInstUsesWith(SI, V);
+      }
+    }
+  }
+
   // select (a || b), c, false -> select a, c, false
   // select c, (a || b), false -> select c, a, false
   //   if c implies that b is false.
   if (match(CondVal, m_LogicalOr(m_Value(A), m_Value(B))) &&
       match(FalseVal, m_Zero())) {
     std::optional<bool> Res = isImpliedCondition(TrueVal, B, DL);
     if (Res && *Res == false)
       return replaceOperand(SI, 0, A);

llvm/test/Transforms/InstCombine/branch.ll

f:
   ret i32 3
 }
 
 ; if (x && y || !x) ret 3; ret 42 --> if (!x || y) ret 3; ret 42
 
 define i32 @logical_and_or(i1 %x, i1 %y) {
 ; CHECK-LABEL: @logical_and_or(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[NOT_X:%.*]] = xor i1 [[X:%.*]], true
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[NOT_X]], i1 true, i1 [[Y:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 true
 ; CHECK-NEXT:    br i1 [[AND]], label [[F:%.*]], label [[T:%.*]]
 ; CHECK:       t:
 ; CHECK-NEXT:    ret i32 42
 ; CHECK:       f:
 ; CHECK-NEXT:    ret i32 3
 ;
 entry:
   %and = select i1 %x, i1 %y, i1 true

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

;
   %cmp2 = icmp eq i8 %z, %sel
   ret i1 %cmp2
 }
 
 define i1 @icmp_select_var_select(i8 %x, i8 %y, i1 %c) {
 ; CHECK-LABEL: @icmp_select_var_select(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[X:%.*]], 0
 ; CHECK-NEXT:    [[CMP212:%.*]] = icmp eq i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOT_C:%.*]] = xor i1 [[C:%.*]], true
-; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[CMP1]], i1 true, i1 [[NOT_C]]
-; CHECK-NEXT:    [[CMP2:%.*]] = select i1 [[TMP1]], i1 true, i1 [[CMP212]]
+; CHECK-NEXT:    [[CMP21:%.*]] = select i1 [[C:%.*]], i1 [[CMP212]], i1 true
+; CHECK-NEXT:    [[CMP2:%.*]] = select i1 [[CMP1]], i1 true, i1 [[CMP21]]
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %z = select i1 %c, i8 %x, i8 %y
   %cmp1 = icmp eq i8 %x, 0
   %sel = select i1 %cmp1, i8 %z, i8 %y
   %cmp2 = icmp eq i8 %z, %sel
   ret i1 %cmp2
 }
;
   ret i1 %cmp2
 }
 
 define i1 @icmp_select_implied_cond_swapped_select_with_inv_cond(i8 %x, i8 %y) {
 ; CHECK-LABEL: @icmp_select_implied_cond_swapped_select_with_inv_cond(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i8 [[X:%.*]], 0
 ; CHECK-NEXT:    call void @use.i1(i1 [[CMP1]])
 ; CHECK-NEXT:    [[CMP21:%.*]] = icmp eq i8 [[Y:%.*]], [[X]]
-; CHECK-NEXT:    [[NOT_CMP1:%.*]] = xor i1 [[CMP1]], true
-; CHECK-NEXT:    [[CMP2:%.*]] = select i1 [[NOT_CMP1]], i1 true, i1 [[CMP21]]
+; CHECK-NEXT:    [[CMP2:%.*]] = select i1 [[CMP1]], i1 [[CMP21]], i1 true
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %cmp1 = icmp ne i8 %x, 0
   call void @use.i1(i1 %cmp1)
   %sel = select i1 %cmp1, i8 %y, i8 0
   %cmp2 = icmp eq i8 %sel, %x
   ret i1 %cmp2
 }
;
   ret i1 %cmp
 }
 
 ; reduces via FoldOpInstSelect, but this could be a simple 'not-of-and'
 
 define i1 @select_constants_and_icmp_eq0_zero_fval(i1 %x, i1 %y) {
 ; CHECK-LABEL: @select_constants_and_icmp_eq0_zero_fval(
 ; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 false
-; CHECK-NEXT:    [[NOT_:%.*]] = xor i1 [[TMP1]], true
-; CHECK-NEXT:    ret i1 [[NOT_]]
+; CHECK-NEXT:    [[CMP:%.*]] = xor i1 [[TMP1]], true
+; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %s1 = select i1 %x, i8 12, i8 0
   %s2 = select i1 %y, i8 12, i8 0
   %and = and i8 %s1, %s2
   %cmp = icmp eq i8 %and, 0
   ret i1 %cmp
 }
 
;
   ret i1 %cmp
 }
 
 ; reduces via FoldOpInstSelect, but this could be a simple 'nor'
 
 define i1 @select_constants_and_icmp_ne0_zero_tval(i1 %x, i1 %y) {
 ; CHECK-LABEL: @select_constants_and_icmp_ne0_zero_tval(
 ; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y:%.*]]
-; CHECK-NEXT:    [[NOT_:%.*]] = xor i1 [[TMP1]], true
-; CHECK-NEXT:    ret i1 [[NOT_]]
+; CHECK-NEXT:    [[CMP:%.*]] = xor i1 [[TMP1]], true
+; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %s1 = select i1 %x, i8 0, i8 12
   %s2 = select i1 %y, i8 0, i8 12
   %and = and i8 %s1, %s2
   %cmp = icmp ne i8 %and, 0
   ret i1 %cmp
 }
 

llvm/test/Transforms/InstCombine/icmp-with-selects.ll

entry:
   %cmp = icmp slt i32 %cond6, %cond1
   ret i1 %cmp
 }
 
 define i1 @both_sides_fold_eq(i32 %param, i1 %cond) {
 ; CHECK-LABEL: define i1 @both_sides_fold_eq
 ; CHECK-SAME: (i32 [[PARAM:%.*]], i1 [[COND:%.*]]) {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[NOT_COND:%.*]] = xor i1 [[COND]], true
-; CHECK-NEXT:    ret i1 [[NOT_COND]]
+; CHECK-NEXT:    [[CMP:%.*]] = xor i1 [[COND]], true
+; CHECK-NEXT:    ret i1 [[CMP]]
 ;
 entry:
   %cond1 = select i1 %cond, i32 1, i32 %param
   %cond6 = select i1 %cond, i32 9, i32 %param
   %cmp = icmp eq i32 %cond6, %cond1
   ret i1 %cmp
 }
 
entry:
   ret i1 %cmp
 }
 
 define i1 @one_side_fold_sgt(i32 %val1, i32 %val2, i32 %param, i1 %cond) {
 ; CHECK-LABEL: define i1 @one_side_fold_sgt
 ; CHECK-SAME: (i32 [[VAL1:%.*]], i32 [[VAL2:%.*]], i32 [[PARAM:%.*]], i1 [[COND:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[VAL2]], [[VAL1]]
-; CHECK-NEXT:    [[NOT_COND:%.*]] = xor i1 [[COND]], true
-; CHECK-NEXT:    [[CMP:%.*]] = select i1 [[NOT_COND]], i1 [[TMP0]], i1 false
+; CHECK-NEXT:    [[CMP:%.*]] = select i1 [[COND]], i1 false, i1 [[TMP0]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
 entry:
   %cond1 = select i1 %cond, i32 %param, i32 %val1
   %cond6 = select i1 %cond, i32 %param, i32 %val2
   %cmp = icmp sgt i32 %cond6, %cond1
   ret i1 %cmp
 }
 
 define i1 @one_side_fold_eq(i32 %val1, i32 %val2, i32 %param, i1 %cond) {
 ; CHECK-LABEL: define i1 @one_side_fold_eq
 ; CHECK-SAME: (i32 [[VAL1:%.*]], i32 [[VAL2:%.*]], i32 [[PARAM:%.*]], i1 [[COND:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i32 [[VAL2]], [[VAL1]]
-; CHECK-NEXT:    [[NOT_COND:%.*]] = xor i1 [[COND]], true
-; CHECK-NEXT:    [[CMP:%.*]] = select i1 [[NOT_COND]], i1 true, i1 [[TMP0]]
+; CHECK-NEXT:    [[CMP:%.*]] = select i1 [[COND]], i1 [[TMP0]], i1 true
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
 entry:
   %cond1 = select i1 %cond, i32 %val1, i32 %param
   %cond6 = select i1 %cond, i32 %val2, i32 %param
   %cmp = icmp eq i32 %cond6, %cond1
   ret i1 %cmp
 }

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

;
   ret i8 %outer.sel
 }
 
 ; Tests with intervening inversions
 
 ; In %outer.sel, %outer.cond is inverted
 define i1 @andcond.001.inv.outer.cond(i1 %inner.cond, i1 %alt.cond, i1 %inner.sel.trueval, i1 %inner.sel.falseval, i1 %outer.sel.trueval) {
 ; CHECK-LABEL: @andcond.001.inv.outer.cond(
-; CHECK-NEXT:    [[NOT_ALT_COND:%.*]] = xor i1 [[ALT_COND:%.*]], true
-; CHECK-NEXT:    [[INNER_SEL:%.*]] = select i1 [[NOT_ALT_COND]], i1 [[INNER_SEL_TRUEVAL:%.*]], i1 false
+; CHECK-NEXT:    [[INNER_SEL:%.*]] = select i1 [[ALT_COND:%.*]], i1 false, i1 [[INNER_SEL_TRUEVAL:%.*]]
 ; CHECK-NEXT:    [[OUTER_SEL:%.*]] = select i1 [[INNER_COND:%.*]], i1 [[INNER_SEL]], i1 [[INNER_SEL_FALSEVAL:%.*]]
 ; CHECK-NEXT:    ret i1 [[OUTER_SEL]]
 ;
   %outer.cond = select i1 %inner.cond, i1 %alt.cond, i1 false ; and %inner.cond, %alt.cond
   %inner.sel = select i1 %inner.cond, i1 %inner.sel.trueval, i1 %inner.sel.falseval
   %not.outer.cond = xor i1 %outer.cond, -1
   %outer.sel = select i1 %not.outer.cond, i1 %inner.sel, i1 false
   ret i1 %outer.sel
 }
 define i1 @orcond.001.inv.outer.cond(i1 %inner.cond, i1 %alt.cond, i1 %inner.sel.trueval, i1 %inner.sel.falseval, i1 %outer.sel.falseval) {
 ; CHECK-LABEL: @orcond.001.inv.outer.cond(
-; CHECK-NEXT:    [[NOT_ALT_COND:%.*]] = xor i1 [[ALT_COND:%.*]], true
-; CHECK-NEXT:    [[INNER_SEL:%.*]] = select i1 [[NOT_ALT_COND]], i1 true, i1 [[INNER_SEL_FALSEVAL:%.*]]
+; CHECK-NEXT:    [[INNER_SEL:%.*]] = select i1 [[ALT_COND:%.*]], i1 [[INNER_SEL_FALSEVAL:%.*]], i1 true
 ; CHECK-NEXT:    [[OUTER_SEL:%.*]] = select i1 [[INNER_COND:%.*]], i1 [[INNER_SEL_TRUEVAL:%.*]], i1 [[INNER_SEL]]
 ; CHECK-NEXT:    ret i1 [[OUTER_SEL]]
 ;
   %outer.cond = select i1 %inner.cond, i1 true, i1 %alt.cond ; or %inner.cond, %alt.cond
   %inner.sel = select i1 %inner.cond, i1 %inner.sel.trueval, i1 %inner.sel.falseval
   %not.outer.cond = xor i1 %outer.cond, -1
   %outer.sel = select i1 %not.outer.cond, i1 true, i1 %inner.sel
   ret i1 %outer.sel

 
 ; In %outer.sel, %outer.cond is inverted
 ; In %inner.sel, %inner.cond is inverted
 define i1 @andcond.011.inv.outer.cond.inv.inner.cond.in.inner.sel(i1 %inner.cond, i1 %alt.cond, i1 %inner.sel.trueval, i1 %inner.sel.falseval, i1 %outer.sel.trueval) {
 ; CHECK-LABEL: @andcond.011.inv.outer.cond.inv.inner.cond.in.inner.sel(
 ; CHECK-NEXT:    [[NOT_INNER_COND:%.*]] = xor i1 [[INNER_COND:%.*]], true
 ; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[NOT_INNER_COND]], i1 true, i1 [[INNER_SEL_FALSEVAL:%.*]]
 ; CHECK-NEXT:    call void @use.i1(i1 [[TMP1]])
-; CHECK-NEXT:    [[NOT_ALT_COND:%.*]] = xor i1 [[ALT_COND:%.*]], true
-; CHECK-NEXT:    [[INNER_SEL:%.*]] = select i1 [[NOT_ALT_COND]], i1 [[INNER_SEL_FALSEVAL]], i1 false
-; CHECK-NEXT:    [[NOT_INNER_COND1:%.*]] = xor i1 [[INNER_COND]], true
-; CHECK-NEXT:    [[OUTER_SEL:%.*]] = select i1 [[NOT_INNER_COND1]], i1 true, i1 [[INNER_SEL]]
+; CHECK-NEXT:    [[INNER_SEL:%.*]] = select i1 [[ALT_COND:%.*]], i1 false, i1 [[INNER_SEL_FALSEVAL]]
+; CHECK-NEXT:    [[OUTER_SEL:%.*]] = select i1 [[INNER_COND]], i1 [[INNER_SEL]], i1 true
 ; CHECK-NEXT:    ret i1 [[OUTER_SEL]]
 ;
   %outer.cond = select i1 %inner.cond, i1 %alt.cond, i1 false ; and %inner.cond, %alt.cond
   %not.inner.cond = xor i1 %inner.cond, -1
   %inner.sel = select i1 %not.inner.cond, i1 true, i1 %inner.sel.falseval
   %not.outer.cond = xor i1 %outer.cond, -1
   call void @use.i1(i1 %inner.sel)
   %outer.sel = select i1 %not.outer.cond, i1 %inner.sel, i1 false
   ret i1 %outer.sel
 }
 define i1 @orcond.011.inv.outer.cond.inv.inner.cond.in.inner.sel(i1 %inner.cond, i1 %alt.cond, i1 %inner.sel.trueval, i1 %inner.sel.falseval, i1 %outer.sel.falseval) {
 ; CHECK-LABEL: @orcond.011.inv.outer.cond.inv.inner.cond.in.inner.sel(
 ; CHECK-NEXT:    [[NOT_INNER_COND:%.*]] = xor i1 [[INNER_COND:%.*]], true
 ; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[NOT_INNER_COND]], i1 [[INNER_SEL_TRUEVAL:%.*]], i1 false
 ; CHECK-NEXT:    call void @use.i1(i1 [[TMP1]])
-; CHECK-NEXT:    [[NOT_ALT_COND:%.*]] = xor i1 [[ALT_COND:%.*]], true
-; CHECK-NEXT:    [[INNER_SEL:%.*]] = select i1 [[NOT_ALT_COND]], i1 true, i1 [[INNER_SEL_TRUEVAL]]
-; CHECK-NEXT:    [[NOT_INNER_COND1:%.*]] = xor i1 [[INNER_COND]], true
-; CHECK-NEXT:    [[OUTER_SEL:%.*]] = select i1 [[NOT_INNER_COND1]], i1 [[INNER_SEL]], i1 false
+; CHECK-NEXT:    [[INNER_SEL:%.*]] = select i1 [[ALT_COND:%.*]], i1 [[INNER_SEL_TRUEVAL]], i1 true
+; CHECK-NEXT:    [[OUTER_SEL:%.*]] = select i1 [[INNER_COND]], i1 false, i1 [[INNER_SEL]]
 ; CHECK-NEXT:    ret i1 [[OUTER_SEL]]
 ;
   %outer.cond = select i1 %inner.cond, i1 true, i1 %alt.cond ; or %inner.cond, %alt.cond
   %not.inner.cond = xor i1 %inner.cond, -1
   %inner.sel = select i1 %not.inner.cond, i1 %inner.sel.trueval, i1 false
   call void @use.i1(i1 %inner.sel)
   %not.outer.cond = xor i1 %outer.cond, -1
   %outer.sel = select i1 %not.outer.cond, i1 true, i1 %inner.sel

 define i1 @andcond.111.inv.all.conds(i1 %inner.cond, i1 %alt.cond, i1 %inner.sel.trueval, i1 %inner.sel.falseval, i1 %outer.sel.trueval) {
 ; CHECK-LABEL: @andcond.111.inv.all.conds(
 ; CHECK-NEXT:    [[NOT_INNER_COND_0:%.*]] = xor i1 [[INNER_COND:%.*]], true
 ; CHECK-NEXT:    [[OUTER_COND:%.*]] = select i1 [[NOT_INNER_COND_0]], i1 [[ALT_COND:%.*]], i1 false
 ; CHECK-NEXT:    call void @use.i1(i1 [[OUTER_COND]])
 ; CHECK-NEXT:    [[NOT_INNER_COND_1:%.*]] = xor i1 [[INNER_COND]], true
 ; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[NOT_INNER_COND_1]], i1 [[INNER_SEL_FALSEVAL:%.*]], i1 false
 ; CHECK-NEXT:    call void @use.i1(i1 [[TMP1]])
-; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[INNER_COND]], i1 true, i1 [[ALT_COND]]
-; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[TMP2]], true
-; CHECK-NEXT:    [[OUTER_SEL:%.*]] = select i1 [[TMP3]], i1 [[INNER_SEL_FALSEVAL]], i1 false
+; CHECK-NEXT:    [[INNER_SEL:%.*]] = select i1 [[ALT_COND]], i1 false, i1 [[INNER_SEL_FALSEVAL]]
+; CHECK-NEXT:    [[OUTER_SEL:%.*]] = select i1 [[NOT_INNER_COND_0]], i1 [[INNER_SEL]], i1 false
 ; CHECK-NEXT:    ret i1 [[OUTER_SEL]]
 ;
   %not.inner.cond.0 = xor i1 %inner.cond, -1
   %outer.cond = select i1 %not.inner.cond.0, i1 %alt.cond, i1 false ; and %inner.cond, %alt.cond
   call void @use.i1(i1 %outer.cond)
   %not.inner.cond.1 = xor i1 %inner.cond, -1
   %inner.sel = select i1 %not.inner.cond.1, i1 %inner.sel.falseval, i1 false
   call void @use.i1(i1 %inner.sel)
   %not.outer.cond = xor i1 %outer.cond, -1
   %outer.sel = select i1 %not.outer.cond, i1 %inner.sel, i1 false
   ret i1 %outer.sel
 }
 define i1 @orcond.111.inv.all.conds(i1 %inner.cond, i1 %alt.cond, i1 %inner.sel.trueval, i1 %inner.sel.falseval, i1 %outer.sel.falseval) {
 ; CHECK-LABEL: @orcond.111.inv.all.conds(
 ; CHECK-NEXT:    [[NOT_INNER_COND_0:%.*]] = xor i1 [[INNER_COND:%.*]], true
 ; CHECK-NEXT:    [[OUTER_COND:%.*]] = select i1 [[NOT_INNER_COND_0]], i1 true, i1 [[ALT_COND:%.*]]
 ; CHECK-NEXT:    call void @use.i1(i1 [[OUTER_COND]])
 ; CHECK-NEXT:    [[NOT_INNER_COND_1:%.*]] = xor i1 [[INNER_COND]], true
 ; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[NOT_INNER_COND_1]], i1 true, i1 [[INNER_SEL_TRUEVAL:%.*]]
 ; CHECK-NEXT:    call void @use.i1(i1 [[TMP1]])
-; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[INNER_COND]], i1 [[ALT_COND]], i1 false
-; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[TMP2]], true
-; CHECK-NEXT:    [[OUTER_SEL:%.*]] = select i1 [[TMP3]], i1 true, i1 [[INNER_SEL_TRUEVAL]]
+; CHECK-NEXT:    [[INNER_SEL:%.*]] = select i1 [[ALT_COND]], i1 [[INNER_SEL_TRUEVAL]], i1 true
+; CHECK-NEXT:    [[OUTER_SEL:%.*]] = select i1 [[NOT_INNER_COND_0]], i1 true, i1 [[INNER_SEL]]
 ; CHECK-NEXT:    ret i1 [[OUTER_SEL]]
 ;
   %not.inner.cond.0 = xor i1 %inner.cond, -1
   %outer.cond = select i1 %not.inner.cond.0, i1 true, i1 %alt.cond ; or %inner.cond, %alt.cond
   call void @use.i1(i1 %outer.cond)
   %not.inner.cond.1 = xor i1 %inner.cond, -1
   %inner.sel = select i1 %not.inner.cond.1, i1 true, i1 %inner.sel.trueval
   call void @use.i1(i1 %inner.sel)
   %not.outer.cond = xor i1 %outer.cond, -1
   %outer.sel = select i1 %not.outer.cond, i1 true, i1 %inner.sel
   ret i1 %outer.sel
 }

llvm/test/Transforms/InstCombine/not.ll

 ;
   %sel = select i1 %x, i1 %y, i1 %z
   %r = xor i1 %sel, true
   ret i1 %r
 }
 
 define i1 @not_select_bool_const1(i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_select_bool_const1(
-; CHECK-NEXT:    [[Y_NOT:%.*]] = xor i1 [[Y:%.*]], true
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[X:%.*]], i1 [[Y_NOT]], i1 false
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 true
+; CHECK-NEXT:    [[R:%.*]] = xor i1 [[SEL]], true
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %sel = select i1 %x, i1 %y, i1 true
   %r = xor i1 %sel, true
   ret i1 %r
 }
 
 define i1 @not_select_bool_const2(i1 %x, i1 %y) {

 ;
   %sel = select i1 %x, i1 true, i1 %y
   %r = xor i1 %sel, true
   ret i1 %r
 }
 
 define i1 @not_select_bool_const4(i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_select_bool_const4(
-; CHECK-NEXT:    [[Y_NOT:%.*]] = xor i1 [[Y:%.*]], true
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y_NOT]]
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[X:%.*]], i1 false, i1 [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = xor i1 [[SEL]], true
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %sel = select i1 %x, i1 false, i1 %y
   %r = xor i1 %sel, true
   ret i1 %r
 }
 
 define <2 x i1> @not_logicalAnd_not_op0(<2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @not_logicalAnd_not_op0(
 ; CHECK-NEXT:    [[Y_NOT:%.*]] = xor <2 x i1> [[Y:%.*]], <i1 true, i1 true>
 ; CHECK-NEXT:    [[NOTAND:%.*]] = select <2 x i1> [[X:%.*]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[Y_NOT]]
 ; CHECK-NEXT:    ret <2 x i1> [[NOTAND]]
 ;
   %notx = xor <2 x i1> %x, <i1 true, i1 true>
   %and = select <2 x i1> %notx, <2 x i1> %y, <2 x i1> zeroinitializer
   %notand = xor <2 x i1> %and, <i1 true, i1 true>
   ret <2 x i1> %notand
 }
 
 define i1 @not_logicalAnd_not_op1(i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_logicalAnd_not_op1(
-; CHECK-NEXT:    [[NOT_X:%.*]] = xor i1 [[X:%.*]], true
-; CHECK-NEXT:    [[NOTAND:%.*]] = select i1 [[NOT_X]], i1 true, i1 [[Y:%.*]]
+; CHECK-NEXT:    [[NOTAND:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 true
 ; CHECK-NEXT:    ret i1 [[NOTAND]]
 ;
   %noty = xor i1 %y, true
   %and = select i1 %x, i1 %noty, i1 false
   %notand = xor i1 %and, true
   ret i1 %notand
 }
 
;
   %notx = xor <2 x i1> %x, <i1 true, i1 true>
   %or = select <2 x i1> %notx, <2 x i1> <i1 true, i1 true>, <2 x i1> %y
   %notor = xor <2 x i1> %or, <i1 true, i1 true>
   ret <2 x i1> %notor
 }
 
 define i1 @not_logicalOr_not_op1(i1 %x, i1 %y) {
 ; CHECK-LABEL: @not_logicalOr_not_op1(
-; CHECK-NEXT:    [[NOT_X:%.*]] = xor i1 [[X:%.*]], true
-; CHECK-NEXT:    [[NOTOR:%.*]] = select i1 [[NOT_X]], i1 [[Y:%.*]], i1 false
+; CHECK-NEXT:    [[NOTOR:%.*]] = select i1 [[X:%.*]], i1 false, i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[NOTOR]]
 ;
   %noty = xor i1 %y, true
   %or = select i1 %x, i1 true, i1 %noty
   %notor = xor i1 %or, true
   ret i1 %notor
 }
 

llvm/test/Transforms/InstCombine/select-and-or.ll

 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %res = select i1 %a, i1 true, i1 %b
   ret i1 %res
 }
 ; Canonicalize to logical and form, even if that requires adding a "not".
 define i1 @logical_and_not(i1 %a, i1 %b) {
 ; CHECK-LABEL: @logical_and_not(
-; CHECK-NEXT:    [[NOT_A:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[NOT_A]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 false, i1 [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %res = select i1 %a, i1 false, i1 %b
   ret i1 %res
 }
 
 ; Canonicalize to logical or form, even if that requires adding a "not".
 define i1 @logical_or_not(i1 %a, i1 %b) {
 ; CHECK-LABEL: @logical_or_not(
-; CHECK-NEXT:    [[NOT_A:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[NOT_A]], i1 true, i1 [[B:%.*]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 true
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %res = select i1 %a, i1 %b, i1 true
   ret i1 %res
 }
 
 ; These are variants where condition or !condition is used to represent true
 ; or false in one of the select arms. It should be canonicalized to the

 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %res = select i1 %a, i1 %a, i1 %b
   ret i1 %res
 }
 
 define i1 @logical_and_not_cond_reuse(i1 %a, i1 %b) {
 ; CHECK-LABEL: @logical_and_not_cond_reuse(
-; CHECK-NEXT:    [[NOT_A:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[NOT_A]], i1 true, i1 [[B:%.*]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 true
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %a.not = xor i1 %a, true
   %res = select i1 %a, i1 %b, i1 %a.not
   ret i1 %res
 }
 
 define i1 @logical_or_not_cond_reuse(i1 %a, i1 %b) {
 ; CHECK-LABEL: @logical_or_not_cond_reuse(
-; CHECK-NEXT:    [[NOT_A:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[NOT_A]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 false, i1 [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %a.not = xor i1 %a, true
   %res = select i1 %a, i1 %a.not, i1 %b
   ret i1 %res
 }
 
 ; Safe to convert to or due to poison implication.

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

 ;
   %ccax = sext i1 %cca to i32
   %r = select i1 %ccb, i32 -1, i32 %ccax
   ret i32 %r
 }
 
 define i32 @test_sext3(i1 %cca, i1 %ccb) {
 ; CHECK-LABEL: @test_sext3(
-; CHECK-NEXT:    [[NOT_CCB:%.*]] = xor i1 [[CCB:%.*]], true
-; CHECK-NEXT:    [[NARROW:%.*]] = select i1 [[NOT_CCB]], i1 [[CCA:%.*]], i1 false
+; CHECK-NEXT:    [[NARROW:%.*]] = select i1 [[CCB:%.*]], i1 false, i1 [[CCA:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = sext i1 [[NARROW]] to i32
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %ccax = sext i1 %cca to i32
   %r = select i1 %ccb, i32 0, i32 %ccax
   ret i32 %r
 }
 
 define i32 @test_sext4(i1 %cca, i1 %ccb) {
 ; CHECK-LABEL: @test_sext4(
-; CHECK-NEXT:    [[NOT_CCB:%.*]] = xor i1 [[CCB:%.*]], true
-; CHECK-NEXT:    [[NARROW:%.*]] = select i1 [[NOT_CCB]], i1 true, i1 [[CCA:%.*]]
+; CHECK-NEXT:    [[NARROW:%.*]] = select i1 [[CCB:%.*]], i1 [[CCA:%.*]], i1 true
 ; CHECK-NEXT:    [[R:%.*]] = sext i1 [[NARROW]] to i32
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %ccax = sext i1 %cca to i32
   %r = select i1 %ccb, i32 %ccax, i32 -1
   ret i32 %r
 }
 

 ;
   %ccax = zext i1 %cca to i32
   %r = select i1 %ccb, i32 1, i32 %ccax
   ret i32 %r
 }
 
 define i32 @test_zext3(i1 %cca, i1 %ccb) {
 ; CHECK-LABEL: @test_zext3(
-; CHECK-NEXT:    [[NOT_CCB:%.*]] = xor i1 [[CCB:%.*]], true
-; CHECK-NEXT:    [[NARROW:%.*]] = select i1 [[NOT_CCB]], i1 [[CCA:%.*]], i1 false
+; CHECK-NEXT:    [[NARROW:%.*]] = select i1 [[CCB:%.*]], i1 false, i1 [[CCA:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = zext i1 [[NARROW]] to i32
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %ccax = zext i1 %cca to i32
   %r = select i1 %ccb, i32 0, i32 %ccax
   ret i32 %r
 }
 
 define i32 @test_zext4(i1 %cca, i1 %ccb) {
 ; CHECK-LABEL: @test_zext4(
-; CHECK-NEXT:    [[NOT_CCB:%.*]] = xor i1 [[CCB:%.*]], true
-; CHECK-NEXT:    [[NARROW:%.*]] = select i1 [[NOT_CCB]], i1 true, i1 [[CCA:%.*]]
+; CHECK-NEXT:    [[NARROW:%.*]] = select i1 [[CCB:%.*]], i1 [[CCA:%.*]], i1 true
 ; CHECK-NEXT:    [[R:%.*]] = zext i1 [[NARROW]] to i32
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %ccax = zext i1 %cca to i32
   %r = select i1 %ccb, i32 %ccax, i32 1
   ret i32 %r
 }
 

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 @xor_and(i1 %c, i32 %X, i32 %Y) {
 ; CHECK-LABEL: @xor_and(
 ; 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:    [[SEL:%.*]] = select i1 [[C:%.*]], i1 [[COMP]], i1 true
 ; 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
 }
 
;
   %sel = select <2 x i1> %c, <2 x i1> %comp, <2 x i1> <i1 icmp eq (ptr @glb, ptr inttoptr (i64 1234 to ptr)), 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 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:    [[SEL:%.*]] = select i1 [[C:%.*]], i1 false, i1 [[COMP]]
 ; 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
 }
 

llvm/test/Transforms/InstCombine/select.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 ; PR1822
 
 target datalayout = "e-p:64:64-p1:16:16-p2:32:32:32-p3:64:64:64"
 
 define i1 @test5(i1 %C) {
 ; CHECK-LABEL: @test5(
-; CHECK-NEXT:    [[NOT_C:%.*]] = xor i1 [[C:%.*]], true
-; CHECK-NEXT:    ret i1 [[NOT_C]]
+; CHECK-NEXT:    [[V:%.*]] = xor i1 [[C:%.*]], true
+; CHECK-NEXT:    ret i1 [[V]]
 ;
   %V = select i1 %C, i1 false, i1 true
   ret i1 %V
 }
 
 define i32 @test6(i1 %C) {
 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:    [[V:%.*]] = zext i1 [[C:%.*]] to i32

 ; CHECK-NEXT:    ret <vscale x 2 x i1> [[R]]
 ;
   %R = select <vscale x 2 x i1> %C, <vscale x 2 x i1> %X, <vscale x 2 x i1> zeroinitializer
   ret <vscale x 2 x i1> %R
 }
 
 define i1 @test9(i1 %C, i1 %X) {
 ; CHECK-LABEL: @test9(
-; CHECK-NEXT:    [[NOT_C:%.*]] = xor i1 [[C:%.*]], true
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[NOT_C]], i1 [[X:%.*]], i1 false
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 false, i1 [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %R = select i1 %C, i1 false, i1 %X
   ret i1 %R
 }
 
 define <2 x i1> @test9vec(<2 x i1> %C, <2 x i1> %X) {
 ; CHECK-LABEL: @test9vec(
-; CHECK-NEXT:    [[NOT_C:%.*]] = xor <2 x i1> [[C:%.*]], <i1 true, i1 true>
-; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[NOT_C]], <2 x i1> [[X:%.*]], <2 x i1> zeroinitializer
+; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[C:%.*]], <2 x i1> zeroinitializer, <2 x i1> [[X:%.*]]
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %R = select <2 x i1> %C, <2 x i1> <i1 false, i1 false>, <2 x i1> %X
   ret <2 x i1> %R
 }
 
 define <vscale x 2 x i1> @test9vvec(<vscale x 2 x i1> %C, <vscale x 2 x i1> %X) {
 ; CHECK-LABEL: @test9vvec(
-; CHECK-NEXT:    [[NOT_C:%.*]] = xor <vscale x 2 x i1> [[C:%.*]], shufflevector (<vscale x 2 x i1> insertelement (<vscale x 2 x i1> poison, i1 true, i64 0), <vscale x 2 x i1> poison, <vscale x 2 x i32> zeroinitializer)
-; CHECK-NEXT:    [[R:%.*]] = select <vscale x 2 x i1> [[NOT_C]], <vscale x 2 x i1> [[X:%.*]], <vscale x 2 x i1> zeroinitializer
+; CHECK-NEXT:    [[R:%.*]] = select <vscale x 2 x i1> [[C:%.*]], <vscale x 2 x i1> zeroinitializer, <vscale x 2 x i1> [[X:%.*]]
 ; CHECK-NEXT:    ret <vscale x 2 x i1> [[R]]
 ;
   %R = select <vscale x 2 x i1> %C, <vscale x 2 x i1> zeroinitializer, <vscale x 2 x i1> %X
   ret <vscale x 2 x i1> %R
 }
 
 define i1 @test10(i1 %C, i1 %X) {
 ; CHECK-LABEL: @test10(
-; CHECK-NEXT:    [[NOT_C:%.*]] = xor i1 [[C:%.*]], true
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[NOT_C]], i1 true, i1 [[X:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[X:%.*]], i1 true
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %R = select i1 %C, i1 %X, i1 true
   ret i1 %R
 }
 
 define <2 x i1> @test10vec(<2 x i1> %C, <2 x i1> %X) {
 ; CHECK-LABEL: @test10vec(
-; CHECK-NEXT:    [[NOT_C:%.*]] = xor <2 x i1> [[C:%.*]], <i1 true, i1 true>
-; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[NOT_C]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[X:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[C:%.*]], <2 x i1> [[X:%.*]], <2 x i1> <i1 true, i1 true>
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %R = select <2 x i1> %C, <2 x i1> %X, <2 x i1> <i1 true, i1 true>
   ret <2 x i1> %R
 }
 
 define i1 @test23(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test23(

 ; CHECK-NEXT:    ret <2 x i1> [[C]]
 ;
   %c = select <2 x i1> %a, <2 x i1> %a, <2 x i1> %b
   ret <2 x i1> %c
 }
 
 define i1 @test62(i1 %A, i1 %B) {
 ; CHECK-LABEL: @test62(
-; CHECK-NEXT:    [[NOT_A:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[NOT_A]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    [[C:%.*]] = select i1 [[A:%.*]], i1 false, i1 [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %not = xor i1 %A, true
   %C = select i1 %A, i1 %not, i1 %B
   ret i1 %C
 }
 
 define <2 x i1> @test62vec(<2 x i1> %A, <2 x i1> %B) {
 ; CHECK-LABEL: @test62vec(
-; CHECK-NEXT:    [[NOT_A:%.*]] = xor <2 x i1> [[A:%.*]], <i1 true, i1 true>
-; CHECK-NEXT:    [[C:%.*]] = select <2 x i1> [[NOT_A]], <2 x i1> [[B:%.*]], <2 x i1> zeroinitializer
+; CHECK-NEXT:    [[C:%.*]] = select <2 x i1> [[A:%.*]], <2 x i1> zeroinitializer, <2 x i1> [[B:%.*]]
 ; CHECK-NEXT:    ret <2 x i1> [[C]]
 ;
   %not = xor <2 x i1> %A, <i1 true, i1 true>
   %C = select <2 x i1> %A, <2 x i1> %not, <2 x i1> %B
   ret <2 x i1> %C
 }
 
 define i1 @test63(i1 %A, i1 %B) {
 ; CHECK-LABEL: @test63(
-; CHECK-NEXT:    [[NOT_A:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[NOT_A]], i1 true, i1 [[B:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 true
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %not = xor i1 %A, true
   %C = select i1 %A, i1 %B, i1 %not
   ret i1 %C
 }
 
 define <2 x i1> @test63vec(<2 x i1> %A, <2 x i1> %B) {
 ; CHECK-LABEL: @test63vec(
-; CHECK-NEXT:    [[NOT_A:%.*]] = xor <2 x i1> [[A:%.*]], <i1 true, i1 true>
-; CHECK-NEXT:    [[C:%.*]] = select <2 x i1> [[NOT_A]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[B:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = select <2 x i1> [[A:%.*]], <2 x i1> [[B:%.*]], <2 x i1> <i1 true, i1 true>
 ; CHECK-NEXT:    ret <2 x i1> [[C]]
 ;
   %not = xor <2 x i1> %A, <i1 true, i1 true>
   %C = select <2 x i1> %A, <2 x i1> %B, <2 x i1> %not
   ret <2 x i1> %C
 }
 
 define i32 @test11(i32 %a) {
;
   %C = icmp eq i32 %a, %b
   %V = select i1 %C, i32 %b, i32 %a
   ret i32 %V
 }
 
 define i1 @test14a(i1 %C, i32 %X) {
 ; CHECK-LABEL: @test14a(
 ; CHECK-NEXT:    [[R1:%.*]] = icmp slt i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[NOT_C:%.*]] = xor i1 [[C:%.*]], true
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[NOT_C]], i1 true, i1 [[R1]]
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[R1]], i1 true
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %V = select i1 %C, i32 %X, i32 0
   ; (X < 1) | !C
   %R = icmp slt i32 %V, 1
   ret i1 %R
 }
 
;
   ret i32 %V
 }
 
 attributes #0 = { null_pointer_is_valid }
 
 define i1 @test17(ptr %X, i1 %C) {
 ; CHECK-LABEL: @test17(
 ; CHECK-NEXT:    [[RV1:%.*]] = icmp eq ptr [[X:%.*]], null
-; CHECK-NEXT:    [[NOT_C:%.*]] = xor i1 [[C:%.*]], true
-; CHECK-NEXT:    [[RV:%.*]] = select i1 [[NOT_C]], i1 true, i1 [[RV1]]
+; CHECK-NEXT:    [[RV:%.*]] = select i1 [[C:%.*]], i1 [[RV1]], i1 true
 ; CHECK-NEXT:    ret i1 [[RV]]
 ;
   %R = select i1 %C, ptr %X, ptr null
   %RV = icmp eq ptr %R, null
   ret i1 %RV
 }
 
 define i32 @test18(i32 %X, i32 %Y, i1 %C) {

llvm/test/Transforms/InstCombine/sink-not-into-logical-and.ll

;
   %i2 = icmp eq i32 %v2, %v3
   %i3 = select i1 %i2, i1 %i1, i1 false
   %i4 = xor i1 %i3, -1
   ret i1 %i4
 }
 define i1 @n2(i32 %v0, i32 %v1, i1 %i2) {
 ; CHECK-LABEL: @n2(
 ; CHECK-NEXT:    [[I1:%.*]] = icmp ne i32 [[V0:%.*]], [[V1:%.*]]
-; CHECK-NEXT:    [[NOT_I2:%.*]] = xor i1 [[I2:%.*]], true
-; CHECK-NEXT:    [[I3:%.*]] = select i1 [[NOT_I2]], i1 true, i1 [[I1]]
+; CHECK-NEXT:    [[I3:%.*]] = select i1 [[I2:%.*]], i1 [[I1]], i1 true
 ; CHECK-NEXT:    ret i1 [[I3]]
 ;
   %i1 = icmp eq i32 %v0, %v1
   %i3 = select i1 %i2, i1 %i1, i1 false
   %i4 = xor i1 %i3, -1
   ret i1 %i4
 }
 define i1 @n3(i1 %i1, i1 %i2) {
;
   %i4 = xor i1 %i3, -1
   ret i1 %i4
 }
 define i1 @n5(i32 %v0, i32 %v1, i32 %v2, i32 %v3) {
 ; CHECK-LABEL: @n5(
 ; CHECK-NEXT:    [[I1:%.*]] = icmp ne i32 [[V0:%.*]], [[V1:%.*]]
 ; CHECK-NEXT:    [[I2:%.*]] = icmp eq i32 [[V2:%.*]], [[V3:%.*]]
 ; CHECK-NEXT:    call void @use1(i1 [[I2]])
-; CHECK-NEXT:    [[NOT_I2:%.*]] = xor i1 [[I2]], true
-; CHECK-NEXT:    [[I3:%.*]] = select i1 [[NOT_I2]], i1 true, i1 [[I1]]
+; CHECK-NEXT:    [[I3:%.*]] = select i1 [[I2]], i1 [[I1]], i1 true
 ; CHECK-NEXT:    ret i1 [[I3]]
 ;
   %i1 = icmp eq i32 %v0, %v1
   %i2 = icmp eq i32 %v2, %v3
   call void @use1(i1 %i2)
   %i3 = select i1 %i2, i1 %i1, i1 false
   %i4 = xor i1 %i3, -1
   ret i1 %i4

 
 ; This would miscompile by not handling the unsimplified select correctly.
 
 define i1 @PR59704(i1 %c, i1 %b, i64 %arg) {
 ; CHECK-LABEL: @PR59704(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[JOIN:%.*]]
 ; CHECK:       if:
-; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i64 [[ARG:%.*]], 0
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[ARG:%.*]], 0
 ; CHECK-NEXT:    br label [[JOIN]]
 ; CHECK:       join:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ [[CMP_NOT]], [[IF]] ]
+; CHECK-NEXT:    [[PHI:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ [[CMP]], [[IF]] ]
 ; CHECK-NEXT:    ret i1 [[PHI]]
 ;
 entry:
   br i1 %c, label %if, label %join
 
 if:
   %cmp = icmp ne i64 %arg, 0
   %and = select i1 %cmp, i1 %cmp, i1 false
   br label %join
 
 join:
   %phi = phi i1 [ false, %entry ], [ %and, %if ]
   %not = xor i1 %phi, true
   ret i1 %not
 }

llvm/test/Transforms/InstCombine/sink-not-into-logical-or.ll

;
   %i2 = icmp eq i32 %v2, %v3
   %i3 = select i1 %i2, i1 true, i1 %i1
   %i4 = xor i1 %i3, -1
   ret i1 %i4
 }
 define i1 @n2(i32 %v0, i32 %v1, i1 %i2) {
 ; CHECK-LABEL: @n2(
 ; CHECK-NEXT:    [[I1:%.*]] = icmp ne i32 [[V0:%.*]], [[V1:%.*]]
-; CHECK-NEXT:    [[NOT_I2:%.*]] = xor i1 [[I2:%.*]], true
-; CHECK-NEXT:    [[I3:%.*]] = select i1 [[NOT_I2]], i1 [[I1]], i1 false
+; CHECK-NEXT:    [[I3:%.*]] = select i1 [[I2:%.*]], i1 false, i1 [[I1]]
 ; CHECK-NEXT:    ret i1 [[I3]]
 ;
   %i1 = icmp eq i32 %v0, %v1
   %i3 = select i1 %i2, i1 true, i1 %i1
   %i4 = xor i1 %i3, -1
   ret i1 %i4
 }
 define i1 @n3(i1 %i1, i1 %i2) {
;
   %i4 = xor i1 %i3, -1
   ret i1 %i4
 }
 define i1 @n5(i32 %v0, i32 %v1, i32 %v2, i32 %v3) {
 ; CHECK-LABEL: @n5(
 ; CHECK-NEXT:    [[I1:%.*]] = icmp ne i32 [[V0:%.*]], [[V1:%.*]]
 ; CHECK-NEXT:    [[I2:%.*]] = icmp eq i32 [[V2:%.*]], [[V3:%.*]]
 ; CHECK-NEXT:    call void @use1(i1 [[I2]])
-; CHECK-NEXT:    [[NOT_I2:%.*]] = xor i1 [[I2]], true
-; CHECK-NEXT:    [[I3:%.*]] = select i1 [[NOT_I2]], i1 [[I1]], i1 false
+; CHECK-NEXT:    [[I3:%.*]] = select i1 [[I2]], i1 false, i1 [[I1]]
 ; CHECK-NEXT:    ret i1 [[I3]]
 ;
   %i1 = icmp eq i32 %v0, %v1
   %i2 = icmp eq i32 %v2, %v3
   call void @use1(i1 %i2)
   %i3 = select i1 %i2, i1 true, i1 %i1
   %i4 = xor i1 %i3, -1
   ret i1 %i4