[InstCombine] Recognize and simplify three way comparison idioms

[anna]

Summary

Many languages have a three way comparison idiom where comparing two values
produces not a boolean, but a tri-state value. Typical values (e.g. as used in
the lcmp/fcmp bytecodes from Java) are -1 for less than, 0 for equality, and +1
for greater than.

We actually do a great job already of converting three way comparisons into
binary comparisons when the result produced has one a single use. Unfortunately,
such values can have more than one use, and in that case, our existing
optimizations break down.

The patch adds a peephole which converts a three-way compare + test idiom into a
binary comparison on the original inputs. It focused on replacing the test on
the result of the three way compare and does nothing about removing the three
way compare itself. That's left to other optimizations (which do actually kick
in commonly.)
We currently recognize one idiom on signed integer compare. In the future, we
plan to recognize and simplify other comparison idioms on
other signed/unsigned datatypes such as floats, vectors etc.

This is a resurrection of Philip Reames' original patch:
https://reviews.llvm.org/D19452

[anna]

Changed wrt Philip's original patch:

1. Adapted to get working with current API (obviously ;) )
2. Addressed review comments by Sanjoy.
3. CHECK pattern on tests were modified -- not a semantic modification, just syntactic, because we generate tmp compares now, not hardcoded compares.

[mkazantsev]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2454

We can check PredA right after we matched line 2450 to avoid further maching if we have a wrong comparison there.

2454

Maybe just another && instead of second if?

2474

Can we assert C on method entry?

2495

Is it possible that more than one of {TrueWhenLessThan, TrueWhenEqual, TrueWhenGreaterThan} is true?

If no, please add an assertion on that and use "else if" below.
If yes, should we not consider this when creating conditions?

[anna]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2454

agreed.

2474

yes. I'll move it.

2495

Yes, more than one can be true at a time: this actually enumerates all the possible 8 combinations, because of the chaining of these ORs in CreateOr. We pass in the Cond as the parameter.

(I actually liked this idea a lot: credit goes to Sanjoy in suggesting this in the original review).

Please see the comment above the code, should I perhaps clarify it more?

[mkazantsev]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2495

I've re-read the comment and the code, and I think it's fine, I just didn't realize the idea from the very beginning.

[anna]

addressed comments.

[mkazantsev]

LGTM.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2441

Why do we need this blank line?

2507

Same here.

lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombiner::foldICmpAddConstant(ICmpInst &Cmp,
   //       C2+1 is a power of 2
   if (Pred == ICmpInst::ICMP_UGT && (*C + 1).isPowerOf2() && (*C2 & *C) == 0)
     return new ICmpInst(ICmpInst::ICMP_NE, Builder->CreateAnd(X, ~(*C)),
                         ConstantExpr::getNeg(cast<Constant>(Y)));
 
   return nullptr;
 }
 
+bool InstCombiner::matchThreeWayIntCompare(SelectInst *SI, Value *&LHS,
+                                           Value *&RHS, ConstantInt *&Less,
+                                           ConstantInt *&Equal,
+                                           ConstantInt *&Greater) {
+
+  // TODO: Generalize this to work with other comparison idioms or ensure
+  // they get canonicalized into this form.
+
+  // select i1 (a == b), i32 Equal, i32 (select i1 (a < b), i32 Less, i32
+  // Greater), where Equal, Less and Greater are placeholders for any three
+  // constants.
+  ICmpInst::Predicate PredA, PredB;
+  if (match(SI->getTrueValue(), m_ConstantInt(Equal)) &&
+      match(SI->getCondition(), m_ICmp(PredA, m_Value(LHS), m_Value(RHS))) &&
+      match(SI->getFalseValue(),
+            m_Select(m_ICmp(PredB, m_Specific(LHS), m_Specific(RHS)),
+                     m_ConstantInt(Less), m_ConstantInt(Greater)))) {
+    if (PredA == ICmpInst::ICMP_EQ && PredB == ICmpInst::ICMP_SLT)
+      return true;
+  }
+  return false;
+}
+
+Instruction *InstCombiner::foldICmpSelectConstant(ICmpInst &Cmp,
+                                                  Instruction *Select,
+                                                  ConstantInt *C) {
+
+  // If we're testing a constant value against the result of a three way
+  // comparison, the result can be expressed directly in terms of the
+  // original values being compared.  Note: We could possibly be more
+  // aggressive here and remove the hasOneUse test. The original select is
+  // really likely to simplify or sink when we remove a test of the result.
+  Value *OrigLHS, *OrigRHS;
+  ConstantInt *C1LessThan, *C2Equal, *C3GreaterThan;
+  if (Cmp.hasOneUse() &&
+      matchThreeWayIntCompare(cast<SelectInst>(Select), OrigLHS, OrigRHS,
+                                 C1LessThan, C2Equal, C3GreaterThan)) {
+    assert(C1LessThan && C2Equal && C3GreaterThan && C);
+
+    bool TrueWhenLessThan =
+        ConstantExpr::getCompare(Cmp.getPredicate(), C1LessThan, C)
+            ->isAllOnesValue();
+    bool TrueWhenEqual =
+        ConstantExpr::getCompare(Cmp.getPredicate(), C2Equal, C)
+            ->isAllOnesValue();
+    bool TrueWhenGreaterThan =
+        ConstantExpr::getCompare(Cmp.getPredicate(), C3GreaterThan, C)
+            ->isAllOnesValue();
+
+    // This generates the new instruction that will replace the original Cmp
+    // Instruction. Instead of enumerating the various combinations when
+    // TrueWhenLessThan, TrueWhenEqual and TrueWhenGreaterThan are true versus
+    // false, we rely on chaining of ORs and future passes of InstCombine to
+    // simplify the OR further (i.e. a s< b || a == b becomes a s<= b).
+
+    // When none of the three constants satisfy the predicate for the RHS (C),
+    // the entire original Cmp can be simplified to a false.
+    Value *Cond = Builder->getFalse();
+    if (TrueWhenLessThan)
+      Cond = Builder->CreateOr(Cond, Builder->CreateICmp(ICmpInst::ICMP_SLT, OrigLHS, OrigRHS));
+    if (TrueWhenEqual)
+      Cond = Builder->CreateOr(Cond, Builder->CreateICmp(ICmpInst::ICMP_EQ, OrigLHS, OrigRHS));
+    if (TrueWhenGreaterThan)
+      Cond = Builder->CreateOr(Cond, Builder->CreateICmp(ICmpInst::ICMP_SGT, OrigLHS, OrigRHS));
+
+    return replaceInstUsesWith(Cmp, Cond);
+  }
+  return nullptr;
+
+}
+
 /// Try to fold integer comparisons with a constant operand: icmp Pred X, C
 /// where X is some kind of instruction.
 Instruction *InstCombiner::foldICmpInstWithConstant(ICmpInst &Cmp) {
   const APInt *C;
   if (!match(Cmp.getOperand(1), m_APInt(C)))
     return nullptr;
 
   BinaryOperator *BO;
if (match(Cmp.getOperand(0), m_BinOp(BO))) {
     default:
       break;
     }
     // TODO: These folds could be refactored to be part of the above calls.
     if (Instruction *I = foldICmpBinOpEqualityWithConstant(Cmp, BO, C))
       return I;
   }
 
+  // Match against CmpInst LHS being instructions other than binary operators.
   Instruction *LHSI;
-  if (match(Cmp.getOperand(0), m_Instruction(LHSI)) &&
-      LHSI->getOpcode() == Instruction::Trunc)
+  if (match(Cmp.getOperand(0), m_Instruction(LHSI))) {
+    switch (LHSI->getOpcode()) {
+    case Instruction::Select:
+      {
+      // For now, we only support constant integers while folding the
+      // ICMP(SELECT)) pattern. We can extend this to support vector of integers
+      // similar to the cases handled by binary ops above.
+      if (ConstantInt *ConstRHS = dyn_cast<ConstantInt>(Cmp.getOperand(1)))
+        if (Instruction *I = foldICmpSelectConstant(Cmp, LHSI, ConstRHS))
+          return I;
+      break;
+      }
+    case Instruction::Trunc:
       if (Instruction *I = foldICmpTruncConstant(Cmp, LHSI, C))
         return I;
+      break;
+    default:
+      break;
+    }
+  }
 
   if (Instruction *I = foldICmpIntrinsicWithConstant(Cmp, C))
     return I;
 
   return nullptr;
 }
 
 /// Fold an icmp equality instruction with binary operator LHS and constant RHS:

lib/Transforms/InstCombine/InstCombineInternal.h

private:
   Value *SimplifyUsingDistributiveLaws(BinaryOperator &I);
 
   /// This tries to simplify binary operations by factorizing out common terms
   /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
   Value *tryFactorization(InstCombiner::BuilderTy *, BinaryOperator &,
                           Instruction::BinaryOps, Value *, Value *, Value *,
                           Value *);
 
+  /// Match a select chain which produces one of three values based on whether
+  /// the LHS is less than, equal to, or greater than RHS respectively.
+  /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
+  /// Equal and Greater values are saved in the matching process and returned to
+  /// the caller.
+  bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
+                               ConstantInt *&Less, ConstantInt *&Equal,
+                               ConstantInt *&Greater);
+
   /// \brief Attempts to replace V with a simpler value based on the demanded
   /// bits.
   Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
                                  unsigned Depth, Instruction *CxtI);
   bool SimplifyDemandedBits(Instruction *I, unsigned Op,
                             const APInt &DemandedMask, KnownBits &Known,
                             unsigned Depth = 0);
   /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
private:
 
   Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
   Instruction *foldICmpWithConstant(ICmpInst &Cmp);
   Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
   Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
   Instruction *foldICmpBinOp(ICmpInst &Cmp);
   Instruction *foldICmpEquality(ICmpInst &Cmp);
 
+  Instruction *foldICmpSelectConstant(ICmpInst &Cmp, Instruction *Select,
+                                      ConstantInt *C);
   Instruction *foldICmpTruncConstant(ICmpInst &Cmp, Instruction *Trunc,
                                      const APInt *C);
   Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
                                    const APInt *C);
   Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
                                    const APInt *C);
   Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
                                   const APInt *C);

test/Transforms/InstCombine/compare-3way.ll

+; RUN: opt -S -instcombine < %s | FileCheck %s
+
+declare void @use(i32)
+
+; These 18 exercise all combinations of signed comparison
+; for each of the three values produced by your typical 
+; 3way compare function (-1, 0, 1)
+
+define void @test_low_sgt(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_low_sgt
+; CHECK: [[TMP1:%.*]] = icmp slt i64 %a, %b
+; CHECK: br i1 [[TMP1]], label %normal, label %unreached
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp sgt i32 %result, -1
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_low_slt(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_low_slt
+; CHECK: br i1 false, label %unreached, label %normal
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp slt i32 %result, -1
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_low_sge(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_low_sge
+; CHECK: br i1 true, label %unreached, label %normal
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp sge i32 %result, -1
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_low_sle(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_low_sle
+; CHECK: [[TMP1:%.*]] = icmp slt i64 %a, %b
+; CHECK: br i1 [[TMP1]], label %unreached, label %normal
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp sle i32 %result, -1
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_low_ne(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_low_ne
+; CHECK: [[TMP1:%.*]] = icmp slt i64 %a, %b
+; CHECK: br i1 [[TMP1]], label %normal, label %unreached
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp ne i32 %result, -1
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_low_eq(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_low_eq
+; CHECK: [[TMP1:%.*]] = icmp slt i64 %a, %b
+; CHECK: br i1 [[TMP1]], label %unreached, label %normal
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp eq i32 %result, -1
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_mid_sgt(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_mid_sgt
+; CHECK: [[TMP1:%.*]] = icmp sgt i64 %a, %b
+; CHECK: br i1 [[TMP1]], label %unreached, label %normal
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp sgt i32 %result, 0
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_mid_slt(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_mid_slt
+; CHECK: [[TMP1:%.*]] = icmp slt i64 %a, %b
+; CHECK: br i1 [[TMP1]], label %unreached, label %normal
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp slt i32 %result, 0
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_mid_sge(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_mid_sge
+; CHECK: [[TMP1:%.*]] = icmp slt i64 %a, %b
+; CHECK: br i1 [[TMP1]], label %normal, label %unreached
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp sge i32 %result, 0
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_mid_sle(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_mid_sle
+; CHECK: [[TMP1:%.*]] = icmp sgt i64 %a, %b
+; CHECK: br i1 [[TMP1]], label %normal, label %unreached
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp sle i32 %result, 0
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_mid_ne(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_mid_ne
+; CHECK: [[TMP1:%.*]] = icmp eq i64 %a, %b
+; CHECK: br i1 [[TMP1]], label %normal, label %unreached
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp ne i32 %result, 0
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_mid_eq(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_mid_eq
+; CHECK: icmp eq i64 %a, %b
+; CHECK: br i1 %eq, label %unreached, label %normal
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp eq i32 %result, 0
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_high_sgt(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_high_sgt
+; CHECK: br i1 false, label %unreached, label %normal
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp sgt i32 %result, 1
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_high_slt(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_high_slt
+; CHECK: [[TMP1:%.*]] = icmp sgt i64 %a, %b
+; CHECK: br i1 [[TMP1]], label %normal, label %unreached
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp slt i32 %result, 1
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_high_sge(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_high_sge
+; CHECK: [[TMP1:%.*]] = icmp sgt i64 %a, %b
+; CHECK: br i1 [[TMP1]], label %unreached, label %normal
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp sge i32 %result, 1
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_high_sle(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_high_sle
+; CHECK: br i1 true, label %unreached, label %normal
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp sle i32 %result, 1
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_high_ne(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_high_ne
+; CHECK: [[TMP1:%.*]] = icmp sgt i64 %a, %b
+; CHECK: br i1 [[TMP1]], label %normal, label %unreached
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp ne i32 %result, 1
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @test_high_eq(i64 %a, i64 %b) {
+; CHECK-LABEL: @test_high_eq
+; CHECK: [[TMP1:%.*]] = icmp sgt i64 %a, %b
+; CHECK: br i1 [[TMP1]], label %unreached, label %normal
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -1, i32 1
+  %result = select i1 %eq, i32 0, i32 %.
+  %cmp = icmp eq i32 %result, 1
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+; These five make sure we didn't accidentally hard code one of the
+; produced values
+
+define void @non_standard_low(i64 %a, i64 %b) {
+; CHECK-LABEL: @non_standard_low
+; CHECK: [[TMP1:%.*]] = icmp slt i64 %a, %b
+; CHECK: br i1 [[TMP1]], label %unreached, label %normal
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -3, i32 -1
+  %result = select i1 %eq, i32 -2, i32 %.
+  %cmp = icmp eq i32 %result, -3
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @non_standard_mid(i64 %a, i64 %b) {
+; CHECK-LABEL: @non_standard_mid
+; CHECK: icmp eq i64 %a, %b
+; CHECK: br i1 %eq, label %unreached, label %normal
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -3, i32 -1
+  %result = select i1 %eq, i32 -2, i32 %.
+  %cmp = icmp eq i32 %result, -2
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @non_standard_high(i64 %a, i64 %b) {
+; CHECK-LABEL: @non_standard_high
+; CHECK: [[TMP1:%.*]] = icmp sgt i64 %a, %b
+; CHECK: br i1 [[TMP1]], label %unreached, label %normal
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -3, i32 -1
+  %result = select i1 %eq, i32 -2, i32 %.
+  %cmp = icmp eq i32 %result, -1
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @non_standard_bound1(i64 %a, i64 %b) {
+; CHECK-LABEL: @non_standard_bound1
+; CHECK: br i1 false, label %unreached, label %normal
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -3, i32 -1
+  %result = select i1 %eq, i32 -2, i32 %.
+  %cmp = icmp eq i32 %result, -20
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}
+
+define void @non_standard_bound2(i64 %a, i64 %b) {
+; CHECK-LABEL: @non_standard_bound2
+; CHECK: br i1 false, label %unreached, label %normal
+  %eq = icmp eq i64 %a, %b
+  %slt = icmp slt i64 %a, %b
+  %. = select i1 %slt, i32 -3, i32 -1
+  %result = select i1 %eq, i32 -2, i32 %.
+  %cmp = icmp eq i32 %result, 0
+  br i1 %cmp, label %unreached, label %normal
+normal:
+  ret void
+unreached:
+  call void @use(i32 %result)
+  ret void
+}