| Message ID | 20190628120613.nwjdjxwemcjh4tgn@kam.mff.cuni.cz |
|---|---|
| State | New |
| Headers | show |
| Series | Reorg nonoverlapping_component_refs_p | expand |
On Fri, 28 Jun 2019, Jan Hubicka wrote: > Hi, > this patch proceeds with further integrating > nonoverlapping_component_refs_for_decl_p and nonoverlapping_component_refs_p > however in bit more careful way then I intended previously (so we do not need > to xfail testcases and miss disambiguations we handled prevoiusly). The > problems with an attempt to zap nonoverlapping_component_refs_for_decl_p was > twofold > > 1) nonoverlapping_component_refs_for_decl_p is faster and it would be pity > to give up on that > 2) nonoverlapping_component_refs_for_decl_p is safe with -fno-strict-aliasing > while nonoverlapping_component_refs_p is not. > > nonoverlapping_component_refs_for_decl_p matches initial segment of access > path and preserves info that if original bases was > > (*) either completely disjoint or equivalent (which is the case of decls) > > then the part of access path walked has the same property. > > The second simply looks for matching references in the middle of > path which relies on fact that if two record types are same by TBAA they > either overlap perfectly or not at all. > > This patch refactors nonoverlapping_component_refs_for_decl_p to > nonoverlapping_component_refs_since_match_p and calls is in the places of > oracle where we establish (*) for refs. This is done in few places - > > 1) for decls that may be the same > 2) for pointers that are equal > 3) in aliasing_component_refs_p when we matched types. > > In all these cases we can go to nonoverlapping_component_refs_since_match_p > check and in most cases it will be able to fully resolve aliasing. > > If aliasing_component_refs_p did not find the match and TBAA says that one > access path can continue atop of other then there should be no matching types > so there is no need to call more expensive nonoverlapping_component_refs_p Nice! I like this. OK. Thanks, Richard. > There are corner case is that aliasing_component_refs_p gave up because of -1 > in same_type_for_tbaa_p or where access paths contains something that > nonoverlapping_component_refs_since_match_p does not understand (union, > non-merged LTO types and such). In this case we resort to > nonoverlapping_component_refs_p. > > I have more testcases but they need bit more tweaking to > nonoverlapping_component_refs_since_match_p. I tried to keep this patch small. > There are possible additional optimization, for example > nonoverlapping_component_refs does not need to walk whole path in many cases. > > Tramp3d disambiguations change from: > > refs_may_alias_p: 3486566 disambiguations, 3820994 queries > ref_maybe_used_by_call_p: 6790 disambiguations, 3512955 queries > call_may_clobber_ref_p: 883 disambiguations, 883 queries > nonoverlapping_component_refs_p: 23 disambiguations, 64926 queries > nonoverlapping_component_refs_of_decl_p: 19 disambiguations, 2314 queries > aliasing_component_refs_p: 893 disambiguations, 20671 queries > TBAA oracle: 1766713 disambiguations 3393231 queries > 536475 are in alias set 0 > 694528 queries asked about the same object > 0 queries asked about the same alias set > 0 access volatile > 264570 are dependent in the DAG > 130945 are aritificially in conflict with void * > > PTA query stats: > pt_solution_includes: 639122 disambiguations, 922905 queries > pt_solutions_intersect: 119319 disambiguations, 506108 queries > > to: > refs_may_alias_p: 3486577 disambiguations, 3821005 queries > ref_maybe_used_by_call_p: 6790 disambiguations, 3512966 queries > call_may_clobber_ref_p: 883 disambiguations, 883 queries > nonoverlapping_component_refs_p: 0 disambiguations, 8953 queries > nonoverlapping_component_refs_since_match_p: 31 disambiguations, 34795 queries > aliasing_component_refs_p: 916 disambiguations, 29748 queries > TBAA oracle: 1766713 disambiguations 3394373 queries > 536477 are in alias set 0 > 694529 queries asked about the same object > 0 queries asked about the same alias set > 0 access volatile > 265709 are dependent in the DAG > 130945 are aritificially in conflict with void * > > PTA query stats: > pt_solution_includes: 639122 disambiguations, 922905 queries > pt_solutions_intersect: 119319 disambiguations, 506118 queries > > So 55973 fewer nonoverlapping_component_refs_p calls but > 32481 more nonoverlapping_component_refs_since_match_p calls > and 9077 more aliasing_component_refs_p calls. > > The decrease of disambiguations of > nonoverlapping_component_refs_p+nonoverlapping_component_refs_since_match_p is > caused by fact that aliasing_component_refs_p disambiguates based on the > nonoverlapping_ranges more frequently now. > Overall there are 11 new disambiguations. > > lto-bootstrapped/regtested x86_64-linux. OK? > > * tree-ssa-alias.c (nonoverlapping_component_refs_for_decl_p): Rename > to .. > (nonoverlapping_component_refs_since_match_p): ... this one; > handle also non-decl bases; return -1 if search gave up. > (alias_stats): Rename nonoverlapping_component_refs_of_decl_p_may_alias, > nonoverlapping_component_refs_of_decl_p_no_alias to > nonoverlapping_component_refs_since_match_p_may_alias, > nonoverlapping_component_refs_since_match_p_no_alias. > (dump_alias_stats): Update dumping. > (aliasing_matching_component_refs_p): Break out from ...; > dispatch to nonoverlapping_component_refs_for_decl_p > and nonoverlapping_component_refs_since_match_p. > (aliasing_component_refs_p): ... here; call > nonoverlapping_component_refs_p in scenarios where we can not > precisely determine base match. > (decl_refs_may_alias_p): Use > nonoverlapping_component_refs_since_match_p. > (indirect_ref_may_alias_decl_p): Do not call > nonoverlapping_component_refs_p. > (indirect_refs_may_alias_p): Likewise. > > * gcc.dg/tree-ssa/alias-access-path-7.c: New testcase. > > Index: tree-ssa-alias.c > =================================================================== > --- tree-ssa-alias.c (revision 272778) > +++ tree-ssa-alias.c (working copy) > @@ -87,6 +87,8 @@ 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 bool nonoverlapping_component_refs_p (const_tree, const_tree); > > /* Query statistics for the different low-level disambiguators. > A high-level query may trigger multiple of them. */ > @@ -102,8 +104,8 @@ 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_of_decl_p_may_alias; > - unsigned HOST_WIDE_INT nonoverlapping_component_refs_of_decl_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_no_alias; > } alias_stats; > > void > @@ -134,12 +136,12 @@ 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_of_decl_p: " > + fprintf (s, " nonoverlapping_component_refs_since_match_p: " > HOST_WIDE_INT_PRINT_DEC" disambiguations, " > HOST_WIDE_INT_PRINT_DEC" queries\n", > - alias_stats.nonoverlapping_component_refs_of_decl_p_no_alias, > - alias_stats.nonoverlapping_component_refs_of_decl_p_no_alias > - + alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias); > + alias_stats.nonoverlapping_component_refs_since_match_p_no_alias, > + alias_stats.nonoverlapping_component_refs_since_match_p_no_alias > + + alias_stats.nonoverlapping_component_refs_since_match_p_may_alias); > fprintf (s, " aliasing_component_refs_p: " > HOST_WIDE_INT_PRINT_DEC" disambiguations, " > HOST_WIDE_INT_PRINT_DEC" queries\n", > @@ -848,6 +850,47 @@ type_has_components_p (tree type) > || TREE_CODE (type) == COMPLEX_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. > + > + Try to disambiguate using the access path starting from the match > + and return false if there is no conflict. > + > + Helper for aliasing_component_refs_p. */ > + > +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 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)) > + { > + ++alias_stats.aliasing_component_refs_p_no_alias; > + return false; > + } > + > + int cmp = nonoverlapping_component_refs_since_match_p (match1, ref1, > + match2, ref2); > + if (cmp == 1 > + || (cmp == -1 && nonoverlapping_component_refs_p (ref1, ref2))) > + { > + ++alias_stats.aliasing_component_refs_p_no_alias; > + return false; > + } > + ++alias_stats.aliasing_component_refs_p_may_alias; > + return true; > +} > + > /* Determine if the two component references REF1 and REF2 which are > based on access types TYPE1 and TYPE2 and of which at least one is based > on an indirect reference may alias. > @@ -969,37 +1012,24 @@ aliasing_component_refs_p (tree ref1, > } > if (same_p2 == 1) > { > - poly_int64 offadj, sztmp, msztmp; > - bool reverse; > - > /* 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 > the access and not contained within another component ref. > - To be safe we also assume partial overlap for VLAs. */ > + To be safe we also assume partial overlap for VLAs. */ > if (TREE_CODE (TREE_TYPE (base1)) == ARRAY_TYPE > && (!TYPE_SIZE (TREE_TYPE (base1)) > || TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) != INTEGER_CST > || ref == base2)) > - { > - ++alias_stats.aliasing_component_refs_p_may_alias; > - return true; > - } > - > - get_ref_base_and_extent (ref, &offadj, &sztmp, &msztmp, &reverse); > - offset2 -= offadj; > - get_ref_base_and_extent (base1, &offadj, &sztmp, &msztmp, &reverse); > - offset1 -= offadj; > - if (ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2)) > - { > - ++alias_stats.aliasing_component_refs_p_may_alias; > - return true; > - } > + /* Setting maybe_match to true triggers > + nonoverlapping_component_refs_p test later that still may do > + useful disambiguation. */ > + maybe_match = true; > else > - { > - ++alias_stats.aliasing_component_refs_p_no_alias; > - return false; > - } > + return aliasing_matching_component_refs_p (base1, ref1, > + offset1, max_size1, > + ref, ref2, > + offset2, max_size2); > } > } > > @@ -1033,32 +1063,16 @@ aliasing_component_refs_p (tree ref1, > } > if (same_p1 == 1) > { > - poly_int64 offadj, sztmp, msztmp; > - bool reverse; > - > if (TREE_CODE (TREE_TYPE (base2)) == ARRAY_TYPE > && (!TYPE_SIZE (TREE_TYPE (base2)) > || TREE_CODE (TYPE_SIZE (TREE_TYPE (base2))) != INTEGER_CST > || ref == base1)) > - { > - ++alias_stats.aliasing_component_refs_p_may_alias; > - return true; > - } > - > - get_ref_base_and_extent (ref, &offadj, &sztmp, &msztmp, &reverse); > - offset1 -= offadj; > - get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp, &reverse); > - offset2 -= offadj; > - if (ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2)) > - { > - ++alias_stats.aliasing_component_refs_p_may_alias; > - return true; > - } > + maybe_match = true; > else > - { > - ++alias_stats.aliasing_component_refs_p_no_alias; > - return false; > - } > + return aliasing_matching_component_refs_p (ref, ref1, > + offset1, max_size1, > + base2, ref2, > + offset2, max_size2); > } > } > > @@ -1067,7 +1081,15 @@ aliasing_component_refs_p (tree ref1, > continuation of another. If we was not able to decide about equivalence, > we need to give up. */ > if (maybe_match) > - return true; > + { > + if (!nonoverlapping_component_refs_p (ref1, ref2)) > + { > + ++alias_stats.aliasing_component_refs_p_may_alias; > + return true; > + } > + ++alias_stats.aliasing_component_refs_p_no_alias; > + return false; > + } > > /* If we have two type access paths B1.path1 and B2.path2 they may > only alias if either B1 is in B2.path2 or B2 is in B1.path1. > @@ -1083,6 +1105,7 @@ aliasing_component_refs_p (tree ref1, > && (base1_alias_set == ref2_alias_set > || alias_set_subset_of (base1_alias_set, ref2_alias_set))) > { > + gcc_checking_assert (!nonoverlapping_component_refs_p (ref1, ref2)); > ++alias_stats.aliasing_component_refs_p_may_alias; > return true; > } > @@ -1095,6 +1118,7 @@ aliasing_component_refs_p (tree ref1, > && (base2_alias_set == ref1_alias_set > || alias_set_subset_of (base2_alias_set, ref1_alias_set))) > { > + gcc_checking_assert (!nonoverlapping_component_refs_p (ref1, ref2)); > ++alias_stats.aliasing_component_refs_p_may_alias; > return true; > } > @@ -1102,11 +1126,30 @@ aliasing_component_refs_p (tree ref1, > return false; > } > > -/* Return true if we can determine that component references REF1 and REF2, > - that are within a common DECL, cannot overlap. */ > +/* 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. > + > + 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 > + match was determined without use of TBAA oracle. > + > + Return 1 if we can determine that component references REF1 and REF2, > + that are within a common DECL, cannot overlap. > + > + Return 0 if paths are same and thus there is nothing to disambiguate more > + (i.e. there is must alias assuming there is must alias between MATCH1 and > + MATCH2) > + > + Return -1 if we can not determine 0 or 1 - this happens when we met > + non-matching types was met in the path. > + In this case it may make sense to continue by other disambiguation > + oracles. */ > > -static bool > -nonoverlapping_component_refs_of_decl_p (tree ref1, tree ref2) > +static int > +nonoverlapping_component_refs_since_match_p (tree match1, tree ref1, > + tree match2, tree ref2) > { > auto_vec<tree, 16> component_refs1; > auto_vec<tree, 16> component_refs2; > @@ -1114,39 +1157,55 @@ nonoverlapping_component_refs_of_decl_p > /* Create the stack of handled components for REF1. */ > while (handled_component_p (ref1)) > { > - component_refs1.safe_push (ref1); > + if (TREE_CODE (ref1) == VIEW_CONVERT_EXPR > + || TREE_CODE (ref1) == BIT_FIELD_REF) > + component_refs1.truncate (0); > + else > + component_refs1.safe_push (ref1); > + if (ref1 == match1) > + break; > ref1 = TREE_OPERAND (ref1, 0); > } > - if (TREE_CODE (ref1) == MEM_REF) > + if (TREE_CODE (ref1) == MEM_REF && ref1 != match1) > { > if (!integer_zerop (TREE_OPERAND (ref1, 1))) > { > - ++alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias; > - return false; > + ++alias_stats.nonoverlapping_component_refs_since_match_p_may_alias; > + return -1; > } > - ref1 = TREE_OPERAND (TREE_OPERAND (ref1, 0), 0); > + } > + /* TODO: Handle TARGET_MEM_REF later. */ > + if (TREE_CODE (ref1) == TARGET_MEM_REF && ref1 != match1) > + { > + ++alias_stats.nonoverlapping_component_refs_since_match_p_may_alias; > + return -1; > } > > /* Create the stack of handled components for REF2. */ > while (handled_component_p (ref2)) > { > - component_refs2.safe_push (ref2); > + if (TREE_CODE (ref2) == VIEW_CONVERT_EXPR > + || TREE_CODE (ref2) == BIT_FIELD_REF) > + component_refs2.truncate (0); > + else > + component_refs2.safe_push (ref2); > + if (ref2 == match2) > + break; > ref2 = TREE_OPERAND (ref2, 0); > } > - if (TREE_CODE (ref2) == MEM_REF) > + if (TREE_CODE (ref2) == MEM_REF && ref2 != match2) > { > if (!integer_zerop (TREE_OPERAND (ref2, 1))) > { > - ++alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias; > - return false; > + ++alias_stats.nonoverlapping_component_refs_since_match_p_may_alias; > + return -1; > } > - ref2 = TREE_OPERAND (TREE_OPERAND (ref2, 0), 0); > } > - > - /* Bases must be either same or uncomparable. */ > - gcc_checking_assert (ref1 == ref2 > - || (DECL_P (ref1) && DECL_P (ref2) > - && compare_base_decls (ref1, ref2) != 0)); > + if (TREE_CODE (ref2) == TARGET_MEM_REF && ref2 != match2) > + { > + ++alias_stats.nonoverlapping_component_refs_since_match_p_may_alias; > + return -1; > + } > > /* Pop the stacks in parallel and examine the COMPONENT_REFs of the same > rank. This is sufficient because we start from the same DECL and you > @@ -1160,8 +1219,9 @@ nonoverlapping_component_refs_of_decl_p > { > if (component_refs1.is_empty ()) > { > - ++alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias; > - return false; > + ++alias_stats > + .nonoverlapping_component_refs_since_match_p_may_alias; > + return 0; > } > ref1 = component_refs1.pop (); > } > @@ -1171,8 +1231,9 @@ nonoverlapping_component_refs_of_decl_p > { > if (component_refs2.is_empty ()) > { > - ++alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias; > - return false; > + ++alias_stats > + .nonoverlapping_component_refs_since_match_p_may_alias; > + return 0; > } > ref2 = component_refs2.pop (); > } > @@ -1182,8 +1243,9 @@ nonoverlapping_component_refs_of_decl_p > if (TREE_CODE (ref1) != COMPONENT_REF > || TREE_CODE (ref2) != COMPONENT_REF) > { > - ++alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias; > - return false; > + ++alias_stats > + .nonoverlapping_component_refs_since_match_p_may_alias; > + return -1; > } > > tree field1 = TREE_OPERAND (ref1, 1); > @@ -1198,8 +1260,8 @@ nonoverlapping_component_refs_of_decl_p > /* We cannot disambiguate fields in a union or qualified union. */ > if (type1 != type2 || TREE_CODE (type1) != RECORD_TYPE) > { > - ++alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias; > - return false; > + ++alias_stats.nonoverlapping_component_refs_since_match_p_may_alias; > + return -1; > } > > if (field1 != field2) > @@ -1209,23 +1271,25 @@ nonoverlapping_component_refs_of_decl_p > if (DECL_BIT_FIELD_REPRESENTATIVE (field1) == field2 > || DECL_BIT_FIELD_REPRESENTATIVE (field2) == field1) > { > - ++alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias; > - return false; > + ++alias_stats > + .nonoverlapping_component_refs_since_match_p_may_alias; > + 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_of_decl_p_may_alias; > - return false; > + ++alias_stats > + .nonoverlapping_component_refs_since_match_p_may_alias; > + return 0; > } > - ++alias_stats.nonoverlapping_component_refs_of_decl_p_no_alias; > - return true; > + ++alias_stats.nonoverlapping_component_refs_since_match_p_no_alias; > + return 1; > } > } > > - ++alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias; > - return false; > + ++alias_stats.nonoverlapping_component_refs_since_match_p_may_alias; > + return 0; > } > > /* qsort compare function to sort FIELD_DECLs after their > @@ -1246,7 +1310,7 @@ ncr_compar (const void *field1_, const v > } > > /* Return true if we can determine that the fields referenced cannot > - overlap for any pair of objects. */ > + overlap for any pair of objects. This relies on TBAA. */ > > static bool > nonoverlapping_component_refs_p (const_tree x, const_tree y) > @@ -1408,7 +1472,8 @@ 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_of_decl_p (ref1, ref2)) > + && nonoverlapping_component_refs_since_match_p (NULL, ref1, > + NULL, ref2) == 1) > return false; > > return true; > @@ -1537,10 +1602,6 @@ indirect_ref_may_alias_decl_p (tree ref1 > && TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) == INTEGER_CST))) > return ranges_maybe_overlap_p (doffset1, max_size1, doffset2, max_size2); > > - if (ref1 && ref2 > - && nonoverlapping_component_refs_p (ref1, ref2)) > - return false; > - > /* Do access-path based disambiguation. */ > if (ref1 && ref2 > && (handled_component_p (ref1) || handled_component_p (ref2))) > @@ -1609,8 +1670,16 @@ indirect_refs_may_alias_p (tree ref1 ATT > { > poly_offset_int moff1 = mem_ref_offset (base1) << LOG2_BITS_PER_UNIT; > poly_offset_int moff2 = mem_ref_offset (base2) << LOG2_BITS_PER_UNIT; > - return ranges_maybe_overlap_p (offset1 + moff1, max_size1, > - offset2 + moff2, max_size2); > + if (!ranges_maybe_overlap_p (offset1 + moff1, max_size1, > + offset2 + moff2, max_size2)) > + return false; > + if (ref1 && ref2) > + { > + int res = nonoverlapping_component_refs_since_match_p (NULL, ref1, > + NULL, ref2); > + if (res != -1) > + return !res; > + } > } > if (!ptr_derefs_may_alias_p (ptr1, ptr2)) > return false; > @@ -1652,10 +1721,6 @@ indirect_refs_may_alias_p (tree ref1 ATT > && TREE_CODE (TREE_TYPE (ptrtype1)) != ARRAY_TYPE) > return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2); > > - if (ref1 && ref2 > - && nonoverlapping_component_refs_p (ref1, ref2)) > - return false; > - > /* Do access-path based disambiguation. */ > if (ref1 && ref2 > && (handled_component_p (ref1) || handled_component_p (ref2))) > Index: testsuite/gcc.dg/tree-ssa/alias-access-path-7.c > =================================================================== > --- testsuite/gcc.dg/tree-ssa/alias-access-path-7.c (nonexistent) > +++ testsuite/gcc.dg/tree-ssa/alias-access-path-7.c (working copy) > @@ -0,0 +1,20 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O1 -fno-strict-aliasing -fdump-tree-optimized" } */ > + > +struct S > +{ > + int i; > + int j; > +}; > +struct U > +{ > + struct S a[10]; > +}; > +int > +foo (struct U *u, int n, int i, int j) > +{ > + u->a[i].i = 123; > + u->a[j].j = j; > + return u->a[i].i; > +} > +/* { dg-final { scan-tree-dump-times "return 123" 1 "optimized"} } */ >
Index: tree-ssa-alias.c =================================================================== --- tree-ssa-alias.c (revision 272778) +++ tree-ssa-alias.c (working copy) @@ -87,6 +87,8 @@ 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 bool nonoverlapping_component_refs_p (const_tree, const_tree); /* Query statistics for the different low-level disambiguators. A high-level query may trigger multiple of them. */ @@ -102,8 +104,8 @@ 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_of_decl_p_may_alias; - unsigned HOST_WIDE_INT nonoverlapping_component_refs_of_decl_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_no_alias; } alias_stats; void @@ -134,12 +136,12 @@ 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_of_decl_p: " + fprintf (s, " nonoverlapping_component_refs_since_match_p: " HOST_WIDE_INT_PRINT_DEC" disambiguations, " HOST_WIDE_INT_PRINT_DEC" queries\n", - alias_stats.nonoverlapping_component_refs_of_decl_p_no_alias, - alias_stats.nonoverlapping_component_refs_of_decl_p_no_alias - + alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias); + alias_stats.nonoverlapping_component_refs_since_match_p_no_alias, + alias_stats.nonoverlapping_component_refs_since_match_p_no_alias + + alias_stats.nonoverlapping_component_refs_since_match_p_may_alias); fprintf (s, " aliasing_component_refs_p: " HOST_WIDE_INT_PRINT_DEC" disambiguations, " HOST_WIDE_INT_PRINT_DEC" queries\n", @@ -848,6 +850,47 @@ type_has_components_p (tree type) || TREE_CODE (type) == COMPLEX_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. + + Try to disambiguate using the access path starting from the match + and return false if there is no conflict. + + Helper for aliasing_component_refs_p. */ + +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 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)) + { + ++alias_stats.aliasing_component_refs_p_no_alias; + return false; + } + + int cmp = nonoverlapping_component_refs_since_match_p (match1, ref1, + match2, ref2); + if (cmp == 1 + || (cmp == -1 && nonoverlapping_component_refs_p (ref1, ref2))) + { + ++alias_stats.aliasing_component_refs_p_no_alias; + return false; + } + ++alias_stats.aliasing_component_refs_p_may_alias; + return true; +} + /* Determine if the two component references REF1 and REF2 which are based on access types TYPE1 and TYPE2 and of which at least one is based on an indirect reference may alias. @@ -969,37 +1012,24 @@ aliasing_component_refs_p (tree ref1, } if (same_p2 == 1) { - poly_int64 offadj, sztmp, msztmp; - bool reverse; - /* 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 the access and not contained within another component ref. - To be safe we also assume partial overlap for VLAs. */ + To be safe we also assume partial overlap for VLAs. */ if (TREE_CODE (TREE_TYPE (base1)) == ARRAY_TYPE && (!TYPE_SIZE (TREE_TYPE (base1)) || TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) != INTEGER_CST || ref == base2)) - { - ++alias_stats.aliasing_component_refs_p_may_alias; - return true; - } - - get_ref_base_and_extent (ref, &offadj, &sztmp, &msztmp, &reverse); - offset2 -= offadj; - get_ref_base_and_extent (base1, &offadj, &sztmp, &msztmp, &reverse); - offset1 -= offadj; - if (ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2)) - { - ++alias_stats.aliasing_component_refs_p_may_alias; - return true; - } + /* Setting maybe_match to true triggers + nonoverlapping_component_refs_p test later that still may do + useful disambiguation. */ + maybe_match = true; else - { - ++alias_stats.aliasing_component_refs_p_no_alias; - return false; - } + return aliasing_matching_component_refs_p (base1, ref1, + offset1, max_size1, + ref, ref2, + offset2, max_size2); } } @@ -1033,32 +1063,16 @@ aliasing_component_refs_p (tree ref1, } if (same_p1 == 1) { - poly_int64 offadj, sztmp, msztmp; - bool reverse; - if (TREE_CODE (TREE_TYPE (base2)) == ARRAY_TYPE && (!TYPE_SIZE (TREE_TYPE (base2)) || TREE_CODE (TYPE_SIZE (TREE_TYPE (base2))) != INTEGER_CST || ref == base1)) - { - ++alias_stats.aliasing_component_refs_p_may_alias; - return true; - } - - get_ref_base_and_extent (ref, &offadj, &sztmp, &msztmp, &reverse); - offset1 -= offadj; - get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp, &reverse); - offset2 -= offadj; - if (ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2)) - { - ++alias_stats.aliasing_component_refs_p_may_alias; - return true; - } + maybe_match = true; else - { - ++alias_stats.aliasing_component_refs_p_no_alias; - return false; - } + return aliasing_matching_component_refs_p (ref, ref1, + offset1, max_size1, + base2, ref2, + offset2, max_size2); } } @@ -1067,7 +1081,15 @@ aliasing_component_refs_p (tree ref1, continuation of another. If we was not able to decide about equivalence, we need to give up. */ if (maybe_match) - return true; + { + if (!nonoverlapping_component_refs_p (ref1, ref2)) + { + ++alias_stats.aliasing_component_refs_p_may_alias; + return true; + } + ++alias_stats.aliasing_component_refs_p_no_alias; + return false; + } /* If we have two type access paths B1.path1 and B2.path2 they may only alias if either B1 is in B2.path2 or B2 is in B1.path1. @@ -1083,6 +1105,7 @@ aliasing_component_refs_p (tree ref1, && (base1_alias_set == ref2_alias_set || alias_set_subset_of (base1_alias_set, ref2_alias_set))) { + gcc_checking_assert (!nonoverlapping_component_refs_p (ref1, ref2)); ++alias_stats.aliasing_component_refs_p_may_alias; return true; } @@ -1095,6 +1118,7 @@ aliasing_component_refs_p (tree ref1, && (base2_alias_set == ref1_alias_set || alias_set_subset_of (base2_alias_set, ref1_alias_set))) { + gcc_checking_assert (!nonoverlapping_component_refs_p (ref1, ref2)); ++alias_stats.aliasing_component_refs_p_may_alias; return true; } @@ -1102,11 +1126,30 @@ aliasing_component_refs_p (tree ref1, return false; } -/* Return true if we can determine that component references REF1 and REF2, - that are within a common DECL, cannot overlap. */ +/* 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. + + 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 + match was determined without use of TBAA oracle. + + Return 1 if we can determine that component references REF1 and REF2, + that are within a common DECL, cannot overlap. + + Return 0 if paths are same and thus there is nothing to disambiguate more + (i.e. there is must alias assuming there is must alias between MATCH1 and + MATCH2) + + Return -1 if we can not determine 0 or 1 - this happens when we met + non-matching types was met in the path. + In this case it may make sense to continue by other disambiguation + oracles. */ -static bool -nonoverlapping_component_refs_of_decl_p (tree ref1, tree ref2) +static int +nonoverlapping_component_refs_since_match_p (tree match1, tree ref1, + tree match2, tree ref2) { auto_vec<tree, 16> component_refs1; auto_vec<tree, 16> component_refs2; @@ -1114,39 +1157,55 @@ nonoverlapping_component_refs_of_decl_p /* Create the stack of handled components for REF1. */ while (handled_component_p (ref1)) { - component_refs1.safe_push (ref1); + if (TREE_CODE (ref1) == VIEW_CONVERT_EXPR + || TREE_CODE (ref1) == BIT_FIELD_REF) + component_refs1.truncate (0); + else + component_refs1.safe_push (ref1); + if (ref1 == match1) + break; ref1 = TREE_OPERAND (ref1, 0); } - if (TREE_CODE (ref1) == MEM_REF) + if (TREE_CODE (ref1) == MEM_REF && ref1 != match1) { if (!integer_zerop (TREE_OPERAND (ref1, 1))) { - ++alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias; - return false; + ++alias_stats.nonoverlapping_component_refs_since_match_p_may_alias; + return -1; } - ref1 = TREE_OPERAND (TREE_OPERAND (ref1, 0), 0); + } + /* TODO: Handle TARGET_MEM_REF later. */ + if (TREE_CODE (ref1) == TARGET_MEM_REF && ref1 != match1) + { + ++alias_stats.nonoverlapping_component_refs_since_match_p_may_alias; + return -1; } /* Create the stack of handled components for REF2. */ while (handled_component_p (ref2)) { - component_refs2.safe_push (ref2); + if (TREE_CODE (ref2) == VIEW_CONVERT_EXPR + || TREE_CODE (ref2) == BIT_FIELD_REF) + component_refs2.truncate (0); + else + component_refs2.safe_push (ref2); + if (ref2 == match2) + break; ref2 = TREE_OPERAND (ref2, 0); } - if (TREE_CODE (ref2) == MEM_REF) + if (TREE_CODE (ref2) == MEM_REF && ref2 != match2) { if (!integer_zerop (TREE_OPERAND (ref2, 1))) { - ++alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias; - return false; + ++alias_stats.nonoverlapping_component_refs_since_match_p_may_alias; + return -1; } - ref2 = TREE_OPERAND (TREE_OPERAND (ref2, 0), 0); } - - /* Bases must be either same or uncomparable. */ - gcc_checking_assert (ref1 == ref2 - || (DECL_P (ref1) && DECL_P (ref2) - && compare_base_decls (ref1, ref2) != 0)); + if (TREE_CODE (ref2) == TARGET_MEM_REF && ref2 != match2) + { + ++alias_stats.nonoverlapping_component_refs_since_match_p_may_alias; + return -1; + } /* Pop the stacks in parallel and examine the COMPONENT_REFs of the same rank. This is sufficient because we start from the same DECL and you @@ -1160,8 +1219,9 @@ nonoverlapping_component_refs_of_decl_p { if (component_refs1.is_empty ()) { - ++alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias; - return false; + ++alias_stats + .nonoverlapping_component_refs_since_match_p_may_alias; + return 0; } ref1 = component_refs1.pop (); } @@ -1171,8 +1231,9 @@ nonoverlapping_component_refs_of_decl_p { if (component_refs2.is_empty ()) { - ++alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias; - return false; + ++alias_stats + .nonoverlapping_component_refs_since_match_p_may_alias; + return 0; } ref2 = component_refs2.pop (); } @@ -1182,8 +1243,9 @@ nonoverlapping_component_refs_of_decl_p if (TREE_CODE (ref1) != COMPONENT_REF || TREE_CODE (ref2) != COMPONENT_REF) { - ++alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias; - return false; + ++alias_stats + .nonoverlapping_component_refs_since_match_p_may_alias; + return -1; } tree field1 = TREE_OPERAND (ref1, 1); @@ -1198,8 +1260,8 @@ nonoverlapping_component_refs_of_decl_p /* We cannot disambiguate fields in a union or qualified union. */ if (type1 != type2 || TREE_CODE (type1) != RECORD_TYPE) { - ++alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias; - return false; + ++alias_stats.nonoverlapping_component_refs_since_match_p_may_alias; + return -1; } if (field1 != field2) @@ -1209,23 +1271,25 @@ nonoverlapping_component_refs_of_decl_p if (DECL_BIT_FIELD_REPRESENTATIVE (field1) == field2 || DECL_BIT_FIELD_REPRESENTATIVE (field2) == field1) { - ++alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias; - return false; + ++alias_stats + .nonoverlapping_component_refs_since_match_p_may_alias; + 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_of_decl_p_may_alias; - return false; + ++alias_stats + .nonoverlapping_component_refs_since_match_p_may_alias; + return 0; } - ++alias_stats.nonoverlapping_component_refs_of_decl_p_no_alias; - return true; + ++alias_stats.nonoverlapping_component_refs_since_match_p_no_alias; + return 1; } } - ++alias_stats.nonoverlapping_component_refs_of_decl_p_may_alias; - return false; + ++alias_stats.nonoverlapping_component_refs_since_match_p_may_alias; + return 0; } /* qsort compare function to sort FIELD_DECLs after their @@ -1246,7 +1310,7 @@ ncr_compar (const void *field1_, const v } /* Return true if we can determine that the fields referenced cannot - overlap for any pair of objects. */ + overlap for any pair of objects. This relies on TBAA. */ static bool nonoverlapping_component_refs_p (const_tree x, const_tree y) @@ -1408,7 +1472,8 @@ 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_of_decl_p (ref1, ref2)) + && nonoverlapping_component_refs_since_match_p (NULL, ref1, + NULL, ref2) == 1) return false; return true; @@ -1537,10 +1602,6 @@ indirect_ref_may_alias_decl_p (tree ref1 && TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) == INTEGER_CST))) return ranges_maybe_overlap_p (doffset1, max_size1, doffset2, max_size2); - if (ref1 && ref2 - && nonoverlapping_component_refs_p (ref1, ref2)) - return false; - /* Do access-path based disambiguation. */ if (ref1 && ref2 && (handled_component_p (ref1) || handled_component_p (ref2))) @@ -1609,8 +1670,16 @@ indirect_refs_may_alias_p (tree ref1 ATT { poly_offset_int moff1 = mem_ref_offset (base1) << LOG2_BITS_PER_UNIT; poly_offset_int moff2 = mem_ref_offset (base2) << LOG2_BITS_PER_UNIT; - return ranges_maybe_overlap_p (offset1 + moff1, max_size1, - offset2 + moff2, max_size2); + if (!ranges_maybe_overlap_p (offset1 + moff1, max_size1, + offset2 + moff2, max_size2)) + return false; + if (ref1 && ref2) + { + int res = nonoverlapping_component_refs_since_match_p (NULL, ref1, + NULL, ref2); + if (res != -1) + return !res; + } } if (!ptr_derefs_may_alias_p (ptr1, ptr2)) return false; @@ -1652,10 +1721,6 @@ indirect_refs_may_alias_p (tree ref1 ATT && TREE_CODE (TREE_TYPE (ptrtype1)) != ARRAY_TYPE) return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2); - if (ref1 && ref2 - && nonoverlapping_component_refs_p (ref1, ref2)) - return false; - /* Do access-path based disambiguation. */ if (ref1 && ref2 && (handled_component_p (ref1) || handled_component_p (ref2))) Index: testsuite/gcc.dg/tree-ssa/alias-access-path-7.c =================================================================== --- testsuite/gcc.dg/tree-ssa/alias-access-path-7.c (nonexistent) +++ testsuite/gcc.dg/tree-ssa/alias-access-path-7.c (working copy) @@ -0,0 +1,20 @@ +/* { dg-do compile } */ +/* { dg-options "-O1 -fno-strict-aliasing -fdump-tree-optimized" } */ + +struct S +{ + int i; + int j; +}; +struct U +{ + struct S a[10]; +}; +int +foo (struct U *u, int n, int i, int j) +{ + u->a[i].i = 123; + u->a[j].j = j; + return u->a[i].i; +} +/* { dg-final { scan-tree-dump-times "return 123" 1 "optimized"} } */
Hi, this patch proceeds with further integrating nonoverlapping_component_refs_for_decl_p and nonoverlapping_component_refs_p however in bit more careful way then I intended previously (so we do not need to xfail testcases and miss disambiguations we handled prevoiusly). The problems with an attempt to zap nonoverlapping_component_refs_for_decl_p was twofold 1) nonoverlapping_component_refs_for_decl_p is faster and it would be pity to give up on that 2) nonoverlapping_component_refs_for_decl_p is safe with -fno-strict-aliasing while nonoverlapping_component_refs_p is not. nonoverlapping_component_refs_for_decl_p matches initial segment of access path and preserves info that if original bases was (*) either completely disjoint or equivalent (which is the case of decls) then the part of access path walked has the same property. The second simply looks for matching references in the middle of path which relies on fact that if two record types are same by TBAA they either overlap perfectly or not at all. This patch refactors nonoverlapping_component_refs_for_decl_p to nonoverlapping_component_refs_since_match_p and calls is in the places of oracle where we establish (*) for refs. This is done in few places - 1) for decls that may be the same 2) for pointers that are equal 3) in aliasing_component_refs_p when we matched types. In all these cases we can go to nonoverlapping_component_refs_since_match_p check and in most cases it will be able to fully resolve aliasing. If aliasing_component_refs_p did not find the match and TBAA says that one access path can continue atop of other then there should be no matching types so there is no need to call more expensive nonoverlapping_component_refs_p There are corner case is that aliasing_component_refs_p gave up because of -1 in same_type_for_tbaa_p or where access paths contains something that nonoverlapping_component_refs_since_match_p does not understand (union, non-merged LTO types and such). In this case we resort to nonoverlapping_component_refs_p. I have more testcases but they need bit more tweaking to nonoverlapping_component_refs_since_match_p. I tried to keep this patch small. There are possible additional optimization, for example nonoverlapping_component_refs does not need to walk whole path in many cases. Tramp3d disambiguations change from: refs_may_alias_p: 3486566 disambiguations, 3820994 queries ref_maybe_used_by_call_p: 6790 disambiguations, 3512955 queries call_may_clobber_ref_p: 883 disambiguations, 883 queries nonoverlapping_component_refs_p: 23 disambiguations, 64926 queries nonoverlapping_component_refs_of_decl_p: 19 disambiguations, 2314 queries aliasing_component_refs_p: 893 disambiguations, 20671 queries TBAA oracle: 1766713 disambiguations 3393231 queries 536475 are in alias set 0 694528 queries asked about the same object 0 queries asked about the same alias set 0 access volatile 264570 are dependent in the DAG 130945 are aritificially in conflict with void * PTA query stats: pt_solution_includes: 639122 disambiguations, 922905 queries pt_solutions_intersect: 119319 disambiguations, 506108 queries to: refs_may_alias_p: 3486577 disambiguations, 3821005 queries ref_maybe_used_by_call_p: 6790 disambiguations, 3512966 queries call_may_clobber_ref_p: 883 disambiguations, 883 queries nonoverlapping_component_refs_p: 0 disambiguations, 8953 queries nonoverlapping_component_refs_since_match_p: 31 disambiguations, 34795 queries aliasing_component_refs_p: 916 disambiguations, 29748 queries TBAA oracle: 1766713 disambiguations 3394373 queries 536477 are in alias set 0 694529 queries asked about the same object 0 queries asked about the same alias set 0 access volatile 265709 are dependent in the DAG 130945 are aritificially in conflict with void * PTA query stats: pt_solution_includes: 639122 disambiguations, 922905 queries pt_solutions_intersect: 119319 disambiguations, 506118 queries So 55973 fewer nonoverlapping_component_refs_p calls but 32481 more nonoverlapping_component_refs_since_match_p calls and 9077 more aliasing_component_refs_p calls. The decrease of disambiguations of nonoverlapping_component_refs_p+nonoverlapping_component_refs_since_match_p is caused by fact that aliasing_component_refs_p disambiguates based on the nonoverlapping_ranges more frequently now. Overall there are 11 new disambiguations. lto-bootstrapped/regtested x86_64-linux. OK? * tree-ssa-alias.c (nonoverlapping_component_refs_for_decl_p): Rename to .. (nonoverlapping_component_refs_since_match_p): ... this one; handle also non-decl bases; return -1 if search gave up. (alias_stats): Rename nonoverlapping_component_refs_of_decl_p_may_alias, nonoverlapping_component_refs_of_decl_p_no_alias to nonoverlapping_component_refs_since_match_p_may_alias, nonoverlapping_component_refs_since_match_p_no_alias. (dump_alias_stats): Update dumping. (aliasing_matching_component_refs_p): Break out from ...; dispatch to nonoverlapping_component_refs_for_decl_p and nonoverlapping_component_refs_since_match_p. (aliasing_component_refs_p): ... here; call nonoverlapping_component_refs_p in scenarios where we can not precisely determine base match. (decl_refs_may_alias_p): Use nonoverlapping_component_refs_since_match_p. (indirect_ref_may_alias_decl_p): Do not call nonoverlapping_component_refs_p. (indirect_refs_may_alias_p): Likewise. * gcc.dg/tree-ssa/alias-access-path-7.c: New testcase.