Correct instcombine of fcmp+select.

[csigg]

Summary

1. Zero fcmp arguments were previously replaced with zero select arguments without considering or adjusting the predicate. However, without no-signed-zeros, only the following are equivalent:

   >= +0  <=>     > -0
   <= -0  <=>     < +0
-0 >=     <=>  +0 >
+0 <=     <=>  -0 <

2. Combining fcmp+select into fminnum is not permitted when the arguments might be two zeros of opposite sign. E.g., fminnum(-0, +0) can return any of the two operands and is therefore not equivalent to '-0 < +0 ? -0 : +0'. This was handled for >= and <= but marked as 'FIXME' for > and <.

3. fminimum does treat -0 as smaller than +0, so fcmp+select can be combined if the NaN-propagating bahaviour of fminimum is permitted. Previously, the handling of signed zeros applied to combining fcmp+select into both fminnum and fminimum.

The same applies for fmaxnum/fmaximum.

Hopefully 3) can make up for the performance lost by fixing 1) and 2).

[csigg]

Rebase.

[csigg]

Rebase.

[spatel]

Something has gone wrong with the diff.

Sorry - I didn't remember this patch when I was looking at a bug fix with:
4e44c22c97be

We may need more unit and/or IR tests to verify that we are getting the correct results for all of these patterns.

[csigg]

In D118126#3786685, @spatel wrote:

Something has gone wrong with the diff.

Very much so, I rebased the wrong diff :-(

Let me try to resurrect it.

[csigg]

Restore diff.

[spatel]

In D118126#3787161, @csigg wrote:

Restore diff.

Still need to update to account for the changes 4e44c22c97be?

llvm/lib/Analysis/ValueTracking.cpp

if (CmpInst::isFPPredicate(Pred)) {
     if (match(TrueVal, m_AnyZeroFP()) && !match(FalseVal, m_AnyZeroFP()) &&
         !cast<Constant>(TrueVal)->containsUndefOrPoisonElement())
       OutputZeroVal = TrueVal;
     else if (match(FalseVal, m_AnyZeroFP()) && !match(TrueVal, m_AnyZeroFP()) &&
              !cast<Constant>(FalseVal)->containsUndefOrPoisonElement())
       OutputZeroVal = FalseVal;
 
     if (OutputZeroVal) {
-      if (match(CmpLHS, m_AnyZeroFP()))
+      // Tries to adjust 'Pred' so that we can flip the sign of one of its zero
+      // operands. SideAndSignBit must be true iff the LHS is positive or iff
+      // the RHS operand is negative. Applies the following equivalences:
+      // >= +0  <=>  > -0  and  -0 >=  <=>  +0 >
+      // <= -0  <=>  < +0  and  +0 <=  <=>  -0 <
+      auto MaybeAdjustPredicate = [&](bool SideAndSignBit) {
+        switch (Pred) {
+        case CmpInst::FCMP_OGT:
+          return SideAndSignBit ? (Pred = CmpInst::FCMP_OGE, true) : false;
+        case CmpInst::FCMP_UGT:
+          return SideAndSignBit ? (Pred = CmpInst::FCMP_UGE, true) : false;
+        case CmpInst::FCMP_OLE:
+          return SideAndSignBit ? (Pred = CmpInst::FCMP_OLT, true) : false;
+        case CmpInst::FCMP_ULE:
+          return SideAndSignBit ? (Pred = CmpInst::FCMP_ULT, true) : false;
+        case CmpInst::FCMP_OGE:
+          return SideAndSignBit ? false : (Pred = CmpInst::FCMP_OGT, true);
+        case CmpInst::FCMP_UGE:
+          return SideAndSignBit ? false : (Pred = CmpInst::FCMP_UGT, true);
+        case CmpInst::FCMP_OLT:
+          return SideAndSignBit ? false : (Pred = CmpInst::FCMP_OLE, true);
+        case CmpInst::FCMP_ULT:
+          return SideAndSignBit ? false : (Pred = CmpInst::FCMP_ULE, true);
+        default:
+          return false;
+        }
+      };
+
+      bool ZeroSignBit = match(OutputZeroVal, m_NegZeroFP());
+      if (match(CmpLHS, m_AnyZeroFP())) {
+        bool SignLHS = match(CmpLHS, m_NegZeroFP());
+        if (FMF.noSignedZeros() || ZeroSignBit == SignLHS ||
+            MaybeAdjustPredicate(SignLHS == false)) {
           CmpLHS = OutputZeroVal;
-      if (match(CmpRHS, m_AnyZeroFP()))
+        }
+      }
+      if (match(CmpRHS, m_AnyZeroFP())) {
+        bool SignRHS = match(CmpLHS, m_NegZeroFP());
+        if (FMF.noSignedZeros() || ZeroSignBit == SignRHS ||
+            MaybeAdjustPredicate(SignRHS == true)) {
           CmpRHS = OutputZeroVal;
         }
       }
+    }
+  }
 
   LHS = CmpLHS;
   RHS = CmpRHS;
 
-  // Signed zero 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 zero.
-  switch (Pred) {
-  default: break;
-  // FIXME: Include OGT/OLT/UGT/ULT.
-  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 (TrueVal == CmpRHS && FalseVal == CmpLHS) {
     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;
   }
 
+  switch (Pred) {
+  default:
+    break;
+  case CmpInst::FCMP_OGT:
+  case CmpInst::FCMP_OGE:
+  case CmpInst::FCMP_OLT:
+  case CmpInst::FCMP_OLE:
+  case CmpInst::FCMP_UGT:
+  case CmpInst::FCMP_UGE:
+  case CmpInst::FCMP_ULT:
+  case CmpInst::FCMP_ULE:
+    if (!FMF.noSignedZeros() && !isKnownNonZero(CmpLHS) &&
+        !isKnownNonZero(CmpRHS)) {
+      // According to (IEEE 754-2008 5.3.1), minNum(0.0, -0.0) and similar may
+      // return either -0.0 or 0.0, so fcmp/select pair has stricter semantics
+      // than minNum. Bail out unless at least one operand is known to be
+      // non-zero or we don't care about signed zeros.
+      if (NaNBehavior == SPNB_RETURNS_OTHER)
+        return {SPF_UNKNOWN, SPNB_NA, false};
+      // Prevent combining into minNum/maxNum because of the stricter semantics
+      // described above, but allow combining into minimum/maximum, which does
+      // guarantee that -0.0 is less than 0.0.
+      if (NaNBehavior == SPNB_RETURNS_ANY)
+        NaNBehavior = SPNB_RETURNS_NAN;
+    }
+  }
+
   // ([if]cmp X, Y) ? X : Y
   if (TrueVal == CmpLHS && FalseVal == CmpRHS) {
     switch (Pred) {
     default: return {SPF_UNKNOWN, SPNB_NA, false}; // Equality.
     case ICmpInst::ICMP_UGT:
     case ICmpInst::ICMP_UGE: return {SPF_UMAX, SPNB_NA, false};
     case ICmpInst::ICMP_SGT:
     case ICmpInst::ICMP_SGE: return {SPF_SMAX, SPNB_NA, false};
else if (match(FalseVal, MaybeSExtCmpLHS)) {
       if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, ZeroOrOne))
         return {SPF_ABS, SPNB_NA, false};
     }
   }
 
   if (CmpInst::isIntPredicate(Pred))
     return matchMinMax(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal, LHS, RHS, Depth);
 
-  // According to (IEEE 754-2008 5.3.1), minNum(0.0, -0.0) and similar
-  // may return either -0.0 or 0.0, so fcmp/select pair has stricter
-  // semantics than minNum. Be conservative in such case.
-  if (NaNBehavior != SPNB_RETURNS_ANY ||
-      (!FMF.noSignedZeros() && !isKnownNonZero(CmpLHS) &&
-       !isKnownNonZero(CmpRHS)))
+  if (NaNBehavior != SPNB_RETURNS_ANY)
     return {SPF_UNKNOWN, SPNB_NA, false};
 
   return matchFastFloatClamp(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal, LHS, RHS);
 }
 
 /// Helps to match a select pattern in case of a type mismatch.
 ///
 /// The function processes the case when type of true and false values of a

llvm/test/CodeGen/AArch64/arm64-fmax-safe.ll

; CHECK-LABEL: test_cross:
   %cmp = fcmp ult float %in, 0.000000e+00
   %val = select i1 %cmp, float %in, float 0.000000e+00
   %longer = fpext float %val to double
   ret double %longer
 
 ; CHECK: fmin s
 }
 
-; Same as previous, but with ordered comparison;
+; Same as previous, but with ordered comparison and no-signed-zero;
 ; must become fminnm, not fmin.
 define double @test_cross_fail_nan(float %in) {
 ; CHECK-LABEL: test_cross_fail_nan:
-  %cmp = fcmp olt float %in, 0.000000e+00
+  %cmp = fcmp nsz olt float %in, 0.000000e+00
   %val = select i1 %cmp, float %in, float 0.000000e+00
   %longer = fpext float %val to double
   ret double %longer
 
 ; CHECK: fminnm s
 }
 
 ; This isn't a min or a max, but passes the first condition for swapping the

llvm/test/CodeGen/ARM/fp16-vminmaxnm-safe.ll

 ; CHECK-NEXT:    vselge.f16 s0, s0, s2
 ; CHECK-NEXT:    vmov r0, s0
 ; CHECK-NEXT:    bx lr
 ; CHECK-NEXT:    .p2align 1
 ; CHECK-NEXT:  @ %bb.1:
 ; CHECK-NEXT:  .LCPI23_0:
 ; CHECK-NEXT:    .short 0x8000 @ half -0
 entry:
-  %cmp1 = fcmp olt half %a, -0.
+  %cmp1 = fcmp nsz olt half %a, -0.
   %cond1 = select i1 %cmp1, half %a, half -0.
   %cmp2 = fcmp ugt half %cond1, -0.
   %cond2 = select i1 %cmp2, half %cond1, half -0.
   ret half %cond2
 }
 
 define half @fp16_vminmaxnm_e_0(half %a) {
 ; CHECK-LABEL: fp16_vminmaxnm_e_0:

llvm/test/CodeGen/ARM/neon_minmax.ll

 ; RUN: llc -mtriple=arm-eabi -mcpu=swift %s -o - | FileCheck %s
 ; RUN: llc -mtriple=arm-eabi -mcpu=cortex-a8 -mattr=-neon %s -o -
 
 define float @fmin_ole(float %x) nounwind {
 ;CHECK-LABEL: fmin_ole:
 ;CHECK: vmin.f32
   %cond = fcmp ole float 1.0, %x
   %min1 = select i1 %cond, float 1.0, float %x
   ret float %min1
 }
 
 define float @fmin_ole_zero(float %x) nounwind {
 ;CHECK-LABEL: fmin_ole_zero:
-;CHECK-NOT: vmin.f32
+;CHECK: vmin.f32
   %cond = fcmp ole float 0.0, %x
   %min1 = select i1 %cond, float 0.0, float %x
   ret float %min1
 }
 
 define float @fmin_ult(float %x) nounwind {
 ;CHECK-LABEL: fmin_ult:
 ;CHECK: vmin.f32

 ;CHECK: vmax.f32
   %cond = fcmp uge float %x, 1.0
   %max1 = select i1 %cond, float %x, float 1.0
   ret float %max1
 }
 
 define float @fmax_uge_zero(float %x) nounwind {
 ;CHECK-LABEL: fmax_uge_zero:
-;CHECK-NOT: vmax.f32
+;CHECK: vmax.f32
   %cond = fcmp uge float %x, 0.0
   %max1 = select i1 %cond, float %x, float 0.0
   ret float %max1
 }
 
 define float @fmax_olt_reverse(float %x) nounwind {
 ;CHECK-LABEL: fmax_olt_reverse:
 ;CHECK: vmax.f32

llvm/test/CodeGen/ARM/vminmaxnm-safe.ll

; CHECK-NOT: vmaxnm.f64
   %cond2 = select i1 %cmp2, double 90., double %cond1
   ret double %cond2
 }
 
 define float @fp-armv8_vminmaxnm_0(float %a) {
 ; CHECK-LABEL: "fp-armv8_vminmaxnm_0":
 ; CHECK-NOT: vminnm.f32
 ; CHECK: vmaxnm.f32
-  %cmp1 = fcmp ult float %a, 0.
+  %cmp1 = fcmp nsz ult float %a, 0.
   %cond1 = select i1 %cmp1, float %a, float 0.
-  %cmp2 = fcmp ogt float %cond1, 0.
+  %cmp2 = fcmp nsz ogt float %cond1, 0.
   %cond2 = select i1 %cmp2, float %cond1, float 0.
   ret float %cond2
 }
 
 define float @fp-armv8_vminmaxnm_neg0(float %a) {
 ; CHECK-LABEL: "fp-armv8_vminmaxnm_neg0":
 ; CHECK: vminnm.f32
 ; CHECK-NOT: vmaxnm.f32
-  %cmp1 = fcmp olt float %a, -0.
+  %cmp1 = fcmp nsz olt float %a, -0.
   %cond1 = select i1 %cmp1, float %a, float -0.
   %cmp2 = fcmp ugt float %cond1, -0.
   %cond2 = select i1 %cmp2, float %cond1, float -0.
   ret float %cond2
 }
 
 define float @fp-armv8_vminmaxnm_e_0(float %a) {
 ; CHECK-LABEL: "fp-armv8_vminmaxnm_e_0":

llvm/test/Transforms/InstCombine/minmax-fp.ll

;
   ret double %3
 }
 
 ; From IEEE754: "Comparisons shall ignore the sign of zero (so +0 = -0)."
 ; So the compare constant may be treated as -0.0, and we sink the fpext.
 
 define double @t7(float %a) {
 ; CHECK-LABEL: @t7(
-; CHECK-NEXT:    [[DOTINV:%.*]] = fcmp oge float [[A:%.*]], 0.000000e+00
+; CHECK-NEXT:    [[DOTINV:%.*]] = fcmp oge float [[A:%.*]], -0.000000e+00
 ; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[DOTINV]], float -0.000000e+00, float [[A]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = fpext float [[TMP1]] to double
 ; CHECK-NEXT:    ret double [[TMP2]]
 ;
   %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
;
   %min2 = select i1 %cmp2, float %min1, float 0.0
   ret float %min2
 }
 
 ; max(max(x, -0.0), -0.0) --> max(x, -0.0)
 
 define float @fmax_fmax_zero_mismatch(float %x) {
 ; CHECK-LABEL: @fmax_fmax_zero_mismatch(
-; CHECK-NEXT:    [[TMP1:%.*]] = fcmp ogt float [[X:%.*]], -0.000000e+00
+; CHECK-NEXT:    [[TMP1:%.*]] = fcmp nsz ogt float [[X:%.*]], -0.000000e+00
 ; CHECK-NEXT:    [[MAX11:%.*]] = select i1 [[TMP1]], float [[X]], float -0.000000e+00
 ; CHECK-NEXT:    ret float [[MAX11]]
 ;
-  %cmp1 = fcmp ogt float %x, 0.0
+  %cmp1 = fcmp nsz ogt float %x, 0.0
   %max1 = select i1 %cmp1, float %x, float -0.0
-  %cmp2 = fcmp ogt float 0.0, %max1
+  %cmp2 = fcmp nsz ogt float 0.0, %max1
   %max2 = select i1 %cmp2, float -0.0, float %max1
   ret float %max2
 }
 
 define i64 @t8(float %a) {
 ; CHECK-LABEL: @t8(
 ; CHECK-NEXT:    [[DOTINV:%.*]] = fcmp oge float [[A:%.*]], 5.000000e+00
 ; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[DOTINV]], float 5.000000e+00, float [[A]]

llvm/unittests/Analysis/ValueTrackingTest.cpp

 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero3) {
   parseAssembly(
       "define float @test(float %a) {\n"
       "  %1 = fcmp olt float 0.0, %a\n"
       "  %A = select i1 %1, float -0.0, float %a\n"
       "  ret float %A\n"
       "}\n");
   // The sign of zero doesn't matter in fcmp.
-  expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, true});
+  expectPattern({SPF_UNKNOWN, SPNB_NA, false});
 }
 
 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero4) {
   parseAssembly(
       "define float @test(float %a) {\n"
       "  %1 = fcmp ogt float %a, 0.0\n"
       "  %A = select i1 %1, float -0.0, float %a\n"
       "  ret float %A\n"
       "}\n");
   // The sign of zero doesn't matter in fcmp.
-  expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false});
+  expectPattern({SPF_UNKNOWN, SPNB_NA, false});
 }
 
 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero5) {
   parseAssembly(
       "define float @test(float %a) {\n"
       "  %1 = fcmp ogt float -0.0, %a\n"
       "  %A = select i1 %1, float %a, float 0.0\n"
       "  ret float %A\n"
       "}\n");
   // The sign of zero doesn't matter in fcmp.
-  expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, false});
+  expectPattern({SPF_UNKNOWN, SPNB_NA, false});
 }
 
 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero6) {
   parseAssembly(
       "define float @test(float %a) {\n"
       "  %1 = fcmp olt float %a, -0.0\n"
       "  %A = select i1 %1, float %a, float 0.0\n"
       "  ret float %A\n"
       "}\n");
   // The sign of zero doesn't matter in fcmp.
-  expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true});
+  expectPattern({SPF_UNKNOWN, SPNB_NA, false});
 }
 
 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero7) {
   parseAssembly(
       "define float @test(float %a) {\n"
       "  %1 = fcmp ogt float 0.0, %a\n"
       "  %A = select i1 %1, float %a, float -0.0\n"
       "  ret float %A\n"
       "}\n");
   // The sign of zero doesn't matter in fcmp.
-  expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, false});
+  expectPattern({SPF_UNKNOWN, SPNB_NA, false});
 }
 
 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZero8) {
   parseAssembly(
       "define float @test(float %a) {\n"
       "  %1 = fcmp olt float %a, 0.0\n"
       "  %A = select i1 %1, float %a, float -0.0\n"
       "  ret float %A\n"
       "}\n");
   // The sign of zero doesn't matter in fcmp.
-  expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true});
+  expectPattern({SPF_UNKNOWN, SPNB_NA, false});
 }
 
 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero1) {
   parseAssembly(
       "define float @test(float %a) {\n"
       "  %1 = fcmp ogt float -0.0, %a\n"
       "  %A = select i1 %1, float 0.0, float %a\n"
       "  ret float %A\n"
       "}\n");
   // The sign of zero doesn't matter in fcmp.
-  expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, true});
+  expectPattern({SPF_UNKNOWN, SPNB_NA, false});
 }
 
 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero2) {
   parseAssembly(
       "define float @test(float %a) {\n"
       "  %1 = fcmp olt float %a, -0.0\n"
       "  %A = select i1 %1, float 0.0, float %a\n"
       "  ret float %A\n"

 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero5) {
   parseAssembly(
       "define float @test(float %a) {\n"
       "  %1 = fcmp olt float -0.0, %a\n"
       "  %A = select i1 %1, float %a, float 0.0\n"
       "  ret float %A\n"
       "}\n");
   // The sign of zero doesn't matter in fcmp.
-  expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, false});
+  expectPattern({SPF_UNKNOWN, SPNB_NA, false});
 }
 
 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero6) {
   parseAssembly(
       "define float @test(float %a) {\n"
       "  %1 = fcmp ogt float %a, -0.0\n"
       "  %A = select i1 %1, float %a, float 0.0\n"
       "  ret float %A\n"
       "}\n");
   // The sign of zero doesn't matter in fcmp.
-  expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true});
+  expectPattern({SPF_UNKNOWN, SPNB_NA, false});
 }
 
 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero7) {
   parseAssembly(
       "define float @test(float %a) {\n"
       "  %1 = fcmp olt float 0.0, %a\n"
       "  %A = select i1 %1, float %a, float -0.0\n"
       "  ret float %A\n"
       "}\n");
   // The sign of zero doesn't matter in fcmp.
-  expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, false});
+  expectPattern({SPF_UNKNOWN, SPNB_NA, false});
 }
 
 TEST_F(MatchSelectPatternTest, FMaxMismatchConstantZero8) {
   parseAssembly(
       "define float @test(float %a) {\n"
       "  %1 = fcmp ogt float %a, 0.0\n"
       "  %A = select i1 %1, float %a, float -0.0\n"
       "  ret float %A\n"
       "}\n");
   // The sign of zero doesn't matter in fcmp.
-  expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true});
+  expectPattern({SPF_UNKNOWN, SPNB_NA, false});
 }
 
 TEST_F(MatchSelectPatternTest, FMinMismatchConstantZeroVecUndef) {
   parseAssembly(
       "define <2 x float> @test(<2 x float> %a) {\n"
       "  %1 = fcmp ogt <2 x float> %a, <float -0.0, float -0.0>\n"
       "  %A = select <2 x i1> %1, <2 x float> <float undef, float 0.0>, <2 x float> %a\n"
       "  ret <2 x float> %A\n"