[InstCombine] Add simplification of two logical and/ors

[aqjune]

Summary

This is a patch that adds folding of two logical and/ors that share one variable:

a && (a && b) -> a && b
a && (a & b) -> a && b
...

This is towards removing the poison-unsafe select optimization (D93065 has more context).

[aqjune]

Rebase

[aqjune]

llvm/lib/Analysis/ValueTracking.cpp

4889 ↗

(On Diff #325153)

This update was necessary to add transformations for pattern
merge_two_logical_ands3: (X && Y) && X -> X && Y
merge_two_logical_ors3: (X || Y) || X -> X || Y

The remaining patterns are supported by the updates in InstCombineSelect.cpp.

[aqjune]

Rebase & ping

[aqjune]

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

332–333

It is correct for this to be select; or i1 propagates poison which is unsafe.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2641–2648

Why does this only deal with select form in the cond operand, unlike the two folds above?

[aqjune]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2641–2648

It's because the non-select cond cases are dealt with the existing transformations (line 2593, 2598).
They fold select (or a, b), true, b into or (or a, b), b which becomes or a, b by visitOr.
This is sound: https://alive2.llvm.org/ce/z/UgMbNq
Similarly, select (and a, b), b, false is folded into and (and a, b), b which becomes and a, b.
This is also okay (https://alive2.llvm.org/ce/z/AWoJK6).

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

4889 ↗

(On Diff #325153)

Just as a side-note, I think the right way to handle this is to replace propagatesPoison() with getPoisonPropagatingOperands() or similar, which allows handling cases like these, where poison is only partially propagated. For now this is fine, though I think it would be better to write it as:

if (const auto *SI = dyn_cast<SelectInst>(I))
  return directlyImpliesPoison(ValAssumedPoison, SI->getCondition(), Depth + 1);

This will keep the same recursion as for the propagatesPoison() case.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2631

Please use && and || instead of /\ and \/.

2639

What currently happens for something like a ? (a | b) : false? I assume it doesn't get folded?

[aqjune]

Address comments

[aqjune]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2639

No, it doesn't get folded.
That being said, I think it is better to simply propagate true/false to select operands, e.g.
a ? (a | b) : false -> a ? (true | b) : false -> a ? b : false. I'll update this patch to do so.

[aqjune]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2639

Nevermind, since the replacement needs to take care of # uses but the current version doesn't need it, I think it does not completely cover the foldings in this patch.

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

4858 ↗

(On Diff #328857)

Feel free to already land this part separately.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2639

What I had in mind here is that this is basically the foldSelectValueEquivalence() fold, just that instead of x == C ? y : z we have x == true ? y : z, with the == true comparison being implicit. If we generalize that fold to handle this special case, this should work automatically (either via SimplifyWithOpReplaced, or by direct operand replacement for single use).

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2639

Ignoring the case of actual operand replacement, I think doing something like this should do:

if (Value *S = SimplifyWithOpReplaced(TrueVal, CondVal, True, SQ, /* AllowRefinement */ true))
  return replaceOperand(SI, 1, S);
if (Value *S = SimplifyWithOpReplaced(FalseVal, CondVal, False, SQ, /* AllowRefinement */ true))
  return replaceOperand(SI, 2, S);

Though probably SimplifyWithOpReplaced needs to be strengthened a bit to also handle selects.

[aqjune]

Update & use SimplifyWithOpReplaced

[aqjune]

clang-format

[aqjune]

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

53

There are a few suboptimal patterns left; Since they are just simple syntactic patterns, I'll write them and push directly.

[aqjune]

Update changes in llvm/test/Transforms/SimplifyCFG/merge-cond-stores.ll

[nikic]

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

266

The previous output here was wrong. Do you know what caused that fold? Maybe there is something more we need to disable.

430

Same here, previous output was wrong.

[aqjune]

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

266

It is here: https://github.com/llvm/llvm-project/blob/99108c791de0285ee726a10e8274772b18cee73c/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp#L2893
I'll push a commit that fixes this by using CreateLogicalAnd if -instcombine-unsafe-select-transform is zero.
Similarly for the or one.

[aqjune]

rebase

[nikic]

LGTM

[leonardchan]

HI,

A bisect seems to show this patch causing the test failures we see on our two-stage clang builders (https://luci-milo.appspot.com/p/fuchsia/builders/prod/clang-linux-x64/b8853364937280028160?):

********************
  LLVM :: Transforms/InstCombine/2011-05-28-swapmulsub.ll
  LLVM :: Transforms/InstCombine/bitcast-bigendian.ll
  LLVM :: Transforms/InstCombine/bitcast-inseltpoison.ll
  LLVM :: Transforms/InstCombine/bitcast.ll
  LLVM :: Transforms/InstCombine/icmp-custom-dl.ll
  LLVM :: Transforms/InstCombine/icmp.ll
  LLVM :: Transforms/InstCombine/shift-amount-reassociation-in-bittest-with-truncation-shl.ll
  LLVM :: Transforms/InstCombine/shift-amount-reassociation-with-truncation-shl.ll
  LLVM :: Transforms/InstCombine/sub-gep.ll
  LLVM :: Transforms/InstCombine/sub.ll
  LLVM :: Transforms/InstCombine/trunc-inseltpoison.ll
  LLVM :: Transforms/InstCombine/trunc.ll

Would you mind taking a look and sending out a fix or reverting? Thanks.

[aqjune]

Yep, I reverted this patch. Could you post the commandline options that is used to build LLVM?
There was a similar failure reported (D95026) which is due to an existing bug in InstructionSimplify; maybe I can check whether its prospective fix resolves this issue as well.

[leonardchan]

In D96945#2614982, @aqjune wrote:

Yep, I reverted this patch. Could you post the commandline options that is used to build LLVM?
There was a similar failure reported (D95026) which is due to an existing bug in InstructionSimplify; maybe I can check whether its prospective fix resolves this issue as well.

Thanks for the followup. Can do. Let me see if I can minimize the reproducer/reduce the number of cmake flags needed for ease first since the two-stage build has dependencies on libxml2 and zlib.

While I'm doing that, if you already have a fix, what I can do is patch it locally and get back to you on if it also fixes the issues we see.

[leonardchan]

In D96945#2615019, @leonardchan wrote:

In D96945#2614982, @aqjune wrote:

Yep, I reverted this patch. Could you post the commandline options that is used to build LLVM?
There was a similar failure reported (D95026) which is due to an existing bug in InstructionSimplify; maybe I can check whether its prospective fix resolves this issue as well.

Thanks for the followup. Can do. Let me see if I can minimize the reproducer/reduce the number of cmake flags needed for ease first since the two-stage build has dependencies on libxml2 and zlib.

While I'm doing that, if you already have a fix, what I can do is patch it locally and get back to you on if it also fixes the issues we see.

Ok, so the cmake invocation for the second stage build is:

cmake "-DCMAKE_EXE_LINKER_FLAGS=-ldl -lpthread" "-DCMAKE_MODULE_LINKER_FLAGS=-ldl -lpthread" "-DCMAKE_SHARED_LINKER_FLAGS=-ldl -lpthread" -DCMAKE_SYSROOT=/usr/local/google/home/leonardchan/sysroot/linux-amd64 -DLLVM_ENABLE_LLD=ON -DLLVM_ENABLE_LTO=ON -DLLVM_EXTERNAL_CLANG_SOURCE_DIR=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-project-1/llvm/../clang -DLLVM_EXTERNAL_CLANG_TOOLS_EXTRA_SOURCE_DIR=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-project-1/llvm/../clang-tools-extra -DLLVM_EXTERNAL_LLD_SOURCE_DIR=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-project-1/llvm/../lld -DLLVM_EXTERNAL_POLLY_SOURCE_DIR=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-project-1/llvm/../polly -DPACKAGE_VERSION=13.0.0git -DPACKAGE_VENDOR=Fuchsia -DLLVM_VERSION_MAJOR=13 -DLLVM_VERSION_MINOR=0 -DLLVM_VERSION_PATCH=0 -DCLANG_VERSION_MAJOR=13 -DCLANG_VERSION_MINOR=0 -DCLANG_VERSION_PATCHLEVEL=0 -DCLANG_VENDOR=Fuchsia -DLLVM_VERSION_SUFFIX=git -DLLVM_BINUTILS_INCDIR= -DCLANG_REPOSITORY_STRING= -DCMAKE_MAKE_PROGRAM=/usr/bin/ninja "-DLLVM_ENABLE_PROJECTS=clang;clang-tools-extra;lld;llvm;polly" "-DLLVM_ENABLE_RUNTIMES=compiler-rt;libcxx;libcxxabi;libunwind" -DLINUX_aarch64-unknown-linux-gnu_SYSROOT=/usr/local/google/home/leonardchan/sysroot/linux-arm64 -DLINUX_x86_64-unknown-linux-gnu_SYSROOT=/usr/local/google/home/leonardchan/sysroot/linux-amd64 -C /usr/local/google/home/leonardchan/llvm-monorepo/llvm-project-1/clang/cmake/caches/Fuchsia-stage2.cmake -DCLANG_STAGE=stage2 -DCMAKE_CXX_COMPILER=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/./bin/clang++ -DCMAKE_C_COMPILER=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/./bin/clang -DCMAKE_ASM_COMPILER=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/./bin/clang -DCMAKE_ASM_COMPILER_ID=Clang -DCMAKE_AR=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/./bin/llvm-ar -DCMAKE_RANLIB=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/./bin/llvm-ranlib -GNinja /usr/local/google/home/leonardchan/llvm-monorepo/llvm-project-1/llvm

/usr/local/google/home/leonardchan/llvm-monorepo/llvm-project-1 can be replaced with whatever the path pointing to your llvm-project repository is.
/usr/local/google/home/leonardchan/llvm-monorepo/llvm-build-1-master-fuchsia-toolchain is the path to your existing clang toolchain made on this revision.

After this, I'm able to reproduce the failures with ninja check-llvm in my second-stage build.

Let me know if I can help more/clarify on some things.

[aqjune]

I could reproduce the failures, thanks :)

[rupprecht]

We're still seeing some *very* strange miscompiles as a result of this patch (maybe not really this patch's fault, it could be some bad optimization that this unblocks). I'm working on a reduction right now.

[rupprecht]

Here's a repro for the issue we're seeing. It only seems to be happening with msan enabled, so I'm not sure if this is just an msan bug, or a general miscompile that *happens* to trigger in this test when msan is enabled.

The source:

#include <string>
#include <variant>

struct a {
  double b;
  double c;
  std::string d;
};

std::variant<std::pair<int, int>, std::string> e(a f) {
  double g = f.b, h = f.c;
  if (f.d == "y") {
    g *= 2.0;
    h *= 2.0;
  }
  int i(g);
  int k(h);
  if (i == 0) i = h;
  if (k == 0) k = i;
  if (k < i || i < 0) {
    std::string j;
    return j;
  }
  return std::make_pair(i, k);
}

int main() {
  auto j = e({1, 0, "x"});
  std::get<0>(j);
}

To build/run it:

$ clang++ \
  -O2 \
  -msse4.2 \
  -fsanitize=memory \
  -std=gnu++17 \
  -stdlib=libc++ \
  repro.cc \
  -o bug
$ ./bug
terminating with uncaught exception of type std::bad_variant_access: bad_variant_access

Thoughts on this example? If I follow correctly, at the if (k < i || i < 0) { check, both k and i should be 1, and that check should not trigger. Instead, it evaluates to true: the std::get<0>(j) triggers an exception, because the method return a std::string, not a std::pair after this patch.

[aqjune]

It indeed seems tricky to find out the root cause for this; this optimization enabled vectorization which led to the error for some reason.
I'll have more time to investigate this tomorrow and weekends.

[aqjune]

This turns out to be a bug in InstCombine. I reported it as https://llvm.org/pr49832 .

[rupprecht]

@spatel c590a9880d7a660a1c911fce07f3d01ea18be2df fixes the unreduced test case. Thanks!

[spatel]

In D96945#2669224, @rupprecht wrote:

@spatel c590a9880d7a660a1c911fce07f3d01ea18be2df fixes the unreduced test case. Thanks!

Great! We also have essentially the same bug inside of InstSimplify, and that should be fixed with:
e2a0f512eaca

I'm not sure exactly where we stand with respect to exposure/timing for the 12.0 release, but I've marked the patches as blockers for now.
That is tracked at:
https://llvm.org/PR49832

llvm/lib/Analysis/InstructionSimplify.cpp

 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
                                const SimplifyQuery &Q, unsigned MaxRecurse);
 static Value *SimplifyOrInst(Value *, Value *, const SimplifyQuery &, unsigned);
 static Value *SimplifyXorInst(Value *, Value *, const SimplifyQuery &, unsigned);
 static Value *SimplifyCastInst(unsigned, Value *, Type *,
                                const SimplifyQuery &, unsigned);
 static Value *SimplifyGEPInst(Type *, ArrayRef<Value *>, const SimplifyQuery &,
                               unsigned);
+static Value *SimplifySelectInst(Value *, Value *, Value *,
+                                 const SimplifyQuery &, unsigned);
 
 static Value *foldSelectWithBinaryOp(Value *Cond, Value *TrueVal,
                                      Value *FalseVal) {
   BinaryOperator::BinaryOps BinOpCode;
   if (auto *BO = dyn_cast<BinaryOperator>(Cond))
     BinOpCode = BO->getOpcode();
   else
     return nullptr;
if (MaxRecurse) {
       SmallVector<Value *, 8> NewOps(GEP->getNumOperands());
       transform(GEP->operands(), NewOps.begin(),
                 [&](Value *V) { return V == Op ? RepOp : V; });
       return PreventSelfSimplify(SimplifyGEPInst(GEP->getSourceElementType(),
                                                  NewOps, Q, MaxRecurse - 1));
     }
   }
 
+  // Same for Selects.
+  if (auto *SI = dyn_cast<SelectInst>(I)) {
+    if (MaxRecurse) {
+      SmallVector<Value *, 3> NewOps(3);
+      transform(SI->operands(), NewOps.begin(),
+                [&](Value *V) { return V == Op ? RepOp : V; });
+      return PreventSelfSimplify(SimplifySelectInst(
+          NewOps[0], NewOps[1], NewOps[2], Q, MaxRecurse - 1));
+    }
+  }
+
   // TODO: We could hand off more cases to instsimplify here.
 
   // If all operands are constant after substituting Op for RepOp then we can
   // constant fold the instruction.
   if (Constant *CRepOp = dyn_cast<Constant>(RepOp)) {
     // Build a list of all constant operands.
     SmallVector<Constant *, 8> ConstOps;
     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

if (match(TrueVal, m_One()) &&
       return BinaryOperator::CreateOr(CondVal, FalseVal);
     }
     if (match(FalseVal, m_Zero()) &&
         (EnableUnsafeSelectTransform || impliesPoison(TrueVal, CondVal))) {
       // Change: A = select B, C, false --> A = and B, C
       return BinaryOperator::CreateAnd(CondVal, TrueVal);
     }
 
+    auto *One = ConstantInt::getTrue(SelType);
+    auto *Zero = ConstantInt::getFalse(SelType);
+
     // select a, false, b -> select !a, b, false
     if (match(TrueVal, m_Zero())) {
       Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
-      return SelectInst::Create(NotCond, FalseVal,
-                                ConstantInt::getFalse(SelType));
+      return SelectInst::Create(NotCond, FalseVal, Zero);
     }
     // select a, b, true -> select !a, true, b
     if (match(FalseVal, m_One())) {
       Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
-      return SelectInst::Create(NotCond, ConstantInt::getTrue(SelType),
-                                TrueVal);
+      return SelectInst::Create(NotCond, One, TrueVal);
     }
 
     // select a, a, b -> select a, true, b
     if (CondVal == TrueVal)
-      return replaceOperand(SI, 1, ConstantInt::getTrue(SelType));
+      return replaceOperand(SI, 1, One);
     // select a, b, a -> select a, b, false
     if (CondVal == FalseVal)
-      return replaceOperand(SI, 2, ConstantInt::getFalse(SelType));
+      return replaceOperand(SI, 2, Zero);
 
     // select a, !a, b -> select !a, b, false
     if (match(TrueVal, m_Not(m_Specific(CondVal))))
-      return SelectInst::Create(TrueVal, FalseVal,
-                                ConstantInt::getFalse(SelType));
+      return SelectInst::Create(TrueVal, FalseVal, Zero);
     // select a, b, !a -> select !a, true, b
     if (match(FalseVal, m_Not(m_Specific(CondVal))))
-      return SelectInst::Create(FalseVal, ConstantInt::getTrue(SelType),
-                                TrueVal);
+      return SelectInst::Create(FalseVal, One, TrueVal);
+
+    Value *A, *B;
+    // 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, 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);
+
+    if (Value *S = SimplifyWithOpReplaced(TrueVal, CondVal, One, SQ,
+                                          /* AllowRefinement */ true))
+      return replaceOperand(SI, 1, S);
+    if (Value *S = SimplifyWithOpReplaced(FalseVal, CondVal, Zero, SQ,
+                                          /* AllowRefinement */ true))
+      return replaceOperand(SI, 2, S);
   }
 
   // Selecting between two integer or vector splat integer constants?
   //
   // Note that we don't handle a scalar select of vectors:
   // select i1 %c, <2 x i8> <1, 1>, <2 x i8> <0, 0>
   // because that may need 3 instructions to splat the condition value:
   // extend, insertelement, shufflevector.
   //
   // Do not handle i1 TrueVal and FalseVal otherwise would result in

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

 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %c = select i1 %A, i1 %B, i1 false
   %res = select i1 %c, i1 %A, i1 false
   ret i1 %res
 }
 define i1 @land_land_left2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @land_land_left2(
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[B:%.*]], i1 [[A:%.*]], i1 false
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[C]], i1 [[A]], i1 false
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[B:%.*]], i1 [[A:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = select i1 %B, i1 %A, i1 false
   %res = select i1 %c, i1 %A, i1 false
   ret i1 %res
 }
 
 ; (A land B) band A
;
   %res = and i1 %c, %A
   ret i1 %res
 }
 
 ; (A land B) lor A
 define i1 @land_lor_left1(i1 %A, i1 %B) {
 ; CHECK-LABEL: @land_lor_left1(
 ; CHECK-NEXT:    [[C:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
 ; CHECK-NEXT:    [[RES:%.*]] = or i1 [[C]], [[A]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = select i1 %A, i1 %B, i1 false
   %res = select i1 %c, i1 true, i1 %A
   ret i1 %res
 }
 define i1 @land_lor_left2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @land_lor_left2(

 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %c = select i1 %A, i1 true, i1 %B
   %res = select i1 %c, i1 true, i1 %A
   ret i1 %res
 }
 define i1 @lor_lor_left2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @lor_lor_left2(
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[B:%.*]], i1 true, i1 [[A:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[C]], i1 true, i1 [[A]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[B:%.*]], i1 true, i1 [[A:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = select i1 %B, i1 true, i1 %A
   %res = select i1 %c, i1 true, i1 %A
   ret i1 %res
 }
 
 ; (A lor B) bor A

 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = select i1 %A, i1 %B, i1 false
   %res = select i1 %A, i1 %c, i1 false
   ret i1 %res
 }
 define i1 @land_land_right2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @land_land_right2(
-; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
-; CHECK-NEXT:    ret i1 [[TMP1]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = select i1 %B, i1 %A, i1 false
   %res = select i1 %A, i1 %c, i1 false
   ret i1 %res
 }
 
 ; A band (A land B)
 define i1 @land_band_right1(i1 %A, i1 %B) {

 ; CHECK-NEXT:    ret i1 [[A:%.*]]
 ;
   %c = select i1 %A, i1 %B, i1 false
   %res = select i1 %A, i1 true, i1 %c
   ret i1 %res
 }
 define i1 @land_lor_right2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @land_lor_right2(
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[B:%.*]], i1 [[A:%.*]], i1 false
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 true, i1 [[C]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[A:%.*]]
 ;
   %c = select i1 %B, i1 %A, i1 false
   %res = select i1 %A, i1 true, i1 %c
   ret i1 %res
 }
 
 ; A bor (A land B)
 define i1 @land_bor_right1(i1 %A, i1 %B) {

 define i1 @land_bor_right2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @land_bor_right2(
 ; CHECK-NEXT:    ret i1 [[A:%.*]]
 ;
   %c = select i1 %B, i1 %A, i1 false
   %res = or i1 %A, %c
   ret i1 %res
 }
 
 ; A land (A band B)
 define i1 @band_land_right1(i1 %A, i1 %B) {
 ; CHECK-LABEL: @band_land_right1(
-; CHECK-NEXT:    [[C:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 [[C]], i1 false
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = and i1 %A, %B
   %res = select i1 %A, i1 %c, i1 false
   ret i1 %res
 }
 define i1 @band_land_right2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @band_land_right2(
-; CHECK-NEXT:    [[C:%.*]] = and i1 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 [[C]], i1 false
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = and i1 %B, %A
   %res = select i1 %A, i1 %c, i1 false
   ret i1 %res
 }
 
 ; A lor (A band B)
 define i1 @band_lor_right1(i1 %A, i1 %B) {
 ; CHECK-LABEL: @band_lor_right1(
-; CHECK-NEXT:    [[C:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 true, i1 [[C]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[A:%.*]]
 ;
   %c = and i1 %A, %B
   %res = select i1 %A, i1 true, i1 %c
   ret i1 %res
 }
 define i1 @band_lor_right2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @band_lor_right2(
-; CHECK-NEXT:    [[C:%.*]] = and i1 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 true, i1 [[C]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[A:%.*]]
 ;
   %c = and i1 %B, %A
   %res = select i1 %A, i1 true, i1 %c
   ret i1 %res
 }
 
 ; A land (A lor B)
 define i1 @lor_land_right1(i1 %A, i1 %B) {
 ; CHECK-LABEL: @lor_land_right1(
 ; CHECK-NEXT:    ret i1 [[A:%.*]]
 ;
   %c = select i1 %A, i1 true, i1 %B
   %res = select i1 %A, i1 %c, i1 false
   ret i1 %res
 }
 define i1 @lor_land_right2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @lor_land_right2(
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[B:%.*]], i1 true, i1 [[A:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 [[C]], i1 false
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[A:%.*]]
 ;
   %c = select i1 %B, i1 true, i1 %A
   %res = select i1 %A, i1 %c, i1 false
   ret i1 %res
 }
 
 ; A band (A lor B)
 define i1 @lor_band_right1(i1 %A, i1 %B) {

 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = select i1 %A, i1 true, i1 %B
   %res = select i1 %A, i1 true, i1 %c
   ret i1 %res
 }
 define i1 @lor_lor_right2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @lor_lor_right2(
-; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP1]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
+; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = select i1 %B, i1 true, i1 %A
   %res = select i1 %A, i1 true, i1 %c
   ret i1 %res
 }
 
 ; A bor (A lor B)
 define i1 @lor_bor_right1(i1 %A, i1 %B) {
;
   %c = select i1 %B, i1 true, i1 %A
   %res = or i1 %A, %c
   ret i1 %res
 }
 
 ; A land (A bor B)
 define i1 @bor_land_right1(i1 %A, i1 %B) {
 ; CHECK-LABEL: @bor_land_right1(
-; CHECK-NEXT:    [[C:%.*]] = or i1 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 [[C]], i1 false
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[A:%.*]]
 ;
   %c = or i1 %A, %B
   %res = select i1 %A, i1 %c, i1 false
   ret i1 %res
 }
 define i1 @bor_land_right2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @bor_land_right2(
-; CHECK-NEXT:    [[C:%.*]] = or i1 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 [[C]], i1 false
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[A:%.*]]
 ;
   %c = or i1 %B, %A
   %res = select i1 %A, i1 %c, i1 false
   ret i1 %res
 }
 
 ; A lor (A bor B)
 define i1 @bor_lor_right1(i1 %A, i1 %B) {
 ; CHECK-LABEL: @bor_lor_right1(
-; CHECK-NEXT:    [[C:%.*]] = or i1 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 true, i1 [[C]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = or i1 %A, %B
   %res = select i1 %A, i1 true, i1 %c
   ret i1 %res
 }
 define i1 @bor_lor_right2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @bor_lor_right2(
-; CHECK-NEXT:    [[C:%.*]] = or i1 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 true, i1 [[C]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = or i1 %B, %A
   %res = select i1 %A, i1 true, i1 %c
   ret i1 %res
 }
 

llvm/test/Transforms/SimplifyCFG/merge-cond-stores.ll

 }
 
 declare void @f()
 
 ; This should get if-converted.
 define i32 @test_diamond_simple(i32* %p, i32* %q, i32 %a, i32 %b) {
 ; CHECK-LABEL: @test_diamond_simple(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[X1:%.*]] = icmp eq i32 [[A:%.*]], 0
-; CHECK-NEXT:    [[Z2:%.*]] = select i1 [[X1]], i32 [[B:%.*]], i32 0
-; CHECK-NEXT:    [[X2:%.*]] = icmp eq i32 [[B]], 0
-; CHECK-NEXT:    [[TMP0:%.*]] = or i32 [[A]], [[B]]
-; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i32 [[TMP0]], 0
-; CHECK-NEXT:    br i1 [[DOTNOT]], label [[TMP2:%.*]], label [[TMP1:%.*]]
-; CHECK:       1:
-; CHECK-NEXT:    [[SIMPLIFYCFG_MERGE:%.*]] = select i1 [[X2]], i32 [[Z2]], i32 1
-; CHECK-NEXT:    store i32 [[SIMPLIFYCFG_MERGE]], i32* [[P:%.*]], align 4
-; CHECK-NEXT:    br label [[TMP2]]
+; CHECK-NEXT:    [[X2:%.*]] = icmp eq i32 [[B:%.*]], 0
+; CHECK-NEXT:    [[TMP0:%.*]] = or i32 [[B]], [[A:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[TMP1]], label [[TMP3:%.*]], label [[TMP2:%.*]]
 ; CHECK:       2:
-; CHECK-NEXT:    [[Z4:%.*]] = select i1 [[X2]], i32 [[Z2]], i32 3
+; CHECK-NEXT:    [[NOT_X2:%.*]] = xor i1 [[X2]], true
+; CHECK-NEXT:    [[SIMPLIFYCFG_MERGE:%.*]] = zext i1 [[NOT_X2]] to i32
+; CHECK-NEXT:    store i32 [[SIMPLIFYCFG_MERGE]], i32* [[P:%.*]], align 4
+; CHECK-NEXT:    br label [[TMP3]]
+; CHECK:       3:
+; CHECK-NEXT:    [[Z4:%.*]] = select i1 [[X2]], i32 0, i32 3
 ; CHECK-NEXT:    ret i32 [[Z4]]
 ;
 entry:
   %x1 = icmp eq i32 %a, 0
   br i1 %x1, label %no1, label %yes1
 
 yes1:
   store i32 0, i32* %p