[ValueTracking] Add support for floating-point minnum and maxnum

[jmolloy]

Summary

The select pattern recognition in ValueTracking (as used by InstCombine
and SelectionDAGBuilder) only knew about integer patterns. This teaches
it about minimum and maximum operations.

The semantics of the patterns it matches match the C99 minnum/maxnum
operations; namely that when presented with two operands one of which
being a QNaN, the non-QNaN operand is returned.

[jmolloy]

lib/Transforms/InstCombine/InstCombineSelect.cpp

42

I've currently put the onus on the user of matchSelectPattern to work out if an ordered or unordered FCMP is needed. I was in two minds about this, the alternative being to change matchSelectPattern to return a struct containing the pattern kind, the orderedness and the fast-math flags if applicable.

[jmolloy]

Updated diff:

1. Added extra checking to ensure we don't convert (0.0 <= -0.0 ? 0.0 : -0.0) to minnum, as we'll return the wrong value.
2. Switched the logic for which operand needs to be non-NaN for unordered and ordered comparisons - it turns out there are two mutually-incompatible implementations of this, one in the ARM backend and one in AArch64. It looks like AArch64 is correct; luckily both will be defunct in a few commits time!

[jmolloy]

Hi,

It's a good thing this hasn't started being reviewed yet - I've just rewritten a bunch of it because I realised the previous implementation wasn't sufficient.

The previous version was only matching C99-style fminf/fmaxf; if one operand is NaN, it must return the other operand. However, idiomatic C is the opposite - "a < b ? a : b" would return NaN (due to ordered comparisons).

So now matchSelectPattern detects floating point mins and maxes regardless of its behaviour under NaN, and returns an extra enum value informing the user what its NaN behaviour is.

If the user (such as InstCombine) wants to rewrite the min/max, they have to use the correct ordered/unordered predicates in their FCMP, so it also returns the orderedness required (if any).

Adding extra reviewers too to widen the review net a bit and because I've been unfairly loading Hal recently!

[arsenm]

lib/Analysis/ValueTracking.cpp

3325–3326

No return after else

3332–3333

ditto

3358

This could use a better name.

3402–3404

This indentation is confusing looking. The assignments should be on their own line, the O = !O looks like it's under the else if

test/Transforms/InstCombine/minmax-fp.ll

140

I don't think I see a test that explicitly checks for fcmp nnan

unittests/Analysis/ValueTrackingTest.cpp

37

I don't think you need the .c_str() here

[jmolloy]

Hi Matt,

Thanks for your review! All your comments applied.

Cheers,

James

[majnemer]

lib/Analysis/ValueTracking.cpp

3323

Use auto *, we know the type from the LHS.

3329

Ditto.

[jmolloy]

Hi David,

Thanks for your review. Done!

James

[arsenm]

lib/Analysis/ValueTracking.cpp

3345

This comment is inaccurate. minnum is specifically allowed to return either 0.0 or -0.0 in this case

3362

This comment is also inaccurate.

a < b is an ordered comparison.
If a is NaN the compare is false and this will return b.
If b is NaN, this will return the NaN b. This is the behavior of the min/max_legacy AMDGPU instructions which do behave as a compare + select. minnum/maxnum can't be matched to a single compare and select except in the special no nan cases. I think the code below is doing the right thing though.

[jmolloy]

Hi Matt,

Agreed. Comments updated.

I've kept the conservative behaviour of bailing out when one input may be a signed zero (and nsz is not set) for the moment.

If you think it's worth being more aggressive in that case, We'll need to add another field to SelectPatternResult modelling the behavior with signed zeroes (ARM's minnum instruction would return -0.0; I have no idea what yours might do). But I suspect there aren't enough cases to justify this extra modelling, not at the moment anyway.

James

[jmolloy]

lib/Analysis/ValueTracking.cpp

3362

Typo: This should of course read 'b', not 'a'; I've updated this locally.

[arsenm]

test/Transforms/InstCombine/minmax-fp.ll

5–6

I think these really need to check the operands of these instructions. At the very minimum, at least the fcmp compare type.

Besides that LGTM

[hfinkel]

lib/Analysis/ValueTracking.cpp

3345

I feel compelled to say that this is sad. The relevant text for minNum/maxNum even notes, "this means results might differ among implementations", and this is the only place I can find in the standard that says that.

3409

This comment should now say icmp/fcmp (or similar).

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2277–2278

Line is too long.

lib/Transforms/InstCombine/InstCombineCasts.cpp

1312

What is the canonical form? I think it would be helpful to say (or refer to somewhere else that says).

[jmolloy]

Hi Matt, Hal,

Both your comments are addressed. Hal, does this LGTY?

Cheers,

James

[jmolloy]

Ping!

[jmolloy]

Ping^2!

[hfinkel]

LGTM.

lib/Analysis/ValueTracking.cpp

3377

"so RHS is NaN" is a bit too much short-hand I think. We don't know that the RHS is NaN, we know that if it is NaN, then it will be returned. Please make the comment a bit more specific.

[jmolloy]

Landed in r244754.

include/llvm/Analysis/ValueTracking.h

OverflowResult computeOverflowForUnsignedAdd(Value *LHS, Value *RHS,
                                                const DataLayout &DL,
                                                AssumptionCache *AC,
                                                const Instruction *CxtI,
                                                const DominatorTree *DT);
   
   /// \brief Specific patterns of select instructions we can match.
   enum SelectPatternFlavor {
     SPF_UNKNOWN = 0,
-    SPF_SMIN,                   // Signed minimum
-    SPF_UMIN,                   // Unsigned minimum
-    SPF_SMAX,                   // Signed maximum
-    SPF_UMAX,                   // Unsigned maximum
-    SPF_ABS,                    // Absolute value
-    SPF_NABS                    // Negated absolute value
+    SPF_SMIN,                   /// Signed minimum
+    SPF_UMIN,                   /// Unsigned minimum
+    SPF_SMAX,                   /// Signed maximum
+    SPF_UMAX,                   /// Unsigned maximum
+    SPF_FMINNUM,                /// Floating point minnum
+    SPF_FMAXNUM,                /// Floating point maxnum
+    SPF_ABS,                    /// Absolute value
+    SPF_NABS                    /// Negated absolute value
+  };
+  /// \brief Behavior when a floating point min/max is given one NaN and one
+  /// non-NaN as input.
+  enum SelectPatternNaNBehavior {
+    SPNB_NA = 0,                /// NaN behavior not applicable.
+    SPNB_RETURNS_NAN,           /// Given one NaN input, returns the NaN.
+    SPNB_RETURNS_OTHER,         /// Given one NaN input, returns the non-NaN.
+    SPNB_RETURNS_ANY            /// Given one NaN input, can return either (or
+                                /// it has been determined that no operands can
+                                /// be NaN).
+  };
+  struct SelectPatternResult {
+    SelectPatternFlavor Flavor;
+    SelectPatternNaNBehavior NaNBehavior; /// Only applicable if Flavor is
+                                          /// SPF_FMINNUM or SPF_FMAXNUM.
+    bool Ordered;               /// When implementing this min/max pattern as
+                                /// fcmp; select, does the fcmp have to be
+                                /// ordered?
   };
   /// Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind
   /// and providing the out parameter results if we successfully match.
   ///
   /// If CastOp is not nullptr, also match MIN/MAX idioms where the type does
   /// not match that of the original select. If this is the case, the cast
   /// operation (one of Trunc,SExt,Zext) that must be done to transform the
   /// type of LHS and RHS into the type of V is returned in CastOp.
   ///
   /// For example:
   ///   %1 = icmp slt i32 %a, i32 4
   ///   %2 = sext i32 %a to i64
   ///   %3 = select i1 %1, i64 %2, i64 4
   ///
   /// -> LHS = %a, RHS = i32 4, *CastOp = Instruction::SExt
   ///
-  SelectPatternFlavor matchSelectPattern(Value *V, Value *&LHS, Value *&RHS,
+  SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS,
                                          Instruction::CastOps *CastOp = nullptr);
 
 } // end namespace llvm
 
 #endif

lib/Analysis/ValueTracking.cpp

if (LHSKnownNonNegative && RHSKnownNonNegative) {
       // Create a simple add instruction, and insert it into the struct.
       return OverflowResult::NeverOverflows;
     }
   }
 
   return OverflowResult::MayOverflow;
 }
 
-static SelectPatternFlavor matchSelectPattern(ICmpInst::Predicate Pred,
+static bool isKnownNonNaN(Value *V, FastMathFlags FMF) {
+  if (FMF.noNaNs())
+    return true;
+
+  if (auto *C = dyn_cast<ConstantFP>(V))
+    return !C->isNaN();
+  return false;
+}
+
+static bool isKnownNonZero(Value *V) {
+  if (auto *C = dyn_cast<ConstantFP>(V))
+    return !C->isZero();
+  return false;
+}
+
+static SelectPatternResult matchSelectPattern(CmpInst::Predicate Pred,
+                                              FastMathFlags FMF,
                                               Value *CmpLHS, Value *CmpRHS,
                                               Value *TrueVal, Value *FalseVal,
                                               Value *&LHS, Value *&RHS) {
   LHS = CmpLHS;
   RHS = CmpRHS;
 
-  // (icmp X, Y) ? X : Y
-  if (TrueVal == CmpLHS && FalseVal == CmpRHS) {
-    switch (Pred) {
-    default: return SPF_UNKNOWN; // Equality.
-    case ICmpInst::ICMP_UGT:
-    case ICmpInst::ICMP_UGE: return SPF_UMAX;
-    case ICmpInst::ICMP_SGT:
-    case ICmpInst::ICMP_SGE: return SPF_SMAX;
-    case ICmpInst::ICMP_ULT:
-    case ICmpInst::ICMP_ULE: return SPF_UMIN;
-    case ICmpInst::ICMP_SLT:
-    case ICmpInst::ICMP_SLE: return SPF_SMIN;
+  // If the predicate is an "or-equal"  (FP) predicate, then signed zeroes may
+  // return inconsistent results between implementations.
+  //   (0.0 <= -0.0) ? 0.0 : -0.0 // Returns 0.0
+  //   minNum(0.0, -0.0)          // May return -0.0 or 0.0 (IEEE 754-2008 5.3.1)
+  // Therefore we behave conservatively and only proceed if at least one of the
+  // operands is known to not be zero, or if we don't care about signed zeroes.
+  default: break;
+  case CmpInst::FCMP_OGE: case CmpInst::FCMP_OLE:
+  case CmpInst::FCMP_UGE: case CmpInst::FCMP_ULE:
+    if (!FMF.noSignedZeros() && !isKnownNonZero(CmpLHS) &&
+        !isKnownNonZero(CmpRHS))
+      return {SPF_UNKNOWN, SPNB_NA, false};
+  }
+
+  SelectPatternNaNBehavior NaNBehavior = SPNB_NA;
+  bool Ordered = false;
+
+  // When given one NaN and one non-NaN input:
+  //   - maxnum/minnum (C99 fmaxf()/fminf()) return the non-NaN input.
+  //   - A simple C99 (a < b ? a : b) construction will return 'b' (as the
+  //     ordered comparison fails), which could be NaN or non-NaN.
+  // so here we discover exactly what NaN behavior is required/accepted.
+  if (CmpInst::isFPPredicate(Pred)) {
+    bool LHSSafe = isKnownNonNaN(CmpLHS, FMF);
+    bool RHSSafe = isKnownNonNaN(CmpRHS, FMF);
+
+    if (LHSSafe && RHSSafe) {
+      // Both operands are known non-NaN.
+      NaNBehavior = SPNB_RETURNS_ANY;
+    } else if (CmpInst::isOrdered(Pred)) {
+      // An ordered comparison will return false when given a NaN, so it
+      // returns the RHS.
+      Ordered = true;
+      if (LHSSafe)
+        // LHS is non-NaN, so RHS is NaN.
+        NaNBehavior = SPNB_RETURNS_NAN;
+      else if (RHSSafe)
+        NaNBehavior = SPNB_RETURNS_OTHER;
+      else
+        // Completely unsafe.
+        return {SPF_UNKNOWN, SPNB_NA, false};
+    } else {
+      Ordered = false;
+      // An unordered comparison will return true when given a NaN, so it
+      // returns the LHS.
+      if (LHSSafe)
+        // LHS is non-NaN.
+        NaNBehavior = SPNB_RETURNS_OTHER;
+      else if (RHSSafe)
+        NaNBehavior = SPNB_RETURNS_NAN;
+      else
+        // Completely unsafe.
+        return {SPF_UNKNOWN, SPNB_NA, false};
     }
   }
 
-  // (icmp X, Y) ? Y : X
   if (TrueVal == CmpRHS && FalseVal == CmpLHS) {
+    std::swap(CmpLHS, CmpRHS);
+    Pred = CmpInst::getSwappedPredicate(Pred);
+    if (NaNBehavior == SPNB_RETURNS_NAN)
+      NaNBehavior = SPNB_RETURNS_OTHER;
+    else if (NaNBehavior == SPNB_RETURNS_OTHER)
+      NaNBehavior = SPNB_RETURNS_NAN;
+    Ordered = !Ordered;
+  }
+
+  // ([if]cmp X, Y) ? X : Y
+  if (TrueVal == CmpLHS && FalseVal == CmpRHS) {
     switch (Pred) {
-    default: return SPF_UNKNOWN; // Equality.
+    default: return {SPF_UNKNOWN, SPNB_NA, false}; // Equality.
     case ICmpInst::ICMP_UGT:
-    case ICmpInst::ICMP_UGE: return SPF_UMIN;
+    case ICmpInst::ICMP_UGE: return {SPF_UMAX, SPNB_NA, false};
     case ICmpInst::ICMP_SGT:
-    case ICmpInst::ICMP_SGE: return SPF_SMIN;
+    case ICmpInst::ICMP_SGE: return {SPF_SMAX, SPNB_NA, false};
     case ICmpInst::ICMP_ULT:
-    case ICmpInst::ICMP_ULE: return SPF_UMAX;
+    case ICmpInst::ICMP_ULE: return {SPF_UMIN, SPNB_NA, false};
     case ICmpInst::ICMP_SLT:
-    case ICmpInst::ICMP_SLE: return SPF_SMAX;
+    case ICmpInst::ICMP_SLE: return {SPF_SMIN, SPNB_NA, false};
+    case FCmpInst::FCMP_UGT:
+    case FCmpInst::FCMP_UGE:
+    case FCmpInst::FCMP_OGT:
+    case FCmpInst::FCMP_OGE: return {SPF_FMAXNUM, NaNBehavior, Ordered};
+    case FCmpInst::FCMP_ULT:
+    case FCmpInst::FCMP_ULE:
+    case FCmpInst::FCMP_OLT:
+    case FCmpInst::FCMP_OLE: return {SPF_FMINNUM, NaNBehavior, Ordered};
     }
   }
 
   if (ConstantInt *C1 = dyn_cast<ConstantInt>(CmpRHS)) {
     if ((CmpLHS == TrueVal && match(FalseVal, m_Neg(m_Specific(CmpLHS)))) ||
         (CmpLHS == FalseVal && match(TrueVal, m_Neg(m_Specific(CmpLHS))))) {
 
       // ABS(X) ==> (X >s 0) ? X : -X and (X >s -1) ? X : -X
       // NABS(X) ==> (X >s 0) ? -X : X and (X >s -1) ? -X : X
       if (Pred == ICmpInst::ICMP_SGT && (C1->isZero() || C1->isMinusOne())) {
-        return (CmpLHS == TrueVal) ? SPF_ABS : SPF_NABS;
+        return {(CmpLHS == TrueVal) ? SPF_ABS : SPF_NABS, SPNB_NA, false};
       }
 
       // ABS(X) ==> (X <s 0) ? -X : X and (X <s 1) ? -X : X
       // NABS(X) ==> (X <s 0) ? X : -X and (X <s 1) ? X : -X
       if (Pred == ICmpInst::ICMP_SLT && (C1->isZero() || C1->isOne())) {
-        return (CmpLHS == FalseVal) ? SPF_ABS : SPF_NABS;
+        return {(CmpLHS == FalseVal) ? SPF_ABS : SPF_NABS, SPNB_NA, false};
       }
     }
     
     // Y >s C ? ~Y : ~C == ~Y <s ~C ? ~Y : ~C = SMIN(~Y, ~C)
     if (const auto *C2 = dyn_cast<ConstantInt>(FalseVal)) {
       if (C1->getType() == C2->getType() && ~C1->getValue() == C2->getValue() &&
           (match(TrueVal, m_Not(m_Specific(CmpLHS))) ||
            match(CmpLHS, m_Not(m_Specific(TrueVal))))) {
         LHS = TrueVal;
         RHS = FalseVal;
-        return SPF_SMIN;
+        return {SPF_SMIN, SPNB_NA, false};
       }
     }
   }
 
   // TODO: (X > 4) ? X : 5   -->  (X >= 5) ? X : 5  -->  MAX(X, 5)
 
-  return SPF_UNKNOWN;
+  return {SPF_UNKNOWN, SPNB_NA, false};
 }
 
-static Constant *lookThroughCast(ICmpInst *CmpI, Value *V1, Value *V2,
+static Constant *lookThroughCast(CmpInst *CmpI, Value *V1, Value *V2,
                                  Instruction::CastOps *CastOp) {
   CastInst *CI = dyn_cast<CastInst>(V1);
   Constant *C = dyn_cast<Constant>(V2);
   if (!CI || !C)
     return nullptr;
   *CastOp = CI->getOpcode();
 
   if (isa<SExtInst>(CI) && CmpI->isSigned()) {
     Constant *T = ConstantExpr::getTrunc(C, CI->getSrcTy());
     // This is only valid if the truncated value can be sign-extended
     // back to the original value.
     if (ConstantExpr::getSExt(T, C->getType()) == C)
       return T;
     return nullptr;
   }
   if (isa<ZExtInst>(CI) && CmpI->isUnsigned())
     return ConstantExpr::getTrunc(C, CI->getSrcTy());
 
   if (isa<TruncInst>(CI))
     return ConstantExpr::getIntegerCast(C, CI->getSrcTy(), CmpI->isSigned());
 
+  if (isa<FPToUIInst>(CI))
+    return ConstantExpr::getUIToFP(C, CI->getSrcTy(), true);
+
+  if (isa<FPToSIInst>(CI))
+    return ConstantExpr::getSIToFP(C, CI->getSrcTy(), true);
+
+  if (isa<UIToFPInst>(CI))
+    return ConstantExpr::getFPToUI(C, CI->getSrcTy(), true);
+
+  if (isa<SIToFPInst>(CI))
+    return ConstantExpr::getFPToSI(C, CI->getSrcTy(), true);
+
+  if (isa<FPTruncInst>(CI))
+    return ConstantExpr::getFPExtend(C, CI->getSrcTy(), true);
+
+  if (isa<FPExtInst>(CI))
+    return ConstantExpr::getFPTrunc(C, CI->getSrcTy(), true);
+
   return nullptr;
 }
 
-SelectPatternFlavor llvm::matchSelectPattern(Value *V,
+SelectPatternResult llvm::matchSelectPattern(Value *V,
                                              Value *&LHS, Value *&RHS,
                                              Instruction::CastOps *CastOp) {
   SelectInst *SI = dyn_cast<SelectInst>(V);
-  if (!SI) return SPF_UNKNOWN;
+  if (!SI) return {SPF_UNKNOWN, SPNB_NA, false};
 
-  ICmpInst *CmpI = dyn_cast<ICmpInst>(SI->getCondition());
-  if (!CmpI) return SPF_UNKNOWN;
+  CmpInst *CmpI = dyn_cast<CmpInst>(SI->getCondition());
+  if (!CmpI) return {SPF_UNKNOWN, SPNB_NA, false};
 
-  ICmpInst::Predicate Pred = CmpI->getPredicate();
+  CmpInst::Predicate Pred = CmpI->getPredicate();
   Value *CmpLHS = CmpI->getOperand(0);
   Value *CmpRHS = CmpI->getOperand(1);
   Value *TrueVal = SI->getTrueValue();
   Value *FalseVal = SI->getFalseValue();
+  FastMathFlags FMF;
+  if (isa<FPMathOperator>(CmpI))
+    FMF = CmpI->getFastMathFlags();
 
   // Bail out early.
   if (CmpI->isEquality())
-    return SPF_UNKNOWN;
+    return {SPF_UNKNOWN, SPNB_NA, false};
 
   // Deal with type mismatches.
   if (CastOp && CmpLHS->getType() != TrueVal->getType()) {
     if (Constant *C = lookThroughCast(CmpI, TrueVal, FalseVal, CastOp))
-      return ::matchSelectPattern(Pred, CmpLHS, CmpRHS,
+      return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS,
                                   cast<CastInst>(TrueVal)->getOperand(0), C,
                                   LHS, RHS);
     if (Constant *C = lookThroughCast(CmpI, FalseVal, TrueVal, CastOp))
-      return ::matchSelectPattern(Pred, CmpLHS, CmpRHS,
+      return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS,
                                   C, cast<CastInst>(FalseVal)->getOperand(0),
                                   LHS, RHS);
   }
-  return ::matchSelectPattern(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal,
+  return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS, TrueVal, FalseVal,
                               LHS, RHS);
 }

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

void SelectionDAGBuilder::visitSelect(const User &I) {
   SDValue RHSVal   = getValue(I.getOperand(2));
   auto BaseOps = {Cond};
   ISD::NodeType OpCode = Cond.getValueType().isVector() ?
     ISD::VSELECT : ISD::SELECT;
 
   // Min/max matching is only viable if all output VTs are the same.
   if (std::equal(ValueVTs.begin(), ValueVTs.end(), ValueVTs.begin())) {
     Value *LHS, *RHS;
-    SelectPatternFlavor SPF = matchSelectPattern(const_cast<User*>(&I), LHS, RHS);
+    SelectPatternFlavor SPF =
+      matchSelectPattern(const_cast<User*>(&I), LHS, RHS).Flavor;
     ISD::NodeType Opc = ISD::DELETED_NODE;
     switch (SPF) {
     case SPF_UMAX: Opc = ISD::UMAX; break;
     case SPF_UMIN: Opc = ISD::UMIN; break;
     case SPF_SMAX: Opc = ISD::SMAX; break;
     case SPF_SMIN: Opc = ISD::SMIN; break;
     default: break;
     }

lib/Transforms/InstCombine/InstCombineCasts.cpp

if (Instruction *Result = commonCastTransforms(CI))
     return Result;
 
   // Test if the trunc is the user of a select which is part of a
   // minimum or maximum operation. If so, don't do any more simplification.
   // Even simplifying demanded bits can break the canonical form of a 
   // min/max.
   Value *LHS, *RHS;
   if (SelectInst *SI = dyn_cast<SelectInst>(CI.getOperand(0)))
-    if (matchSelectPattern(SI, LHS, RHS) != SPF_UNKNOWN)
+    if (matchSelectPattern(SI, LHS, RHS).Flavor != SPF_UNKNOWN)
       return nullptr;
   
   // See if we can simplify any instructions used by the input whose sole
   // purpose is to compute bits we don't care about.
   if (SimplifyDemandedInstructionBits(CI))
     return &CI;
 
   Value *Src = CI.getOperand(0);
if (BinaryOperator::isFNeg(OpI)) {
       Instruction *RI = BinaryOperator::CreateFNeg(InnerTrunc);
       RI->copyFastMathFlags(OpI);
       return RI;
     }
   }
 
   // (fptrunc (select cond, R1, Cst)) -->
   // (select cond, (fptrunc R1), (fptrunc Cst))
+  //
+  //  - but only if this isn't part of a min/max operation, else we'll
+  // ruin min/max canonical form which is to have the select and
+  // compare's operands be of the same type with no casts to look through.
+  Value *LHS, *RHS;
   SelectInst *SI = dyn_cast<SelectInst>(CI.getOperand(0));
   if (SI &&
       (isa<ConstantFP>(SI->getOperand(1)) ||
-       isa<ConstantFP>(SI->getOperand(2)))) {
+       isa<ConstantFP>(SI->getOperand(2))) &&
+      matchSelectPattern(SI, LHS, RHS).Flavor == SPF_UNKNOWN) {
     Value *LHSTrunc = Builder->CreateFPTrunc(SI->getOperand(1),
                                              CI.getType());
     Value *RHSTrunc = Builder->CreateFPTrunc(SI->getOperand(2),
                                              CI.getType());
     return SelectInst::Create(SI->getOperand(0), LHSTrunc, RHSTrunc);
   }
 
   IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI.getOperand(0));

lib/Transforms/InstCombine/InstCombineSelect.cpp

case SPF_UMIN:
     return SPF_UMAX;
   case SPF_SMAX:
     return SPF_SMIN;
   case SPF_UMAX:
     return SPF_UMIN;
   }
 }
 
-static CmpInst::Predicate getICmpPredicateForMinMax(SelectPatternFlavor SPF) {
+static CmpInst::Predicate getCmpPredicateForMinMax(SelectPatternFlavor SPF,
+                                                   bool Ordered=false) {
   switch (SPF) {
   default:
     llvm_unreachable("unhandled!");
 
   case SPF_SMIN:
     return ICmpInst::ICMP_SLT;
   case SPF_UMIN:
     return ICmpInst::ICMP_ULT;
   case SPF_SMAX:
     return ICmpInst::ICMP_SGT;
   case SPF_UMAX:
     return ICmpInst::ICMP_UGT;
+  case SPF_FMINNUM:
+    return Ordered ? FCmpInst::FCMP_OLT : FCmpInst::FCMP_ULT;
+  case SPF_FMAXNUM:
+    return Ordered ? FCmpInst::FCMP_OGT : FCmpInst::FCMP_UGT;
   }
 }
 
 static Value *generateMinMaxSelectPattern(InstCombiner::BuilderTy *Builder,
                                           SelectPatternFlavor SPF, Value *A,
                                           Value *B) {
-  CmpInst::Predicate Pred = getICmpPredicateForMinMax(SPF);
+  CmpInst::Predicate Pred = getCmpPredicateForMinMax(SPF);
+  assert(CmpInst::isIntPredicate(Pred));
   return Builder->CreateSelect(Builder->CreateICmp(Pred, A, B), A, B);
 }
 
 /// GetSelectFoldableOperands - We want to turn code that looks like this:
 ///   %C = or %A, %B
 ///   %D = select %cond, %C, %A
 /// into:
 ///   %C = select %cond, %B, 0
if (FCI->getOperand(0) == TrueVal && FCI->getOperand(1) == FalseVal) {
 
       // Canonicalize to use ordered comparisons by swapping the select
       // operands.
       //
       // e.g.
       // (X ugt Y) ? X : Y -> (X ole Y) ? Y : X
       if (FCI->hasOneUse() && FCmpInst::isUnordered(FCI->getPredicate())) {
         FCmpInst::Predicate InvPred = FCI->getInversePredicate();
+        IRBuilder<>::FastMathFlagGuard FMFG(*Builder);
+        Builder->SetFastMathFlags(FCI->getFastMathFlags());
         Value *NewCond = Builder->CreateFCmp(InvPred, TrueVal, FalseVal,
                                              FCI->getName() + ".inv");
 
         return SelectInst::Create(NewCond, FalseVal, TrueVal,
                                   SI.getName() + ".p");
       }
 
       // NOTE: if we wanted to, this is where to detect MIN/MAX
if (FCI->getOperand(0) == TrueVal && FCI->getOperand(1) == FalseVal) {
 
       // Canonicalize to use ordered comparisons by swapping the select
       // operands.
       //
       // e.g.
       // (X ugt Y) ? X : Y -> (X ole Y) ? X : Y
       if (FCI->hasOneUse() && FCmpInst::isUnordered(FCI->getPredicate())) {
         FCmpInst::Predicate InvPred = FCI->getInversePredicate();
+        IRBuilder<>::FastMathFlagGuard FMFG(*Builder);
+        Builder->SetFastMathFlags(FCI->getFastMathFlags());
         Value *NewCond = Builder->CreateFCmp(InvPred, FalseVal, TrueVal,
                                              FCI->getName() + ".inv");
 
         return SelectInst::Create(NewCond, FalseVal, TrueVal,
                                   SI.getName() + ".p");
       }
 
       // NOTE: if we wanted to, this is where to detect MIN/MAX
if (Instruction *FI = dyn_cast<Instruction>(FalseVal))
               return RI;
             } else
               return BinaryOperator::CreateAdd(SubOp->getOperand(0), NewSel);
           }
         }
       }
 
   // See if we can fold the select into one of our operands.
-  if (SI.getType()->isIntOrIntVectorTy()) {
+  if (SI.getType()->isIntOrIntVectorTy() || SI.getType()->isFPOrFPVectorTy()) {
     if (Instruction *FoldI = FoldSelectIntoOp(SI, TrueVal, FalseVal))
       return FoldI;
 
     Value *LHS, *RHS, *LHS2, *RHS2;
     Instruction::CastOps CastOp;
-    SelectPatternFlavor SPF = matchSelectPattern(&SI, LHS, RHS, &CastOp);
+    SelectPatternResult SPR = matchSelectPattern(&SI, LHS, RHS, &CastOp);
+    auto SPF = SPR.Flavor;
 
     if (SPF) {
       // Canonicalize so that type casts are outside select patterns.
       if (LHS->getType()->getPrimitiveSizeInBits() !=
           SI.getType()->getPrimitiveSizeInBits()) {
-        CmpInst::Predicate Pred = getICmpPredicateForMinMax(SPF);
-        Value *Cmp = Builder->CreateICmp(Pred, LHS, RHS);
+        CmpInst::Predicate Pred = getCmpPredicateForMinMax(SPF, SPR.Ordered);
+
+        Value *Cmp;
+        if (CmpInst::isIntPredicate(Pred)) {
+          Cmp = Builder->CreateICmp(Pred, LHS, RHS);
+        } else {
+          IRBuilder<>::FastMathFlagGuard FMFG(*Builder);
+          auto FMF = cast<FPMathOperator>(SI.getCondition())->getFastMathFlags();
+          Builder->SetFastMathFlags(FMF);
+          Cmp = Builder->CreateFCmp(Pred, LHS, RHS);
+        }
+
         Value *NewSI = Builder->CreateCast(CastOp,
                                            Builder->CreateSelect(Cmp, LHS, RHS),
                                            SI.getType());
         return ReplaceInstUsesWith(SI, NewSI);
       }
 
       // MAX(MAX(a, b), a) -> MAX(a, b)
       // MIN(MIN(a, b), a) -> MIN(a, b)
       // MAX(MIN(a, b), a) -> a
       // MIN(MAX(a, b), a) -> a
-      if (SelectPatternFlavor SPF2 = matchSelectPattern(LHS, LHS2, RHS2))
+      if (SelectPatternFlavor SPF2 = matchSelectPattern(LHS, LHS2, RHS2).Flavor)
         if (Instruction *R = FoldSPFofSPF(cast<Instruction>(LHS),SPF2,LHS2,RHS2,
                                           SI, SPF, RHS))
           return R;
-      if (SelectPatternFlavor SPF2 = matchSelectPattern(RHS, LHS2, RHS2))
+      if (SelectPatternFlavor SPF2 = matchSelectPattern(RHS, LHS2, RHS2).Flavor)
         if (Instruction *R = FoldSPFofSPF(cast<Instruction>(RHS),SPF2,LHS2,RHS2,
                                           SI, SPF, LHS))
           return R;
     }
 
     // MAX(~a, ~b) -> ~MIN(a, b)
     if (SPF == SPF_SMAX || SPF == SPF_UMAX) {
       if (IsFreeToInvert(LHS, LHS->hasNUses(2)) &&

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

case Instruction::Xor: {
     // Output known-1 are known to be set if set in only one of the LHS, RHS.
     KnownOne = (RHSKnownZero & LHSKnownOne) | (RHSKnownOne & LHSKnownZero);
     break;
   }
   case Instruction::Select:
     // If this is a select as part of a min/max pattern, don't simplify any
     // further in case we break the structure.
     Value *LHS, *RHS;
-    if (matchSelectPattern(I, LHS, RHS) != SPF_UNKNOWN)
+    if (matchSelectPattern(I, LHS, RHS).Flavor != SPF_UNKNOWN)
       return nullptr;
       
     if (SimplifyDemandedBits(I->getOperandUse(2), DemandedMask, RHSKnownZero,
                              RHSKnownOne, Depth + 1) ||
         SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, LHSKnownZero,
                              LHSKnownOne, Depth + 1))
       return I;
     assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?");

test/Transforms/InstCombine/minmax-fp.ll

+; RUN: opt -S -instcombine < %s | FileCheck %s
+
+; CHECK-LABEL: @t1
+; CHECK-NEXT: fcmp oge float %a, 5.000000e+00
+; CHECK-NEXT: select i1 %.inv, float 5.000000e+00, float %a
+; CHECK-NEXT: fpext float %1 to double
+define double @t1(float %a) {
+  ; This is the canonical form for a type-changing min/max.
+  %1 = fcmp ult float %a, 5.0
+  %2 = select i1 %1, float %a, float 5.0
+  %3 = fpext float %2 to double
+  ret double %3
+}
+
+; CHECK-LABEL: @t2
+; CHECK-NEXT: fcmp oge float %a, 5.000000e+00
+; CHECK-NEXT: select i1 %.inv, float 5.000000e+00, float %a
+; CHECK-NEXT: fpext float %1 to double
+define double @t2(float %a) {
+  ; Check this is converted into canonical form, as above.
+  %1 = fcmp ult float %a, 5.0
+  %2 = fpext float %a to double
+  %3 = select i1 %1, double %2, double 5.0
+  ret double %3
+}
+
+; CHECK-LABEL: @t4
+; CHECK-NEXT: fcmp oge double %a, 5.000000e+00
+; CHECK-NEXT: select i1 %.inv, double 5.000000e+00, double %a
+; CHECK-NEXT: fptrunc double %1 to float
+define float @t4(double %a) {
+  ; Same again, with trunc.
+  %1 = fcmp ult double %a, 5.0
+  %2 = fptrunc double %a to float
+  %3 = select i1 %1, float %2, float 5.0
+  ret float %3
+}
+
+; CHECK-LABEL: @t5
+; CHECK-NEXT: fcmp ult float %a, 5.000000e+00
+; CHECK-NEXT: fpext float %a to double
+; CHECK-NEXT: select i1 %1, double %2, double 5.001
+define double @t5(float %a) {
+  ; different values, should not be converted.
+  %1 = fcmp ult float %a, 5.0
+  %2 = fpext float %a to double
+  %3 = select i1 %1, double %2, double 5.001
+  ret double %3
+}
+
+; CHECK-LABEL: @t6
+; CHECK-NEXT: fcmp ult float %a, -0.0
+; CHECK-NEXT: fpext float %a to double
+; CHECK-NEXT: select i1 %1, double %2, double 0.0
+define double @t6(float %a) {
+  ; Signed zero, should not be converted
+  %1 = fcmp ult float %a, -0.0
+  %2 = fpext float %a to double
+  %3 = select i1 %1, double %2, double 0.0
+  ret double %3
+}
+
+; CHECK-LABEL: @t7
+; CHECK-NEXT: fcmp ult float %a, 0.0
+; CHECK-NEXT: fpext float %a to double
+; CHECK-NEXT: select i1 %1, double %2, double -0.0
+define double @t7(float %a) {
+  ; Signed zero, should not be converted
+  %1 = fcmp ult float %a, 0.0
+  %2 = fpext float %a to double
+  %3 = select i1 %1, double %2, double -0.0
+  ret double %3
+}
+
+; CHECK-LABEL: @t8
+; CHECK-NEXT: fcmp oge float %a, 5.000000e+00
+; CHECK-NEXT: select i1 %.inv, float 5.000000e+00, float %a
+; CHECK-NEXT: fptoui float %1 to i64
+define i64 @t8(float %a) {
+  %1 = fcmp ult float %a, 5.0
+  %2 = fptoui float %a to i64
+  %3 = select i1 %1, i64 %2, i64 5
+  ret i64 %3
+}
+
+; CHECK-LABEL: @t9
+; CHECK-NEXT: fcmp oge float %a, 0.000000e+00
+; CHECK-NEXT: select i1 %.inv, float 0.000000e+00, float %a
+; CHECK-NEXT: fptosi float %1 to i8
+define i8 @t9(float %a) {
+  %1 = fcmp ult float %a, 0.0
+  %2 = fptosi float %a to i8
+  %3 = select i1 %1, i8 %2, i8 0
+  ret i8 %3
+}
+
+; CHECK-LABEL: @t11
+; CHECK-NEXT: fcmp fast oge float %b, %a
+; CHECK-NEXT: select i1 %.inv, float %a, float %b
+; CHECK-NEXT: fptosi
+define i8 @t11(float %a, float %b) {
+  ; Either operand could be NaN, but fast modifier applied.
+  %1 = fcmp fast ult float %b, %a
+  %2 = fptosi float %a to i8
+  %3 = fptosi float %b to i8
+  %4 = select i1 %1, i8 %3, i8 %2
+  ret i8 %4
+}
+
+; CHECK-LABEL: @t12
+; CHECK-NEXT: fcmp nnan oge float %b, %a
+; CHECK-NEXT: select i1 %.inv, float %a, float %b
+; CHECK-NEXT: fptosi float %.v to i8
+define i8 @t12(float %a, float %b) {
+  ; Either operand could be NaN, but nnan modifier applied.
+  %1 = fcmp nnan ult float %b, %a
+  %2 = fptosi float %a to i8
+  %3 = fptosi float %b to i8
+  %4 = select i1 %1, i8 %3, i8 %2
+  ret i8 %4
+}
+
+; CHECK-LABEL: @t13
+; CHECK-NEXT: fcmp ult float %a, 1.500000e+00
+; CHECK-NEXT: fptosi float %a to i8
+; CHECK-NEXT: select i1 %1, i8 %2, i8 1
+define i8 @t13(float %a) {
+  ; Float and int values do not match.
+  %1 = fcmp ult float %a, 1.5
+  %2 = fptosi float %a to i8
+  %3 = select i1 %1, i8 %2, i8 1
+  ret i8 %3
+}
+
+; CHECK-LABEL: @t14
+; CHECK-NEXT: fcmp ule float %a, 0.000000e+00
+; CHECK-NEXT: fptosi float %a to i8
+; CHECK-NEXT: select i1 %1, i8 %2, i8 0
+define i8 @t14(float %a) {
+  ; <= comparison, where %a could be -0.0. Not safe.
+  %1 = fcmp ule float %a, 0.0
+  %2 = fptosi float %a to i8
+  %3 = select i1 %1, i8 %2, i8 0
+  ret i8 %3
+}
+
+; CHECK-LABEL: @t15
+; CHECK-NEXT: fcmp nsz oge float %a, 0.000000e+00
+; CHECK-NEXT: select i1 %.inv, float 0.000000e+00, float %a
+; CHECK-NEXT: fptosi float %1 to i8
+define i8 @t15(float %a) {
+  %1 = fcmp nsz ule float %a, 0.0
+  %2 = fptosi float %a to i8
+  %3 = select i1 %1, i8 %2, i8 0
+  ret i8 %3
+}

unittests/Analysis/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   IPA
   Analysis
   AsmParser
   Core
   Support
   )
 
 add_llvm_unittest(AnalysisTests
   AliasAnalysisTest.cpp
   CallGraphTest.cpp
   CFGTest.cpp
   LazyCallGraphTest.cpp
   ScalarEvolutionTest.cpp
   MixedTBAATest.cpp
+  ValueTrackingTest.cpp
   )

unittests/Analysis/ValueTrackingTest.cpp

+//===- ValueTrackingTest.cpp - ValueTracking tests ------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/SourceMgr.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+class MatchSelectPatternTest : public testing::Test {
+protected:
+  void parseAssembly(const char *Assembly) {
+    SMDiagnostic Error;
+    M = parseAssemblyString(Assembly, Error, getGlobalContext());
+
+    std::string errMsg;
+    raw_string_ostream os(errMsg);
+    Error.print("", os);
+
+    // A failure here means that the test itself is buggy.
+    if (!M)
+      report_fatal_error(os.str());
+
+    Function *F = M->getFunction("test");
+    if (F == nullptr)
+      report_fatal_error("Test must have a function named @test");
+
+    A = nullptr;
+    for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
+      if (I->hasName()) {
+        if (I->getName() == "A")
+          A = &*I;
+      }
+    }
+    if (A == nullptr)
+      report_fatal_error("@test must have an instruction %A");
+  }
+
+  void expectPattern(const SelectPatternResult &P) {
+    Value *LHS, *RHS;
+    Instruction::CastOps CastOp;
+    SelectPatternResult R = matchSelectPattern(A, LHS, RHS, &CastOp);
+    EXPECT_EQ(P.Flavor, R.Flavor);
+    EXPECT_EQ(P.NaNBehavior, R.NaNBehavior);
+    EXPECT_EQ(P.Ordered, R.Ordered);
+  }
+
+  std::unique_ptr<Module> M;
+  Instruction *A, *B;
+};
+
+}
+
+TEST_F(MatchSelectPatternTest, SimpleFMin) {
+  parseAssembly(
+      "define float @test(float %a) {\n"
+      "  %1 = fcmp ult float %a, 5.0\n"
+      "  %A = select i1 %1, float %a, float 5.0\n"
+      "  ret float %A\n"
+      "}\n");
+  expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false});
+}
+
+TEST_F(MatchSelectPatternTest, SimpleFMax) {
+  parseAssembly(
+      "define float @test(float %a) {\n"
+      "  %1 = fcmp ogt float %a, 5.0\n"
+      "  %A = select i1 %1, float %a, float 5.0\n"
+      "  ret float %A\n"
+      "}\n");
+  expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true});
+}
+
+TEST_F(MatchSelectPatternTest, SwappedFMax) {
+  parseAssembly(
+      "define float @test(float %a) {\n"
+      "  %1 = fcmp olt float 5.0, %a\n"
+      "  %A = select i1 %1, float %a, float 5.0\n"
+      "  ret float %A\n"
+      "}\n");
+  expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, false});
+}
+
+TEST_F(MatchSelectPatternTest, SwappedFMax2) {
+  parseAssembly(
+      "define float @test(float %a) {\n"
+      "  %1 = fcmp olt float %a, 5.0\n"
+      "  %A = select i1 %1, float 5.0, float %a\n"
+      "  ret float %A\n"
+      "}\n");
+  expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, false});
+}
+
+TEST_F(MatchSelectPatternTest, SwappedFMax3) {
+  parseAssembly(
+      "define float @test(float %a) {\n"
+      "  %1 = fcmp ult float %a, 5.0\n"
+      "  %A = select i1 %1, float 5.0, float %a\n"
+      "  ret float %A\n"
+      "}\n");
+  expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true});
+}
+
+TEST_F(MatchSelectPatternTest, FastFMin) {
+  parseAssembly(
+      "define float @test(float %a) {\n"
+      "  %1 = fcmp nnan olt float %a, 5.0\n"
+      "  %A = select i1 %1, float %a, float 5.0\n"
+      "  ret float %A\n"
+      "}\n");
+  expectPattern({SPF_FMINNUM, SPNB_RETURNS_ANY, false});
+}
+
+TEST_F(MatchSelectPatternTest, FMinConstantZero) {
+  parseAssembly(
+      "define float @test(float %a) {\n"
+      "  %1 = fcmp ole float %a, 0.0\n"
+      "  %A = select i1 %1, float %a, float 0.0\n"
+      "  ret float %A\n"
+      "}\n");
+  // This shouldn't be matched, as %a could be -0.0.
+  expectPattern({SPF_UNKNOWN, SPNB_NA, false});
+}
+
+TEST_F(MatchSelectPatternTest, FMinConstantZeroNsz) {
+  parseAssembly(
+      "define float @test(float %a) {\n"
+      "  %1 = fcmp nsz ole float %a, 0.0\n"
+      "  %A = select i1 %1, float %a, float 0.0\n"
+      "  ret float %A\n"
+      "}\n");
+  // But this should be, because we've ignored signed zeroes.
+  expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true});
+}