From patchwork Fri Jul 30 15:58:15 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 1511741 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=dC91xnZ9; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4GbsXR1k8Mz9sT6 for ; Sat, 31 Jul 2021 01:59:19 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 12088394D809 for ; Fri, 30 Jul 2021 15:59:17 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 12088394D809 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1627660757; bh=u11Lm2KIqj9k8VUEZ0HrU0mtg9+C6afu/tREc1wrUhE=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=dC91xnZ9kHw39j1d5LqgJ/y55VybdrWQqLkxeYPznJIO1b9DmfOlocZM8c9RvPdWT 4EcBCRhjKBgFaZZQvKwCu6WgzyftgFFKC5Lsibr4k5xuLO/jwXsvfHvYtpkM55yUeQ rYvLjj6Zu3P+KJ4CTBIGWKbwF8OLLqSQVjl2WqyQ= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id 23EB6394D825 for ; Fri, 30 Jul 2021 15:58:17 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 23EB6394D825 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id CED7F113E for ; Fri, 30 Jul 2021 08:58:16 -0700 (PDT) Received: from localhost (e121540-lin.manchester.arm.com [10.32.98.126]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 59D0D3F66F for ; Fri, 30 Jul 2021 08:58:16 -0700 (PDT) To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Subject: [PATCH] Add a simple fraction class Date: Fri, 30 Jul 2021 16:58:15 +0100 Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 X-Spam-Status: No, score=-12.4 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_STATUS, KAM_SHORT, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Sandiford via Gcc-patches From: Richard Sandiford Reply-To: Richard Sandiford Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" 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 +// . + +// 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 +class simple_fraction +{ +public: + // Construct a fraction equal to NOMINATOR. + template + constexpr simple_fraction (T1 nominator = 0) + : m_nominator (nominator), m_denominator (1) {} + + // Construct a fraction equal to NOMINATOR / DENOMINATOR (simplifying + // where possible). + template + 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 +simple_fraction::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 +simple_fraction +simple_fraction::operator- () const +{ + return { -m_nominator, m_denominator, 1 }; +} + +template +simple_fraction +simple_fraction::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 +simple_fraction & +simple_fraction::operator+= (const simple_fraction &other) +{ + *this = *this + other; + return *this; +} + +template +simple_fraction +simple_fraction::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 +simple_fraction & +simple_fraction::operator-= (const simple_fraction &other) +{ + *this = *this - other; + return *this; +} + +template +simple_fraction +simple_fraction::operator* (const simple_fraction &other) const +{ + return { m_nominator * other.m_nominator, + m_denominator * other.m_denominator }; +} + +template +simple_fraction & +simple_fraction::operator*= (const simple_fraction &other) +{ + *this = *this * other; + return *this; +} + +template +simple_fraction +simple_fraction::operator/ (const simple_fraction &other) const +{ + return { m_nominator * other.m_denominator, + m_denominator * other.m_nominator }; +} + +template +simple_fraction & +simple_fraction::operator/= (const simple_fraction &other) +{ + *this = *this / other; + return *this; +} + +template +bool +simple_fraction::operator== (const simple_fraction &other) const +{ + return (m_nominator == other.m_nominator + && m_denominator == other.m_denominator); +} + +template +bool +simple_fraction::operator!= (const simple_fraction &other) const +{ + return !operator== (other); +} + +template +bool +simple_fraction::operator< (const simple_fraction &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 +bool +simple_fraction::operator<= (const simple_fraction &other) const +{ + return !other.operator< (*this); +} + +template +bool +simple_fraction::operator>= (const simple_fraction &other) const +{ + return !operator< (other); +} + +template +bool +simple_fraction::operator> (const simple_fraction &other) const +{ + return other.operator< (*this); +} + +template +auto +operator+ (T1 a, const simple_fraction &b) -> decltype (b.operator+ (a)) +{ + return b.operator+ (a); +} + +template +auto +operator- (T1 a, const simple_fraction &b) -> decltype (b.operator- (a)) +{ + return simple_fraction (a).operator- (b); +} + +template +auto +operator* (T1 a, const simple_fraction &b) -> decltype (b.operator* (a)) +{ + return b.operator* (a); +} + +template +auto +operator/ (T1 a, const simple_fraction &b) -> decltype (b.operator/ (a)) +{ + return simple_fraction (a).operator/ (b); +} + +template +auto +operator== (T1 a, const simple_fraction &b) -> decltype (b.operator== (a)) +{ + return b.operator== (a); +} + +template +auto +operator!= (T1 a, const simple_fraction &b) -> decltype (b.operator!= (a)) +{ + return b.operator!= (a); +} + +template +auto +operator< (T1 a, const simple_fraction &b) -> decltype (b.operator>= (a)) +{ + return b.operator> (a); +} + +template +auto +operator<= (T1 a, const simple_fraction &b) -> decltype (b.operator> (a)) +{ + return b.operator>= (a); +} + +template +auto +operator>= (T1 a, const simple_fraction &b) -> decltype (b.operator< (a)) +{ + return b.operator<= (a); +} + +template +auto +operator> (T1 a, const simple_fraction &b) -> decltype (b.operator<= (a)) +{ + return b.operator< (a); +} + +// Round towards -Inf and return the result as an integer. +template +T +simple_fraction::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 +T +simple_fraction::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 +// . + +#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; + + 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