From patchwork Fri Jan 28 17:24:41 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 80877 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 9CBB1B70F9 for ; Sat, 29 Jan 2011 04:25:04 +1100 (EST) Received: (qmail 14015 invoked by alias); 28 Jan 2011 17:25:01 -0000 Received: (qmail 13991 invoked by uid 22791); 28 Jan 2011 17:25:00 -0000 X-SWARE-Spam-Status: No, hits=-2.3 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, T_TO_NO_BRKTS_FREEMAIL X-Spam-Check-By: sourceware.org Received: from mail-yi0-f47.google.com (HELO mail-yi0-f47.google.com) (209.85.218.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 28 Jan 2011 17:24:55 +0000 Received: by yie16 with SMTP id 16so1270791yie.20 for ; Fri, 28 Jan 2011 09:24:53 -0800 (PST) Received: by 10.151.28.2 with SMTP id f2mr4437214ybj.378.1296235493062; Fri, 28 Jan 2011 09:24:53 -0800 (PST) Received: from napoca ([163.181.251.115]) by mx.google.com with ESMTPS id q33sm11752475yba.7.2011.01.28.09.24.46 (version=TLSv1/SSLv3 cipher=RC4-MD5); Fri, 28 Jan 2011 09:24:47 -0800 (PST) Received: by napoca (sSMTP sendmail emulation); Fri, 28 Jan 2011 11:24:45 -0600 From: Sebastian Pop To: gcc-patches@gcc.gnu.org Cc: joseph@codesourcery.com, Sebastian Pop Subject: [PATCH] Use HOST_WIDE_INTs in gcd and least_common_multiple. Date: Fri, 28 Jan 2011 11:24:41 -0600 Message-Id: <1296235481-4039-1-git-send-email-sebpop@gmail.com> In-Reply-To: References: X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Hi Joseph, this patch fixes some of the problems that you raised in your review. The patch passed regstrap on amd64-linux. Ok for trunk? Thanks, Sebastian 2011-01-28 Sebastian Pop * Makefile.in (hwint.o): Depend on DIAGNOSTIC_CORE_H. * hwint.c: Include diagnostic-core.h. (abs_hwi): New. (gcd): Moved here... (pos_mul_hwi): New. (mul_hwi): New. (least_common_multiple): Moved here... * hwint.h (gcd): ... from here. (least_common_multiple): ... from here. (HOST_WIDE_INT_MIN): New. (HOST_WIDE_INT_MAX): New. (abs_hwi): Declared. (gcd): Declared. (pos_mul_hwi): Declared. (mul_hwi): Declared. (least_common_multiple): Declared. * omega.c (check_pos_mul): Removed. (check_mul): Removed. (omega_solve_geq): Use pos_mul_hwi instead of check_pos_mul and mul_hwi instead of check_mul. --- gcc/ChangeLog | 23 +++++++++++++++++ gcc/Makefile.in | 2 +- gcc/hwint.c | 71 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ gcc/hwint.h | 37 +++++++--------------------- gcc/omega.c | 47 ++++++------------------------------ 5 files changed, 112 insertions(+), 68 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index f724648..ca3fcc5 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,26 @@ +2011-01-28 Sebastian Pop + + * Makefile.in (hwint.o): Depend on DIAGNOSTIC_CORE_H. + * hwint.c: Include diagnostic-core.h. + (abs_hwi): New. + (gcd): Moved here... + (pos_mul_hwi): New. + (mul_hwi): New. + (least_common_multiple): Moved here... + * hwint.h (gcd): ... from here. + (least_common_multiple): ... from here. + (HOST_WIDE_INT_MIN): New. + (HOST_WIDE_INT_MAX): New. + (abs_hwi): Declared. + (gcd): Declared. + (pos_mul_hwi): Declared. + (mul_hwi): Declared. + (least_common_multiple): Declared. + * omega.c (check_pos_mul): Removed. + (check_mul): Removed. + (omega_solve_geq): Use pos_mul_hwi instead of check_pos_mul and + mul_hwi instead of check_mul. + 2011-01-28 Rainer Orth * configure.ac (gcc_cv_ld_static_dynamic): IRIX 6 ld supports diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 9a8262a..b2f4bad 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -2820,7 +2820,7 @@ toplev.o : toplev.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \ -DTARGET_NAME=\"$(target_noncanonical)\" \ -c $(srcdir)/toplev.c $(OUTPUT_OPTION) -hwint.o : hwint.c $(CONFIG_H) $(SYSTEM_H) +hwint.o : hwint.c $(CONFIG_H) $(SYSTEM_H) $(DIAGNOSTIC_CORE_H) passes.o : passes.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \ $(RTL_H) $(FUNCTION_H) $(FLAGS_H) xcoffout.h $(INPUT_H) $(INSN_ATTR_H) output.h \ diff --git a/gcc/hwint.c b/gcc/hwint.c index 85c1326..4d96628 100644 --- a/gcc/hwint.c +++ b/gcc/hwint.c @@ -21,6 +21,7 @@ along with GCC; see the file COPYING3. If not see #include "config.h" #include "system.h" +#include "diagnostic-core.h" #if GCC_VERSION < 3004 @@ -98,3 +99,73 @@ ffs_hwi (unsigned HOST_WIDE_INT x) } #endif /* GCC_VERSION < 3004 */ + +/* Compute the absolute value of X. */ + +HOST_WIDE_INT +abs_hwi (HOST_WIDE_INT x) +{ + gcc_checking_assert (x != HOST_WIDE_INT_MIN); + return x >= 0 ? x : -x; +} + +/* Compute the greatest common divisor of two numbers A and B using + Euclid's algorithm. */ + +HOST_WIDE_INT +gcd (HOST_WIDE_INT a, HOST_WIDE_INT b) +{ + HOST_WIDE_INT x, y, z; + + x = abs_hwi (a); + y = abs_hwi (b); + + while (x > 0) + { + z = y % x; + y = x; + x = z; + } + + return y; +} + +/* For X and Y positive integers, return X multiplied by Y and check + that the result does not overflow. */ + +HOST_WIDE_INT +pos_mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y) +{ + if (x != 0) + gcc_checking_assert ((HOST_WIDE_INT_MAX) / x > y); + + return x * y; +} + +/* Return X multiplied by Y and check that the result does not + overflow. */ + +HOST_WIDE_INT +mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y) +{ + if (x >= 0) + { + if (y >= 0) + return pos_mul_hwi (x, y); + + return -pos_mul_hwi (x, -y); + } + + if (y >= 0) + return -pos_mul_hwi (-x, y); + + return pos_mul_hwi (-x, -y); +} + +/* Compute the least common multiple of two numbers A and B . */ + +HOST_WIDE_INT +least_common_multiple (HOST_WIDE_INT a, HOST_WIDE_INT b) +{ + return mul_hwi (abs_hwi (a) / gcd (a, b), abs_hwi (b)); +} diff --git a/gcc/hwint.h b/gcc/hwint.h index 1eadd45..fa77b11 100644 --- a/gcc/hwint.h +++ b/gcc/hwint.h @@ -228,33 +228,14 @@ exact_log2 (unsigned HOST_WIDE_INT x) #endif /* GCC_VERSION >= 3004 */ -/* Compute the greatest common divisor of two numbers using - Euclid's algorithm. */ - -static inline int -gcd (int a, int b) -{ - int x, y, z; - - x = abs (a); - y = abs (b); - - while (x > 0) - { - z = y % x; - y = x; - x = z; - } - - return y; -} - -/* Compute the least common multiple of two numbers A and B . */ - -static inline int -least_common_multiple (int a, int b) -{ - return (abs (a) * abs (b) / gcd (a, b)); -} +#define HOST_WIDE_INT_MIN (HOST_WIDE_INT) \ + ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)) +#define HOST_WIDE_INT_MAX (~(HOST_WIDE_INT_MIN)) + +extern HOST_WIDE_INT abs_hwi (HOST_WIDE_INT); +extern HOST_WIDE_INT gcd (HOST_WIDE_INT, HOST_WIDE_INT); +extern HOST_WIDE_INT pos_mul_hwi (HOST_WIDE_INT, HOST_WIDE_INT); +extern HOST_WIDE_INT mul_hwi (HOST_WIDE_INT, HOST_WIDE_INT); +extern HOST_WIDE_INT least_common_multiple (HOST_WIDE_INT, HOST_WIDE_INT); #endif /* ! GCC_HWINT_H */ diff --git a/gcc/omega.c b/gcc/omega.c index 1717f8e..c8768d8 100644 --- a/gcc/omega.c +++ b/gcc/omega.c @@ -110,37 +110,6 @@ int_mod (int a, int b) return a - b * int_div (a, b); } -/* For X and Y positive integers, return X multiplied by Y and check - that the result does not overflow. */ - -static inline int -check_pos_mul (int x, int y) -{ - if (x != 0) - gcc_assert ((INT_MAX) / x > y); - - return x * y; -} - -/* Return X multiplied by Y and check that the result does not - overflow. */ - -static inline int -check_mul (int x, int y) -{ - if (x >= 0) - { - if (y >= 0) - return check_pos_mul (x, y); - else - return -check_pos_mul (x, -y); - } - else if (y >= 0) - return -check_pos_mul (-x, y); - else - return check_pos_mul (-x, -y); -} - /* Test whether equation E is red. */ static inline bool @@ -3907,8 +3876,8 @@ omega_solve_geq (omega_pb pb, enum omega_result desired_res) max_splinters += -minC - 1; else max_splinters += - check_pos_mul ((pb->geqs[e].coef[i] - 1), - (-minC - 1)) / (-minC) + 1; + pos_mul_hwi ((pb->geqs[e].coef[i] - 1), + (-minC - 1)) / (-minC) + 1; } /* #ifdef Omega3 */ @@ -4321,8 +4290,8 @@ omega_solve_geq (omega_pb pb, enum omega_result desired_res) for (k = 0; k <= n_vars; k++) pb->geqs[Ue].coef[k] = - check_mul (pb->geqs[Ue].coef[k], Lc) + - check_mul (lbeqn->coef[k], Uc); + mul_hwi (pb->geqs[Ue].coef[k], Lc) + + mul_hwi (lbeqn->coef[k], Uc); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -4384,8 +4353,8 @@ omega_solve_geq (omega_pb pb, enum omega_result desired_res) for (k = n_vars; k >= 0; k--) pb->geqs[e2].coef[k] = - check_mul (pb->geqs[Ue].coef[k], Lc) + - check_mul (pb->geqs[Le].coef[k], Uc); + mul_hwi (pb->geqs[Ue].coef[k], Lc) + + mul_hwi (pb->geqs[Le].coef[k], Uc); pb->geqs[e2].coef[n_vars + 1] = 0; pb->geqs[e2].touched = 1; @@ -4506,8 +4475,8 @@ omega_solve_geq (omega_pb pb, enum omega_result desired_res) { for (k = n_vars; k >= 0; k--) iS->geqs[e2].coef[k] = rS->geqs[e2].coef[k] = - check_mul (pb->geqs[Ue].coef[k], Lc) + - check_mul (pb->geqs[Le].coef[k], Uc); + mul_hwi (pb->geqs[Ue].coef[k], Lc) + + mul_hwi (pb->geqs[Le].coef[k], Uc); iS->geqs[e2].coef[0] -= (Uc - 1) * (Lc - 1); }