From patchwork Wed Mar 31 10:15:08 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 1460462 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@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=uU+f+DKi; 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 4F9MdL3NKkz9sWQ for ; Wed, 31 Mar 2021 21:15:17 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 654CE385700A; Wed, 31 Mar 2021 10:15:14 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 654CE385700A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1617185714; bh=6+9FEco64McB5uNyqpWvBVt6t2f5e5DCBlUeqRQYBqY=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=uU+f+DKiCSMmUx9a0O2y6CK1heKmkcVZ4lAtW7ixbQe5NFXtsyJXpHKxWm5/0xRtA MLS7n6EVtxoS17bdm59PED4a00Hs5rITPRrfuyZRZx0tEr1m5d1RVkhMWzwsAvXYsm A4i1DUEEfRawOKlT88fQiWcWNoQ6riENr0zD+OEU= 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 AC97B3858012 for ; Wed, 31 Mar 2021 10:15:10 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org AC97B3858012 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 3D66611B3 for ; Wed, 31 Mar 2021 03:15:10 -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 BC6473F792 for ; Wed, 31 Mar 2021 03:15:09 -0700 (PDT) To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Subject: [PATCH] data-ref: Tighten index-based alias checks [PR99726] Date: Wed, 31 Mar 2021 11:15:08 +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.2 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_ASCII_DIVIDERS, KAM_DMARC_STATUS, 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-Patchwork-Original-From: Richard Sandiford via Gcc-patches From: Richard Sandiford Reply-To: Richard Sandiford Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" create_intersect_range_checks_index tries to create a runtime alias check based on index comparisons. It looks through the access functions for the two DRs to find a SCEV for the loop that is being versioned and converts a DR_STEP-based check into an index-based check. However, there isn't any reliable sign information in the types, so the code expects the value of the IV step (when interpreted as signed) to be negative iff the DR_STEP (when interpreted as signed) is negative. r10-4762 added another assert related to this assumption and the assert fired for the testcase in the PR. The sign of the IV step didn't match the sign of the DR_STEP. I think this is actually showing what was previously a wrong-code bug. The signs didn't match because the DRs contained *two* access function SCEVs for the loop being versioned. It doesn't look like the code is set up to deal with this, since it checks each access function independently and treats it as the sole source of DR_STEP. The patch therefore moves the main condition out of the loop. This also has the advantage of not building a tree for one access function only to throw it away if we find an inner function that makes the comparison invalid. Tested on aarch64-linux-gnu, armeb-eabi and x86_64-linux-gnu. OK to install? Richard gcc/ PR tree-optimization/99726 * tree-data-ref.c (create_intersect_range_checks_index): Bail out if there is more than one access function SCEV for the loop being versioned. gcc/testsuite/ PR tree-optimization/99726 * gcc.target/i386/pr99726.c: New test. --- gcc/testsuite/gcc.target/i386/pr99726.c | 15 ++ gcc/tree-data-ref.c | 245 +++++++++++++----------- 2 files changed, 143 insertions(+), 117 deletions(-) create mode 100644 gcc/testsuite/gcc.target/i386/pr99726.c [ -b version ]-------------------------------------------------------------- diff --git a/gcc/testsuite/gcc.target/i386/pr99726.c b/gcc/testsuite/gcc.target/i386/pr99726.c new file mode 100644 index 00000000000..ff19bcabe4f --- /dev/null +++ b/gcc/testsuite/gcc.target/i386/pr99726.c @@ -0,0 +1,15 @@ +/* { dg-options "-flive-patching=inline-clone -mavx512f -O2 -floop-nest-optimize -ftree-loop-vectorize -ftrapv -m32" } */ + +extern int a[256][1024]; +int b; +long c, d; +unsigned int e; + +int +main () +{ + for (; e < d; e++) + for (unsigned j = 1; j < c; j++) + a[e][j] = b * a[e - 1][j + 1]; + return 0; +} diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 124a7bea6a9..e6dd5f15bed 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -2147,8 +2147,8 @@ create_intersect_range_checks_index (class loop *loop, tree *cond_expr, bool waw_or_war_p = (alias_pair.flags & ~(DR_ALIAS_WAR | DR_ALIAS_WAW)) == 0; - unsigned int i; - for (i = 0; i < DR_NUM_DIMENSIONS (dr_a.dr); i++) + int found = -1; + for (unsigned int i = 0; i < DR_NUM_DIMENSIONS (dr_a.dr); i++) { tree access1 = DR_ACCESS_FN (dr_a.dr, i); tree access2 = DR_ACCESS_FN (dr_b.dr, i); @@ -2164,7 +2164,19 @@ create_intersect_range_checks_index (class loop *loop, tree *cond_expr, return false; } + if (found >= 0) + return false; + found = i; + } + + /* Ought not to happen in practice, since if all accesses are equal then the + alias should be decidable at compile time. */ + if (found < 0) + return false; + /* The two indices must have the same step. */ + tree access1 = DR_ACCESS_FN (dr_a.dr, found); + tree access2 = DR_ACCESS_FN (dr_b.dr, found); if (!operand_equal_p (CHREC_RIGHT (access1), CHREC_RIGHT (access2), 0)) return false; @@ -2221,7 +2233,7 @@ create_intersect_range_checks_index (class loop *loop, tree *cond_expr, When checking for general overlap, we need to test whether the range: - [min1 + low_offset1, min2 + high_offset1 + idx_access1 - 1] + [min1 + low_offset1, min1 + high_offset1 + idx_access1 - 1] overlaps: @@ -2312,7 +2324,6 @@ create_intersect_range_checks_index (class loop *loop, tree *cond_expr, *cond_expr, part_cond_expr); else *cond_expr = part_cond_expr; - } if (dump_enabled_p ()) { if (waw_or_war_p) [ Real patch ]-------------------------------------------------------------- diff --git a/gcc/testsuite/gcc.target/i386/pr99726.c b/gcc/testsuite/gcc.target/i386/pr99726.c new file mode 100644 index 00000000000..ff19bcabe4f --- /dev/null +++ b/gcc/testsuite/gcc.target/i386/pr99726.c @@ -0,0 +1,15 @@ +/* { dg-options "-flive-patching=inline-clone -mavx512f -O2 -floop-nest-optimize -ftree-loop-vectorize -ftrapv -m32" } */ + +extern int a[256][1024]; +int b; +long c, d; +unsigned int e; + +int +main () +{ + for (; e < d; e++) + for (unsigned j = 1; j < c; j++) + a[e][j] = b * a[e - 1][j + 1]; + return 0; +} diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 124a7bea6a9..e6dd5f15bed 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -2147,8 +2147,8 @@ create_intersect_range_checks_index (class loop *loop, tree *cond_expr, bool waw_or_war_p = (alias_pair.flags & ~(DR_ALIAS_WAR | DR_ALIAS_WAW)) == 0; - unsigned int i; - for (i = 0; i < DR_NUM_DIMENSIONS (dr_a.dr); i++) + int found = -1; + for (unsigned int i = 0; i < DR_NUM_DIMENSIONS (dr_a.dr); i++) { tree access1 = DR_ACCESS_FN (dr_a.dr, i); tree access2 = DR_ACCESS_FN (dr_b.dr, i); @@ -2164,155 +2164,166 @@ create_intersect_range_checks_index (class loop *loop, tree *cond_expr, return false; } - /* The two indices must have the same step. */ - if (!operand_equal_p (CHREC_RIGHT (access1), CHREC_RIGHT (access2), 0)) + if (found >= 0) return false; + found = i; + } - tree idx_step = CHREC_RIGHT (access1); - /* Index must have const step, otherwise DR_STEP won't be constant. */ - gcc_assert (TREE_CODE (idx_step) == INTEGER_CST); - /* Index must evaluate in the same direction as DR. */ - gcc_assert (!neg_step || tree_int_cst_sign_bit (idx_step) == 1); + /* Ought not to happen in practice, since if all accesses are equal then the + alias should be decidable at compile time. */ + if (found < 0) + return false; - tree min1 = CHREC_LEFT (access1); - tree min2 = CHREC_LEFT (access2); - if (!types_compatible_p (TREE_TYPE (min1), TREE_TYPE (min2))) - return false; + /* The two indices must have the same step. */ + tree access1 = DR_ACCESS_FN (dr_a.dr, found); + tree access2 = DR_ACCESS_FN (dr_b.dr, found); + if (!operand_equal_p (CHREC_RIGHT (access1), CHREC_RIGHT (access2), 0)) + return false; - /* Ideally, alias can be checked against loop's control IV, but we - need to prove linear mapping between control IV and reference - index. Although that should be true, we check against (array) - index of data reference. Like segment length, index length is - linear function of the number of iterations with index_step as - the coefficient, i.e, niter_len * idx_step. */ - offset_int abs_idx_step = offset_int::from (wi::to_wide (idx_step), - SIGNED); - if (neg_step) - abs_idx_step = -abs_idx_step; - poly_offset_int idx_len1 = abs_idx_step * niter_len1; - poly_offset_int idx_len2 = abs_idx_step * niter_len2; - poly_offset_int idx_access1 = abs_idx_step * niter_access1; - poly_offset_int idx_access2 = abs_idx_step * niter_access2; + tree idx_step = CHREC_RIGHT (access1); + /* Index must have const step, otherwise DR_STEP won't be constant. */ + gcc_assert (TREE_CODE (idx_step) == INTEGER_CST); + /* Index must evaluate in the same direction as DR. */ + gcc_assert (!neg_step || tree_int_cst_sign_bit (idx_step) == 1); - gcc_assert (known_ge (idx_len1, 0) - && known_ge (idx_len2, 0) - && known_ge (idx_access1, 0) - && known_ge (idx_access2, 0)); + tree min1 = CHREC_LEFT (access1); + tree min2 = CHREC_LEFT (access2); + if (!types_compatible_p (TREE_TYPE (min1), TREE_TYPE (min2))) + return false; - /* Each access has the following pattern, with lengths measured - in units of INDEX: + /* Ideally, alias can be checked against loop's control IV, but we + need to prove linear mapping between control IV and reference + index. Although that should be true, we check against (array) + index of data reference. Like segment length, index length is + linear function of the number of iterations with index_step as + the coefficient, i.e, niter_len * idx_step. */ + offset_int abs_idx_step = offset_int::from (wi::to_wide (idx_step), + SIGNED); + if (neg_step) + abs_idx_step = -abs_idx_step; + poly_offset_int idx_len1 = abs_idx_step * niter_len1; + poly_offset_int idx_len2 = abs_idx_step * niter_len2; + poly_offset_int idx_access1 = abs_idx_step * niter_access1; + poly_offset_int idx_access2 = abs_idx_step * niter_access2; - <-- idx_len --> - <--- A: -ve step ---> - +-----+-------+-----+-------+-----+ - | n-1 | ..... | 0 | ..... | n-1 | - +-----+-------+-----+-------+-----+ - <--- B: +ve step ---> - <-- idx_len --> - | - min + gcc_assert (known_ge (idx_len1, 0) + && known_ge (idx_len2, 0) + && known_ge (idx_access1, 0) + && known_ge (idx_access2, 0)); - where "n" is the number of scalar iterations covered by the segment - and where each access spans idx_access units. + /* Each access has the following pattern, with lengths measured + in units of INDEX: - A is the range of bytes accessed when the step is negative, - B is the range when the step is positive. + <-- idx_len --> + <--- A: -ve step ---> + +-----+-------+-----+-------+-----+ + | n-1 | ..... | 0 | ..... | n-1 | + +-----+-------+-----+-------+-----+ + <--- B: +ve step ---> + <-- idx_len --> + | + min - When checking for general overlap, we need to test whether - the range: + where "n" is the number of scalar iterations covered by the segment + and where each access spans idx_access units. - [min1 + low_offset1, min2 + high_offset1 + idx_access1 - 1] + A is the range of bytes accessed when the step is negative, + B is the range when the step is positive. - overlaps: + When checking for general overlap, we need to test whether + the range: - [min2 + low_offset2, min2 + high_offset2 + idx_access2 - 1] + [min1 + low_offset1, min1 + high_offset1 + idx_access1 - 1] - where: + overlaps: + + [min2 + low_offset2, min2 + high_offset2 + idx_access2 - 1] - low_offsetN = +ve step ? 0 : -idx_lenN; - high_offsetN = +ve step ? idx_lenN : 0; + where: - This is equivalent to testing whether: + low_offsetN = +ve step ? 0 : -idx_lenN; + high_offsetN = +ve step ? idx_lenN : 0; + + This is equivalent to testing whether: - min1 + low_offset1 <= min2 + high_offset2 + idx_access2 - 1 - && min2 + low_offset2 <= min1 + high_offset1 + idx_access1 - 1 + min1 + low_offset1 <= min2 + high_offset2 + idx_access2 - 1 + && min2 + low_offset2 <= min1 + high_offset1 + idx_access1 - 1 - Converting this into a single test, there is an overlap if: + Converting this into a single test, there is an overlap if: - 0 <= min2 - min1 + bias <= limit + 0 <= min2 - min1 + bias <= limit - where bias = high_offset2 + idx_access2 - 1 - low_offset1 - limit = (high_offset1 - low_offset1 + idx_access1 - 1) - + (high_offset2 - low_offset2 + idx_access2 - 1) - i.e. limit = idx_len1 + idx_access1 - 1 + idx_len2 + idx_access2 - 1 + where bias = high_offset2 + idx_access2 - 1 - low_offset1 + limit = (high_offset1 - low_offset1 + idx_access1 - 1) + + (high_offset2 - low_offset2 + idx_access2 - 1) + i.e. limit = idx_len1 + idx_access1 - 1 + idx_len2 + idx_access2 - 1 - Combining the tests requires limit to be computable in an unsigned - form of the index type; if it isn't, we fall back to the usual - pointer-based checks. + Combining the tests requires limit to be computable in an unsigned + form of the index type; if it isn't, we fall back to the usual + pointer-based checks. - We can do better if DR_B is a write and if DR_A and DR_B are - well-ordered in both the original and the new code (see the - comment above the DR_ALIAS_* flags for details). In this case - we know that for each i in [0, n-1], the write performed by - access i of DR_B occurs after access numbers j<=i of DR_A in - both the original and the new code. Any write or anti - dependencies wrt those DR_A accesses are therefore maintained. + We can do better if DR_B is a write and if DR_A and DR_B are + well-ordered in both the original and the new code (see the + comment above the DR_ALIAS_* flags for details). In this case + we know that for each i in [0, n-1], the write performed by + access i of DR_B occurs after access numbers j<=i of DR_A in + both the original and the new code. Any write or anti + dependencies wrt those DR_A accesses are therefore maintained. - We just need to make sure that each individual write in DR_B does not - overlap any higher-indexed access in DR_A; such DR_A accesses happen - after the DR_B access in the original code but happen before it in - the new code. + We just need to make sure that each individual write in DR_B does not + overlap any higher-indexed access in DR_A; such DR_A accesses happen + after the DR_B access in the original code but happen before it in + the new code. - We know the steps for both accesses are equal, so by induction, we - just need to test whether the first write of DR_B overlaps a later - access of DR_A. In other words, we need to move min1 along by - one iteration: + We know the steps for both accesses are equal, so by induction, we + just need to test whether the first write of DR_B overlaps a later + access of DR_A. In other words, we need to move min1 along by + one iteration: - min1' = min1 + idx_step + min1' = min1 + idx_step - and use the ranges: + and use the ranges: - [min1' + low_offset1', min1' + high_offset1' + idx_access1 - 1] + [min1' + low_offset1', min1' + high_offset1' + idx_access1 - 1] - and: + and: - [min2, min2 + idx_access2 - 1] + [min2, min2 + idx_access2 - 1] - where: + where: - low_offset1' = +ve step ? 0 : -(idx_len1 - |idx_step|) - high_offset1' = +ve_step ? idx_len1 - |idx_step| : 0. */ - if (waw_or_war_p) - idx_len1 -= abs_idx_step; + low_offset1' = +ve step ? 0 : -(idx_len1 - |idx_step|) + high_offset1' = +ve_step ? idx_len1 - |idx_step| : 0. */ + if (waw_or_war_p) + idx_len1 -= abs_idx_step; - poly_offset_int limit = idx_len1 + idx_access1 - 1 + idx_access2 - 1; - if (!waw_or_war_p) - limit += idx_len2; + poly_offset_int limit = idx_len1 + idx_access1 - 1 + idx_access2 - 1; + if (!waw_or_war_p) + limit += idx_len2; - tree utype = unsigned_type_for (TREE_TYPE (min1)); - if (!wi::fits_to_tree_p (limit, utype)) - return false; + tree utype = unsigned_type_for (TREE_TYPE (min1)); + if (!wi::fits_to_tree_p (limit, utype)) + return false; - poly_offset_int low_offset1 = neg_step ? -idx_len1 : 0; - poly_offset_int high_offset2 = neg_step || waw_or_war_p ? 0 : idx_len2; - poly_offset_int bias = high_offset2 + idx_access2 - 1 - low_offset1; - /* Equivalent to adding IDX_STEP to MIN1. */ - if (waw_or_war_p) - bias -= wi::to_offset (idx_step); - - tree subject = fold_build2 (MINUS_EXPR, utype, - fold_convert (utype, min2), - fold_convert (utype, min1)); - subject = fold_build2 (PLUS_EXPR, utype, subject, - wide_int_to_tree (utype, bias)); - tree part_cond_expr = fold_build2 (GT_EXPR, boolean_type_node, subject, - wide_int_to_tree (utype, limit)); - if (*cond_expr) - *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, - *cond_expr, part_cond_expr); - else - *cond_expr = part_cond_expr; - } + poly_offset_int low_offset1 = neg_step ? -idx_len1 : 0; + poly_offset_int high_offset2 = neg_step || waw_or_war_p ? 0 : idx_len2; + poly_offset_int bias = high_offset2 + idx_access2 - 1 - low_offset1; + /* Equivalent to adding IDX_STEP to MIN1. */ + if (waw_or_war_p) + bias -= wi::to_offset (idx_step); + + tree subject = fold_build2 (MINUS_EXPR, utype, + fold_convert (utype, min2), + fold_convert (utype, min1)); + subject = fold_build2 (PLUS_EXPR, utype, subject, + wide_int_to_tree (utype, bias)); + tree part_cond_expr = fold_build2 (GT_EXPR, boolean_type_node, subject, + wide_int_to_tree (utype, limit)); + if (*cond_expr) + *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, + *cond_expr, part_cond_expr); + else + *cond_expr = part_cond_expr; if (dump_enabled_p ()) { if (waw_or_war_p)