From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 48423 invoked by alias); 9 Jul 2019 11:49:27 -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 48411 invoked by uid 89); 9 Jul 2019 11:49:27 -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=i,j, 273193, beware 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, 09 Jul 2019 11:49:24 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id F0D8728252A; Tue, 9 Jul 2019 13:49:17 +0200 (CEST) Date: Tue, 09 Jul 2019 12:02:00 -0000 From: Jan Hubicka To: Richard Biener Cc: gcc-patches@gcc.gnu.org, d@dcepelik.cz Subject: Re: Make nonoverlapping_component_refs work with duplicated main variants Message-ID: <20190709114917.qva4nb2h7j5vzdur@kam.mff.cuni.cz> References: <20190708072649.vqd5u6jxsz5ybtt7@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: NeoMutt/20170113 (1.7.2) X-SW-Source: 2019-07/txt/msg00683.txt.bz2 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? 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); + + 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 + { + /* 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; + + 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; + + /* 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; + + 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; +} +