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?
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
