From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 118989 invoked by alias); 9 Jul 2019 12:14:35 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 118942 invoked by uid 89); 9 Jul 2019 12:14:31 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-10.4 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_2,GIT_PATCH_3,KAM_ASCII_DIVIDERS,SPF_PASS autolearn=ham version=3.3.1 spammy=vertical X-HELO: mx1.suse.de Received: from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 09 Jul 2019 12:14:28 +0000 Received: from relay2.suse.de (unknown [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id 31073AD5D; Tue, 9 Jul 2019 12:14:26 +0000 (UTC) Date: Tue, 09 Jul 2019 12:21:00 -0000 From: Richard Biener To: Jan Hubicka cc: gcc-patches@gcc.gnu.org, d@dcepelik.cz Subject: Re: Make nonoverlapping_component_refs work with duplicated main variants In-Reply-To: <20190709114917.qva4nb2h7j5vzdur@kam.mff.cuni.cz> Message-ID: References: <20190708072649.vqd5u6jxsz5ybtt7@kam.mff.cuni.cz> <20190709114917.qva4nb2h7j5vzdur@kam.mff.cuni.cz> User-Agent: Alpine 2.20 (LSU 67 2015-01-07) MIME-Version: 1.0 Content-Type: multipart/mixed; BOUNDARY="-1609908220-2137534706-1562674466=:2976" X-SW-Source: 2019-07/txt/msg00685.txt.bz2 This message is in MIME format. The first part should be readable text, while the remaining parts are likely unreadable without MIME-aware tools. ---1609908220-2137534706-1562674466=:2976 Content-Type: text/plain; charset=ISO-8859-15 Content-Transfer-Encoding: 8BIT Content-length: 16530 On Tue, 9 Jul 2019, Jan Hubicka wrote: > Hi, > this is updated patch. I based the logic on gimple_compare_field_offset but > dropped bits about PLACEHOLDER_EXPR since my understanding is that to get > comparsion done I would then need to compare operand #2 of COMPONENT_REF which > I don't. > > I also wrote the range checks using polyint since I believe that most code is > supposed to be updated this way (shall we update gimple_compare_field_offset? For consistency yes I guess but IIRC they cannot really appear in FIELD_DECLs. > It is used in canonical type merging and considering fields different may lead > to wrong code I would say, but I do not know enough about SVE to construct > testcase). > > I updated documentation of return values which I also find somewhat confusing > since 1/0 meanings in nonoverlapping_* is reversed compared to > aliasing_component_refs. Main entry is called refs_may_alias so I am > considering rename all the functions into *_may_alias and make them return 0 > for disambiguation, 1 for non-disambiguation and use -1's to keep decidion > whether to work harder. > > However for now I am sticking with the nonoverlapping reversed semantics. > > > There are no changes in tramp3d stats (there are no unmerged types) > Here are stats on cc1plus build: > > Alias oracle query stats: > refs_may_alias_p: 43435216 disambiguations, 51989307 queries > ref_maybe_used_by_call_p: 60843 disambiguations, 44040532 queries > call_may_clobber_ref_p: 6051 disambiguations, 9115 queries > nonoverlapping_component_refs_p: 0 disambiguations, 2535 queries > nonoverlapping_component_refs_since_match_p: 12297 disambiguations, 40458 must overlaps, 53243 queries > aliasing_component_refs_p: 70892 disambiguations, 374789 queries > TBAA oracle: 12680127 disambiguations 32179405 queries > 10383370 are in alias set 0 > 5747729 queries asked about the same object > 148 queries asked about the same alias set > 0 access volatile > 2482808 are dependent in the DAG > 885223 are aritificially in conflict with void * > > PTA query stats: > pt_solution_includes: 562382 disambiguations, 7467931 queries > pt_solutions_intersect: 412873 disambiguations, 7818955 queries > > It seems that nonoverlapping_component_refs_since_match_p is pretty good on > making decision and there are only few cases where it return -1 which is good. > So i guess teaching it about ARRAY_REFs is logical next step. > > If I would like to benchmark alias oracle compile time, what is > reasonable way to do that? > > Bootstrapped/regtested x86_64-linux, OK? > > Honza > > * tree-ssa-alias.c (nonoverlapping_component_refs_p_1): Break out > from ...; work also on duplicated types. > (nonoverlapping_component_refs_since_match): ... here > (ncr_type_uid): Break out from ... > (ncr_compar): ... here; look for TYPE_UID of canonical type if > available. > (nonoverlapping_component_refs_p): Use same_type_for_tbaa to match > the types and nonoverlapping_component_refs_p_1 to disambiguate. > * g++.dg/lto/alias-3_0.C: New file. > * g++.dg/lto/alias-3_1.c: New file. > > Index: tree-ssa-alias.c > =================================================================== > --- tree-ssa-alias.c (revision 273193) > +++ tree-ssa-alias.c (working copy) > @@ -1128,6 +1128,90 @@ aliasing_component_refs_p (tree ref1, > return false; > } > > +/* FIELD1 and FIELD2 are two component refs whose bases either do > + not overlap at all or their addresses are the same. > + > + Return 1 if FIELD1 and FIELD2 are non-overlapping > + > + Return 0 if FIELD1 and FIELD2 are posisbly overlapping but in case of > + overlap their addresses are the same. > + > + Return -1 otherwise. > + > + Main difference between 0 and -1 is to let > + nonoverlapping_component_refs_since_match_p discover the semnatically > + equivalent part of the access path. */ > + > +static int > +nonoverlapping_component_refs_p_1 (const_tree field1, const_tree field2) > +{ > + /* If both fields are of the same type, we could save hard work of > + comparing offsets. > + ??? We cannot simply use the type of operand #0 of the refs here > + as the Fortran compiler smuggles type punning into COMPONENT_REFs > + for common blocks instead of using unions like everyone else. */ > + tree type1 = DECL_CONTEXT (field1); > + tree type2 = DECL_CONTEXT (field2); > + drop the vertical space > + if (type1 == type2 && TREE_CODE (type1) == RECORD_TYPE) > + { > + if (field1 == field2) > + return 0; > + /* A field and its representative need to be considered the > + same. */ > + if (DECL_BIT_FIELD_REPRESENTATIVE (field1) == field2 > + || DECL_BIT_FIELD_REPRESENTATIVE (field2) == field1) > + return 0; > + /* Different fields of the same record type cannot overlap. > + ??? Bitfields can overlap at RTL level so punt on them. */ > + if (DECL_BIT_FIELD (field1) && DECL_BIT_FIELD (field2)) > + return 0; > + /* Assume that different FIELD_DECLs never overlap in a RECORD_TYPE. */ > + return 1; > + } > + else > + { drop the else { > + /* Different fields of the same record type cannot overlap. > + ??? Bitfields can overlap at RTL level so punt on them. */ > + if (DECL_BIT_FIELD (field1) && DECL_BIT_FIELD (field2)) > + return 0; > + don't you need the DECL_BIT_FIELD_REPRESENTATIVE check here as well? I'd do if (DECL_BIT_FIELD_REPRESENTATIVE (field1)) field1 = DECL_BIT_FIELD_REPRESENTATIVE (field1); if (DECL_BIT_FIELD_REPRESENTATIVE (field2)) field2 = DECL_BIT_FIELD_REPRESENTATIVE (field2); thus use the representative for the overlap check. It might be the case that we can improve here and if we do this can do the DECL_BIT_FIELD check after this (hoping the representative doesn't have it set). > + if (tree_int_cst_equal (DECL_FIELD_OFFSET (field1), > + DECL_FIELD_OFFSET (field2)) > + && tree_int_cst_equal (DECL_FIELD_BIT_OFFSET (field1), > + DECL_FIELD_BIT_OFFSET (field2))) > + return 0; In gimple_compare_field_offset this was fast-pathed for DECL_OFFSET_ALIGN (f1) == DECL_OFFSET_ALIGN (f2) so I suggest to do that here as well. Note that DECL_FIELD_OFFSET can be a non-constant which means you cannot use tree_int_cst_equal unconditionally here but you have to use operand_equal_p. > + /* Note that it may be possible to use component_ref_field_offset > + which would provide offsets as trees. However constructing and folding > + trees is expensive and does not seem to be worth the compile time > + cost. */ > + > + poly_uint64 offset1, offset2; > + poly_uint64 bit_offset1, bit_offset2; > + poly_uint64 size1, size2; I think you need poly_offset_int here since you convert to bits below. The gimple_compare_field_offset checking way looks cheaper btw, so I wonder why you don't simply call it but replicate things here? When do we expect to have partially overlapping field decls? Even when considering canonical type merging? > + if (poly_int_tree_p (DECL_FIELD_OFFSET (field1), &offset1) > + && poly_int_tree_p (DECL_FIELD_OFFSET (field2), &offset2) > + && poly_int_tree_p (DECL_FIELD_BIT_OFFSET (field1), &bit_offset1) > + && poly_int_tree_p (DECL_FIELD_BIT_OFFSET (field2), &bit_offset2) > + && poly_int_tree_p (DECL_SIZE (field1), &size1) > + && poly_int_tree_p (DECL_SIZE (field2), &size2)) > + { > + offset1 = (offset1 << LOG2_BITS_PER_UNIT) + bit_offset1; > + offset2 = (offset2 << LOG2_BITS_PER_UNIT) + bit_offset2; > + > + if (known_eq (offset1, offset2)) > + return 0; > + if (!ranges_maybe_overlap_p (offset1, size1, offset2, size2)) > + return 1; > + } > + } > + /* Resort to slower overlap checking by looking for matching types in > + the middle of access path. */ > + return -1; > +} > + > /* 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 > @@ -1224,6 +1308,7 @@ nonoverlapping_component_refs_since_matc > case the return value will precisely be false. */ > while (true) > { > + bool seen_noncomponent_ref_p = false; > do > { > if (component_refs1.is_empty ()) > @@ -1233,6 +1318,8 @@ nonoverlapping_component_refs_since_matc > return 0; > } > ref1 = component_refs1.pop (); > + if (TREE_CODE (ref1) != COMPONENT_REF) > + seen_noncomponent_ref_p = true; > } > while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref1, 0)))); > > @@ -1245,17 +1332,15 @@ nonoverlapping_component_refs_since_matc > return 0; > } > ref2 = component_refs2.pop (); > + if (TREE_CODE (ref2) != COMPONENT_REF) > + seen_noncomponent_ref_p = true; > } > while (!RECORD_OR_UNION_TYPE_P (TREE_TYPE (TREE_OPERAND (ref2, 0)))); > > - /* Beware of BIT_FIELD_REF. */ > - if (TREE_CODE (ref1) != COMPONENT_REF > - || TREE_CODE (ref2) != COMPONENT_REF) > - { > - ++alias_stats > - .nonoverlapping_component_refs_since_match_p_may_alias; > - return -1; > - } > + /* BIT_FIELD_REF and VIEW_CONVERT_EXPR are taken off the vectors > + earlier. */ > + gcc_checking_assert (TREE_CODE (ref1) == COMPONENT_REF > + && TREE_CODE (ref2) == COMPONENT_REF); > > tree field1 = TREE_OPERAND (ref1, 1); > tree field2 = TREE_OPERAND (ref2, 1); > @@ -1266,33 +1351,27 @@ nonoverlapping_component_refs_since_matc > tree type1 = DECL_CONTEXT (field1); > tree type2 = DECL_CONTEXT (field2); > > - /* We cannot disambiguate fields in a union or qualified union. */ > - if (type1 != type2 || TREE_CODE (type1) != RECORD_TYPE) > + /* 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 > + && !operand_equal_p (TYPE_SIZE (type1), TYPE_SIZE (type2), 0)) > { > - ++alias_stats.nonoverlapping_component_refs_since_match_p_may_alias; > + ++alias_stats > + .nonoverlapping_component_refs_since_match_p_may_alias; > return -1; > } > > - if (field1 != field2) > + int cmp = nonoverlapping_component_refs_p_1 (field1, field2); > + if (cmp == -1) > { > - /* A field and its representative need to be considered the > - same. */ > - if (DECL_BIT_FIELD_REPRESENTATIVE (field1) == field2 > - || DECL_BIT_FIELD_REPRESENTATIVE (field2) == field1) > - { > - ++alias_stats > - .nonoverlapping_component_refs_since_match_p_must_overlap; > - return 0; > - } > - /* Different fields of the same record type cannot overlap. > - ??? Bitfields can overlap at RTL level so punt on them. */ > - if (DECL_BIT_FIELD (field1) && DECL_BIT_FIELD (field2)) > - { > - ++alias_stats > - .nonoverlapping_component_refs_since_match_p_must_overlap; > - return 0; > - } > - ++alias_stats.nonoverlapping_component_refs_since_match_p_no_alias; > + ++alias_stats > + .nonoverlapping_component_refs_since_match_p_may_alias; > + return -1; > + } > + else if (cmp == 1) > + { > + ++alias_stats > + .nonoverlapping_component_refs_since_match_p_no_alias; > return 1; > } > } > @@ -1301,6 +1380,24 @@ nonoverlapping_component_refs_since_matc > return 0; > } > > +/* Return TYPE_UID which can be used to match record types we consider > + same for TBAA purposes. */ > + > +static inline int > +ncr_type_uid (const_tree field) > +{ > + /* ??? We cannot simply use the type of operand #0 of the refs here > + as the Fortran compiler smuggles type punning into COMPONENT_REFs > + for common blocks instead of using unions like everyone else. */ > + tree type = DECL_FIELD_CONTEXT (field); > + /* With LTO types considered same_type_for_tbaa_p > + from different translation unit may not have same > + main variant. They however have same TYPE_CANONICAL. */ > + if (TYPE_CANONICAL (type)) > + return TYPE_UID (TYPE_CANONICAL (type)); > + return TYPE_UID (type); > +} > + > /* qsort compare function to sort FIELD_DECLs after their > DECL_FIELD_CONTEXT TYPE_UID. */ > > @@ -1309,8 +1406,9 @@ ncr_compar (const void *field1_, const v > { > const_tree field1 = *(const_tree *) const_cast (field1_); > const_tree field2 = *(const_tree *) const_cast (field2_); > - unsigned int uid1 = TYPE_UID (DECL_FIELD_CONTEXT (field1)); > - unsigned int uid2 = TYPE_UID (DECL_FIELD_CONTEXT (field2)); > + unsigned int uid1 = ncr_type_uid (field1); > + unsigned int uid2 = ncr_type_uid (field2); > + > if (uid1 < uid2) > return -1; > else if (uid1 > uid2) > @@ -1377,10 +1475,9 @@ nonoverlapping_component_refs_p (const_t > if (fieldsx.length () == 1 > && fieldsy.length () == 1) > { > - if ((DECL_FIELD_CONTEXT (fieldsx[0]) > - == DECL_FIELD_CONTEXT (fieldsy[0])) > - && fieldsx[0] != fieldsy[0] > - && !(DECL_BIT_FIELD (fieldsx[0]) && DECL_BIT_FIELD (fieldsy[0]))) > + if (same_type_for_tbaa (DECL_FIELD_CONTEXT (fieldsx[0]), > + DECL_FIELD_CONTEXT (fieldsy[0])) == 1 > + && nonoverlapping_component_refs_p_1 (fieldsx[0], fieldsy[0]) == 1) > { > ++alias_stats.nonoverlapping_component_refs_p_no_alias; > return true; > @@ -1413,31 +1510,18 @@ nonoverlapping_component_refs_p (const_t > { > const_tree fieldx = fieldsx[i]; > const_tree fieldy = fieldsy[j]; > - tree typex = DECL_FIELD_CONTEXT (fieldx); > - tree typey = DECL_FIELD_CONTEXT (fieldy); > - if (typex == typey) > - { > - /* We're left with accessing different fields of a structure, > - no possible overlap. */ > - if (fieldx != fieldy) > - { > - /* A field and its representative need to be considered the > - same. */ > - if (DECL_BIT_FIELD_REPRESENTATIVE (fieldx) == fieldy > - || DECL_BIT_FIELD_REPRESENTATIVE (fieldy) == fieldx) > - ; > - /* Different fields of the same record type cannot overlap. > - ??? Bitfields can overlap at RTL level so punt on them. */ > - else if (DECL_BIT_FIELD (fieldx) && DECL_BIT_FIELD (fieldy)) > - ; > - else > - { > - ++alias_stats.nonoverlapping_component_refs_p_no_alias; > - return true; > - } > - } > + > + /* We're left with accessing different fields of a structure, > + no possible overlap. */ > + if (same_type_for_tbaa (DECL_FIELD_CONTEXT (fieldx), > + DECL_FIELD_CONTEXT (fieldy)) == 1 > + && nonoverlapping_component_refs_p_1 (fieldx, fieldy) == 1) > + { > + ++alias_stats.nonoverlapping_component_refs_p_no_alias; > + return true; > } > - if (TYPE_UID (typex) < TYPE_UID (typey)) > + > + if (ncr_type_uid (fieldx) < ncr_type_uid (fieldy)) > { > i++; > if (i == fieldsx.length ()) > Index: testsuite/g++.dg/lto/alias-3_0.C > =================================================================== > --- testsuite/g++.dg/lto/alias-3_0.C (nonexistent) > +++ testsuite/g++.dg/lto/alias-3_0.C (working copy) > @@ -0,0 +1,27 @@ > +/* { dg-lto-do run } */ > +/* { dg-lto-options { { -O3 -flto -fno-early-inlining } } } */ > + > +struct a > +{ > + int foo,bar; > +}; > +struct b > +{ > + struct a a[10]; > +}; > + > +__attribute__ ((used)) struct b b, *bptr=&b, *bptr2=&b; > +__attribute__ ((used)) int i,j; > + > +extern "C" void inline_me_late (void); > + > +int > +main (void) > +{ > + int jj=j; > + bptr2->a[jj].bar = 0; > + inline_me_late (); > + if (!__builtin_constant_p (bptr2->a[jj].bar == 0)) > + __builtin_abort (); > + return 0; > +} > Index: testsuite/g++.dg/lto/alias-3_1.c > =================================================================== > --- testsuite/g++.dg/lto/alias-3_1.c (nonexistent) > +++ testsuite/g++.dg/lto/alias-3_1.c (working copy) > @@ -0,0 +1,20 @@ > +/* { dg-lto-do run } */ > +/* { dg-lto-options { { -O3 -flto -fno-early-inlining } } } */ > +struct a > +{ > + int foo,bar; > +}; > +struct b > +{ > + struct a a[10]; > +}; > + > +extern struct b *bptr; > +extern int i; > + > +void > +inline_me_late (void) > +{ > + bptr->a[i].foo=1; > +} > + > -- Richard Biener SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany; GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG Nürnberg) ---1609908220-2137534706-1562674466=:2976--