| Message ID | mptpmuzg5ew.fsf@arm.com |
|---|---|
| State | New |
| Headers | show |
| Series | Add a simple fraction class | expand |
On Fri, Jul 30, 2021 at 5:59 PM Richard Sandiford via Gcc-patches <gcc-patches@gcc.gnu.org> wrote: > > This patch adds a simple class for holding A/B fractions. > As the comments in the patch say, the class isn't designed > to have nice numerial properties at the extremes. > > The motivating use case was some aarch64 costing work, > where being able to represent fractions was much easier > than using single integers and avoided the rounding errors > that would come with using floats. (Unlike things like > COSTS_N_INSNS, there was no sensible constant base factor > that could be used.) > > Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install? Hmm, we use the sreal type for profiles. I don't see any overflow/underflow handling in your class - I suppose you're going to use it on integer types given we're not allowed to use native FP? I mean, how exactly does the class solve the problem of rounding errors? Thanks, Richard. > Thanks, > Richard > > > gcc/ > * simple-fraction.h: New file. > * simple-fraction.cc: Likewise. > * Makefile.in (OBJS): Add simple-fraction.o. > * selftest.h (simple_fraction_cc_tests): Declare. > * selftest-run-tests.c (selftest::run_tests): Call it. > --- > gcc/Makefile.in | 1 + > gcc/selftest-run-tests.c | 1 + > gcc/selftest.h | 1 + > gcc/simple-fraction.cc | 160 ++++++++++++++++++++ > gcc/simple-fraction.h | 308 +++++++++++++++++++++++++++++++++++++++ > 5 files changed, 471 insertions(+) > create mode 100644 gcc/simple-fraction.cc > create mode 100644 gcc/simple-fraction.h > > diff --git a/gcc/Makefile.in b/gcc/Makefile.in > index 1666ef84d6a..8eaaab84143 100644 > --- a/gcc/Makefile.in > +++ b/gcc/Makefile.in > @@ -1572,6 +1572,7 @@ OBJS = \ > selftest-run-tests.o \ > sese.o \ > shrink-wrap.o \ > + simple-fraction.o \ > simplify-rtx.o \ > sparseset.o \ > spellcheck.o \ > diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c > index 1b5583e476a..f17d4e24884 100644 > --- a/gcc/selftest-run-tests.c > +++ b/gcc/selftest-run-tests.c > @@ -80,6 +80,7 @@ selftest::run_tests () > opt_problem_cc_tests (); > ordered_hash_map_tests_cc_tests (); > splay_tree_cc_tests (); > + simple_fraction_cc_tests (); > > /* Mid-level data structures. */ > input_c_tests (); > diff --git a/gcc/selftest.h b/gcc/selftest.h > index 80459d63a39..716ba41f6bf 100644 > --- a/gcc/selftest.h > +++ b/gcc/selftest.h > @@ -254,6 +254,7 @@ extern void read_rtl_function_c_tests (); > extern void rtl_tests_c_tests (); > extern void sbitmap_c_tests (); > extern void selftest_c_tests (); > +extern void simple_fraction_cc_tests (); > extern void simplify_rtx_c_tests (); > extern void spellcheck_c_tests (); > extern void spellcheck_tree_c_tests (); > diff --git a/gcc/simple-fraction.h b/gcc/simple-fraction.h > new file mode 100644 > index 00000000000..8d3ff2bdd2d > --- /dev/null > +++ b/gcc/simple-fraction.h > @@ -0,0 +1,308 @@ > +// Simple fraction utilities > +// Copyright (C) 2021 Free Software Foundation, Inc. > +// > +// This file is part of GCC. > +// > +// GCC is free software; you can redistribute it and/or modify it under > +// the terms of the GNU General Public License as published by the Free > +// Software Foundation; either version 3, or (at your option) any later > +// version. > +// > +// GCC is distributed in the hope that it will be useful, but WITHOUT ANY > +// WARRANTY; without even the implied warranty of MERCHANTABILITY or > +// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License > +// for more details. > +// > +// You should have received a copy of the GNU General Public License > +// along with GCC; see the file COPYING3. If not see > +// <http://www.gnu.org/licenses/>. > + > +// A simple fraction with nominator and denominator of integral type T. > +// There is little attempt to handle multiplication overflow, so the class > +// shouldn't be used in cases where that's a risk. It also doesn't cope > +// gracefully with the minimum T value, if T is signed. > +template <typename T> > +class simple_fraction > +{ > +public: > + // Construct a fraction equal to NOMINATOR. > + template<typename T1> > + constexpr simple_fraction (T1 nominator = 0) > + : m_nominator (nominator), m_denominator (1) {} > + > + // Construct a fraction equal to NOMINATOR / DENOMINATOR (simplifying > + // where possible). > + template<typename T1, typename T2> > + simple_fraction (T1 nominator, T2 denominator) > + : simple_fraction (nominator, denominator, gcd (nominator, denominator)) {} > + > + simple_fraction operator- () const; > + simple_fraction operator+ (const simple_fraction &) const; > + simple_fraction operator- (const simple_fraction &) const; > + simple_fraction operator* (const simple_fraction &) const; > + simple_fraction operator/ (const simple_fraction &) const; > + > + simple_fraction &operator+= (const simple_fraction &); > + simple_fraction &operator-= (const simple_fraction &); > + simple_fraction &operator*= (const simple_fraction &); > + simple_fraction &operator/= (const simple_fraction &); > + > + bool operator== (const simple_fraction &) const; > + bool operator!= (const simple_fraction &) const; > + bool operator< (const simple_fraction &) const; > + bool operator<= (const simple_fraction &) const; > + bool operator>= (const simple_fraction &) const; > + bool operator> (const simple_fraction &) const; > + > + explicit operator bool () const { return m_nominator != 0; } > + > + T floor () const; > + T ceil () const; > + > + // Convert the value to a double. > + double as_double () const { return double (m_nominator) / m_denominator; } > + > + T nominator () const { return m_nominator; } > + T denominator () const { return m_denominator; } > + > +private: > + simple_fraction (T, T, T); > + > + T m_nominator, m_denominator; > +}; > + > +template<typename T> > +simple_fraction<T>::simple_fraction (T nominator, T denominator, T factor) > + // Canonicalize the components by dividing each one by FACTOR. > + : m_nominator (nominator / factor), > + m_denominator (nominator ? denominator / factor : 1) > +{ > + if (T (0) - 1 < T (0) && m_denominator < 0) > + { > + m_nominator = -m_nominator; > + m_denominator = -m_denominator; > + } > +} > + > +template<typename T> > +simple_fraction<T> > +simple_fraction<T>::operator- () const > +{ > + return { -m_nominator, m_denominator, 1 }; > +} > + > +template<typename T> > +simple_fraction<T> > +simple_fraction<T>::operator+ (const simple_fraction &other) const > +{ > + if (m_denominator == other.m_denominator) > + return { m_nominator + other.m_nominator, m_denominator }; > + > + T factor = gcd (m_denominator, other.m_denominator); > + T new_nominator = (m_nominator * (other.m_denominator / factor) > + + other.m_nominator * (m_denominator / factor)); > + T new_denominator = m_denominator * (other.m_denominator / factor); > + return { new_nominator, new_denominator }; > +} > + > +template<typename T> > +simple_fraction<T> & > +simple_fraction<T>::operator+= (const simple_fraction &other) > +{ > + *this = *this + other; > + return *this; > +} > + > +template<typename T> > +simple_fraction<T> > +simple_fraction<T>::operator- (const simple_fraction &other) const > +{ > + if (m_denominator == other.m_denominator) > + return { m_nominator - other.m_nominator, m_denominator }; > + > + T factor = gcd (m_denominator, other.m_denominator); > + T new_nominator = (m_nominator * (other.m_denominator / factor) > + - other.m_nominator * (m_denominator / factor)); > + T new_denominator = m_denominator * (other.m_denominator / factor); > + return { new_nominator, new_denominator }; > +} > + > +template<typename T> > +simple_fraction<T> & > +simple_fraction<T>::operator-= (const simple_fraction &other) > +{ > + *this = *this - other; > + return *this; > +} > + > +template<typename T> > +simple_fraction<T> > +simple_fraction<T>::operator* (const simple_fraction &other) const > +{ > + return { m_nominator * other.m_nominator, > + m_denominator * other.m_denominator }; > +} > + > +template<typename T> > +simple_fraction<T> & > +simple_fraction<T>::operator*= (const simple_fraction &other) > +{ > + *this = *this * other; > + return *this; > +} > + > +template<typename T> > +simple_fraction<T> > +simple_fraction<T>::operator/ (const simple_fraction &other) const > +{ > + return { m_nominator * other.m_denominator, > + m_denominator * other.m_nominator }; > +} > + > +template<typename T> > +simple_fraction<T> & > +simple_fraction<T>::operator/= (const simple_fraction &other) > +{ > + *this = *this / other; > + return *this; > +} > + > +template<typename T> > +bool > +simple_fraction<T>::operator== (const simple_fraction &other) const > +{ > + return (m_nominator == other.m_nominator > + && m_denominator == other.m_denominator); > +} > + > +template<typename T> > +bool > +simple_fraction<T>::operator!= (const simple_fraction &other) const > +{ > + return !operator== (other); > +} > + > +template<typename T> > +bool > +simple_fraction<T>::operator< (const simple_fraction<T> &other) const > +{ > + if (m_denominator == other.m_denominator) > + return m_nominator < other.m_nominator; > + > + T factor = gcd (m_denominator, other.m_denominator); > + return (m_nominator * (other.m_denominator / factor) > + < other.m_nominator * (m_denominator / factor)); > +} > + > +template<typename T> > +bool > +simple_fraction<T>::operator<= (const simple_fraction<T> &other) const > +{ > + return !other.operator< (*this); > +} > + > +template<typename T> > +bool > +simple_fraction<T>::operator>= (const simple_fraction<T> &other) const > +{ > + return !operator< (other); > +} > + > +template<typename T> > +bool > +simple_fraction<T>::operator> (const simple_fraction<T> &other) const > +{ > + return other.operator< (*this); > +} > + > +template<typename T1, typename T2> > +auto > +operator+ (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator+ (a)) > +{ > + return b.operator+ (a); > +} > + > +template<typename T1, typename T2> > +auto > +operator- (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator- (a)) > +{ > + return simple_fraction<T2> (a).operator- (b); > +} > + > +template<typename T1, typename T2> > +auto > +operator* (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator* (a)) > +{ > + return b.operator* (a); > +} > + > +template<typename T1, typename T2> > +auto > +operator/ (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator/ (a)) > +{ > + return simple_fraction<T2> (a).operator/ (b); > +} > + > +template<typename T1, typename T2> > +auto > +operator== (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator== (a)) > +{ > + return b.operator== (a); > +} > + > +template<typename T1, typename T2> > +auto > +operator!= (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator!= (a)) > +{ > + return b.operator!= (a); > +} > + > +template<typename T1, typename T2> > +auto > +operator< (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator>= (a)) > +{ > + return b.operator> (a); > +} > + > +template<typename T1, typename T2> > +auto > +operator<= (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator> (a)) > +{ > + return b.operator>= (a); > +} > + > +template<typename T1, typename T2> > +auto > +operator>= (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator< (a)) > +{ > + return b.operator<= (a); > +} > + > +template<typename T1, typename T2> > +auto > +operator> (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator<= (a)) > +{ > + return b.operator< (a); > +} > + > +// Round towards -Inf and return the result as an integer. > +template<typename T> > +T > +simple_fraction<T>::floor () const > +{ > + if (T (0) - 1 < T (0) && m_nominator < T (0)) > + return -CEIL (-m_nominator, m_denominator); > + else > + return m_nominator / m_denominator; > +} > + > +// Round towards +Inf and return the result as an integer. > +template<typename T> > +T > +simple_fraction<T>::ceil () const > +{ > + if (T (0) - 1 < T (0) && m_nominator < T (0)) > + return -(-m_nominator / m_denominator); > + else > + return CEIL (m_nominator, m_denominator); > +} > diff --git a/gcc/simple-fraction.cc b/gcc/simple-fraction.cc > new file mode 100644 > index 00000000000..01c736be9d9 > --- /dev/null > +++ b/gcc/simple-fraction.cc > @@ -0,0 +1,160 @@ > +// Simple fraction utilities > +// Copyright (C) 2021 Free Software Foundation, Inc. > +// > +// This file is part of GCC. > +// > +// GCC is free software; you can redistribute it and/or modify it under > +// the terms of the GNU General Public License as published by the Free > +// Software Foundation; either version 3, or (at your option) any later > +// version. > +// > +// GCC is distributed in the hope that it will be useful, but WITHOUT ANY > +// WARRANTY; without even the implied warranty of MERCHANTABILITY or > +// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License > +// for more details. > +// > +// You should have received a copy of the GNU General Public License > +// along with GCC; see the file COPYING3. If not see > +// <http://www.gnu.org/licenses/>. > + > +#define INCLUDE_ALGORITHM > +#define INCLUDE_ARRAY > +#include "config.h" > +#include "system.h" > +#include "coretypes.h" > +#include "simple-fraction.h" > +#include "selftest.h" > + > +#if CHECKING_P > +namespace selftest { > + > +// Run all tests for this module. > +void > +simple_fraction_cc_tests () > +{ > + using intf = simple_fraction<int>; > + > + ASSERT_EQ (intf (0, 100), 0); > + > + ASSERT_EQ (intf (4, 2), 2); > + ASSERT_EQ (intf (-4, 2), -2); > + ASSERT_EQ (3, intf (9, 3)); > + ASSERT_EQ (-3, intf (9, -3)); > + ASSERT_EQ (intf (-1, 4), intf (1, -4)); > + ASSERT_EQ (intf (-1, -4), intf (1, 4)); > + ASSERT_EQ (intf (-2, -8), intf (1, 4)); > + > + ASSERT_NE (intf (5, 2), 2); > + ASSERT_NE (intf (-4, 2), 2); > + ASSERT_NE (3, intf (8, 3)); > + ASSERT_NE (-3, intf (9, 3)); > + ASSERT_NE (intf (-1, -4), intf (-1, 4)); > + > + ASSERT_EQ (-intf (0), 0); > + ASSERT_EQ (-intf (-1, 4), intf (1, 4)); > + ASSERT_EQ (-intf (1, 4), intf (-1, 4)); > + > + ASSERT_EQ (intf (7, 11) + intf (15, 11), 2); > + ASSERT_EQ (intf (2, 3) + intf (3, 5), intf (19, 15)); > + ASSERT_EQ (intf (2, 3) + intf (1, 6) + intf (1, 6), 1); > + ASSERT_EQ (intf (1, 0x10000) + intf (7, 0x20000), intf (9, 0x20000)); > + ASSERT_EQ (intf (1, 0x10000) + 10, intf (0xa0001, 0x10000)); > + ASSERT_EQ (10 + intf (1, 0x10000), intf (0xa0001, 0x10000)); > + > + ASSERT_EQ (intf (14, 15) - intf (4, 15), intf (2, 3)); > + ASSERT_EQ (intf (1, 4) - intf (1, 2), intf (-1, 4)); > + ASSERT_EQ (intf (3, 5) - intf (1, 10), intf (1, 2)); > + ASSERT_EQ (intf (11, 3) - 3, intf (2, 3)); > + ASSERT_EQ (3 - intf (7, 3), intf (2, 3)); > + > + ASSERT_EQ (intf (2, 3) * intf (3, 5), intf (2, 5)); > + ASSERT_EQ (intf (-2, 9) * intf (3, 5), intf (-2, 15)); > + ASSERT_EQ (intf (2, 3) * intf (-1, 6), intf (-1, 9)); > + ASSERT_EQ (intf (-2, 5) * intf (-3, 7), intf (6, 35)); > + ASSERT_EQ (intf (5, 6) * 3, intf (5, 2)); > + ASSERT_EQ (14 * intf (11, 21), intf (22, 3)); > + > + ASSERT_EQ (intf (2, 3) / intf (3, 5), intf (10, 9)); > + ASSERT_EQ (intf (3, 14) / intf (-1, 2), intf (-3, 7)); > + ASSERT_EQ (intf (-13, 17) / intf (3, 2), intf (-26, 51)); > + ASSERT_EQ (intf (-7, 9) / intf (-4, 3), intf (7, 12)); > + > + ASSERT_TRUE (intf (4, 15) < intf (5, 15)); > + ASSERT_FALSE (intf (5, 15) < intf (5, 15)); > + ASSERT_FALSE (intf (6, 15) < intf (5, 15)); > + ASSERT_TRUE (intf (1, 3) < intf (2, 5)); > + ASSERT_TRUE (intf (-1, 6) < intf (1, 12)); > + ASSERT_FALSE (intf (5, 3) < intf (5, 3)); > + ASSERT_FALSE (intf (7, 11) < intf (13, 22)); > + ASSERT_TRUE (intf (7, 11) < intf (15, 22)); > + ASSERT_TRUE (intf (100, 101) < 1); > + ASSERT_FALSE (intf (101, 101) < 1); > + ASSERT_FALSE (intf (102, 101) < 1); > + ASSERT_FALSE (2 < intf (99, 50)); > + ASSERT_FALSE (2 < intf (100, 50)); > + ASSERT_TRUE (2 < intf (101, 50)); > + > + ASSERT_TRUE (intf (4, 15) <= intf (5, 15)); > + ASSERT_TRUE (intf (5, 15) <= intf (5, 15)); > + ASSERT_FALSE (intf (6, 15) <= intf (5, 15)); > + ASSERT_TRUE (intf (1, 3) <= intf (2, 5)); > + ASSERT_TRUE (intf (-1, 6) <= intf (1, 12)); > + ASSERT_TRUE (intf (5, 3) <= intf (5, 3)); > + ASSERT_FALSE (intf (7, 11) <= intf (13, 22)); > + ASSERT_TRUE (intf (7, 11) <= intf (15, 22)); > + ASSERT_TRUE (intf (100, 101) <= 1); > + ASSERT_TRUE (intf (101) / 101 <= 1); > + ASSERT_FALSE (intf (102, 101) <= 1); > + ASSERT_FALSE (2 <= intf (99, 50)); > + ASSERT_TRUE (2 <= intf (100, 50)); > + ASSERT_TRUE (2 <= intf (101, 50)); > + > + ASSERT_FALSE (intf (4, 15) >= intf (5, 15)); > + ASSERT_TRUE (intf (5, 15) >= intf (5, 15)); > + ASSERT_TRUE (intf (6, 15) >= intf (5, 15)); > + ASSERT_FALSE (intf (1, 3) >= intf (2, 5)); > + ASSERT_FALSE (intf (-1, 6) >= intf (1, 12)); > + ASSERT_TRUE (intf (5, 3) >= intf (5, 3)); > + ASSERT_TRUE (intf (7, 11) >= intf (13, 22)); > + ASSERT_FALSE (intf (7, 11) >= intf (15, 22)); > + ASSERT_FALSE (intf (100, 101) >= 1); > + ASSERT_TRUE (intf (101, 101) >= 1); > + ASSERT_TRUE (intf (102, 101) >= 1); > + ASSERT_TRUE (2 >= intf (99, 50)); > + ASSERT_TRUE (2 >= intf (100, 50)); > + ASSERT_FALSE (2 >= intf (101, 50)); > + > + ASSERT_FALSE (intf (4, 15) > intf (5, 15)); > + ASSERT_FALSE (intf (5, 15) > intf (5, 15)); > + ASSERT_TRUE (intf (6, 15) > intf (5, 15)); > + ASSERT_FALSE (intf (1, 3) > intf (2, 5)); > + ASSERT_FALSE (intf (-1, 6) > intf (1, 12)); > + ASSERT_FALSE (intf (5, 3) > intf (5, 3)); > + ASSERT_TRUE (intf (7, 11) > intf (13, 22)); > + ASSERT_FALSE (intf (7, 11) > intf (15, 22)); > + ASSERT_FALSE (intf (100, 101) > 1); > + ASSERT_FALSE (intf (101) / 101 > 1); > + ASSERT_TRUE (intf (102, 101) > 1); > + ASSERT_TRUE (2 > intf (99, 50)); > + ASSERT_FALSE (2 > intf (100, 50)); > + ASSERT_FALSE (2 > intf (101, 50)); > + > + ASSERT_EQ (intf (1, 2).floor (), 0); > + ASSERT_EQ (intf (11, 7).floor (), 1); > + ASSERT_EQ (intf (20, 1).floor (), 20); > + ASSERT_EQ (intf (-1, 2).floor (), -1); > + ASSERT_EQ (intf (-11, 7).floor (), -2); > + ASSERT_EQ (intf (-20, 1).floor (), -20); > + > + ASSERT_EQ (intf (1, 2).ceil (), 1); > + ASSERT_EQ (intf (11, 7).ceil (), 2); > + ASSERT_EQ (intf (20, 1).ceil (), 20); > + ASSERT_EQ (intf (-1, 2).ceil (), 0); > + ASSERT_EQ (intf (-11, 7).ceil (), -1); > + ASSERT_EQ (intf (-20, 1).ceil (), -20); > + > + ASSERT_EQ (intf (1, 2).as_double (), 0.5); > + ASSERT_EQ (intf (-5, 4).as_double (), -1.25); > +} > +} > +#endif // CHECKING_P
Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> writes: > On Fri, Jul 30, 2021 at 5:59 PM Richard Sandiford via Gcc-patches > <gcc-patches@gcc.gnu.org> wrote: >> >> This patch adds a simple class for holding A/B fractions. >> As the comments in the patch say, the class isn't designed >> to have nice numerial properties at the extremes. >> >> The motivating use case was some aarch64 costing work, >> where being able to represent fractions was much easier >> than using single integers and avoided the rounding errors >> that would come with using floats. (Unlike things like >> COSTS_N_INSNS, there was no sensible constant base factor >> that could be used.) >> >> Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install? > > Hmm, we use the sreal type for profiles. I don't see any overflow/underflow > handling in your class - I suppose you're going to use it on integer types > given we're not allowed to use native FP? Yeah, I'm going to use it on integer types. And it's not designed to have nice properties at extremes, including handling underflow and overflow. I want to use it in costing code, where we already happily multiply and add “int”-sized costs without worrying about overflow. I'll be using uint64_t for the fractions though, just in case. :-) sreal doesn't help because it's still significand/exponent. That matters because… > I mean, how exactly does > the class solve the problem of rounding errors? …I wanted something that represented the results exactly (barring any of integer ops overflowing). This makes it meaningful to compare costs for equality. It also means we can use ordered comparisons without having to introduce a fudge factor to cope with one calculation having different intermediate rounding from the other. E.g. aarch64 has code like: if (scalar_cycles_per_iter < sve_estimate) { unsigned int min_cost = orig_body_cost * estimated_poly_value (BYTES_PER_SVE_VECTOR); if (body_cost < min_cost) { if (dump_enabled_p ()) dump_printf_loc (MSG_NOTE, vect_location, "Increasing body cost to %d because the" " scalar code could issue within the limit" " imposed by predicate operations\n", min_cost); body_cost = min_cost; should_disparage = true; } } I want to be able to keep this while making scalar_cycles_per_iter and sve_estimate non-integral. Thanks, Richard
On Mon, Aug 2, 2021 at 12:43 PM Richard Sandiford <richard.sandiford@arm.com> wrote: > > Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> writes: > > On Fri, Jul 30, 2021 at 5:59 PM Richard Sandiford via Gcc-patches > > <gcc-patches@gcc.gnu.org> wrote: > >> > >> This patch adds a simple class for holding A/B fractions. > >> As the comments in the patch say, the class isn't designed > >> to have nice numerial properties at the extremes. > >> > >> The motivating use case was some aarch64 costing work, > >> where being able to represent fractions was much easier > >> than using single integers and avoided the rounding errors > >> that would come with using floats. (Unlike things like > >> COSTS_N_INSNS, there was no sensible constant base factor > >> that could be used.) > >> > >> Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install? > > > > Hmm, we use the sreal type for profiles. I don't see any overflow/underflow > > handling in your class - I suppose you're going to use it on integer types > > given we're not allowed to use native FP? > > Yeah, I'm going to use it on integer types. And it's not designed > to have nice properties at extremes, including handling underflow and > overflow. So maybe assert that it doesn't? In particular nominator/denominator are prone to overflowing in fractional representations. There's the option to round or ICE. Or rather than the only option is to round (or use a more expensive arbitrary precision representation). So the question is whether the fractional behavior is better in more cases than the sreal behavior (I can easily believe it is). > I want to use it in costing code, where we already happily multiply > and add “int”-sized costs without worrying about overflow. I'll be > using uint64_t for the fractions though, just in case. :-) > > sreal doesn't help because it's still significand/exponent. That matters > because… > > > I mean, how exactly does > > the class solve the problem of rounding errors? > > …I wanted something that represented the results exactly (barring any of > integer ops overflowing). This makes it meaningful to compare costs for > equality. It also means we can use ordered comparisons without having > to introduce a fudge factor to cope with one calculation having different > intermediate rounding from the other. I think you're underestimating how quickly your denominator will overflow? So I suppose all factors of all possible denominators are known, in fact whats your main source for the divisions? The VF? > E.g. aarch64 has code like: > > if (scalar_cycles_per_iter < sve_estimate) > { > unsigned int min_cost > = orig_body_cost * estimated_poly_value (BYTES_PER_SVE_VECTOR); > if (body_cost < min_cost) > { > if (dump_enabled_p ()) > dump_printf_loc (MSG_NOTE, vect_location, > "Increasing body cost to %d because the" > " scalar code could issue within the limit" > " imposed by predicate operations\n", > min_cost); > body_cost = min_cost; > should_disparage = true; > } > } > > I want to be able to keep this while making scalar_cycles_per_iter and > sve_estimate non-integral. > > Thanks, > Richard
Richard Biener <richard.guenther@gmail.com> writes: > On Mon, Aug 2, 2021 at 12:43 PM Richard Sandiford > <richard.sandiford@arm.com> wrote: >> >> Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> writes: >> > On Fri, Jul 30, 2021 at 5:59 PM Richard Sandiford via Gcc-patches >> > <gcc-patches@gcc.gnu.org> wrote: >> >> >> >> This patch adds a simple class for holding A/B fractions. >> >> As the comments in the patch say, the class isn't designed >> >> to have nice numerial properties at the extremes. >> >> >> >> The motivating use case was some aarch64 costing work, >> >> where being able to represent fractions was much easier >> >> than using single integers and avoided the rounding errors >> >> that would come with using floats. (Unlike things like >> >> COSTS_N_INSNS, there was no sensible constant base factor >> >> that could be used.) >> >> >> >> Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install? >> > >> > Hmm, we use the sreal type for profiles. I don't see any overflow/underflow >> > handling in your class - I suppose you're going to use it on integer types >> > given we're not allowed to use native FP? >> >> Yeah, I'm going to use it on integer types. And it's not designed >> to have nice properties at extremes, including handling underflow and >> overflow. > > So maybe assert that it doesn't? In particular nominator/denominator > are prone to overflowing in fractional representations. > > There's the option to round or ICE. Or rather than the only option > is to round (or use a more expensive arbitrary precision representation). Yeah, I guess we could do that, but it semes inconsistent to assert for these costs and not do it for vector costs in general. I think it's difficult to guarantee that there is no user input for which the current vector costs overflow. And if we assert, we have to have a reason for believing that no such user input exists (modulo bugs). E.g. vect-inner-loop-cost-factor has an upper limit of 999999, so the existing code only needs a cost of 2148 to overflow “int”. > So the question is whether the fractional behavior is better in more > cases than the sreal behavior (I can easily believe it is). > >> I want to use it in costing code, where we already happily multiply >> and add “int”-sized costs without worrying about overflow. I'll be >> using uint64_t for the fractions though, just in case. :-) >> >> sreal doesn't help because it's still significand/exponent. That matters >> because… >> >> > I mean, how exactly does >> > the class solve the problem of rounding errors? >> >> …I wanted something that represented the results exactly (barring any of >> integer ops overflowing). This makes it meaningful to compare costs for >> equality. It also means we can use ordered comparisons without having >> to introduce a fudge factor to cope with one calculation having different >> intermediate rounding from the other. > > I think you're underestimating how quickly your denominator will overflow? Well, it depends on how you use it. :-) I agree you have to go into this knowing the risks of the representation (but then I'd argue that's true for floats/sreals too, if you use them for costs). > So I suppose all factors of all possible denominators are known, in fact > whats your main source for the divisions? The VF? Yeah, the set of possible dominators is fixed at compile time and relatively small, but not easily enumerable. The VF is one source, but we also have “number of X per cycle” values. The problem with sreal is that sometimes those “X per cycle” values are 3, and 1/3 is where the rounding problems with floats/sreals start to come in. I'm fairly sure that using a uint64_t fractional representation for int costs and these set of denominator values is safe. But if we think that this is just too dangerous to advertise as a general class within GCC, we could make it local to the aarch64 cost code instead. Would that be OK? Thanks, Richard
On Mon, Aug 2, 2021 at 1:31 PM Richard Sandiford <richard.sandiford@arm.com> wrote: > > Richard Biener <richard.guenther@gmail.com> writes: > > On Mon, Aug 2, 2021 at 12:43 PM Richard Sandiford > > <richard.sandiford@arm.com> wrote: > >> > >> Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> writes: > >> > On Fri, Jul 30, 2021 at 5:59 PM Richard Sandiford via Gcc-patches > >> > <gcc-patches@gcc.gnu.org> wrote: > >> >> > >> >> This patch adds a simple class for holding A/B fractions. > >> >> As the comments in the patch say, the class isn't designed > >> >> to have nice numerial properties at the extremes. > >> >> > >> >> The motivating use case was some aarch64 costing work, > >> >> where being able to represent fractions was much easier > >> >> than using single integers and avoided the rounding errors > >> >> that would come with using floats. (Unlike things like > >> >> COSTS_N_INSNS, there was no sensible constant base factor > >> >> that could be used.) > >> >> > >> >> Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install? > >> > > >> > Hmm, we use the sreal type for profiles. I don't see any overflow/underflow > >> > handling in your class - I suppose you're going to use it on integer types > >> > given we're not allowed to use native FP? > >> > >> Yeah, I'm going to use it on integer types. And it's not designed > >> to have nice properties at extremes, including handling underflow and > >> overflow. > > > > So maybe assert that it doesn't? In particular nominator/denominator > > are prone to overflowing in fractional representations. > > > > There's the option to round or ICE. Or rather than the only option > > is to round (or use a more expensive arbitrary precision representation). > > Yeah, I guess we could do that, but it semes inconsistent to assert > for these costs and not do it for vector costs in general. I think it's > difficult to guarantee that there is no user input for which the current > vector costs overflow. And if we assert, we have to have a reason for > believing that no such user input exists (modulo bugs). > > E.g. vect-inner-loop-cost-factor has an upper limit of 999999, so the > existing code only needs a cost of 2148 to overflow “int”. I'd argue those are of course bugs. The 999999 upper bound is way too big given REB_BR_PROB_BASE is only 10000. But then we're now set up to initialize vinfo->inner_loop_cost_factor based on profile data (if it is reliable). > > So the question is whether the fractional behavior is better in more > > cases than the sreal behavior (I can easily believe it is). > > > >> I want to use it in costing code, where we already happily multiply > >> and add “int”-sized costs without worrying about overflow. I'll be > >> using uint64_t for the fractions though, just in case. :-) > >> > >> sreal doesn't help because it's still significand/exponent. That matters > >> because… > >> > >> > I mean, how exactly does > >> > the class solve the problem of rounding errors? > >> > >> …I wanted something that represented the results exactly (barring any of > >> integer ops overflowing). This makes it meaningful to compare costs for > >> equality. It also means we can use ordered comparisons without having > >> to introduce a fudge factor to cope with one calculation having different > >> intermediate rounding from the other. > > > > I think you're underestimating how quickly your denominator will overflow? > > Well, it depends on how you use it. :-) I agree you have to go into > this knowing the risks of the representation (but then I'd argue that's > true for floats/sreals too, if you use them for costs). Yeah, and sreals handle overflow/underflow in a well-defined way because profile info tends to be crap ;) > > So I suppose all factors of all possible denominators are known, in fact > > whats your main source for the divisions? The VF? > > Yeah, the set of possible dominators is fixed at compile time and > relatively small, but not easily enumerable. The VF is one source, > but we also have “number of X per cycle” values. The problem with sreal > is that sometimes those “X per cycle” values are 3, and 1/3 is where the > rounding problems with floats/sreals start to come in. > > I'm fairly sure that using a uint64_t fractional representation for > int costs and these set of denominator values is safe. But if we > think that this is just too dangerous to advertise as a general > class within GCC, we could make it local to the aarch64 cost code > instead. Would that be OK? I think we should instead make its use safe, that is, simply round when the denominator gets too big. The gcn compute is already expensive and so is the division, I suppose a practical way would be to use uint32 for the representation and [u]int64 for the intermediate compute? One could put extra debugging that dumps to the active dumpfile whenever this happens as well (but likely with a editable #define, disabled by default). Maybe even gcc_checking_assert()s would do if we document that the set of denominators need to be fixed in a way to ensure overflow doesn't happen. Richard. > Thanks, > Richard
Richard Biener <richard.guenther@gmail.com> writes: > On Mon, Aug 2, 2021 at 1:31 PM Richard Sandiford > <richard.sandiford@arm.com> wrote: >> >> Richard Biener <richard.guenther@gmail.com> writes: >> > On Mon, Aug 2, 2021 at 12:43 PM Richard Sandiford >> > <richard.sandiford@arm.com> wrote: >> >> >> >> Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> writes: >> >> > On Fri, Jul 30, 2021 at 5:59 PM Richard Sandiford via Gcc-patches >> >> > <gcc-patches@gcc.gnu.org> wrote: >> >> >> >> >> >> This patch adds a simple class for holding A/B fractions. >> >> >> As the comments in the patch say, the class isn't designed >> >> >> to have nice numerial properties at the extremes. >> >> >> >> >> >> The motivating use case was some aarch64 costing work, >> >> >> where being able to represent fractions was much easier >> >> >> than using single integers and avoided the rounding errors >> >> >> that would come with using floats. (Unlike things like >> >> >> COSTS_N_INSNS, there was no sensible constant base factor >> >> >> that could be used.) >> >> >> >> >> >> Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install? >> >> > >> >> > Hmm, we use the sreal type for profiles. I don't see any overflow/underflow >> >> > handling in your class - I suppose you're going to use it on integer types >> >> > given we're not allowed to use native FP? >> >> >> >> Yeah, I'm going to use it on integer types. And it's not designed >> >> to have nice properties at extremes, including handling underflow and >> >> overflow. >> > >> > So maybe assert that it doesn't? In particular nominator/denominator >> > are prone to overflowing in fractional representations. >> > >> > There's the option to round or ICE. Or rather than the only option >> > is to round (or use a more expensive arbitrary precision representation). >> >> Yeah, I guess we could do that, but it semes inconsistent to assert >> for these costs and not do it for vector costs in general. I think it's >> difficult to guarantee that there is no user input for which the current >> vector costs overflow. And if we assert, we have to have a reason for >> believing that no such user input exists (modulo bugs). >> >> E.g. vect-inner-loop-cost-factor has an upper limit of 999999, so the >> existing code only needs a cost of 2148 to overflow “int”. > > I'd argue those are of course bugs. The 999999 upper bound is way > too big given REB_BR_PROB_BASE is only 10000. But then we're now > set up to initialize vinfo->inner_loop_cost_factor based on profile data > (if it is reliable). > >> > So the question is whether the fractional behavior is better in more >> > cases than the sreal behavior (I can easily believe it is). >> > >> >> I want to use it in costing code, where we already happily multiply >> >> and add “int”-sized costs without worrying about overflow. I'll be >> >> using uint64_t for the fractions though, just in case. :-) >> >> >> >> sreal doesn't help because it's still significand/exponent. That matters >> >> because… >> >> >> >> > I mean, how exactly does >> >> > the class solve the problem of rounding errors? >> >> >> >> …I wanted something that represented the results exactly (barring any of >> >> integer ops overflowing). This makes it meaningful to compare costs for >> >> equality. It also means we can use ordered comparisons without having >> >> to introduce a fudge factor to cope with one calculation having different >> >> intermediate rounding from the other. >> > >> > I think you're underestimating how quickly your denominator will overflow? >> >> Well, it depends on how you use it. :-) I agree you have to go into >> this knowing the risks of the representation (but then I'd argue that's >> true for floats/sreals too, if you use them for costs). > > Yeah, and sreals handle overflow/underflow in a well-defined way because > profile info tends to be crap ;) > >> > So I suppose all factors of all possible denominators are known, in fact >> > whats your main source for the divisions? The VF? >> >> Yeah, the set of possible dominators is fixed at compile time and >> relatively small, but not easily enumerable. The VF is one source, >> but we also have “number of X per cycle” values. The problem with sreal >> is that sometimes those “X per cycle” values are 3, and 1/3 is where the >> rounding problems with floats/sreals start to come in. >> >> I'm fairly sure that using a uint64_t fractional representation for >> int costs and these set of denominator values is safe. But if we >> think that this is just too dangerous to advertise as a general >> class within GCC, we could make it local to the aarch64 cost code >> instead. Would that be OK? > > I think we should instead make its use safe, that is, simply round when > the denominator gets too big. The gcn compute is already expensive > and so is the division, I suppose a practical way would be to use > uint32 for the representation and [u]int64 for the intermediate compute? > > One could put extra debugging that dumps to the active dumpfile > whenever this happens as well (but likely with a editable #define, > disabled by default). Hmm, that feels quite a bit more complicated than what I was hoping for though. Perhaps I was trying to generalise too far. For the aarch64 vector cost code, we can make do with a fixed-point representation with a target- specific scale factor, so I went with that instead. I tried to address your correctness concerns by making the arithmetic saturating. I'll post the series (all AArch64-specific) in a sec. Thanks, Richard
On Tue, Aug 3, 2021 at 1:58 PM Richard Sandiford <richard.sandiford@arm.com> wrote: > > Richard Biener <richard.guenther@gmail.com> writes: > > On Mon, Aug 2, 2021 at 1:31 PM Richard Sandiford > > <richard.sandiford@arm.com> wrote: > >> > >> Richard Biener <richard.guenther@gmail.com> writes: > >> > On Mon, Aug 2, 2021 at 12:43 PM Richard Sandiford > >> > <richard.sandiford@arm.com> wrote: > >> >> > >> >> Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> writes: > >> >> > On Fri, Jul 30, 2021 at 5:59 PM Richard Sandiford via Gcc-patches > >> >> > <gcc-patches@gcc.gnu.org> wrote: > >> >> >> > >> >> >> This patch adds a simple class for holding A/B fractions. > >> >> >> As the comments in the patch say, the class isn't designed > >> >> >> to have nice numerial properties at the extremes. > >> >> >> > >> >> >> The motivating use case was some aarch64 costing work, > >> >> >> where being able to represent fractions was much easier > >> >> >> than using single integers and avoided the rounding errors > >> >> >> that would come with using floats. (Unlike things like > >> >> >> COSTS_N_INSNS, there was no sensible constant base factor > >> >> >> that could be used.) > >> >> >> > >> >> >> Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install? > >> >> > > >> >> > Hmm, we use the sreal type for profiles. I don't see any overflow/underflow > >> >> > handling in your class - I suppose you're going to use it on integer types > >> >> > given we're not allowed to use native FP? > >> >> > >> >> Yeah, I'm going to use it on integer types. And it's not designed > >> >> to have nice properties at extremes, including handling underflow and > >> >> overflow. > >> > > >> > So maybe assert that it doesn't? In particular nominator/denominator > >> > are prone to overflowing in fractional representations. > >> > > >> > There's the option to round or ICE. Or rather than the only option > >> > is to round (or use a more expensive arbitrary precision representation). > >> > >> Yeah, I guess we could do that, but it semes inconsistent to assert > >> for these costs and not do it for vector costs in general. I think it's > >> difficult to guarantee that there is no user input for which the current > >> vector costs overflow. And if we assert, we have to have a reason for > >> believing that no such user input exists (modulo bugs). > >> > >> E.g. vect-inner-loop-cost-factor has an upper limit of 999999, so the > >> existing code only needs a cost of 2148 to overflow “int”. > > > > I'd argue those are of course bugs. The 999999 upper bound is way > > too big given REB_BR_PROB_BASE is only 10000. But then we're now > > set up to initialize vinfo->inner_loop_cost_factor based on profile data > > (if it is reliable). > > > >> > So the question is whether the fractional behavior is better in more > >> > cases than the sreal behavior (I can easily believe it is). > >> > > >> >> I want to use it in costing code, where we already happily multiply > >> >> and add “int”-sized costs without worrying about overflow. I'll be > >> >> using uint64_t for the fractions though, just in case. :-) > >> >> > >> >> sreal doesn't help because it's still significand/exponent. That matters > >> >> because… > >> >> > >> >> > I mean, how exactly does > >> >> > the class solve the problem of rounding errors? > >> >> > >> >> …I wanted something that represented the results exactly (barring any of > >> >> integer ops overflowing). This makes it meaningful to compare costs for > >> >> equality. It also means we can use ordered comparisons without having > >> >> to introduce a fudge factor to cope with one calculation having different > >> >> intermediate rounding from the other. > >> > > >> > I think you're underestimating how quickly your denominator will overflow? > >> > >> Well, it depends on how you use it. :-) I agree you have to go into > >> this knowing the risks of the representation (but then I'd argue that's > >> true for floats/sreals too, if you use them for costs). > > > > Yeah, and sreals handle overflow/underflow in a well-defined way because > > profile info tends to be crap ;) > > > >> > So I suppose all factors of all possible denominators are known, in fact > >> > whats your main source for the divisions? The VF? > >> > >> Yeah, the set of possible dominators is fixed at compile time and > >> relatively small, but not easily enumerable. The VF is one source, > >> but we also have “number of X per cycle” values. The problem with sreal > >> is that sometimes those “X per cycle” values are 3, and 1/3 is where the > >> rounding problems with floats/sreals start to come in. > >> > >> I'm fairly sure that using a uint64_t fractional representation for > >> int costs and these set of denominator values is safe. But if we > >> think that this is just too dangerous to advertise as a general > >> class within GCC, we could make it local to the aarch64 cost code > >> instead. Would that be OK? > > > > I think we should instead make its use safe, that is, simply round when > > the denominator gets too big. The gcn compute is already expensive > > and so is the division, I suppose a practical way would be to use > > uint32 for the representation and [u]int64 for the intermediate compute? > > > > One could put extra debugging that dumps to the active dumpfile > > whenever this happens as well (but likely with a editable #define, > > disabled by default). > > Hmm, that feels quite a bit more complicated than what I was hoping for > though. Sorry ;) I think if we're introducing some generic abstraction it needs to adhere to higher correctness standards than random cost code sprinkled in the vectorizer... > Perhaps I was trying to generalise too far. For the aarch64 vector cost > code, we can make do with a fixed-point representation with a target- > specific scale factor, so I went with that instead. I tried to address > your correctness concerns by making the arithmetic saturating. > > I'll post the series (all AArch64-specific) in a sec. > > Thanks, > Richard
diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 1666ef84d6a..8eaaab84143 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1572,6 +1572,7 @@ OBJS = \ selftest-run-tests.o \ sese.o \ shrink-wrap.o \ + simple-fraction.o \ simplify-rtx.o \ sparseset.o \ spellcheck.o \ diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c index 1b5583e476a..f17d4e24884 100644 --- a/gcc/selftest-run-tests.c +++ b/gcc/selftest-run-tests.c @@ -80,6 +80,7 @@ selftest::run_tests () opt_problem_cc_tests (); ordered_hash_map_tests_cc_tests (); splay_tree_cc_tests (); + simple_fraction_cc_tests (); /* Mid-level data structures. */ input_c_tests (); diff --git a/gcc/selftest.h b/gcc/selftest.h index 80459d63a39..716ba41f6bf 100644 --- a/gcc/selftest.h +++ b/gcc/selftest.h @@ -254,6 +254,7 @@ extern void read_rtl_function_c_tests (); extern void rtl_tests_c_tests (); extern void sbitmap_c_tests (); extern void selftest_c_tests (); +extern void simple_fraction_cc_tests (); extern void simplify_rtx_c_tests (); extern void spellcheck_c_tests (); extern void spellcheck_tree_c_tests (); diff --git a/gcc/simple-fraction.h b/gcc/simple-fraction.h new file mode 100644 index 00000000000..8d3ff2bdd2d --- /dev/null +++ b/gcc/simple-fraction.h @@ -0,0 +1,308 @@ +// Simple fraction utilities +// Copyright (C) 2021 Free Software Foundation, Inc. +// +// This file is part of GCC. +// +// GCC is free software; you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation; either version 3, or (at your option) any later +// version. +// +// GCC is distributed in the hope that it will be useful, but WITHOUT ANY +// WARRANTY; without even the implied warranty of MERCHANTABILITY or +// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +// for more details. +// +// You should have received a copy of the GNU General Public License +// along with GCC; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// A simple fraction with nominator and denominator of integral type T. +// There is little attempt to handle multiplication overflow, so the class +// shouldn't be used in cases where that's a risk. It also doesn't cope +// gracefully with the minimum T value, if T is signed. +template <typename T> +class simple_fraction +{ +public: + // Construct a fraction equal to NOMINATOR. + template<typename T1> + constexpr simple_fraction (T1 nominator = 0) + : m_nominator (nominator), m_denominator (1) {} + + // Construct a fraction equal to NOMINATOR / DENOMINATOR (simplifying + // where possible). + template<typename T1, typename T2> + simple_fraction (T1 nominator, T2 denominator) + : simple_fraction (nominator, denominator, gcd (nominator, denominator)) {} + + simple_fraction operator- () const; + simple_fraction operator+ (const simple_fraction &) const; + simple_fraction operator- (const simple_fraction &) const; + simple_fraction operator* (const simple_fraction &) const; + simple_fraction operator/ (const simple_fraction &) const; + + simple_fraction &operator+= (const simple_fraction &); + simple_fraction &operator-= (const simple_fraction &); + simple_fraction &operator*= (const simple_fraction &); + simple_fraction &operator/= (const simple_fraction &); + + bool operator== (const simple_fraction &) const; + bool operator!= (const simple_fraction &) const; + bool operator< (const simple_fraction &) const; + bool operator<= (const simple_fraction &) const; + bool operator>= (const simple_fraction &) const; + bool operator> (const simple_fraction &) const; + + explicit operator bool () const { return m_nominator != 0; } + + T floor () const; + T ceil () const; + + // Convert the value to a double. + double as_double () const { return double (m_nominator) / m_denominator; } + + T nominator () const { return m_nominator; } + T denominator () const { return m_denominator; } + +private: + simple_fraction (T, T, T); + + T m_nominator, m_denominator; +}; + +template<typename T> +simple_fraction<T>::simple_fraction (T nominator, T denominator, T factor) + // Canonicalize the components by dividing each one by FACTOR. + : m_nominator (nominator / factor), + m_denominator (nominator ? denominator / factor : 1) +{ + if (T (0) - 1 < T (0) && m_denominator < 0) + { + m_nominator = -m_nominator; + m_denominator = -m_denominator; + } +} + +template<typename T> +simple_fraction<T> +simple_fraction<T>::operator- () const +{ + return { -m_nominator, m_denominator, 1 }; +} + +template<typename T> +simple_fraction<T> +simple_fraction<T>::operator+ (const simple_fraction &other) const +{ + if (m_denominator == other.m_denominator) + return { m_nominator + other.m_nominator, m_denominator }; + + T factor = gcd (m_denominator, other.m_denominator); + T new_nominator = (m_nominator * (other.m_denominator / factor) + + other.m_nominator * (m_denominator / factor)); + T new_denominator = m_denominator * (other.m_denominator / factor); + return { new_nominator, new_denominator }; +} + +template<typename T> +simple_fraction<T> & +simple_fraction<T>::operator+= (const simple_fraction &other) +{ + *this = *this + other; + return *this; +} + +template<typename T> +simple_fraction<T> +simple_fraction<T>::operator- (const simple_fraction &other) const +{ + if (m_denominator == other.m_denominator) + return { m_nominator - other.m_nominator, m_denominator }; + + T factor = gcd (m_denominator, other.m_denominator); + T new_nominator = (m_nominator * (other.m_denominator / factor) + - other.m_nominator * (m_denominator / factor)); + T new_denominator = m_denominator * (other.m_denominator / factor); + return { new_nominator, new_denominator }; +} + +template<typename T> +simple_fraction<T> & +simple_fraction<T>::operator-= (const simple_fraction &other) +{ + *this = *this - other; + return *this; +} + +template<typename T> +simple_fraction<T> +simple_fraction<T>::operator* (const simple_fraction &other) const +{ + return { m_nominator * other.m_nominator, + m_denominator * other.m_denominator }; +} + +template<typename T> +simple_fraction<T> & +simple_fraction<T>::operator*= (const simple_fraction &other) +{ + *this = *this * other; + return *this; +} + +template<typename T> +simple_fraction<T> +simple_fraction<T>::operator/ (const simple_fraction &other) const +{ + return { m_nominator * other.m_denominator, + m_denominator * other.m_nominator }; +} + +template<typename T> +simple_fraction<T> & +simple_fraction<T>::operator/= (const simple_fraction &other) +{ + *this = *this / other; + return *this; +} + +template<typename T> +bool +simple_fraction<T>::operator== (const simple_fraction &other) const +{ + return (m_nominator == other.m_nominator + && m_denominator == other.m_denominator); +} + +template<typename T> +bool +simple_fraction<T>::operator!= (const simple_fraction &other) const +{ + return !operator== (other); +} + +template<typename T> +bool +simple_fraction<T>::operator< (const simple_fraction<T> &other) const +{ + if (m_denominator == other.m_denominator) + return m_nominator < other.m_nominator; + + T factor = gcd (m_denominator, other.m_denominator); + return (m_nominator * (other.m_denominator / factor) + < other.m_nominator * (m_denominator / factor)); +} + +template<typename T> +bool +simple_fraction<T>::operator<= (const simple_fraction<T> &other) const +{ + return !other.operator< (*this); +} + +template<typename T> +bool +simple_fraction<T>::operator>= (const simple_fraction<T> &other) const +{ + return !operator< (other); +} + +template<typename T> +bool +simple_fraction<T>::operator> (const simple_fraction<T> &other) const +{ + return other.operator< (*this); +} + +template<typename T1, typename T2> +auto +operator+ (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator+ (a)) +{ + return b.operator+ (a); +} + +template<typename T1, typename T2> +auto +operator- (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator- (a)) +{ + return simple_fraction<T2> (a).operator- (b); +} + +template<typename T1, typename T2> +auto +operator* (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator* (a)) +{ + return b.operator* (a); +} + +template<typename T1, typename T2> +auto +operator/ (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator/ (a)) +{ + return simple_fraction<T2> (a).operator/ (b); +} + +template<typename T1, typename T2> +auto +operator== (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator== (a)) +{ + return b.operator== (a); +} + +template<typename T1, typename T2> +auto +operator!= (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator!= (a)) +{ + return b.operator!= (a); +} + +template<typename T1, typename T2> +auto +operator< (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator>= (a)) +{ + return b.operator> (a); +} + +template<typename T1, typename T2> +auto +operator<= (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator> (a)) +{ + return b.operator>= (a); +} + +template<typename T1, typename T2> +auto +operator>= (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator< (a)) +{ + return b.operator<= (a); +} + +template<typename T1, typename T2> +auto +operator> (T1 a, const simple_fraction<T2> &b) -> decltype (b.operator<= (a)) +{ + return b.operator< (a); +} + +// Round towards -Inf and return the result as an integer. +template<typename T> +T +simple_fraction<T>::floor () const +{ + if (T (0) - 1 < T (0) && m_nominator < T (0)) + return -CEIL (-m_nominator, m_denominator); + else + return m_nominator / m_denominator; +} + +// Round towards +Inf and return the result as an integer. +template<typename T> +T +simple_fraction<T>::ceil () const +{ + if (T (0) - 1 < T (0) && m_nominator < T (0)) + return -(-m_nominator / m_denominator); + else + return CEIL (m_nominator, m_denominator); +} diff --git a/gcc/simple-fraction.cc b/gcc/simple-fraction.cc new file mode 100644 index 00000000000..01c736be9d9 --- /dev/null +++ b/gcc/simple-fraction.cc @@ -0,0 +1,160 @@ +// Simple fraction utilities +// Copyright (C) 2021 Free Software Foundation, Inc. +// +// This file is part of GCC. +// +// GCC is free software; you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation; either version 3, or (at your option) any later +// version. +// +// GCC is distributed in the hope that it will be useful, but WITHOUT ANY +// WARRANTY; without even the implied warranty of MERCHANTABILITY or +// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +// for more details. +// +// You should have received a copy of the GNU General Public License +// along with GCC; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +#define INCLUDE_ALGORITHM +#define INCLUDE_ARRAY +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "simple-fraction.h" +#include "selftest.h" + +#if CHECKING_P +namespace selftest { + +// Run all tests for this module. +void +simple_fraction_cc_tests () +{ + using intf = simple_fraction<int>; + + ASSERT_EQ (intf (0, 100), 0); + + ASSERT_EQ (intf (4, 2), 2); + ASSERT_EQ (intf (-4, 2), -2); + ASSERT_EQ (3, intf (9, 3)); + ASSERT_EQ (-3, intf (9, -3)); + ASSERT_EQ (intf (-1, 4), intf (1, -4)); + ASSERT_EQ (intf (-1, -4), intf (1, 4)); + ASSERT_EQ (intf (-2, -8), intf (1, 4)); + + ASSERT_NE (intf (5, 2), 2); + ASSERT_NE (intf (-4, 2), 2); + ASSERT_NE (3, intf (8, 3)); + ASSERT_NE (-3, intf (9, 3)); + ASSERT_NE (intf (-1, -4), intf (-1, 4)); + + ASSERT_EQ (-intf (0), 0); + ASSERT_EQ (-intf (-1, 4), intf (1, 4)); + ASSERT_EQ (-intf (1, 4), intf (-1, 4)); + + ASSERT_EQ (intf (7, 11) + intf (15, 11), 2); + ASSERT_EQ (intf (2, 3) + intf (3, 5), intf (19, 15)); + ASSERT_EQ (intf (2, 3) + intf (1, 6) + intf (1, 6), 1); + ASSERT_EQ (intf (1, 0x10000) + intf (7, 0x20000), intf (9, 0x20000)); + ASSERT_EQ (intf (1, 0x10000) + 10, intf (0xa0001, 0x10000)); + ASSERT_EQ (10 + intf (1, 0x10000), intf (0xa0001, 0x10000)); + + ASSERT_EQ (intf (14, 15) - intf (4, 15), intf (2, 3)); + ASSERT_EQ (intf (1, 4) - intf (1, 2), intf (-1, 4)); + ASSERT_EQ (intf (3, 5) - intf (1, 10), intf (1, 2)); + ASSERT_EQ (intf (11, 3) - 3, intf (2, 3)); + ASSERT_EQ (3 - intf (7, 3), intf (2, 3)); + + ASSERT_EQ (intf (2, 3) * intf (3, 5), intf (2, 5)); + ASSERT_EQ (intf (-2, 9) * intf (3, 5), intf (-2, 15)); + ASSERT_EQ (intf (2, 3) * intf (-1, 6), intf (-1, 9)); + ASSERT_EQ (intf (-2, 5) * intf (-3, 7), intf (6, 35)); + ASSERT_EQ (intf (5, 6) * 3, intf (5, 2)); + ASSERT_EQ (14 * intf (11, 21), intf (22, 3)); + + ASSERT_EQ (intf (2, 3) / intf (3, 5), intf (10, 9)); + ASSERT_EQ (intf (3, 14) / intf (-1, 2), intf (-3, 7)); + ASSERT_EQ (intf (-13, 17) / intf (3, 2), intf (-26, 51)); + ASSERT_EQ (intf (-7, 9) / intf (-4, 3), intf (7, 12)); + + ASSERT_TRUE (intf (4, 15) < intf (5, 15)); + ASSERT_FALSE (intf (5, 15) < intf (5, 15)); + ASSERT_FALSE (intf (6, 15) < intf (5, 15)); + ASSERT_TRUE (intf (1, 3) < intf (2, 5)); + ASSERT_TRUE (intf (-1, 6) < intf (1, 12)); + ASSERT_FALSE (intf (5, 3) < intf (5, 3)); + ASSERT_FALSE (intf (7, 11) < intf (13, 22)); + ASSERT_TRUE (intf (7, 11) < intf (15, 22)); + ASSERT_TRUE (intf (100, 101) < 1); + ASSERT_FALSE (intf (101, 101) < 1); + ASSERT_FALSE (intf (102, 101) < 1); + ASSERT_FALSE (2 < intf (99, 50)); + ASSERT_FALSE (2 < intf (100, 50)); + ASSERT_TRUE (2 < intf (101, 50)); + + ASSERT_TRUE (intf (4, 15) <= intf (5, 15)); + ASSERT_TRUE (intf (5, 15) <= intf (5, 15)); + ASSERT_FALSE (intf (6, 15) <= intf (5, 15)); + ASSERT_TRUE (intf (1, 3) <= intf (2, 5)); + ASSERT_TRUE (intf (-1, 6) <= intf (1, 12)); + ASSERT_TRUE (intf (5, 3) <= intf (5, 3)); + ASSERT_FALSE (intf (7, 11) <= intf (13, 22)); + ASSERT_TRUE (intf (7, 11) <= intf (15, 22)); + ASSERT_TRUE (intf (100, 101) <= 1); + ASSERT_TRUE (intf (101) / 101 <= 1); + ASSERT_FALSE (intf (102, 101) <= 1); + ASSERT_FALSE (2 <= intf (99, 50)); + ASSERT_TRUE (2 <= intf (100, 50)); + ASSERT_TRUE (2 <= intf (101, 50)); + + ASSERT_FALSE (intf (4, 15) >= intf (5, 15)); + ASSERT_TRUE (intf (5, 15) >= intf (5, 15)); + ASSERT_TRUE (intf (6, 15) >= intf (5, 15)); + ASSERT_FALSE (intf (1, 3) >= intf (2, 5)); + ASSERT_FALSE (intf (-1, 6) >= intf (1, 12)); + ASSERT_TRUE (intf (5, 3) >= intf (5, 3)); + ASSERT_TRUE (intf (7, 11) >= intf (13, 22)); + ASSERT_FALSE (intf (7, 11) >= intf (15, 22)); + ASSERT_FALSE (intf (100, 101) >= 1); + ASSERT_TRUE (intf (101, 101) >= 1); + ASSERT_TRUE (intf (102, 101) >= 1); + ASSERT_TRUE (2 >= intf (99, 50)); + ASSERT_TRUE (2 >= intf (100, 50)); + ASSERT_FALSE (2 >= intf (101, 50)); + + ASSERT_FALSE (intf (4, 15) > intf (5, 15)); + ASSERT_FALSE (intf (5, 15) > intf (5, 15)); + ASSERT_TRUE (intf (6, 15) > intf (5, 15)); + ASSERT_FALSE (intf (1, 3) > intf (2, 5)); + ASSERT_FALSE (intf (-1, 6) > intf (1, 12)); + ASSERT_FALSE (intf (5, 3) > intf (5, 3)); + ASSERT_TRUE (intf (7, 11) > intf (13, 22)); + ASSERT_FALSE (intf (7, 11) > intf (15, 22)); + ASSERT_FALSE (intf (100, 101) > 1); + ASSERT_FALSE (intf (101) / 101 > 1); + ASSERT_TRUE (intf (102, 101) > 1); + ASSERT_TRUE (2 > intf (99, 50)); + ASSERT_FALSE (2 > intf (100, 50)); + ASSERT_FALSE (2 > intf (101, 50)); + + ASSERT_EQ (intf (1, 2).floor (), 0); + ASSERT_EQ (intf (11, 7).floor (), 1); + ASSERT_EQ (intf (20, 1).floor (), 20); + ASSERT_EQ (intf (-1, 2).floor (), -1); + ASSERT_EQ (intf (-11, 7).floor (), -2); + ASSERT_EQ (intf (-20, 1).floor (), -20); + + ASSERT_EQ (intf (1, 2).ceil (), 1); + ASSERT_EQ (intf (11, 7).ceil (), 2); + ASSERT_EQ (intf (20, 1).ceil (), 20); + ASSERT_EQ (intf (-1, 2).ceil (), 0); + ASSERT_EQ (intf (-11, 7).ceil (), -1); + ASSERT_EQ (intf (-20, 1).ceil (), -20); + + ASSERT_EQ (intf (1, 2).as_double (), 0.5); + ASSERT_EQ (intf (-5, 4).as_double (), -1.25); +} +} +#endif // CHECKING_P