Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
Hi,
(now even including gcc-patches mailing list which we managed to drop
again and Honza whom I forgot to CC the last time)
On Thu, Jun 06 2019, Richard Biener wrote:
> yOn Tue, 4 Jun 2019, Martin Jambor wrote:
>> >> @@ -1822,9 +1863,19 @@ build_ref_for_model (location_t loc, tree base,
>> >> HOST_WIDE_INT offset,
>> >> NULL_TREE);
>> >> }
>> >>else
>> >> -return
>> >> - build_ref_for_offset (loc, base, offset, model->reverse,
>> >> model->type,
>> >> - gsi, insert_after);
>> >> +{
>> >> + tree res;
>> >> + if (model->grp_same_access_path
>> >> + && offset <= model->offset
>> >> + && get_object_alignment (base) >= TYPE_ALIGN (TREE_TYPE (base))
>> >
>> > not sure what this tests - but I think it should be part of the
>> > grp_same_access_path check?
>> >
>>
>> It checks that base is not under-aligned, I was assuming that I can
>> safely construct COMPONENT_REFs and ARRAY_REFs on a properly aligned
>> base. I hope that is still safe even of reference copying with
>> unsharing but of course there is more room for surprises.
>>
>> It cannot be part of grp_same_access_path check because BASE is now
>> something quite different. For example when optimizing
>>
>> s = *p;
>> v = s.i;
>>
>> build_ref_for_model can be called to construct reference to load p->i
>> and BASE is *p, as opposed to grp_same_access_path where the path is
>> based on s.
>
> Oh, I see. Still alignment is ultimatively on the base, so
> there shouldn't be any constraints here. That is, if you
> substitute a base with different alignment the accesses will
> change accordingly and that's independend on whether you
> use a simple MEM_REF or re-build the access path.
>
>>
>> The patch passes bootstrap end testing on x86_64-linux, please let me
>> know if there is anything else you'd like me to adjust.
>
> Looks good to me. As said, eventually the alignment check is
> unnecessary.
OK, thank you.
I am going to commit it and then immediately follow up with a patch
removing the test. The combination has just passed bootstrap and
testing on an x86_64-linux. At least I hope the above is a permission
to do so.
Thanks,
Martin
Subject: [PATCH 2/2] Drop alignment check in build_reconstructed_reference
2019-06-06 Martin Jambor
* tree-sra.c (build_reconstructed_reference): Drop the alignment
check.
---
gcc/tree-sra.c | 3 ---
1 file changed, 3 deletions(-)
diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c
index a246a93a48d..074d4964379 100644
--- a/gcc/tree-sra.c
+++ b/gcc/tree-sra.c
@@ -1817,9 +1817,6 @@ build_reconstructed_reference (location_t, tree base,
struct access *model)
expr = TREE_OPERAND (expr, 0);
}
- if (get_object_alignment (base) < get_object_alignment (expr))
-return NULL;
-
TREE_OPERAND (prev_expr, 0) = base;
tree ref = unshare_expr (model->expr);
TREE_OPERAND (prev_expr, 0) = expr;
--
2.21.0
For the reference of people on the mailing list, the first patch was:
Subject: [PATCH 1/2] Make SRA re-construct orginal memory accesses when easy
2019-06-03 Martin Jambor
* tree-sra.c (struct access): New field grp_same_access_path.
(dump_access): Dump it.
(build_reconstructed_reference): New function.
(build_ref_for_model): Use it if possible.
(path_comparable_for_same_access): New function.
(same_access_path_p): Likewise.
(sort_and_splice_var_accesses): Set the new flag.
(analyze_access_subtree): Likewise.
(propagate_subaccesses_across_link): Propagate zero value of the new
flag down the access tree.
testsuite/
* gcc.dg/tree-ssa/alias-access-path-1.c: Remove -fno-tree-sra option.
* gcc.dg/tree-ssa/ssa-dse-26.c: Disable FRE.
* testsuite/gnat.dg/opt39.adb: Adjust scan dump.
Addressed Richi's comments
---
.../gcc.dg/tree-ssa/alias-access-path-1.c | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-26.c| 2 +-
gcc/testsuite/gnat.dg/opt39.adb | 3 +-
gcc/tree-sra.c| 135 --
4 files changed, 131 insertions(+), 11 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
index 264f72aff0a..ba90b56fe5c 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-fre3 -fno-tree-sra" } */
+/* { dg-options "-O2 -fdump-tree-fre3" } */
struct foo
{
int val;
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-26.c
b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-26.c
index 32d63899b63..836a8092ab9 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-26.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-26.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-dse1-details -fno-short-enums" } */
+/* {
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
On Wed, 29 May 2019, Jan Hubicka wrote:
> Hi,
> this is a variant of testcase I have comitted. Once Martin implements SRA
> part, we could add next variant that drops -fno-tree-sra.
>
> It seems odd that constant propagation only happens in fre3.
> I woud expect fre1 to discover this already.
> The IL before fre1 and 3 differs only by:
>
> test ()
> {
>struct foo foo;
>struct bar * barptr.0_1;
>struct foo * fooptr.1_2;
> - struct bar * barptr.2_3;
> - int _8;
> + int _7;
>
> - :
> + [local count: 1073741824]:
>foo.val = 0;
>barptr.0_1 = barptr;
>barptr.0_1->val2 = 123;
>fooptr.1_2 = fooptr;
>*fooptr.1_2 = foo;
> - barptr.2_3 = barptr;
> - _8 = barptr.2_3->val2;
> + _7 = barptr.0_1->val2;
>foo ={v} {CLOBBER};
> - return _8;
> + return _7;
>
> }
>
> Why VN is not able to optimize the barptr access and lookup through
> it at once? It looks that could potentially save some need to re-run
> GVN since it is common to store pointers to memory and use them multiple
> times to access other pointers.
This is because in the first pass we substitute the value of
barptr.2_3 (barptr.0_1) when looking up barptr.2_3->val2 and
since that happens in VNs IL we run into
ao_ref_init_from_vn_reference which does not re-build
a GENERIC tree for the access path but leaves us with NULL
ao_ref.ref -- I suppose we could put the original ref tree
in there, too, even if the pieces are "valueized", it's just
a more imprecise representation of the ref.
That helps this testcase.
Bootstrap / regtest running on x86_64-unknown-linux-gnu.
Richard.
2019-05-31 Richard Biener
* tree-ssa-sccvn.c (ao_ref_init_from_vn_reference): Get original
full reference tree and record in ref->ref.
(vn_reference_lookup_3): Pass in original ref to
ao_ref_init_from_vn_reference.
(vn_reference_lookup): Likewise.
* tree-ssa-sccvn.h (ao_ref_init_from_vn_reference): Adjust prototype.
* gcc.dg/tree-ssa/alias-access-path-1.c: Scan fre1.
Index: gcc/tree-ssa-sccvn.c
===
--- gcc/tree-ssa-sccvn.c(revision 271803)
+++ gcc/tree-ssa-sccvn.c(working copy)
@@ -995,7 +995,7 @@ copy_reference_ops_from_ref (tree ref, v
bool
ao_ref_init_from_vn_reference (ao_ref *ref,
alias_set_type set, tree type,
- vec ops)
+ vec ops, tree orig_ref)
{
vn_reference_op_t op;
unsigned i;
@@ -1149,7 +1149,7 @@ ao_ref_init_from_vn_reference (ao_ref *r
if (base == NULL_TREE)
return false;
- ref->ref = NULL_TREE;
+ ref->ref = orig_ref;
ref->base = base;
ref->ref_alias_set = set;
if (base_alias_set != -1)
@@ -1976,7 +1976,8 @@ vn_reference_lookup_3 (ao_ref *ref, tree
{
lhs_ref_ok = ao_ref_init_from_vn_reference (_ref,
get_alias_set (lhs),
- TREE_TYPE (lhs), lhs_ops);
+ TREE_TYPE (lhs), lhs_ops,
+ lhs);
if (lhs_ref_ok
&& !refs_may_alias_p_1 (ref, _ref, true))
{
@@ -2718,7 +2719,7 @@ vn_reference_lookup (tree op, tree vuse,
Otherwise preserve the full reference for advanced TBAA. */
if (!valuezied_anything
|| !ao_ref_init_from_vn_reference (, vr1.set, vr1.type,
-vr1.operands))
+vr1.operands, op))
ao_ref_init (, op);
if (! tbaa_p)
r.ref_alias_set = r.base_alias_set = 0;
Index: gcc/tree-ssa-sccvn.h
===
--- gcc/tree-ssa-sccvn.h(revision 271803)
+++ gcc/tree-ssa-sccvn.h(working copy)
@@ -229,7 +229,7 @@ vn_nary_op_t vn_nary_op_insert (tree, tr
vn_nary_op_t vn_nary_op_insert_pieces (unsigned int, enum tree_code,
tree, tree *, tree, unsigned int);
bool ao_ref_init_from_vn_reference (ao_ref *, alias_set_type, tree,
- vec );
+ vec, tree = NULL_TREE);
vec vn_reference_operands_for_lookup (tree);
tree vn_reference_lookup_pieces (tree, alias_set_type, tree,
vec ,
Index: gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
===
--- gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c (revision 271803)
+++ gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c (working copy)
@@ -1,5 +1,6 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-fre3 -fno-tree-sra" } */
+/* { dg-options "-O2 -fdump-tree-fre1 -fno-tree-sra" } */
+
struct foo
{
int val;
@@ -18,4 +19,4 @@ test ()
return barptr->val2;
}
-/* {
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
Hi,
On Wed, May 29 2019, Jan Hubicka wrote:
>> > but we do not optimize it. I.e. optimized dump has:
>> >
>> > test ()
>> > {
>> > struct bar * barptr.0_1;
>> > struct foo * fooptr.1_2;
>> > int _6;
>> >
>> >[local count: 1073741824]:
>> > barptr.0_1 = barptr;
>> > barptr.0_1->val2 = 1;
>> > fooptr.1_2 = fooptr;
>> > MEM[(struct foo *)fooptr.1_2] = 0;
>> > _6 = barptr.0_1->val2;
>> > return _6;
>> > }
>> >
>> > I see no reason why we should not constant propagate the return value.
>>
>> Indeed a good example. Make it work and add it to the testsuite ;)
>
> I think Martin Jambor is working on it. One needs -fno-tree-sra to
> get this optimized :)
> Othewise we punt on the check that both types in MEM_REF are the same.
>
I'd like to fix this with the following patch which passes bootstrap but
I have just found that it makes the following three tests fail:
gcc.dg/tree-ssa/ssa-dse-26.c scan-tree-dump-times dse1 "Deleted dead store: x
= " 1
gcc.dg/tree-ssa/ssa-dse-26.c scan-tree-dump-times dse1 "Deleted dead store: y
= " 1
gnat.dg/opt39.adb scan-tree-dump-times optimized "MEM" 1
Hopefully all require only adjusting the testcase somehow, but it's
still something I need to look at tomorrow. The patch can then be
incrementally improved to also work with one-element arrays which are
however indexed with an SSA_NAME.
As far as alias oracle statistics are concerned, the patch (on top of
r271763) improves from:
Alias oracle query stats:
refs_may_alias_p: 3792598 disambiguations, 4181030 queries
ref_maybe_used_by_call_p: 8291 disambiguations, 3829922 queries
call_may_clobber_ref_p: 1092 disambiguations, 1092 queries
aliasing_component_ref_p: 192 disambiguations, 18684 queries
TBAA oracle: 1820750 disambiguations 3584527 queries
778806 are in alias set 0
723538 queries asked about the same object
0 queries asked about the same alias set
0 access volatile
261267 are dependent in the DAG
166 are aritificially in conflict with void *
to:
Alias oracle query stats:
refs_may_alias_p: 3786679 disambiguations, 4174429 queries
ref_maybe_used_by_call_p: 8285 disambiguations, 3824058 queries
call_may_clobber_ref_p: 1092 disambiguations, 1092 queries
aliasing_component_ref_p: 362 disambiguations, 19215 queries
TBAA oracle: 1822975 disambiguations 3579314 queries
775069 are in alias set 0
727061 queries asked about the same object
0 queries asked about the same alias set
0 access volatile
254043 are dependent in the DAG
166 are aritificially in conflict with void *
Martin
Subject: [PATCH] Make SRA re-construct orginal memory accesses when easy
2019-05-30 Martin Jambor
* tree-sra.c (struct access): New field grp_same_access_path.
(dump_access): Dump it.
(build_reconstructed_reference): New function.
(build_ref_for_model): Use it if possible.
(path_comparable_for_same_access): New function.
(same_access_path_p): Likewise.
(sort_and_splice_var_accesses): Set the new flag.
(analyze_access_subtree): Likewise.
(propagate_subaccesses_across_link): Propagate zero value of the new
flag down the access tree.
testsuite/
* gcc.dg/tree-ssa/alias-access-path-1.c: Remove -fno-tree-sra option.
---
.../gcc.dg/tree-ssa/alias-access-path-1.c | 2 +-
gcc/tree-sra.c| 197 +-
2 files changed, 190 insertions(+), 9 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
index 264f72aff0a..ba90b56fe5c 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/alias-access-path-1.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-fre3 -fno-tree-sra" } */
+/* { dg-options "-O2 -fdump-tree-fre3" } */
struct foo
{
int val;
diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c
index fd51a3d0323..dc2a776d66c 100644
--- a/gcc/tree-sra.c
+++ b/gcc/tree-sra.c
@@ -242,6 +242,10 @@ struct access
access tree. */
unsigned grp_unscalarized_data : 1;
+ /* Set if all accesses in the group consist of the same chain of
+ COMPONENT_REFs and ARRAY_REFs. */
+ unsigned grp_same_access_path : 1;
+
/* Does this access and/or group contain a write access through a
BIT_FIELD_REF? */
unsigned grp_partial_lhs : 1;
@@ -443,16 +447,18 @@ dump_access (FILE *f, struct access *access, bool grp)
"grp_scalar_write = %d, grp_total_scalarization = %d, "
"grp_hint = %d, grp_covered = %d, "
"grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
-"grp_partial_lhs = %d, grp_to_be_replaced = %d, "
-"grp_to_be_debug_replaced = %d, grp_maybe_modified = %d, "
+
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
Hi,
this is a variant of testcase I have comitted. Once Martin implements SRA
part, we could add next variant that drops -fno-tree-sra.
It seems odd that constant propagation only happens in fre3.
I woud expect fre1 to discover this already.
The IL before fre1 and 3 differs only by:
test ()
{
struct foo foo;
struct bar * barptr.0_1;
struct foo * fooptr.1_2;
- struct bar * barptr.2_3;
- int _8;
+ int _7;
- :
+ [local count: 1073741824]:
foo.val = 0;
barptr.0_1 = barptr;
barptr.0_1->val2 = 123;
fooptr.1_2 = fooptr;
*fooptr.1_2 = foo;
- barptr.2_3 = barptr;
- _8 = barptr.2_3->val2;
+ _7 = barptr.0_1->val2;
foo ={v} {CLOBBER};
- return _8;
+ return _7;
}
Why VN is not able to optimize the barptr access and lookup through
it at once? It looks that could potentially save some need to re-run
GVN since it is common to store pointers to memory and use them multiple
times to access other pointers.
* tree-ssa/alias-access-spath-1.c: new testcase.
Index: gcc.dg/tree-ssa/alias-access-path-1.c
===
--- gcc.dg/tree-ssa/alias-access-path-1.c (nonexistent)
+++ gcc.dg/tree-ssa/alias-access-path-1.c (working copy)
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fre3 -fno-tree-sra" } */
+struct foo
+{
+ int val;
+} *fooptr;
+struct bar
+{
+ struct foo foo;
+ int val2;
+} *barptr;
+int
+test ()
+{
+ struct foo foo = { 0 };
+ barptr->val2 = 123;
+ *fooptr = foo;
+ return barptr->val2;
+}
+
+/* { dg-final { scan-tree-dump-times "return 123" 1 "fre3"} } */
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
> > but we do not optimize it. I.e. optimized dump has:
> >
> > test ()
> > {
> > struct bar * barptr.0_1;
> > struct foo * fooptr.1_2;
> > int _6;
> >
> >[local count: 1073741824]:
> > barptr.0_1 = barptr;
> > barptr.0_1->val2 = 1;
> > fooptr.1_2 = fooptr;
> > MEM[(struct foo *)fooptr.1_2] = 0;
> > _6 = barptr.0_1->val2;
> > return _6;
> > }
> >
> > I see no reason why we should not constant propagate the return value.
>
> Indeed a good example. Make it work and add it to the testsuite ;)
I think Martin Jambor is working on it. One needs -fno-tree-sra to
get this optimized :)
Othewise we punt on the check that both types in MEM_REF are the same.
Honza
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
> > /* ??? Array types are not properly unified in all cases as we have > > spurious changes in the index types for example. Removing this > > causes all sorts of problems with the Fortran frontend. */ > > if (TREE_CODE (type1) == ARRAY_TYPE > > && TREE_CODE (type2) == ARRAY_TYPE) > > return -1; > > > > And it causes no regressions. I looked for the history and see you > > added it in 2009 because Fortran mixes up array of chars with char > > itself. I am not sure if that was fixed since then or it is just > > about missing testcase? > > I think we had a testcase back then and I'm not aware of any fixes > here. The introducing mail says we miscompile protein (part of > polyhedron). Another thing about arrays is that unification > doesn't work for VLAs even in C (consider nested fns being > inlined and sharing an array type with the caller), so we cannot > really say ARRAY_TYPEs with non-constant bounds are ever > "not equal". So simply dropping this check looks wrong. > I'm not sure about char[] vs char but the FE definitely can > end up with char vs. char[1] and we need not consider those > different. > > The fortran FE is similarly sloppy in other areas, see > > /* ??? 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); I think the reason why tings work now is the following test: /* ??? 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; If you have arrays of compatible basetype, say int a[10] int b[var] or array and its basetype, say int a[10] int we will end up returning -1 because array alias set is basetype alias set unless it is TYPE_NONALIASED_COMPONENT (and I think those we should be able to skip inside the access patch oracles). With the array check removed we however will disambiguate int a[10]; short a[10]; This has similar effect as logic I implemented in the original patch (i.e. we can prove arrays to be incompatible, but without extra care about VLA bounds we can't prove them to be same) Honza > > > > > It does not seem to be that important, but looks odd > > and makes me woried about other changes :) > > > > Honza > > > > > > Richard. > > > > -- > Richard Biener > SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany; > GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG Nürnberg)
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
On Wed, May 29, 2019 at 3:21 PM Jan Hubicka wrote:
>
> >
> > Please also see if there are testcases that do anything meaningful
> > and FAIL after instead of
> >
> > /* Do access-path based disambiguation. */
> > if (ref1 && ref2
> > && (handled_component_p (ref1) || handled_component_p (ref2)))
> >
> > doing
> >
> > /* Do access-path based disambiguation. */
> > if (ref1 && ref2
> > && (handled_component_p (ref1) && handled_component_p (ref2)))
> >
> On tramp3d we get quite few matches which are attached. If ref1 is
> MEM_REF and ref2 has non-trivial access path then it seems we need:
> 1) ref1 and ref2 to conflict (ref1 is a record or alias set 0)
> 2) basetype2 to contain ref1 (so it conflicts too)
> 3) if ref1 is a record than the access path may go into a type
> contained as field of ref1 but via path not containing ref1 itself.
>
> I tried to construct testcase:
>
> truct foo {int val;} *fooptr;
> struct bar {struct foo foo; int val2;} *barptr;
> int test()
> {
> struct foo foo={0};
> barptr->val2 = 1;
> *fooptr=foo;
> return barptr->val2;
> }
>
> but we do not optimize it. I.e. optimized dump has:
>
> test ()
> {
> struct bar * barptr.0_1;
> struct foo * fooptr.1_2;
> int _6;
>
>[local count: 1073741824]:
> barptr.0_1 = barptr;
> barptr.0_1->val2 = 1;
> fooptr.1_2 = fooptr;
> MEM[(struct foo *)fooptr.1_2] = 0;
> _6 = barptr.0_1->val2;
> return _6;
> }
>
> I see no reason why we should not constant propagate the return value.
Indeed a good example. Make it work and add it to the testsuite ;)
I would have said get_alias_set () on the ref type should already have
disambiguated 'int' (barptr->val2) from *fooptr (struct foo) but of course
they conflict because foo contains 'int'.
I guess it doesn't work because 'struct foo' isn't part of the other
path. Here nonoverlapping_component_refs_of_decl_p would be
the vehicle to use (but IIRC that would also require a common
type in one of both paths).
Richard.
>
> Honza
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
>
> Please also see if there are testcases that do anything meaningful
> and FAIL after instead of
>
> /* Do access-path based disambiguation. */
> if (ref1 && ref2
> && (handled_component_p (ref1) || handled_component_p (ref2)))
>
> doing
>
> /* Do access-path based disambiguation. */
> if (ref1 && ref2
> && (handled_component_p (ref1) && handled_component_p (ref2)))
>
On tramp3d we get quite few matches which are attached. If ref1 is
MEM_REF and ref2 has non-trivial access path then it seems we need:
1) ref1 and ref2 to conflict (ref1 is a record or alias set 0)
2) basetype2 to contain ref1 (so it conflicts too)
3) if ref1 is a record than the access path may go into a type
contained as field of ref1 but via path not containing ref1 itself.
I tried to construct testcase:
truct foo {int val;} *fooptr;
struct bar {struct foo foo; int val2;} *barptr;
int test()
{
struct foo foo={0};
barptr->val2 = 1;
*fooptr=foo;
return barptr->val2;
}
but we do not optimize it. I.e. optimized dump has:
test ()
{
struct bar * barptr.0_1;
struct foo * fooptr.1_2;
int _6;
[local count: 1073741824]:
barptr.0_1 = barptr;
barptr.0_1->val2 = 1;
fooptr.1_2 = fooptr;
MEM[(struct foo *)fooptr.1_2] = 0;
_6 = barptr.0_1->val2;
return _6;
}
I see no reason why we should not constant propagate the return value.
Honza
rep5-sametest2-fits6.gz
Description: application/gzip
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
On Wed, 29 May 2019, Jan Hubicka wrote: > > On Mon, 27 May 2019, Jan Hubicka wrote: > > > > > Hi, > > > this is minimal version of patch adding just the pointer compare. > > > Bootstrapped/regtested x86_64-linux, makes sense? :) > > > > Yes, obviously. > > Thanks, i will go ahead with installing it. > Note that I have also tested removal of: > > /* ??? Array types are not properly unified in all cases as we have > spurious changes in the index types for example. Removing this > causes all sorts of problems with the Fortran frontend. */ > if (TREE_CODE (type1) == ARRAY_TYPE > && TREE_CODE (type2) == ARRAY_TYPE) > return -1; > > And it causes no regressions. I looked for the history and see you > added it in 2009 because Fortran mixes up array of chars with char > itself. I am not sure if that was fixed since then or it is just > about missing testcase? I think we had a testcase back then and I'm not aware of any fixes here. The introducing mail says we miscompile protein (part of polyhedron). Another thing about arrays is that unification doesn't work for VLAs even in C (consider nested fns being inlined and sharing an array type with the caller), so we cannot really say ARRAY_TYPEs with non-constant bounds are ever "not equal". So simply dropping this check looks wrong. I'm not sure about char[] vs char but the FE definitely can end up with char vs. char[1] and we need not consider those different. The fortran FE is similarly sloppy in other areas, see /* ??? 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); > It does not seem to be that important, but looks odd > and makes me woried about other changes :) > > Honza > > > > Richard. > -- Richard Biener SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany; GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG Nürnberg)
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
> On Mon, 27 May 2019, Jan Hubicka wrote: > > > Hi, > > this is minimal version of patch adding just the pointer compare. > > Bootstrapped/regtested x86_64-linux, makes sense? :) > > Yes, obviously. Thanks, i will go ahead with installing it. Note that I have also tested removal of: /* ??? Array types are not properly unified in all cases as we have spurious changes in the index types for example. Removing this causes all sorts of problems with the Fortran frontend. */ if (TREE_CODE (type1) == ARRAY_TYPE && TREE_CODE (type2) == ARRAY_TYPE) return -1; And it causes no regressions. I looked for the history and see you added it in 2009 because Fortran mixes up array of chars with char itself. I am not sure if that was fixed since then or it is just about missing testcase? It does not seem to be that important, but looks odd and makes me woried about other changes :) Honza > > Richard.
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
On Mon, 27 May 2019, Jan Hubicka wrote: > Hi, > this is minimal version of patch adding just the pointer compare. > Bootstrapped/regtested x86_64-linux, makes sense? :) Yes, obviously. Richard.
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
On Mon, 27 May 2019, Jan Hubicka wrote:
> > The way you do it above seeing struct X p will end up comparing
> > 'struct X' but that doesn't really have any say on whether we
> > can apply TBAA to the outermost pointer type which, if used as a base,
> > cannot be subsetted by components anyway.
>
> We remove pointers in pairs so seeing
> struct X p
> struct Y q
> we will end up saying that these pointers are same if struct X and Y are
> same (which we will do by pointer type) or if we can not decide (one of
> them is void).
>
> Non-LTO code returns 0 in the second case, but I think that could be
> considered unsafe when mixing K and ansi-C code.
> >
> > So - why's anything besides treating all structurally equivalent
> > non-composite types as the same sensible here (and not waste of time)?
>
> I think you are right that with current implementation it should not
> make difference. I want eventually to disambiguate
>
> struct foo {struct bar *a;} ptr1;
> struct foobar **ptr2;
>
> ptr1->a and *ptr2;
>
> Here we will currently punt on comparing different pointer types.
> With structural compare we will end up to base because we would
> consider struct foobar * and struct bar * as same types (they are both
> incomplete in LTO now).
But *ptr2 has no access 'path' so we shouldn't even consider it here.
That is, when the innermost reference (for *ptr2 that is a reference
to type foobar *) is of non-aggregate type there's no paths to
disambiguate. That is same_types_for_tbaa shouldn't even be asked
for non-aggregate types...
> Same_types_for_tbaa does not need to form equivalences and if we unwind
> pointers to types mathing odr_comparable_p (i.e. we have two
> accesses originating from C++ code), we can disambiguate incompete
> pointers based on mangled name of types they point to. I have
> incremental patch for that (which futher improves disambiguations to
> about 8000).
> >
> > I realize this is mostly my mess but if we try to "enhance" things
> > we need to make it clearer what we want...
> >
> > Maybe even commonize more code paths (the path TBAA stuff is really
> > replicated in at least two places IIRC).
>
> Yep, I am trying to understand what we need to do here and clean things
> up.
>
> I guess we could handle few independent issues
> 1) if it is safe to return 1 for types that compare as equivalent as
>pointers (currently we return -1 if canonical types are not defined).
>This seems to handle a most common case
> 2) decide what to do about pointers
> 3) decide what to do about arrays
> 4) decide what to do about ODR
> 5) see how much we can merge with alias set & canonical type
> computation.
>
> I would propose first just add
> if (type1 == type2)
> reutrn 1;
That works for me.
> and I will do bit deeper look at the pointers next and produce also some
> testcases.
Please also see if there are testcases that do anything meaningful
and FAIL after instead of
/* Do access-path based disambiguation. */
if (ref1 && ref2
&& (handled_component_p (ref1) || handled_component_p (ref2)))
doing
/* Do access-path based disambiguation. */
if (ref1 && ref2
&& (handled_component_p (ref1) && handled_component_p (ref2)))
Thanks.
Richard.
>
> Honza
> >
> > Richard.
> >
> > > Honza
> > > >
> > > > > + else
> > > > > + {
> > > > > + if (POINTER_TYPE_P (type1) != POINTER_TYPE_P (type2))
> > > > > + return 0;
> > > > > + return in_ptr ? 1 : -1;
> > > > > + }
> > > > > +
> > > > > + if (type1 == type2)
> > > > > +return in_array ? -1 : 1;
> > > > > +}
> > > > >
> > > > >/* Compare the canonical types. */
> > > > >if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
> > > > > -return 1;
> > > > > +return in_array ? -1 : 1;
> > > > >
> > > > >/* ??? Array types are not properly unified in all cases as we have
> > > > > spurious changes in the index types for example. Removing this
> > > > > causes all sorts of problems with the Fortran frontend. */
> > > > >if (TREE_CODE (type1) == ARRAY_TYPE
> > > > >&& TREE_CODE (type2) == ARRAY_TYPE)
> > > > > -return -1;
> > > > > +return in_ptr ? 1 : -1;
> > > > >
> > > > >/* ??? 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
> > > > > @@ -770,7 +858,7 @@ same_type_for_tbaa (tree type1, tree typ
> > > > > 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;
> > > > > +return in_ptr ? 1 : -1;
> > > > >
> > > > >/* The types are known to be not equal. */
> > > > >return 0;
> > > > >
> > > >
> > > > --
> > > > Richard Biener
> > > > SUSE Linux GmbH,
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
Hi, this is minimal version of patch adding just the pointer compare. Bootstrapped/regtested x86_64-linux, makes sense? :) Honza * tree-ssa-alias.c (same_type_for_tbaa): Return 1 if types same as pointers. Index: tree-ssa-alias.c === --- tree-ssa-alias.c(revision 271599) +++ tree-ssa-alias.c(working copy) @@ -787,6 +787,10 @@ same_type_for_tbaa (tree type1, tree typ type1 = TYPE_MAIN_VARIANT (type1); type2 = TYPE_MAIN_VARIANT (type2); + /* Handle common case. */ + if (type1 == type2) +return 1; + /* If we would have to do structural comparison bail out. */ if (TYPE_STRUCTURAL_EQUALITY_P (type1) || TYPE_STRUCTURAL_EQUALITY_P (type2))
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
> The way you do it above seeing struct X p will end up comparing
> 'struct X' but that doesn't really have any say on whether we
> can apply TBAA to the outermost pointer type which, if used as a base,
> cannot be subsetted by components anyway.
We remove pointers in pairs so seeing
struct X p
struct Y q
we will end up saying that these pointers are same if struct X and Y are
same (which we will do by pointer type) or if we can not decide (one of
them is void).
Non-LTO code returns 0 in the second case, but I think that could be
considered unsafe when mixing K and ansi-C code.
>
> So - why's anything besides treating all structurally equivalent
> non-composite types as the same sensible here (and not waste of time)?
I think you are right that with current implementation it should not
make difference. I want eventually to disambiguate
struct foo {struct bar *a;} ptr1;
struct foobar **ptr2;
ptr1->a and *ptr2;
Here we will currently punt on comparing different pointer types.
With structural compare we will end up to base because we would
consider struct foobar * and struct bar * as same types (they are both
incomplete in LTO now).
Same_types_for_tbaa does not need to form equivalences and if we unwind
pointers to types mathing odr_comparable_p (i.e. we have two
accesses originating from C++ code), we can disambiguate incompete
pointers based on mangled name of types they point to. I have
incremental patch for that (which futher improves disambiguations to
about 8000).
>
> I realize this is mostly my mess but if we try to "enhance" things
> we need to make it clearer what we want...
>
> Maybe even commonize more code paths (the path TBAA stuff is really
> replicated in at least two places IIRC).
Yep, I am trying to understand what we need to do here and clean things
up.
I guess we could handle few independent issues
1) if it is safe to return 1 for types that compare as equivalent as
pointers (currently we return -1 if canonical types are not defined).
This seems to handle a most common case
2) decide what to do about pointers
3) decide what to do about arrays
4) decide what to do about ODR
5) see how much we can merge with alias set & canonical type
computation.
I would propose first just add
if (type1 == type2)
reutrn 1;
and I will do bit deeper look at the pointers next and produce also some
testcases.
Honza
>
> Richard.
>
> > Honza
> > >
> > > > + else
> > > > + {
> > > > + if (POINTER_TYPE_P (type1) != POINTER_TYPE_P (type2))
> > > > + return 0;
> > > > + return in_ptr ? 1 : -1;
> > > > + }
> > > > +
> > > > + if (type1 == type2)
> > > > +return in_array ? -1 : 1;
> > > > +}
> > > >
> > > >/* Compare the canonical types. */
> > > >if (TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
> > > > -return 1;
> > > > +return in_array ? -1 : 1;
> > > >
> > > >/* ??? Array types are not properly unified in all cases as we have
> > > > spurious changes in the index types for example. Removing this
> > > > causes all sorts of problems with the Fortran frontend. */
> > > >if (TREE_CODE (type1) == ARRAY_TYPE
> > > >&& TREE_CODE (type2) == ARRAY_TYPE)
> > > > -return -1;
> > > > +return in_ptr ? 1 : -1;
> > > >
> > > >/* ??? 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
> > > > @@ -770,7 +858,7 @@ same_type_for_tbaa (tree type1, tree typ
> > > > 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;
> > > > +return in_ptr ? 1 : -1;
> > > >
> > > >/* The types are known to be not equal. */
> > > >return 0;
> > > >
> > >
> > > --
> > > Richard Biener
> > > SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany;
> > > GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG Nürnberg)
> >
> >
>
> --
> Richard Biener
> SUSE Linux GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany;
> GF: Felix Imendörffer, Mary Higgins, Sri Rasiah; HRB 21284 (AG Nürnberg)
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
On Fri, 24 May 2019, Jan Hubicka wrote:
> > > so about 5 times increase of alias_components_refs_p disambiguations.
> >
> > Note the number of queries also changes so it's "somewhat" comparing
> > apples and oranges (possibly the alias walk doesn't have to give up
> > and thus we walk more and do more queries).
>
> Yep, I know. If you disambiguate you may increase number of queries
> overall because oracles walks further or decrease because tings get
> optimized out.
>
> It is however relatively useful to check if patch is doing something :)
>
> > > + /* If same_type_for_tbaa returns true we make an assumption that
> > > pointers to
> > > + TYPE1 and TYPE2 can either point to same copy of the type or
> > > completely
> > > + different.
> > > +
> > > + This is not necessarily true for arrays where overlap can be partial
> > > + as in gcc.dg/torture/alias-2.c. So we can only prove that arrays
> > > are
> > > + disjoint becuase they are derived from different types but we can
> > > not
> > > + prove they are same.
> > > +
> > > + On the other hand for pointers we can always consider them to be
> > > same
> > > + unless we can prove that pointed-to types are different.
> >
> > What about different address-spaces and/or pointer sizes?
> >
> > > + So normally return values are
> > > + 0 if types are known to be different
> > > + 1 if types are same and there is no partial overlap
> > > + -1 otherwise.
> > > +
> > > + However if comparing two pointers return values are
> > > + 0 if pointed to types are known to be different
> > > + 1 otherwise (because partial overlaps do not happen).
> >
> > Doesn't this apply to all non-composite types? (the "partial overlaps
> > do not happen"?)
>
> I think we should have TYPE_CANONICAL defined on those so the comparsion
> should follow the usual way.
> >
> > > + If comparing array or vector to other type return values are
> > > + 0 if types array/vector are derived from are known to be
> > > different
> > > + -1 otherwise (to watch for partial overlaps). */
> > > +
> > > + bool in_ptr = false;
> > > + bool in_array = false;
> > > +
> > > + if (type1 == type2)
> > > +return 1;
> > > +
> > > + /* Do structural comparsion for types that have no canonical types in
> > > LTO. */
> > > + while (TYPE_STRUCTURAL_EQUALITY_P (type1)
> > > + || TYPE_STRUCTURAL_EQUALITY_P (type2))
> > > +{
> > > + /* Pointer types are same if they point to same types. */
> > > + if (POINTER_TYPE_P (type1) && POINTER_TYPE_P (type2))
> > > + {
> > > + type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
> > > + type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
> > > + if (!in_array)
> > > + in_ptr = true;
> >
> > Don't you run into unrelated types when visiting pointed-to types
> > here? Why would we care for the pointed-to type anwyways?
>
> What do you mean by unrelated type here?
> >
> > That is, the loop should just handle composite types
> > and after it compare non-composite types with
> > types_compatible_p for example? Maybe even do that change
> > independently.
>
> It would probably give more 1s and less 0s which would, in turn, make
> aliasing_component_refs to apply range check (which will return 1)
> instead of concluding that access paths are disjoint.
>
> Why do you think this is better than looking up the pointed-to type
> and comparing that one?
The way you do it above seeing struct X p will end up comparing
'struct X' but that doesn't really have any say on whether we
can apply TBAA to the outermost pointer type which, if used as a base,
cannot be subsetted by components anyway.
So - why's anything besides treating all structurally equivalent
non-composite types as the same sensible here (and not waste of time)?
> >
> > > + }
> > > + /* Peel out arrays and vector to compare inner types. */
> > > + else if ((TREE_CODE (type1) == ARRAY_TYPE
> > > + || TREE_CODE (type1) == VECTOR_TYPE)
> > > +&& TYPE_STRUCTURAL_EQUALITY_P (type1))
> > > + {
> > > + type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
> > > + if (!in_ptr)
> > > + in_array = true;
> > > + }
> > > + else if ((TREE_CODE (type2) == ARRAY_TYPE
> > > + || TREE_CODE (type2) == VECTOR_TYPE)
> > > +&& TYPE_STRUCTURAL_EQUALITY_P (type2))
> > > + {
> > > + type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
> > > + if (!in_ptr)
> > > + in_array = true;
> > > + }
> >
> > I don't think it works like this, peeling arrays/vectors from
> > types individually instead of in lock-step?
>
> The intention here is behave similarly to get_alias_set and handle
> declare arrays/vectors to be the same as the type they are derived from
> + dissabling the assumption about non-existence of partial overlaps.
But this will cause us to use path based disambiguation for, say
a[i][j].b vs. (*p)[k].b, no?
I think we need to clarify what the comparison
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
> I don't think it works like this, peeling arrays/vectors from
> types individually instead of in lock-step?
>
> I think for better testing coverage you want to force
> TYPE_STRUCTURAL_EQUALITY on all types here - this shouldn't
> make things invalid but otherwise these code-paths are not
> tested very well.
Here is coverage of the function compiling tramp3d with -flto.
All the paths through are relatively frequent.
Most of time we call function for case where type1 and type2 have same
main variants. Out of 1.5m remaining cases approx 30k are
pointers/arrays and go the structural walk which in 17k cases goes to
mismatched pointer types.
2k cases are considered equivalent because of canonical check and
126k cases we disprove equivalence.
-: 780:/* Return 1 if TYPE1 and TYPE2 are to be considered equivalent
for the
-: 781: purpose of TBAA. Return 0 if they are distinct and -1 if we
cannot
-: 782: decide. */
-: 783:
-: 784:static inline int
669818: 785:same_type_for_tbaa (tree type1, tree type2)
-: 786:{
669818: 787: type1 = TYPE_MAIN_VARIANT (type1);
669818: 788: type2 = TYPE_MAIN_VARIANT (type2);
-: 789:
-: 790: /* If same_type_for_tbaa returns true we make an assumption
that pointers to
-: 791: TYPE1 and TYPE2 can either point to same copy of the type
or completely
-: 792: different.
-: 793:
-: 794: This is not necessarily true for arrays where overlap can
be partial
-: 795: as in gcc.dg/torture/alias-2.c. So we can only prove that
arrays are
-: 796: disjoint becuase they are derived from different types but
we can not
-: 797: prove they are same.
-: 798:
-: 799: On the other hand for pointers we can always consider them
to be same
-: 800: unless we can prove that pointed-to types are different.
-: 801:
-: 802: So normally return values are
-: 803: 0 if types are known to be different
-: 804: 1 if types are same and there is no partial overlap
-: 805: -1 otherwise.
-: 806:
-: 807: However if comparing two pointers return values are
-: 808: 0 if pointed to types are known to be different
-: 809: 1 otherwise (because partial overlaps do not happen).
-: 810:
-: 811: If comparing array or vector to other type return values
are
-: 812: 0 if types array/vector are derived from are known to
be different
-: 813: -1 otherwise (to watch for partial overlaps). */
-: 814:
669818: 815: bool in_ptr = false;
669818: 816: bool in_array = false;
-: 817:
669818: 818: if (type1 == type2)
515089: 819:return 1;
-: 820:
-: 821: /* Do structural comparsion for types that have no canonical
types in LTO. */
162119: 822: while (TYPE_STRUCTURAL_EQUALITY_P (type1)
162119: 823: || TYPE_STRUCTURAL_EQUALITY_P (type2))
-: 824:{
-: 825: /* Pointer types are same if they point to same types. */
30761: 826: if (POINTER_TYPE_P (type1) && POINTER_TYPE_P (type2))
-: 827:{
4662: 828: type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
4662: 829: type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
4662: 830: if (!in_array)
4662: 831:in_ptr = true;
-: 832:}
-: 833: /* Peel out arrays and vector to compare inner types. */
52198: 834: else if ((TREE_CODE (type1) == ARRAY_TYPE
23728: 835:|| TREE_CODE (type1) == VECTOR_TYPE)
49827: 836: && TYPE_STRUCTURAL_EQUALITY_P (type1))
-: 837:{
2371: 838: type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
2371: 839: if (!in_ptr)
2371: 840:in_array = true;
-: 841:}
47456: 842: else if ((TREE_CODE (type2) == ARRAY_TYPE
21042: 843:|| TREE_CODE (type2) == VECTOR_TYPE)
44770: 844: && TYPE_STRUCTURAL_EQUALITY_P (type2))
-: 845:{
2686: 846: type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
2686: 847: if (!in_ptr)
2686: 848:in_array = true;
-: 849:}
-: 850: else
-: 851:{
21042: 852: if (POINTER_TYPE_P (type1) != POINTER_TYPE_P (type2))
17208: 853:return 0;
3834*: 854: return in_ptr ? 1 : -1;
-: 855:}
-: 856:
9719: 857: if (type1 == type2)
2329: 858:return in_array ? -1 : 1;
-: 859:}
-: 860:
-: 861: /* Compare the canonical types. */
131358: 862: if (TYPE_CANONICAL (type1) ==
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
> > so about 5 times increase of alias_components_refs_p disambiguations.
>
> Note the number of queries also changes so it's "somewhat" comparing
> apples and oranges (possibly the alias walk doesn't have to give up
> and thus we walk more and do more queries).
Yep, I know. If you disambiguate you may increase number of queries
overall because oracles walks further or decrease because tings get
optimized out.
It is however relatively useful to check if patch is doing something :)
> > + /* If same_type_for_tbaa returns true we make an assumption that
> > pointers to
> > + TYPE1 and TYPE2 can either point to same copy of the type or
> > completely
> > + different.
> > +
> > + This is not necessarily true for arrays where overlap can be partial
> > + as in gcc.dg/torture/alias-2.c. So we can only prove that arrays are
> > + disjoint becuase they are derived from different types but we can not
> > + prove they are same.
> > +
> > + On the other hand for pointers we can always consider them to be same
> > + unless we can prove that pointed-to types are different.
>
> What about different address-spaces and/or pointer sizes?
>
> > + So normally return values are
> > + 0 if types are known to be different
> > + 1 if types are same and there is no partial overlap
> > + -1 otherwise.
> > +
> > + However if comparing two pointers return values are
> > + 0 if pointed to types are known to be different
> > + 1 otherwise (because partial overlaps do not happen).
>
> Doesn't this apply to all non-composite types? (the "partial overlaps
> do not happen"?)
I think we should have TYPE_CANONICAL defined on those so the comparsion
should follow the usual way.
>
> > + If comparing array or vector to other type return values are
> > + 0 if types array/vector are derived from are known to be different
> > + -1 otherwise (to watch for partial overlaps). */
> > +
> > + bool in_ptr = false;
> > + bool in_array = false;
> > +
> > + if (type1 == type2)
> > +return 1;
> > +
> > + /* Do structural comparsion for types that have no canonical types in
> > LTO. */
> > + while (TYPE_STRUCTURAL_EQUALITY_P (type1)
> > +|| TYPE_STRUCTURAL_EQUALITY_P (type2))
> > +{
> > + /* Pointer types are same if they point to same types. */
> > + if (POINTER_TYPE_P (type1) && POINTER_TYPE_P (type2))
> > + {
> > + type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
> > + type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
> > + if (!in_array)
> > + in_ptr = true;
>
> Don't you run into unrelated types when visiting pointed-to types
> here? Why would we care for the pointed-to type anwyways?
What do you mean by unrelated type here?
>
> That is, the loop should just handle composite types
> and after it compare non-composite types with
> types_compatible_p for example? Maybe even do that change
> independently.
It would probably give more 1s and less 0s which would, in turn, make
aliasing_component_refs to apply range check (which will return 1)
instead of concluding that access paths are disjoint.
Why do you think this is better than looking up the pointed-to type
and comparing that one?
>
> > + }
> > + /* Peel out arrays and vector to compare inner types. */
> > + else if ((TREE_CODE (type1) == ARRAY_TYPE
> > + || TREE_CODE (type1) == VECTOR_TYPE)
> > + && TYPE_STRUCTURAL_EQUALITY_P (type1))
> > + {
> > + type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
> > + if (!in_ptr)
> > + in_array = true;
> > + }
> > + else if ((TREE_CODE (type2) == ARRAY_TYPE
> > + || TREE_CODE (type2) == VECTOR_TYPE)
> > + && TYPE_STRUCTURAL_EQUALITY_P (type2))
> > + {
> > + type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
> > + if (!in_ptr)
> > + in_array = true;
> > + }
>
> I don't think it works like this, peeling arrays/vectors from
> types individually instead of in lock-step?
The intention here is behave similarly to get_alias_set and handle
declare arrays/vectors to be the same as the type they are derived from
+ dissabling the assumption about non-existence of partial overlaps.
>
> I think for better testing coverage you want to force
> TYPE_STRUCTURAL_EQUALITY on all types here - this shouldn't
> make things invalid but otherwise these code-paths are not
> tested very well.
I played around with this on non-LTO builds bypasing the
TYPE_STRUCTURAL_EQUALITY check. For pointers it agreed with
the TYPE_CANONICAL check, for arrays I run into problems that
same_types_for_tbaa returns 1 because it first check TYPE_CANONICAL for
equality and ARRAY_TYPEs later. There is some code later to special case
this but not very systematic. Such as:
/* But avoid treating arrays as "objects", instead assume they
can overlap by an exact multiple of their element size. */
&& TREE_CODE (TREE_TYPE
Re: Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
On Fri, 24 May 2019, Jan Hubicka wrote: > Hi, > this patch implements basic structura compare so same_type_for_tbaa does > not return -1 for all arrays, vectors and pointers with LTO. > The current TBAA stats for tramp3d are: > > Alias oracle query stats: > refs_may_alias_p: 3016393 disambiguations, 3316783 queries > ref_maybe_used_by_call_p: 7112 disambiguations, 3041993 queries > call_may_clobber_ref_p: 817 disambiguations, 817 queries > aliasing_component_ref_p: 652 disambiguations, 19720 queries > TBAA oracle: 1420658 disambiguations 2918622 queries >552186 are in alias set 0 >569271 queries asked about the same object >0 queries asked about the same alias set >0 access volatile >260166 are dependent in the DAG >116341 are aritificially in conflict with void * > > compared to: > Alias oracle query stats: > refs_may_alias_p: 3013166 disambiguations, 3313523 queries > ref_maybe_used_by_call_p: 7112 disambiguations, 3038766 queries > call_may_clobber_ref_p: 817 disambiguations, 817 queries > aliasing_component_ref_p: 124 disambiguations, 12414 queries > TBAA oracle: 1417999 disambiguations 2914624 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 >258909 are dependent in the DAG >116259 are aritificially in conflict with void * > > so about 5 times increase of alias_components_refs_p disambiguations. Note the number of queries also changes so it's "somewhat" comparing apples and oranges (possibly the alias walk doesn't have to give up and thus we walk more and do more queries). > > The basic idea is simple - pointers are same if points-to types are same > and similarly for arrays/vector. > > I have noticed that a lot of -1s come from comparing void pointers to non-void > because void is structural type we consider incomparable with everyting. > I think for pointers it is OK to return either 0 or 1 and never care about > undecided cases that matters only in the middle of paths. > For this I track if we compare pointers and return this. > > For arrays situation is slightly different - we can only disprove array > equivalence but we do not want to return 1 because we support partial overlaps > on them. The logic about arrays is bit sloppy: some users of > types_same_for_tbaa_p explicitly disallow them while others doesn't and there > are cases where the function returns 1 w/o LTO. We can also handle matches > when > array is not the outer type of whole reference which is a common case. > I plan to clean it up incrementally. > > lto-bootstrapped/regtested x86_64-linux, OK? > > Honza > > * tree-ssa-alias.c (same_type_for_tbaa): Handle structural comparison > of pointers, arrays and vectors. > Index: tree-ssa-alias.c > === > --- tree-ssa-alias.c (revision 271292) > +++ tree-ssa-alias.c (working copy) > @@ -745,21 +767,87 @@ same_type_for_tbaa (tree type1, tree typ >type1 = TYPE_MAIN_VARIANT (type1); >type2 = TYPE_MAIN_VARIANT (type2); > > - /* If we would have to do structural comparison bail out. */ > - if (TYPE_STRUCTURAL_EQUALITY_P (type1) > - || TYPE_STRUCTURAL_EQUALITY_P (type2)) > -return -1; > + /* If same_type_for_tbaa returns true we make an assumption that pointers > to > + TYPE1 and TYPE2 can either point to same copy of the type or completely > + different. > + > + This is not necessarily true for arrays where overlap can be partial > + as in gcc.dg/torture/alias-2.c. So we can only prove that arrays are > + disjoint becuase they are derived from different types but we can not > + prove they are same. > + > + On the other hand for pointers we can always consider them to be same > + unless we can prove that pointed-to types are different. What about different address-spaces and/or pointer sizes? > + So normally return values are > + 0 if types are known to be different > + 1 if types are same and there is no partial overlap > + -1 otherwise. > + > + However if comparing two pointers return values are > + 0 if pointed to types are known to be different > + 1 otherwise (because partial overlaps do not happen). Doesn't this apply to all non-composite types? (the "partial overlaps do not happen"?) > + If comparing array or vector to other type return values are > + 0 if types array/vector are derived from are known to be different > + -1 otherwise (to watch for partial overlaps). */ > + > + bool in_ptr = false; > + bool in_array = false; > + > + if (type1 == type2) > +return 1; > + > + /* Do structural comparsion for types that have no canonical types in LTO. > */ > + while
Teach same_types_for_tbaa to structurally compare arrays, pointers and vectors
Hi,
this patch implements basic structura compare so same_type_for_tbaa does
not return -1 for all arrays, vectors and pointers with LTO.
The current TBAA stats for tramp3d are:
Alias oracle query stats:
refs_may_alias_p: 3016393 disambiguations, 3316783 queries
ref_maybe_used_by_call_p: 7112 disambiguations, 3041993 queries
call_may_clobber_ref_p: 817 disambiguations, 817 queries
aliasing_component_ref_p: 652 disambiguations, 19720 queries
TBAA oracle: 1420658 disambiguations 2918622 queries
552186 are in alias set 0
569271 queries asked about the same object
0 queries asked about the same alias set
0 access volatile
260166 are dependent in the DAG
116341 are aritificially in conflict with void *
compared to:
Alias oracle query stats:
refs_may_alias_p: 3013166 disambiguations, 3313523 queries
ref_maybe_used_by_call_p: 7112 disambiguations, 3038766 queries
call_may_clobber_ref_p: 817 disambiguations, 817 queries
aliasing_component_ref_p: 124 disambiguations, 12414 queries
TBAA oracle: 1417999 disambiguations 2914624 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
258909 are dependent in the DAG
116259 are aritificially in conflict with void *
so about 5 times increase of alias_components_refs_p disambiguations.
The basic idea is simple - pointers are same if points-to types are same
and similarly for arrays/vector.
I have noticed that a lot of -1s come from comparing void pointers to non-void
because void is structural type we consider incomparable with everyting.
I think for pointers it is OK to return either 0 or 1 and never care about
undecided cases that matters only in the middle of paths.
For this I track if we compare pointers and return this.
For arrays situation is slightly different - we can only disprove array
equivalence but we do not want to return 1 because we support partial overlaps
on them. The logic about arrays is bit sloppy: some users of
types_same_for_tbaa_p explicitly disallow them while others doesn't and there
are cases where the function returns 1 w/o LTO. We can also handle matches when
array is not the outer type of whole reference which is a common case.
I plan to clean it up incrementally.
lto-bootstrapped/regtested x86_64-linux, OK?
Honza
* tree-ssa-alias.c (same_type_for_tbaa): Handle structural comparison
of pointers, arrays and vectors.
Index: tree-ssa-alias.c
===
--- tree-ssa-alias.c(revision 271292)
+++ tree-ssa-alias.c(working copy)
@@ -745,21 +767,87 @@ same_type_for_tbaa (tree type1, tree typ
type1 = TYPE_MAIN_VARIANT (type1);
type2 = TYPE_MAIN_VARIANT (type2);
- /* If we would have to do structural comparison bail out. */
- if (TYPE_STRUCTURAL_EQUALITY_P (type1)
- || TYPE_STRUCTURAL_EQUALITY_P (type2))
-return -1;
+ /* If same_type_for_tbaa returns true we make an assumption that pointers to
+ TYPE1 and TYPE2 can either point to same copy of the type or completely
+ different.
+
+ This is not necessarily true for arrays where overlap can be partial
+ as in gcc.dg/torture/alias-2.c. So we can only prove that arrays are
+ disjoint becuase they are derived from different types but we can not
+ prove they are same.
+
+ On the other hand for pointers we can always consider them to be same
+ unless we can prove that pointed-to types are different.
+
+ So normally return values are
+ 0 if types are known to be different
+ 1 if types are same and there is no partial overlap
+ -1 otherwise.
+
+ However if comparing two pointers return values are
+ 0 if pointed to types are known to be different
+ 1 otherwise (because partial overlaps do not happen).
+
+ If comparing array or vector to other type return values are
+ 0 if types array/vector are derived from are known to be different
+ -1 otherwise (to watch for partial overlaps). */
+
+ bool in_ptr = false;
+ bool in_array = false;
+
+ if (type1 == type2)
+return 1;
+
+ /* Do structural comparsion for types that have no canonical types in LTO.
*/
+ while (TYPE_STRUCTURAL_EQUALITY_P (type1)
+|| TYPE_STRUCTURAL_EQUALITY_P (type2))
+{
+ /* Pointer types are same if they point to same types. */
+ if (POINTER_TYPE_P (type1) && POINTER_TYPE_P (type2))
+ {
+ type1 = TYPE_MAIN_VARIANT (TREE_TYPE (type1));
+ type2 = TYPE_MAIN_VARIANT (TREE_TYPE (type2));
+ if (!in_array)
+ in_ptr = true;
+ }
+ /* Peel out arrays and vector to compare inner types. */
+ else if ((TREE_CODE (type1) == ARRAY_TYPE
+ || TREE_CODE (type1) == VECTOR_TYPE)
+
