Do not give up early on access path oracle
Richard Biener
rguenther@suse.de
Mon Jun 17 12:33:00 GMT 2019
On Mon, 17 Jun 2019, Jan Hubicka wrote:
> Hi,
> while working on testcases for nonoverlapping_component_refs_p I run into issue
> that we often bypass it because the indirect-decl and indirect-indirect oracles
> give up if they manage to match bases and ranges_maybe_overlap_p return true.
> (one testcase is included in patch).
>
> The issue is that decl-decl oracle first test base+offsets and if that
> fails it proceeds to nonoverlapping_component_refs_of_decl_p which is
> still able to do some useful disambiguations when the access paths
> contains non-constat ARRAY_REFs where max_size is not very informative.
>
> I modified the other two oracles to avoid the early return which increased
> effectivity of nonoverlapping_component_refs_p and aliasing_component_refs_p
> somewhat but also about doubled number of calls of them.
>
> I can't say if the early return is just omision or intended to save compile time
> but it appeared to me that most of those nondisambiguated comparsions acutally
> covers the case we know that access paths are the same and in such case
> we could still return early.
>
> This patch adds same_access_paths_p which implements simple logic matching
> max_size with type size (thus ruling out variable array accesses) and then
> verifying that there are no unions on the way (in that case we still may have
> different access paths to same memory location.
>
> With this patch I get relatively reasonable increase in number of querries
> and disambiguations.
>
> For tramp3d:
>
> Alias oracle query stats:
> refs_may_alias_p: 3021539 disambiguations, 3321136 queries
> ref_maybe_used_by_call_p: 7118 disambiguations, 3047133 queries
> call_may_clobber_ref_p: 817 disambiguations, 817 queries
> nonoverlapping_component_refs_p: 22 disambiguations, 61735 queries
> nonoverlapping_component_refs_of_decl_p: 19 disambiguations, 2192 queries
> aliasing_component_refs_p: 2050 disambiguations, 19908 queries
> TBAA oracle: 1419961 disambiguations 2916692 queries
> 555158 are in alias set 0
> 575103 queries asked about the same object
> 0 queries asked about the same alias set
> 0 access volatile
> 252874 are dependent in the DAG
> 113596 are aritificially in conflict with void *
>
> PTA query stats:
> pt_solution_includes: 671982 disambiguations, 952513 queries
> pt_solutions_intersect: 97060 disambiguations, 437912 queries
>
> to:
>
> Alias oracle query stats:
> refs_may_alias_p: 3021842 disambiguations, 3321308 queries
> ref_maybe_used_by_call_p: 7118 disambiguations, 3047440 queries
> call_may_clobber_ref_p: 817 disambiguations, 817 queries
> nonoverlapping_component_refs_p: 25 disambiguations, 63108 queries
> nonoverlapping_component_refs_of_decl_p: 19 disambiguations, 2192 queries
> aliasing_component_refs_p: 2236 disambiguations, 20594 queries
> TBAA oracle: 1420030 disambiguations 2918103 queries
> 555158 are in alias set 0
> 575109 queries asked about the same object
> 0 queries asked about the same alias set
> 0 access volatile
> 253260 are dependent in the DAG
> 114546 are aritificially in conflict with void *
>
> PTA query stats:
> pt_solution_includes: 671990 disambiguations, 952532 queries
> pt_solutions_intersect: 97060 disambiguations, 438091 queries
>
> So 3% new querries on wich we seems to have have about 30% disambiguation rate
> (190 new disambiguations)
>
> For cc1:
>
> Alias oracle query stats:
> refs_may_alias_p: 38345354 disambiguations, 46034874 queries
> ref_maybe_used_by_call_p: 57452 disambiguations, 38905700 queries
> call_may_clobber_ref_p: 5856 disambiguations, 8685 queries
> nonoverlapping_component_refs_p: 9674 disambiguations, 743745 queries
> nonoverlapping_component_refs_of_decl_p: 6962 disambiguations, 212637 queries
> aliasing_component_refs_p: 103234 disambiguations, 291017 queries
> TBAA oracle: 10719978 disambiguations 32885735 queries
> 13521045 are in alias set 0
> 5233132 queries asked about the same object
> 200 queries asked about the same alias set
> 0 access volatile
> 1459189 are dependent in the DAG
> 1952191 are aritificially in conflict with void *
>
> PTA query stats:
> pt_solution_includes: 465494 disambiguations, 6918046 queries
> pt_solutions_intersect: 342384 disambiguations, 6435014 queries
>
> to:
>
> Alias oracle query stats:
> refs_may_alias_p: 38345581 disambiguations, 46035002 queries
> ref_maybe_used_by_call_p: 57452 disambiguations, 38905936 queries
> call_may_clobber_ref_p: 5856 disambiguations, 8685 queries
> nonoverlapping_component_refs_p: 9754 disambiguations, 768725 queries
> nonoverlapping_component_refs_of_decl_p: 6962 disambiguations, 212637 queries
> aliasing_component_refs_p: 103316 disambiguations, 314129 queries
> TBAA oracle: 10720037 disambiguations 32893789 queries
> 13521037 are in alias set 0
> 5233163 queries asked about the same object
> 200 queries asked about the same alias set
> 0 access volatile
> 1462737 are dependent in the DAG
> 1956615 are aritificially in conflict with void *
>
> PTA query stats:
> pt_solution_includes: 465494 disambiguations, 6918049 queries
> pt_solutions_intersect: 342386 disambiguations, 6435109 queries
>
> So 23112 (7%) increase in the number of querries to access path and 162 more
> disambiguations which is not great, but I hope it will still increase
> as the access path oracle starts to work better.
>
> It will also let me to glue aliasing_coponent_refs into decl-decl oracle
> w/o wasting too much of compile time. This seems useful since we now
> have a lot of non-trivial MEM_REFs on decls resulting from inlining of
> member functions which we do not disambiguate very well if they mix with
> arrays (nonoverlapping_component_refs_of_decl_p gives up and we do
> nothing except for base/offset/maxsize tests).
>
> Bootstrapped/regtested x86_64-linux, seems reasonable?
>
> * gcc.dg/tree-ssa/alias-access-path-3.c
> * tree-ssa-alias.c (same_access_paths_p): New predicate.
> (indirect_ref_may_alias_decl_p, indirect_refs_may_alias_p):
> Use it.
>
> 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,23 @@
> +/* { 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=124;
> + 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"} } */
> +/* { dg-final { scan-tree-dump-not "return 124" "fre1"} } */
> Index: tree-ssa-alias.c
> ===================================================================
> --- tree-ssa-alias.c (revision 272358)
> +++ tree-ssa-alias.c (working copy)
> @@ -1413,6 +1413,36 @@ decl_refs_may_alias_p (tree ref1, tree b
> return true;
> }
>
> +/* Return true if access paths are same and thus access path
> + oracles can be skiped. This is just a quick check for common
> + cases where we assume that outer types or addresses has been
> + previously matched. */
> +
> +bool
> +same_access_paths_p (tree ref1, poly_int64 max_size1,
> + tree ref2, poly_int64 max_size2)
> +{
> + poly_uint64 size;
> + if (!ref1 || !ref2
> + || !known_eq (max_size1, max_size2)
> + || TYPE_SIZE (TREE_TYPE (ref1)) != TYPE_SIZE (TREE_TYPE (ref2))
> + || !poly_int_tree_p (TYPE_SIZE (TREE_TYPE (ref1)), &size)
> + || !known_eq ((poly_int64)size, max_size1))
> + return false;
> + while (handled_component_p (ref1))
> + {
> + if (!handled_component_p (ref2))
> + return false;
> + if (TREE_CODE (TREE_TYPE (ref1)) == UNION_TYPE
> + || TREE_CODE (TREE_TYPE (ref1))
> + != TREE_CODE (TREE_TYPE (ref2)))
> + return false;
> + ref1 = TREE_OPERAND (ref1, 0);
> + ref2 = TREE_OPERAND (ref2, 0);
> + }
But part of the expensiveness we want to avoid is this
(repeated) walking of the ref tree...
So...
> + return !handled_component_p (ref2);
> +}
> +
> /* Return true if an indirect reference based on *PTR1 constrained
> to [OFFSET1, OFFSET1 + MAX_SIZE1) may alias a variable based on BASE2
> constrained to [OFFSET2, OFFSET2 + MAX_SIZE2). *PTR1 and BASE2 have
> @@ -1533,7 +1563,12 @@ 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 (same_access_paths_p (ref1, max_size1, ref2, max_size2))
> + return true;
how about a simpler test like
if (known_size_p (max_size1) && known_size_p (max_size2))
return true;
/* If there's an unconstrained variable access in the ref fall
through to access-path based disambiguation. */
?
I'd certainly like to see testcases btw...
A more stricter test would be
if (!maybe_eq (max_size1, size1) && !maybe_eq (max_size2, size2))
return true;
/* If there's a variable access in one of the refs fall through
to access-path based disambiguation. */
where you'd need to pass down ao_ref_size in addition to max_size as well.
Richard.
> + }
>
> if (ref1 && ref2
> && nonoverlapping_component_refs_p (ref1, ref2))
> @@ -1613,8 +1648,9 @@ 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 (!ptr_derefs_may_alias_p (ptr1, ptr2))
> return false;
> @@ -1654,7 +1690,12 @@ 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 (same_access_paths_p (ref1, max_size1, ref2, max_size2))
> + return true;
> + }
>
> if (ref1 && ref2
> && nonoverlapping_component_refs_p (ref1, ref2))
>
--
Richard Biener <rguenther@suse.de>
SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany;
GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG NÌrnberg)
More information about the Gcc-patches
mailing list