On Tue, 2 Jul 2019, Jan Hubicka wrote:
> 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.
Yeah, that sounds worthwhile (this function is the worst offender
compile-time wise)
> 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"} } */
Why does this only happen in fre3?!
Otherwise OK.
Thanks,
Richard.
> 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);
>
