hello,
only providing you the testcase why I need transitive closure of "contains
pointer" via the extra child I noticed that there is extra symmetry to handle:
struct a {void *ptr;}
char **ptr = (char **)&a.ptr;
ptr = ...
This one doesn't really fly with my extra subset code, because ptr is not
universal pointer, but struct a contains one and thus should conflict with
every pointer. Adding every pointer as subset of every structure with
universal pointer is impractical (childs of those structures would be appearing
as new pointer types get alias sets) and thus indeed it is better to handle it
same way as alias set 0 - by a special case in alias_set_subset_of
and alias_sets_conflict_p.
So I added the second flag - has_pointer that is transitive closure of
is_pointer and added the special case to alias_sets_conflict_p instead of
adding the extra subset relation into the DAG.
I also added statistics and made changes you suggested (making child
hash to be possibly NULL and clenaing up alias set conflict construction)
I also constructed a testcase that covers all the new code paths.
The patch bootstrapped/regtested ppc64-linux. I am not bound to teaching
next week, so if I hear no negative comments, I will schedule commiting the
patch for weekend to deal with possible fallout.
There are few cleanups possible incrementally - i.e. the hash set seems
irrationaly large for average type, we could avoid some pointer travelling
overhead and we could also do better at alias_sets_must_conflict_p.
Honza
* alias.c (alias_set_entry_d): Add is_pointer and has_pointer.
(alias_stats): Add num_universal.
(alias_set_subset_of): Special case pointers; be ready for NULL
children.
(alias_sets_conflict_p): Special case pointers; be ready for NULL
children.
(init_alias_set_entry): Break out from ...
(record_alias_subset): ... here; propagate new fields;
allocate children only when really needed.
(get_alias_set): Do less generous pointer globbing.
(dump_alias_stats_in_alias_c): Update statistics.
* gcc.dg/alias-8.c: Do not xfail.
* gcc.dg/pr62167.c: Prevent FRE.
* gcc.dg/alias-14.c: New testcase.
Index: alias.c
===================================================================
--- alias.c (revision 223772)
+++ alias.c (working copy)
@@ -183,10 +184,6 @@ struct GTY(()) alias_set_entry_d {
/* The alias set number, as stored in MEM_ALIAS_SET. */
alias_set_type alias_set;
- /* Nonzero if would have a child of zero: this effectively makes this
- alias set the same as alias set zero. */
- int has_zero_child;
-
/* The children of the alias set. These are not just the immediate
children, but, in fact, all descendants. So, if we have:
@@ -195,6 +192,17 @@ struct GTY(()) alias_set_entry_d {
continuing our example above, the children here will be all of
`int', `double', `float', and `struct S'. */
hash_map<int, int, alias_set_traits> *children;
+
+ /* Nonzero if would have a child of zero: this effectively makes this
+ alias set the same as alias set zero. */
+ bool has_zero_child;
+ /* Nonzero if alias set corresponds to pointer type itself (i.e. not to
+ aggregate contaiing pointer.
+ This is used for a special case where we need an universal pointer type
+ compatible with all other pointer types. */
+ bool is_pointer;
+ /* Nonzero if is_pointer or if one of childs have has_pointer set. */
+ bool has_pointer;
};
typedef struct alias_set_entry_d *alias_set_entry;
@@ -222,6 +230,7 @@ static struct {
unsigned long long num_same_objects;
unsigned long long num_volatile;
unsigned long long num_dag;
+ unsigned long long num_universal;
unsigned long long num_disambiguated;
} alias_stats;
@@ -454,18 +463,58 @@ mems_in_disjoint_alias_sets_p (const_rtx
bool
alias_set_subset_of (alias_set_type set1, alias_set_type set2)
{
- alias_set_entry ase;
+ alias_set_entry ase2;
/* Everything is a subset of the "aliases everything" set. */
if (set2 == 0)
return true;
- /* Otherwise, check if set1 is a subset of set2. */
- ase = get_alias_set_entry (set2);
- if (ase != 0
- && (ase->has_zero_child
- || ase->children->get (set1)))
+ /* Check if set1 is a subset of set2. */
+ ase2 = get_alias_set_entry (set2);
+ if (ase2 != 0
+ && (ase2->has_zero_child
+ || (ase2->children && ase2->children->get (set1))))
return true;
+
+ /* As a special case we consider alias set of "void *" to be both subset
+ and superset of every alias set of a pointer. This extra symmetry does
+ not matter for alias_sets_conflict_p but it makes
aliasing_component_refs_p
+ to return true on the following testcase:
+
+ void *ptr;
+ char **ptr2=(char **)&ptr;
+ *ptr2 = ...
+
+ Additionally if a set contains universal pointer, we consider every
pointer
+ to be a subset of it, but we do not represent this explicitely - doing so
+ would require us to update transitive closure each time we introduce new
+ pointer type. This makes aliasing_component_refs_p to return true
+ on the following testcase:
+
+ struct a {void *ptr;}
+ char **ptr = (char **)&a.ptr;
+ ptr = ...
+
+ This makes void * truly universal pointer type. See pointer handling in
+ get_alias_set for more details. */
+ if (ase2 && ase2->has_pointer)
+ {
+ alias_set_entry ase1 = get_alias_set_entry (set1);
+
+ if (ase1 && ase1->is_pointer)
+ {
+ alias_set_type voidptr_set = TYPE_ALIAS_SET (ptr_type_node);
+ /* If one is ptr_type_node and other is pointer, then we consider
+ them subset of each other. */
+ if (set1 == voidptr_set || set2 == voidptr_set)
+ return true;
+ /* If SET2 contains universal pointer's alias set, then we consdier
+ every (non-universal) pointer. */
+ if (ase2->children && set1 != voidptr_set
+ && ase2->children->get (voidptr_set))
+ return true;
+ }
+ }
return false;
}
@@ -474,29 +523,68 @@ alias_set_subset_of (alias_set_type set1
int
alias_sets_conflict_p (alias_set_type set1, alias_set_type set2)
{
- alias_set_entry ase;
+ alias_set_entry ase1;
+ alias_set_entry ase2;
/* The easy case. */
if (alias_sets_must_conflict_p (set1, set2))
return 1;
/* See if the first alias set is a subset of the second. */
- ase = get_alias_set_entry (set1);
- if (ase != 0
- && ase->children->get (set2))
+ ase1 = get_alias_set_entry (set1);
+ if (ase1 != 0
+ && ase1->children && ase1->children->get (set2))
{
++alias_stats.num_dag;
return 1;
}
/* Now do the same, but with the alias sets reversed. */
- ase = get_alias_set_entry (set2);
- if (ase != 0
- && ase->children->get (set1))
+ ase2 = get_alias_set_entry (set2);
+ if (ase2 != 0
+ && ase2->children && ase2->children->get (set1))
{
++alias_stats.num_dag;
return 1;
}
+
+ /* We want void * to be compatible with any other pointer without
+ really dropping it to alias set 0. Doing so would make it
+ compatible with all non-pointer types too.
+
+ This is not strictly necessary by the C/C++ language
+ standards, but avoids common type punning mistakes. In
+ addition to that, we need the existence of such universal
+ pointer to implement Fortran's C_PTR type (which is defined as
+ type compatible with all C pointers). */
+ if (ase1 && ase2 && ase1->has_pointer && ase2->has_pointer)
+ {
+ alias_set_type voidptr_set = TYPE_ALIAS_SET (ptr_type_node);
+
+ /* If one of the sets corresponds to universal pointer,
+ we consider it to conflict with anything that is
+ or contains pointer. */
+ if (set1 == voidptr_set || set2 == voidptr_set)
+ {
+ ++alias_stats.num_universal;
+ return true;
+ }
+ /* If one of sets is (non-universal) pointer and the other
+ contains universal pointer, we also get conflict. */
+ if (ase1->is_pointer && set2 != voidptr_set
+ && ase2->children && ase2->children->get (voidptr_set))
+ {
+ ++alias_stats.num_universal;
+ return true;
+ }
+ if (ase2->is_pointer && set1 != voidptr_set
+ && ase1->children && ase1->children->get (voidptr_set))
+ {
+ ++alias_stats.num_universal;
+ return true;
+ }
+ }
+
++alias_stats.num_disambiguated;
/* The two alias sets are distinct and neither one is the
@@ -764,6 +852,22 @@ alias_ptr_types_compatible_p (tree t1, t
== TYPE_MAIN_VARIANT (TREE_TYPE (t2)));
}
+/* Create emptry alias set entry. */
+
+alias_set_entry
+init_alias_set_entry (alias_set_type set)
+{
+ alias_set_entry ase = ggc_alloc<alias_set_entry_d> ();
+ ase->alias_set = set;
+ ase->children = NULL;
+ ase->has_zero_child = false;
+ ase->is_pointer = false;
+ ase->has_pointer = false;
+ gcc_checking_assert (!get_alias_set_entry (set));
+ (*alias_sets)[set] = ase;
+ return ase;
+}
+
/* Return the alias set for T, which may be either a type or an
expression. Call language-specific routine for help, if needed. */
@@ -903,35 +1007,77 @@ get_alias_set (tree t)
the pointed-to types. This issue has been reported to the
C++ committee.
- In addition to the above canonicalization issue, with LTO
- we should also canonicalize `T (*)[]' to `T *' avoiding
- alias issues with pointer-to element types and pointer-to
- array types.
-
- Likewise we need to deal with the situation of incomplete
- pointed-to types and make `*(struct X **)&a' and
- `*(struct X {} **)&a' alias. Otherwise we will have to
- guarantee that all pointer-to incomplete type variants
- will be replaced by pointer-to complete type variants if
- they are available.
-
- With LTO the convenient situation of using `void *' to
- access and store any pointer type will also become
- more apparent (and `void *' is just another pointer-to
- incomplete type). Assigning alias-set zero to `void *'
- and all pointer-to incomplete types is a not appealing
- solution. Assigning an effective alias-set zero only
- affecting pointers might be - by recording proper subset
- relationships of all pointer alias-sets.
-
- Pointer-to function types are another grey area which
- needs caution. Globbing them all into one alias-set
- or the above effective zero set would work.
-
- For now just assign the same alias-set to all pointers.
- That's simple and avoids all the above problems. */
- else if (POINTER_TYPE_P (t)
- && t != ptr_type_node)
+ For this reason go to canonical type of the unqalified pointer type.
+ Until GCC 6 this code set all pointers sets to have alias set of
+ ptr_type_node but that is a bad idea, because it prevents disabiguations
+ in between pointers. For Firefox this accounts about 20% of all
+ disambiguations in the program. */
+ else if (POINTER_TYPE_P (t) && t != ptr_type_node && !in_lto_p)
+ {
+ tree p;
+ auto_vec <bool, 8> reference;
+
+ /* Unnest all pointers and references.
+ We also want to make pointer to array equivalent to pointer to its
+ element. So skip all array types, too. */
+ for (p = t; POINTER_TYPE_P (p)
+ || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p));
+ p = TREE_TYPE (p))
+ {
+ if (TREE_CODE (p) == REFERENCE_TYPE)
+ reference.safe_push (true);
+ if (TREE_CODE (p) == POINTER_TYPE)
+ reference.safe_push (false);
+ }
+ p = TYPE_MAIN_VARIANT (p);
+
+ /* Make void * compatible with char * and also void **.
+ Programs are commonly violating TBAA by this.
+
+ We also make void * to conflict with every pointer
+ (see record_component_aliases) and thus it is safe it to use it for
+ pointers to types with TYPE_STRUCTURAL_EQUALITY_P. */
+ if (TREE_CODE (p) == VOID_TYPE || TYPE_STRUCTURAL_EQUALITY_P (p))
+ set = get_alias_set (ptr_type_node);
+ else
+ {
+ /* Rebuild pointer type from starting from canonical types using
+ unqualified pointers and references only. This way all such
+ pointers will have the same alias set and will conflict with
+ each other.
+
+ Most of time we already have pointers or references of a given
type.
+ If not we build new one just to be sure that if someone later
+ (probably only middle-end can, as we should assign all alias
+ classes only after finishing translation unit) builds the pointer
+ type, the canonical type will match. */
+ p = TYPE_CANONICAL (p);
+ while (!reference.is_empty ())
+ {
+ if (reference.pop ())
+ p = build_reference_type (p);
+ else
+ p = build_pointer_type (p);
+ p = TYPE_CANONICAL (TYPE_MAIN_VARIANT (p));
+ }
+ gcc_checking_assert (TYPE_CANONICAL (p) == p);
+
+ /* Assign the alias set to both p and t.
+ We can not call get_alias_set (p) here as that would trigger
+ infinite recursion when p == t. In other cases it would just
+ trigger unnecesary legwork of rebuilding the pointer again. */
+ if (TYPE_ALIAS_SET_KNOWN_P (p))
+ set = TYPE_ALIAS_SET (p);
+ else
+ {
+ set = new_alias_set ();
+ TYPE_ALIAS_SET (p) = set;
+ }
+ }
+ }
+ /* In LTO the rules above needs to be part of canonical type machinery.
+ For now just punt. */
+ else if (POINTER_TYPE_P (t) && t != ptr_type_node && in_lto_p)
set = get_alias_set (ptr_type_node);
/* Otherwise make a new alias set for this type. */
@@ -953,6 +1099,16 @@ get_alias_set (tree t)
if (AGGREGATE_TYPE_P (t) || TREE_CODE (t) == COMPLEX_TYPE)
record_component_aliases (t);
+ /* We treat pointer types specially in alias_set_subset_of. */
+ if (POINTER_TYPE_P (t) && set)
+ {
+ alias_set_entry ase = get_alias_set_entry (set);
+ if (!ase)
+ ase = init_alias_set_entry (set);
+ ase->is_pointer = true;
+ ase->has_pointer = true;
+ }
+
return set;
}
@@ -1003,12 +1159,7 @@ record_alias_subset (alias_set_type supe
{
/* Create an entry for the SUPERSET, so that we have a place to
attach the SUBSET. */
- superset_entry = ggc_cleared_alloc<alias_set_entry_d> ();
- superset_entry->alias_set = superset;
- superset_entry->children
- = hash_map<int, int, alias_set_traits>::create_ggc (64);
- superset_entry->has_zero_child = 0;
- (*alias_sets)[superset] = superset_entry;
+ superset_entry = init_alias_set_entry (superset);
}
if (subset == 0)
@@ -1016,17 +1167,25 @@ record_alias_subset (alias_set_type supe
else
{
subset_entry = get_alias_set_entry (subset);
+ if (!superset_entry->children)
+ superset_entry->children
+ = hash_map<int, int, alias_set_traits>::create_ggc (64);
/* If there is an entry for the subset, enter all of its children
(if they are not already present) as children of the SUPERSET. */
if (subset_entry)
{
if (subset_entry->has_zero_child)
- superset_entry->has_zero_child = 1;
+ superset_entry->has_zero_child = true;
+ if (subset_entry->has_pointer)
+ superset_entry->has_pointer = true;
- hash_map<int, int, alias_set_traits>::iterator iter
- = subset_entry->children->begin ();
- for (; iter != subset_entry->children->end (); ++iter)
- superset_entry->children->put ((*iter).first, (*iter).second);
+ if (subset_entry->children)
+ {
+ hash_map<int, int, alias_set_traits>::iterator iter
+ = subset_entry->children->begin ();
+ for (; iter != subset_entry->children->end (); ++iter)
+ superset_entry->children->put ((*iter).first, (*iter).second);
+ }
}
/* Enter the SUBSET itself as a child of the SUPERSET. */
@@ -3086,13 +3245,15 @@ dump_alias_stats_in_alias_c (FILE *s)
" %llu queries asked about the same object\n"
" %llu queries asked about the same alias set\n"
" %llu access volatile\n"
- " %llu are dependent in the DAG\n",
+ " %llu are dependent in the DAG\n"
+ " %llu are aritificially in conflict with void *\n",
alias_stats.num_disambiguated,
alias_stats.num_alias_zero + alias_stats.num_same_alias_set
+ alias_stats.num_same_objects + alias_stats.num_volatile
- + alias_stats.num_dag,
+ + alias_stats.num_dag + alias_stats.num_disambiguated
+ + alias_stats.num_universal,
alias_stats.num_alias_zero, alias_stats.num_same_alias_set,
- + alias_stats.num_same_objects, alias_stats.num_volatile,
- + alias_stats.num_dag);
+ alias_stats.num_same_objects, alias_stats.num_volatile,
+ alias_stats.num_dag, alias_stats.num_universal);
}
#include "gt-alias.h"
Index: testsuite/gcc.dg/alias-14.c
===================================================================
--- testsuite/gcc.dg/alias-14.c (revision 0)
+++ testsuite/gcc.dg/alias-14.c (working copy)
@@ -0,0 +1,70 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+#include <stddef.h>
+void *a;
+int *b;
+struct c {void * a;} c;
+struct d {short * a;} d;
+
+int *ip= (int *)(size_t)2;
+int **ipp = &ip;
+
+int
+main()
+{
+ float **ptr;
+ void **uptr;
+ int* const* cipp = (int* const*)ipp;
+ /* as an extension we consider void * universal. Writes to it should alias.
*/
+ asm ("":"=r"(ptr):"0"(&a));
+ a=NULL;
+ *ptr=(float*)(size_t)1;
+ if (!a)
+ __builtin_abort ();
+ a=NULL;
+ if (*ptr)
+ __builtin_abort ();
+
+ asm ("":"=r"(uptr):"0"(&b));
+ b=NULL;
+ *uptr=(void*)(size_t)1;
+ if (!b)
+ __builtin_abort ();
+ b=NULL;
+ if (*uptr)
+ __builtin_abort ();
+
+ /* Check that we disambiguate int * and char *. */
+ asm ("":"=r"(ptr):"0"(&b));
+ b=NULL;
+ *ptr=(float*)(size_t)1;
+ if (b)
+ __builtin_abort ();
+
+ /* Again we should make void * in the structure conflict with any pointer.
*/
+ asm ("":"=r"(ptr):"0"(&c));
+ c.a=NULL;
+ *ptr=(float*)(size_t)1;
+ if (!c.a)
+ __builtin_abort ();
+ c.a=NULL;
+ if (*ptr)
+ __builtin_abort ();
+
+ asm ("":"=r"(uptr):"0"(&d));
+ d.a=NULL;
+ *uptr=(void*)(size_t)1;
+ if (!d.a)
+ __builtin_abort ();
+ d.a=NULL;
+ if (*uptr)
+ __builtin_abort ();
+
+ if ((void *)*cipp != (void*)(size_t)2)
+ __builtin_abort ();
+ *ipp = NULL;
+ if (*cipp)
+ __builtin_abort ();
+
+ return 0;
+}
Index: testsuite/gcc.dg/alias-8.c
===================================================================
--- testsuite/gcc.dg/alias-8.c (revision 223772)
+++ testsuite/gcc.dg/alias-8.c (working copy)
@@ -8,5 +8,5 @@ struct s {
void
func(struct s *ptr)
{
- *(void **)&ptr->p = 0; /* { dg-warning "type-punned pointer" "" { xfail
*-*-* } } */
+ *(void **)&ptr->p = 0; /* { dg-warning "type-punned pointer" "" { } } */
}
Index: testsuite/gcc.dg/pr62167.c
===================================================================
--- testsuite/gcc.dg/pr62167.c (revision 223772)
+++ testsuite/gcc.dg/pr62167.c (working copy)
@@ -29,6 +29,8 @@ main ()
node.prev = (void *)head;
+ asm("":"=m"(node.prev));
+
head->first = &node;
struct node *n = head->first;
