From patchwork Mon Jul 25 06:49:16 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 56295 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 DF22B3857BA2 for ; Mon, 25 Jul 2022 06:50:10 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org DF22B3857BA2 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1658731810; bh=Wc0cFXWPgLBZymiZ9wsJ8kLGEueTG040yWw36W6PJZU=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=K5zMNTJgEjdxHfAP0v4tKBxIzjyN9mUgKR2XZ+LtN3dfi0KWMVQJo8TQYYVsMdPIM 14Rd+GzsyVTDU3FUcv4Ht0g+aE0KUYSmQY3pNuV/y8aH9tT9/yruE7vSXIhe3fXGEp HsIMAWQOTGuMccAAXwziLzTxxQ8VjEcQEJGINNY8= 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 E14423858403 for ; Mon, 25 Jul 2022 06:49:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E14423858403 Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-98-xa_T5RmpPc-PbY7ZLTF4CQ-1; Mon, 25 Jul 2022 02:49:30 -0400 X-MC-Unique: xa_T5RmpPc-PbY7ZLTF4CQ-1 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.rdu2.redhat.com [10.11.54.6]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 069F2101A586; Mon, 25 Jul 2022 06:49:30 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.148]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 664202166B26; Mon, 25 Jul 2022 06:49:29 +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 26P6nQ8q2116914 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Mon, 25 Jul 2022 08:49:26 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.17.1/8.17.1/Submit) id 26P6nQsv2116913; Mon, 25 Jul 2022 08:49:26 +0200 To: GCC patches Subject: [COMMITTED] frange class to represent floating point ranges Date: Mon, 25 Jul 2022 08:49:16 +0200 Message-Id: <20220725064916.2116867-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.78 on 10.11.54.6 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-11.7 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 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 Cc: Jakub Jelinek , roger@eyesopen.com Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" This implements a basic frange class to represent floating point ranges. Although it is meant to be a base for further development, it is enough to handle relations and propagate NAN and other properties. For ranger clients to become floating point aware, we still need the range-op entries, which I will submit later this week. Since those entries require specialized FP knowledge, I will ask for a review from the FP experts before committing. Once range-op entries come live, all ranger clients that have been converted to the type agnostic vrange API will become FP aware: evrp, DOM, the threaders, loop-ch, etc. (Still missing is loop unswitching, as a lot of the int_range* temporaries should be Value_Range. I don't have enough cycles to convert loop unswitching, but could gladly give guidance. It should be straightforward for those familiar with the code ;-)). Samples things we handle: * We can set the FP properties (!NAN, !INF, etc) at assignment from constants (and propagate them throughout the CFG): float z = 0.0; if (__builtin_isnan (z)) link_error (); * The relation oracle works in tandem with the FP ranges: if (x > y) ; else if (!__builtin_isnan (x) && !__builtin_isnan (y)) { // If x and y are not NAN, the x <= y relationship holds, and the // following conditional can be folded away. if (x <= y) bar (); } * We know the true side of all ordered conditionals (except !=) implies !NAN: if (x > y) { if (__builtin_isnan (x) || __builtin_isnan (y)) link_error (); } Range-ops also works correctly with -ffinite-math-only, and avoids checking for NANs, etc. I believe this is enough to get a fully fleshed out floating point support for evrp and friends, but doing so is beyond my limited FP knowledge. For example, frange could be enhanced to track constant endpoints, and we could track other FP properties aside from NAN. Further discussion is gladly welcome. Tested on x86-64 Linux. gcc/ChangeLog: * value-range-pretty-print.cc (vrange_printer::visit): New. (vrange_printer::print_frange_prop): New. * value-range-pretty-print.h (class vrange_printer): Add visit and print_frange_prop. * value-range-storage.h (vrange_allocator::alloc_vrange): Handle frange. (vrange_allocator::alloc_frange): New. * value-range.cc (vrange::operator=): Handle frange. (vrange::operator==): Same. (frange::accept): New. (frange::set): New. (frange::normalize_kind): New. (frange::union_): New. (frange::intersect): New. (frange::operator=): New. (frange::operator==): New. (frange::supports_type_p): New. (frange::verify_range): New. * value-range.h (enum value_range_discriminator): Handle frange. (class fp_prop): New. (FP_PROP_ACCESSOR): New. (class frange_props): New. (FRANGE_PROP_ACCESSOR): New. (class frange): New. (Value_Range::init): Handle frange. (Value_Range::operator=): Same. (Value_Range::supports_type_p): Same. (frange_props::operator==): New. (frange_props::union_): New. (frange_props::intersect): New (frange::frange): New. (frange::type): New. (frange::set_varying): New. (frange::set_undefined): New. --- gcc/value-range-pretty-print.cc | 41 +++++++ gcc/value-range-pretty-print.h | 2 + gcc/value-range-storage.h | 27 ++++- gcc/value-range.cc | 195 +++++++++++++++++++++++++++++++- gcc/value-range.h | 194 ++++++++++++++++++++++++++++++- 5 files changed, 452 insertions(+), 7 deletions(-) diff --git a/gcc/value-range-pretty-print.cc b/gcc/value-range-pretty-print.cc index b795e92d8fb..485612fe67c 100644 --- a/gcc/value-range-pretty-print.cc +++ b/gcc/value-range-pretty-print.cc @@ -109,3 +109,44 @@ vrange_printer::print_irange_bitmasks (const irange &r) const print_hex (nz, buf); pp_string (pp, buf); } + +// Print an frange. + +void +vrange_printer::visit (const frange &r) const +{ + pp_string (pp, "[frange] "); + if (r.undefined_p ()) + { + pp_string (pp, "UNDEFINED"); + return; + } + dump_generic_node (pp, r.type (), 0, TDF_NONE, false); + pp_string (pp, " "); + if (r.varying_p ()) + { + pp_string (pp, "VARYING"); + return; + } + print_frange_prop ("NAN", r.get_nan ()); + print_frange_prop ("INF", r.get_inf ()); + print_frange_prop ("NINF", r.get_ninf ()); +} + +// Print the FP properties in an frange. + +void +vrange_printer::print_frange_prop (const char *str, const fp_prop &prop) const +{ + if (prop.varying_p ()) + return; + + if (prop.yes_p ()) + pp_string (pp, str); + else if (prop.no_p ()) + { + pp_character (pp, '!'); + pp_string (pp, str); + } + pp_character (pp, ' '); +} diff --git a/gcc/value-range-pretty-print.h b/gcc/value-range-pretty-print.h index 6d2fb74cc7a..c1c7c4244cc 100644 --- a/gcc/value-range-pretty-print.h +++ b/gcc/value-range-pretty-print.h @@ -27,9 +27,11 @@ public: vrange_printer (pretty_printer *pp_) : pp (pp_) { } void visit (const unsupported_range &) const override; void visit (const irange &) const override; + void visit (const frange &) const override; private: void print_irange_bound (tree bound) const; void print_irange_bitmasks (const irange &) const; + void print_frange_prop (const char *str, const fp_prop &) const; pretty_printer *pp; }; diff --git a/gcc/value-range-storage.h b/gcc/value-range-storage.h index 7e005e4db56..5a3336b673b 100644 --- a/gcc/value-range-storage.h +++ b/gcc/value-range-storage.h @@ -39,6 +39,7 @@ public: template T *clone (const T &src); private: irange *alloc_irange (unsigned pairs); + frange *alloc_frange (); void operator= (const vrange_allocator &) = delete; }; @@ -142,7 +143,9 @@ vrange_allocator::alloc_vrange (tree type) { if (irange::supports_p (type)) return alloc_irange (2); - + if (frange::supports_p (type)) + return alloc_frange (); + return NULL; gcc_unreachable (); } @@ -164,6 +167,13 @@ vrange_allocator::alloc_irange (unsigned num_pairs) return new (r) irange (mem, num_pairs); } +inline frange * +vrange_allocator::alloc_frange () +{ + void *r = alloc (sizeof (frange)); + return new (r) frange (); +} + // Return a clone of an irange. template <> @@ -175,6 +185,17 @@ vrange_allocator::clone (const irange &src) return r; } +// Return a clone of an frange. + +template <> +inline frange * +vrange_allocator::clone (const frange &src) +{ + frange *r = alloc_frange (); + *r = src; + return r; +} + // Return a clone of a vrange. template <> @@ -183,7 +204,9 @@ vrange_allocator::clone (const vrange &src) { if (is_a (src)) return clone (as_a (src)); - + if (is_a (src)) + return clone (as_a (src)); + return NULL; gcc_unreachable (); } diff --git a/gcc/value-range.cc b/gcc/value-range.cc index 525e1924057..e49b06d1038 100644 --- a/gcc/value-range.cc +++ b/gcc/value-range.cc @@ -195,12 +195,12 @@ vrange & vrange::operator= (const vrange &src) { if (is_a (src)) - { - as_a (*this) = as_a (src); - return *this; - } + as_a (*this) = as_a (src); + else if (is_a (src)) + as_a (*this) = as_a (src); else gcc_unreachable (); + return *this; } // Equality operator for generic ranges. @@ -210,6 +210,8 @@ vrange::operator== (const vrange &src) const { if (is_a (src)) return as_a (*this) == as_a (src); + if (is_a (src)) + return as_a (*this) == as_a (src); gcc_unreachable (); } @@ -252,6 +254,191 @@ unsupported_range::unsupported_range () set_undefined (); } +void +frange::accept (const vrange_visitor &v) const +{ + v.visit (*this); +} + +// Setter for franges. Currently only singletons are supported. + +void +frange::set (tree min, tree max, value_range_kind kind) +{ + gcc_checking_assert (kind == VR_RANGE); + gcc_checking_assert (operand_equal_p (min, max)); + gcc_checking_assert (TREE_CODE (min) == REAL_CST); + + m_kind = kind; + m_type = TREE_TYPE (min); + + REAL_VALUE_TYPE *const cst = TREE_REAL_CST_PTR (min); + if (real_isnan (cst)) + m_props.nan_set_yes (); + else + m_props.nan_set_no (); + + if (real_isinf (cst)) + { + if (real_isneg (cst)) + { + m_props.inf_set_no (); + m_props.ninf_set_yes (); + } + else + { + m_props.inf_set_yes (); + m_props.ninf_set_no (); + } + } + else + { + m_props.inf_set_no (); + m_props.ninf_set_no (); + } + + if (flag_checking) + verify_range (); +} + +// Normalize range to VARYING or UNDEFINED, or vice versa. +// +// A range with no known properties can be dropped to VARYING. +// Similarly, a VARYING with any properties should be dropped to a +// VR_RANGE. Normalizing ranges upon changing them ensures there is +// only one representation for a given range. + +void +frange::normalize_kind () +{ + if (m_kind == VR_RANGE) + { + // No FP properties set means varying. + if (m_props.nan_varying_p () + && m_props.inf_varying_p () + && m_props.ninf_varying_p ()) + { + set_varying (m_type); + return; + } + // Undefined is viral. + if (m_props.nan_undefined_p () + || m_props.inf_undefined_p () + || m_props.ninf_undefined_p ()) + { + set_undefined (); + return; + } + } + else if (m_kind == VR_VARYING) + { + // If a VARYING has any FP properties, it's no longer VARYING. + if (!m_props.nan_varying_p () + || !m_props.inf_varying_p () + || !m_props.ninf_varying_p ()) + m_kind = VR_RANGE; + } +} + +bool +frange::union_ (const vrange &v) +{ + const frange &r = as_a (v); + + if (r.undefined_p () || varying_p ()) + return false; + if (undefined_p () || r.varying_p ()) + { + *this = r; + return true; + } + + bool ret = m_props.union_ (r.m_props); + normalize_kind (); + + if (flag_checking) + verify_range (); + return ret; +} + +bool +frange::intersect (const vrange &v) +{ + const frange &r = as_a (v); + + if (undefined_p () || r.varying_p ()) + return false; + if (r.undefined_p ()) + { + set_undefined (); + return true; + } + if (varying_p ()) + { + *this = r; + return true; + } + + bool ret = m_props.intersect (r.m_props); + normalize_kind (); + + if (flag_checking) + verify_range (); + return ret; +} + +frange & +frange::operator= (const frange &src) +{ + m_kind = src.m_kind; + m_type = src.m_type; + m_props = src.m_props; + + if (flag_checking) + verify_range (); + return *this; +} + +bool +frange::operator== (const frange &src) const +{ + if (m_kind == src.m_kind) + { + if (undefined_p ()) + return true; + + if (varying_p ()) + return types_compatible_p (m_type, src.m_type); + + return m_props == src.m_props; + } + return false; +} + +bool +frange::supports_type_p (tree type) const +{ + return supports_p (type); +} + +void +frange::verify_range () +{ + if (undefined_p ()) + { + gcc_checking_assert (m_props.undefined_p ()); + return; + } + else if (varying_p ()) + { + gcc_checking_assert (m_props.varying_p ()); + return; + } + + gcc_checking_assert (m_kind == VR_RANGE); + gcc_checking_assert (!m_props.varying_p () && !m_props.undefined_p ()); +} + // Here we copy between any two irange's. The ranges can be legacy or // multi-ranges, and copying between any combination works correctly. diff --git a/gcc/value-range.h b/gcc/value-range.h index 4af92fd65d9..e43fbe30f27 100644 --- a/gcc/value-range.h +++ b/gcc/value-range.h @@ -45,6 +45,8 @@ enum value_range_discriminator { // Range holds an integer or pointer. VR_IRANGE, + // Floating point range. + VR_FRANGE, // Range holds an unsupported type. VR_UNKNOWN }; @@ -252,6 +254,117 @@ public: virtual void accept (const vrange_visitor &v) const override; }; +// Floating point property to represent possible values of a NAN, INF, etc. + +class fp_prop +{ +public: + enum kind { + UNDEFINED = 0x0, // Prop is impossible. + YES = 0x1, // Prop is definitely set. + NO = 0x2, // Prop is definitely not set. + VARYING = (YES | NO) // Prop may hold. + }; + fp_prop (kind f) : m_kind (f) { } + bool varying_p () const { return m_kind == VARYING; } + bool undefined_p () const { return m_kind == UNDEFINED; } + bool yes_p () const { return m_kind == YES; } + bool no_p () const { return m_kind == NO; } +private: + unsigned char m_kind : 2; +}; + +// Accessors for individual FP properties. + +#define FP_PROP_ACCESSOR(NAME) \ + void NAME##_set_varying () { u.bits.NAME = fp_prop::VARYING; } \ + void NAME##_set_yes () { u.bits.NAME = fp_prop::YES; } \ + void NAME##_set_no () { u.bits.NAME = fp_prop::NO; } \ + bool NAME##_varying_p () const { return u.bits.NAME == fp_prop::VARYING; } \ + bool NAME##_undefined_p () const { return u.bits.NAME == fp_prop::UNDEFINED; } \ + bool NAME##_yes_p () const { return u.bits.NAME == fp_prop::YES; } \ + bool NAME##_no_p () const { return u.bits.NAME == fp_prop::NO; } \ + fp_prop get_##NAME () const \ + { return fp_prop ((fp_prop::kind) u.bits.NAME); } \ + void set_##NAME (fp_prop::kind f) { u.bits.NAME = f; } + +// Aggregate of all the FP properties in an frange packed into one +// structure to save space. Using explicit fp_prop's in the frange, +// would take one byte per property because of padding. Instead, we +// can save all properties into one byte. + +class frange_props +{ +public: + frange_props () { set_varying (); } + void set_varying () { u.bytes = 0xff; } + void set_undefined () { u.bytes = 0; } + bool varying_p () { return u.bytes == 0xff; } + bool undefined_p () { return u.bytes == 0; } + bool union_ (const frange_props &other); + bool intersect (const frange_props &other); + bool operator== (const frange_props &other) const; + FP_PROP_ACCESSOR(nan) + FP_PROP_ACCESSOR(inf) + FP_PROP_ACCESSOR(ninf) +private: + union { + struct { + unsigned char nan : 2; + unsigned char inf : 2; + unsigned char ninf : 2; + } bits; + unsigned char bytes; + } u; +}; + +// Accessors for getting/setting all FP properties at once. + +#define FRANGE_PROP_ACCESSOR(NAME) \ + fp_prop get_##NAME () const { return m_props.get_##NAME (); } \ + void set_##NAME (fp_prop::kind f) \ + { \ + m_props.set_##NAME (f); \ + normalize_kind (); \ + } + +// A floating point range. + +class frange : public vrange +{ + friend class frange_storage_slot; +public: + frange (); + frange (const frange &); + static bool supports_p (tree type) + { + // Disabled until floating point range-ops come live. + return 0 && SCALAR_FLOAT_TYPE_P (type); + } + virtual tree type () const override; + virtual void set (tree, tree, value_range_kind = VR_RANGE) override; + 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 supports_type_p (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); } + + // Each fp_prop can be accessed with get_PROP() and set_PROP(). + FRANGE_PROP_ACCESSOR(nan) + FRANGE_PROP_ACCESSOR(inf) + FRANGE_PROP_ACCESSOR(ninf) +private: + void verify_range (); + void normalize_kind (); + + frange_props m_props; + tree m_type; +}; + // is_a<> and as_a<> implementation for vrange. // Anything we haven't specialized is a hard fail. @@ -297,10 +410,18 @@ is_a (vrange &v) return v.m_discriminator == VR_IRANGE; } +template <> +inline bool +is_a (vrange &v) +{ + return v.m_discriminator == VR_FRANGE; +} + class vrange_visitor { public: virtual void visit (const irange &) const { } + virtual void visit (const frange &) const { } virtual void visit (const unsupported_range &) const { } }; @@ -360,6 +481,7 @@ private: unsupported_range m_unsupported; vrange *m_vrange; int_range_max m_irange; + frange m_frange; }; inline @@ -401,6 +523,8 @@ Value_Range::init (tree type) if (irange::supports_p (type)) m_vrange = &m_irange; + else if (frange::supports_p (type)) + m_vrange = &m_frange; else m_vrange = &m_unsupported; } @@ -426,6 +550,11 @@ Value_Range::operator= (const vrange &r) m_irange = as_a (r); m_vrange = &m_irange; } + else if (is_a (r)) + { + m_frange = as_a (r); + m_vrange = &m_frange; + } else gcc_unreachable (); @@ -461,7 +590,7 @@ Value_Range::operator const vrange &() const inline bool Value_Range::supports_type_p (tree type) { - return irange::supports_p (type); + return irange::supports_p (type) || frange::supports_p (type); } // Returns true for an old-school value_range as described above. @@ -881,6 +1010,69 @@ irange::normalize_kind () } } + +// Supporting methods for frange. + +inline bool +frange_props::operator== (const frange_props &other) const +{ + return u.bytes == other.u.bytes; +} + +inline bool +frange_props::union_ (const frange_props &other) +{ + unsigned char saved = u.bytes; + u.bytes |= other.u.bytes; + return u.bytes != saved; +} + +inline bool +frange_props::intersect (const frange_props &other) +{ + unsigned char saved = u.bytes; + u.bytes &= other.u.bytes; + return u.bytes != saved; +} + +inline +frange::frange () +{ + m_discriminator = VR_FRANGE; + m_type = nullptr; + set_undefined (); +} + +inline +frange::frange (const frange &src) +{ + m_discriminator = VR_FRANGE; + *this = src; +} + +inline tree +frange::type () const +{ + return m_type; +} + +inline void +frange::set_varying (tree type) +{ + m_kind = VR_VARYING; + m_type = type; + m_props.set_varying (); +} + +inline void +frange::set_undefined () +{ + m_kind = VR_UNDEFINED; + m_type = NULL; + m_props.set_undefined (); +} + + // Return the maximum value for TYPE. inline tree