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);
+ }
+ 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;
+ }
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))
