* [PATCH] Handle overflow in dependence analysis lambda ops gracefully
@ 2021-01-20 11:29 Richard Biener
2021-01-20 11:33 ` Jakub Jelinek
0 siblings, 1 reply; 8+ messages in thread
From: Richard Biener @ 2021-01-20 11:29 UTC (permalink / raw)
To: gcc-patches; +Cc: jakub, richard.sandiford
The following tries to handle overflow in the integer computations
done by lambda ops of dependence analysis by failing instead of
silently continuing with overflowed values.
It also avoids treating large unsigned CHREC_RIGHT as negative
unless the chrec is of pointer type and avoids the most negative
integer value to avoid excessive overflow checking (with this
the fix for PR98758 can be partly simplified as seen).
I've added add_hwi and mul_hwi functions computing HOST_WIDE_INT
signed sum and product with indicating overflow, they hopefully
get matched to the appropriate internal functions.
I don't have any testcases triggering overflow in any of the
guarded computations.
Bootstrapped and tested on x86_64-unknown-linux-gnu, any comments?
Thanks,
Richard.
2021-01-20 Richard Biener <rguenther@suse.de>
* hwint.h (add_hwi): New function.
(mul_hwi): Likewise.
* tree-data-ref.c (initialize_matrix_A): Properly translate
tree constants and avoid HOST_WIDE_INT_MIN.
(lambda_matrix_row_add): Avoid undefined integer overflow
and return true on such overflow.
(lambda_matrix_right_hermite): Handle overflow from
lambda_matrix_row_add gracefully. Simplify previous fix.
(analyze_subscript_affine_affine): Likewise.
---
gcc/hwint.h | 29 +++++++++++++++++++++
gcc/tree-data-ref.c | 63 +++++++++++++++++++++++++++++++++++----------
2 files changed, 78 insertions(+), 14 deletions(-)
diff --git a/gcc/hwint.h b/gcc/hwint.h
index 127b0130c66..53f4ed5dcad 100644
--- a/gcc/hwint.h
+++ b/gcc/hwint.h
@@ -333,4 +333,33 @@ absu_hwi (HOST_WIDE_INT x)
return x >= 0 ? (unsigned HOST_WIDE_INT)x : -(unsigned HOST_WIDE_INT)x;
}
+/* Compute the sum of signed A and B and indicate in *OVERFLOW whether
+ that operation overflowed. */
+
+inline HOST_WIDE_INT
+add_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool *overflow)
+{
+ unsigned HOST_WIDE_INT result = a + b;
+ if ((((result ^ a) & (result ^ b))
+ >> (HOST_BITS_PER_WIDE_INT - 1)) & 1)
+ *overflow = true;
+ else
+ *overflow = false;
+ return result;
+}
+
+/* Compute the product of signed A and B and indicate in *OVERFLOW whether
+ that operation overflowed. */
+
+inline HOST_WIDE_INT
+mul_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool *overflow)
+{
+ unsigned HOST_WIDE_INT result = a * (unsigned HOST_WIDE_INT)b;
+ if (a != 0 && (HOST_WIDE_INT)result / a != b)
+ *overflow = true;
+ else
+ *overflow = false;
+ return result;
+}
+
#endif /* ! GCC_HWINT_H */
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 9d07b415e9d..d19c5eb51e4 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -3924,9 +3924,25 @@ initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
- if (!cst_and_fits_in_hwi (CHREC_RIGHT (chrec)))
+ /* CHREC_RIGHT and its negated value should fit in a lambda_int.
+ Pointer typed chrecs right are to be interpreted signed. */
+ HOST_WIDE_INT chrec_right;
+ if (POINTER_TYPE_P (chrec_type (chrec)))
+ {
+ if (!cst_and_fits_in_hwi (CHREC_RIGHT (chrec)))
+ return chrec_dont_know;
+ chrec_right = int_cst_value (CHREC_RIGHT (chrec));
+ }
+ else
+ {
+ if (!tree_fits_shwi_p (CHREC_RIGHT (chrec)))
+ return chrec_dont_know;
+ chrec_right = tree_to_shwi (CHREC_RIGHT (chrec));
+ }
+ /* We want to be able to negate without overflow. */
+ if (chrec_right == HOST_WIDE_INT_MIN)
return chrec_dont_know;
- A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
+ A[index][0] = mult * chrec_right;
return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
case PLUS_EXPR:
@@ -4193,17 +4209,28 @@ lambda_vector_first_nz (lambda_vector vec1, int n, int start)
/* Add a multiple of row R1 of matrix MAT with N columns to row R2:
R2 = R2 + CONST1 * R1. */
-static void
+static bool
lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2,
lambda_int const1)
{
int i;
if (const1 == 0)
- return;
+ return true;
for (i = 0; i < n; i++)
- mat[r2][i] += const1 * mat[r1][i];
+ {
+ bool ovf;
+ lambda_int tem = mul_hwi (mat[r1][i], const1, &ovf);
+ if (ovf)
+ return false;
+ lambda_int tem2 = add_hwi (mat[r2][i], tem, &ovf);
+ if (ovf || tem2 == HOST_WIDE_INT_MIN)
+ return false;
+ mat[r2][i] = tem2;
+ }
+
+ return true;
}
/* Multiply vector VEC1 of length SIZE by a constant CONST1,
@@ -4258,7 +4285,7 @@ lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
Ref: Algorithm 2.1 page 33 in "Loop Transformations for
Restructuring Compilers" Utpal Banerjee. */
-static void
+static bool
lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
lambda_matrix S, lambda_matrix U)
{
@@ -4276,24 +4303,26 @@ lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
{
while (S[i][j] != 0)
{
- lambda_int sigma, factor, a, b;
+ lambda_int factor, a, b;
a = S[i-1][j];
b = S[i][j];
- sigma = ((a < 0) ^ (b < 0)) ? -1: 1;
- unsigned HOST_WIDE_INT abs_a = absu_hwi (a);
- unsigned HOST_WIDE_INT abs_b = absu_hwi (b);
- factor = sigma * (lambda_int)(abs_a / abs_b);
+ gcc_assert (a != HOST_WIDE_INT_MIN);
+ factor = a / b;
- lambda_matrix_row_add (S, n, i, i-1, -factor);
+ if (!lambda_matrix_row_add (S, n, i, i-1, -factor))
+ return false;
std::swap (S[i], S[i-1]);
- lambda_matrix_row_add (U, m, i, i-1, -factor);
+ if (!lambda_matrix_row_add (U, m, i, i-1, -factor))
+ return false;
std::swap (U[i], U[i-1]);
}
}
}
}
+
+ return true;
}
/* Determines the overlapping elements due to accesses CHREC_A and
@@ -4410,7 +4439,13 @@ analyze_subscript_affine_affine (tree chrec_a,
}
/* U.A = S */
- lambda_matrix_right_hermite (A, dim, 1, S, U);
+ if (!lambda_matrix_right_hermite (A, dim, 1, S, U))
+ {
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
+ goto end_analyze_subs_aa;
+ }
if (S[0][0] < 0)
{
--
2.26.2
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] Handle overflow in dependence analysis lambda ops gracefully
2021-01-20 11:29 [PATCH] Handle overflow in dependence analysis lambda ops gracefully Richard Biener
@ 2021-01-20 11:33 ` Jakub Jelinek
2021-01-20 12:15 ` Richard Biener
0 siblings, 1 reply; 8+ messages in thread
From: Jakub Jelinek @ 2021-01-20 11:33 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches, richard.sandiford
On Wed, Jan 20, 2021 at 12:29:23PM +0100, Richard Biener wrote:
> +/* Compute the product of signed A and B and indicate in *OVERFLOW whether
> + that operation overflowed. */
> +
> +inline HOST_WIDE_INT
> +mul_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool *overflow)
> +{
> + unsigned HOST_WIDE_INT result = a * (unsigned HOST_WIDE_INT)b;
> + if (a != 0 && (HOST_WIDE_INT)result / a != b)
> + *overflow = true;
> + else
> + *overflow = false;
This isn't sufficiently bulletproof.
It should be
if ((a == -1 && b == HOST_WIDE_INT_MIN)
|| (a != 0 && (HOST_WIDE_INT)result / a != b))
*overflow = true;
else
*overflow = false;
or so.
And except that a == -1 && b == min checks my recent widening_mul changes
should match that to __builtin_mul_overflow, so it will not be perfect code,
but at least will not be unnecessarily slow on x86.
Jakub
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] Handle overflow in dependence analysis lambda ops gracefully
2021-01-20 11:33 ` Jakub Jelinek
@ 2021-01-20 12:15 ` Richard Biener
2021-01-20 12:19 ` Jakub Jelinek
0 siblings, 1 reply; 8+ messages in thread
From: Richard Biener @ 2021-01-20 12:15 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: gcc-patches, richard.sandiford
On Wed, 20 Jan 2021, Jakub Jelinek wrote:
> On Wed, Jan 20, 2021 at 12:29:23PM +0100, Richard Biener wrote:
> > +/* Compute the product of signed A and B and indicate in *OVERFLOW whether
> > + that operation overflowed. */
> > +
> > +inline HOST_WIDE_INT
> > +mul_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool *overflow)
> > +{
> > + unsigned HOST_WIDE_INT result = a * (unsigned HOST_WIDE_INT)b;
> > + if (a != 0 && (HOST_WIDE_INT)result / a != b)
> > + *overflow = true;
> > + else
> > + *overflow = false;
>
> This isn't sufficiently bulletproof.
> It should be
> if ((a == -1 && b == HOST_WIDE_INT_MIN)
> || (a != 0 && (HOST_WIDE_INT)result / a != b))
> *overflow = true;
> else
> *overflow = false;
> or so.
>
> And except that a == -1 && b == min checks my recent widening_mul changes
> should match that to __builtin_mul_overflow, so it will not be perfect code,
> but at least will not be unnecessarily slow on x86.
OK, fixed. Guess we could also use __builtin_mul_overflow directly
if supported via a GCC_VERSION check. Looks like it's present
since GCC 5 at least. So sth like (incremental)
diff --git a/gcc/hwint.h b/gcc/hwint.h
index 53f4ed5dcad..6d2d491acfa 100644
--- a/gcc/hwint.h
+++ b/gcc/hwint.h
@@ -354,12 +354,19 @@ add_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool
*overflow)
inline HOST_WIDE_INT
mul_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool *overflow)
{
+#if GCC_VERSION < 5001
unsigned HOST_WIDE_INT result = a * (unsigned HOST_WIDE_INT)b;
- if (a != 0 && (HOST_WIDE_INT)result / a != b)
+ if ((a == -1 && b == HOST_WIDE_INT_MIN)
+ || (a != 0 && (HOST_WIDE_INT)result / a != b))
*overflow = true;
else
*overflow = false;
return result;
+#else
+ HOST_WIDE_INT result;
+ *overflow = __builtin_mul_overflow (a, b, &result);
+ return result;
+#endif
}
for the add case we should match all of the function I guess.
Richard.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] Handle overflow in dependence analysis lambda ops gracefully
2021-01-20 12:15 ` Richard Biener
@ 2021-01-20 12:19 ` Jakub Jelinek
2021-01-20 13:24 ` Richard Biener
0 siblings, 1 reply; 8+ messages in thread
From: Jakub Jelinek @ 2021-01-20 12:19 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches, richard.sandiford
On Wed, Jan 20, 2021 at 01:15:12PM +0100, Richard Biener wrote:
> OK, fixed. Guess we could also use __builtin_mul_overflow directly
> if supported via a GCC_VERSION check. Looks like it's present
> since GCC 5 at least. So sth like (incremental)
>
> diff --git a/gcc/hwint.h b/gcc/hwint.h
> index 53f4ed5dcad..6d2d491acfa 100644
> --- a/gcc/hwint.h
> +++ b/gcc/hwint.h
> @@ -354,12 +354,19 @@ add_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool
> *overflow)
> inline HOST_WIDE_INT
> mul_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool *overflow)
> {
> +#if GCC_VERSION < 5001
> unsigned HOST_WIDE_INT result = a * (unsigned HOST_WIDE_INT)b;
> - if (a != 0 && (HOST_WIDE_INT)result / a != b)
> + if ((a == -1 && b == HOST_WIDE_INT_MIN)
> + || (a != 0 && (HOST_WIDE_INT)result / a != b))
> *overflow = true;
> else
> *overflow = false;
> return result;
> +#else
> + HOST_WIDE_INT result;
> + *overflow = __builtin_mul_overflow (a, b, &result);
> + return result;
> +#endif
> }
>
> for the add case we should match all of the function I guess.
Yeah, sure.
Maybe bump somewhat the GCC_VERSION number in there, we've had bugs in
__builtin_mul_overflow expansion too.
Jakub
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] Handle overflow in dependence analysis lambda ops gracefully
2021-01-20 12:19 ` Jakub Jelinek
@ 2021-01-20 13:24 ` Richard Biener
2021-01-20 14:21 ` Richard Biener
0 siblings, 1 reply; 8+ messages in thread
From: Richard Biener @ 2021-01-20 13:24 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: gcc-patches, richard.sandiford
On Wed, 20 Jan 2021, Jakub Jelinek wrote:
> On Wed, Jan 20, 2021 at 01:15:12PM +0100, Richard Biener wrote:
> > OK, fixed. Guess we could also use __builtin_mul_overflow directly
> > if supported via a GCC_VERSION check. Looks like it's present
> > since GCC 5 at least. So sth like (incremental)
> >
> > diff --git a/gcc/hwint.h b/gcc/hwint.h
> > index 53f4ed5dcad..6d2d491acfa 100644
> > --- a/gcc/hwint.h
> > +++ b/gcc/hwint.h
> > @@ -354,12 +354,19 @@ add_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool
> > *overflow)
> > inline HOST_WIDE_INT
> > mul_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool *overflow)
> > {
> > +#if GCC_VERSION < 5001
> > unsigned HOST_WIDE_INT result = a * (unsigned HOST_WIDE_INT)b;
> > - if (a != 0 && (HOST_WIDE_INT)result / a != b)
> > + if ((a == -1 && b == HOST_WIDE_INT_MIN)
> > + || (a != 0 && (HOST_WIDE_INT)result / a != b))
> > *overflow = true;
> > else
> > *overflow = false;
> > return result;
> > +#else
> > + HOST_WIDE_INT result;
> > + *overflow = __builtin_mul_overflow (a, b, &result);
> > + return result;
> > +#endif
> > }
> >
> > for the add case we should match all of the function I guess.
>
> Yeah, sure.
> Maybe bump somewhat the GCC_VERSION number in there, we've had bugs in
> __builtin_mul_overflow expansion too.
Wow, a bugzilla search finds wrong-code that's only fixed in 9.3+.
So I guess I'll check for GCC 11+ then and not worry for stage1,
non-bootstrapped GCC or crosses with host != GCC 11.
Richard.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] Handle overflow in dependence analysis lambda ops gracefully
2021-01-20 13:24 ` Richard Biener
@ 2021-01-20 14:21 ` Richard Biener
2021-01-20 14:24 ` Richard Sandiford
0 siblings, 1 reply; 8+ messages in thread
From: Richard Biener @ 2021-01-20 14:21 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: gcc-patches, richard.sandiford
On Wed, 20 Jan 2021, Richard Biener wrote:
> On Wed, 20 Jan 2021, Jakub Jelinek wrote:
>
> > On Wed, Jan 20, 2021 at 01:15:12PM +0100, Richard Biener wrote:
> > > OK, fixed. Guess we could also use __builtin_mul_overflow directly
> > > if supported via a GCC_VERSION check. Looks like it's present
> > > since GCC 5 at least. So sth like (incremental)
> > >
> > > diff --git a/gcc/hwint.h b/gcc/hwint.h
> > > index 53f4ed5dcad..6d2d491acfa 100644
> > > --- a/gcc/hwint.h
> > > +++ b/gcc/hwint.h
> > > @@ -354,12 +354,19 @@ add_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool
> > > *overflow)
> > > inline HOST_WIDE_INT
> > > mul_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool *overflow)
> > > {
> > > +#if GCC_VERSION < 5001
> > > unsigned HOST_WIDE_INT result = a * (unsigned HOST_WIDE_INT)b;
> > > - if (a != 0 && (HOST_WIDE_INT)result / a != b)
> > > + if ((a == -1 && b == HOST_WIDE_INT_MIN)
> > > + || (a != 0 && (HOST_WIDE_INT)result / a != b))
> > > *overflow = true;
> > > else
> > > *overflow = false;
> > > return result;
> > > +#else
> > > + HOST_WIDE_INT result;
> > > + *overflow = __builtin_mul_overflow (a, b, &result);
> > > + return result;
> > > +#endif
> > > }
> > >
> > > for the add case we should match all of the function I guess.
> >
> > Yeah, sure.
> > Maybe bump somewhat the GCC_VERSION number in there, we've had bugs in
> > __builtin_mul_overflow expansion too.
>
> Wow, a bugzilla search finds wrong-code that's only fixed in 9.3+.
> So I guess I'll check for GCC 11+ then and not worry for stage1,
> non-bootstrapped GCC or crosses with host != GCC 11.
Like this. Bootstrapped / tested on x86_64-unknown-linux-gnu,
also covered add_hwi with __builtin_add_overflow now.
Richard.
From f188df08649f8ccadc808f084f0eba43a0cdd66e Mon Sep 17 00:00:00 2001
From: Richard Biener <rguenther@suse.de>
Date: Wed, 20 Jan 2021 11:28:30 +0100
Subject: [PATCH] Handle overflow in dependence analysis lambda ops gracefully
To: gcc-patches@gcc.gnu.org
The following tries to handle overflow in the integer computations
done by lambda ops of dependence analysis by failing instead of
silently continuing with overflowed values.
It also avoids treating large unsigned CHREC_RIGHT as negative
unless the chrec is of pointer type and avoids the most negative
integer value to avoid excessive overflow checking (with this
the fix for PR98758 can be partly simplified as seen).
I've added add_hwi and mul_hwi functions computing HOST_WIDE_INT
signed sum and product with indicating overflow, they hopefully
get matched to the appropriate internal functions.
I don't have any testcases triggering overflow in any of the
guarded computations.
2021-01-20 Richard Biener <rguenther@suse.de>
* hwint.h (add_hwi): New function.
(mul_hwi): Likewise.
* tree-data-ref.c (initialize_matrix_A): Properly translate
tree constants and avoid HOST_WIDE_INT_MIN.
(lambda_matrix_row_add): Avoid undefined integer overflow
and return true on such overflow.
(lambda_matrix_right_hermite): Handle overflow from
lambda_matrix_row_add gracefully. Simplify previous fix.
(analyze_subscript_affine_affine): Likewise.
---
gcc/hwint.h | 42 ++++++++++++++++++++++++++++++
gcc/tree-data-ref.c | 63 +++++++++++++++++++++++++++++++++++----------
2 files changed, 91 insertions(+), 14 deletions(-)
diff --git a/gcc/hwint.h b/gcc/hwint.h
index 127b0130c66..8812bc7150f 100644
--- a/gcc/hwint.h
+++ b/gcc/hwint.h
@@ -333,4 +333,46 @@ absu_hwi (HOST_WIDE_INT x)
return x >= 0 ? (unsigned HOST_WIDE_INT)x : -(unsigned HOST_WIDE_INT)x;
}
+/* Compute the sum of signed A and B and indicate in *OVERFLOW whether
+ that operation overflowed. */
+
+inline HOST_WIDE_INT
+add_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool *overflow)
+{
+#if GCC_VERSION < 11000
+ unsigned HOST_WIDE_INT result = a + b;
+ if ((((result ^ a) & (result ^ b))
+ >> (HOST_BITS_PER_WIDE_INT - 1)) & 1)
+ *overflow = true;
+ else
+ *overflow = false;
+ return result;
+#else
+ HOST_WIDE_INT result;
+ *overflow = __builtin_add_overflow (a, b, &result);
+ return result;
+#endif
+}
+
+/* Compute the product of signed A and B and indicate in *OVERFLOW whether
+ that operation overflowed. */
+
+inline HOST_WIDE_INT
+mul_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool *overflow)
+{
+#if GCC_VERSION < 11000
+ unsigned HOST_WIDE_INT result = a * (unsigned HOST_WIDE_INT)b;
+ if ((a == -1 && b == HOST_WIDE_INT_MIN)
+ || (a != 0 && (HOST_WIDE_INT)result / a != b))
+ *overflow = true;
+ else
+ *overflow = false;
+ return result;
+#else
+ HOST_WIDE_INT result;
+ *overflow = __builtin_mul_overflow (a, b, &result);
+ return result;
+#endif
+}
+
#endif /* ! GCC_HWINT_H */
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 9d07b415e9d..d19c5eb51e4 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -3924,9 +3924,25 @@ initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
- if (!cst_and_fits_in_hwi (CHREC_RIGHT (chrec)))
+ /* CHREC_RIGHT and its negated value should fit in a lambda_int.
+ Pointer typed chrecs right are to be interpreted signed. */
+ HOST_WIDE_INT chrec_right;
+ if (POINTER_TYPE_P (chrec_type (chrec)))
+ {
+ if (!cst_and_fits_in_hwi (CHREC_RIGHT (chrec)))
+ return chrec_dont_know;
+ chrec_right = int_cst_value (CHREC_RIGHT (chrec));
+ }
+ else
+ {
+ if (!tree_fits_shwi_p (CHREC_RIGHT (chrec)))
+ return chrec_dont_know;
+ chrec_right = tree_to_shwi (CHREC_RIGHT (chrec));
+ }
+ /* We want to be able to negate without overflow. */
+ if (chrec_right == HOST_WIDE_INT_MIN)
return chrec_dont_know;
- A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
+ A[index][0] = mult * chrec_right;
return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
case PLUS_EXPR:
@@ -4193,17 +4209,28 @@ lambda_vector_first_nz (lambda_vector vec1, int n, int start)
/* Add a multiple of row R1 of matrix MAT with N columns to row R2:
R2 = R2 + CONST1 * R1. */
-static void
+static bool
lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2,
lambda_int const1)
{
int i;
if (const1 == 0)
- return;
+ return true;
for (i = 0; i < n; i++)
- mat[r2][i] += const1 * mat[r1][i];
+ {
+ bool ovf;
+ lambda_int tem = mul_hwi (mat[r1][i], const1, &ovf);
+ if (ovf)
+ return false;
+ lambda_int tem2 = add_hwi (mat[r2][i], tem, &ovf);
+ if (ovf || tem2 == HOST_WIDE_INT_MIN)
+ return false;
+ mat[r2][i] = tem2;
+ }
+
+ return true;
}
/* Multiply vector VEC1 of length SIZE by a constant CONST1,
@@ -4258,7 +4285,7 @@ lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
Ref: Algorithm 2.1 page 33 in "Loop Transformations for
Restructuring Compilers" Utpal Banerjee. */
-static void
+static bool
lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
lambda_matrix S, lambda_matrix U)
{
@@ -4276,24 +4303,26 @@ lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
{
while (S[i][j] != 0)
{
- lambda_int sigma, factor, a, b;
+ lambda_int factor, a, b;
a = S[i-1][j];
b = S[i][j];
- sigma = ((a < 0) ^ (b < 0)) ? -1: 1;
- unsigned HOST_WIDE_INT abs_a = absu_hwi (a);
- unsigned HOST_WIDE_INT abs_b = absu_hwi (b);
- factor = sigma * (lambda_int)(abs_a / abs_b);
+ gcc_assert (a != HOST_WIDE_INT_MIN);
+ factor = a / b;
- lambda_matrix_row_add (S, n, i, i-1, -factor);
+ if (!lambda_matrix_row_add (S, n, i, i-1, -factor))
+ return false;
std::swap (S[i], S[i-1]);
- lambda_matrix_row_add (U, m, i, i-1, -factor);
+ if (!lambda_matrix_row_add (U, m, i, i-1, -factor))
+ return false;
std::swap (U[i], U[i-1]);
}
}
}
}
+
+ return true;
}
/* Determines the overlapping elements due to accesses CHREC_A and
@@ -4410,7 +4439,13 @@ analyze_subscript_affine_affine (tree chrec_a,
}
/* U.A = S */
- lambda_matrix_right_hermite (A, dim, 1, S, U);
+ if (!lambda_matrix_right_hermite (A, dim, 1, S, U))
+ {
+ *overlaps_a = conflict_fn_not_known ();
+ *overlaps_b = conflict_fn_not_known ();
+ *last_conflicts = chrec_dont_know;
+ goto end_analyze_subs_aa;
+ }
if (S[0][0] < 0)
{
--
2.26.2
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] Handle overflow in dependence analysis lambda ops gracefully
2021-01-20 14:21 ` Richard Biener
@ 2021-01-20 14:24 ` Richard Sandiford
2021-01-20 14:26 ` Richard Biener
0 siblings, 1 reply; 8+ messages in thread
From: Richard Sandiford @ 2021-01-20 14:24 UTC (permalink / raw)
To: Richard Biener; +Cc: Jakub Jelinek, gcc-patches
Richard Biener <rguenther@suse.de> writes:
> diff --git a/gcc/hwint.h b/gcc/hwint.h
> index 127b0130c66..8812bc7150f 100644
> --- a/gcc/hwint.h
> +++ b/gcc/hwint.h
> @@ -333,4 +333,46 @@ absu_hwi (HOST_WIDE_INT x)
> return x >= 0 ? (unsigned HOST_WIDE_INT)x : -(unsigned HOST_WIDE_INT)x;
> }
>
> +/* Compute the sum of signed A and B and indicate in *OVERFLOW whether
> + that operation overflowed. */
> +
> +inline HOST_WIDE_INT
> +add_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool *overflow)
> +{
> +#if GCC_VERSION < 11000
> + unsigned HOST_WIDE_INT result = a + b;
Sorry for the late comment, but shouldn't this cast a or b to
unsigned HOST_WIDE_INT?
Thanks,
Richard
> + if ((((result ^ a) & (result ^ b))
> + >> (HOST_BITS_PER_WIDE_INT - 1)) & 1)
> + *overflow = true;
> + else
> + *overflow = false;
> + return result;
> +#else
> + HOST_WIDE_INT result;
> + *overflow = __builtin_add_overflow (a, b, &result);
> + return result;
> +#endif
> +}
> +
> +/* Compute the product of signed A and B and indicate in *OVERFLOW whether
> + that operation overflowed. */
> +
> +inline HOST_WIDE_INT
> +mul_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool *overflow)
> +{
> +#if GCC_VERSION < 11000
> + unsigned HOST_WIDE_INT result = a * (unsigned HOST_WIDE_INT)b;
> + if ((a == -1 && b == HOST_WIDE_INT_MIN)
> + || (a != 0 && (HOST_WIDE_INT)result / a != b))
> + *overflow = true;
> + else
> + *overflow = false;
> + return result;
> +#else
> + HOST_WIDE_INT result;
> + *overflow = __builtin_mul_overflow (a, b, &result);
> + return result;
> +#endif
> +}
> +
> #endif /* ! GCC_HWINT_H */
> diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
> index 9d07b415e9d..d19c5eb51e4 100644
> --- a/gcc/tree-data-ref.c
> +++ b/gcc/tree-data-ref.c
> @@ -3924,9 +3924,25 @@ initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
> switch (TREE_CODE (chrec))
> {
> case POLYNOMIAL_CHREC:
> - if (!cst_and_fits_in_hwi (CHREC_RIGHT (chrec)))
> + /* CHREC_RIGHT and its negated value should fit in a lambda_int.
> + Pointer typed chrecs right are to be interpreted signed. */
> + HOST_WIDE_INT chrec_right;
> + if (POINTER_TYPE_P (chrec_type (chrec)))
> + {
> + if (!cst_and_fits_in_hwi (CHREC_RIGHT (chrec)))
> + return chrec_dont_know;
> + chrec_right = int_cst_value (CHREC_RIGHT (chrec));
> + }
> + else
> + {
> + if (!tree_fits_shwi_p (CHREC_RIGHT (chrec)))
> + return chrec_dont_know;
> + chrec_right = tree_to_shwi (CHREC_RIGHT (chrec));
> + }
> + /* We want to be able to negate without overflow. */
> + if (chrec_right == HOST_WIDE_INT_MIN)
> return chrec_dont_know;
> - A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
> + A[index][0] = mult * chrec_right;
> return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
>
> case PLUS_EXPR:
> @@ -4193,17 +4209,28 @@ lambda_vector_first_nz (lambda_vector vec1, int n, int start)
> /* Add a multiple of row R1 of matrix MAT with N columns to row R2:
> R2 = R2 + CONST1 * R1. */
>
> -static void
> +static bool
> lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2,
> lambda_int const1)
> {
> int i;
>
> if (const1 == 0)
> - return;
> + return true;
>
> for (i = 0; i < n; i++)
> - mat[r2][i] += const1 * mat[r1][i];
> + {
> + bool ovf;
> + lambda_int tem = mul_hwi (mat[r1][i], const1, &ovf);
> + if (ovf)
> + return false;
> + lambda_int tem2 = add_hwi (mat[r2][i], tem, &ovf);
> + if (ovf || tem2 == HOST_WIDE_INT_MIN)
> + return false;
> + mat[r2][i] = tem2;
> + }
> +
> + return true;
> }
>
> /* Multiply vector VEC1 of length SIZE by a constant CONST1,
> @@ -4258,7 +4285,7 @@ lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
> Ref: Algorithm 2.1 page 33 in "Loop Transformations for
> Restructuring Compilers" Utpal Banerjee. */
>
> -static void
> +static bool
> lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
> lambda_matrix S, lambda_matrix U)
> {
> @@ -4276,24 +4303,26 @@ lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
> {
> while (S[i][j] != 0)
> {
> - lambda_int sigma, factor, a, b;
> + lambda_int factor, a, b;
>
> a = S[i-1][j];
> b = S[i][j];
> - sigma = ((a < 0) ^ (b < 0)) ? -1: 1;
> - unsigned HOST_WIDE_INT abs_a = absu_hwi (a);
> - unsigned HOST_WIDE_INT abs_b = absu_hwi (b);
> - factor = sigma * (lambda_int)(abs_a / abs_b);
> + gcc_assert (a != HOST_WIDE_INT_MIN);
> + factor = a / b;
>
> - lambda_matrix_row_add (S, n, i, i-1, -factor);
> + if (!lambda_matrix_row_add (S, n, i, i-1, -factor))
> + return false;
> std::swap (S[i], S[i-1]);
>
> - lambda_matrix_row_add (U, m, i, i-1, -factor);
> + if (!lambda_matrix_row_add (U, m, i, i-1, -factor))
> + return false;
> std::swap (U[i], U[i-1]);
> }
> }
> }
> }
> +
> + return true;
> }
>
> /* Determines the overlapping elements due to accesses CHREC_A and
> @@ -4410,7 +4439,13 @@ analyze_subscript_affine_affine (tree chrec_a,
> }
>
> /* U.A = S */
> - lambda_matrix_right_hermite (A, dim, 1, S, U);
> + if (!lambda_matrix_right_hermite (A, dim, 1, S, U))
> + {
> + *overlaps_a = conflict_fn_not_known ();
> + *overlaps_b = conflict_fn_not_known ();
> + *last_conflicts = chrec_dont_know;
> + goto end_analyze_subs_aa;
> + }
>
> if (S[0][0] < 0)
> {
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] Handle overflow in dependence analysis lambda ops gracefully
2021-01-20 14:24 ` Richard Sandiford
@ 2021-01-20 14:26 ` Richard Biener
0 siblings, 0 replies; 8+ messages in thread
From: Richard Biener @ 2021-01-20 14:26 UTC (permalink / raw)
To: Richard Sandiford; +Cc: Jakub Jelinek, gcc-patches
On Wed, 20 Jan 2021, Richard Sandiford wrote:
> Richard Biener <rguenther@suse.de> writes:
> > diff --git a/gcc/hwint.h b/gcc/hwint.h
> > index 127b0130c66..8812bc7150f 100644
> > --- a/gcc/hwint.h
> > +++ b/gcc/hwint.h
> > @@ -333,4 +333,46 @@ absu_hwi (HOST_WIDE_INT x)
> > return x >= 0 ? (unsigned HOST_WIDE_INT)x : -(unsigned HOST_WIDE_INT)x;
> > }
> >
> > +/* Compute the sum of signed A and B and indicate in *OVERFLOW whether
> > + that operation overflowed. */
> > +
> > +inline HOST_WIDE_INT
> > +add_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool *overflow)
> > +{
> > +#if GCC_VERSION < 11000
> > + unsigned HOST_WIDE_INT result = a + b;
>
> Sorry for the late comment, but shouldn't this cast a or b to
> unsigned HOST_WIDE_INT?
Yes ...
> Thanks,
> Richard
>
> > + if ((((result ^ a) & (result ^ b))
> > + >> (HOST_BITS_PER_WIDE_INT - 1)) & 1)
> > + *overflow = true;
> > + else
> > + *overflow = false;
> > + return result;
> > +#else
> > + HOST_WIDE_INT result;
> > + *overflow = __builtin_add_overflow (a, b, &result);
> > + return result;
> > +#endif
> > +}
> > +
> > +/* Compute the product of signed A and B and indicate in *OVERFLOW whether
> > + that operation overflowed. */
> > +
> > +inline HOST_WIDE_INT
> > +mul_hwi (HOST_WIDE_INT a, HOST_WIDE_INT b, bool *overflow)
> > +{
> > +#if GCC_VERSION < 11000
> > + unsigned HOST_WIDE_INT result = a * (unsigned HOST_WIDE_INT)b;
> > + if ((a == -1 && b == HOST_WIDE_INT_MIN)
> > + || (a != 0 && (HOST_WIDE_INT)result / a != b))
> > + *overflow = true;
> > + else
> > + *overflow = false;
> > + return result;
> > +#else
> > + HOST_WIDE_INT result;
> > + *overflow = __builtin_mul_overflow (a, b, &result);
> > + return result;
> > +#endif
> > +}
> > +
> > #endif /* ! GCC_HWINT_H */
> > diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
> > index 9d07b415e9d..d19c5eb51e4 100644
> > --- a/gcc/tree-data-ref.c
> > +++ b/gcc/tree-data-ref.c
> > @@ -3924,9 +3924,25 @@ initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
> > switch (TREE_CODE (chrec))
> > {
> > case POLYNOMIAL_CHREC:
> > - if (!cst_and_fits_in_hwi (CHREC_RIGHT (chrec)))
> > + /* CHREC_RIGHT and its negated value should fit in a lambda_int.
> > + Pointer typed chrecs right are to be interpreted signed. */
> > + HOST_WIDE_INT chrec_right;
> > + if (POINTER_TYPE_P (chrec_type (chrec)))
> > + {
> > + if (!cst_and_fits_in_hwi (CHREC_RIGHT (chrec)))
> > + return chrec_dont_know;
> > + chrec_right = int_cst_value (CHREC_RIGHT (chrec));
> > + }
> > + else
> > + {
> > + if (!tree_fits_shwi_p (CHREC_RIGHT (chrec)))
> > + return chrec_dont_know;
> > + chrec_right = tree_to_shwi (CHREC_RIGHT (chrec));
> > + }
> > + /* We want to be able to negate without overflow. */
> > + if (chrec_right == HOST_WIDE_INT_MIN)
> > return chrec_dont_know;
> > - A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
> > + A[index][0] = mult * chrec_right;
> > return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
> >
> > case PLUS_EXPR:
> > @@ -4193,17 +4209,28 @@ lambda_vector_first_nz (lambda_vector vec1, int n, int start)
> > /* Add a multiple of row R1 of matrix MAT with N columns to row R2:
> > R2 = R2 + CONST1 * R1. */
> >
> > -static void
> > +static bool
> > lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2,
> > lambda_int const1)
> > {
> > int i;
> >
> > if (const1 == 0)
> > - return;
> > + return true;
> >
> > for (i = 0; i < n; i++)
> > - mat[r2][i] += const1 * mat[r1][i];
> > + {
> > + bool ovf;
> > + lambda_int tem = mul_hwi (mat[r1][i], const1, &ovf);
> > + if (ovf)
> > + return false;
> > + lambda_int tem2 = add_hwi (mat[r2][i], tem, &ovf);
> > + if (ovf || tem2 == HOST_WIDE_INT_MIN)
> > + return false;
> > + mat[r2][i] = tem2;
> > + }
> > +
> > + return true;
> > }
> >
> > /* Multiply vector VEC1 of length SIZE by a constant CONST1,
> > @@ -4258,7 +4285,7 @@ lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
> > Ref: Algorithm 2.1 page 33 in "Loop Transformations for
> > Restructuring Compilers" Utpal Banerjee. */
> >
> > -static void
> > +static bool
> > lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
> > lambda_matrix S, lambda_matrix U)
> > {
> > @@ -4276,24 +4303,26 @@ lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
> > {
> > while (S[i][j] != 0)
> > {
> > - lambda_int sigma, factor, a, b;
> > + lambda_int factor, a, b;
> >
> > a = S[i-1][j];
> > b = S[i][j];
> > - sigma = ((a < 0) ^ (b < 0)) ? -1: 1;
> > - unsigned HOST_WIDE_INT abs_a = absu_hwi (a);
> > - unsigned HOST_WIDE_INT abs_b = absu_hwi (b);
> > - factor = sigma * (lambda_int)(abs_a / abs_b);
> > + gcc_assert (a != HOST_WIDE_INT_MIN);
> > + factor = a / b;
> >
> > - lambda_matrix_row_add (S, n, i, i-1, -factor);
> > + if (!lambda_matrix_row_add (S, n, i, i-1, -factor))
> > + return false;
> > std::swap (S[i], S[i-1]);
> >
> > - lambda_matrix_row_add (U, m, i, i-1, -factor);
> > + if (!lambda_matrix_row_add (U, m, i, i-1, -factor))
> > + return false;
> > std::swap (U[i], U[i-1]);
> > }
> > }
> > }
> > }
> > +
> > + return true;
> > }
> >
> > /* Determines the overlapping elements due to accesses CHREC_A and
> > @@ -4410,7 +4439,13 @@ analyze_subscript_affine_affine (tree chrec_a,
> > }
> >
> > /* U.A = S */
> > - lambda_matrix_right_hermite (A, dim, 1, S, U);
> > + if (!lambda_matrix_right_hermite (A, dim, 1, S, U))
> > + {
> > + *overlaps_a = conflict_fn_not_known ();
> > + *overlaps_b = conflict_fn_not_known ();
> > + *last_conflicts = chrec_dont_know;
> > + goto end_analyze_subs_aa;
> > + }
> >
> > if (S[0][0] < 0)
> > {
>
--
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2021-01-20 14:26 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-01-20 11:29 [PATCH] Handle overflow in dependence analysis lambda ops gracefully Richard Biener
2021-01-20 11:33 ` Jakub Jelinek
2021-01-20 12:15 ` Richard Biener
2021-01-20 12:19 ` Jakub Jelinek
2021-01-20 13:24 ` Richard Biener
2021-01-20 14:21 ` Richard Biener
2021-01-20 14:24 ` Richard Sandiford
2021-01-20 14:26 ` Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).