[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

4865

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

192

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

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2642–2649

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

[aqjune]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2642–2649

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

4865

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

2632

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

2640

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

2640

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

2640

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

Feel free to already land this part separately.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2640

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

2640

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

16–18

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

126–127

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

228–229

Same here, previous output was wrong.

[aqjune]

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

126–127

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/include/llvm/IR/PatternMatch.h

 //===- PatternMatch.h - Match on the LLVM IR --------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //

 /// Matches L && R either in the form of L & R or L ? R : false.
 /// Note that the latter form is poison-blocking.
 template <typename LHS, typename RHS>
 inline LogicalOp_match<LHS, RHS, Instruction::And>
 m_LogicalAnd(const LHS &L, const RHS &R) {
   return LogicalOp_match<LHS, RHS, Instruction::And>(L, R);
 }
 
+template <typename LHS, typename RHS>
+inline auto m_c_LogicalAnd(const LHS &L, const RHS &R) {
+  return m_CombineOr(m_LogicalAnd(L, R), m_LogicalAnd(R, L));
+}
+
 /// Matches L || R either in the form of L | R or L ? true : R.
 /// Note that the latter form is poison-blocking.
 template <typename LHS, typename RHS>
 inline LogicalOp_match<LHS, RHS, Instruction::Or>
 m_LogicalOr(const LHS &L, const RHS &R) {
   return LogicalOp_match<LHS, RHS, Instruction::Or>(L, R);
 }
 
 /// Matches L || R where L and R are arbitrary values.
 inline auto m_LogicalOr() {
   return m_LogicalOr(m_Value(), m_Value());
 }
 
+template <typename LHS, typename RHS>
+inline auto m_c_LogicalOr(const LHS &L, const RHS &R) {
+  return m_CombineOr(m_LogicalOr(L, R), m_LogicalOr(R, L));
+}
+
 } // end namespace PatternMatch
 } // end namespace llvm
 
 #endif // LLVM_IR_PATTERNMATCH_H

llvm/lib/Analysis/ValueTracking.cpp

 //===- ValueTracking.cpp - Walk computations to compute properties --------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (const auto *I = dyn_cast<Instruction>(V)) {
     if (propagatesPoison(cast<Operator>(I)))
       return any_of(I->operands(), [=](const Value *Op) {
         return directlyImpliesPoison(ValAssumedPoison, Op, Depth + 1);
       });
 
     // V  = extractvalue V0, idx
     // V2 = extractvalue V0, idx2
     // V0's elements are all poison or not. (e.g., add_with_overflow)
     const WithOverflowInst *II;
     if (match(I, m_ExtractValue(m_WithOverflowInst(II))) &&
         match(ValAssumedPoison, m_ExtractValue(m_Specific(II))))
       return true;
+
+    // 'select ValAssumedPoison, _, _' is poison.
+    if (match(I, m_Select(m_Specific(ValAssumedPoison), m_Value(), m_Value())))
+      return true;
   }
   return false;
 }
 
 static bool impliesPoison(const Value *ValAssumedPoison, const Value *V,
                           unsigned Depth) {
   if (isGuaranteedNotToBeUndefOrPoison(ValAssumedPoison))
     return true;

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

 //===- InstCombineSelect.cpp ----------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (SelType->isIntOrIntVectorTy(1) &&
     // select a, !a, b -> select !a, b, false
     if (match(TrueVal, m_Not(m_Specific(CondVal))))
       return SelectInst::Create(TrueVal, FalseVal,
                                 ConstantInt::getFalse(SelType));
     // select a, b, !a -> select !a, true, b
     if (match(FalseVal, m_Not(m_Specific(CondVal))))
       return SelectInst::Create(FalseVal, ConstantInt::getTrue(SelType),
                                 TrueVal);
+
+    // select a, (a /\ b), false -> select a, b, false
+    Value *A, *B;
+    if (match(TrueVal, m_c_LogicalAnd(m_Specific(CondVal), m_Value(B))) &&
+        match(FalseVal, m_Zero()))
+      return replaceOperand(SI, 1, B);
+    // select a, true, (a \/ b) -> select a, true, b
+    if (match(TrueVal, m_One()) &&
+        match(FalseVal, m_c_LogicalOr(m_Specific(CondVal), m_Value(B))))
+      return replaceOperand(SI, 2, 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);
   }
 
   // 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.

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine-unsafe-select-transform=0 -instcombine -S | FileCheck %s
 
-; TODO: All of these should be optimized to a single instruction of select/
-; and/or.
-
 ; 1. --- X /\ (X /\ Y) ---
 
 define i1 @merge_logical_and_and(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_logical_and_and(
 ; CHECK-NEXT:    [[C:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %c = select i1 %X, i1 %Y, i1 false
   %res = and i1 %X, %c
   ret i1 %res
 }
 
 define i1 @merge_two_logical_ands(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_two_logical_ands(
 ; CHECK-NEXT:    [[RES:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = select i1 %X, i1 %Y, i1 false
   %res = select i1 %X, i1 %c, i1 false
   ret i1 %res
 }
 
 define i1 @merge_and_logical_and(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_and_logical_and(
-; CHECK-NEXT:    [[C:%.*]] = and i1 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[X]], i1 [[C]], i1 false
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = and i1 %X, %Y
   %res = select i1 %X, i1 %c, i1 false
   ret i1 %res
 }
 
 ; 2. --- X /\ (Y /\ X) ---
 
 ; This can be optimized to 'and i1 %X, %Y'
 define i1 @merge_logical_and_and2(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_logical_and_and2(
 ; CHECK-NEXT:    [[C:%.*]] = select i1 [[Y:%.*]], i1 [[X:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %c = select i1 %Y, i1 %X, i1 false
   %res = and i1 %X, %c
   ret i1 %res
 }
 
 define i1 @merge_two_logical_ands2(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_two_logical_ands2(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP1]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 false
+; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = select i1 %Y, i1 %X, i1 false
   %res = select i1 %X, i1 %c, i1 false
   ret i1 %res
 }
 
 define i1 @merge_and_logical_and2(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_and_logical_and2(
-; CHECK-NEXT:    [[C:%.*]] = and i1 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[X]], i1 [[C]], i1 false
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = and i1 %Y, %X
   %res = select i1 %X, i1 %c, i1 false
   ret i1 %res
 }
 
 ; 3. --- (X /\ Y) /\ X ---
 
 define i1 @merge_logical_and_and3(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_logical_and_and3(
 ; CHECK-NEXT:    [[C:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %c = select i1 %X, i1 %Y, i1 false
   %res = and i1 %c, %X
   ret i1 %res
 }
 
 define i1 @merge_two_logical_ands3(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_two_logical_ands3(
 ; CHECK-NEXT:    [[C:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 false
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[C]], i1 [[X]], i1 false
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[C]]
 ;
   %c = select i1 %X, i1 %Y, i1 false
   %res = select i1 %c, i1 %X, i1 false
   ret i1 %res
 }
 
 ; This can be optimized to 'and i1 %X, %Y'
 define i1 @merge_and_logical_and3(i1 %X, i1 %Y) {

 ;
   %c = select i1 %Y, i1 %X, i1 false
   %res = and i1 %c, %X
   ret i1 %res
 }
 
 define i1 @merge_two_logical_ands4(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_two_logical_ands4(
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[Y:%.*]], i1 [[X:%.*]], i1 false
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[C]], i1 [[X]], i1 false
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[Y:%.*]], i1 [[X:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = select i1 %Y, i1 %X, i1 false
   %res = select i1 %c, i1 %X, i1 false
   ret i1 %res
 }
 
 ; This can be optimized to 'and i1 %X, %Y'
 define i1 @merge_and_logical_and4(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_and_logical_and4(
 ; CHECK-NEXT:    [[C:%.*]] = and i1 [[Y:%.*]], [[X:%.*]]

 ;
   %c = select i1 %X, i1 true, i1 %Y
   %res = select i1 %X, i1 true, i1 %c
   ret i1 %res
 }
 
 define i1 @merge_or_logical_or(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_or_logical_or(
-; CHECK-NEXT:    [[C:%.*]] = or i1 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[X]], i1 true, i1 [[C]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = or i1 %X, %Y
   %res = select i1 %X, i1 true, i1 %c
   ret i1 %res
 }
 
 ; 6. --- X \/ (Y \/ X) ---
 
 ; This can be optimized to 'or i1 %X, %Y'
 define i1 @merge_logical_or_or2(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_logical_or_or2(
 ; CHECK-NEXT:    [[C:%.*]] = select i1 [[Y:%.*]], i1 true, i1 [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %c = select i1 %Y, i1 true, i1 %X
   %res = or i1 %X, %c
   ret i1 %res
 }
 
 define i1 @merge_two_logical_ors2(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_two_logical_ors2(
-; CHECK-NEXT:    [[TMP1:%.*]] = or i1 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP1]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y:%.*]]
+; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = select i1 %Y, i1 true, i1 %X
   %res = select i1 %X, i1 true, i1 %c
   ret i1 %res
 }
 
 define i1 @merge_or_logical_or2(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_or_logical_or2(
-; CHECK-NEXT:    [[C:%.*]] = or i1 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[X]], i1 true, i1 [[C]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = or i1 %Y, %X
   %res = select i1 %X, i1 true, i1 %c
   ret i1 %res
 }
 
 ; 7. --- (X \/ Y) \/ X ---
 
 define i1 @merge_logical_or_or3(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_logical_or_or3(
 ; CHECK-NEXT:    [[C:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %c = select i1 %X, i1 true, i1 %Y
   %res = or i1 %c, %X
   ret i1 %res
 }
 
 define i1 @merge_two_logical_ors3(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_two_logical_ors3(
 ; CHECK-NEXT:    [[C:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[C]], i1 true, i1 [[X]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[C]]
 ;
   %c = select i1 %X, i1 true, i1 %Y
   %res = select i1 %c, i1 true, i1 %X
   ret i1 %res
 }
 
 ; This can be optimized to 'or i1 %Y, %X'
 define i1 @merge_or_logical_or3(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_or_logical_or3(
 ; CHECK-NEXT:    [[C:%.*]] = or i1 [[X:%.*]], [[Y:%.*]]

 ;
   %c = select i1 %Y, i1 true, i1 %X
   %res = or i1 %c, %X
   ret i1 %res
 }
 
 define i1 @merge_two_logical_ors4(i1 %X, i1 %Y) {
 ; CHECK-LABEL: @merge_two_logical_ors4(
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[Y:%.*]], i1 true, i1 [[X:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[C]], i1 true, i1 [[X]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[Y:%.*]], i1 true, i1 [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = select i1 %Y, i1 true, i1 %X
   %res = select i1 %c, i1 true, i1 %X
   ret i1 %res
 }
 
 ; This can be optimized to 'or i1 %Y, %X'