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
