From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2136) id 0B3C63986426; Tue, 30 Aug 2022 09:27:53 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 0B3C63986426 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661851673; bh=4l0mbDmhjnz38Xl4DE9L718RIpxnScj3iblyirtm1hM=; h=From:To:Subject:Date:From; b=WjXb1Pfa1zcCI6rjkc0Lq38XKZQM2MDFqpqWwbF5f0ayx/HpTWA6ZOeD0WRhCQTid EJkpODzSbsL/e1mDmkoL3rlMRtIDaoIZoMM+lTZl8lpuqf2Gr3p4YYbLS1zqCoKc0L aA96dE4YPBLYPJdc9dPU2nR0MqjDagrDs6n/MvN8= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Aldy Hernandez To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-2267] Implement relational operators for frange with endpoints. X-Act-Checkin: gcc X-Git-Author: Aldy Hernandez X-Git-Refname: refs/heads/master X-Git-Oldrev: 8bb1df032cc080b751e00c0d7d86c31a630105f9 X-Git-Newrev: 4fbe3e6aa74dae5c75a73c46ae6683fdecd1a75d Message-Id: <20220830092753.0B3C63986426@sourceware.org> Date: Tue, 30 Aug 2022 09:27:53 +0000 (GMT) List-Id: https://gcc.gnu.org/g:4fbe3e6aa74dae5c75a73c46ae6683fdecd1a75d commit r13-2267-g4fbe3e6aa74dae5c75a73c46ae6683fdecd1a75d Author: Aldy Hernandez Date: Tue Aug 30 08:23:51 2022 +0200 Implement relational operators for frange with endpoints. This is the implementation of the relational range operators for frange. These are the core operations that require specific FP domain knowledge. gcc/ChangeLog: * range-op-float.cc (finite_operand_p): New. (build_le): New. (build_lt): New. (build_ge): New. (build_gt): New. (foperator_equal::fold_range): New implementation with endpoints. (foperator_equal::op1_range): Same. (foperator_not_equal::fold_range): Same. (foperator_not_equal::op1_range): Same. (foperator_lt::fold_range): Same. (foperator_lt::op1_range): Same. (foperator_lt::op2_range): Same. (foperator_le::fold_range): Same. (foperator_le::op1_range): Same. (foperator_le::op2_range): Same. (foperator_gt::fold_range): Same. (foperator_gt::op1_range): Same. (foperator_gt::op2_range): Same. (foperator_ge::fold_range): Same. (foperator_ge::op1_range): Same. (foperator_ge::op2_range): Same. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/recip-3.c: Avoid premature optimization so test has a chance to succeed. Diff: --- gcc/range-op-float.cc | 358 +++++++++++++++++++++++++++----- gcc/testsuite/gcc.dg/tree-ssa/recip-3.c | 5 + 2 files changed, 309 insertions(+), 54 deletions(-) diff --git a/gcc/range-op-float.cc b/gcc/range-op-float.cc index ca41136f4cd..d859309f863 100644 --- a/gcc/range-op-float.cc +++ b/gcc/range-op-float.cc @@ -162,6 +162,14 @@ frange_set_nan (frange &r, tree type) r.set (type, rv, rv); } +// Return TRUE if OP1 is known to be free of NANs. + +static inline bool +finite_operand_p (const frange &op1) +{ + return flag_finite_math_only || op1.get_nan ().no_p (); +} + // Return TRUE if OP1 and OP2 are known to be free of NANs. static inline bool @@ -240,6 +248,45 @@ default_frelop_fold_range (irange &r, tree type, return true; } +// (X <= VAL) produces the range of [MIN, VAL]. + +static void +build_le (frange &r, tree type, const REAL_VALUE_TYPE &val) +{ + REAL_VALUE_TYPE min; + real_inf (&min, 1); + r.set (type, min, val); +} + +// (X < VAL) produces the range of [MIN, VAL). + +static void +build_lt (frange &r, tree type, const REAL_VALUE_TYPE &val) +{ + // Hijack LE because we only support closed intervals. + build_le (r, type, val); +} + +// (X >= VAL) produces the range of [VAL, MAX]. + +static void +build_ge (frange &r, tree type, const REAL_VALUE_TYPE &val) +{ + REAL_VALUE_TYPE max; + real_inf (&max, 0); + r.set (type, val, max); +} + +// (X > VAL) produces the range of (VAL, MAX]. + +static void +build_gt (frange &r, tree type, const REAL_VALUE_TYPE &val) +{ + // Hijack GE because we only support closed intervals. + build_ge (r, type, val); +} + + class foperator_identity : public range_operator_float { using range_operator_float::fold_range; @@ -270,10 +317,7 @@ class foperator_equal : public range_operator_float bool fold_range (irange &r, tree type, const frange &op1, const frange &op2, - relation_kind rel) const final override - { - return default_frelop_fold_range (r, type, op1, op2, rel, VREL_EQ); - } + relation_kind rel) const final override; relation_kind op1_op2_relation (const irange &lhs) const final override { return equal_op1_op2_relation (lhs); @@ -289,6 +333,39 @@ class foperator_equal : public range_operator_float } } fop_equal; +bool +foperator_equal::fold_range (irange &r, tree type, + const frange &op1, const frange &op2, + relation_kind rel) const +{ + if (frelop_early_resolve (r, type, op1, op2, rel, VREL_EQ)) + return true; + + // We can be sure the values are always equal or not if both ranges + // consist of a single value, and then compare them. + if (op1.singleton_p () && op2.singleton_p ()) + { + if (op1 == op2) + r = range_true (type); + else + r = range_false (type); + } + else if (finite_operands_p (op1, op2)) + { + // If ranges do not intersect, we know the range is not equal, + // otherwise we don't know anything for sure. + frange tmp = op1; + tmp.intersect (op2); + if (tmp.undefined_p ()) + r = range_false (type); + else + r = range_true_and_false (type); + } + else + r = range_true_and_false (type); + return true; +} + bool foperator_equal::op1_range (frange &r, tree type, const irange &lhs, @@ -309,6 +386,14 @@ foperator_equal::op1_range (frange &r, tree type, // The FALSE side of op1 == op1 implies op1 is a NAN. if (rel == VREL_EQ) frange_set_nan (r, type); + // If the result is false, the only time we know anything is + // if OP2 is a constant. + else if (op2.singleton_p () + || (finite_operand_p (op2) && op2.zero_p ())) + { + REAL_VALUE_TYPE tmp = op2.lower_bound (); + r.set (type, tmp, tmp, VR_ANTI_RANGE); + } break; default: @@ -324,10 +409,7 @@ class foperator_not_equal : public range_operator_float bool fold_range (irange &r, tree type, const frange &op1, const frange &op2, - relation_kind rel) const final override - { - return default_frelop_fold_range (r, type, op1, op2, rel, VREL_NE); - } + relation_kind rel) const final override; relation_kind op1_op2_relation (const irange &lhs) const final override { return not_equal_op1_op2_relation (lhs); @@ -337,6 +419,39 @@ class foperator_not_equal : public range_operator_float relation_kind rel) const final override; } fop_not_equal; +bool +foperator_not_equal::fold_range (irange &r, tree type, + const frange &op1, const frange &op2, + relation_kind rel) const +{ + if (frelop_early_resolve (r, type, op1, op2, rel, VREL_NE)) + return true; + + // We can be sure the values are always equal or not if both ranges + // consist of a single value, and then compare them. + if (op1.singleton_p () && op2.singleton_p ()) + { + if (op1 != op2) + r = range_true (type); + else + r = range_false (type); + } + else if (finite_operands_p (op1, op2)) + { + // If ranges do not intersect, we know the range is not equal, + // otherwise we don't know anything for sure. + frange tmp = op1; + tmp.intersect (op2); + if (tmp.undefined_p ()) + r = range_true (type); + else + r = range_true_and_false (type); + } + else + r = range_true_and_false (type); + return true; +} + bool foperator_not_equal::op1_range (frange &r, tree type, const irange &lhs, @@ -346,11 +461,23 @@ foperator_not_equal::op1_range (frange &r, tree type, switch (get_bool_state (r, lhs, type)) { case BRS_TRUE: - r.set_varying (type); + // If the result is true, the only time we know anything is if + // OP2 is a constant. + if (op2.singleton_p ()) + { + // This is correct even if op1 is NAN, because the following + // range would be ~[tmp, tmp] with the NAN property set to + // maybe (VARYING). + REAL_VALUE_TYPE tmp = op2.lower_bound (); + r.set (type, tmp, tmp, VR_ANTI_RANGE); + } + else + r.set_varying (type); break; case BRS_FALSE: - r.set_varying (type); + // If it's false, the result is the same as OP2. + r = op2; // The FALSE side of op1 != op2 implies op1 is !NAN. r.set_nan (fp_prop::NO); break; @@ -369,10 +496,7 @@ class foperator_lt : public range_operator_float bool fold_range (irange &r, tree type, const frange &op1, const frange &op2, - relation_kind rel) const final override - { - return default_frelop_fold_range (r, type, op1, op2, rel, VREL_LT); - } + relation_kind rel) const final override; relation_kind op1_op2_relation (const irange &lhs) const final override { return lt_op1_op2_relation (lhs); @@ -385,6 +509,31 @@ class foperator_lt : public range_operator_float relation_kind rel) const final override; } fop_lt; +bool +foperator_lt::fold_range (irange &r, tree type, + const frange &op1, const frange &op2, + relation_kind rel) const +{ + if (frelop_early_resolve (r, type, op1, op2, rel, VREL_LT)) + return true; + + if (finite_operands_p (op1, op2)) + { + if (real_less (&op1.upper_bound (), &op2.lower_bound ())) + r = range_true (type); + else if (finite_operands_p (op1, op2) + && !real_less (&op1.lower_bound (), &op2.upper_bound ())) + r = range_false (type); + else + r = range_true_and_false (type); + } + else if (op1.get_nan ().yes_p () || op2.get_nan ().yes_p ()) + r = range_false (type); + else + r = range_true_and_false (type); + return true; +} + bool foperator_lt::op1_range (frange &r, tree type, @@ -395,15 +544,14 @@ foperator_lt::op1_range (frange &r, switch (get_bool_state (r, lhs, type)) { case BRS_TRUE: - r.set_varying (type); - // The TRUE side of op1 < op2 implies op1 is !NAN and !INF. + build_lt (r, type, op2.upper_bound ()); r.set_nan (fp_prop::NO); // x < y implies x is not +INF. frange_drop_inf (r, type); break; case BRS_FALSE: - r.set_varying (type); + build_ge (r, type, op2.lower_bound ()); break; default: @@ -422,15 +570,14 @@ foperator_lt::op2_range (frange &r, switch (get_bool_state (r, lhs, type)) { case BRS_TRUE: - r.set_varying (type); - // The TRUE side of op1 < op2 implies op2 is !NAN and !NINF. + build_gt (r, type, op1.lower_bound ()); r.set_nan (fp_prop::NO); // x < y implies y is not -INF. frange_drop_ninf (r, type); break; case BRS_FALSE: - r.set_varying (type); + build_le (r, type, op1.upper_bound ()); break; default: @@ -447,10 +594,7 @@ class foperator_le : public range_operator_float bool fold_range (irange &r, tree type, const frange &op1, const frange &op2, - relation_kind rel) const final override - { - return default_frelop_fold_range (r, type, op1, op2, rel, VREL_LE); - } + relation_kind rel) const final override; relation_kind op1_op2_relation (const irange &lhs) const final override { return le_op1_op2_relation (lhs); @@ -460,29 +604,74 @@ class foperator_le : public range_operator_float relation_kind rel) const final override; bool op2_range (frange &r, tree type, const irange &lhs, const frange &op1, - relation_kind rel) const final override - { - return op1_range (r, type, lhs, op1, rel); - } + relation_kind rel) const final override; } fop_le; +bool +foperator_le::fold_range (irange &r, tree type, + const frange &op1, const frange &op2, + relation_kind rel) const +{ + if (frelop_early_resolve (r, type, op1, op2, rel, VREL_LE)) + return true; + + if (finite_operands_p (op1, op2)) + { + if (real_compare (LE_EXPR, &op1.upper_bound (), &op2.lower_bound ())) + r = range_true (type); + else if (finite_operands_p (op1, op2) + && !real_compare (LE_EXPR, &op1.lower_bound (), &op2.upper_bound ())) + r = range_false (type); + else + r = range_true_and_false (type); + } + else if (op1.get_nan ().yes_p () || op2.get_nan ().yes_p ()) + r = range_false (type); + else + r = range_true_and_false (type); + return true; +} + bool foperator_le::op1_range (frange &r, tree type, const irange &lhs, - const frange &op2 ATTRIBUTE_UNUSED, + const frange &op2, relation_kind) const { switch (get_bool_state (r, lhs, type)) { case BRS_TRUE: - r.set_varying (type); - // The TRUE side of op1 <= op2 implies op1 is !NAN. + build_le (r, type, op2.upper_bound ()); r.set_nan (fp_prop::NO); break; case BRS_FALSE: - r.set_varying (type); + build_gt (r, type, op2.lower_bound ()); + break; + + default: + break; + } + return true; +} + +bool +foperator_le::op2_range (frange &r, + tree type, + const irange &lhs, + const frange &op1, + relation_kind) const +{ + switch (get_bool_state (r, lhs, type)) + { + case BRS_TRUE: + build_ge (r, type, op1.lower_bound ()); + r.set_nan (fp_prop::NO); + break; + + case BRS_FALSE: + build_lt (r, type, op1.upper_bound ()); break; default: @@ -499,10 +688,7 @@ class foperator_gt : public range_operator_float bool fold_range (irange &r, tree type, const frange &op1, const frange &op2, - relation_kind rel) const final override - { - return default_frelop_fold_range (r, type, op1, op2, rel, VREL_GT); - } + relation_kind rel) const final override; relation_kind op1_op2_relation (const irange &lhs) const final override { return gt_op1_op2_relation (lhs); @@ -515,6 +701,31 @@ class foperator_gt : public range_operator_float relation_kind rel) const final override; } fop_gt; +bool +foperator_gt::fold_range (irange &r, tree type, + const frange &op1, const frange &op2, + relation_kind rel) const +{ + if (frelop_early_resolve (r, type, op1, op2, rel, VREL_GT)) + return true; + + if (finite_operands_p (op1, op2)) + { + if (real_compare (GT_EXPR, &op1.lower_bound (), &op2.upper_bound ())) + r = range_true (type); + else if (finite_operands_p (op1, op2) + && !real_compare (GT_EXPR, &op1.upper_bound (), &op2.lower_bound ())) + r = range_false (type); + else + r = range_true_and_false (type); + } + else if (op1.get_nan ().yes_p () || op2.get_nan ().yes_p ()) + r = range_false (type); + else + r = range_true_and_false (type); + return true; +} + bool foperator_gt::op1_range (frange &r, tree type, @@ -525,15 +736,14 @@ foperator_gt::op1_range (frange &r, switch (get_bool_state (r, lhs, type)) { case BRS_TRUE: - r.set_varying (type); - // The TRUE side of op1 > op2 implies op1 is !NAN and !NINF. + build_gt (r, type, op2.lower_bound ()); r.set_nan (fp_prop::NO); // x > y implies x is not -INF. frange_drop_ninf (r, type); break; case BRS_FALSE: - r.set_varying (type); + build_le (r, type, op2.upper_bound ()); break; default: @@ -552,15 +762,14 @@ foperator_gt::op2_range (frange &r, switch (get_bool_state (r, lhs, type)) { case BRS_TRUE: - r.set_varying (type); - // The TRUE side of op1 > op2 implies op2 is !NAN and !INF. + build_lt (r, type, op1.upper_bound ()); r.set_nan (fp_prop::NO); // x > y implies y is not +INF. frange_drop_inf (r, type); break; case BRS_FALSE: - r.set_varying (type); + build_ge (r, type, op1.lower_bound ()); break; default: @@ -577,10 +786,7 @@ class foperator_ge : public range_operator_float bool fold_range (irange &r, tree type, const frange &op1, const frange &op2, - relation_kind rel) const final override - { - return default_frelop_fold_range (r, type, op1, op2, rel, VREL_GE); - } + relation_kind rel) const final override; relation_kind op1_op2_relation (const irange &lhs) const final override { return ge_op1_op2_relation (lhs); @@ -590,29 +796,73 @@ class foperator_ge : public range_operator_float relation_kind rel) const final override; bool op2_range (frange &r, tree type, const irange &lhs, const frange &op1, - relation_kind rel) const final override - { - return op1_range (r, type, lhs, op1, rel); - } + relation_kind rel) const final override; } fop_ge; +bool +foperator_ge::fold_range (irange &r, tree type, + const frange &op1, const frange &op2, + relation_kind rel) const +{ + if (frelop_early_resolve (r, type, op1, op2, rel, VREL_GE)) + return true; + + if (finite_operands_p (op1, op2)) + { + if (real_compare (GE_EXPR, &op1.lower_bound (), &op2.upper_bound ())) + r = range_true (type); + else if (finite_operands_p (op1, op2) + && !real_compare (GE_EXPR, &op1.upper_bound (), &op2.lower_bound ())) + r = range_false (type); + else + r = range_true_and_false (type); + } + else if (op1.get_nan ().yes_p () || op2.get_nan ().yes_p ()) + r = range_false (type); + else + r = range_true_and_false (type); + return true; +} + bool foperator_ge::op1_range (frange &r, tree type, const irange &lhs, - const frange &op2 ATTRIBUTE_UNUSED, + const frange &op2, relation_kind) const { switch (get_bool_state (r, lhs, type)) { case BRS_TRUE: - r.set_varying (type); - // The TRUE side of op1 >= op2 implies op1 is !NAN. + build_ge (r, type, op2.lower_bound ()); r.set_nan (fp_prop::NO); break; case BRS_FALSE: - r.set_varying (type); + build_lt (r, type, op2.upper_bound ()); + break; + + default: + break; + } + return true; +} + +bool +foperator_ge::op2_range (frange &r, tree type, + const irange &lhs, + const frange &op1, + relation_kind) const +{ + switch (get_bool_state (r, lhs, type)) + { + case BRS_FALSE: + build_gt (r, type, op1.lower_bound ()); + break; + + case BRS_TRUE: + build_le (r, type, op1.upper_bound ()); + r.set_nan (fp_prop::NO); break; default: diff --git a/gcc/testsuite/gcc.dg/tree-ssa/recip-3.c b/gcc/testsuite/gcc.dg/tree-ssa/recip-3.c index 410b28044b4..036f32a9c33 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/recip-3.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/recip-3.c @@ -1,6 +1,11 @@ /* { dg-do compile } */ /* { dg-options "-O1 -fno-trapping-math -funsafe-math-optimizations -fdump-tree-recip" } */ +/* The recip pass has a threshold of 3 reciprocal operations before it attempts + to optimize a sequence. With a FP enabled ranger, we eliminate one of them + earlier, causing the pass to skip this optimization. */ +/* { dg-additional-options "-fno-thread-jumps -fno-tree-dominator-opts" } */ + double F[5] = { 0.0, 0.0 }, e; /* In this case the optimization is interesting. */