From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx2.suse.de (mx2.suse.de [195.135.220.15]) by sourceware.org (Postfix) with ESMTPS id 54F0F3950C61 for ; Wed, 20 Jan 2021 11:29:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 54F0F3950C61 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=rguenther@suse.de X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 5BD66B278; Wed, 20 Jan 2021 11:29:24 +0000 (UTC) Date: Wed, 20 Jan 2021 12:29:23 +0100 (CET) From: Richard Biener Sender: rguenther@ryzen.fritz.box To: gcc-patches@gcc.gnu.org cc: jakub@redhat.com, richard.sandiford@arm.com Subject: [PATCH] Handle overflow in dependence analysis lambda ops gracefully Message-ID: User-Agent: Alpine 2.21 (LSU 202 2017-01-01) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Spam-Status: No, score=-11.5 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_STATUS, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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-List-Received-Date: Wed, 20 Jan 2021 11:29:27 -0000 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 * 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