[PatternMatch] Switch to using ValueTracking::matchSelectPattern for min/max matching

[jmolloy]

Summary

Instead of rolling our own min/max matching code (which is notoriously hard to get completely right), use ValueTracking's instead.

MFCI (minimal functional change intended)

[hfinkel]

include/llvm/IR/PatternMatch.h

966

I think this makes sense, but I wonder if we should now swap the order of the checks here to check L.match and R.match first. The current ordering certainly made sense because the predicate checks done before calling those functions were cheap. Calling matchSelectPattern, however, calls isKnownNonZero (at least for integer comparisons), and that can get expensive. I'd recommend that we not call matchSelectPattern until the end. My suggestion is that we:

1. Check that V is a SelectInst (and maybe that SI->getCondition() is a CmpInst)
2. Check L.match(LHS) && R.match(RHS)
3. Call matchSelectPattern and check Pred_t::match(SPR)

[jmolloy]

Hi Hal,

Thanks for the review.

include/llvm/IR/PatternMatch.h

966

That makes sense. However we can't do step 2 first, because we need to bind LHS and RHS via matchSelectPattern before we can bind L and R to them with match().

[jmolloy]

Updated diff following Hal's comments.

[jmolloy]

Ping!

[majnemer]

include/llvm/IR/PatternMatch.h

959–962

Unless I'm mistaken, isn't this what llvm::matchSelectPattern already does? I'd be surprised if the extra call frame matters here.

[hfinkel]

Remove the redundant check as noted, and this LGTM.

include/llvm/IR/PatternMatch.h

959–962

Yea, he half-implemented my earlier suggestion by putting this check here. But, as James pointed out, he needs to call matchSelectPattern first anyway to bind LHS and RHS. Thus, as you point out, this is not needed.

[jmolloy]

Committed with required changes in r25178.

include/llvm/IR/PatternMatch.h

 // This is primarily useful to things like the instruction combiner, but can
 // also be useful for static analysis tools or code generators.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_PATTERNMATCH_H
 #define LLVM_IR_PATTERNMATCH_H
 
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Operator.h"
 
 namespace llvm {
 namespace PatternMatch {

 template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t>
 struct MaxMin_match {
   LHS_t L;
   RHS_t R;
 
   MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
-    auto *SI = dyn_cast<SelectInst>(V);
-    if (!SI)
-      return false;
-    auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
-    if (!Cmp)
-      return false;
-    // At this point we have a select conditioned on a comparison.  Check that
-    // it is the values returned by the select that are being compared.
-    Value *TrueVal = SI->getTrueValue();
-    Value *FalseVal = SI->getFalseValue();
-    Value *LHS = Cmp->getOperand(0);
-    Value *RHS = Cmp->getOperand(1);
-    if ((TrueVal != LHS || FalseVal != RHS) &&
-        (TrueVal != RHS || FalseVal != LHS))
-      return false;
-    typename CmpInst_t::Predicate Pred =
-        LHS == TrueVal ? Cmp->getPredicate() : Cmp->getSwappedPredicate();
-    // Does "(x pred y) ? x : y" represent the desired max/min operation?
-    if (!Pred_t::match(Pred))
+    // matchSelectPattern can get expensive, so do some early bailout checks
+    // first.
+    if (!isa<SelectInst>(V) ||
+        !isa<CmpInst>(cast<SelectInst>(V)->getCondition()))
       return false;
-    // It does!  Bind the operands.
-    return L.match(LHS) && R.match(RHS);
+
+    Value *LHS, *RHS;
+    auto SPR = matchSelectPattern(V, LHS, RHS);
+    return Pred_t::match(SPR) && L.match(LHS) && R.match(RHS);
   }
 };
 
 /// \brief Helper class for identifying signed max predicates.
 struct smax_pred_ty {
-  static bool match(ICmpInst::Predicate Pred) {
-    return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
+  static bool match(SelectPatternResult SPR) {
+    return SPR.Flavor == SPF_SMAX;
   }
 };
 
 /// \brief Helper class for identifying signed min predicates.
 struct smin_pred_ty {
-  static bool match(ICmpInst::Predicate Pred) {
-    return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE;
+  static bool match(SelectPatternResult SPR) {
+    return SPR.Flavor == SPF_SMIN;
   }
 };
 
 /// \brief Helper class for identifying unsigned max predicates.
 struct umax_pred_ty {
-  static bool match(ICmpInst::Predicate Pred) {
-    return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE;
+  static bool match(SelectPatternResult SPR) {
+    return SPR.Flavor == SPF_UMAX;
   }
 };
 
 /// \brief Helper class for identifying unsigned min predicates.
 struct umin_pred_ty {
-  static bool match(ICmpInst::Predicate Pred) {
-    return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE;
+  static bool match(SelectPatternResult SPR) {
+    return SPR.Flavor == SPF_UMIN;
   }
 };
 
 /// \brief Helper class for identifying ordered max predicates.
 struct ofmax_pred_ty {
-  static bool match(FCmpInst::Predicate Pred) {
-    return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE;
+  static bool match(SelectPatternResult SPR) {
+    return SPR.Flavor == SPF_FMAXNUM &&
+      (SPR.Ordered || SPR.NaNBehavior == SPNB_RETURNS_ANY);
   }
 };
 
 /// \brief Helper class for identifying ordered min predicates.
 struct ofmin_pred_ty {
-  static bool match(FCmpInst::Predicate Pred) {
-    return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE;
+  static bool match(SelectPatternResult SPR) {
+    return SPR.Flavor == SPF_FMINNUM &&
+      (SPR.Ordered || SPR.NaNBehavior == SPNB_RETURNS_ANY);
   }
 };
 
 /// \brief Helper class for identifying unordered max predicates.
 struct ufmax_pred_ty {
-  static bool match(FCmpInst::Predicate Pred) {
-    return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE;
+  static bool match(SelectPatternResult SPR) {
+    return SPR.Flavor == SPF_FMAXNUM &&
+      (!SPR.Ordered || SPR.NaNBehavior == SPNB_RETURNS_ANY);
   }
 };
 
 /// \brief Helper class for identifying unordered min predicates.
 struct ufmin_pred_ty {
-  static bool match(FCmpInst::Predicate Pred) {
-    return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE;
+  static bool match(SelectPatternResult SPR) {
+    return SPR.Flavor == SPF_FMINNUM &&
+      (!SPR.Ordered || SPR.NaNBehavior == SPNB_RETURNS_ANY);
   }
 };
 
 template <typename LHS, typename RHS>
 inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty> m_SMax(const LHS &L,
                                                              const RHS &R) {
   return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>(L, R);
 }