[PATCH] Add a simple fraction class

Richard Biener richard.guenther@gmail.com
Mon Aug 2 09:55:49 GMT 2021


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


More information about the Gcc-patches mailing list