On Thu, 30 May 2019, Jan Hubicka wrote:
> Hi,
> this patch makes aliasing_component_refs_p to not give up at the first
> -1 returned by types_same_for_tbaa_p and continue searching for pairs of types
> we know to be the same. This affects disambiguations as follows:
>
> With patch:
> refs_may_alias_p: 3013678 disambiguations, 3314059 queries
> ref_maybe_used_by_call_p: 7112 disambiguations, 3039278 queries
> call_may_clobber_ref_p: 817 disambiguations, 817 queries
> aliasing_component_ref_p: 636 disambiguations, 15844 queries
> TBAA oracle: 1417999 disambiguations 2915696 queries
> 552182 are in alias set 0
> 569795 queries asked about the same object
> 0 queries asked about the same alias set
> 0 access volatile
> 259437 are dependent in the DAG
> 116283 are aritificially in conflict with void *
>
> Without:
>
> Alias oracle query stats:
> refs_may_alias_p: 3013194 disambiguations, 3313539 queries
> ref_maybe_used_by_call_p: 7112 disambiguations, 3038794 queries
> call_may_clobber_ref_p: 817 disambiguations, 817 queries
> aliasing_component_ref_p: 152 disambiguations, 14285 queries
> TBAA oracle: 1417999 disambiguations 2914656 queries
> 552182 are in alias set 0
> 569275 queries asked about the same object
> 0 queries asked about the same alias set
> 0 access volatile
> 258917 are dependent in the DAG
> 116283 are aritificially in conflict with void *
>
> Basically all comming from disambiguating
> MEM[(const Element_t[3] &)_116][1];
> usedGuards.upper_m[2];
> There are number of similar matches in testsuite.
> More disambiguations would be possible if we did not allow partial
> overlaps of arrays.
>
> I had to however plug a problem with alias-2.c testcase (the one about
> overlapping arrays):
>
> /* We do not want to treat int[3] as an object that cannot overlap
> itself but treat it as arbitrary sub-array of a larger array object. */
> int ar1(int (*p)[3], int (*q)[3])
> {
> (*p)[0] = 1;
> (*q)[1] = 2;
> return (*p)[0];
> }
> int main()
> {
> int a[4];
> if (ar1 ((int (*)[3])&a[1], (int (*)[3])&a[0]) != 2)
> __builtin_abort ();
> return 0;
> }
>
> Previously indirect_refs_may_alias_p bypased the offset+range test because
> it explicitly tests for array types:
>
> /* But avoid treating arrays as "objects", instead assume they
> can overlap by an exact multiple of their element size. */
> && TREE_CODE (TREE_TYPE (ptrtype1)) != ARRAY_TYPE)
> return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2);
>
> Later the code continues to aliasing_component_refs_p which used to give up
> comparing int[3] and int with -1 because of:
>
> /* ??? In Ada, an lvalue of an unconstrained type can be used to access an
> object of one of its constrained subtypes, e.g. when a function with an
> unconstrained parameter passed by reference is called on an object and
> inlined. But, even in the case of a fixed size, type and subtypes are
> not equivalent enough as to share the same TYPE_CANONICAL, since this
> would mean that conversions between them are useless, whereas they are
> not (e.g. type and subtypes can have different modes). So, in the end,
> they are only guaranteed to have the same alias set. */
> if (get_alias_set (type1) == get_alias_set (type2))
> return -1;
>
> This is more of an accident and there are cases where we do not trip across
> this -1 and we disambiguate array accesses that seems unsafe to me.
>
> With my change aliasing_component_refs_p finds the match of the
> array types (type_same_for_tbaa_p returns 1 with non-LTO becuase they
> have same canonical type) and disambiguates based on disjoint access ranges.
>
> I have thus went ahead and updated all uses of type_same_for_tbaa_p to special
> case arrays and reffer to this testcase (which seems odd and is only one in
> testsuite): We can still do useful disambiguation if the array is not toplevel
> reference or we know that the memory object is not bigger. This is tested by a
> testcase I added and is quite frequent in real world code.
>
> I also added check to give up on VLAs since I can not convicne myself that
> this is safe: I think early inlining VLAs and streaming them may lead to
> same VLA type have two different sizes at a time enabling it to partially
> overlap.
OK - sorry for the delay. The array stuff gets a bit ugly so
we eventually want to do sth about that ...
Thanks,
Richard.
> * gcc.dg/lto/alias-access-path-2.0.c: New testcase.
>
> * tree-ssa-alias.c (aliasing_component_refs_p): Do not give up
> immediately after same_types_for_tbaa_p returns -1 and continue
> looking for possible exact match; if matching types are arrays
> watch for partial overlaps.
> (indirect_ref_may_alias_decl_p): Watch for partial array overlaps.
> (indirect_refs_may_alias_p): Do type based disambiguation first;
> update comment.
> Index: testsuite/g++.dg/lto/pr88130_0.C
> ===================================================================
> --- testsuite/g++.dg/lto/pr88130_0.C (nonexistent)
> +++ testsuite/g++.dg/lto/pr88130_0.C (working copy)
> @@ -0,0 +1,28 @@
> +// { dg-lto-do link }
> +// // { dg-lto-options { "-O2 -flto" } }
> +// // { dg-extra-ld-options "-r -nostdlib" }
> +class a {
> +public:
> + static const long b = 1;
> +};
> +struct c {
> + enum d { e };
> +};
> +class C;
> +class f {
> +public:
> + f(c::d);
> + template <typename g> C operator<=(g);
> +};
> +class C {
> +public:
> + template <typename h> void operator!=(h &);
> +};
> +void i() {
> + f j(c::e);
> + try {
> + j <= 0 != a::b;
> + } catch (...) {
> + }
> +}
> +
> Index: testsuite/gcc.dg/lto/alias-access-path-2_0.c
> ===================================================================
> --- testsuite/gcc.dg/lto/alias-access-path-2_0.c (nonexistent)
> +++ testsuite/gcc.dg/lto/alias-access-path-2_0.c (working copy)
> @@ -0,0 +1,38 @@
> +/* { dg-lto-do run } */
> +/* { dg-lto-options { { -O3 -flto -fno-early-inlining } } } */
> +
> +/* In this test the access patch orracle (aliasing_component_refs_p)
> + can disambiguage array[0] from array[1] by base+offset but it needs to be
> + able to find the common type and not give up by not being able to compare
> + types earlier. */
> +
> +typedef int (*fnptr) ();
> +
> +__attribute__ ((used))
> +struct a
> +{
> + void *array[2];
> +} a, *aptr = &a;
> +
> +__attribute__ ((used))
> +struct b
> +{
> + struct a a;
> +} *bptr;
> +
> +static void
> +inline_me_late (int argc)
> +{
> + if (argc == -1)
> + bptr->a.array[1] = bptr;
> +}
> +
> +int
> +main (int argc)
> +{
> + aptr->array[0] = 0;
> + inline_me_late (argc);
> + if (!__builtin_constant_p (aptr->array[0] == 0))
> + __builtin_abort ();
> + return 0;
> +}
> Index: tree-ssa-alias.c
> ===================================================================
> --- tree-ssa-alias.c (revision 271747)
> +++ tree-ssa-alias.c (working copy)
> @@ -850,6 +850,7 @@ aliasing_component_refs_p (tree ref1,
> tree type1, type2;
> tree *refp;
> int same_p1 = 0, same_p2 = 0;
> + bool maybe_match = false;
>
> /* Choose bases and base types to search for. */
> base1 = ref1;
> @@ -880,8 +881,14 @@ aliasing_component_refs_p (tree ref1,
> if (cmp == 0)
> {
> same_p2 = same_type_for_tbaa (TREE_TYPE (*refp), type1);
> - if (same_p2 != 0)
> + if (same_p2 == 1)
> break;
> + /* In case we can't decide whether types are same try to
> + continue looking for the exact match.
> + Remember however that we possibly saw a match
> + to bypass the access path continuations tests we do later. */
> + if (same_p2 == -1)
> + maybe_match = true;
> }
> if (!handled_component_p (*refp))
> break;
> @@ -891,6 +898,21 @@ aliasing_component_refs_p (tree ref1,
> {
> 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. */
> + if (TREE_CODE (TREE_TYPE (base1)) == ARRAY_TYPE
> + && (!TYPE_SIZE (TREE_TYPE (base1))
> + || TREE_CODE (TYPE_SIZE (TREE_TYPE (base1))) != INTEGER_CST
> + || (*refp == base2 && !ref2_is_decl)))
> + {
> + ++alias_stats.aliasing_component_refs_p_may_alias;
> + return true;
> + }
> +
> get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse);
> offset2 -= offadj;
> get_ref_base_and_extent (base1, &offadj, &sztmp, &msztmp, &reverse);
> @@ -922,8 +944,10 @@ aliasing_component_refs_p (tree ref1,
> if (cmp == 0)
> {
> same_p1 = same_type_for_tbaa (TREE_TYPE (*refp), type2);
> - if (same_p1 != 0)
> + if (same_p1 == 1)
> break;
> + if (same_p1 == -1)
> + maybe_match = true;
> }
> if (!handled_component_p (*refp))
> break;
> @@ -934,6 +958,15 @@ aliasing_component_refs_p (tree ref1,
> 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
> + || (*refp == base1 && !ref2_is_decl)))
> + {
> + ++alias_stats.aliasing_component_refs_p_may_alias;
> + return true;
> + }
> +
> get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse);
> offset1 -= offadj;
> get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp, &reverse);
> @@ -955,7 +988,7 @@ aliasing_component_refs_p (tree ref1,
> paths do not overlap and thus accesses alias only if one path can be
> continuation of another. If we was not able to decide about
> equivalence,
> we need to give up. */
> - if (same_p1 == -1 || same_p2 == -1)
> + if (maybe_match)
> return true;
>
> /* If we have two type access paths B1.path1 and B2.path2 they may
> @@ -1338,10 +1371,17 @@ indirect_ref_may_alias_decl_p (tree ref1
> For MEM_REFs we require that the component-ref offset we computed
> is relative to the start of the type which we ensure by
> comparing rvalue and access type and disregarding the constant
> - pointer offset. */
> + pointer offset.
> +
> + But avoid treating variable length arrays as "objects", instead assume
> they
> + can overlap by an exact multiple of their element size.
> + See gcc.dg/torture/alias-2.c. */
> if ((TREE_CODE (base1) != TARGET_MEM_REF
> || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
> - && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (dbase2)) == 1)
> + && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (dbase2)) == 1
> + && (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 (ref1 && ref2
> @@ -1434,6 +1474,16 @@ indirect_refs_may_alias_p (tree ref1 ATT
> || base2_alias_set == 0)
> return true;
>
> + /* Do type-based disambiguation. */
> + if (base1_alias_set != base2_alias_set
> + && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
> + return false;
> +
> + /* If either reference is view-converted, give up now. */
> + if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) != 1
> + || same_type_for_tbaa (TREE_TYPE (base2), TREE_TYPE (ptrtype2)) != 1)
> + return true;
> +
> /* If both references are through the same type, they do not alias
> if the accesses do not overlap. This does extra disambiguation
> for mixed/pointer accesses but requires strict aliasing. */
> @@ -1441,25 +1491,14 @@ indirect_refs_may_alias_p (tree ref1 ATT
> || (!TMR_INDEX (base1) && !TMR_INDEX2 (base1)))
> && (TREE_CODE (base2) != TARGET_MEM_REF
> || (!TMR_INDEX (base2) && !TMR_INDEX2 (base2)))
> - && same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) == 1
> - && same_type_for_tbaa (TREE_TYPE (base2), TREE_TYPE (ptrtype2)) == 1
> && same_type_for_tbaa (TREE_TYPE (ptrtype1),
> TREE_TYPE (ptrtype2)) == 1
> /* But avoid treating arrays as "objects", instead assume they
> - can overlap by an exact multiple of their element size. */
> + 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);
>
> - /* Do type-based disambiguation. */
> - if (base1_alias_set != base2_alias_set
> - && !alias_sets_conflict_p (base1_alias_set, base2_alias_set))
> - return false;
> -
> - /* If either reference is view-converted, give up now. */
> - if (same_type_for_tbaa (TREE_TYPE (base1), TREE_TYPE (ptrtype1)) != 1
> - || same_type_for_tbaa (TREE_TYPE (base2), TREE_TYPE (ptrtype2)) != 1)
> - return true;
> -
> if (ref1 && ref2
> && nonoverlapping_component_refs_p (ref1, ref2))
> return false;
>
--
Richard Biener <rguent...@suse.de>
SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany;
GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG Nürnberg)
