From patchwork Tue Aug 23 11:42:25 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 56944 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 8A07A3857C40 for ; Tue, 23 Aug 2022 11:43:49 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8A07A3857C40 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661255029; bh=wAAc8RA53nUVygHOyvbi7N2INYHHH0l9PvU3sRF1LqE=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=Bk/XfHV8yIlK3qsVprYHLtXamNhB7wWkQNTH/83NippNp9Hfax5OiVS5sIky5yvwB VpzgYBwOlNQWiue3MMT5rBO/kWi31JgPMdme1G11i/1bpr2HPqKE7gi8I//yR9Gf2n YnrNEe5mGCnR0QeiDJArkyojWNGC6MpP2xOpzBzk= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id A61B53858C83 for ; Tue, 23 Aug 2022 11:43:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A61B53858C83 Received: from mimecast-mx02.redhat.com (mx3-rdu2.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-302-EH0bpaC_Nha8rfWpKlAi5w-1; Tue, 23 Aug 2022 07:43:16 -0400 X-MC-Unique: EH0bpaC_Nha8rfWpKlAi5w-1 Received: from smtp.corp.redhat.com (int-mx03.intmail.prod.int.rdu2.redhat.com [10.11.54.3]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 035C029DD988 for ; Tue, 23 Aug 2022 11:43:16 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.193.180]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 606681121315; Tue, 23 Aug 2022 11:43:15 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.17.1/8.17.1) with ESMTPS id 27NBhChc905189 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Tue, 23 Aug 2022 13:43:12 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.17.1/8.17.1/Submit) id 27NBhCc5905188; Tue, 23 Aug 2022 13:43:12 +0200 To: GCC patches Subject: [PATCH] Add support for floating point endpoints to frange. Date: Tue, 23 Aug 2022 13:42:25 +0200 Message-Id: <20220823114224.904934-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.78 on 10.11.54.3 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Aldy Hernandez via Gcc-patches From: Aldy Hernandez Reply-To: Aldy Hernandez Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" The current implementation of frange is just a type with some bits to represent NAN and INF. We can do better and represent endpoints to ultimately solve longstanding PRs such as PR24021. This patch adds these endpoints. In follow-up patches I will add support for relational operators using them, as well as a bare bones PLUS_EXPR range-op-float entry to solve the PR. I have chosen to use REAL_VALUE_TYPEs for the endpoints, since that's what we use underneath the trees. This will be somewhat analogous to our eventual use of wide-ints in the irange. No sense going through added levels of indirection if we can avoid it. That, plus real.* already has a nice API for dealing with floats. With this patch, ranges will be closed float point intervals, which make the implementation simpler, since we don't have to keep track of open/closed intervals. This is conservative enough for use in the ranger world, as we'd rather err on the side of more elements in a range, than less. For example, even though we cannot precisely represent the open interval (3.0, 5.0) with this approach, it is perfectably reasonable to represent it as [3.0, 5.0] since the closed interval is a super set of the open one. In the VRP/ranger world, it is always better to err on the side of more information in a range, than not. After all, when we don't know anything about a range, we just use VARYING which is a fancy term for a range spanning the entire domain. Since REAL_VALUE_TYPEs have properly defined infinity and NAN semantics, all the math can be made to work: [-INF, 3.0] !NAN => Numbers <= 3.0 (NAN cannot happen) [3.0, +INF] => Numbers >= 3.0 (NAN is possible) [-INF, +INF] => VARYING (NAN is possible) [-INF, +INF] !NAN => Entire domain. NAN cannot happen. Also, since REAL_VALUE_TYPEs can represent the minimum and maximum representable values of a TYPE_MODE, we can disambiguate between them and negative and positive infinity (see get_max_float in real.cc). This also makes the math all work. For example, suppose we know nothing about x and y (VARYING). On the TRUE side of x > y, we can deduce that: (a) x cannot be NAN (b) y cannot be NAN (c) y cannot be +INF. (c) means that we can drop the upper bound of "y" from +INF to the maximum representable value for its type. Having endpoints with different representation for infinity and the maximum representable values, means we can drop the +-INF properties we currently have in the frange. I will do this as a follow-up patch, as well as contributing more detailed relational operators. I am still tweaking some regressed tests because of the usual premature threading and VRP in the presence of smarter ranges. I figured I'd post now to give others a chance to comment in the meantime. gcc/ChangeLog: * value-range-pretty-print.cc (vrange_printer::visit): Adapt for endpoints. * value-range.cc (frange::set): Same. (frange::normalize_kind): Same. (frange::union_): Same. (frange::intersect): Same. (frange::operator=): Same. (frange::verify_range): Same. (frange::contains_p): New. (frange::singleton_p): New. (frange_float): New. (real_max_representable): New. (real_min_representable): New. (range_tests_floats): New. (range_tests): Call range_tests_floats. * value-range.h (frange::lower_bound): New. (frange::upper_bound): New. (vrp_val_min): Use real_inf with a sign argument. (frange::frange): New. (frange::set_varying): Adapt for endpoints. (frange::set_undefined): Adapt for endpoints. --- gcc/value-range-pretty-print.cc | 12 +- gcc/value-range.cc | 259 ++++++++++++++++++++++++++++++-- gcc/value-range.h | 53 ++++++- 3 files changed, 312 insertions(+), 12 deletions(-) diff --git a/gcc/value-range-pretty-print.cc b/gcc/value-range-pretty-print.cc index cbf50d3d854..1a026c22f99 100644 --- a/gcc/value-range-pretty-print.cc +++ b/gcc/value-range-pretty-print.cc @@ -122,19 +122,29 @@ vrange_printer::print_irange_bitmasks (const irange &r) const void vrange_printer::visit (const frange &r) const { + tree type = r.type (); + pp_string (pp, "[frange] "); if (r.undefined_p ()) { pp_string (pp, "UNDEFINED"); return; } - dump_generic_node (pp, r.type (), 0, TDF_NONE, false); + dump_generic_node (pp, type, 0, TDF_NONE, false); pp_string (pp, " "); if (r.varying_p ()) { pp_string (pp, "VARYING"); return; } + pp_character (pp, '['); + dump_generic_node (pp, + build_real (type, r.lower_bound ()), 0, TDF_NONE, false); + pp_string (pp, ", "); + dump_generic_node (pp, + build_real (type, r.upper_bound ()), 0, TDF_NONE, false); + pp_string (pp, "] "); + print_frange_prop ("NAN", r.get_nan ()); print_frange_prop ("INF", r.get_inf ()); print_frange_prop ("NINF", r.get_ninf ()); diff --git a/gcc/value-range.cc b/gcc/value-range.cc index d056f7356e1..3d81a884192 100644 --- a/gcc/value-range.cc +++ b/gcc/value-range.cc @@ -287,6 +287,8 @@ frange::set (tree min, tree max, value_range_kind kind) m_kind = kind; m_type = TREE_TYPE (min); m_props.set_varying (); + m_min = *TREE_REAL_CST_PTR (min); + m_max = *TREE_REAL_CST_PTR (max); bool is_min = vrp_val_is_min (min); bool is_max = vrp_val_is_max (max); @@ -332,6 +334,16 @@ frange::set (tree min, tree max, value_range_kind kind) verify_range (); } +// Setter for frange from REAL_VALUE_TYPE endpoints. + +void +frange::set (tree type, + const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max, + value_range_kind kind) +{ + set (build_real (type, min), build_real (type, max), kind); +} + // Normalize range to VARYING or UNDEFINED, or vice versa. Return // TRUE if anything changed. // @@ -343,7 +355,9 @@ frange::set (tree min, tree max, value_range_kind kind) bool frange::normalize_kind () { - if (m_kind == VR_RANGE) + if (m_kind == VR_RANGE + && real_isinf (&m_min, 1) + && real_isinf (&m_max, 0)) { // No FP properties set means varying. if (m_props.varying_p ()) @@ -366,6 +380,8 @@ frange::normalize_kind () if (!m_props.varying_p ()) { m_kind = VR_RANGE; + real_inf (&m_min, 1); + real_inf (&m_max, 0); return true; } } @@ -385,12 +401,22 @@ frange::union_ (const vrange &v) return true; } - bool ret = m_props.union_ (r.m_props); - ret |= normalize_kind (); + bool changed = m_props.union_ (r.m_props); + if (real_less (&r.m_min, &m_min)) + { + m_min = r.m_min; + changed = true; + } + if (real_less (&m_max, &r.m_max)) + { + m_max = r.m_max; + changed = true; + } + changed |= normalize_kind (); if (flag_checking) verify_range (); - return ret; + return changed; } bool @@ -411,12 +437,28 @@ frange::intersect (const vrange &v) return true; } - bool ret = m_props.intersect (r.m_props); - ret |= normalize_kind (); + bool changed = m_props.intersect (r.m_props); + if (real_less (&m_min, &r.m_min)) + { + m_min = r.m_min; + changed = true; + } + if (real_less (&r.m_max, &m_max)) + { + m_max = r.m_max; + changed = true; + } + // If the endpoints are swapped, the ranges are disjoint. + if (real_less (&m_max, &m_min)) + { + set_undefined (); + return true; + } + changed |= normalize_kind (); if (flag_checking) verify_range (); - return ret; + return changed; } frange & @@ -424,6 +466,8 @@ frange::operator= (const frange &src) { m_kind = src.m_kind; m_type = src.m_type; + m_min = src.m_min; + m_max = src.m_max; m_props = src.m_props; if (flag_checking) @@ -442,7 +486,44 @@ frange::operator== (const frange &src) const if (varying_p ()) return types_compatible_p (m_type, src.m_type); - return m_props == src.m_props; + return (real_identical (&m_min, &src.m_min) + && real_identical (&m_max, &src.m_max) + && m_props == src.m_props + && types_compatible_p (m_type, src.m_type)); + } + return false; +} + +// Return TRUE if range contains the TREE_REAL_CST_PTR in CST. + +bool +frange::contains_p (tree cst) const +{ + if (undefined_p ()) + return false; + + if (varying_p ()) + return true; + + gcc_checking_assert (m_kind == VR_RANGE); + + return (real_compare (GE_EXPR, TREE_REAL_CST_PTR (cst), &m_min) + && real_compare (LE_EXPR, TREE_REAL_CST_PTR (cst), &m_max)); +} + +// If range is a singleton, place it in RESULT and return TRUE. If +// RESULT is NULL, just return TRUE. + +bool +frange::singleton_p (tree *result) const +{ + if (m_kind == VR_RANGE + && real_identical (&m_min, &m_max) + && !real_isnan (&m_min)) + { + if (result) + *result = build_real (m_type, m_min); + return true; } return false; } @@ -461,13 +542,32 @@ frange::verify_range () gcc_checking_assert (m_props.undefined_p ()); return; } + gcc_checking_assert (!m_props.undefined_p ()); + if (varying_p ()) { gcc_checking_assert (m_props.varying_p ()); return; } + + // We don't support the inverse of an frange (yet). gcc_checking_assert (m_kind == VR_RANGE); - gcc_checking_assert (!m_props.varying_p () && !m_props.undefined_p ()); + + bool is_nan = real_isnan (&m_min) || real_isnan (&m_max); + if (is_nan) + { + // If either is a NAN, both must be a NAN. + gcc_checking_assert (real_identical (&m_min, &m_max)); + gcc_checking_assert (get_nan ().yes_p ()); + } + else + // Make sure we don't have swapped ranges. + gcc_checking_assert (!real_less (&m_max, &m_min)); + + // If all the properties are clear, we better not span the entire + // domain, because that would make us varying. + if (m_props.varying_p ()) + gcc_checking_assert (!real_isinf (&m_min, 1) || !real_isinf (&m_max, 0)); } // Here we copy between any two irange's. The ranges can be legacy or @@ -3300,6 +3400,146 @@ range_tests_nonzero_bits () ASSERT_TRUE (r0.varying_p ()); } +// Build an frange from string endpoints. + +static inline frange +frange_float (const char *lb, const char *ub, tree type = float_type_node) +{ + REAL_VALUE_TYPE min, max; + real_from_string (&min, lb); + real_from_string (&max, ub); + return frange (type, min, max); +} + +// Set R to maximum representable value for TYPE. + +static inline void +real_max_representable (REAL_VALUE_TYPE *r, tree type) +{ + char buf[128]; + get_max_float (REAL_MODE_FORMAT (TYPE_MODE (type)), + buf, sizeof (buf), false); + real_from_string (r, buf); +} + +// Set R to minimum representable value for TYPE. + +static inline void +real_min_representable (REAL_VALUE_TYPE *r, tree type) +{ + real_max_representable (r, type); + real_value_negate (r); +} + +static void +range_tests_floats () +{ + frange r0, r1; + + + // Equal ranges but with differing NAN bits are not equal. + r1 = frange_float ("10", "12"); + r0 = r1; + ASSERT_EQ (r0, r1); + r0.set_nan (fp_prop::NO); + ASSERT_NE (r0, r1); + r0.set_nan (fp_prop::YES); + ASSERT_NE (r0, r1); + r0.set_nan (fp_prop::VARYING); + ASSERT_EQ (r0, r1); + + // A range of [-INF,+INF] is actually VARYING... + r0 = frange_float ("-Inf", "+Inf"); + ASSERT_TRUE (r0.varying_p ()); + // ...unless it has some special property... + r0.set_nan (fp_prop::NO); + ASSERT_FALSE (r0.varying_p ()); + + // The endpoints of a VARYING are +-INF. + REAL_VALUE_TYPE inf, ninf; + real_inf (&inf, 0); + real_inf (&ninf, 1); + r0.set_varying (float_type_node); + ASSERT_TRUE (real_identical (&r0.lower_bound (), &ninf)); + ASSERT_TRUE (real_identical (&r0.upper_bound (), &inf)); + + // The maximum representable range for a type is still a subset of VARYING. + REAL_VALUE_TYPE q, r; + real_min_representable (&q, float_type_node); + real_max_representable (&r, float_type_node); + r0 = frange (float_type_node, q, r); + // r0 is not a varying, because it does not include -INF/+INF. + ASSERT_FALSE (r0.varying_p ()); + // The upper bound of r0 must be less than +INF. + ASSERT_TRUE (real_less (&r0.upper_bound (), &inf)); + // The lower bound of r0 must be greater than -INF. + ASSERT_TRUE (real_less (&ninf, &r0.lower_bound ())); + + // For most architectures, where float and double are different + // sizes, having the same endpoints does not necessarily mean the + // ranges are equal. + if (!types_compatible_p (float_type_node, double_type_node)) + { + r0 = frange_float ("3.0", "3.0", float_type_node); + r1 = frange_float ("3.0", "3.0", double_type_node); + ASSERT_NE (r0, r1); + } + + // [3,5] U [10,12] = [3,12]. + r0 = frange_float ("3", "5"); + r1 = frange_float ("10", "12"); + r0.union_ (r1); + ASSERT_EQ (r0, frange_float ("3", "12")); + + // [5,10] U [4,8] = [4,10] + r0 = frange_float ("5", "10"); + r1 = frange_float ("4", "8"); + r0.union_ (r1); + ASSERT_EQ (r0, frange_float ("4", "10")); + + // [3,5] U [4,10] = [3,10] + r0 = frange_float ("3", "5"); + r1 = frange_float ("4", "10"); + r0.union_ (r1); + ASSERT_EQ (r0, frange_float ("3", "10")); + + // [4,10] U [5,11] = [4,11] + r0 = frange_float ("4", "10"); + r1 = frange_float ("5", "11"); + r0.union_ (r1); + ASSERT_EQ (r0, frange_float ("4", "11")); + + // [3,12] ^ [10,12] = [10,12]. + r0 = frange_float ("3", "12"); + r1 = frange_float ("10", "12"); + r0.intersect (r1); + ASSERT_EQ (r0, frange_float ("10", "12")); + + // [10,12] ^ [11,11] = [11,11] + r0 = frange_float ("10", "12"); + r1 = frange_float ("11", "11"); + r0.intersect (r1); + ASSERT_EQ (r0, frange_float ("11", "11")); + + // [10,20] ^ [5,15] = [10,15] + r0 = frange_float ("10", "20"); + r1 = frange_float ("5", "15"); + r0.intersect (r1); + ASSERT_EQ (r0, frange_float ("10", "15")); + + // [10,20] ^ [15,25] = [15,20] + r0 = frange_float ("10", "20"); + r1 = frange_float ("15", "25"); + r0.intersect (r1); + ASSERT_EQ (r0, frange_float ("15", "20")); + + // [10,20] ^ [21,25] = [] + r0 = frange_float ("10", "20"); + r1 = frange_float ("21", "25"); + r0.intersect (r1); + ASSERT_TRUE (r0.undefined_p ()); +} + void range_tests () { @@ -3308,6 +3548,7 @@ range_tests () range_tests_int_range_max (); range_tests_strict_enum (); range_tests_nonzero_bits (); + range_tests_floats (); range_tests_misc (); } diff --git a/gcc/value-range.h b/gcc/value-range.h index f0075d0fb1a..7be9e84e13a 100644 --- a/gcc/value-range.h +++ b/gcc/value-range.h @@ -345,21 +345,30 @@ class frange : public vrange public: frange (); frange (const frange &); + frange (tree, tree, value_range_kind = VR_RANGE); + frange (tree type, const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max, + value_range_kind = VR_RANGE); static bool supports_p (const_tree type) { return SCALAR_FLOAT_TYPE_P (type); } virtual tree type () const override; virtual void set (tree, tree, value_range_kind = VR_RANGE) override; + void set (tree type, const REAL_VALUE_TYPE &, const REAL_VALUE_TYPE &, + value_range_kind = VR_RANGE); virtual void set_varying (tree type) override; virtual void set_undefined () override; virtual bool union_ (const vrange &) override; virtual bool intersect (const vrange &) override; + virtual bool contains_p (tree) const override; + virtual bool singleton_p (tree *result = NULL) const override; virtual bool supports_type_p (const_tree type) const override; virtual void accept (const vrange_visitor &v) const override; frange& operator= (const frange &); bool operator== (const frange &) const; bool operator!= (const frange &r) const { return !(*this == r); } + const REAL_VALUE_TYPE &lower_bound () const; + const REAL_VALUE_TYPE &upper_bound () const; // Each fp_prop can be accessed with get_PROP() and set_PROP(). FRANGE_PROP_ACCESSOR(nan) @@ -371,8 +380,24 @@ private: frange_props m_props; tree m_type; + REAL_VALUE_TYPE m_min; + REAL_VALUE_TYPE m_max; }; +inline const REAL_VALUE_TYPE & +frange::lower_bound () const +{ + gcc_checking_assert (!undefined_p ()); + return m_min; +} + +inline const REAL_VALUE_TYPE & +frange::upper_bound () const +{ + gcc_checking_assert (!undefined_p ()); + return m_max; +} + // is_a<> and as_a<> implementation for vrange. // Anything we haven't specialized is a hard fail. @@ -1051,8 +1076,8 @@ vrp_val_min (const_tree type) if (frange::supports_p (type)) { REAL_VALUE_TYPE real, real_ninf; - real_inf (&real); - real_ninf = real_value_negate (&real); + real_inf (&real, 0); + real_inf (&real_ninf, 1); return build_real (const_cast (type), real_ninf); } return NULL_TREE; @@ -1096,6 +1121,26 @@ frange::frange (const frange &src) *this = src; } +// frange constructor from REAL_VALUE_TYPE endpoints. + +inline +frange::frange (tree type, + const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max, + value_range_kind kind) +{ + m_discriminator = VR_FRANGE; + set (type, min, max, kind); +} + +// frange constructor from trees. + +inline +frange::frange (tree min, tree max, value_range_kind kind) +{ + m_discriminator = VR_FRANGE; + set (min, max, kind); +} + inline tree frange::type () const { @@ -1107,6 +1152,8 @@ frange::set_varying (tree type) { m_kind = VR_VARYING; m_type = type; + real_inf (&m_min, 1); + real_inf (&m_max, 0); m_props.set_varying (); } @@ -1116,6 +1163,8 @@ frange::set_undefined () m_kind = VR_UNDEFINED; m_type = NULL; m_props.set_undefined (); + memset (&m_min, 0, sizeof (m_min)); + memset (&m_max, 0, sizeof (m_max)); } #endif // GCC_VALUE_RANGE_H