diff mbox

Use HOST_WIDE_INTs in gcd and least_common_multiple.

Message ID 1296235481-4039-1-git-send-email-sebpop@gmail.com
State New
Headers show

Commit Message

Sebastian Pop Jan. 28, 2011, 5:24 p.m. UTC 
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  <sebastian.pop@amd.com>

	* 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(-)

Comments

Joseph Myers Jan. 28, 2011, 5:41 p.m. UTC | #1 
On Fri, 28 Jan 2011, Sebastian Pop wrote:

> +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);

The case of equality should be OK as well - that is, >= not >.

> +/* 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);

All the negations here of x and y could overflow - an assertion that x and 
y are not HOST_WIDE_INT_MIN is probably the simplest fix.  (Because 
pos_mul_hwi returns a positive value, the negation of that return value 
won't overflow, however.)
Jay Foad Jan. 31, 2011, 2:07 p.m. UTC | #2 
> +/* 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);
> +}

How about:

HOST_WIDE_INT
mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
{
  HOST_WIDE_INT r = x * y;
  /* Multiplying by 0 is always safe. Multiplying by -1 is safe except for
     HOST_WIDE_INT_MIN. In all other cases we can divide to check we get back
     the number we first thought of.  */
  gcc_checking_assert (x == 0 || (x == -1 ? r != y : r / x == y));
  return r;
}

Jay.
Joseph Myers Jan. 31, 2011, 2:10 p.m. UTC | #3 
On Mon, 31 Jan 2011, Jay Foad wrote:

> How about:
> 
> HOST_WIDE_INT
> mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
> {
>   HOST_WIDE_INT r = x * y;

At this point, undefined behavior may have occurred.

>   /* Multiplying by 0 is always safe. Multiplying by -1 is safe except for
>      HOST_WIDE_INT_MIN. In all other cases we can divide to check we get back
>      the number we first thought of.  */

Checking after the event is never safe.
Jay Foad Jan. 31, 2011, 2:22 p.m. UTC | #4 
>> How about:
>>
>> HOST_WIDE_INT
>> mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
>> {
>>   HOST_WIDE_INT r = x * y;
>
> At this point, undefined behavior may have occurred.

Well, then:

HOST_WIDE_INT r = (unsigned HOST_WIDE_INT) x * (unsigned HOST_WIDE_INT) y;

Jay.
diff mbox

Patch

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  <sebastian.pop@amd.com>
+
+	* 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  <ro@CeBiTec.Uni-Bielefeld.DE>
 
 	* 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);
 			  }