From patchwork Fri Jul 19 14:22:49 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 1134108 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-505342-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=ucw.cz Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="x8TGVk6A"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 45qtWt4k6Kz9s00 for ; Sat, 20 Jul 2019 00:23:04 +1000 (AEST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=OByOsQFTscAV7ESTPj5y6GJWsYphjS+IMd9VV/YHMaJf8BCpiR0Ms QzZBAP227xl3xgaegAaAFiVbChyfg5xP3LQDSpPK7BD6DSLxDNfU7H66UvmmyNOu 7I0Mg4bl0lOdgSI6BK2sXYq1JQSib/ixUaIWFwUnAA5EsB3Ohg8c+0= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=q2Oxk3EltXiLI0W50WuYVRlloKU=; b=x8TGVk6A4aw0FXYipu8+ xWV04mLk2GIpIWVHu4sTTmtFto1A4xjhmYYh+mZIeVxzLCSsQXGRgYuJwcc25xXQ F0CvfA5K/lLrNm+TdMxX1OguHz4mqdwUOdggUgl7v792UeH0IR/cQh+/TxTrBJ5g JEdmuH4EWkOSSZQxHigo4Ag= Received: (qmail 16424 invoked by alias); 19 Jul 2019 14:22:55 -0000 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 Received: (qmail 16414 invoked by uid 89); 19 Jul 2019 14:22:55 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-9.6 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS autolearn=ham version=3.3.1 spammy=statistics, bases, ARRAY_TYPE, disambiguation X-HELO: nikam.ms.mff.cuni.cz Received: from nikam.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 19 Jul 2019 14:22:52 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id 771F828264E; Fri, 19 Jul 2019 16:22:49 +0200 (CEST) Date: Fri, 19 Jul 2019 16:22:49 +0200 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, rguenther@suse.de, d@dcepelik.cz Subject: Add ARRAY_REF based access patch disambiguation Message-ID: <20190719142249.e7fuzf3exlfb437j@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: NeoMutt/20170113 (1.7.2) Hi, this patch adds bare bones of disambiguation of access paths via ARRAY_REF. Similarly to COMPONENT_REF we need a matched ARRAY_REF size and prove that indexes are actually different. This adds about 20 new disambiguations to tramp3d. Bootstrapped/regtested x86_64-linux, OK? * tree-ssa-alias.c (nonoverlapping_component_refs_since_match_p): Rename to ... (nonoverlapping_refs_since_match_p): ... this; handle also ARRAY_REFs. (alias_stats): Update stats. (dump_alias_stats): Likewise. (aliasing_matching_component_refs_p): Add partial_overlap argument; pass it to nonoverlapping_refs_since_match_p. (aliasing_component_refs_walk): Update call of aliasing_matching_component_refs_p (nonoverlapping_array_refs_p): New function. (decl_refs_may_alias_p, indirect_ref_may_alias_decl_p, indirect_refs_may_alias_p): Update calls of nonoverlapping_refs_since_match_p. * gcc.dg/tree-ssa/alias-access-path-10.c: New testcase. Index: tree-ssa-alias.c =================================================================== --- tree-ssa-alias.c (revision 273570) +++ tree-ssa-alias.c (working copy) @@ -87,7 +87,7 @@ along with GCC; see the file COPYING3. this file. Low-level disambiguators dealing with points-to information are in tree-ssa-structalias.c. */ -static int nonoverlapping_component_refs_since_match_p (tree, tree, tree, tree); +static int nonoverlapping_refs_since_match_p (tree, tree, tree, tree, bool); static bool nonoverlapping_component_refs_p (const_tree, const_tree); /* Query statistics for the different low-level disambiguators. @@ -104,9 +104,9 @@ static struct { unsigned HOST_WIDE_INT aliasing_component_refs_p_no_alias; unsigned HOST_WIDE_INT nonoverlapping_component_refs_p_may_alias; unsigned HOST_WIDE_INT nonoverlapping_component_refs_p_no_alias; - unsigned HOST_WIDE_INT nonoverlapping_component_refs_since_match_p_may_alias; - unsigned HOST_WIDE_INT nonoverlapping_component_refs_since_match_p_must_overlap; - unsigned HOST_WIDE_INT nonoverlapping_component_refs_since_match_p_no_alias; + unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_may_alias; + unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_must_overlap; + unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_no_alias; } alias_stats; void @@ -137,15 +137,15 @@ dump_alias_stats (FILE *s) alias_stats.nonoverlapping_component_refs_p_no_alias, alias_stats.nonoverlapping_component_refs_p_no_alias + alias_stats.nonoverlapping_component_refs_p_may_alias); - fprintf (s, " nonoverlapping_component_refs_since_match_p: " + fprintf (s, " nonoverlapping_refs_since_match_p: " HOST_WIDE_INT_PRINT_DEC" disambiguations, " HOST_WIDE_INT_PRINT_DEC" must overlaps, " HOST_WIDE_INT_PRINT_DEC" queries\n", - alias_stats.nonoverlapping_component_refs_since_match_p_no_alias, - alias_stats.nonoverlapping_component_refs_since_match_p_must_overlap, - alias_stats.nonoverlapping_component_refs_since_match_p_no_alias - + alias_stats.nonoverlapping_component_refs_since_match_p_may_alias - + alias_stats.nonoverlapping_component_refs_since_match_p_must_overlap); + alias_stats.nonoverlapping_refs_since_match_p_no_alias, + alias_stats.nonoverlapping_refs_since_match_p_must_overlap, + alias_stats.nonoverlapping_refs_since_match_p_no_alias + + alias_stats.nonoverlapping_refs_since_match_p_may_alias + + alias_stats.nonoverlapping_refs_since_match_p_must_overlap); fprintf (s, " aliasing_component_refs_p: " HOST_WIDE_INT_PRINT_DEC" disambiguations, " HOST_WIDE_INT_PRINT_DEC" queries\n", @@ -856,7 +856,8 @@ type_has_components_p (tree type) /* MATCH1 and MATCH2 which are part of access path of REF1 and REF2 respectively are either pointing to same address or are completely - disjoint. + disjoint. If PARITAL_OVERLAP is true, assume that outermost arrays may + just partly overlap. Try to disambiguate using the access path starting from the match and return false if there is no conflict. @@ -867,24 +868,27 @@ static bool aliasing_matching_component_refs_p (tree match1, tree ref1, poly_int64 offset1, poly_int64 max_size1, tree match2, tree ref2, - poly_int64 offset2, poly_int64 max_size2) + poly_int64 offset2, poly_int64 max_size2, + bool partial_overlap) { poly_int64 offadj, sztmp, msztmp; bool reverse; - - get_ref_base_and_extent (match2, &offadj, &sztmp, &msztmp, &reverse); - offset2 -= offadj; - get_ref_base_and_extent (match1, &offadj, &sztmp, &msztmp, &reverse); - offset1 -= offadj; - if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2)) + if (!partial_overlap) { - ++alias_stats.aliasing_component_refs_p_no_alias; - return false; + get_ref_base_and_extent (match2, &offadj, &sztmp, &msztmp, &reverse); + offset2 -= offadj; + get_ref_base_and_extent (match1, &offadj, &sztmp, &msztmp, &reverse); + offset1 -= offadj; + if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2)) + { + ++alias_stats.aliasing_component_refs_p_no_alias; + return false; + } } - int cmp = nonoverlapping_component_refs_since_match_p (match1, ref1, - match2, ref2); + int cmp = nonoverlapping_refs_since_match_p (match1, ref1, match2, ref2, + partial_overlap); if (cmp == 1 || (cmp == -1 && nonoverlapping_component_refs_p (ref1, ref2))) { @@ -964,6 +968,8 @@ aliasing_component_refs_walk (tree ref1, } if (same_p == 1) { + bool partial_overlap = false; + /* We assume that arrays can overlap by multiple of their elements size as tested in gcc.dg/torture/alias-2.c. This partial overlap happen only when both arrays are bases of @@ -973,15 +979,18 @@ aliasing_component_refs_walk (tree ref1, && (!TYPE_SIZE (TREE_TYPE (base1)) || TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) != INTEGER_CST || ref == base2)) - /* Setting maybe_match to true triggers - nonoverlapping_component_refs_p test later that still may do - useful disambiguation. */ - *maybe_match = true; - else - return aliasing_matching_component_refs_p (base1, ref1, - offset1, max_size1, - ref, ref2, - offset2, max_size2); + { + /* Setting maybe_match to true triggers + nonoverlapping_component_refs_p test later that still may do + useful disambiguation. */ + *maybe_match = true; + partial_overlap = true; + } + return aliasing_matching_component_refs_p (base1, ref1, + offset1, max_size1, + ref, ref2, + offset2, max_size2, + partial_overlap); } return -1; } @@ -1225,10 +1234,57 @@ nonoverlapping_component_refs_p_1 (const return -1; } +/* REF1 and REF2 are ARRAY_REFs which either start at the same address or + are completely disjoint. + + Return 1 if the refs are non-overlapping. + Return 0 if they are possibly overlapping but if so the overlap again + starts on the same address. + Return -1 otherwise. */ + +int +nonoverlapping_array_refs_p (tree ref1, tree ref2) +{ + tree low_bound1 = array_ref_low_bound (ref1); + tree low_bound2 = array_ref_low_bound (ref2); + tree index1 = TREE_OPERAND (ref1, 1); + tree index2 = TREE_OPERAND (ref2, 1); + + /* Handle zero offsets first: we do not need to match type size in this + case. */ + if (operand_equal_p (index1, low_bound1, 0) + && operand_equal_p (index2, low_bound2, 0)) + return 0; + + /* If type sizes are different, give up. */ + if (!operand_equal_p (array_ref_element_size (ref1), + array_ref_element_size (ref2), 0)) + return -1; + + /* Since we know that type sizes are the same, there is no need to return + -1 after this point, since partial overlap can not be introduced. */ + + /* We may need to fold trees in this case. + TODO: Handle integer constant case at least. */ + if (!operand_equal_p (low_bound1, low_bound2, 0)) + return 0; + + if (TREE_CODE (index1) == INTEGER_CST && TREE_CODE (index2) == INTEGER_CST) + { + if (tree_int_cst_equal (index1, index2)) + return 0; + return 1; + } + /* TODO: We can use VRP to further disambiguate here. */ + return 0; +} + /* Try to disambiguate REF1 and REF2 under the assumption that MATCH1 and MATCH2 either point to the same address or are disjoint. MATCH1 and MATCH2 are assumed to be ref in the access path of REF1 and REF2 respectively or NULL in the case we established equivalence of bases. + If PARTIAL_OVERLAP is true assume that the toplevel arrays may actually + overlap by exact multiply of their element size. This test works by matching the initial segment of the access path and does not rely on TBAA thus is safe for !flag_strict_aliasing if @@ -1247,8 +1303,9 @@ nonoverlapping_component_refs_p_1 (const oracles. */ static int -nonoverlapping_component_refs_since_match_p (tree match1, tree ref1, - tree match2, tree ref2) +nonoverlapping_refs_since_match_p (tree match1, tree ref1, + tree match2, tree ref2, + bool partial_overlap) { /* Early return if there are no references to match, we do not need to walk the access paths. @@ -1301,7 +1358,7 @@ nonoverlapping_component_refs_since_matc && !tree_int_cst_equal (TREE_OPERAND (ref1, 1), TREE_OPERAND (ref2, 1)))) { - ++alias_stats.nonoverlapping_component_refs_since_match_p_may_alias; + ++alias_stats.nonoverlapping_refs_since_match_p_may_alias; return -1; } @@ -1318,18 +1375,75 @@ nonoverlapping_component_refs_since_matc case the return value will precisely be false. */ while (true) { - bool seen_noncomponent_ref_p = false; + /* Track if we seen unmatched ref with non-zero offset. In this case + we must look for partial overlaps. */ + bool seen_unmatched_ref_p = false; + + /* First match ARRAY_REFs an try to disambiguate. */ + if (!component_refs1.is_empty () + && !component_refs2.is_empty ()) + { + unsigned int narray_refs1=0, narray_refs2=0; + + /* We generally assume that both access paths starts by same sequence + of refs. However if number of array refs is not in sync, try + to recover and pop elts until number match. This helps the case + where one access path starts by array and other by element. */ + for (narray_refs1 = 0; narray_refs1 < component_refs1.length (); + narray_refs1++) + if (TREE_CODE (component_refs1 [component_refs1.length() + - 1 - narray_refs1]) != ARRAY_REF) + break; + + for (narray_refs2 = 0; narray_refs2 < component_refs2.length (); + narray_refs2++) + if (TREE_CODE (component_refs2 [component_refs2.length() + - 1 - narray_refs2]) != ARRAY_REF) + break; + for (; narray_refs1 > narray_refs2; narray_refs1--) + { + ref1 = component_refs1.pop (); + if (!operand_equal_p (TREE_OPERAND (ref1, 1), + array_ref_low_bound (ref1), 0)) + seen_unmatched_ref_p = true; + } + for (; narray_refs2 > narray_refs1; narray_refs2--) + { + ref2 = component_refs2.pop (); + if (!operand_equal_p (TREE_OPERAND (ref2, 1), + array_ref_low_bound (ref2), 0)) + seen_unmatched_ref_p = true; + } + /* Try to disambiguate matched arrays. */ + for (unsigned int i = 0; i < narray_refs1; i++) + { + int cmp = nonoverlapping_array_refs_p (component_refs1.pop (), + component_refs2.pop ()); + if (cmp == 1 && !partial_overlap) + { + ++alias_stats + .nonoverlapping_refs_since_match_p_no_alias; + return 1; + } + partial_overlap = false; + if (cmp == -1) + seen_unmatched_ref_p = true; + } + } + + /* Next look for component_refs. */ + do { if (component_refs1.is_empty ()) { ++alias_stats - .nonoverlapping_component_refs_since_match_p_must_overlap; + .nonoverlapping_refs_since_match_p_must_overlap; return 0; } ref1 = component_refs1.pop (); if (TREE_CODE (ref1) != COMPONENT_REF) - seen_noncomponent_ref_p = true; + seen_unmatched_ref_p = true; } while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref1, 0)))); @@ -1338,12 +1452,12 @@ nonoverlapping_component_refs_since_matc if (component_refs2.is_empty ()) { ++alias_stats - .nonoverlapping_component_refs_since_match_p_must_overlap; + .nonoverlapping_refs_since_match_p_must_overlap; return 0; } ref2 = component_refs2.pop (); if (TREE_CODE (ref2) != COMPONENT_REF) - seen_noncomponent_ref_p = true; + seen_unmatched_ref_p = true; } while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref2, 0)))); @@ -1361,13 +1475,15 @@ nonoverlapping_component_refs_since_matc tree type1 = DECL_CONTEXT (field1); tree type2 = DECL_CONTEXT (field2); + partial_overlap = false; + /* If we skipped array refs on type of different sizes, we can no longer be sure that there are not partial overlaps. */ - if (seen_noncomponent_ref_p + if (seen_unmatched_ref_p && !operand_equal_p (TYPE_SIZE (type1), TYPE_SIZE (type2), 0)) { ++alias_stats - .nonoverlapping_component_refs_since_match_p_may_alias; + .nonoverlapping_refs_since_match_p_may_alias; return -1; } @@ -1375,18 +1491,18 @@ nonoverlapping_component_refs_since_matc if (cmp == -1) { ++alias_stats - .nonoverlapping_component_refs_since_match_p_may_alias; + .nonoverlapping_refs_since_match_p_may_alias; return -1; } else if (cmp == 1) { ++alias_stats - .nonoverlapping_component_refs_since_match_p_no_alias; + .nonoverlapping_refs_since_match_p_no_alias; return 1; } } - ++alias_stats.nonoverlapping_component_refs_since_match_p_must_overlap; + ++alias_stats.nonoverlapping_refs_since_match_p_must_overlap; return 0; } @@ -1583,8 +1699,7 @@ decl_refs_may_alias_p (tree ref1, tree b so we disambiguate component references manually. */ if (ref1 && ref2 && handled_component_p (ref1) && handled_component_p (ref2) - && nonoverlapping_component_refs_since_match_p (NULL, ref1, - NULL, ref2) == 1) + && nonoverlapping_refs_since_match_p (NULL, ref1, NULL, ref2, false) == 1) return false; return true; @@ -1709,19 +1824,22 @@ indirect_ref_may_alias_decl_p (tree ref1 || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1))) && (TREE_CODE (dbase2) != TARGET_MEM_REF || (!TMR_INDEX (dbase2) && !TMR_INDEX2 (dbase2)))) - && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (dbase2)) == 1 - && (TREE_CODE (TREE_TYPE (base1)) != ARRAY_TYPE - || (TYPE_SIZE (TREE_TYPE (base1)) - && TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) == INTEGER_CST))) + && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (dbase2)) == 1) { - if (!ranges_maybe_overlap_p (doffset1, max_size1, doffset2, max_size2)) + bool partial_overlap = (TREE_CODE (TREE_TYPE (base1)) == ARRAY_TYPE + && (TYPE_SIZE (TREE_TYPE (base1)) + && TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) + != INTEGER_CST)); + if (!partial_overlap + && !ranges_maybe_overlap_p (doffset1, max_size1, doffset2, max_size2)) return false; if (!ref1 || !ref2 /* If there is must alias, there is no use disambiguating further. */ - || (known_eq (size1, max_size1) && known_eq (size2, max_size2))) + || (!partial_overlap + && known_eq (size1, max_size1) && known_eq (size2, max_size2))) return true; - int res = nonoverlapping_component_refs_since_match_p (base1, ref1, - base2, ref2); + int res = nonoverlapping_refs_since_match_p (base1, ref1, base2, ref2, + partial_overlap); if (res == -1) return !nonoverlapping_component_refs_p (ref1, ref2); return !res; @@ -1805,8 +1923,8 @@ indirect_refs_may_alias_p (tree ref1 ATT return true; if (ref1 && ref2) { - int res = nonoverlapping_component_refs_since_match_p (NULL, ref1, - NULL, ref2); + int res = nonoverlapping_refs_since_match_p (NULL, ref1, NULL, ref2, + false); if (res != -1) return !res; } @@ -1844,19 +1962,22 @@ indirect_refs_may_alias_p (tree ref1 ATT && (TREE_CODE (base2) != TARGET_MEM_REF || (!TMR_INDEX (base2) && !TMR_INDEX2 (base2))) && same_type_for_tbaa (TREE_TYPE (ptrtype1), - TREE_TYPE (ptrtype2)) == 1 + TREE_TYPE (ptrtype2)) == 1) + { /* But avoid treating arrays as "objects", instead assume they can overlap by an exact multiple of their element size. See gcc.dg/torture/alias-2.c. */ - && TREE_CODE (TREE_TYPE (ptrtype1)) != ARRAY_TYPE) - { - if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2)) + bool partial_overlap = TREE_CODE (TREE_TYPE (ptrtype1)) == ARRAY_TYPE; + + if (!partial_overlap + && !ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2)) return false; if (!ref1 || !ref2 - || (known_eq (size1, max_size1) && known_eq (size2, max_size2))) + || (!partial_overlap + && known_eq (size1, max_size1) && known_eq (size2, max_size2))) return true; - int res = nonoverlapping_component_refs_since_match_p (base1, ref1, - base2, ref2); + int res = nonoverlapping_refs_since_match_p (base1, ref1, base2, ref2, + partial_overlap); if (res == -1) return !nonoverlapping_component_refs_p (ref1, ref2); return !res; Index: testsuite/gcc.dg/tree-ssa/alias-access-path-10.c =================================================================== --- testsuite/gcc.dg/tree-ssa/alias-access-path-10.c (nonexistent) +++ testsuite/gcc.dg/tree-ssa/alias-access-path-10.c (working copy) @@ -0,0 +1,12 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-fre1" } */ + +struct a {int array[3];} a[10]; +int +test(int i,int j) +{ + a[i].array[1]=123; + a[j].array[2]=2; + return a[i].array[1]; +} +/* { dg-final { scan-tree-dump-times "return 123" 1 "fre1"} } */