CodeGenPrepare: Avoid and/or i1 in select conditions.

[MatzeB]

Summary

Thanks for the comments chandler.

I extracted the visitAND/visitOR refactoring to http://reviews.llvm.org/D8026. This new version only deals with the select DAG combines:

This is based on the following equivalences:
select(C0 & C1, X, Y) <=> select(C0, select(C1, X, Y), Y)
select(C0 | C1, X, Y) <=> select(C0, X, select(C1, X, Y))

Many target cannot perform and/or on the CPU flags and therefore the
right side should be choosen to avoid materializign the i1 flags in an
integer register. If the target can perform this operation efficiently
we normalize to the left form.

[ab]

I should note that this would have been useful as a DAGCombine as
well, because for instance on X86, (select (fcmp oeq/une)) is lowered
into the pattern matched here.

Matthias tells me doing it as a DAGCombine was frowned upon (why?), so
I'm doing pretty much the same thing on X86ISD::CMOV nodes, and will
submit shortly.
-Ahmed

[hfinkel]

In D7622#123459, @ab wrote:

I should note that this would have been useful as a DAGCombine as
well, because for instance on X86, (select (fcmp oeq/une)) is lowered
into the pattern matched here.

Matthias tells me doing it as a DAGCombine was frowned upon (why?),

I also don't understand why this would not be done in DAGCombine. It is basic-block local, and concerns itself with type legality, it seems appropriate for DAGCombine. One complication with DAGCombine is, if SELECT is not legal, then matching this might be hard.

so
I'm doing pretty much the same thing on X86ISD::CMOV nodes, and will
submit shortly.
-Ahmed

[MatzeB]

We discussed this in IRC, and I think chandler (and you?) told me that DAGCombine is supposed to normalize in a target independent way, as this normalization should or should not be done depending on the target I was told to do it in CodeGenPrepare...

Legality should not be a problem here as there is already a select instruction in use, I don't see why duplicating this select with a different condition (but same true/false input) could not be legal.

• Matthias

[MatzeB]

New version performing the transformation as a DAGCombine operation instead of CodeGenPrepare.

[MatzeB]

The commit message for this:

DAGCombine: Canonicalize select(and/or,x,y) depending on target.

This is based on the following equivalences:
select(C0 & C1, X, Y) <=> select(C0, select(C1, X, Y), Y)
select(C0 | C1, X, Y) <=> select(C0, X, select(C1, X, Y))

Many target cannot perform and/or on the CPU flags and therefore the
right side should be choosen to avoid materializign the i1 flags in an
integer register. If the target can perform this operation efficiently
we normalize to the left form.

Canonicalizing to nested selects has the problem that the and/or in the
conditions is only implcit afterwards, so this patch factors our bigger
parts of the and/or DAGCombiners so they can be applied to nested
selects as well.

[chandlerc]

There is no context in the diff, and there appears to be a bunch of unrelated code motion mixed in with the change. Fixing those issues would make it much easier to review.

If the code motion doesn't change any behavior but makes it easier to fit this into the DAG combine, just submit the no-op code motion change first and base this patch off that?

[hfinkel]

include/llvm/Target/TargetLowering.h

1095

I think it makes more sense to make this default to:

!hasMultipleConditionRegisters()

because if a target has multiple condition registers, then it probably has operations on those registers.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4714 ↗

(On Diff #21077)

Range-based for?

lib/Target/PowerPC/PPCISelLowering.h

624

This needs to default to !Subtarget.useCRBits() (so you might need to move the implementation into the PPCISelLowering.cpp).

Better yet, if you use hasMultipleConditionRegisters() for the default implementation (which I think you should), then you don't need this at all.

[MatzeB]

Thanks for the review Hal, the new version uses hasMultipleConditionRegisters() as default.

Comment at: lib/CodeGen/SelectionDAG/DAGCombiner.cpp:4714
@@ +4713,3 @@
+ const SDNode *Node = Value.getNode();
+ for (auto I = Node->use_begin(), E = Node->use_end(); I != E; ++I) {

+ const SDUse &Use = I.getUse();

Range-based for?

A range based for prohibits me from doing I.getUse() above as I can't access the iterator anymore.

[hfinkel]

In D7622#134397, @MatzeB wrote:

Thanks for the review Hal, the new version uses hasMultipleConditionRegisters() as default.

Comment at: lib/CodeGen/SelectionDAG/DAGCombiner.cpp:4714
@@ +4713,3 @@
+ const SDNode *Node = Value.getNode();
+ for (auto I = Node->use_begin(), E = Node->use_end(); I != E; ++I) {

+ const SDUse &Use = I.getUse();

Range-based for?

A range based for prohibits me from doing I.getUse() above as I can't access the iterator anymore.

Ah, alright.

include/llvm/Target/TargetLowering.h

1094

You should update the comment also. I'd say:

// If a target has multiple condition registers, then it likely has logical operations on those registers.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4716 ↗

(On Diff #21217)

Don't you want to check that it is used as the condition operand of the select?

[MatzeB]

Thanks Hal,

good points. Addressed in this update.

Thanks,
Matthias

[hfinkel]

LGTM.

[MatzeB]

Thanks again for the review. I can't commit this yet though as it depends on http://reviews.llvm.org/D8026

[MatzeB]

After looking at some more examples I tweaked the code some more:

• I'm not checking for hasOnlySelectAsUser() anymore. The fact that we have only select users means that we could get rid of the extra register and the SETCC but we produce an extra select instruction for each of the users, this is not necessarily better so I changed to the conservative hasOneUser().
• Tweak the callback to not cover types that need multiple registers as those will typically be broken down into multiple select-like instructions.

[hfinkel]

include/llvm/Target/TargetLowering.h

1113

Tweak the callback to not cover types that need multiple registers as those will typically be broken down into multiple select-like instructions.

Normally, to check this condition, we'd just use:

isTypeLegal(VT)

[MatzeB]

include/llvm/Target/TargetLowering.h

1113

But that will report false for types like i8 and i16 on many target even though we will end up with a single select like instruction. What about?

LegalizeTypeAction Action = getTypeAction(Context, VT);
return Action != TypeExpandInteger && Action != TYpeExpandFloat &&
  Action != TypeSplitVector

[hfinkel]

include/llvm/Target/TargetLowering.h

1113

Sure; seems reasonable to me. Go ahead whenever you're ready.

[michele.scandale]

Hi all,

working on compiler-rt for an out-of-tree target I found an issue related to this commit. I was able to reproduce it using the Mips backend. Please have a look to the inline comments.

Thanks in advance.

-Michele

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4853–4854 ↗

(On Diff #21383)

fixunsxfdi.ll1 KBDownload

Running "llc -O3" on the attached example I reach the following assertion

llc: /home/scandale/devel/pure-llvm/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:3204: llvm::SDValue llvm::SelectionDAG::getNode(unsigned int, llvm::SDLoc, llvm::EVT, llvm::SDValue, llvm::SDValue, bool, bool, bool): Assertion `N1.getValueType() == N2.getValueType() && N1.getValueType() == VT && "Binary operator types must match!"' failed.
#0 0x1997d75 llvm::sys::PrintStackTrace(llvm::raw_ostream&) /home/scandale/devel/pure-llvm/llvm/lib/Support/Unix/Signals.inc:425:0
#1 0x19980f1 PrintStackTraceSignalHandler(void*) /home/scandale/devel/pure-llvm/llvm/lib/Support/Unix/Signals.inc:483:0
#2 0x1996cc9 SignalHandler(int) /home/scandale/devel/pure-llvm/llvm/lib/Support/Unix/Signals.inc:199:0
#3 0x7f677b48e740 __restore_rt (/usr/lib/libpthread.so.0+0x10740)
#4 0x7f677a6ce4b7 __GI_raise (/usr/lib/libc.so.6+0x334b7)
#5 0x7f677a6cf88a __GI_abort (/usr/lib/libc.so.6+0x3488a)
#6 0x7f677a6c741d __assert_fail_base (/usr/lib/libc.so.6+0x2c41d)
#7 0x7f677a6c74d2 (/usr/lib/libc.so.6+0x2c4d2)
#8 0x181f0cb llvm::SelectionDAG::getNode(unsigned int, llvm::SDLoc, llvm::EVT, llvm::SDValue, llvm::SDValue, bool, bool, bool) /home/scandale/devel/pure-llvm/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:3203:0
#9 0x17781ae (anonymous namespace)::DAGCombiner::visitSELECT(llvm::SDNode*) /home/scandale/devel/pure-llvm/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:4888:0

This is because the condition values of the two select nodes have different types, thus we cannot create an AND between them.

A quick workaround is to check also that the types of the two conditions are the same. An alternative could be to extend one of the condition to have homogeneous types.

4872–4873 ↗

(On Diff #21383)

Same issue of lines 4853-4854...

[MatzeB]

I would be fine with either skipping the transformation if the types don't match up or extending the types. I personally would lean towards skipping the transformation as the extension is an extra instruction which makes the transformation less beneficial. As none of the targets I know are affected, what would the preference for your target?

• Matthias

[michele.scandale]

In D7622#154957, @MatzeB wrote:

I would be fine with either skipping the transformation if the types don't match up or extending the types. I personally would lean towards skipping the transformation as the extension is an extra instruction which makes the transformation less beneficial. As none of the targets I know are affected, what would the preference for your target?

• Matthias

The previous example was showing the issue using the in-tree Mips backend.
Btw, the behavior of the target I am working on is quite close to Mips. On the proposed example it is better to skip the transformation when the two condition are not homogeneous.

-Michele

[MatzeB]

I fixed this in r234763.

include/llvm/Target/TargetLowering.h

   virtual LoadInst *lowerIdempotentRMWIntoFencedLoad(AtomicRMWInst *RMWI) const {
     return nullptr;
   }
+
+  /// Returns true if we should normalize
+  /// select(N0&N1, X, Y) => select(N0, select(N1, X, Y), Y) and
+  /// select(N0|N1, X, Y) => select(N0, select(N1, X, Y, Y)) if it is likely
+  /// that it saves us from materializing N0 and N1 in an integer register.
+  /// Targets that are able to perform and/or on flags should return false here.
+  virtual bool shouldNormalizeToSelectSequence(const SelectInst &SI) const {
+    (void)SI;
+    // If SELECTs are expensive then we should not do this.
+    return !isSelectExpensive();
+  }
+
   //===--------------------------------------------------------------------===//
   // TargetLowering Configuration Methods - These methods should be invoked by
   // the derived class constructor to configure this object for the target.

lib/CodeGen/CodeGenPrepare.cpp

     bool OptimizeCallInst(CallInst *CI, bool& ModifiedDT);
     bool MoveExtToFormExtLoad(Instruction *&I);
     bool OptimizeExtUses(Instruction *I);
+    bool OptimizeSelectAndOr(SelectInst &SI);
     bool OptimizeSelectInst(SelectInst *SI);
     bool OptimizeShuffleVectorInst(ShuffleVectorInst *SI);
     bool OptimizeExtractElementInst(Instruction *Inst);

           (isa<LoadInst>(CmpOp1) && CmpOp1->hasOneUse()));
 }
 
+/// Test whether @p CondVal is a tree of And/Or/Compare instructions. If it is
+/// not then it is hard to decide whether breaking selects apart is helpful.
+static bool isTreeOfAndOrCompare(const Value &CondVal) {
+  if (!CondVal.hasOneUse())
+    return false;
+
+  const Instruction *CondInstr = dyn_cast<const Instruction>(&CondVal);
+  if (CondInstr == nullptr)
+    return false;
+  switch (CondInstr->getOpcode()) {
+  case Instruction::ICmp:
+  case Instruction::FCmp:
+    return true;
+  case Instruction::And:
+  case Instruction::Or: {
+    const Value *Op0 = CondInstr->getOperand(0);
+    const Value *Op1 = CondInstr->getOperand(1);
+    return isTreeOfAndOrCompare(*Op0) && isTreeOfAndOrCompare(*Op1);
+  }
+  default:
+    return false;
+  }
+}
+
+/// Transform select with And/Or in the Condition into a sequence of select
+/// instructions if profitable for the target:
+/// select((N0 & N1), a, b) => select(N0, select(N1, a, b), b)
+/// select((N0 | N1), a, b) => select(N0, a, select(N1, a, b))
+bool CodeGenPrepare::OptimizeSelectAndOr(SelectInst &SI) {
+  Value *Condition = SI.getCondition();
+  Instruction *CondI = dyn_cast<Instruction>(Condition);
+  if (CondI == nullptr)
+    return false;
+  unsigned Opcode = CondI->getOpcode();
+  if (Opcode != Instruction::And && Opcode != Instruction::Or)
+    return false;
+  if (!TLI || !TLI->shouldNormalizeToSelectSequence(SI))
+    return false;
+
+  // If any of the conditions gets materialized in an integer register anyway
+  // then the transformation is not helpful. We conservatively approximate this
+  // by checking whether we have a tree of And/Or/Compare instructions.
+  if (!isTreeOfAndOrCompare(*CondI))
+    return false;
+
+  IRBuilder<> Builder(SI.getContext());
+  Builder.SetInsertPoint(&SI);
+  Value *N0 = CondI->getOperand(0);
+  Value *N1 = CondI->getOperand(1);
+  Value *TrueVal = SI.getTrueValue();
+  Value *FalseVal = SI.getFalseValue();
+  Value *InnerSelect = Builder.CreateSelect(N1, TrueVal, FalseVal,
+                                            SI.getName()+".0");
+  SI.setOperand(0, N0);
+  unsigned SelectOp = Opcode == Instruction::And ? 1 : 2;
+  SI.setOperand(SelectOp, InnerSelect);
+
+  // SI was the only user of CondI, we can remove it.
+  CondI->eraseFromParent();
+
+  // Optimize the new/changed select instructions.
+  if (SelectInst *InnerSelectSI = dyn_cast<SelectInst>(InnerSelect))
+    OptimizeSelectAndOr(*InnerSelectSI);
+  OptimizeSelectAndOr(SI);
+  return true;
+}
 
 /// If we have a SelectInst that will likely profit from branch prediction,
 /// turn it into a branch.
 bool CodeGenPrepare::OptimizeSelectInst(SelectInst *SI) {
+  bool Changed = OptimizeSelectAndOr(*SI);
+
   bool VectorCond = !SI->getCondition()->getType()->isIntegerTy(1);
 
   // Can we convert the 'select' to CF ?
   if (DisableSelectToBranch || OptSize || !TLI || VectorCond)
-    return false;
+    return Changed;
 
   TargetLowering::SelectSupportKind SelectKind;
   if (VectorCond)

     // Check if it is profitable to keep this 'select'.
     if (!TLI->isPredictableSelectExpensive() ||
         !isFormingBranchFromSelectProfitable(SI))
-      return false;
+      return Changed;
   }
 
   ModifiedDT = true;

   // Instruct OptimizeBlock to skip to the next block.
   CurInstIterator = StartBlock->end();
   ++NumSelectsExpanded;
-  return true;
+  Changed = true;
+  return Changed;
 }
 
 static bool isBroadcastShuffle(ShuffleVectorInst *SVI) {

lib/Target/PowerPC/PPCISelLowering.h

       return Ty->isArrayTy();
     }
 
+    /// No gain in select sequences as we can natively perform and/or on flag
+    /// registers.
+    bool shouldNormalizeToSelectSequence(const SelectInst &SI) const override {
+      return false;
+    }
+
   private:
 
     struct ReuseLoadInfo {

test/CodeGen/R600/or.ll

 ; EG: OR_INT {{\** *}}T{{[0-9]+\.[XYZW], PV\.[XYZW], PS}}
 
 ; SI: s_or_b64 s[{{[0-9]+:[0-9]+}}], s[{{[0-9]+:[0-9]+}}], s[{{[0-9]+:[0-9]+}}]
-define void @or_i1(float addrspace(1)* %out, float addrspace(1)* %in0, float addrspace(1)* %in1) {
+define void @or_i1(i32 addrspace(1)* %out, float addrspace(1)* %in0, float addrspace(1)* %in1) {
   %a = load float addrspace(1)* %in0
   %b = load float addrspace(1)* %in1
   %acmp = fcmp oge float %a, 0.000000e+00
   %bcmp = fcmp oge float %b, 0.000000e+00
   %or = or i1 %acmp, %bcmp
-  %result = select i1 %or, float %a, float %b
-  store float %result, float addrspace(1)* %out
+  %result = zext i1 %or to i32
+  store i32 %result, i32 addrspace(1)* %out
   ret void
 }
 

test/CodeGen/X86/jump_sign.ll

 ; PR13475
 ; If we have sub a, b and cmp b, a and the result of cmp is used
 ; by sbb, we should not optimize cmp away.
-define i32 @func_q(i32 %j.4, i32 %w, i32 %el) {
+define i32 @func_q(i32 %a0, i32 %a1, i32 %a2) {
 ; CHECK-LABEL: func_q:
 ; CHECK: cmp
 ; CHECK-NEXT: sbb
-  %tmp532 = add i32 %j.4, %w
-  %tmp533 = icmp ugt i32 %tmp532, %el
-  %tmp534 = icmp ult i32 %w, %el
-  %or.cond = and i1 %tmp533, %tmp534
-  %tmp535 = sub i32 %el, %w
-  %j.5 = select i1 %or.cond, i32 %tmp535, i32 %j.4
-  ret i32 %j.5
+  %1 = icmp ult i32 %a0, %a1
+  %2 = sub i32 %a1, %a0
+  %3 = select i1 %1, i32 -1, i32 0
+  %4 = xor i32 %2, %3
+  ret i32 %4
 }
 ; rdar://11873276
 define i8* @func_r(i8* %base, i32* nocapture %offset, i32 %size) nounwind {

test/CodeGen/X86/zext-sext.ll

   %tmp12 = add i64 %tmp11, 5089792279245435153
 
 ; CHECK:      addl  $2138875574, %e[[REGISTER_zext:[a-z0-9]+]]
-; CHECK:      movslq  %e[[REGISTER_zext]], [[REGISTER_sext:%r[a-z0-9]+]]
 ; CHECK:      cmpl  $-8608074, %e[[REGISTER_zext]]
+; CHECK:      movslq  %e[[REGISTER_zext]], [[REGISTER_sext:%r[a-z0-9]+]]
 ; CHECK-NOT:  [[REGISTER_zext]]
-; CHECK-DAG:  testl     %e[[REGISTER_zext]]
-; CHECK:      subq  %r[[REGISTER_zext]], [[REGISTER_sext]]
+; CHECK-DAG:  cmpl  $2138875573, %e[[REGISTER_zext]]
+; CHECK:      movq  [[REGISTER_sext]], [[REGISTER_sext2:%[a-z0-9]+]]
+; CHECK:      subq  %r[[REGISTER_zext]], [[REGISTER_sext2]]
 
   %tmp13 = sub i64 %tmp12, 2138875574
   %tmp14 = zext i32 %tmp4 to i64

test/Transforms/CodeGenPrepare/AArch64/select_and_or.ll

+; RUN: opt -mtriple=aarch64-unknown-unknown -codegenprepare -S -o - %s | FileCheck %s
+
+define i32 @select_or(i32 %a0, i32 %a1, i32 %a2, i32 %a3, i32 %a4) {
+; CHECK-LABEL: select_or
+; CHECK-NOT: and
+; CHECK-NOT: or
+; CHECK: select
+; CHECK: select
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = icmp ult i32 %a1, %a2
+  %or = or i1 %cmp0, %cmp1
+  %res = select i1 %or, i32 %a3, i32 %a4
+  ret i32 %res
+}
+
+@var32 = global i32 0
+
+define i32 @select_or2(i32 %a0, i32 %a1, i32 %a2, i32 %a3, i32 %a4) {
+; CHECK-LABEL: select_or2
+; CHECK: or
+; CHECK: select
+; CHECK-NOT: select
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = icmp ult i32 %a1, %a2
+  %or = or i1 %cmp0, %cmp1
+  %zero_one = zext i1 %or to i32
+  store volatile i32 %zero_one, i32* @var32
+  %res = select i1 %or, i32 %a3, i32 %a4
+  ret i32 %res
+}
+
+define i32 @select_and(i32 %a0, i32 %a1, float %a2, float %a3, i32 %a4, i32 %a5) {
+; CHECK-LABEL: select_and
+; CHECK-NOT: and
+; CHECK-NOT: or
+; CHECK: select
+; CHECK: select
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = fcmp uge float %a2, %a3
+  %or = and i1 %cmp0, %cmp1
+  %res = select i1 %or, i32 %a4, i32 %a5
+  ret i32 %res
+}
+
+define i32 @select_multi(i32 %a0, i32 %a1, float %a2, float %a3, i32 %a4, i32 %a5) {
+; CHECK-LABEL: select_multi
+; CHECK-NOT: and
+; CHECK-NOT: or
+; CHECK: select
+; CHECK: select
+; CHECK: select
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = icmp uge i32 %a4, %a1
+  %cmp2 = fcmp uge float %a2, %a3
+  %or = or i1 %cmp0, %cmp1
+  %and = and i1 %or, %cmp2
+  %res = select i1 %and, i32 %a4, i32 %a5
+  ret i32 %res
+}

test/Transforms/CodeGenPrepare/PowerPC/lit.local.cfg

+if not 'PowerPC' in config.root.targets:
+    config.unsupported = True
+

test/Transforms/CodeGenPrepare/PowerPC/select_and_or.ll

+; RUN: opt -mtriple=powerpc-unknown-unknown -codegenprepare -S -o - %s | FileCheck %s
+
+define i32 @select_or(i32 %a0, i32 %a1, i32 %a2, i32 %a3, i32 %a4) {
+; CHECK-LABEL: select_or
+; CHECK: or
+; CHECK: select
+; CHECK-NOT: select
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = icmp ult i32 %a1, %a2
+  %or = or i1 %cmp0, %cmp1
+  %res = select i1 %or, i32 %a3, i32 %a4
+  ret i32 %res
+}
+
+@var32 = global i32 0
+
+define i32 @select_or2(i32 %a0, i32 %a1, i32 %a2, i32 %a3, i32 %a4) {
+; CHECK-LABEL: select_or2
+; CHECK: or
+; CHECK: select
+; CHECK-NOT: select
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = icmp ult i32 %a1, %a2
+  %or = or i1 %cmp0, %cmp1
+  %zero_one = zext i1 %or to i32
+  store volatile i32 %zero_one, i32* @var32
+  %res = select i1 %or, i32 %a3, i32 %a4
+  ret i32 %res
+}
+
+define i32 @select_and(i32 %a0, i32 %a1, float %a2, float %a3, i32 %a4, i32 %a5) {
+; CHECK-LABEL: select_and
+; CHECK: and
+; CHECK: select
+; CHECK-NOT: select
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = fcmp uge float %a2, %a3
+  %or = and i1 %cmp0, %cmp1
+  %res = select i1 %or, i32 %a4, i32 %a5
+  ret i32 %res
+}
+
+define i32 @select_multi(i32 %a0, i32 %a1, float %a2, float %a3, i32 %a4, i32 %a5) {
+; CHECK-LABEL: select_multi
+; CHECK: or
+; CHECK: and
+; CHECK: select
+; CHECK-NOT: select
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = icmp uge i32 %a4, %a1
+  %cmp2 = fcmp uge float %a2, %a3
+  %or = or i1 %cmp0, %cmp1
+  %and = and i1 %or, %cmp2
+  %res = select i1 %and, i32 %a4, i32 %a5
+  ret i32 %res
+}

test/Transforms/CodeGenPrepare/X86/select_and_or.ll

+; RUN: opt -mtriple=x86_64-unknown-unknown -codegenprepare -S -o - %s | FileCheck %s
+
+define i32 @select_or(i32 %a0, i32 %a1, i32 %a2, i32 %a3, i32 %a4) {
+; CHECK-LABEL: select_or
+; CHECK-NOT: and
+; CHECK-NOT: or
+; CHECK: select
+; CHECK: select
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = icmp ult i32 %a1, %a2
+  %or = or i1 %cmp0, %cmp1
+  %res = select i1 %or, i32 %a3, i32 %a4
+  ret i32 %res
+}
+
+@var32 = global i32 0
+
+define i32 @select_or2(i32 %a0, i32 %a1, i32 %a2, i32 %a3, i32 %a4) {
+; CHECK-LABEL: select_or2
+; CHECK: or
+; CHECK: select
+; CHECK-NOT: select
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = icmp ult i32 %a1, %a2
+  %or = or i1 %cmp0, %cmp1
+  %zero_one = zext i1 %or to i32
+  store volatile i32 %zero_one, i32* @var32
+  %res = select i1 %or, i32 %a3, i32 %a4
+  ret i32 %res
+}
+
+define i32 @select_and(i32 %a0, i32 %a1, float %a2, float %a3, i32 %a4, i32 %a5) {
+; CHECK-LABEL: select_and
+; CHECK-NOT: and
+; CHECK-NOT: or
+; CHECK: select
+; CHECK: select
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = fcmp uge float %a2, %a3
+  %or = and i1 %cmp0, %cmp1
+  %res = select i1 %or, i32 %a4, i32 %a5
+  ret i32 %res
+}
+
+define i32 @select_multi(i32 %a0, i32 %a1, float %a2, float %a3, i32 %a4, i32 %a5) {
+; CHECK-LABEL: select_multi
+; CHECK-NOT: and
+; CHECK-NOT: or
+; CHECK: select
+; CHECK: select
+; CHECK: select
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = icmp uge i32 %a4, %a1
+  %cmp2 = fcmp uge float %a2, %a3
+  %or = or i1 %cmp0, %cmp1
+  %and = and i1 %or, %cmp2
+  %res = select i1 %and, i32 %a4, i32 %a5
+  ret i32 %res
+}