* [PATCH] range-op: Implement floating point multiplication fold_range [PR107569] @ 2022-11-10 13:44 Jakub Jelinek 2022-11-10 14:50 ` Aldy Hernandez 0 siblings, 1 reply; 12+ messages in thread From: Jakub Jelinek @ 2022-11-10 13:44 UTC (permalink / raw) To: Aldy Hernandez; +Cc: gcc-patches Hi! The following patch implements frange multiplication, including the special case of x * x. The callers don't tell us that it is x * x, just that it is either z = x * x or if (x == y) z = x * y; For irange that makes no difference, but for frange it can mean x is -0.0 and y is 0.0 if they have the same range that includes both signed and unsigned zeros, so we need to assume result could be -0.0. The patch causes one regression: +FAIL: gcc.dg/fold-overflow-1.c scan-assembler-times 2139095040 2 but that is already tracked in PR107608 and affects not just the newly added multiplication, but addition and other floating point operations (and doesn't seem like a ranger bug but dce or whatever else). Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? Once we have division and the reverse ops for all of these, perhaps we can do some cleanups to share common code, but the way I have division now partly written doesn't show up many commonalities. Multiplication is simple, division is a nightmare. 2022-11-10 Jakub Jelinek <jakub@redhat.com> PR tree-optimization/107569 PR tree-optimization/107591 * range-op.h (range_operator_float::rv_fold): Add relation_kind argument. * range-op-float.cc (range_operator_float::fold_range): Name last argument trio and pass trio.op1_op2 () as last argument to rv_fold. (range_operator_float::rv_fold): Add relation_kind argument. (foperator_plus::rv_fold, foperator_minus::rv_fold): Likewise. (frange_mult): New function. (foperator_mult): New class. (floating_op_table::floating_op_table): Use foperator_mult for MULT_EXPR. --- gcc/range-op.h.jj 2022-11-10 00:55:09.430219763 +0100 +++ gcc/range-op.h 2022-11-10 11:30:33.594114939 +0100 @@ -123,7 +123,8 @@ public: const REAL_VALUE_TYPE &lh_lb, const REAL_VALUE_TYPE &lh_ub, const REAL_VALUE_TYPE &rh_lb, - const REAL_VALUE_TYPE &rh_ub) const; + const REAL_VALUE_TYPE &rh_ub, + relation_kind) const; // Unary operations have the range of the LHS as op2. virtual bool fold_range (irange &r, tree type, const frange &lh, --- gcc/range-op-float.cc.jj 2022-11-10 00:55:09.318221259 +0100 +++ gcc/range-op-float.cc 2022-11-10 11:31:29.040359082 +0100 @@ -51,7 +51,7 @@ along with GCC; see the file COPYING3. bool range_operator_float::fold_range (frange &r, tree type, const frange &op1, const frange &op2, - relation_trio) const + relation_trio trio) const { if (empty_range_varying (r, type, op1, op2)) return true; @@ -65,7 +65,7 @@ range_operator_float::fold_range (frange bool maybe_nan; rv_fold (lb, ub, maybe_nan, type, op1.lower_bound (), op1.upper_bound (), - op2.lower_bound (), op2.upper_bound ()); + op2.lower_bound (), op2.upper_bound (), trio.op1_op2 ()); // Handle possible NANs by saturating to the appropriate INF if only // one end is a NAN. If both ends are a NAN, just return a NAN. @@ -103,8 +103,8 @@ range_operator_float::rv_fold (REAL_VALU const REAL_VALUE_TYPE &lh_lb ATTRIBUTE_UNUSED, const REAL_VALUE_TYPE &lh_ub ATTRIBUTE_UNUSED, const REAL_VALUE_TYPE &rh_lb ATTRIBUTE_UNUSED, - const REAL_VALUE_TYPE &rh_ub ATTRIBUTE_UNUSED) - const + const REAL_VALUE_TYPE &rh_ub ATTRIBUTE_UNUSED, + relation_kind) const { lb = dconstninf; ub = dconstinf; @@ -1868,7 +1868,8 @@ class foperator_plus : public range_oper const REAL_VALUE_TYPE &lh_lb, const REAL_VALUE_TYPE &lh_ub, const REAL_VALUE_TYPE &rh_lb, - const REAL_VALUE_TYPE &rh_ub) const final override + const REAL_VALUE_TYPE &rh_ub, + relation_kind) const final override { frange_arithmetic (PLUS_EXPR, type, lb, lh_lb, rh_lb, dconstninf); frange_arithmetic (PLUS_EXPR, type, ub, lh_ub, rh_ub, dconstinf); @@ -1892,7 +1893,8 @@ class foperator_minus : public range_ope const REAL_VALUE_TYPE &lh_lb, const REAL_VALUE_TYPE &lh_ub, const REAL_VALUE_TYPE &rh_lb, - const REAL_VALUE_TYPE &rh_ub) const final override + const REAL_VALUE_TYPE &rh_ub, + relation_kind) const final override { frange_arithmetic (MINUS_EXPR, type, lb, lh_lb, rh_ub, dconstninf); frange_arithmetic (MINUS_EXPR, type, ub, lh_ub, rh_lb, dconstinf); @@ -1908,6 +1910,123 @@ class foperator_minus : public range_ope } } fop_minus; +/* Wrapper around frange_arithmetics, that computes the result + if inexact rounded to both directions. Also, if one of the + operands is +-0.0 and another +-INF, return +-0.0 rather than + NAN. */ + +static void +frange_mult (tree type, REAL_VALUE_TYPE &result_lb, REAL_VALUE_TYPE &result_ub, + const REAL_VALUE_TYPE &op1, const REAL_VALUE_TYPE &op2) +{ + if (real_iszero (&op1) && real_isinf (&op2)) + { + result_lb = op1; + if (real_isneg (&op2)) + result_lb = real_value_negate (&result_lb); + result_ub = result_lb; + } + else if (real_isinf (&op1) && real_iszero (&op2)) + { + result_lb = op2; + if (real_isneg (&op1)) + result_lb = real_value_negate (&result_lb); + result_ub = result_lb; + } + else + { + frange_arithmetic (MULT_EXPR, type, result_lb, op1, op2, dconstninf); + frange_arithmetic (MULT_EXPR, type, result_ub, op1, op2, dconstinf); + } +} + +class foperator_mult : public range_operator_float +{ + void rv_fold (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, bool &maybe_nan, + tree type, + const REAL_VALUE_TYPE &lh_lb, + const REAL_VALUE_TYPE &lh_ub, + const REAL_VALUE_TYPE &rh_lb, + const REAL_VALUE_TYPE &rh_ub, + relation_kind kind) const final override + { + REAL_VALUE_TYPE cp[8]; + bool is_square + = (kind == VREL_EQ + && real_equal (&lh_lb, &rh_lb) + && real_equal (&lh_ub, &rh_ub) + && real_isneg (&lh_lb) == real_isneg (&rh_lb) + && real_isneg (&lh_ub) == real_isneg (&rh_ub)); + // Do a cross-product. + frange_mult (type, cp[0], cp[4], lh_lb, rh_lb); + if (is_square) + { + // For x * x we can just do max (lh_lb * lh_lb, lh_ub * lh_ub) + // as maximum and -0.0 as minimum if 0.0 is in the range, + // otherwise min (lh_lb * lh_lb, lh_ub * lh_ub). + // -0.0 rather than 0.0 because VREL_EQ doesn't prove that + // x and y are bitwise equal, just that they compare equal. + if (real_compare (LE_EXPR, &lh_lb, &dconst0) + && real_compare (GE_EXPR, &lh_ub, &dconst0)) + cp[1] = real_value_negate (&dconst0); + else + cp[1] = cp[0]; + cp[2] = cp[0]; + cp[5] = cp[4]; + cp[6] = cp[4]; + } + else + { + frange_mult (type, cp[1], cp[5], lh_lb, rh_ub); + frange_mult (type, cp[2], cp[6], lh_ub, rh_lb); + } + frange_mult (type, cp[3], cp[7], lh_ub, rh_ub); + for (int i = 1; i < 4; ++i) + { + if (real_less (&cp[i], &cp[0]) + || (real_iszero (&cp[0]) && real_isnegzero (&cp[i]))) + std::swap (cp[i], cp[0]); + if (real_less (&cp[4], &cp[i + 4]) + || (real_isnegzero (&cp[4]) && real_iszero (&cp[i + 4]))) + std::swap (cp[i + 4], cp[4]); + } + lb = cp[0]; + ub = cp[4]; + + // If both operands are the same, then we know it can be +-0.0, or +-INF, + // but not both at the same time, so it will never be invalid unless + // operand was already NAN. + if (is_square) + maybe_nan = false; + // [+-0, +-0] * [+INF,+INF] (or [-INF,-INF] or swapped is a known NAN. + else if ((real_iszero (&lh_lb) + && real_iszero (&lh_ub) + && real_isinf (&rh_lb) + && real_isinf (&rh_ub, real_isneg (&rh_lb))) + || (real_iszero (&rh_lb) + && real_iszero (&rh_ub) + && real_isinf (&lh_lb) + && real_isinf (&lh_ub, real_isneg (&lh_lb)))) + { + real_nan (&lb, "", 0, TYPE_MODE (type)); + ub = lb; + maybe_nan = true; + } + // Otherwise, if one range includes zero and the other ends with +-INF, + // it is a maybe NAN. + else if (real_compare (LE_EXPR, &lh_lb, &dconst0) + && real_compare (GE_EXPR, &lh_ub, &dconst0) + && (real_isinf (&rh_lb) || real_isinf (&rh_ub))) + maybe_nan = true; + else if (real_compare (LE_EXPR, &rh_lb, &dconst0) + && real_compare (GE_EXPR, &rh_ub, &dconst0) + && (real_isinf (&lh_lb) || real_isinf (&lh_ub))) + maybe_nan = true; + else + maybe_nan = false; + } +} fop_mult; + // Instantiate a range_op_table for floating point operations. static floating_op_table global_floating_table; @@ -1942,6 +2061,7 @@ floating_op_table::floating_op_table () set (NEGATE_EXPR, fop_negate); set (PLUS_EXPR, fop_plus); set (MINUS_EXPR, fop_minus); + set (MULT_EXPR, fop_mult); } // Return a pointer to the range_operator_float instance, if there is Jakub ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH] range-op: Implement floating point multiplication fold_range [PR107569] 2022-11-10 13:44 [PATCH] range-op: Implement floating point multiplication fold_range [PR107569] Jakub Jelinek @ 2022-11-10 14:50 ` Aldy Hernandez 2022-11-10 19:20 ` Jakub Jelinek 0 siblings, 1 reply; 12+ messages in thread From: Aldy Hernandez @ 2022-11-10 14:50 UTC (permalink / raw) To: Jakub Jelinek; +Cc: gcc-patches On 11/10/22 14:44, Jakub Jelinek wrote: > Hi! > > The following patch implements frange multiplication, including the > special case of x * x. The callers don't tell us that it is x * x, > just that it is either z = x * x or if (x == y) z = x * y; > For irange that makes no difference, but for frange it can mean > x is -0.0 and y is 0.0 if they have the same range that includes both > signed and unsigned zeros, so we need to assume result could be -0.0. > > The patch causes one regression: > +FAIL: gcc.dg/fold-overflow-1.c scan-assembler-times 2139095040 2 > but that is already tracked in PR107608 and affects not just the newly > added multiplication, but addition and other floating point operations > (and doesn't seem like a ranger bug but dce or whatever else). > > Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? > > Once we have division and the reverse ops for all of these, perhaps > we can do some cleanups to share common code, but the way I have division > now partly written doesn't show up many commonalities. Multiplication > is simple, division is a nightmare. Thanks for tackling this. I'm happy you think multiplication is simple, cause all the cross product operators make my head spin. > > 2022-11-10 Jakub Jelinek <jakub@redhat.com> > > PR tree-optimization/107569 > PR tree-optimization/107591 > * range-op.h (range_operator_float::rv_fold): Add relation_kind > argument. > * range-op-float.cc (range_operator_float::fold_range): Name > last argument trio and pass trio.op1_op2 () as last argument to > rv_fold. > (range_operator_float::rv_fold): Add relation_kind argument. > (foperator_plus::rv_fold, foperator_minus::rv_fold): Likewise. > (frange_mult): New function. > (foperator_mult): New class. > (floating_op_table::floating_op_table): Use foperator_mult for > MULT_EXPR. > > --- gcc/range-op.h.jj 2022-11-10 00:55:09.430219763 +0100 > +++ gcc/range-op.h 2022-11-10 11:30:33.594114939 +0100 > @@ -123,7 +123,8 @@ public: > const REAL_VALUE_TYPE &lh_lb, > const REAL_VALUE_TYPE &lh_ub, > const REAL_VALUE_TYPE &rh_lb, > - const REAL_VALUE_TYPE &rh_ub) const; > + const REAL_VALUE_TYPE &rh_ub, > + relation_kind) const; > // Unary operations have the range of the LHS as op2. > virtual bool fold_range (irange &r, tree type, > const frange &lh, > --- gcc/range-op-float.cc.jj 2022-11-10 00:55:09.318221259 +0100 > +++ gcc/range-op-float.cc 2022-11-10 11:31:29.040359082 +0100 > @@ -51,7 +51,7 @@ along with GCC; see the file COPYING3. > bool > range_operator_float::fold_range (frange &r, tree type, > const frange &op1, const frange &op2, > - relation_trio) const > + relation_trio trio) const > { > if (empty_range_varying (r, type, op1, op2)) > return true; > @@ -65,7 +65,7 @@ range_operator_float::fold_range (frange > bool maybe_nan; > rv_fold (lb, ub, maybe_nan, type, > op1.lower_bound (), op1.upper_bound (), > - op2.lower_bound (), op2.upper_bound ()); > + op2.lower_bound (), op2.upper_bound (), trio.op1_op2 ()); > > // Handle possible NANs by saturating to the appropriate INF if only > // one end is a NAN. If both ends are a NAN, just return a NAN. > @@ -103,8 +103,8 @@ range_operator_float::rv_fold (REAL_VALU > const REAL_VALUE_TYPE &lh_lb ATTRIBUTE_UNUSED, > const REAL_VALUE_TYPE &lh_ub ATTRIBUTE_UNUSED, > const REAL_VALUE_TYPE &rh_lb ATTRIBUTE_UNUSED, > - const REAL_VALUE_TYPE &rh_ub ATTRIBUTE_UNUSED) > - const > + const REAL_VALUE_TYPE &rh_ub ATTRIBUTE_UNUSED, > + relation_kind) const > { > lb = dconstninf; > ub = dconstinf; > @@ -1868,7 +1868,8 @@ class foperator_plus : public range_oper > const REAL_VALUE_TYPE &lh_lb, > const REAL_VALUE_TYPE &lh_ub, > const REAL_VALUE_TYPE &rh_lb, > - const REAL_VALUE_TYPE &rh_ub) const final override > + const REAL_VALUE_TYPE &rh_ub, > + relation_kind) const final override > { > frange_arithmetic (PLUS_EXPR, type, lb, lh_lb, rh_lb, dconstninf); > frange_arithmetic (PLUS_EXPR, type, ub, lh_ub, rh_ub, dconstinf); > @@ -1892,7 +1893,8 @@ class foperator_minus : public range_ope > const REAL_VALUE_TYPE &lh_lb, > const REAL_VALUE_TYPE &lh_ub, > const REAL_VALUE_TYPE &rh_lb, > - const REAL_VALUE_TYPE &rh_ub) const final override > + const REAL_VALUE_TYPE &rh_ub, > + relation_kind) const final override > { > frange_arithmetic (MINUS_EXPR, type, lb, lh_lb, rh_ub, dconstninf); > frange_arithmetic (MINUS_EXPR, type, ub, lh_ub, rh_lb, dconstinf); > @@ -1908,6 +1910,123 @@ class foperator_minus : public range_ope > } > } fop_minus; > > +/* Wrapper around frange_arithmetics, that computes the result > + if inexact rounded to both directions. Also, if one of the > + operands is +-0.0 and another +-INF, return +-0.0 rather than > + NAN. */ s/frange_arithmetics/frange_arithmetic/ Also, would you mind written a little blurb about why it's necessary not to compute INF*0.0 as NAN. I assume it's because you're using it for the cross product and you'll set maybe_nan separately, but it's nice to spell it out. > + > +static void > +frange_mult (tree type, REAL_VALUE_TYPE &result_lb, REAL_VALUE_TYPE &result_ub, > + const REAL_VALUE_TYPE &op1, const REAL_VALUE_TYPE &op2) > +{ > + if (real_iszero (&op1) && real_isinf (&op2)) > + { > + result_lb = op1; > + if (real_isneg (&op2)) > + result_lb = real_value_negate (&result_lb); > + result_ub = result_lb; > + } > + else if (real_isinf (&op1) && real_iszero (&op2)) > + { > + result_lb = op2; > + if (real_isneg (&op1)) > + result_lb = real_value_negate (&result_lb); > + result_ub = result_lb; > + } > + else > + { > + frange_arithmetic (MULT_EXPR, type, result_lb, op1, op2, dconstninf); > + frange_arithmetic (MULT_EXPR, type, result_ub, op1, op2, dconstinf); > + } > +} > + > +class foperator_mult : public range_operator_float > +{ > + void rv_fold (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, bool &maybe_nan, > + tree type, > + const REAL_VALUE_TYPE &lh_lb, > + const REAL_VALUE_TYPE &lh_ub, > + const REAL_VALUE_TYPE &rh_lb, > + const REAL_VALUE_TYPE &rh_ub, > + relation_kind kind) const final override > + { > + REAL_VALUE_TYPE cp[8]; > + bool is_square > + = (kind == VREL_EQ > + && real_equal (&lh_lb, &rh_lb) > + && real_equal (&lh_ub, &rh_ub) > + && real_isneg (&lh_lb) == real_isneg (&rh_lb) > + && real_isneg (&lh_ub) == real_isneg (&rh_ub)); > + // Do a cross-product. > + frange_mult (type, cp[0], cp[4], lh_lb, rh_lb); > + if (is_square) > + { > + // For x * x we can just do max (lh_lb * lh_lb, lh_ub * lh_ub) > + // as maximum and -0.0 as minimum if 0.0 is in the range, > + // otherwise min (lh_lb * lh_lb, lh_ub * lh_ub). > + // -0.0 rather than 0.0 because VREL_EQ doesn't prove that > + // x and y are bitwise equal, just that they compare equal. > + if (real_compare (LE_EXPR, &lh_lb, &dconst0) > + && real_compare (GE_EXPR, &lh_ub, &dconst0)) > + cp[1] = real_value_negate (&dconst0); > + else > + cp[1] = cp[0]; > + cp[2] = cp[0]; > + cp[5] = cp[4]; > + cp[6] = cp[4]; > + } > + else > + { > + frange_mult (type, cp[1], cp[5], lh_lb, rh_ub); > + frange_mult (type, cp[2], cp[6], lh_ub, rh_lb); > + } > + frange_mult (type, cp[3], cp[7], lh_ub, rh_ub); > + for (int i = 1; i < 4; ++i) > + { > + if (real_less (&cp[i], &cp[0]) > + || (real_iszero (&cp[0]) && real_isnegzero (&cp[i]))) > + std::swap (cp[i], cp[0]); > + if (real_less (&cp[4], &cp[i + 4]) > + || (real_isnegzero (&cp[4]) && real_iszero (&cp[i + 4]))) > + std::swap (cp[i + 4], cp[4]); > + } > + lb = cp[0]; > + ub = cp[4]; > + > + // If both operands are the same, then we know it can be +-0.0, or +-INF, > + // but not both at the same time, so it will never be invalid unless > + // operand was already NAN. > + if (is_square) > + maybe_nan = false; > + // [+-0, +-0] * [+INF,+INF] (or [-INF,-INF] or swapped is a known NAN. > + else if ((real_iszero (&lh_lb) > + && real_iszero (&lh_ub) > + && real_isinf (&rh_lb) > + && real_isinf (&rh_ub, real_isneg (&rh_lb))) > + || (real_iszero (&rh_lb) > + && real_iszero (&rh_ub) > + && real_isinf (&lh_lb) > + && real_isinf (&lh_ub, real_isneg (&lh_lb)))) > + { > + real_nan (&lb, "", 0, TYPE_MODE (type)); > + ub = lb; > + maybe_nan = true; > + } > + // Otherwise, if one range includes zero and the other ends with +-INF, > + // it is a maybe NAN. > + else if (real_compare (LE_EXPR, &lh_lb, &dconst0) > + && real_compare (GE_EXPR, &lh_ub, &dconst0) > + && (real_isinf (&rh_lb) || real_isinf (&rh_ub))) > + maybe_nan = true; > + else if (real_compare (LE_EXPR, &rh_lb, &dconst0) > + && real_compare (GE_EXPR, &rh_ub, &dconst0) > + && (real_isinf (&lh_lb) || real_isinf (&lh_ub))) > + maybe_nan = true; > + else > + maybe_nan = false; > + } > +} fop_mult; > + > // Instantiate a range_op_table for floating point operations. > static floating_op_table global_floating_table; > > @@ -1942,6 +2061,7 @@ floating_op_table::floating_op_table () > set (NEGATE_EXPR, fop_negate); > set (PLUS_EXPR, fop_plus); > set (MINUS_EXPR, fop_minus); > + set (MULT_EXPR, fop_mult); > } > > // Return a pointer to the range_operator_float instance, if there is It'd be nice to have some testcases. For example, from what I can see, the original integer multiplication code came with some tests in gcc.dg/tree-ssa/vrp13.c (commit 9983270bec0a18). It'd be nice to have some sanity checks, especially because so many things can go wrong with floats. I'll leave it to you to decide what tests to include. Otherwise, LGTM. Thanks. Aldy ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH] range-op: Implement floating point multiplication fold_range [PR107569] 2022-11-10 14:50 ` Aldy Hernandez @ 2022-11-10 19:20 ` Jakub Jelinek 2022-11-11 2:06 ` Jakub Jelinek ` (2 more replies) 0 siblings, 3 replies; 12+ messages in thread From: Jakub Jelinek @ 2022-11-10 19:20 UTC (permalink / raw) To: Aldy Hernandez; +Cc: gcc-patches On Thu, Nov 10, 2022 at 03:50:47PM +0100, Aldy Hernandez wrote: > > @@ -1908,6 +1910,123 @@ class foperator_minus : public range_ope > > } > > } fop_minus; > > +/* Wrapper around frange_arithmetics, that computes the result > > + if inexact rounded to both directions. Also, if one of the > > + operands is +-0.0 and another +-INF, return +-0.0 rather than > > + NAN. */ > > s/frange_arithmetics/frange_arithmetic/ > > Also, would you mind written a little blurb about why it's necessary not to > compute INF*0.0 as NAN. I assume it's because you're using it for the cross > product and you'll set maybe_nan separately, but it's nice to spell it out. This made me think about it some more and I'll need to play around with it some more, perhaps the right thing is similarly to what I've attached for division to handle special cases upfront and call frange_arithmetic only for the safe cases. E.g. one case which the posted foperator_mult handles pessimistically is [0.0, 10.0] * [INF, INF]. This should be just [INF, INF] +-NAN IMHO, because the 0.0 * INF case will result in NAN, while nextafter (0.0, 1.0) * INF will be already INF and everything larger as well. I could in frange_mult be very conservative and for the 0 * INF cases set result_lb and result_ub to [0.0, INF] range (corresponding signs depending on the xor of sign of ops), but that would be quite pessimistic as well. If one has: [0.0, 0.0] * [10.0, INF], the result should be just [0.0, 0.0] +-NAN, because again 0.0 * INF is NAN, but 0.0 * nextafter (INF, 0.0) is already 0.0. Note, the is_square case doesn't suffer from all of this mess, the result is never NAN (unless operand is NAN). > It'd be nice to have some testcases. For example, from what I can see, the > original integer multiplication code came with some tests in > gcc.dg/tree-ssa/vrp13.c (commit 9983270bec0a18). It'd be nice to have some > sanity checks, especially because so many things can go wrong with floats. > > I'll leave it to you to decide what tests to include. I've tried following, but it suffers from various issues: 1) we don't handle __builtin_signbit (whatever) == 0 (or != 0) as guarantee that in the guarded code whatever has signbit 0 or 1 2) __builtin_isinf (x) > 0 is lowered to x > DBL_MAX, but unfortunately we don't infer from that [INF,INF] range, but [DBL_MAX, INF] range 3) what I wrote above, I think we don't handle [0, 2] * [INF, INF] right but due to 2) we can't see it So, maybe for now a selftest will be better than a testcase, or alternatively a plugin test which acts like a selftest. /* { dg-do compile { target { ! { vax-*-* powerpc-*-*spe pdp11-*-* } } } } */ /* { dg-options "-O2 -fno-trapping-math -fno-signaling-nans -fsigned-zeros -fno-tree-fre -fno-tree-dominator-opts -fno-thread-jumps -fdump-tree-optimized" } */ /* { dg-add-options ieee } */ void foo (double x, double y) { const double inf = __builtin_inf (); const double minf = -inf; if (__builtin_isnan (x) || __builtin_isnan (y)) return; #define TEST(n, xl, xu, yl, yu, rl, ru, nan) \ if ((__builtin_isinf (xl) > 0 \ ? x > 0.0 && __builtin_isinf (x) \ : __builtin_isinf (xu) < 0 \ ? x < 0.0 && __builtin_isinf (x) \ : x >= xl && x <= xu \ && (xl != 0.0 \ || __builtin_signbit (xl) \ || !__builtin_signbit (x)) \ && (xu != 0.0 \ || !__builtin_signbit (xu) \ || __builtin_signbit (x))) \ && (__builtin_isinf (yl) > 0 \ ? y > 0.0 && __builtin_isinf (y) \ : __builtin_isinf (yu) < 0 \ ? y < 0.0 && __builtin_isinf (y) \ : y >= yl && y <= yu \ && (yl != 0.0 \ || __builtin_signbit (yl) \ || !__builtin_signbit (y)) \ && (yu != 0.0 \ || !__builtin_signbit (yu) \ || __builtin_signbit (y)))) \ { \ double r##n = x * y; \ if (nan == 2) \ { \ if (!__builtin_isnan (r##n)) \ __builtin_abort (); \ } \ else if (nan == 1) \ { \ if (!__builtin_isnan (r##n)) \ { \ if (r##n < rl || r##n > ru) \ __builtin_abort (); \ } \ } \ else \ { \ if (__builtin_isnan (r##n)) \ __builtin_abort (); \ if (r##n < rl || r##n > ru) \ __builtin_abort (); \ } \ } #define TEST2(n, xl, xu, rl, ru) \ if (__builtin_isinf (xl) > 0 \ ? x > 0.0 && __builtin_isinf (x) \ : __builtin_isinf (xu) < 0 \ ? x < 0.0 && __builtin_isinf (x) \ : x >= xl && x <= xu \ && (xl != 0.0 \ || __builtin_signbit (xl) \ || !__builtin_signbit (x)) \ && (xu != 0.0 \ || !__builtin_signbit (xu) \ || __builtin_signbit (x))) \ { \ double s##n = x * x; \ if (__builtin_isnan (s##n)) \ __builtin_abort (); \ if (s##n < rl || s##n > ru) \ __builtin_abort (); \ } TEST (1, 2.0, 4.0, 6.0, 8.0, 12.0, 32.0, 0); TEST (2, -2.0, 3.0, -7.0, 4.0, -21.0, 14.0, 0); TEST (3, -9.0, 5.0, 8.0, 10.0, -90.0, 50.0, 0); TEST (4, -0.0, 0.0, 16.0, 32.0, -0.0, 0.0, 0); TEST (5, -0.0, 0.0, 16.0, 32.0, -0.0, 0.0, 0); TEST (6, 0.0, 0.0, 16.0, 32.0, 0.0, 0.0, 0); TEST (7, 0.0, 0.0, 16.0, 32.0, 0.0, 0.0, 0); TEST (8, -0.0, -0.0, 16.0, 32.0, -0.0, -0.0, 0); TEST (9, -0.0, -0.0, 16.0, 32.0, -0.0, -0.0, 0); TEST (10, minf, inf, minf, inf, minf, inf, 1); TEST (11, -0.0, 0.0, 128.0, inf, -0.0, 0.0, 1); TEST (12, -0.0, 0.0, inf, inf, 0.0, 0.0, 2); TEST (13, minf, minf, 0.0, 0.0, 0.0, 0.0, 2); TEST (14, 0.0, 2.0, inf, inf, inf, inf, 1); TEST (15, 0.0, 2.0, minf, minf, minf, minf, 1); TEST (16, inf, inf, -0.0, 2.0, minf, inf, 1); TEST (17, minf, minf, -0.0, 3.0, minf, inf, 1); TEST2 (1, 2.0, 4.0, 4.0, 16.0); TEST2 (2, -0.0, 0.0, -0.0, 0.0); TEST2 (3, 0.0, inf, 0.0, inf); TEST2 (4, inf, inf, inf, inf); } Jakub ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH] range-op: Implement floating point multiplication fold_range [PR107569] 2022-11-10 19:20 ` Jakub Jelinek @ 2022-11-11 2:06 ` Jakub Jelinek 2022-11-11 8:52 ` [PATCH] range-op, v2: " Jakub Jelinek 2022-11-11 10:01 ` [PATCH] range-op: Implement floating point multiplication " Aldy Hernandez 2 siblings, 0 replies; 12+ messages in thread From: Jakub Jelinek @ 2022-11-11 2:06 UTC (permalink / raw) To: Aldy Hernandez, gcc-patches On Thu, Nov 10, 2022 at 08:20:06PM +0100, Jakub Jelinek via Gcc-patches wrote: > So, maybe for now a selftest will be better than a testcase, or > alternatively a plugin test which acts like a selftest. For a testsuite/g*.dg/plugin/ range-op-plugin.c test, would be nice to write a short plugin that does: 1) register 2 new attributes, say gcc_range and gcc_expected_range, parse their arguments 2) registers some new pass (dunno where it would be best, say before evrp or so), which would: - for function parameters with gcc_range attributes set global? range on default def of that parameter - if function itself has a gcc_expected_range attribute, propagate ranges from arguments to the function result and compare against gcc_expected_range - if function itself has gcc_range attribute and one of the arguments gcc_expected_range itself, try to propagate range backwards from result to the argument Then we could say write tests like: __attribute__((gcc_expected_range (12.0, 32.0, 0))) double foo (double x __attribute__((gcc_range (2.0, 4.0, 0))), double y __attribute__((gcc_range (6.0, 8.0, 0)))) { return x * y; } with for floating point types (parameter type or function result type) the arguments of the attribute being (constant folded) low bound, high bound, integer about NAN (say 0 meaning clear_nan, bit 0 meaning +NAN, bit 1 -NAN, bit 2 meaning known NAN (then the 2 bounds would be ignored)). Eventually we could do something similar for integral types, pointer types etc. I think this would be far more useful compared to writing selftests for it, and compared to the testcase I've posted would be easier to request or check exact range rather than a rough range. And we could easily test not just very simple binary ops (in both directions), but builtin calls etc. Thoughts on this? I can try to write a plugin that registers the attributes, parses them and registers a pass, but would appreciate your or Andrew's help in filling the actual pass. Jakub ^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH] range-op, v2: Implement floating point multiplication fold_range [PR107569] 2022-11-10 19:20 ` Jakub Jelinek 2022-11-11 2:06 ` Jakub Jelinek @ 2022-11-11 8:52 ` Jakub Jelinek 2022-11-11 10:01 ` [PATCH] range-op: Cleanup floating point multiplication and division " Jakub Jelinek 2022-11-11 10:01 ` [PATCH] range-op: Implement floating point multiplication " Aldy Hernandez 2 siblings, 1 reply; 12+ messages in thread From: Jakub Jelinek @ 2022-11-11 8:52 UTC (permalink / raw) To: Aldy Hernandez; +Cc: gcc-patches On Thu, Nov 10, 2022 at 08:20:06PM +0100, Jakub Jelinek via Gcc-patches wrote: > This made me think about it some more and I'll need to play around with it > some more, perhaps the right thing is similarly to what I've attached for > division to handle special cases upfront and call frange_arithmetic only > for the safe cases. > E.g. one case which the posted foperator_mult handles pessimistically is > [0.0, 10.0] * [INF, INF]. This should be just [INF, INF] +-NAN IMHO, > because the 0.0 * INF case will result in NAN, while > nextafter (0.0, 1.0) * INF > will be already INF and everything larger as well. > I could in frange_mult be very conservative and for the 0 * INF cases > set result_lb and result_ub to [0.0, INF] range (corresponding signs > depending on the xor of sign of ops), but that would be quite pessimistic as > well. If one has: > [0.0, 0.0] * [10.0, INF], the result should be just [0.0, 0.0] +-NAN, > because again 0.0 * INF is NAN, but 0.0 * nextafter (INF, 0.0) is already 0.0. > > Note, the is_square case doesn't suffer from all of this mess, the result > is never NAN (unless operand is NAN). Ok, here is the patch rewritten in the foperator_div style, with special cases handled first and then the ordinary cases without problematic cases. I guess if/once we have a plugin testing infrastructure, we could compare the two versions of the patch, I think this one is more precise. And, admittedly there are many similar spots with the foperator_div case (but also with significant differences), so perhaps if foperator_{mult,div} inherit from some derived class from range_operator_float and that class would define various smaller helper static? methods, like this discussed in the PR - contains_zero_p, singleton_nan_p, zero_p, that + bool must_have_signbit_zero = false; + bool must_have_signbit_nonzero = false; + if (real_isneg (&lh_lb) == real_isneg (&lh_ub) + && real_isneg (&rh_lb) == real_isneg (&rh_ub)) + { + if (real_isneg (&lh_lb) == real_isneg (&rh_ub)) + must_have_signbit_zero = true; + else + must_have_signbit_nonzero = true; + } returned as -1/0/1 int, and those set result (based on the above value) to [+INF, +INF], [-INF, -INF] or [-INF, +INF] or [+0, +0], [-0, -0] or [-0, +0] or [+0, +INF], [-INF, -0] or [-INF, +INF] and the + for (int i = 1; i < 4; ++i) + { + if (real_less (&cp[i], &cp[0]) + || (real_iszero (&cp[0]) && real_isnegzero (&cp[i]))) + std::swap (cp[i], cp[0]); + if (real_less (&cp[4], &cp[i + 4]) + || (real_isnegzero (&cp[4]) && real_iszero (&cp[i + 4]))) + std::swap (cp[i + 4], cp[4]); + } block, it could be smaller and more readable. Thoughts? This has been just compile tested so far. 2022-11-11 Jakub Jelinek <jakub@redhat.com> PR tree-optimization/107569 PR tree-optimization/107591 * range-op.h (range_operator_float::rv_fold): Add relation_kind argument. * range-op-float.cc (range_operator_float::fold_range): Name last argument trio and pass trio.op1_op2 () as last argument to rv_fold. (range_operator_float::rv_fold): Add relation_kind argument. (foperator_plus::rv_fold, foperator_minus::rv_fold): Likewise. (foperator_mult): New class. (floating_op_table::floating_op_table): Use foperator_mult for MULT_EXPR. --- gcc/range-op.h.jj 2022-11-11 08:15:20.952520590 +0100 +++ gcc/range-op.h 2022-11-11 08:48:27.649349048 +0100 @@ -123,7 +123,8 @@ public: const REAL_VALUE_TYPE &lh_lb, const REAL_VALUE_TYPE &lh_ub, const REAL_VALUE_TYPE &rh_lb, - const REAL_VALUE_TYPE &rh_ub) const; + const REAL_VALUE_TYPE &rh_ub, + relation_kind) const; // Unary operations have the range of the LHS as op2. virtual bool fold_range (irange &r, tree type, const frange &lh, --- gcc/range-op-float.cc.jj 2022-11-11 08:15:20.933520849 +0100 +++ gcc/range-op-float.cc 2022-11-11 09:39:14.950523368 +0100 @@ -51,7 +51,7 @@ along with GCC; see the file COPYING3. bool range_operator_float::fold_range (frange &r, tree type, const frange &op1, const frange &op2, - relation_trio) const + relation_trio trio) const { if (empty_range_varying (r, type, op1, op2)) return true; @@ -65,7 +65,7 @@ range_operator_float::fold_range (frange bool maybe_nan; rv_fold (lb, ub, maybe_nan, type, op1.lower_bound (), op1.upper_bound (), - op2.lower_bound (), op2.upper_bound ()); + op2.lower_bound (), op2.upper_bound (), trio.op1_op2 ()); // Handle possible NANs by saturating to the appropriate INF if only // one end is a NAN. If both ends are a NAN, just return a NAN. @@ -103,8 +103,8 @@ range_operator_float::rv_fold (REAL_VALU const REAL_VALUE_TYPE &lh_lb ATTRIBUTE_UNUSED, const REAL_VALUE_TYPE &lh_ub ATTRIBUTE_UNUSED, const REAL_VALUE_TYPE &rh_lb ATTRIBUTE_UNUSED, - const REAL_VALUE_TYPE &rh_ub ATTRIBUTE_UNUSED) - const + const REAL_VALUE_TYPE &rh_ub ATTRIBUTE_UNUSED, + relation_kind) const { lb = dconstninf; ub = dconstinf; @@ -1868,7 +1868,8 @@ class foperator_plus : public range_oper const REAL_VALUE_TYPE &lh_lb, const REAL_VALUE_TYPE &lh_ub, const REAL_VALUE_TYPE &rh_lb, - const REAL_VALUE_TYPE &rh_ub) const final override + const REAL_VALUE_TYPE &rh_ub, + relation_kind) const final override { frange_arithmetic (PLUS_EXPR, type, lb, lh_lb, rh_lb, dconstninf); frange_arithmetic (PLUS_EXPR, type, ub, lh_ub, rh_ub, dconstinf); @@ -1892,7 +1893,8 @@ class foperator_minus : public range_ope const REAL_VALUE_TYPE &lh_lb, const REAL_VALUE_TYPE &lh_ub, const REAL_VALUE_TYPE &rh_lb, - const REAL_VALUE_TYPE &rh_ub) const final override + const REAL_VALUE_TYPE &rh_ub, + relation_kind) const final override { frange_arithmetic (MINUS_EXPR, type, lb, lh_lb, rh_ub, dconstninf); frange_arithmetic (MINUS_EXPR, type, ub, lh_ub, rh_lb, dconstinf); @@ -1908,6 +1910,182 @@ class foperator_minus : public range_ope } } fop_minus; + +class foperator_mult : public range_operator_float +{ + void rv_fold (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, bool &maybe_nan, + tree type, + const REAL_VALUE_TYPE &lh_lb, + const REAL_VALUE_TYPE &lh_ub, + const REAL_VALUE_TYPE &rh_lb, + const REAL_VALUE_TYPE &rh_ub, + relation_kind kind) const final override + { + bool is_square + = (kind == VREL_EQ + && real_equal (&lh_lb, &rh_lb) + && real_equal (&lh_ub, &rh_ub) + && real_isneg (&lh_lb) == real_isneg (&rh_lb) + && real_isneg (&lh_ub) == real_isneg (&rh_ub)); + + maybe_nan = false; + // x * x never produces a new NAN and we only multiply the same + // values, so the 0 * INF problematic cases never appear there. + if (!is_square) + { + // [+-0, +-0] * [+INF,+INF] (or [-INF,-INF] or swapped is a known NAN. + if ((real_iszero (&lh_lb) + && real_iszero (&lh_ub) + && real_isinf (&rh_lb) + && real_isinf (&rh_ub, real_isneg (&rh_lb))) + || (real_iszero (&rh_lb) + && real_iszero (&rh_ub) + && real_isinf (&lh_lb) + && real_isinf (&lh_ub, real_isneg (&lh_lb)))) + { + real_nan (&lb, "", 0, TYPE_MODE (type)); + ub = lb; + maybe_nan = true; + return; + } + + // Otherwise, if one range includes zero and the other ends with +-INF, + // it is a maybe NAN. + if ((real_compare (LE_EXPR, &lh_lb, &dconst0) + && real_compare (GE_EXPR, &lh_ub, &dconst0) + && (real_isinf (&rh_lb) || real_isinf (&rh_ub))) + || (real_compare (LE_EXPR, &rh_lb, &dconst0) + && real_compare (GE_EXPR, &rh_ub, &dconst0) + && (real_isinf (&lh_lb) || real_isinf (&lh_ub)))) + { + maybe_nan = true; + + bool must_have_signbit_zero = false; + bool must_have_signbit_nonzero = false; + if (real_isneg (&lh_lb) == real_isneg (&lh_ub) + && real_isneg (&rh_lb) == real_isneg (&rh_ub)) + { + if (real_isneg (&lh_lb) == real_isneg (&rh_ub)) + must_have_signbit_zero = true; + else + must_have_signbit_nonzero = true; + } + + // If one of the ranges that includes INF is singleton + // and the other range includes zero, the resulting + // range is INF and NAN, because the 0 * INF boundary + // case will be NAN, but already nextafter (0, 1) * INF + // is INF. + if ((real_isinf (&lh_lb) + && real_isinf (&lh_ub, real_isneg (&lh_lb))) + || (real_isinf (&rh_lb) + && real_isinf (&rh_ub, real_isneg (&rh_lb)))) + { + // If all the boundary signs are the same, [+INF, +INF]. + if (must_have_signbit_zero) + ub = lb = dconstinf; + // If the two multiplicands have always different sign, + // [-INF, -INF]. + else if (must_have_signbit_nonzero) + ub = lb = dconstninf; + // Otherwise -> [-INF, +INF] (-INF or +INF). + else + { + lb = dconstninf; + ub = dconstinf; + } + return; + } + + // If one of the multiplicands must be zero, the resulting + // range is +-0 and NAN. + if ((real_iszero (&lh_lb) && real_iszero (&lh_ub)) + || (real_iszero (&rh_lb) && real_iszero (&rh_ub))) + { + ub = lb = dconst0; + // If all the boundary signs are the same, [+0.0, +0.0]. + if (must_have_signbit_zero) + ; + // If divisor and dividend must have different signs, + // [-0.0, -0.0]. + else if (must_have_signbit_nonzero) + ub = lb = real_value_negate (&dconst0); + // Otherwise -> [-0.0, +0.0]. + else + lb = real_value_negate (&dconst0); + return; + } + + // Otherwise one of the multiplicands could be + // [0.0, nextafter (0.0, 1.0)] and the [DBL_MAX, INF] + // or similarly with different signs. 0.0 * DBL_MAX + // is still 0.0, nextafter (0.0, 1.0) * INF is still INF, + // so if the signs are always the same or always different, + // result is [+0.0, +INF] or [-INF, -0.0], otherwise VARYING. + if (must_have_signbit_zero) + { + lb = dconst0; + ub = dconstinf; + } + else if (must_have_signbit_nonzero) + { + lb = dconstninf; + ub = real_value_negate (&dconst0); + } + else + { + lb = dconstninf; + ub = dconstinf; + } + return; + } + } + + REAL_VALUE_TYPE cp[8]; + // Do a cross-product. + frange_arithmetic (MULT_EXPR, type, cp[0], lh_lb, rh_lb, dconstninf); + frange_arithmetic (MULT_EXPR, type, cp[4], lh_lb, rh_lb, dconstinf); + if (is_square) + { + // For x * x we can just do max (lh_lb * lh_lb, lh_ub * lh_ub) + // as maximum and -0.0 as minimum if 0.0 is in the range, + // otherwise min (lh_lb * lh_lb, lh_ub * lh_ub). + // -0.0 rather than 0.0 because VREL_EQ doesn't prove that + // x and y are bitwise equal, just that they compare equal. + if (real_compare (LE_EXPR, &lh_lb, &dconst0) + && real_compare (GE_EXPR, &lh_ub, &dconst0)) + cp[1] = real_value_negate (&dconst0); + else + cp[1] = cp[0]; + cp[2] = cp[0]; + cp[5] = cp[4]; + cp[6] = cp[4]; + } + else + { + frange_arithmetic (MULT_EXPR, type, cp[1], lh_lb, rh_ub, dconstninf); + frange_arithmetic (MULT_EXPR, type, cp[5], lh_lb, rh_ub, dconstinf); + frange_arithmetic (MULT_EXPR, type, cp[2], lh_ub, rh_lb, dconstninf); + frange_arithmetic (MULT_EXPR, type, cp[6], lh_ub, rh_lb, dconstinf); + } + frange_arithmetic (MULT_EXPR, type, cp[3], lh_ub, rh_ub, dconstninf); + frange_arithmetic (MULT_EXPR, type, cp[7], lh_ub, rh_ub, dconstinf); + + for (int i = 1; i < 4; ++i) + { + if (real_less (&cp[i], &cp[0]) + || (real_iszero (&cp[0]) && real_isnegzero (&cp[i]))) + std::swap (cp[i], cp[0]); + if (real_less (&cp[4], &cp[i + 4]) + || (real_isnegzero (&cp[4]) && real_iszero (&cp[i + 4]))) + std::swap (cp[i + 4], cp[4]); + } + lb = cp[0]; + ub = cp[4]; + + } +} fop_mult; + // Instantiate a range_op_table for floating point operations. static floating_op_table global_floating_table; @@ -1942,6 +2120,7 @@ floating_op_table::floating_op_table () set (NEGATE_EXPR, fop_negate); set (PLUS_EXPR, fop_plus); set (MINUS_EXPR, fop_minus); + set (MULT_EXPR, fop_mult); } // Return a pointer to the range_operator_float instance, if there is Jakub ^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH] range-op: Cleanup floating point multiplication and division fold_range [PR107569] 2022-11-11 8:52 ` [PATCH] range-op, v2: " Jakub Jelinek @ 2022-11-11 10:01 ` Jakub Jelinek 2022-11-11 10:12 ` Aldy Hernandez 2022-11-11 14:27 ` Aldy Hernandez 0 siblings, 2 replies; 12+ messages in thread From: Jakub Jelinek @ 2022-11-11 10:01 UTC (permalink / raw) To: Aldy Hernandez; +Cc: gcc-patches On Fri, Nov 11, 2022 at 09:52:53AM +0100, Jakub Jelinek via Gcc-patches wrote: > Ok, here is the patch rewritten in the foperator_div style, with special > cases handled first and then the ordinary cases without problematic cases. > I guess if/once we have a plugin testing infrastructure, we could compare > the two versions of the patch, I think this one is more precise. > And, admittedly there are many similar spots with the foperator_div case > (but also with significant differences), so perhaps if foperator_{mult,div} > inherit from some derived class from range_operator_float and that class > would define various smaller helper static? methods, like this > discussed in the PR - contains_zero_p, singleton_nan_p, zero_p, > that > + bool must_have_signbit_zero = false; > + bool must_have_signbit_nonzero = false; > + if (real_isneg (&lh_lb) == real_isneg (&lh_ub) > + && real_isneg (&rh_lb) == real_isneg (&rh_ub)) > + { > + if (real_isneg (&lh_lb) == real_isneg (&rh_ub)) > + must_have_signbit_zero = true; > + else > + must_have_signbit_nonzero = true; > + } > returned as -1/0/1 int, and those set result (based on the above value) to > [+INF, +INF], [-INF, -INF] or [-INF, +INF] > or > [+0, +0], [-0, -0] or [-0, +0] > or > [+0, +INF], [-INF, -0] or [-INF, +INF] > and the > + for (int i = 1; i < 4; ++i) > + { > + if (real_less (&cp[i], &cp[0]) > + || (real_iszero (&cp[0]) && real_isnegzero (&cp[i]))) > + std::swap (cp[i], cp[0]); > + if (real_less (&cp[4], &cp[i + 4]) > + || (real_isnegzero (&cp[4]) && real_iszero (&cp[i + 4]))) > + std::swap (cp[i + 4], cp[4]); > + } > block, it could be smaller and more readable. Here is an incremental patch on top of this and division patch, which does that. 2022-11-11 Jakub Jelinek <jakub@redhat.com> PR tree-optimization/107569 * range-op-float.cc (foperator_mult_div_base): New class. (foperator_mult, foperator_div): Derive from that and use protected static methods from it to simplify the code. --- gcc/range-op-float.cc.jj 2022-11-11 10:13:30.879410560 +0100 +++ gcc/range-op-float.cc 2022-11-11 10:55:57.602617289 +0100 @@ -1911,7 +1911,125 @@ class foperator_minus : public range_ope } fop_minus; -class foperator_mult : public range_operator_float +class foperator_mult_div_base : public range_operator_float +{ +protected: + // True if [lb, ub] is [+-0, +-0]. + static bool zero_p (const REAL_VALUE_TYPE &lb, + const REAL_VALUE_TYPE &ub) + { + return real_iszero (&lb) && real_iszero (&ub); + } + + // True if +0 or -0 is in [lb, ub] range. + static bool contains_zero_p (const REAL_VALUE_TYPE &lb, + const REAL_VALUE_TYPE &ub) + { + return (real_compare (LE_EXPR, &lb, &dconst0) + && real_compare (GE_EXPR, &ub, &dconst0)); + } + + // True if [lb, ub] is [-INF, -INF] or [+INF, +INF]. + static bool singleton_inf_p (const REAL_VALUE_TYPE &lb, + const REAL_VALUE_TYPE &ub) + { + return real_isinf (&lb) && real_isinf (&ub, real_isneg (&lb)); + } + + // Return -1 if binary op result must have sign bit set, + // 1 if binary op result must have sign bit clear, + // 0 otherwise. + // Sign bit of binary op result is exclusive or of the + // operand's sign bits. + static int signbit_known_p (const REAL_VALUE_TYPE &lh_lb, + const REAL_VALUE_TYPE &lh_ub, + const REAL_VALUE_TYPE &rh_lb, + const REAL_VALUE_TYPE &rh_ub) + { + if (real_isneg (&lh_lb) == real_isneg (&lh_ub) + && real_isneg (&rh_lb) == real_isneg (&rh_ub)) + { + if (real_isneg (&lh_lb) == real_isneg (&rh_ub)) + return 1; + else + return -1; + } + return 0; + } + + // Set [lb, ub] to [-0, -0], [-0, +0] or [+0, +0] depending on + // signbit_known. + static void zero_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, + int signbit_known) + { + ub = lb = dconst0; + if (signbit_known <= 0) + lb = real_value_negate (&dconst0); + if (signbit_known < 0) + ub = lb; + } + + // Set [lb, ub] to [-INF, -INF], [-INF, +INF] or [+INF, +INF] depending on + // signbit_known. + static void inf_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, + int signbit_known) + { + if (signbit_known > 0) + ub = lb = dconstinf; + else if (signbit_known < 0) + ub = lb = dconstninf; + else + { + lb = dconstninf; + ub = dconstinf; + } + } + + // Set [lb, ub] to [-INF, -0], [-INF, +INF] or [+0, +INF] depending on + // signbit_known. + static void zero_to_inf_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, + int signbit_known) + { + if (signbit_known > 0) + { + lb = dconst0; + ub = dconstinf; + } + else if (signbit_known < 0) + { + lb = dconstninf; + ub = real_value_negate (&dconst0); + } + else + { + lb = dconstninf; + ub = dconstinf; + } + } + + // Given CP[0] to CP[3] floating point values rounded to -INF, + // set LB to the smallest of them (treating -0 as smaller to +0). + // Given CP[4] to CP[7] floating point values rounded to +INF, + // set UB to the largest of them (treating -0 as smaller to +0). + static void find_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, + const REAL_VALUE_TYPE (&cp)[8]) + { + lb = cp[0]; + ub = cp[4]; + for (int i = 1; i < 4; ++i) + { + if (real_less (&cp[i], &lb) + || (real_iszero (&lb) && real_isnegzero (&cp[i]))) + lb = cp[i]; + if (real_less (&ub, &cp[i + 4]) + || (real_isnegzero (&ub) && real_iszero (&cp[i + 4]))) + ub = cp[i + 4]; + } + } +}; + + +class foperator_mult : public foperator_mult_div_base { void rv_fold (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, bool &maybe_nan, tree type, @@ -1934,14 +2052,8 @@ class foperator_mult : public range_oper if (!is_square) { // [+-0, +-0] * [+INF,+INF] (or [-INF,-INF] or swapped is a known NAN. - if ((real_iszero (&lh_lb) - && real_iszero (&lh_ub) - && real_isinf (&rh_lb) - && real_isinf (&rh_ub, real_isneg (&rh_lb))) - || (real_iszero (&rh_lb) - && real_iszero (&rh_ub) - && real_isinf (&lh_lb) - && real_isinf (&lh_ub, real_isneg (&lh_lb)))) + if ((zero_p (lh_lb, lh_ub) && singleton_inf_p (rh_lb, rh_ub)) + || (zero_p (rh_lb, rh_ub) && singleton_inf_p (lh_lb, lh_ub))) { real_nan (&lb, "", 0, TYPE_MODE (type)); ub = lb; @@ -1951,70 +2063,28 @@ class foperator_mult : public range_oper // Otherwise, if one range includes zero and the other ends with +-INF, // it is a maybe NAN. - if ((real_compare (LE_EXPR, &lh_lb, &dconst0) - && real_compare (GE_EXPR, &lh_ub, &dconst0) + if ((contains_zero_p (lh_lb, lh_ub) && (real_isinf (&rh_lb) || real_isinf (&rh_ub))) - || (real_compare (LE_EXPR, &rh_lb, &dconst0) - && real_compare (GE_EXPR, &rh_ub, &dconst0) + || (contains_zero_p (rh_lb, rh_ub) && (real_isinf (&lh_lb) || real_isinf (&lh_ub)))) { maybe_nan = true; - bool must_have_signbit_zero = false; - bool must_have_signbit_nonzero = false; - if (real_isneg (&lh_lb) == real_isneg (&lh_ub) - && real_isneg (&rh_lb) == real_isneg (&rh_ub)) - { - if (real_isneg (&lh_lb) == real_isneg (&rh_ub)) - must_have_signbit_zero = true; - else - must_have_signbit_nonzero = true; - } + int signbit_known = signbit_known_p (lh_lb, lh_ub, rh_lb, rh_ub); // If one of the ranges that includes INF is singleton // and the other range includes zero, the resulting // range is INF and NAN, because the 0 * INF boundary // case will be NAN, but already nextafter (0, 1) * INF // is INF. - if ((real_isinf (&lh_lb) - && real_isinf (&lh_ub, real_isneg (&lh_lb))) - || (real_isinf (&rh_lb) - && real_isinf (&rh_ub, real_isneg (&rh_lb)))) - { - // If all the boundary signs are the same, [+INF, +INF]. - if (must_have_signbit_zero) - ub = lb = dconstinf; - // If the two multiplicands have always different sign, - // [-INF, -INF]. - else if (must_have_signbit_nonzero) - ub = lb = dconstninf; - // Otherwise -> [-INF, +INF] (-INF or +INF). - else - { - lb = dconstninf; - ub = dconstinf; - } - return; - } + if (singleton_inf_p (lh_lb, lh_ub) + || singleton_inf_p (rh_lb, rh_ub)) + return inf_range (lb, ub, signbit_known); // If one of the multiplicands must be zero, the resulting // range is +-0 and NAN. - if ((real_iszero (&lh_lb) && real_iszero (&lh_ub)) - || (real_iszero (&rh_lb) && real_iszero (&rh_ub))) - { - ub = lb = dconst0; - // If all the boundary signs are the same, [+0.0, +0.0]. - if (must_have_signbit_zero) - ; - // If divisor and dividend must have different signs, - // [-0.0, -0.0]. - else if (must_have_signbit_nonzero) - ub = lb = real_value_negate (&dconst0); - // Otherwise -> [-0.0, +0.0]. - else - lb = real_value_negate (&dconst0); - return; - } + if (zero_p (lh_lb, lh_ub) || zero_p (rh_lb, rh_ub)) + return zero_range (lb, ub, signbit_known); // Otherwise one of the multiplicands could be // [0.0, nextafter (0.0, 1.0)] and the [DBL_MAX, INF] @@ -2022,27 +2092,13 @@ class foperator_mult : public range_oper // is still 0.0, nextafter (0.0, 1.0) * INF is still INF, // so if the signs are always the same or always different, // result is [+0.0, +INF] or [-INF, -0.0], otherwise VARYING. - if (must_have_signbit_zero) - { - lb = dconst0; - ub = dconstinf; - } - else if (must_have_signbit_nonzero) - { - lb = dconstninf; - ub = real_value_negate (&dconst0); - } - else - { - lb = dconstninf; - ub = dconstinf; - } - return; + return zero_to_inf_range (lb, ub, signbit_known); } } REAL_VALUE_TYPE cp[8]; - // Do a cross-product. + // Do a cross-product. At this point none of the multiplications + // should produce a NAN. frange_arithmetic (MULT_EXPR, type, cp[0], lh_lb, rh_lb, dconstninf); frange_arithmetic (MULT_EXPR, type, cp[4], lh_lb, rh_lb, dconstinf); if (is_square) @@ -2052,9 +2108,13 @@ class foperator_mult : public range_oper // otherwise min (lh_lb * lh_lb, lh_ub * lh_ub). // -0.0 rather than 0.0 because VREL_EQ doesn't prove that // x and y are bitwise equal, just that they compare equal. - if (real_compare (LE_EXPR, &lh_lb, &dconst0) - && real_compare (GE_EXPR, &lh_ub, &dconst0)) - cp[1] = real_value_negate (&dconst0); + if (contains_zero_p (lh_lb, lh_ub)) + { + if (real_isneg (&lh_lb) == real_isneg (&lh_ub)) + cp[1] = dconst0; + else + cp[1] = real_value_negate (&dconst0); + } else cp[1] = cp[0]; cp[2] = cp[0]; @@ -2071,22 +2131,12 @@ class foperator_mult : public range_oper frange_arithmetic (MULT_EXPR, type, cp[3], lh_ub, rh_ub, dconstninf); frange_arithmetic (MULT_EXPR, type, cp[7], lh_ub, rh_ub, dconstinf); - for (int i = 1; i < 4; ++i) - { - if (real_less (&cp[i], &cp[0]) - || (real_iszero (&cp[0]) && real_isnegzero (&cp[i]))) - std::swap (cp[i], cp[0]); - if (real_less (&cp[4], &cp[i + 4]) - || (real_isnegzero (&cp[4]) && real_iszero (&cp[i + 4]))) - std::swap (cp[i + 4], cp[4]); - } - lb = cp[0]; - ub = cp[4]; - + find_range (lb, ub, cp); } } fop_mult; -class foperator_div : public range_operator_float + +class foperator_div : public foperator_mult_div_base { void rv_fold (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, bool &maybe_nan, tree type, @@ -2097,14 +2147,8 @@ class foperator_div : public range_opera relation_kind) const final override { // +-0.0 / +-0.0 or +-INF / +-INF is a known NAN. - if ((real_iszero (&lh_lb) - && real_iszero (&lh_ub) - && real_iszero (&rh_lb) - && real_iszero (&rh_ub)) - || (real_isinf (&lh_lb) - && real_isinf (&lh_ub, real_isneg (&lh_lb)) - && real_isinf (&rh_lb) - && real_isinf (&rh_ub, real_isneg (&rh_lb)))) + if ((zero_p (lh_lb, lh_ub) && zero_p (rh_lb, rh_ub)) + || (singleton_inf_p (lh_lb, lh_ub) || singleton_inf_p (rh_lb, rh_ub))) { real_nan (&lb, "", 0, TYPE_MODE (type)); ub = lb; @@ -2112,84 +2156,31 @@ class foperator_div : public range_opera return; } - bool both_maybe_zero = false; - bool both_maybe_inf = false; - bool must_have_signbit_zero = false; - bool must_have_signbit_nonzero = false; - // If +-0.0 is in both ranges, it is a maybe NAN. - if (real_compare (LE_EXPR, &lh_lb, &dconst0) - && real_compare (GE_EXPR, &lh_ub, &dconst0) - && real_compare (LE_EXPR, &rh_lb, &dconst0) - && real_compare (GE_EXPR, &rh_ub, &dconst0)) - { - both_maybe_zero = true; - maybe_nan = true; - } + if (contains_zero_p (lh_lb, lh_ub) && contains_zero_p (rh_lb, rh_ub)) + maybe_nan = true; // If +-INF is in both ranges, it is a maybe NAN. else if ((real_isinf (&lh_lb) || real_isinf (&lh_ub)) && (real_isinf (&rh_lb) || real_isinf (&rh_ub))) - { - both_maybe_inf = true; - maybe_nan = true; - } + maybe_nan = true; else maybe_nan = false; - if (real_isneg (&lh_lb) == real_isneg (&lh_ub) - && real_isneg (&rh_lb) == real_isneg (&rh_ub)) - { - if (real_isneg (&lh_lb) == real_isneg (&rh_ub)) - must_have_signbit_zero = true; - else - must_have_signbit_nonzero = true; - } + int signbit_known = signbit_known_p (lh_lb, lh_ub, rh_lb, rh_ub); // If dividend must be zero, the range is just +-0 // (including if the divisor is +-INF). // If divisor must be +-INF, the range is just +-0 // (including if the dividend is zero). - if ((real_iszero (&lh_lb) && real_iszero (&lh_ub)) - || real_isinf (&rh_lb, false) - || real_isinf (&rh_ub, true)) - { - ub = lb = dconst0; - // If all the boundary signs are the same, [+0.0, +0.0]. - if (must_have_signbit_zero) - ; - // If divisor and dividend must have different signs, - // [-0.0, -0.0]. - else if (must_have_signbit_nonzero) - ub = lb = real_value_negate (&dconst0); - // Otherwise -> [-0.0, +0.0]. - else - lb = real_value_negate (&dconst0); - return; - } + if (zero_p (lh_lb, lh_ub) || singleton_inf_p (rh_lb, rh_ub)) + return zero_range (lb, ub, signbit_known); // If divisor must be zero, the range is just +-INF // (including if the dividend is +-INF). // If dividend must be +-INF, the range is just +-INF // (including if the dividend is zero). - if ((real_iszero (&rh_lb) && real_iszero (&rh_ub)) - || real_isinf (&lh_lb, false) - || real_isinf (&lh_ub, true)) - { - // If all the boundary signs are the same, [+INF, +INF]. - if (must_have_signbit_zero) - ub = lb = dconstinf; - // If divisor and dividend must have different signs, - // [-INF, -INF]. - else if (must_have_signbit_nonzero) - ub = lb = dconstninf; - // Otherwise -> [-INF, +INF] (-INF or +INF). - else - { - lb = dconstninf; - ub = dconstinf; - } - return; - } + if (zero_p (rh_lb, rh_ub) || singleton_inf_p (lh_lb, lh_ub)) + return inf_range (lb, ub, signbit_known); // Otherwise if both operands may be zero, divisor could be // nextafter(0.0, +-1.0) and dividend +-0.0 @@ -2204,30 +2195,12 @@ class foperator_div : public range_opera // signs of divisor and dividend are always the same we have // [+0.0, +INF], if they are always different we have // [-INF, -0.0]. If they vary, VARYING. - if (both_maybe_zero || both_maybe_inf) - { - if (must_have_signbit_zero) - { - lb = dconst0; - ub = dconstinf; - } - else if (must_have_signbit_nonzero) - { - lb = dconstninf; - ub = real_value_negate (&dconst0); - } - else - { - lb = dconstninf; - ub = dconstinf; - } - return; - } + if (maybe_nan) + return zero_to_inf_range (lb, ub, signbit_known); REAL_VALUE_TYPE cp[8]; // Do a cross-division. At this point none of the divisions should // produce a NAN. - gcc_assert (!maybe_nan); frange_arithmetic (RDIV_EXPR, type, cp[0], lh_lb, rh_lb, dconstninf); frange_arithmetic (RDIV_EXPR, type, cp[1], lh_lb, rh_ub, dconstninf); frange_arithmetic (RDIV_EXPR, type, cp[2], lh_ub, rh_lb, dconstninf); @@ -2237,27 +2210,16 @@ class foperator_div : public range_opera frange_arithmetic (RDIV_EXPR, type, cp[6], lh_ub, rh_lb, dconstinf); frange_arithmetic (RDIV_EXPR, type, cp[7], lh_ub, rh_ub, dconstinf); - for (int i = 1; i < 4; ++i) - { - if (real_less (&cp[i], &cp[0]) - || (real_iszero (&cp[0]) && real_isnegzero (&cp[i]))) - std::swap (cp[i], cp[0]); - if (real_less (&cp[4], &cp[i + 4]) - || (real_isnegzero (&cp[4]) && real_iszero (&cp[i + 4]))) - std::swap (cp[i + 4], cp[4]); - } - lb = cp[0]; - ub = cp[4]; + find_range (lb, ub, cp); // If divisor may be zero (but is not known to be only zero), // and dividend can't be zero, the range can go up to -INF or +INF // depending on the signs. - if (real_compare (LE_EXPR, &rh_lb, &dconst0) - && real_compare (GE_EXPR, &rh_ub, &dconst0)) + if (contains_zero_p (rh_lb, rh_ub)) { - if (!must_have_signbit_zero) + if (signbit_known <= 0) real_inf (&lb, true); - if (!must_have_signbit_nonzero) + if (signbit_known >= 0) real_inf (&ub, false); } } Jakub ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH] range-op: Cleanup floating point multiplication and division fold_range [PR107569] 2022-11-11 10:01 ` [PATCH] range-op: Cleanup floating point multiplication and division " Jakub Jelinek @ 2022-11-11 10:12 ` Aldy Hernandez 2022-11-11 10:56 ` Jakub Jelinek 2022-11-11 14:27 ` Aldy Hernandez 1 sibling, 1 reply; 12+ messages in thread From: Aldy Hernandez @ 2022-11-11 10:12 UTC (permalink / raw) To: Jakub Jelinek; +Cc: gcc-patches On 11/11/22 11:01, Jakub Jelinek wrote: > On Fri, Nov 11, 2022 at 09:52:53AM +0100, Jakub Jelinek via Gcc-patches wrote: >> Ok, here is the patch rewritten in the foperator_div style, with special >> cases handled first and then the ordinary cases without problematic cases. >> I guess if/once we have a plugin testing infrastructure, we could compare >> the two versions of the patch, I think this one is more precise. >> And, admittedly there are many similar spots with the foperator_div case >> (but also with significant differences), so perhaps if foperator_{mult,div} >> inherit from some derived class from range_operator_float and that class >> would define various smaller helper static? methods, like this >> discussed in the PR - contains_zero_p, singleton_nan_p, zero_p, >> that >> + bool must_have_signbit_zero = false; >> + bool must_have_signbit_nonzero = false; >> + if (real_isneg (&lh_lb) == real_isneg (&lh_ub) >> + && real_isneg (&rh_lb) == real_isneg (&rh_ub)) >> + { >> + if (real_isneg (&lh_lb) == real_isneg (&rh_ub)) >> + must_have_signbit_zero = true; >> + else >> + must_have_signbit_nonzero = true; >> + } >> returned as -1/0/1 int, and those set result (based on the above value) to >> [+INF, +INF], [-INF, -INF] or [-INF, +INF] >> or >> [+0, +0], [-0, -0] or [-0, +0] >> or >> [+0, +INF], [-INF, -0] or [-INF, +INF] >> and the >> + for (int i = 1; i < 4; ++i) >> + { >> + if (real_less (&cp[i], &cp[0]) >> + || (real_iszero (&cp[0]) && real_isnegzero (&cp[i]))) >> + std::swap (cp[i], cp[0]); >> + if (real_less (&cp[4], &cp[i + 4]) >> + || (real_isnegzero (&cp[4]) && real_iszero (&cp[i + 4]))) >> + std::swap (cp[i + 4], cp[4]); >> + } >> block, it could be smaller and more readable. > > Here is an incremental patch on top of this and division patch, > which does that. > > 2022-11-11 Jakub Jelinek <jakub@redhat.com> > > PR tree-optimization/107569 > * range-op-float.cc (foperator_mult_div_base): New class. > (foperator_mult, foperator_div): Derive from that and use > protected static methods from it to simplify the code. > > --- gcc/range-op-float.cc.jj 2022-11-11 10:13:30.879410560 +0100 > +++ gcc/range-op-float.cc 2022-11-11 10:55:57.602617289 +0100 > @@ -1911,7 +1911,125 @@ class foperator_minus : public range_ope > } fop_minus; > > > -class foperator_mult : public range_operator_float > +class foperator_mult_div_base : public range_operator_float > +{ > +protected: > + // True if [lb, ub] is [+-0, +-0]. > + static bool zero_p (const REAL_VALUE_TYPE &lb, > + const REAL_VALUE_TYPE &ub) > + { > + return real_iszero (&lb) && real_iszero (&ub); > + } > + > + // True if +0 or -0 is in [lb, ub] range. > + static bool contains_zero_p (const REAL_VALUE_TYPE &lb, > + const REAL_VALUE_TYPE &ub) > + { > + return (real_compare (LE_EXPR, &lb, &dconst0) > + && real_compare (GE_EXPR, &ub, &dconst0)); > + } > + > + // True if [lb, ub] is [-INF, -INF] or [+INF, +INF]. > + static bool singleton_inf_p (const REAL_VALUE_TYPE &lb, > + const REAL_VALUE_TYPE &ub) > + { > + return real_isinf (&lb) && real_isinf (&ub, real_isneg (&lb)); > + } > + > + // Return -1 if binary op result must have sign bit set, > + // 1 if binary op result must have sign bit clear, > + // 0 otherwise. > + // Sign bit of binary op result is exclusive or of the > + // operand's sign bits. > + static int signbit_known_p (const REAL_VALUE_TYPE &lh_lb, > + const REAL_VALUE_TYPE &lh_ub, > + const REAL_VALUE_TYPE &rh_lb, > + const REAL_VALUE_TYPE &rh_ub) > + { > + if (real_isneg (&lh_lb) == real_isneg (&lh_ub) > + && real_isneg (&rh_lb) == real_isneg (&rh_ub)) > + { > + if (real_isneg (&lh_lb) == real_isneg (&rh_ub)) > + return 1; > + else > + return -1; > + } > + return 0; > + } > + > + // Set [lb, ub] to [-0, -0], [-0, +0] or [+0, +0] depending on > + // signbit_known. > + static void zero_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, > + int signbit_known) > + { > + ub = lb = dconst0; > + if (signbit_known <= 0) > + lb = real_value_negate (&dconst0); > + if (signbit_known < 0) > + ub = lb; > + } > + > + // Set [lb, ub] to [-INF, -INF], [-INF, +INF] or [+INF, +INF] depending on > + // signbit_known. > + static void inf_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, > + int signbit_known) > + { > + if (signbit_known > 0) > + ub = lb = dconstinf; > + else if (signbit_known < 0) > + ub = lb = dconstninf; > + else > + { > + lb = dconstninf; > + ub = dconstinf; > + } > + } > + > + // Set [lb, ub] to [-INF, -0], [-INF, +INF] or [+0, +INF] depending on > + // signbit_known. > + static void zero_to_inf_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, > + int signbit_known) > + { > + if (signbit_known > 0) > + { > + lb = dconst0; > + ub = dconstinf; > + } > + else if (signbit_known < 0) > + { > + lb = dconstninf; > + ub = real_value_negate (&dconst0); > + } > + else > + { > + lb = dconstninf; > + ub = dconstinf; > + } > + } The above functions look like they could be useful outside of the mult/div implementation. Perhaps put them in file scope, instead limiting it to foperator_mult_div_base? > + static void zero_to_inf_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, > + int signbit_known) > + { > + if (signbit_known > 0) The rest of frange uses bool for a sign. Also, real_iszero, real_isinf, real_inf, etc all use bool sign. Can you use a bool, or is there a reason for the int? > + > + // Given CP[0] to CP[3] floating point values rounded to -INF, > + // set LB to the smallest of them (treating -0 as smaller to +0). > + // Given CP[4] to CP[7] floating point values rounded to +INF, > + // set UB to the largest of them (treating -0 as smaller to +0). > + static void find_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, > + const REAL_VALUE_TYPE (&cp)[8]) > + { > + lb = cp[0]; > + ub = cp[4]; > + for (int i = 1; i < 4; ++i) > + { > + if (real_less (&cp[i], &lb) > + || (real_iszero (&lb) && real_isnegzero (&cp[i]))) > + lb = cp[i]; > + if (real_less (&ub, &cp[i + 4]) > + || (real_isnegzero (&ub) && real_iszero (&cp[i + 4]))) > + ub = cp[i + 4]; > + } > + } > +}; > + > + > +class foperator_mult : public foperator_mult_div_base > { > void rv_fold (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, bool &maybe_nan, > tree type, > @@ -1934,14 +2052,8 @@ class foperator_mult : public range_oper > if (!is_square) > { > // [+-0, +-0] * [+INF,+INF] (or [-INF,-INF] or swapped is a known NAN. > - if ((real_iszero (&lh_lb) > - && real_iszero (&lh_ub) > - && real_isinf (&rh_lb) > - && real_isinf (&rh_ub, real_isneg (&rh_lb))) > - || (real_iszero (&rh_lb) > - && real_iszero (&rh_ub) > - && real_isinf (&lh_lb) > - && real_isinf (&lh_ub, real_isneg (&lh_lb)))) > + if ((zero_p (lh_lb, lh_ub) && singleton_inf_p (rh_lb, rh_ub)) > + || (zero_p (rh_lb, rh_ub) && singleton_inf_p (lh_lb, lh_ub))) > { > real_nan (&lb, "", 0, TYPE_MODE (type)); > ub = lb; > @@ -1951,70 +2063,28 @@ class foperator_mult : public range_oper > > // Otherwise, if one range includes zero and the other ends with +-INF, > // it is a maybe NAN. > - if ((real_compare (LE_EXPR, &lh_lb, &dconst0) > - && real_compare (GE_EXPR, &lh_ub, &dconst0) > + if ((contains_zero_p (lh_lb, lh_ub) > && (real_isinf (&rh_lb) || real_isinf (&rh_ub))) > - || (real_compare (LE_EXPR, &rh_lb, &dconst0) > - && real_compare (GE_EXPR, &rh_ub, &dconst0) > + || (contains_zero_p (rh_lb, rh_ub) > && (real_isinf (&lh_lb) || real_isinf (&lh_ub)))) > { > maybe_nan = true; > > - bool must_have_signbit_zero = false; > - bool must_have_signbit_nonzero = false; > - if (real_isneg (&lh_lb) == real_isneg (&lh_ub) > - && real_isneg (&rh_lb) == real_isneg (&rh_ub)) > - { > - if (real_isneg (&lh_lb) == real_isneg (&rh_ub)) > - must_have_signbit_zero = true; > - else > - must_have_signbit_nonzero = true; > - } > + int signbit_known = signbit_known_p (lh_lb, lh_ub, rh_lb, rh_ub); > > // If one of the ranges that includes INF is singleton > // and the other range includes zero, the resulting > // range is INF and NAN, because the 0 * INF boundary > // case will be NAN, but already nextafter (0, 1) * INF > // is INF. > - if ((real_isinf (&lh_lb) > - && real_isinf (&lh_ub, real_isneg (&lh_lb))) > - || (real_isinf (&rh_lb) > - && real_isinf (&rh_ub, real_isneg (&rh_lb)))) > - { > - // If all the boundary signs are the same, [+INF, +INF]. > - if (must_have_signbit_zero) > - ub = lb = dconstinf; > - // If the two multiplicands have always different sign, > - // [-INF, -INF]. > - else if (must_have_signbit_nonzero) > - ub = lb = dconstninf; > - // Otherwise -> [-INF, +INF] (-INF or +INF). > - else > - { > - lb = dconstninf; > - ub = dconstinf; > - } > - return; > - } > + if (singleton_inf_p (lh_lb, lh_ub) > + || singleton_inf_p (rh_lb, rh_ub)) > + return inf_range (lb, ub, signbit_known); > > // If one of the multiplicands must be zero, the resulting > // range is +-0 and NAN. > - if ((real_iszero (&lh_lb) && real_iszero (&lh_ub)) > - || (real_iszero (&rh_lb) && real_iszero (&rh_ub))) > - { > - ub = lb = dconst0; > - // If all the boundary signs are the same, [+0.0, +0.0]. > - if (must_have_signbit_zero) > - ; > - // If divisor and dividend must have different signs, > - // [-0.0, -0.0]. > - else if (must_have_signbit_nonzero) > - ub = lb = real_value_negate (&dconst0); > - // Otherwise -> [-0.0, +0.0]. > - else > - lb = real_value_negate (&dconst0); > - return; > - } > + if (zero_p (lh_lb, lh_ub) || zero_p (rh_lb, rh_ub)) > + return zero_range (lb, ub, signbit_known); > > // Otherwise one of the multiplicands could be > // [0.0, nextafter (0.0, 1.0)] and the [DBL_MAX, INF] > @@ -2022,27 +2092,13 @@ class foperator_mult : public range_oper > // is still 0.0, nextafter (0.0, 1.0) * INF is still INF, > // so if the signs are always the same or always different, > // result is [+0.0, +INF] or [-INF, -0.0], otherwise VARYING. > - if (must_have_signbit_zero) > - { > - lb = dconst0; > - ub = dconstinf; > - } > - else if (must_have_signbit_nonzero) > - { > - lb = dconstninf; > - ub = real_value_negate (&dconst0); > - } > - else > - { > - lb = dconstninf; > - ub = dconstinf; > - } > - return; > + return zero_to_inf_range (lb, ub, signbit_known); > } > } > > REAL_VALUE_TYPE cp[8]; > - // Do a cross-product. > + // Do a cross-product. At this point none of the multiplications > + // should produce a NAN. > frange_arithmetic (MULT_EXPR, type, cp[0], lh_lb, rh_lb, dconstninf); > frange_arithmetic (MULT_EXPR, type, cp[4], lh_lb, rh_lb, dconstinf); > if (is_square) > @@ -2052,9 +2108,13 @@ class foperator_mult : public range_oper > // otherwise min (lh_lb * lh_lb, lh_ub * lh_ub). > // -0.0 rather than 0.0 because VREL_EQ doesn't prove that > // x and y are bitwise equal, just that they compare equal. > - if (real_compare (LE_EXPR, &lh_lb, &dconst0) > - && real_compare (GE_EXPR, &lh_ub, &dconst0)) > - cp[1] = real_value_negate (&dconst0); > + if (contains_zero_p (lh_lb, lh_ub)) > + { > + if (real_isneg (&lh_lb) == real_isneg (&lh_ub)) > + cp[1] = dconst0; > + else > + cp[1] = real_value_negate (&dconst0); > + } > else > cp[1] = cp[0]; > cp[2] = cp[0]; > @@ -2071,22 +2131,12 @@ class foperator_mult : public range_oper > frange_arithmetic (MULT_EXPR, type, cp[3], lh_ub, rh_ub, dconstninf); > frange_arithmetic (MULT_EXPR, type, cp[7], lh_ub, rh_ub, dconstinf); > > - for (int i = 1; i < 4; ++i) > - { > - if (real_less (&cp[i], &cp[0]) > - || (real_iszero (&cp[0]) && real_isnegzero (&cp[i]))) > - std::swap (cp[i], cp[0]); > - if (real_less (&cp[4], &cp[i + 4]) > - || (real_isnegzero (&cp[4]) && real_iszero (&cp[i + 4]))) > - std::swap (cp[i + 4], cp[4]); > - } > - lb = cp[0]; > - ub = cp[4]; > - > + find_range (lb, ub, cp); > } > } fop_mult; > > -class foperator_div : public range_operator_float > + > +class foperator_div : public foperator_mult_div_base > { > void rv_fold (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, bool &maybe_nan, > tree type, > @@ -2097,14 +2147,8 @@ class foperator_div : public range_opera > relation_kind) const final override > { > // +-0.0 / +-0.0 or +-INF / +-INF is a known NAN. > - if ((real_iszero (&lh_lb) > - && real_iszero (&lh_ub) > - && real_iszero (&rh_lb) > - && real_iszero (&rh_ub)) > - || (real_isinf (&lh_lb) > - && real_isinf (&lh_ub, real_isneg (&lh_lb)) > - && real_isinf (&rh_lb) > - && real_isinf (&rh_ub, real_isneg (&rh_lb)))) > + if ((zero_p (lh_lb, lh_ub) && zero_p (rh_lb, rh_ub)) > + || (singleton_inf_p (lh_lb, lh_ub) || singleton_inf_p (rh_lb, rh_ub))) > { > real_nan (&lb, "", 0, TYPE_MODE (type)); > ub = lb; > @@ -2112,84 +2156,31 @@ class foperator_div : public range_opera > return; > } > > - bool both_maybe_zero = false; > - bool both_maybe_inf = false; > - bool must_have_signbit_zero = false; > - bool must_have_signbit_nonzero = false; > - > // If +-0.0 is in both ranges, it is a maybe NAN. > - if (real_compare (LE_EXPR, &lh_lb, &dconst0) > - && real_compare (GE_EXPR, &lh_ub, &dconst0) > - && real_compare (LE_EXPR, &rh_lb, &dconst0) > - && real_compare (GE_EXPR, &rh_ub, &dconst0)) > - { > - both_maybe_zero = true; > - maybe_nan = true; > - } > + if (contains_zero_p (lh_lb, lh_ub) && contains_zero_p (rh_lb, rh_ub)) > + maybe_nan = true; > // If +-INF is in both ranges, it is a maybe NAN. > else if ((real_isinf (&lh_lb) || real_isinf (&lh_ub)) > && (real_isinf (&rh_lb) || real_isinf (&rh_ub))) > - { > - both_maybe_inf = true; > - maybe_nan = true; > - } > + maybe_nan = true; > else > maybe_nan = false; > > - if (real_isneg (&lh_lb) == real_isneg (&lh_ub) > - && real_isneg (&rh_lb) == real_isneg (&rh_ub)) > - { > - if (real_isneg (&lh_lb) == real_isneg (&rh_ub)) > - must_have_signbit_zero = true; > - else > - must_have_signbit_nonzero = true; > - } > + int signbit_known = signbit_known_p (lh_lb, lh_ub, rh_lb, rh_ub); > > // If dividend must be zero, the range is just +-0 > // (including if the divisor is +-INF). > // If divisor must be +-INF, the range is just +-0 > // (including if the dividend is zero). > - if ((real_iszero (&lh_lb) && real_iszero (&lh_ub)) > - || real_isinf (&rh_lb, false) > - || real_isinf (&rh_ub, true)) > - { > - ub = lb = dconst0; > - // If all the boundary signs are the same, [+0.0, +0.0]. > - if (must_have_signbit_zero) > - ; > - // If divisor and dividend must have different signs, > - // [-0.0, -0.0]. > - else if (must_have_signbit_nonzero) > - ub = lb = real_value_negate (&dconst0); > - // Otherwise -> [-0.0, +0.0]. > - else > - lb = real_value_negate (&dconst0); > - return; > - } > + if (zero_p (lh_lb, lh_ub) || singleton_inf_p (rh_lb, rh_ub)) > + return zero_range (lb, ub, signbit_known); > > // If divisor must be zero, the range is just +-INF > // (including if the dividend is +-INF). > // If dividend must be +-INF, the range is just +-INF > // (including if the dividend is zero). > - if ((real_iszero (&rh_lb) && real_iszero (&rh_ub)) > - || real_isinf (&lh_lb, false) > - || real_isinf (&lh_ub, true)) > - { > - // If all the boundary signs are the same, [+INF, +INF]. > - if (must_have_signbit_zero) > - ub = lb = dconstinf; > - // If divisor and dividend must have different signs, > - // [-INF, -INF]. > - else if (must_have_signbit_nonzero) > - ub = lb = dconstninf; > - // Otherwise -> [-INF, +INF] (-INF or +INF). > - else > - { > - lb = dconstninf; > - ub = dconstinf; > - } > - return; > - } > + if (zero_p (rh_lb, rh_ub) || singleton_inf_p (lh_lb, lh_ub)) > + return inf_range (lb, ub, signbit_known); > > // Otherwise if both operands may be zero, divisor could be > // nextafter(0.0, +-1.0) and dividend +-0.0 > @@ -2204,30 +2195,12 @@ class foperator_div : public range_opera > // signs of divisor and dividend are always the same we have > // [+0.0, +INF], if they are always different we have > // [-INF, -0.0]. If they vary, VARYING. > - if (both_maybe_zero || both_maybe_inf) > - { > - if (must_have_signbit_zero) > - { > - lb = dconst0; > - ub = dconstinf; > - } > - else if (must_have_signbit_nonzero) > - { > - lb = dconstninf; > - ub = real_value_negate (&dconst0); > - } > - else > - { > - lb = dconstninf; > - ub = dconstinf; > - } > - return; > - } > + if (maybe_nan) > + return zero_to_inf_range (lb, ub, signbit_known); > > REAL_VALUE_TYPE cp[8]; > // Do a cross-division. At this point none of the divisions should > // produce a NAN. > - gcc_assert (!maybe_nan); > frange_arithmetic (RDIV_EXPR, type, cp[0], lh_lb, rh_lb, dconstninf); > frange_arithmetic (RDIV_EXPR, type, cp[1], lh_lb, rh_ub, dconstninf); > frange_arithmetic (RDIV_EXPR, type, cp[2], lh_ub, rh_lb, dconstninf); > @@ -2237,27 +2210,16 @@ class foperator_div : public range_opera > frange_arithmetic (RDIV_EXPR, type, cp[6], lh_ub, rh_lb, dconstinf); > frange_arithmetic (RDIV_EXPR, type, cp[7], lh_ub, rh_ub, dconstinf); > > - for (int i = 1; i < 4; ++i) > - { > - if (real_less (&cp[i], &cp[0]) > - || (real_iszero (&cp[0]) && real_isnegzero (&cp[i]))) > - std::swap (cp[i], cp[0]); > - if (real_less (&cp[4], &cp[i + 4]) > - || (real_isnegzero (&cp[4]) && real_iszero (&cp[i + 4]))) > - std::swap (cp[i + 4], cp[4]); > - } > - lb = cp[0]; > - ub = cp[4]; > + find_range (lb, ub, cp); > > // If divisor may be zero (but is not known to be only zero), > // and dividend can't be zero, the range can go up to -INF or +INF > // depending on the signs. > - if (real_compare (LE_EXPR, &rh_lb, &dconst0) > - && real_compare (GE_EXPR, &rh_ub, &dconst0)) > + if (contains_zero_p (rh_lb, rh_ub)) > { > - if (!must_have_signbit_zero) > + if (signbit_known <= 0) > real_inf (&lb, true); > - if (!must_have_signbit_nonzero) > + if (signbit_known >= 0) > real_inf (&ub, false); > } > } BTW, looks a lot more readable. Thanks. Aldy ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH] range-op: Cleanup floating point multiplication and division fold_range [PR107569] 2022-11-11 10:12 ` Aldy Hernandez @ 2022-11-11 10:56 ` Jakub Jelinek 0 siblings, 0 replies; 12+ messages in thread From: Jakub Jelinek @ 2022-11-11 10:56 UTC (permalink / raw) To: Aldy Hernandez; +Cc: gcc-patches On Fri, Nov 11, 2022 at 11:12:01AM +0100, Aldy Hernandez wrote: > > --- gcc/range-op-float.cc.jj 2022-11-11 10:13:30.879410560 +0100 > > +++ gcc/range-op-float.cc 2022-11-11 10:55:57.602617289 +0100 > > @@ -1911,7 +1911,125 @@ class foperator_minus : public range_ope > > } fop_minus; > > -class foperator_mult : public range_operator_float > > +class foperator_mult_div_base : public range_operator_float > > +{ > > +protected: > > + // True if [lb, ub] is [+-0, +-0]. > > + static bool zero_p (const REAL_VALUE_TYPE &lb, > > + const REAL_VALUE_TYPE &ub) > > + { > > + return real_iszero (&lb) && real_iszero (&ub); > > + } > > + > > + // True if +0 or -0 is in [lb, ub] range. > > + static bool contains_zero_p (const REAL_VALUE_TYPE &lb, > > + const REAL_VALUE_TYPE &ub) > > + { > > + return (real_compare (LE_EXPR, &lb, &dconst0) > > + && real_compare (GE_EXPR, &ub, &dconst0)); > > + } > > + > > + // True if [lb, ub] is [-INF, -INF] or [+INF, +INF]. > > + static bool singleton_inf_p (const REAL_VALUE_TYPE &lb, > > + const REAL_VALUE_TYPE &ub) > > + { > > + return real_isinf (&lb) && real_isinf (&ub, real_isneg (&lb)); > > + } > > + > > + // Return -1 if binary op result must have sign bit set, > > + // 1 if binary op result must have sign bit clear, > > + // 0 otherwise. > > + // Sign bit of binary op result is exclusive or of the > > + // operand's sign bits. > > + static int signbit_known_p (const REAL_VALUE_TYPE &lh_lb, > > + const REAL_VALUE_TYPE &lh_ub, > > + const REAL_VALUE_TYPE &rh_lb, > > + const REAL_VALUE_TYPE &rh_ub) > > + { > > + if (real_isneg (&lh_lb) == real_isneg (&lh_ub) > > + && real_isneg (&rh_lb) == real_isneg (&rh_ub)) > > + { > > + if (real_isneg (&lh_lb) == real_isneg (&rh_ub)) > > + return 1; > > + else > > + return -1; > > + } > > + return 0; > > + } > > + > > + // Set [lb, ub] to [-0, -0], [-0, +0] or [+0, +0] depending on > > + // signbit_known. > > + static void zero_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, > > + int signbit_known) > > + { > > + ub = lb = dconst0; > > + if (signbit_known <= 0) > > + lb = real_value_negate (&dconst0); > > + if (signbit_known < 0) > > + ub = lb; > > + } > > + > > + // Set [lb, ub] to [-INF, -INF], [-INF, +INF] or [+INF, +INF] depending on > > + // signbit_known. > > + static void inf_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, > > + int signbit_known) > > + { > > + if (signbit_known > 0) > > + ub = lb = dconstinf; > > + else if (signbit_known < 0) > > + ub = lb = dconstninf; > > + else > > + { > > + lb = dconstninf; > > + ub = dconstinf; > > + } > > + } > > + > > + // Set [lb, ub] to [-INF, -0], [-INF, +INF] or [+0, +INF] depending on > > + // signbit_known. > > + static void zero_to_inf_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, > > + int signbit_known) > > + { > > + if (signbit_known > 0) > > + { > > + lb = dconst0; > > + ub = dconstinf; > > + } > > + else if (signbit_known < 0) > > + { > > + lb = dconstninf; > > + ub = real_value_negate (&dconst0); > > + } > > + else > > + { > > + lb = dconstninf; > > + ub = dconstinf; > > + } > > + } > > The above functions look like they could be useful outside of the mult/div > implementation. Perhaps put them in file scope, instead limiting it to > foperator_mult_div_base? Well, I didn't want to export them to everything and most of the file works on franges, not on REAL_VALUE_TYPE pairs. But sure, if there are other uses, it can be moved elsewhere. > > + static void zero_to_inf_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE > &ub, > > + int signbit_known) > > + { > > + if (signbit_known > 0) > > The rest of frange uses bool for a sign. Also, real_iszero, real_isinf, > real_inf, etc all use bool sign. Can you use a bool, or is there a reason > for the int? I need a tristate. signbit is known and clear (this happens when all the 4 bounds have the same sign), signbit is known and set (this happens when one operand has signbit clear and the other signbit set, or vice versa), or the state of the resulting signbit is unknown (at least one operand has some values in the range with clear and others with set signbit). Jakub ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH] range-op: Cleanup floating point multiplication and division fold_range [PR107569] 2022-11-11 10:01 ` [PATCH] range-op: Cleanup floating point multiplication and division " Jakub Jelinek 2022-11-11 10:12 ` Aldy Hernandez @ 2022-11-11 14:27 ` Aldy Hernandez 1 sibling, 0 replies; 12+ messages in thread From: Aldy Hernandez @ 2022-11-11 14:27 UTC (permalink / raw) To: Jakub Jelinek; +Cc: gcc-patches, amacleod On 11/11/22 11:01, Jakub Jelinek wrote: > On Fri, Nov 11, 2022 at 09:52:53AM +0100, Jakub Jelinek via Gcc-patches wrote: >> Ok, here is the patch rewritten in the foperator_div style, with special >> cases handled first and then the ordinary cases without problematic cases. >> I guess if/once we have a plugin testing infrastructure, we could compare >> the two versions of the patch, I think this one is more precise. >> And, admittedly there are many similar spots with the foperator_div case >> (but also with significant differences), so perhaps if foperator_{mult,div} >> inherit from some derived class from range_operator_float and that class >> would define various smaller helper static? methods, like this >> discussed in the PR - contains_zero_p, singleton_nan_p, zero_p, >> that >> + bool must_have_signbit_zero = false; >> + bool must_have_signbit_nonzero = false; >> + if (real_isneg (&lh_lb) == real_isneg (&lh_ub) >> + && real_isneg (&rh_lb) == real_isneg (&rh_ub)) >> + { >> + if (real_isneg (&lh_lb) == real_isneg (&rh_ub)) >> + must_have_signbit_zero = true; >> + else >> + must_have_signbit_nonzero = true; >> + } >> returned as -1/0/1 int, and those set result (based on the above value) to >> [+INF, +INF], [-INF, -INF] or [-INF, +INF] >> or >> [+0, +0], [-0, -0] or [-0, +0] >> or >> [+0, +INF], [-INF, -0] or [-INF, +INF] >> and the >> + for (int i = 1; i < 4; ++i) >> + { >> + if (real_less (&cp[i], &cp[0]) >> + || (real_iszero (&cp[0]) && real_isnegzero (&cp[i]))) >> + std::swap (cp[i], cp[0]); >> + if (real_less (&cp[4], &cp[i + 4]) >> + || (real_isnegzero (&cp[4]) && real_iszero (&cp[i + 4]))) >> + std::swap (cp[i + 4], cp[4]); >> + } >> block, it could be smaller and more readable. > > Here is an incremental patch on top of this and division patch, > which does that. > > 2022-11-11 Jakub Jelinek <jakub@redhat.com> > > PR tree-optimization/107569 > * range-op-float.cc (foperator_mult_div_base): New class. > (foperator_mult, foperator_div): Derive from that and use > protected static methods from it to simplify the code. > > --- gcc/range-op-float.cc.jj 2022-11-11 10:13:30.879410560 +0100 > +++ gcc/range-op-float.cc 2022-11-11 10:55:57.602617289 +0100 > @@ -1911,7 +1911,125 @@ class foperator_minus : public range_ope > } fop_minus; > > > -class foperator_mult : public range_operator_float > +class foperator_mult_div_base : public range_operator_float > +{ > +protected: > + // True if [lb, ub] is [+-0, +-0]. > + static bool zero_p (const REAL_VALUE_TYPE &lb, > + const REAL_VALUE_TYPE &ub) > + { > + return real_iszero (&lb) && real_iszero (&ub); > + } > + > + // True if +0 or -0 is in [lb, ub] range. > + static bool contains_zero_p (const REAL_VALUE_TYPE &lb, > + const REAL_VALUE_TYPE &ub) > + { > + return (real_compare (LE_EXPR, &lb, &dconst0) > + && real_compare (GE_EXPR, &ub, &dconst0)); > + } > + > + // True if [lb, ub] is [-INF, -INF] or [+INF, +INF]. > + static bool singleton_inf_p (const REAL_VALUE_TYPE &lb, > + const REAL_VALUE_TYPE &ub) > + { > + return real_isinf (&lb) && real_isinf (&ub, real_isneg (&lb)); > + } > + > + // Return -1 if binary op result must have sign bit set, > + // 1 if binary op result must have sign bit clear, > + // 0 otherwise. > + // Sign bit of binary op result is exclusive or of the > + // operand's sign bits. > + static int signbit_known_p (const REAL_VALUE_TYPE &lh_lb, > + const REAL_VALUE_TYPE &lh_ub, > + const REAL_VALUE_TYPE &rh_lb, > + const REAL_VALUE_TYPE &rh_ub) > + { > + if (real_isneg (&lh_lb) == real_isneg (&lh_ub) > + && real_isneg (&rh_lb) == real_isneg (&rh_ub)) > + { > + if (real_isneg (&lh_lb) == real_isneg (&rh_ub)) > + return 1; > + else > + return -1; > + } > + return 0; > + } > + > + // Set [lb, ub] to [-0, -0], [-0, +0] or [+0, +0] depending on > + // signbit_known. > + static void zero_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, > + int signbit_known) > + { > + ub = lb = dconst0; > + if (signbit_known <= 0) > + lb = real_value_negate (&dconst0); > + if (signbit_known < 0) > + ub = lb; > + } > + > + // Set [lb, ub] to [-INF, -INF], [-INF, +INF] or [+INF, +INF] depending on > + // signbit_known. > + static void inf_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, > + int signbit_known) > + { > + if (signbit_known > 0) > + ub = lb = dconstinf; > + else if (signbit_known < 0) > + ub = lb = dconstninf; > + else > + { > + lb = dconstninf; > + ub = dconstinf; > + } > + } > + > + // Set [lb, ub] to [-INF, -0], [-INF, +INF] or [+0, +INF] depending on > + // signbit_known. > + static void zero_to_inf_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, > + int signbit_known) > + { > + if (signbit_known > 0) > + { > + lb = dconst0; > + ub = dconstinf; > + } > + else if (signbit_known < 0) > + { > + lb = dconstninf; > + ub = real_value_negate (&dconst0); > + } > + else > + { > + lb = dconstninf; > + ub = dconstinf; > + } > + } > + > + // Given CP[0] to CP[3] floating point values rounded to -INF, > + // set LB to the smallest of them (treating -0 as smaller to +0). > + // Given CP[4] to CP[7] floating point values rounded to +INF, > + // set UB to the largest of them (treating -0 as smaller to +0). > + static void find_range (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, > + const REAL_VALUE_TYPE (&cp)[8]) > + { > + lb = cp[0]; > + ub = cp[4]; > + for (int i = 1; i < 4; ++i) > + { > + if (real_less (&cp[i], &lb) > + || (real_iszero (&lb) && real_isnegzero (&cp[i]))) > + lb = cp[i]; > + if (real_less (&ub, &cp[i + 4]) > + || (real_isnegzero (&ub) && real_iszero (&cp[i + 4]))) > + ub = cp[i + 4]; > + } > + } > +}; It seems find_range() is only applicable to mult/div. If so, perhaps that one should go in foperator_mult_div_base. Unless you think it'll be useful for implementing other operators. > + > + > +class foperator_mult : public foperator_mult_div_base > { > void rv_fold (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, bool &maybe_nan, > tree type, > @@ -1934,14 +2052,8 @@ class foperator_mult : public range_oper > if (!is_square) > { > // [+-0, +-0] * [+INF,+INF] (or [-INF,-INF] or swapped is a known NAN. > - if ((real_iszero (&lh_lb) > - && real_iszero (&lh_ub) > - && real_isinf (&rh_lb) > - && real_isinf (&rh_ub, real_isneg (&rh_lb))) > - || (real_iszero (&rh_lb) > - && real_iszero (&rh_ub) > - && real_isinf (&lh_lb) > - && real_isinf (&lh_ub, real_isneg (&lh_lb)))) > + if ((zero_p (lh_lb, lh_ub) && singleton_inf_p (rh_lb, rh_ub)) > + || (zero_p (rh_lb, rh_ub) && singleton_inf_p (lh_lb, lh_ub))) > { > real_nan (&lb, "", 0, TYPE_MODE (type)); > ub = lb; > @@ -1951,70 +2063,28 @@ class foperator_mult : public range_oper > > // Otherwise, if one range includes zero and the other ends with +-INF, > // it is a maybe NAN. > - if ((real_compare (LE_EXPR, &lh_lb, &dconst0) > - && real_compare (GE_EXPR, &lh_ub, &dconst0) > + if ((contains_zero_p (lh_lb, lh_ub) > && (real_isinf (&rh_lb) || real_isinf (&rh_ub))) > - || (real_compare (LE_EXPR, &rh_lb, &dconst0) > - && real_compare (GE_EXPR, &rh_ub, &dconst0) > + || (contains_zero_p (rh_lb, rh_ub) > && (real_isinf (&lh_lb) || real_isinf (&lh_ub)))) > { > maybe_nan = true; > > - bool must_have_signbit_zero = false; > - bool must_have_signbit_nonzero = false; > - if (real_isneg (&lh_lb) == real_isneg (&lh_ub) > - && real_isneg (&rh_lb) == real_isneg (&rh_ub)) > - { > - if (real_isneg (&lh_lb) == real_isneg (&rh_ub)) > - must_have_signbit_zero = true; > - else > - must_have_signbit_nonzero = true; > - } > + int signbit_known = signbit_known_p (lh_lb, lh_ub, rh_lb, rh_ub); > > // If one of the ranges that includes INF is singleton > // and the other range includes zero, the resulting > // range is INF and NAN, because the 0 * INF boundary > // case will be NAN, but already nextafter (0, 1) * INF > // is INF. > - if ((real_isinf (&lh_lb) > - && real_isinf (&lh_ub, real_isneg (&lh_lb))) > - || (real_isinf (&rh_lb) > - && real_isinf (&rh_ub, real_isneg (&rh_lb)))) > - { > - // If all the boundary signs are the same, [+INF, +INF]. > - if (must_have_signbit_zero) > - ub = lb = dconstinf; > - // If the two multiplicands have always different sign, > - // [-INF, -INF]. > - else if (must_have_signbit_nonzero) > - ub = lb = dconstninf; > - // Otherwise -> [-INF, +INF] (-INF or +INF). > - else > - { > - lb = dconstninf; > - ub = dconstinf; > - } > - return; > - } > + if (singleton_inf_p (lh_lb, lh_ub) > + || singleton_inf_p (rh_lb, rh_ub)) > + return inf_range (lb, ub, signbit_known); > > // If one of the multiplicands must be zero, the resulting > // range is +-0 and NAN. > - if ((real_iszero (&lh_lb) && real_iszero (&lh_ub)) > - || (real_iszero (&rh_lb) && real_iszero (&rh_ub))) > - { > - ub = lb = dconst0; > - // If all the boundary signs are the same, [+0.0, +0.0]. > - if (must_have_signbit_zero) > - ; > - // If divisor and dividend must have different signs, > - // [-0.0, -0.0]. > - else if (must_have_signbit_nonzero) > - ub = lb = real_value_negate (&dconst0); > - // Otherwise -> [-0.0, +0.0]. > - else > - lb = real_value_negate (&dconst0); > - return; > - } > + if (zero_p (lh_lb, lh_ub) || zero_p (rh_lb, rh_ub)) > + return zero_range (lb, ub, signbit_known); > > // Otherwise one of the multiplicands could be > // [0.0, nextafter (0.0, 1.0)] and the [DBL_MAX, INF] > @@ -2022,27 +2092,13 @@ class foperator_mult : public range_oper > // is still 0.0, nextafter (0.0, 1.0) * INF is still INF, > // so if the signs are always the same or always different, > // result is [+0.0, +INF] or [-INF, -0.0], otherwise VARYING. > - if (must_have_signbit_zero) > - { > - lb = dconst0; > - ub = dconstinf; > - } > - else if (must_have_signbit_nonzero) > - { > - lb = dconstninf; > - ub = real_value_negate (&dconst0); > - } > - else > - { > - lb = dconstninf; > - ub = dconstinf; > - } > - return; > + return zero_to_inf_range (lb, ub, signbit_known); > } > } > > REAL_VALUE_TYPE cp[8]; > - // Do a cross-product. > + // Do a cross-product. At this point none of the multiplications > + // should produce a NAN. > frange_arithmetic (MULT_EXPR, type, cp[0], lh_lb, rh_lb, dconstninf); > frange_arithmetic (MULT_EXPR, type, cp[4], lh_lb, rh_lb, dconstinf); > if (is_square) > @@ -2052,9 +2108,13 @@ class foperator_mult : public range_oper > // otherwise min (lh_lb * lh_lb, lh_ub * lh_ub). > // -0.0 rather than 0.0 because VREL_EQ doesn't prove that > // x and y are bitwise equal, just that they compare equal. > - if (real_compare (LE_EXPR, &lh_lb, &dconst0) > - && real_compare (GE_EXPR, &lh_ub, &dconst0)) > - cp[1] = real_value_negate (&dconst0); > + if (contains_zero_p (lh_lb, lh_ub)) > + { > + if (real_isneg (&lh_lb) == real_isneg (&lh_ub)) > + cp[1] = dconst0; > + else > + cp[1] = real_value_negate (&dconst0); > + } > else > cp[1] = cp[0]; > cp[2] = cp[0]; > @@ -2071,22 +2131,12 @@ class foperator_mult : public range_oper > frange_arithmetic (MULT_EXPR, type, cp[3], lh_ub, rh_ub, dconstninf); > frange_arithmetic (MULT_EXPR, type, cp[7], lh_ub, rh_ub, dconstinf); > > - for (int i = 1; i < 4; ++i) > - { > - if (real_less (&cp[i], &cp[0]) > - || (real_iszero (&cp[0]) && real_isnegzero (&cp[i]))) > - std::swap (cp[i], cp[0]); > - if (real_less (&cp[4], &cp[i + 4]) > - || (real_isnegzero (&cp[4]) && real_iszero (&cp[i + 4]))) > - std::swap (cp[i + 4], cp[4]); > - } > - lb = cp[0]; > - ub = cp[4]; > - > + find_range (lb, ub, cp); > } > } fop_mult; > > -class foperator_div : public range_operator_float > + > +class foperator_div : public foperator_mult_div_base > { > void rv_fold (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub, bool &maybe_nan, > tree type, > @@ -2097,14 +2147,8 @@ class foperator_div : public range_opera > relation_kind) const final override > { > // +-0.0 / +-0.0 or +-INF / +-INF is a known NAN. > - if ((real_iszero (&lh_lb) > - && real_iszero (&lh_ub) > - && real_iszero (&rh_lb) > - && real_iszero (&rh_ub)) > - || (real_isinf (&lh_lb) > - && real_isinf (&lh_ub, real_isneg (&lh_lb)) > - && real_isinf (&rh_lb) > - && real_isinf (&rh_ub, real_isneg (&rh_lb)))) > + if ((zero_p (lh_lb, lh_ub) && zero_p (rh_lb, rh_ub)) > + || (singleton_inf_p (lh_lb, lh_ub) || singleton_inf_p (rh_lb, rh_ub))) > { > real_nan (&lb, "", 0, TYPE_MODE (type)); > ub = lb; > @@ -2112,84 +2156,31 @@ class foperator_div : public range_opera > return; > } > > - bool both_maybe_zero = false; > - bool both_maybe_inf = false; > - bool must_have_signbit_zero = false; > - bool must_have_signbit_nonzero = false; > - > // If +-0.0 is in both ranges, it is a maybe NAN. > - if (real_compare (LE_EXPR, &lh_lb, &dconst0) > - && real_compare (GE_EXPR, &lh_ub, &dconst0) > - && real_compare (LE_EXPR, &rh_lb, &dconst0) > - && real_compare (GE_EXPR, &rh_ub, &dconst0)) > - { > - both_maybe_zero = true; > - maybe_nan = true; > - } > + if (contains_zero_p (lh_lb, lh_ub) && contains_zero_p (rh_lb, rh_ub)) > + maybe_nan = true; > // If +-INF is in both ranges, it is a maybe NAN. > else if ((real_isinf (&lh_lb) || real_isinf (&lh_ub)) > && (real_isinf (&rh_lb) || real_isinf (&rh_ub))) > - { > - both_maybe_inf = true; > - maybe_nan = true; > - } > + maybe_nan = true; > else > maybe_nan = false; > > - if (real_isneg (&lh_lb) == real_isneg (&lh_ub) > - && real_isneg (&rh_lb) == real_isneg (&rh_ub)) > - { > - if (real_isneg (&lh_lb) == real_isneg (&rh_ub)) > - must_have_signbit_zero = true; > - else > - must_have_signbit_nonzero = true; > - } > + int signbit_known = signbit_known_p (lh_lb, lh_ub, rh_lb, rh_ub); > > // If dividend must be zero, the range is just +-0 > // (including if the divisor is +-INF). > // If divisor must be +-INF, the range is just +-0 > // (including if the dividend is zero). > - if ((real_iszero (&lh_lb) && real_iszero (&lh_ub)) > - || real_isinf (&rh_lb, false) > - || real_isinf (&rh_ub, true)) > - { > - ub = lb = dconst0; > - // If all the boundary signs are the same, [+0.0, +0.0]. > - if (must_have_signbit_zero) > - ; > - // If divisor and dividend must have different signs, > - // [-0.0, -0.0]. > - else if (must_have_signbit_nonzero) > - ub = lb = real_value_negate (&dconst0); > - // Otherwise -> [-0.0, +0.0]. > - else > - lb = real_value_negate (&dconst0); > - return; > - } > + if (zero_p (lh_lb, lh_ub) || singleton_inf_p (rh_lb, rh_ub)) > + return zero_range (lb, ub, signbit_known); > > // If divisor must be zero, the range is just +-INF > // (including if the dividend is +-INF). > // If dividend must be +-INF, the range is just +-INF > // (including if the dividend is zero). > - if ((real_iszero (&rh_lb) && real_iszero (&rh_ub)) > - || real_isinf (&lh_lb, false) > - || real_isinf (&lh_ub, true)) > - { > - // If all the boundary signs are the same, [+INF, +INF]. > - if (must_have_signbit_zero) > - ub = lb = dconstinf; > - // If divisor and dividend must have different signs, > - // [-INF, -INF]. > - else if (must_have_signbit_nonzero) > - ub = lb = dconstninf; > - // Otherwise -> [-INF, +INF] (-INF or +INF). > - else > - { > - lb = dconstninf; > - ub = dconstinf; > - } > - return; > - } > + if (zero_p (rh_lb, rh_ub) || singleton_inf_p (lh_lb, lh_ub)) > + return inf_range (lb, ub, signbit_known); > > // Otherwise if both operands may be zero, divisor could be > // nextafter(0.0, +-1.0) and dividend +-0.0 > @@ -2204,30 +2195,12 @@ class foperator_div : public range_opera > // signs of divisor and dividend are always the same we have > // [+0.0, +INF], if they are always different we have > // [-INF, -0.0]. If they vary, VARYING. > - if (both_maybe_zero || both_maybe_inf) > - { > - if (must_have_signbit_zero) > - { > - lb = dconst0; > - ub = dconstinf; > - } > - else if (must_have_signbit_nonzero) > - { > - lb = dconstninf; > - ub = real_value_negate (&dconst0); > - } > - else > - { > - lb = dconstninf; > - ub = dconstinf; > - } > - return; > - } > + if (maybe_nan) > + return zero_to_inf_range (lb, ub, signbit_known); > > REAL_VALUE_TYPE cp[8]; > // Do a cross-division. At this point none of the divisions should > // produce a NAN. > - gcc_assert (!maybe_nan); > frange_arithmetic (RDIV_EXPR, type, cp[0], lh_lb, rh_lb, dconstninf); > frange_arithmetic (RDIV_EXPR, type, cp[1], lh_lb, rh_ub, dconstninf); > frange_arithmetic (RDIV_EXPR, type, cp[2], lh_ub, rh_lb, dconstninf); > @@ -2237,27 +2210,16 @@ class foperator_div : public range_opera > frange_arithmetic (RDIV_EXPR, type, cp[6], lh_ub, rh_lb, dconstinf); > frange_arithmetic (RDIV_EXPR, type, cp[7], lh_ub, rh_ub, dconstinf); > > - for (int i = 1; i < 4; ++i) > - { > - if (real_less (&cp[i], &cp[0]) > - || (real_iszero (&cp[0]) && real_isnegzero (&cp[i]))) > - std::swap (cp[i], cp[0]); > - if (real_less (&cp[4], &cp[i + 4]) > - || (real_isnegzero (&cp[4]) && real_iszero (&cp[i + 4]))) > - std::swap (cp[i + 4], cp[4]); > - } > - lb = cp[0]; > - ub = cp[4]; > + find_range (lb, ub, cp); > > // If divisor may be zero (but is not known to be only zero), > // and dividend can't be zero, the range can go up to -INF or +INF > // depending on the signs. > - if (real_compare (LE_EXPR, &rh_lb, &dconst0) > - && real_compare (GE_EXPR, &rh_ub, &dconst0)) > + if (contains_zero_p (rh_lb, rh_ub)) > { > - if (!must_have_signbit_zero) > + if (signbit_known <= 0) > real_inf (&lb, true); > - if (!must_have_signbit_nonzero) > + if (signbit_known >= 0) > real_inf (&ub, false); > } > } I have no objections to any of your mult/div patches. You're obviously more qualified to determine what's right here. Feel free to commit when you're ready. Thanks for your work on this. Aldy ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH] range-op: Implement floating point multiplication fold_range [PR107569] 2022-11-10 19:20 ` Jakub Jelinek 2022-11-11 2:06 ` Jakub Jelinek 2022-11-11 8:52 ` [PATCH] range-op, v2: " Jakub Jelinek @ 2022-11-11 10:01 ` Aldy Hernandez 2022-11-11 10:47 ` Jakub Jelinek 2 siblings, 1 reply; 12+ messages in thread From: Aldy Hernandez @ 2022-11-11 10:01 UTC (permalink / raw) To: Jakub Jelinek; +Cc: gcc-patches On 11/10/22 20:20, Jakub Jelinek wrote: > On Thu, Nov 10, 2022 at 03:50:47PM +0100, Aldy Hernandez wrote: >>> @@ -1908,6 +1910,123 @@ class foperator_minus : public range_ope >>> } >>> } fop_minus; >>> +/* Wrapper around frange_arithmetics, that computes the result >>> + if inexact rounded to both directions. Also, if one of the >>> + operands is +-0.0 and another +-INF, return +-0.0 rather than >>> + NAN. */ >> >> s/frange_arithmetics/frange_arithmetic/ >> >> Also, would you mind written a little blurb about why it's necessary not to >> compute INF*0.0 as NAN. I assume it's because you're using it for the cross >> product and you'll set maybe_nan separately, but it's nice to spell it out. > > This made me think about it some more and I'll need to play around with it > some more, perhaps the right thing is similarly to what I've attached for > division to handle special cases upfront and call frange_arithmetic only > for the safe cases. > E.g. one case which the posted foperator_mult handles pessimistically is > [0.0, 10.0] * [INF, INF]. This should be just [INF, INF] +-NAN IMHO, > because the 0.0 * INF case will result in NAN, while > nextafter (0.0, 1.0) * INF > will be already INF and everything larger as well. > I could in frange_mult be very conservative and for the 0 * INF cases > set result_lb and result_ub to [0.0, INF] range (corresponding signs > depending on the xor of sign of ops), but that would be quite pessimistic as > well. If one has: > [0.0, 0.0] * [10.0, INF], the result should be just [0.0, 0.0] +-NAN, > because again 0.0 * INF is NAN, but 0.0 * nextafter (INF, 0.0) is already 0.0. > > Note, the is_square case doesn't suffer from all of this mess, the result > is never NAN (unless operand is NAN). > >> It'd be nice to have some testcases. For example, from what I can see, the >> original integer multiplication code came with some tests in >> gcc.dg/tree-ssa/vrp13.c (commit 9983270bec0a18). It'd be nice to have some >> sanity checks, especially because so many things can go wrong with floats. >> >> I'll leave it to you to decide what tests to include. > > I've tried following, but it suffers from various issues: > 1) we don't handle __builtin_signbit (whatever) == 0 (or != 0) as guarantee > that in the guarded code whatever has signbit 0 or 1 We have a range-op entry for __builtin_signbit in cfn_signbit. Is this a shortcoming of this code, or something else? > 2) __builtin_isinf (x) > 0 is lowered to x > DBL_MAX, but unfortunately we don't > infer from that [INF,INF] range, but [DBL_MAX, INF] range > 3) what I wrote above, I think we don't handle [0, 2] * [INF, INF] right but > due to 2) we can't see it Doesn't this boil down to a representation issue? I wonder if we should bite the bullet and tweak build_gt() and build_lt() to represent open ranges. In theory it should be one more/less ULP, while adjusting for HONOR_INFINITIES. If the signbit issue were resolved and we could represent > and < properly, would that allow us to write proper testcases without having to writing a plug-in (which I assume is a lot harder)? Aldy > > So, maybe for now a selftest will be better than a testcase, or > alternatively a plugin test which acts like a selftest. > > /* { dg-do compile { target { ! { vax-*-* powerpc-*-*spe pdp11-*-* } } } } */ > /* { dg-options "-O2 -fno-trapping-math -fno-signaling-nans -fsigned-zeros -fno-tree-fre -fno-tree-dominator-opts -fno-thread-jumps -fdump-tree-optimized" } */ > /* { dg-add-options ieee } */ > > void > foo (double x, double y) > { > const double inf = __builtin_inf (); > const double minf = -inf; > if (__builtin_isnan (x) || __builtin_isnan (y)) > return; > #define TEST(n, xl, xu, yl, yu, rl, ru, nan) \ > if ((__builtin_isinf (xl) > 0 \ > ? x > 0.0 && __builtin_isinf (x) \ > : __builtin_isinf (xu) < 0 \ > ? x < 0.0 && __builtin_isinf (x) \ > : x >= xl && x <= xu \ > && (xl != 0.0 \ > || __builtin_signbit (xl) \ > || !__builtin_signbit (x)) \ > && (xu != 0.0 \ > || !__builtin_signbit (xu) \ > || __builtin_signbit (x))) \ > && (__builtin_isinf (yl) > 0 \ > ? y > 0.0 && __builtin_isinf (y) \ > : __builtin_isinf (yu) < 0 \ > ? y < 0.0 && __builtin_isinf (y) \ > : y >= yl && y <= yu \ > && (yl != 0.0 \ > || __builtin_signbit (yl) \ > || !__builtin_signbit (y)) \ > && (yu != 0.0 \ > || !__builtin_signbit (yu) \ > || __builtin_signbit (y)))) \ > { \ > double r##n = x * y; \ > if (nan == 2) \ > { \ > if (!__builtin_isnan (r##n)) \ > __builtin_abort (); \ > } \ > else if (nan == 1) \ > { \ > if (!__builtin_isnan (r##n)) \ > { \ > if (r##n < rl || r##n > ru) \ > __builtin_abort (); \ > } \ > } \ > else \ > { \ > if (__builtin_isnan (r##n)) \ > __builtin_abort (); \ > if (r##n < rl || r##n > ru) \ > __builtin_abort (); \ > } \ > } > #define TEST2(n, xl, xu, rl, ru) \ > if (__builtin_isinf (xl) > 0 \ > ? x > 0.0 && __builtin_isinf (x) \ > : __builtin_isinf (xu) < 0 \ > ? x < 0.0 && __builtin_isinf (x) \ > : x >= xl && x <= xu \ > && (xl != 0.0 \ > || __builtin_signbit (xl) \ > || !__builtin_signbit (x)) \ > && (xu != 0.0 \ > || !__builtin_signbit (xu) \ > || __builtin_signbit (x))) \ > { \ > double s##n = x * x; \ > if (__builtin_isnan (s##n)) \ > __builtin_abort (); \ > if (s##n < rl || s##n > ru) \ > __builtin_abort (); \ > } > TEST (1, 2.0, 4.0, 6.0, 8.0, 12.0, 32.0, 0); > TEST (2, -2.0, 3.0, -7.0, 4.0, -21.0, 14.0, 0); > TEST (3, -9.0, 5.0, 8.0, 10.0, -90.0, 50.0, 0); > TEST (4, -0.0, 0.0, 16.0, 32.0, -0.0, 0.0, 0); > TEST (5, -0.0, 0.0, 16.0, 32.0, -0.0, 0.0, 0); > TEST (6, 0.0, 0.0, 16.0, 32.0, 0.0, 0.0, 0); > TEST (7, 0.0, 0.0, 16.0, 32.0, 0.0, 0.0, 0); > TEST (8, -0.0, -0.0, 16.0, 32.0, -0.0, -0.0, 0); > TEST (9, -0.0, -0.0, 16.0, 32.0, -0.0, -0.0, 0); > TEST (10, minf, inf, minf, inf, minf, inf, 1); > TEST (11, -0.0, 0.0, 128.0, inf, -0.0, 0.0, 1); > TEST (12, -0.0, 0.0, inf, inf, 0.0, 0.0, 2); > TEST (13, minf, minf, 0.0, 0.0, 0.0, 0.0, 2); > TEST (14, 0.0, 2.0, inf, inf, inf, inf, 1); > TEST (15, 0.0, 2.0, minf, minf, minf, minf, 1); > TEST (16, inf, inf, -0.0, 2.0, minf, inf, 1); > TEST (17, minf, minf, -0.0, 3.0, minf, inf, 1); > > TEST2 (1, 2.0, 4.0, 4.0, 16.0); > TEST2 (2, -0.0, 0.0, -0.0, 0.0); > TEST2 (3, 0.0, inf, 0.0, inf); > TEST2 (4, inf, inf, inf, inf); > } > > > Jakub > ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH] range-op: Implement floating point multiplication fold_range [PR107569] 2022-11-11 10:01 ` [PATCH] range-op: Implement floating point multiplication " Aldy Hernandez @ 2022-11-11 10:47 ` Jakub Jelinek 2022-11-11 10:59 ` Aldy Hernandez 0 siblings, 1 reply; 12+ messages in thread From: Jakub Jelinek @ 2022-11-11 10:47 UTC (permalink / raw) To: Aldy Hernandez; +Cc: gcc-patches On Fri, Nov 11, 2022 at 11:01:38AM +0100, Aldy Hernandez wrote: > > I've tried following, but it suffers from various issues: > > 1) we don't handle __builtin_signbit (whatever) == 0 (or != 0) as guarantee > > that in the guarded code whatever has signbit 0 or 1 > > We have a range-op entry for __builtin_signbit in cfn_signbit. Is this a > shortcoming of this code, or something else? Dunno, I admit I haven't investigated it much. I just saw it when putting a breakpoint on the mult fold_range. > > 2) __builtin_isinf (x) > 0 is lowered to x > DBL_MAX, but unfortunately we don't > > infer from that [INF,INF] range, but [DBL_MAX, INF] range > > 3) what I wrote above, I think we don't handle [0, 2] * [INF, INF] right but > > due to 2) we can't see it > > Doesn't this boil down to a representation issue? I wonder if we should > bite the bullet and tweak build_gt() and build_lt() to represent open > ranges. In theory it should be one more/less ULP, while adjusting for > HONOR_INFINITIES. At least with the exception of MODE_COMPOSITE_P, I think we don't need to introduce open ranges (and who cares about MODE_COMPOSITE_P if it is conservatively correct). For other floats, I think x > cst is always equivalent to x >= nextafter (cst, inf) and x < cst is always equivalent to x <= nextafter (cst, -inf) except for the signed zero cases which needs tiny bit more thought. So, if we have if (x > DBL_MAX) then in code guarded by that we can just use [INF, INF] as range. > If the signbit issue were resolved and we could represent > and < properly, > would that allow us to write proper testcases without having to writing a > plug-in (which I assume is a lot harder)? I don't know, we'd need to see. First work out on all the issues that result on the testcase the operand ranges aren't exactly what we want (whether on the testcase side or on the range-ops side or wherever) and once that looks ok, see if the ranges on the rN/sN vars are correct and if so, watch what hasn't been folded away and why. I think the plugin would be 100-200 lines of code and then we could just write multiple testcases against the plugin. Jakub ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH] range-op: Implement floating point multiplication fold_range [PR107569] 2022-11-11 10:47 ` Jakub Jelinek @ 2022-11-11 10:59 ` Aldy Hernandez 0 siblings, 0 replies; 12+ messages in thread From: Aldy Hernandez @ 2022-11-11 10:59 UTC (permalink / raw) To: Jakub Jelinek; +Cc: gcc-patches On 11/11/22 11:47, Jakub Jelinek wrote: > On Fri, Nov 11, 2022 at 11:01:38AM +0100, Aldy Hernandez wrote: >>> I've tried following, but it suffers from various issues: >>> 1) we don't handle __builtin_signbit (whatever) == 0 (or != 0) as guarantee >>> that in the guarded code whatever has signbit 0 or 1 >> >> We have a range-op entry for __builtin_signbit in cfn_signbit. Is this a >> shortcoming of this code, or something else? > > Dunno, I admit I haven't investigated it much. I just saw it when putting > a breakpoint on the mult fold_range. Could you send me a small testcase. I can look into that. > >>> 2) __builtin_isinf (x) > 0 is lowered to x > DBL_MAX, but unfortunately we don't >>> infer from that [INF,INF] range, but [DBL_MAX, INF] range >>> 3) what I wrote above, I think we don't handle [0, 2] * [INF, INF] right but >>> due to 2) we can't see it >> >> Doesn't this boil down to a representation issue? I wonder if we should >> bite the bullet and tweak build_gt() and build_lt() to represent open >> ranges. In theory it should be one more/less ULP, while adjusting for >> HONOR_INFINITIES. > > At least with the exception of MODE_COMPOSITE_P, I think we don't need > to introduce open ranges (and who cares about MODE_COMPOSITE_P if it is > conservatively correct). > For other floats, I think > x > cst > is always equivalent to > x >= nextafter (cst, inf) > and > x < cst > is always equivalent to > x <= nextafter (cst, -inf) > except for the signed zero cases which needs tiny bit more thought. > So, if we have > if (x > DBL_MAX) > then in code guarded by that we can just use [INF, INF] as range. Yeah, yeah. That's exactly what I meant... using nextafter. I'll look into that, as there seems there's more than one issue related to our lack of precision in representing < and >. > >> If the signbit issue were resolved and we could represent > and < properly, >> would that allow us to write proper testcases without having to writing a >> plug-in (which I assume is a lot harder)? > > I don't know, we'd need to see. > First work out on all the issues that result on the testcase the operand > ranges aren't exactly what we want (whether on the testcase side or on the > range-ops side or wherever) and once that looks ok, see if the ranges > on the rN/sN vars are correct and if so, watch what hasn't been folded away > and why. > I think the plugin would be 100-200 lines of code and then we could just > write multiple testcases against the plugin. If you think the plug-in will get better test coverage, by all means. I was just trying to save you/us some work. Andrew, do you have any thoughts on the plug-in? Aldy ^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2022-11-11 14:27 UTC | newest] Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2022-11-10 13:44 [PATCH] range-op: Implement floating point multiplication fold_range [PR107569] Jakub Jelinek 2022-11-10 14:50 ` Aldy Hernandez 2022-11-10 19:20 ` Jakub Jelinek 2022-11-11 2:06 ` Jakub Jelinek 2022-11-11 8:52 ` [PATCH] range-op, v2: " Jakub Jelinek 2022-11-11 10:01 ` [PATCH] range-op: Cleanup floating point multiplication and division " Jakub Jelinek 2022-11-11 10:12 ` Aldy Hernandez 2022-11-11 10:56 ` Jakub Jelinek 2022-11-11 14:27 ` Aldy Hernandez 2022-11-11 10:01 ` [PATCH] range-op: Implement floating point multiplication " Aldy Hernandez 2022-11-11 10:47 ` Jakub Jelinek 2022-11-11 10:59 ` Aldy Hernandez
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).