Refactor implied condition logic from ValueTracking directly into CmpInst. NFC.

[mcrosier]

Summary

This logic allows a compare instruction to infer the condition of another compare with matching operands without having to use ValueTracking directly.

Chad

[sanjoy]

lib/Analysis/ValueTracking.cpp

3845

Can't the logic in this switch also be moved to CmpInst::isTrueWhenOperandsMatch and CmpInst::isFaseWhenOperandsMatch ?

[mcrosier]

Move the remaining bit of logic into CmpInst, per Sanjoy's suggestion.

[sanjoy]

Given that this passes all the checked in tests then I'm okay signing off on this for now (with a FIXME stating what remains to be done); but depending on how much time you're willing to commit here, I think we can make this code more comprehensive. I've added a comment inline about some of the missing cases, but there is a useful litmus test here: we should be able to implement isFalseWhenOperandsMatch(X, Y) exactly as isTrueWhenOperandsMatch(X, getInversePredicate(Y)). Any situation where that doesn't work is a missing case.

lib/IR/Instructions.cpp

3609

UGT also implies UGE etc.

EQ will imply all UGE, SLE etc. variants.

[mcrosier]

In D19330#407408, @sanjoy wrote:

Given that this passes all the checked in tests then I'm okay signing off on this for now (with a FIXME stating what remains to be done); but depending on how much time you're willing to commit here, I think we can make this code more comprehensive. I've added a comment inline about some of the missing cases, but there is a useful litmus test here: we should be able to implement isFalseWhenOperandsMatch(X, Y) exactly as isTrueWhenOperandsMatch(X, getInversePredicate(Y)). Any situation where that doesn't work is a missing case.

Yes, the code can be more comprehensive. I'll post a patch shortly as I'd like for this work to be complete. Thanks, Sanjoy.

include/llvm/IR/InstrTypes.h

public:
   }
 
   /// This is just a convenience.
   /// @brief Determine if this is false when both operands are the same.
   bool isFalseWhenEqual() const {
     return isFalseWhenEqual(getPredicate());
   }
 
+  /// @brief Determine if Pred1 implies Pred2 is true when two compares have
+  /// matching operands.
+  bool isTrueWhenOperandsMatch(Predicate Pred2) {
+    return isTrueWhenOperandsMatch(getPredicate(), Pred2);
+  }
+
+  /// @brief Determine if Pred1 implies Pred2 is false when two compares have
+  /// matching operands.
+  bool isFalseWhenOperandsMatch(Predicate Pred2) {
+    return isFalseWhenOperandsMatch(getPredicate(), Pred2);
+  }
+
   /// @returns true if the predicate is unsigned, false otherwise.
   /// @brief Determine if the predicate is an unsigned operation.
   static bool isUnsigned(Predicate predicate);
 
   /// @returns true if the predicate is signed, false otherwise.
   /// @brief Determine if the predicate is an signed operation.
   static bool isSigned(Predicate predicate);
 
   /// @brief Determine if the predicate is an ordered operation.
   static bool isOrdered(Predicate predicate);
 
   /// @brief Determine if the predicate is an unordered operation.
   static bool isUnordered(Predicate predicate);
 
   /// Determine if the predicate is true when comparing a value with itself.
   static bool isTrueWhenEqual(Predicate predicate);
 
   /// Determine if the predicate is false when comparing a value with itself.
   static bool isFalseWhenEqual(Predicate predicate);
 
+  /// Determine if Pred1 implies Pred2 is true when two compares have matching
+  /// operands.
+  static bool isTrueWhenOperandsMatch(Predicate Pred1, Predicate Pred2);
+
+  /// Determine if Pred1 implies Pred2 is false when two compares have matching
+  /// operands.
+  static bool isFalseWhenOperandsMatch(Predicate Pred1, Predicate Pred2);
+
   /// @brief Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const Instruction *I) {
     return I->getOpcode() == Instruction::ICmp ||
            I->getOpcode() == Instruction::FCmp;
   }
   static inline bool classof(const Value *V) {
     return isa<Instruction>(V) && classof(cast<Instruction>(V));
   }

lib/Analysis/ValueTracking.cpp

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) {
+  if (CmpInst::isTrueWhenOperandsMatch(APred, BPred)) {
     ImpliedTrue = true;
     return true;
   }
 
-  // If an inverted APred matches BPred, we can infer the second condition is
-  // false.
-  if (CmpInst::getInversePredicate(APred) == BPred) {
+  if (CmpInst::isFalseWhenOperandsMatch(APred, BPred)) {
     ImpliedTrue = false;
     return true;
   }
 
-  // If a swapped APred matches BPred, we can infer the second condition is
-  // false in many cases.
-  if (CmpInst::getSwappedPredicate(APred) == BPred) {
-    switch (APred) {
-    default:
-      break;
-    case CmpInst::ICMP_UGT: // A >u B implies A <u B is false.
-    case CmpInst::ICMP_ULT: // A <u B implies A >u B is false.
-    case CmpInst::ICMP_SGT: // A >s B implies A <s B is false.
-    case CmpInst::ICMP_SLT: // A <s B implies A >s B is false.
-      ImpliedTrue = false;
-      return true;
-    }
-  }
-
   // The predicates must match sign or at least one of them must be an equality
   // comparison (which is signless).
   if (ICmpInst::isSigned(APred) != ICmpInst::isSigned(BPred) &&
       !ICmpInst::isEquality(APred) && !ICmpInst::isEquality(BPred))
     return false;
 
   switch (APred) {
   default:
     break;
   case CmpInst::ICMP_EQ:
     // A == B implies A > B and A < B are false.
     if (CmpInst::isFalseWhenEqual(BPred)) {
       ImpliedTrue = false;
       return true;
     }

lib/IR/Instructions.cpp

 bool CmpInst::isFalseWhenEqual(Predicate predicate) {
   switch(predicate) {
   case ICMP_NE:    case ICMP_UGT: case ICMP_ULT: case ICMP_SGT: case ICMP_SLT:
   case FCMP_FALSE: case FCMP_ONE: case FCMP_OGT: case FCMP_OLT: return true;
   default: return false;
   }
 }
 
+bool CmpInst::isTrueWhenOperandsMatch(Predicate Pred1, Predicate Pred2) {
+  // If the predicates match, then we know the first condition implies the
+  // second is true.
+  return Pred1 == Pred2;
+}
+
+bool CmpInst::isFalseWhenOperandsMatch(Predicate Pred1, Predicate Pred2) {
+  // If an inverted Pred1 matches Pred2, we can infer the second condition is
+  // false.
+  if (getInversePredicate(Pred1) == Pred2)
+    return true;
+
+  // If a swapped Pred1 matches Pred2, we can infer the second condition is
+  // false in many cases.
+  if (getSwappedPredicate(Pred1) == Pred2) {
+    switch (Pred1) {
+    default:
+      break;
+    case ICMP_UGT: // A >u B implies A <u B is false.
+    case ICMP_ULT: // A <u B implies A >u B is false.
+    case ICMP_SGT: // A >s B implies A <s B is false.
+    case ICMP_SLT: // A <s B implies A >s B is false.
+      return true;
+    }
+  }
+  return false;
+}
 
 //===----------------------------------------------------------------------===//
 //                        SwitchInst Implementation
 //===----------------------------------------------------------------------===//
 
 void SwitchInst::init(Value *Value, BasicBlock *Default, unsigned NumReserved) {
   assert(Value && Default && NumReserved);
   ReservedSpace = NumReserved;