[ValueTracking] Improve isImpliedCondition for conditions with matching operands.

[mcrosier]

Summary

This patch improves SimplifyCFG to catch things like:

if (a < b) {
  if (b < a) <- known to be false
    unreachable;
}

and

if (a > b) {
  if (b < a) { <- always true; remove control flow
    always reachable;
  }
}

The later case is generally captured when the compares are canonicalized, but in my testing I found that there are cases in the wild where compares aren't always in canonical form. I do plan on addressing the FIXME in jump threading, but I wanted to get this patch approved first.

Please take a look,
Chad

[mcrosier]

test/Transforms/SimplifyCFG/implied-cond-swapped.ll

40 ↗

(On Diff #53063)

This should be (b < a). I've already updated my local version. The IR itself is correct.

[mcrosier]

This is an optimization identified by Souper.

[sanjoy]

include/llvm/Analysis/ValueTracking.h

440

I'd use something a little more descriptive -- maybe ImpliedTrue?

The Right(TM) fix here is to change isImpliedCondition to return Optional<bool>, but I don't know how much work that will be.

lib/Analysis/ValueTracking.cpp

3818

Minor: no braces need here.

lib/Transforms/Utils/SimplifyCFG.cpp

2733–2735

Huh? Why static ?

[sanjoy]

lib/Analysis/ValueTracking.cpp

3815

I'm not sure this is correct for "or equal" predicates -- A >= B does not imply !(B >= A) since if A == B then both of these are true.

[mcrosier]

Address Sanjoy's comments.

[mcrosier]

Thanks for the speedy feedback, Sanjoy!

include/llvm/Analysis/ValueTracking.h

440

I've updated everything to ImpliedTrue. Mind if I defer the second suggestion? :)

lib/Analysis/ValueTracking.cpp

3815

You're absolutely correct. Thanks!!

lib/Transforms/Utils/SimplifyCFG.cpp

2733–2736

cut-pasteo. Removed.

[sanjoy]

include/llvm/Analysis/ValueTracking.h

440

SGTM.

But I'd change the doxygen comment slightly -- 'depending on the value of ImpliedTrue' -> 'depending on what is returned in ImpliedTrue', to make it obvious that ImpliedTrue is a return parameter.

lib/Analysis/InstructionSimplify.cpp

2134

I didn't notice these last time, but I'm not sure if this usage is correct (or will remain correct, even if they're correct in practice after this patch :)): isImpliedCondition will return true with ImpliedTrue set to false if RHS -> NOT(LHS). But in that case you're simplifying RHS -> LHS to false, meaning you're asserting NOT(RHS -> LHS). NOT(RHS -> LHS) is not the same as RHS -> NOT(LHS) if RHS is false.

[mcrosier]

Address Sanjoy's comments:
-Update comment to make it more explicit that ImpliedTrue is a return value.
-Correct the logic in InstSimplify.

[mcrosier]

-Make this patch much more general by not insisting the operands be swapped.
-Address the FIXME by handling the remaining comparisons (e.g., A == B implies A >B, A <B, and A != B are false, etc.).

Passes all correctness test for the test-suite, SPEC200X, EEMBC and a clang bootstrap.

I believe this is in pretty good shape.

Chad

[sanjoy]

lib/Analysis/ValueTracking.cpp

3830

This scares me. Can you use a different variable name for APred and BPred here, like UnsignedAPred?

3857

Won't this return true for A ugt B => NOT(A sle B) (since you unconditionally coerced both to the unsigned variants) (consider A = -1, B = 0)?

[mcrosier]

Thanks for the feedback, Sanjoy. Let me know if my comments make sense. I'll upload a new diff shortly.

lib/Analysis/ValueTracking.cpp

3830

Sure, no problem. I don't want to scare anyone. :)

3857

See my comment below about checking to make sure the predicates share the same sign, if they're signed. I believe such a check would avoid this situation.

3924

At minimum, I'm thinking we need a check here to make sure both compares have the same sign (or at least one compare is an equality check, which has no sign).

We don't think we want 'icmp ugt a, b' to imply 'icmp sgt b, a' is false, for example.

I'll add tests cases.

[mcrosier]

Address Sanjoy's feedback by:
-Renaming predicates that are unconditionally converted to unsigned predicate.
-Add a check to make sure we're never comparing predicates of different signs (with associated test case).

[gberry]

Added a couple of comments, still looking over other bits of the change...

lib/Analysis/ValueTracking.cpp

3907–3910

The value returned in ImpliedTrue is undefined (and may be checked by the caller) if this path is taken.

lib/Transforms/Scalar/JumpThreading.cpp

938

This seems like an easy thing to go ahead and fix. Just factor out the 0 and 1 successor indices above and swap them if ImpliedTrue is false, right?

[mcrosier]

Address Geoff's comments:
-Fix undef of IsImpliedCond when LHS == RHS
-Enable changes in jump threading

[gberry]

lib/Analysis/ValueTracking.cpp

3803

Perhaps this function could be simplified by canonicalizing to the IsMatchingOps case at the beginning:

if (IsSwappedOps) {
  std::swap(BLHS, BRHS);
  BPred = ICmpInst::getSwappedPredicate(BPred);
}

Then you don't need to consider the IsSwappedOps cases below.

3927

This check seems like it should be pushed down into isImpliedCondMatchingOperands since it doesn't necessarily apply to isImpliedCondOperands? I feel like maybe I'm missing something here.

3935

I don't follow why this check needs to be added when isImpliedCondOperands has not been changed.

[mcrosier]

lib/Analysis/ValueTracking.cpp

3803

Sure. I'll need to add the cases to the switch at the bottom, but I agree it will likely make the code less confusing.

3927

Based on experiments with InstCombine, I believe this condition must always be true to infer anything about the two conditions. My expectation is that other improvements will come along (e.g., D19073) that also require this check. Therefore, I went ahead an put the check here, rather than in isImpliedCondMatchingOperands(), to make sure I or others don't miss this important requirement in the future.

I can sink it if you like, but I expect my follow on patches will just pull this logic back out.

3935

if you're referring to

if (APred == BPred) {

that check is not new. :)

[mcrosier]

Address Geoff's comments:
-Canonicalize operands so they match to simplify logic.

Other minor refactoring.

[gberry]

lib/Analysis/ValueTracking.cpp

3935

Ah, okay, I misread the diff before.

[bmakam]

test/Transforms/SimplifyCFG/implied-cond-matching.ll

116

Won't this be always reachable?

[bmakam]

test/Transforms/SimplifyCFG/implied-cond-matching.ll

116

Please ignore this comment, this should be always unreachable

[bmakam]

Perhaps instcombine is a better place to catch this? I verified PR23333 could be caught by this approach. While improving D18841 I could handle PR23333 and almost all the cases mentioned in here except for test_gt, test_ltand test_eq. I can easily handle these cases but I have currently limited D18841 to the immediate dominator of depth 1 in favor of walking the entire dominator tree for compile-time tradeoff. I am not sure which approach is better. Perhaps you could improve this to also handle PR23333 and other tests in D18841 or perhaps both solutions could co-exist.

[mcrosier]

In D18905#402690, @bmakam wrote:

Perhaps instcombine is a better place to catch this? I verified PR23333 could be catched by this approach. While improving D18841 I could handle PR23333 and almost all the cases mentioned in here except for test_gt, test_ltand test_eq. I can easily handle these cases but I have currently limited D18841 to the immediate dominator of depth 1 in favor of walking the entire dominator tree for compile-time tradeoff. I am not sure which approach is better. Perhaps you could improve this to also handle PR23333 and other tests in D18841 or perhaps both solutions could co-exist.

I think the right plan of attack is to implement this logic here and then have other passes use the isImpliedCondition() API as is already done in SimplifyCFG, Jump Threading, and InstSimplify.

The logic added in this patch can prove that the first condition in PR23333 implies the second. It will also catch the test cases in D18841 if isImpliedCondition() were used in InstCombine as you suggest.

[sanjoy]

lib/Analysis/ValueTracking.cpp

3801

I'd change the comment to be in terms of the formal parameters (i.e. APred, ARHS etc.) to make things more obvious.

3832

Nit: I'd use auto here.

3834

This does not need to happen in this change, but it really looks like this logic is general enough to live in CmpInst along with things like isTrueWhenEqual as CmpInst::isImpliedPredicate.

3838

Can't you use CmpInst::isFalseWhenEqual here?

3876

Some of this boilerplate can be removed by checking if getInversePredicate(APred) == BPred outside the switch.

3907–3911

This is why I'd have liked an Optional<bool> return value. :) Avoids mistakes like these.

3926

I wouldn't do the check here, since it isn't obvious how this check relates to isImpliedCondMatchingOperands or even why the precondition is needed. Instead, I'll change the assert in isImpliedCondMatchingOperands to return false if the predicates are not comparable.

[mcrosier]

Address Sanjoy's comments.

[mcrosier]

lib/Analysis/ValueTracking.cpp

3834

I'll need to investigate. Thanks for the suggestion, Sanjoy.

3907–3911

:/ I'll address this in a follow up commit.

[sanjoy]

lgtm with two nits inline

Other than that I'll urge you to try to refactor the tricky predicate logic in isImpliedCondMatchingOperands into CmpInst soon.

lib/Analysis/ValueTracking.cpp

3829

Nit: I'd just inline the body here. PredicatesComparable isn't terribly descriptive or general, and the function is a two liner anyway.

3842

Please verify this, but I don't think you need to enumerate the predicates here, and you don't even need to guard this under PredicatesComparable. You can just straightforwardly do;

if (CmpInst::getInversePredicate(UnsignedAPred) == UnsignedBPred) {
  ImpliedTrue = false;
  return true;
}

[mcrosier]

Thanks, Sanjoy. I'll follow up on your suggestions shortly.

Committed r266767.

[mcrosier]

In D18905#404808, @sanjoy wrote:

I'll urge you to try to refactor the tricky predicate logic in isImpliedCondMatchingOperands into CmpInst soon.

Please let me know if D19330 is along the lines of what you were suggesting, Sanjoy.

include/llvm/Analysis/ValueTracking.h

template <typename T> class ArrayRef;
   SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS,
                                          Instruction::CastOps *CastOp = nullptr);
 
   /// Parse out a conservative ConstantRange from !range metadata.
   ///
   /// E.g. if RangeMD is !{i32 0, i32 10, i32 15, i32 20} then return [0, 20).
   ConstantRange getConstantRangeFromMetadata(MDNode &RangeMD);
 
-  /// Return true if RHS is known to be implied by LHS.  A & B must be i1
-  /// (boolean) values or a vector of such values. Note that the truth table for
-  /// implication is the same as <=u on i1 values (but not <=s!).  The truth
-  /// table for both is:
+  /// Return true if RHS is known to be implied by LHS.  The implication may be
+  /// either true or false depending on what is returned in ImpliedTrue.
+  /// A & B must be i1 (boolean) values or a vector of such values. Note that
+  /// the truth table for implication is the same as <=u on i1 values (but not
+  /// <=s!).  The truth table for both is:
   ///    | T | F (B)
   ///  T | T | F
   ///  F | T | T
   /// (A)
-  bool isImpliedCondition(Value *LHS, Value *RHS, const DataLayout &DL,
-                          unsigned Depth = 0, AssumptionCache *AC = nullptr,
+  bool isImpliedCondition(Value *LHS, Value *RHS, bool &ImpliedTrue,
+                          const DataLayout &DL, unsigned Depth = 0,
+                          AssumptionCache *AC = nullptr,
                           const Instruction *CxtI = nullptr,
                           const DominatorTree *DT = nullptr);
 } // end namespace llvm
 
 #endif

lib/Analysis/InstructionSimplify.cpp

case ICmpInst::ICMP_NE:
       if (match(RHS, m_Zero()))
         return LHS;
       break;
     case ICmpInst::ICMP_UGT:
       // X >u 0 -> X
       if (match(RHS, m_Zero()))
         return LHS;
       break;
-    case ICmpInst::ICMP_UGE:
+    case ICmpInst::ICMP_UGE: {
       // X >=u 1 -> X
       if (match(RHS, m_One()))
         return LHS;
-      if (isImpliedCondition(RHS, LHS, Q.DL))
+      bool ImpliedTrue;
+      if (isImpliedCondition(RHS, LHS, ImpliedTrue, Q.DL) && ImpliedTrue)
         return getTrue(ITy);
       break;
-    case ICmpInst::ICMP_SGE:
+    }
+    case ICmpInst::ICMP_SGE: {
       /// For signed comparison, the values for an i1 are 0 and -1
       /// respectively. This maps into a truth table of:
       /// LHS | RHS | LHS >=s RHS   | LHS implies RHS
       ///  0  |  0  |  1 (0 >= 0)   |  1
       ///  0  |  1  |  1 (0 >= -1)  |  1
       ///  1  |  0  |  0 (-1 >= 0)  |  0
       ///  1  |  1  |  1 (-1 >= -1) |  1
-      if (isImpliedCondition(LHS, RHS, Q.DL))
+      bool ImpliedTrue;
+      if (isImpliedCondition(LHS, RHS, ImpliedTrue, Q.DL) && ImpliedTrue)
         return getTrue(ITy);
       break;
+    }
     case ICmpInst::ICMP_SLT:
       // X <s 0 -> X
       if (match(RHS, m_Zero()))
         return LHS;
       break;
     case ICmpInst::ICMP_SLE:
       // X <=s -1 -> X
       if (match(RHS, m_One()))
         return LHS;
       break;
-    case ICmpInst::ICMP_ULE:
-      if (isImpliedCondition(LHS, RHS, Q.DL))
+    case ICmpInst::ICMP_ULE: {
+      bool ImpliedTrue;
+      if (isImpliedCondition(LHS, RHS, ImpliedTrue, Q.DL) && ImpliedTrue)
         return getTrue(ITy);
       break;
     }
     }
+  }
 
   // If we are comparing with zero then try hard since this is a common case.
   if (match(RHS, m_Zero())) {
     bool LHSKnownNonNegative, LHSKnownNegative;
     switch (Pred) {
     default: llvm_unreachable("Unknown ICmp predicate!");
     case ICmpInst::ICMP_ULT:
       return getFalse(ITy);

lib/Analysis/ValueTracking.cpp

static bool isImpliedCondOperands(CmpInst::Predicate Pred, Value *ALHS,
   case CmpInst::ICMP_ULE:
     return isTruePredicate(CmpInst::ICMP_ULE, BLHS, ALHS, DL, Depth, AC, CxtI,
                            DT) &&
            isTruePredicate(CmpInst::ICMP_ULE, ARHS, BRHS, DL, Depth, AC, CxtI,
                            DT);
   }
 }
 
-bool llvm::isImpliedCondition(Value *LHS, Value *RHS, const DataLayout &DL,
-                              unsigned Depth, AssumptionCache *AC,
-                              const Instruction *CxtI,
+// The predicates must match sign or at least one of them must be an equality
+// comparison (which is signless).
+static bool PredicatesComparable(CmpInst::Predicate APred,
+                                 CmpInst::Predicate BPred) {
+  if (ICmpInst::isSigned(APred) != ICmpInst::isSigned(BPred) &&
+      !ICmpInst::isEquality(APred) && !ICmpInst::isEquality(BPred))
+    return false;
+  return true;
+}
+
+/// Return true if "icmp2 BPred BLHS BRHS" is known to be implied by "icmp1
+/// APred ALHS ARHS".  The implication may be either true or false depending on
+/// the return value of ImpliedTrue.
+static bool isImpliedCondMatchingOperands(CmpInst::Predicate APred, Value *ALHS,
+                                          Value *ARHS, CmpInst::Predicate BPred,
+                                          Value *BLHS, Value *BRHS,
+                                          bool &ImpliedTrue) {
+  // The operands of the two compares must match.
+  bool IsMatchingOps = (ALHS == BLHS && ARHS == BRHS);
+  bool IsSwappedOps = (ALHS == BRHS && ARHS == BLHS);
+  if (!IsMatchingOps && !IsSwappedOps)
+    return false;
+
+  // Canonicalize the operands so they're matching.
+  if (IsSwappedOps) {
+    std::swap(BLHS, BRHS);
+    BPred = ICmpInst::getSwappedPredicate(BPred);
+  }
+
+  // If the predicates match, then we know the first condition implies the
+  // second is true.
+  if (APred == BPred) {
+    ImpliedTrue = true;
+    return true;
+  }
+
+  // The predicates must match sign or at least one of them must be an equality
+  // comparison (which is signless).
+  if (!PredicatesComparable(APred, BPred))
+    return false;
+
+  // The next bit of logic is the same for unsigned and signed comparison.
+  // Therefore, unconditionally convert the predicates to their unsigned
+  // equivalent to reduce the amount of logic needed.  This is safe because
+  // we've already verified that the sign of the predicates match.
+  auto UnsignedAPred = ICmpInst::getUnsignedPredicate(APred);
+  auto UnsignedBPred = ICmpInst::getUnsignedPredicate(BPred);
+
+  // If an inverted APred matches BPred, we can infer the second condition is
+  // false in many cases.
+  if (CmpInst::getInversePredicate(UnsignedAPred) == UnsignedBPred) {
+    switch (UnsignedAPred) {
+    default:
+      break;
+    case CmpInst::ICMP_EQ:  // A == B implies A != B is false.
+    case CmpInst::ICMP_NE:  // A != B implies A == B is false.
+    case CmpInst::ICMP_UGT: // A > B implies A <= B is false.
+    case CmpInst::ICMP_ULT: // A < B implies A >= B is false.
+    case CmpInst::ICMP_UGE: // A >= B implies A < B is false.
+    case CmpInst::ICMP_ULE: // A <= B implies A > B is false.
+      ImpliedTrue = false;
+      return true;
+    }
+  }
+
+  // If a swapped APred matches BPred, we can infer the second condition is
+  // false in many cases.
+  if (CmpInst::getSwappedPredicate(UnsignedAPred) == UnsignedBPred) {
+    switch (UnsignedAPred) {
+    default:
+      break;
+    case CmpInst::ICMP_UGT: // A > B implies A < B is false.
+    case CmpInst::ICMP_ULT: // A < B implies A > B is false.
+      ImpliedTrue = false;
+      return true;
+    }
+  }
+
+  switch (UnsignedAPred) {
+  default:
+    break;
+  case CmpInst::ICMP_EQ:
+    // A == B implies A > B and A < B are false.
+    if (CmpInst::isFalseWhenEqual(UnsignedBPred)) {
+      ImpliedTrue = false;
+      return true;
+    }
+    break;
+  case CmpInst::ICMP_UGT:
+  case CmpInst::ICMP_ULT:
+    // A > B implies A == B is false.
+    // A < B implies A == B is false.
+    if (UnsignedBPred == CmpInst::ICMP_EQ) {
+      ImpliedTrue = false;
+      return true;
+    }
+    // A > B implies A != B is true.
+    // A < B implies A != B is true.
+    if (UnsignedBPred == CmpInst::ICMP_NE) {
+      ImpliedTrue = true;
+      return true;
+    }
+    break;
+  }
+  return false;
+}
+
+bool llvm::isImpliedCondition(Value *LHS, Value *RHS, bool &ImpliedTrue,
+                              const DataLayout &DL, unsigned Depth,
+                              AssumptionCache *AC, const Instruction *CxtI,
                               const DominatorTree *DT) {
   assert(LHS->getType() == RHS->getType() && "mismatched type");
   Type *OpTy = LHS->getType();
   assert(OpTy->getScalarType()->isIntegerTy(1));
 
   // LHS ==> RHS by definition
-  if (LHS == RHS) return true;
+  if (LHS == RHS) {
+    ImpliedTrue = true;
+    return true;
+  }
 
   if (OpTy->isVectorTy())
     // TODO: extending the code below to handle vectors
     return false;
   assert(OpTy->isIntegerTy(1) && "implied by above");
 
   ICmpInst::Predicate APred, BPred;
   Value *ALHS, *ARHS;
   Value *BLHS, *BRHS;
 
   if (!match(LHS, m_ICmp(APred, m_Value(ALHS), m_Value(ARHS))) ||
       !match(RHS, m_ICmp(BPred, m_Value(BLHS), m_Value(BRHS))))
     return false;
 
-  if (APred == BPred)
+  if (isImpliedCondMatchingOperands(APred, ALHS, ARHS, BPred, BLHS, BRHS,
+                                    ImpliedTrue))
+    return true;
+
+  if (APred == BPred) {
+    ImpliedTrue = true;
     return isImpliedCondOperands(APred, ALHS, ARHS, BLHS, BRHS, DL, Depth, AC,
                                  CxtI, DT);
+  }
 
   return false;
 }

lib/Transforms/Scalar/JumpThreading.cpp

bool JumpThreading::ProcessImpliedCondition(BasicBlock *BB) {
 
   auto &DL = BB->getModule()->getDataLayout();
 
   while (CurrentPred && Iter++ < ImplicationSearchThreshold) {
     auto *PBI = dyn_cast<BranchInst>(CurrentPred->getTerminator());
     if (!PBI || !PBI->isConditional() || PBI->getSuccessor(0) != CurrentBB)
       return false;
 
-    if (isImpliedCondition(PBI->getCondition(), Cond, DL)) {
-      BI->getSuccessor(1)->removePredecessor(BB);
-      BranchInst::Create(BI->getSuccessor(0), BI);
+    bool ImpliedTrue;
+    if (isImpliedCondition(PBI->getCondition(), Cond, ImpliedTrue, DL)) {
+      BI->getSuccessor(ImpliedTrue ? 1 : 0)->removePredecessor(BB);
+      BranchInst::Create(BI->getSuccessor(ImpliedTrue ? 0 : 1), BI);
       BI->eraseFromParent();
       return true;
     }
     CurrentBB = CurrentPred;
     CurrentPred = CurrentBB->getSinglePredecessor();
   }
 
   return false;
 }
 
 /// SimplifyPartiallyRedundantLoad - If LI is an obviously partially redundant
 /// load instruction, eliminate it by replacing it with a PHI node.  This is an

lib/Transforms/Utils/SimplifyCFG.cpp

static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI,
   }
 
   if (auto *CE = dyn_cast<ConstantExpr>(BI->getCondition()))
     if (CE->canTrap())
       return false;
 
   // If BI is reached from the true path of PBI and PBI's condition implies
   // BI's condition, we know the direction of the BI branch.
+  bool ImpliedTrue;
   if (PBI->getSuccessor(0) == BI->getParent() &&
-      isImpliedCondition(PBI->getCondition(), BI->getCondition(), DL) &&
+      isImpliedCondition(PBI->getCondition(), BI->getCondition(), ImpliedTrue,
+                         DL) &&
       PBI->getSuccessor(0) != PBI->getSuccessor(1) &&
       BB->getSinglePredecessor()) {
     // Turn this into a branch on constant.
     auto *OldCond = BI->getCondition();
-    BI->setCondition(ConstantInt::getTrue(BB->getContext()));
+    ConstantInt *CI = ImpliedTrue ? ConstantInt::getTrue(BB->getContext())
+                                  : ConstantInt::getFalse(BB->getContext());
+    BI->setCondition(CI);
     RecursivelyDeleteTriviallyDeadInstructions(OldCond);
     return true;  // Nuke the branch on constant.
   }
 
   // If both branches are conditional and both contain stores to the same
   // address, remove the stores from the conditionals and create a conditional
   // merged store at the end.
   if (MergeCondStores && mergeConditionalStores(PBI, BI))
     return true;

test/Transforms/JumpThreading/implied-cond.ll

left0:
   call void @side_effect(i32 0)
   ret void
 
  right:
   %t = phi i32 [ 1, %left ], [ 2, %entry ], [ 3, %cont ]
   call void @side_effect(i32 %t)
   ret void
 }
+
+; A s<= B implies A s> B is false.
+; CHECK-LABEL: @test3(
+; CHECK: entry:
+; CHECK: br i1 %cmp, label %if.end, label %if.end3
+; CHECK-NOT: br i1 %cmp1, label %if.then2, label %if.end
+; CHECK-NOT: call void @side_effect(i32 0)
+; CHECK: br label %if.end3
+; CHECK: ret void
+
+define void @test3(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp sle i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp sgt i32 %a, %b
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @side_effect(i32 0)
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}

test/Transforms/SimplifyCFG/implied-cond-matching.ll

+; RUN: opt %s -S -simplifycfg | FileCheck %s
+
+; Test same condition with swapped operands.
+; void test_swapped_ops(unsigned a, unsigned b) {
+;   if (a > b) {
+;     if (b > a) <- always false
+;       dead();
+;     alive();
+;   }
+; }
+;
+; CHECK-LABEL: @test_swapped_ops
+; CHECK-NOT: call void @dead()
+; CHECK: call void @alive()
+; CHECK: ret
+define void @test_swapped_ops(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ugt i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp ugt i32 %b, %a
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @dead()
+  br label %if.end
+
+if.end:
+  call void @alive()
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; void test_swapped_pred(unsigned a, unsigned b) {
+;   if (a > b) {
+;     alive();
+;     if (b < a) <- always true; remove branch
+;       alive();
+;   }
+; }
+;
+; CHECK-LABEL: @test_swapped_pred
+; CHECK: call void @alive()
+; CHECK-NEXT: call void @alive()
+; CHECK: ret
+define void @test_swapped_pred(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ugt i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  call void @alive()
+  %cmp1 = icmp ult i32 %b, %a
+  br i1 %cmp1, label %if.then2, label %if.end3
+
+if.then2:
+  call void @alive()
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A == B implies A > B is false
+; A == B implies A < B is false
+; A == B implies A != B is false
+; CHECK-LABEL: @test_eq
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_eq(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp eq i32 %a, %b
+  br i1 %cmp, label %if.end, label %if.end9
+
+if.end:
+  %cmp3 = icmp ugt i32 %a, %b
+  br i1 %cmp3, label %if.then4, label %if.end5
+
+if.then4:
+  call void @dead()
+  br label %if.end5
+
+if.end5:
+  %cmp6 = icmp ult i32 %a, %b
+  br i1 %cmp6, label %if.then7, label %if.end8
+
+if.then7:
+  call void @dead()
+  br label %if.end8
+
+if.end8:
+  br label %if.end9
+
+if.end9:
+  ret void
+}
+
+; A != B implies A == B is false
+; CHECK-LABEL: @test_ne
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_ne(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ne i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp eq i32 %a, %b
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @dead()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A > B implies A == B is false.
+; A > B implies A <= B is false.
+; A > B implies A != B is true.
+; CHECK-LABEL: @test_gt
+; CHECK-NOT: dead
+; CHECK: alive
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_gt(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ugt i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end9
+
+if.then:
+  %cmp1 = icmp eq i32 %a, %b
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @dead()
+  br label %if.end
+
+if.end:
+  %cmp3 = icmp ule i32 %a, %b
+  br i1 %cmp3, label %if.then4, label %if.end5
+
+if.then4:
+  call void @dead()
+  br label %if.end5
+
+if.end5:
+  %cmp6 = icmp ne i32 %a, %b
+  br i1 %cmp6, label %if.then7, label %if.end8
+
+if.then7:
+  call void @alive()
+  br label %if.end8
+
+if.end8:
+  br label %if.end9
+
+if.end9:
+  ret void
+}
+
+; A < B implies A == B is false.
+; A < B implies A >= B is false.
+; A < B implies A != B is true.
+; CHECK-LABEL: @test_lt
+; CHECK-NOT: dead
+; CHECK: alive
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_lt(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ult i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end9
+
+if.then:
+  %cmp1 = icmp eq i32 %a, %b
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @dead()
+  br label %if.end
+
+if.end:
+  %cmp3 = icmp ult i32 %a, %b
+  br i1 %cmp3, label %if.end5, label %if.then4
+
+if.then4:
+  call void @dead()
+  br label %if.end5
+
+if.end5:
+  %cmp6 = icmp eq i32 %a, %b
+  br i1 %cmp6, label %if.end8, label %if.then7
+
+if.then7:
+  call void @alive()
+  br label %if.end8
+
+if.end8:
+  br label %if.end9
+
+if.end9:
+  ret void
+}
+
+; A >= B implies A < B is false.
+; CHECK-LABEL: @test_ge
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_ge(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp uge i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp ult i32 %a, %b
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @dead()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A <= B implies A > B is false.
+; CHECK-LABEL: @test_le
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_le(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ule i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp ugt i32 %a, %b
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @dead()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A u<= B does not imply A s> B is false.
+; CHECK-LABEL: @test_ule_sgt_unsafe
+; CHECK: alive
+; CHECK: ret void
+define void @test_ule_sgt_unsafe(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ule i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp sgt i32 %a, %b
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @alive()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A u> B does not imply B s> A is false.
+; CHECK-LABEL: @test_ugt_sgt_unsafe
+; CHECK: alive
+; CHECK: ret void
+define void @test_ugt_sgt_unsafe(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ugt i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp sgt i32 %b, %a
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @alive()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+declare void @dead()
+declare void @alive()