From patchwork Tue Jul 2 09:14:48 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 1126092 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-504145-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="FM3KSWj0"; 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 45dJVs4Jbyz9sNs for ; Tue, 2 Jul 2019 19:15:27 +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=ntVc2vInjsLNXk2mWWW+rnOI6A8NYmZWOdus05qnYKtAyQJuQSOil r1HQETUf9pVRsb7+u9LtCPJ2tFospB5nkXXppPe0IINFnVY/xdjuLv9CabB5afR7 5d4hnKyR/GMQJbAPB9GMr7vfaKywte+iHndGMO5FA8AQNf+h50uhps= 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=NkNiCBNU0f8ifQiE5Ruy76XjGFU=; b=FM3KSWj0VE02P7895GiA ck7uaAANMFYOPPWD0cxvrqR4/EBUkesVsy6p7ukPmyhG6E8L87PXEsn/5DTcd27d rNA2OVKDFaQYD9A+/uw5X3IJgXhqVubOqVR9NThfQqtfInVPhmg2vqxRM3aXru1A KNHj02yFnJtXwJV3+Ed4Qc0= Received: (qmail 32604 invoked by alias); 2 Jul 2019 09:15:12 -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 32401 invoked by uid 89); 2 Jul 2019 09:15:03 -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=fre3 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; Tue, 02 Jul 2019 09:14:58 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id 7B3BC28083C; Tue, 2 Jul 2019 11:14:48 +0200 (CEST) Date: Tue, 2 Jul 2019 11:14:48 +0200 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, d@dcepelik.cz, rguenther@suse.de Subject: Enable nonoverallping_component_refs even after the base pointers are equivalent Message-ID: <20190702091448.jeum2qlk33d7ddl4@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: NeoMutt/20170113 (1.7.2) Hi, this patch adds the shortcut for must aliases discussed earlier and enables access path even if bases are proved to be equivalent - it could still do useful job for arrays etc. tramp3d stats go from: Alias oracle query stats: refs_may_alias_p: 4421560 disambiguations, 4781790 queries ref_maybe_used_by_call_p: 6790 disambiguations, 4447962 queries call_may_clobber_ref_p: 883 disambiguations, 883 queries nonoverlapping_component_refs_p: 0 disambiguations, 9272 queries nonoverlapping_component_refs_since_match_p: 31 disambiguations, 39391 queries aliasing_component_refs_p: 918 disambiguations, 30889 queries TBAA oracle: 1924468 disambiguations 3851145 queries 774336 are in alias set 0 714019 queries asked about the same object 0 queries asked about the same alias set 0 access volatile 282546 are dependent in the DAG 155776 are aritificially in conflict with void * to Alias oracle query stats: refs_may_alias_p: 4421611 disambiguations, 4781828 queries ref_maybe_used_by_call_p: 6790 disambiguations, 4448013 queries call_may_clobber_ref_p: 883 disambiguations, 883 queries nonoverlapping_component_refs_p: 0 disambiguations, 8964 queries nonoverlapping_component_refs_since_match_p: 66 disambiguations, 18470 queries aliasing_component_refs_p: 918 disambiguations, 30371 queries TBAA oracle: 1924492 disambiguations 3849967 queries 774336 are in alias set 0 714095 queries asked about the same object 0 queries asked about the same alias set 0 access volatile 281268 are dependent in the DAG 155776 are aritificially in conflict with void * PTA query stats: pt_solution_includes: 906632 disambiguations, 1214744 queries pt_solutions_intersect: 121330 disambiguations, 553172 queries So twice as many nonoverlapping_component_refs_since_match_p disambiguations, half of querries. We can miss some of disambiguations where addresses are same but types are different, but I think those are not useful - this is the case where memory type was dynamically changed. If we walk with TBAA enabled and see the prevoius use, we got kind of lost anyway and propagating even older values seems to have no use. Note that i tried to implement ranges_must_overlap_p predicate which could save us from more tests but got lost in polyints and I think it is not worth the effort since these cases are quite borderline. Similar test would make sense in aliasing_component_refs_p but I think it may make more sense to reorder the tests there. Right now we do: 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)) First I think that one get_ref_base_and_extent is always redundant since either match1 or match2 is base so we could pass it down. However it seems to me that perhaps doing nonoverlapping_component_refs_since_match_p would be cheaper and one can do the range check only after this one returns -1 saving quite many get_ref_base_and_extent calls. Bootstrapped/regtested x86_64-linux, OK? Honza Index: testsuite/gcc.dg/tree-ssa/alias-access-path-3.c =================================================================== --- testsuite/gcc.dg/tree-ssa/alias-access-path-3.c (nonexistent) +++ testsuite/gcc.dg/tree-ssa/alias-access-path-3.c (working copy) @@ -0,0 +1,22 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-fre1" } */ +struct a {int v1; + int v2;}; +struct b {struct a a[0];}; + +int +test (struct b *bptr1, struct b *bptr2, int i, int j) +{ + bptr1->a[i].v1=123; + bptr2->a[j].v2=1; + return bptr1->a[i].v1; +} +int +test2 (struct b *bptr1, struct b *bptr2, int i, int j) +{ + bptr1->a[i].v1=123; + bptr2->a[j].v1=1; + return bptr1->a[i].v1; +} +/* test should be optimized, while test2 should not. */ +/* { dg-final { scan-tree-dump-times "return 123" 1 "fre1"} } */ Index: testsuite/gcc.dg/tree-ssa/alias-access-path-8.c =================================================================== --- testsuite/gcc.dg/tree-ssa/alias-access-path-8.c (nonexistent) +++ testsuite/gcc.dg/tree-ssa/alias-access-path-8.c (working copy) @@ -0,0 +1,21 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-fre3" } */ +struct a { + int val; +}; +struct b { + struct a a[10],a2[10]; +}; +struct c { + struct b b[10]; +} *cptr,*cptr2; + + +int +test (int i, int j, int k, int l) +{ + cptr->b[i].a[j].val=123; + cptr2->b[k].a2[l].val=2; + return cptr->b[i].a[j].val; +} +/* { dg-final { scan-tree-dump-times "return 123" 1 "fre3"} } */ Index: tree-ssa-alias.c =================================================================== --- tree-ssa-alias.c (revision 272927) +++ tree-ssa-alias.c (working copy) @@ -1452,8 +1452,10 @@ nonoverlapping_component_refs_p (const_t static bool decl_refs_may_alias_p (tree ref1, tree base1, poly_int64 offset1, poly_int64 max_size1, + poly_int64 size1, tree ref2, tree base2, - poly_int64 offset2, poly_int64 max_size2) + poly_int64 offset2, poly_int64 max_size2, + poly_int64 size2) { gcc_checking_assert (DECL_P (base1) && DECL_P (base2)); @@ -1466,6 +1468,10 @@ decl_refs_may_alias_p (tree ref1, tree b if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2)) return false; + /* If there is must alias, there is no use disambiguating further. */ + if (known_eq (size1, max_size1) && known_eq (size2, max_size2)) + return true; + /* For components with variable position, the above test isn't sufficient, so we disambiguate component references manually. */ if (ref1 && ref2 @@ -1487,10 +1493,12 @@ decl_refs_may_alias_p (tree ref1, tree b static bool indirect_ref_may_alias_decl_p (tree ref1 ATTRIBUTE_UNUSED, tree base1, poly_int64 offset1, poly_int64 max_size1, + poly_int64 size1, alias_set_type ref1_alias_set, alias_set_type base1_alias_set, tree ref2 ATTRIBUTE_UNUSED, tree base2, poly_int64 offset2, poly_int64 max_size2, + poly_int64 size2, alias_set_type ref2_alias_set, alias_set_type base2_alias_set, bool tbaa_p) { @@ -1598,7 +1606,19 @@ indirect_ref_may_alias_decl_p (tree ref1 && (TREE_CODE (TREE_TYPE (base1)) != ARRAY_TYPE || (TYPE_SIZE (TREE_TYPE (base1)) && TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) == INTEGER_CST))) - return ranges_maybe_overlap_p (doffset1, max_size1, doffset2, max_size2); + { + if (!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))) + return true; + int res = nonoverlapping_component_refs_since_match_p (base1, ref1, + base2, ref2); + if (res == -1) + return !nonoverlapping_component_refs_p (ref1, ref2); + return !res; + } /* Do access-path based disambiguation. */ if (ref1 && ref2 @@ -1623,10 +1643,12 @@ indirect_ref_may_alias_decl_p (tree ref1 static bool indirect_refs_may_alias_p (tree ref1 ATTRIBUTE_UNUSED, tree base1, poly_int64 offset1, poly_int64 max_size1, + poly_int64 size1, alias_set_type ref1_alias_set, alias_set_type base1_alias_set, tree ref2 ATTRIBUTE_UNUSED, tree base2, poly_int64 offset2, poly_int64 max_size2, + poly_int64 size2, alias_set_type ref2_alias_set, alias_set_type base2_alias_set, bool tbaa_p) { @@ -1671,6 +1693,9 @@ indirect_refs_may_alias_p (tree ref1 ATT if (!ranges_maybe_overlap_p (offset1 + moff1, max_size1, offset2 + moff2, max_size2)) return false; + /* If there is must alias, there is no use disambiguating further. */ + if (known_eq (size1, max_size1) && known_eq (size2, max_size2)) + return true; if (ref1 && ref2) { int res = nonoverlapping_component_refs_since_match_p (NULL, ref1, @@ -1717,7 +1742,18 @@ indirect_refs_may_alias_p (tree ref1 ATT can overlap by an exact multiple of their element size. See gcc.dg/torture/alias-2.c. */ && TREE_CODE (TREE_TYPE (ptrtype1)) != ARRAY_TYPE) - return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2); + { + if (!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))) + return true; + int res = nonoverlapping_component_refs_since_match_p (base1, ref1, + base2, ref2); + if (res == -1) + return !nonoverlapping_component_refs_p (ref1, ref2); + return !res; + } /* Do access-path based disambiguation. */ if (ref1 && ref2 @@ -1802,7 +1838,9 @@ refs_may_alias_p_2 (ao_ref *ref1, ao_ref var2_p = DECL_P (base2); if (var1_p && var2_p) return decl_refs_may_alias_p (ref1->ref, base1, offset1, max_size1, - ref2->ref, base2, offset2, max_size2); + ref1->size, + ref2->ref, base2, offset2, max_size2, + ref2->size); /* Handle restrict based accesses. ??? ao_ref_base strips inner MEM_REF [&decl], recover from that @@ -1870,21 +1908,21 @@ refs_may_alias_p_2 (ao_ref *ref1, ao_ref /* Dispatch to the pointer-vs-decl or pointer-vs-pointer disambiguators. */ if (var1_p && ind2_p) return indirect_ref_may_alias_decl_p (ref2->ref, base2, - offset2, max_size2, + offset2, max_size2, ref2->size, ao_ref_alias_set (ref2), ao_ref_base_alias_set (ref2), ref1->ref, base1, - offset1, max_size1, + offset1, max_size1, ref1->size, ao_ref_alias_set (ref1), ao_ref_base_alias_set (ref1), tbaa_p); else if (ind1_p && ind2_p) return indirect_refs_may_alias_p (ref1->ref, base1, - offset1, max_size1, + offset1, max_size1, ref1->size, ao_ref_alias_set (ref1), ao_ref_base_alias_set (ref1), ref2->ref, base2, - offset2, max_size2, + offset2, max_size2, ref2->size, ao_ref_alias_set (ref2), ao_ref_base_alias_set (ref2), tbaa_p);