Enable pointer TBAA for LTO

Enable pointer TBAA for LTO

[Jan Hubicka]

Hi,
this patch adds basic TBAA for pointers to LTO.  The basic scheme is simple;
because TYPE_CANONICAL is not really needed by get_alias_set, we completely
drop the caluclation of these (which also saves about 50% canonical type hash
searches) and update get_alias_set to not punt on pointers with
TYPE_STRUCTURAL_EQUALITY.

The patch makes quite nice improvements (32%) on number of disambiguations on
dealII (that is my random C++ testbed):

Before:
[WPA] GIMPLE canonical type table: size 16381, 817 elements, 35453 searches, 91 collisions (ratio: 0.002567)
[WPA] GIMPLE canonical type pointer-map: 817 elements, 15570 searches           

after:
[WPA] GIMPLE canonical type table: size 16381, 822 elements, 14863 searches, 114 collisions (ratio: 0.007670)
[WPA] GIMPLE canonical type pointer-map: 822 elements, 12663 searches           

The number of disambiguations goes 1713472->2331078 (32%)
and number of queries goes 3387753->3669698 (8%)
We get code size growth 677527->701782 (3%)

Also a query is disambiguated 63% of the time instead of 50% we had before.

Clearly there are many areas for improvements (since functions are
TYPE_STRUCTURAL_EQUALITY in LTO we ptr_type_node alias set on them), but that
M
can wait for next stage1.

lto-bootstrapped/regtested x86_64-linux and also used it in my tree for quite
a while, so the patch was tested on Firefox and other applications.

OK?
Honza

	* alias.c (get_alias_set): Do structural equality for pointer types;
	drop LTO specific path.
	* lto.c (iterative_hash_canonical_type): Do not compute TYPE_CANONICAL
	for pointer types.
	(gimple_register_canonical_type_1): Likewise.
	(gimple_register_canonical_type): Likewise.
	(lto_register_canonical_types): Do not clear canonical types of pointer
	types.
Index: lto/lto.c
===================================================================
--- lto/lto.c	(revision 229968)
+++ lto/lto.c	(working copy)
@@ -396,8 +396,13 @@ iterative_hash_canonical_type (tree type
 
   /* All type variants have same TYPE_CANONICAL.  */
   type = TYPE_MAIN_VARIANT (type);
+
+  /* We do not compute TYPE_CANONICAl of POINTER_TYPE becuase the aliasing
+     code never use it anyway.  */
+  if (POINTER_TYPE_P (type))
+    v = hash_canonical_type (type);
   /* An already processed type.  */
-  if (TYPE_CANONICAL (type))
+  else if (TYPE_CANONICAL (type))
     {
       type = TYPE_CANONICAL (type);
       v = gimple_canonical_type_hash (type);
@@ -445,7 +450,9 @@ gimple_register_canonical_type_1 (tree t
 {
   void **slot;
 
-  gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t));
+  gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t)
+		       && type_with_alias_set_p (t)
+		       && TREE_CODE (t) != POINTER_TYPE);
 
   slot = htab_find_slot_with_hash (gimple_canonical_types, t, hash, INSERT);
   if (*slot)
@@ -478,7 +485,7 @@ gimple_register_canonical_type_1 (tree t
 static void
 gimple_register_canonical_type (tree t)
 {
-  if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t))
+  if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t) || POINTER_TYPE_P (t))
     return;
 
   /* Canonical types are same among all complete variants.  */
@@ -498,14 +505,13 @@ static void
 lto_register_canonical_types (tree node, bool first_p)
 {
   if (!node
-      || !TYPE_P (node))
+      || !TYPE_P (node) || POINTER_TYPE_P (node))
     return;
 
   if (first_p)
     TYPE_CANONICAL (node) = NULL_TREE;
 
-  if (POINTER_TYPE_P (node)
-      || TREE_CODE (node) == COMPLEX_TYPE
+  if (TREE_CODE (node) == COMPLEX_TYPE
       || TREE_CODE (node) == ARRAY_TYPE)
     lto_register_canonical_types (TREE_TYPE (node), first_p);
 
Index: tree.c
===================================================================
--- tree.c	(revision 229968)
+++ tree.c	(working copy)
@@ -13198,6 +13198,7 @@ gimple_canonical_types_compatible_p (con
   /* If the types have been previously registered and found equal
      they still are.  */
   if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t2)
+      && !POINTER_TYPE_P (t1) && !POINTER_TYPE_P (t2)
       && trust_type_canonical)
     return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
 
Index: alias.c
===================================================================
--- alias.c	(revision 229968)
+++ alias.c	(working copy)
@@ -869,13 +874,19 @@ get_alias_set (tree t)
       set = lang_hooks.get_alias_set (t);
       if (set != -1)
 	return set;
-      return 0;
+      /* LTO frontend does not assign canonical types to pointers (which we
+	 ignore anyway) and we compute them.  The following path may be
+	 probably enabled for non-LTO, too, and it may improve TBAA for
+	 pointers to types with structural equality.  */
+      if (!in_lto_p || !POINTER_TYPE_P (t))
+        return 0;
+    }
+  else
+    {
+      t = TYPE_CANONICAL (t);
+      /* The canonical type should not require structural equality checks.  */
+      gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
     }
-
-  t = TYPE_CANONICAL (t);
-
-  /* The canonical type should not require structural equality checks.  */
-  gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
 
   /* If this is a type with a known alias set, return it.  */
   if (TYPE_ALIAS_SET_KNOWN_P (t))
@@ -952,20 +963,23 @@ get_alias_set (tree t)
      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)
+  else if (POINTER_TYPE_P (t) && t != ptr_type_node)
     {
       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.  */
+	 We also want to make pointer to array/vector equivalent to pointer to
+	 its element (see the reasoning above). Skip all those types, too.  */
       for (p = t; POINTER_TYPE_P (p)
-	   || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p));
+	   || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p))
+	   || TREE_CODE (p) == VECTOR_TYPE;
 	   p = TREE_TYPE (p))
 	{
 	  if (TREE_CODE (p) == REFERENCE_TYPE)
-	    reference.safe_push (true);
+	    /* In LTO we want languages that use references to be compatible
+ 	       with languages that use pointers.  */
+	    reference.safe_push (true && !in_lto_p);
 	  if (TREE_CODE (p) == POINTER_TYPE)
 	    reference.safe_push (false);
 	}
@@ -998,9 +1012,23 @@ get_alias_set (tree t)
 		p = build_reference_type (p);
 	      else
 		p = build_pointer_type (p);
-	      p = TYPE_CANONICAL (TYPE_MAIN_VARIANT (p));
+	      p = TYPE_MAIN_VARIANT (p);
+	      /* Normally all pointer types are built by
+ 		 build_pointer_type_for_mode which ensures they have canonical
+		 type unless they point to type with structural equality.
+		 LTO frontend produce pointer types without TYPE_CANONICAL
+		 that are then added to TYPE_POINTER_TO lists and 
+		 build_pointer_type_for_mode will end up picking one for us.
+		 Declare it the canonical one.  This is the same as
+		 build_pointer_type_for_mode would do. */
+	      if (!TYPE_CANONICAL (p))
+		{
+		  TYPE_CANONICAL (p) = p;
+		  gcc_checking_assert (in_lto_p);
+		}
+	      else
+	        gcc_checking_assert (p == TYPE_CANONICAL (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
@@ -1015,11 +1043,6 @@ get_alias_set (tree t)
 	    }
 	}
     }
-  /* In LTO the rules above needs to be part of canonical type machinery.
-     For now just punt.  */
-  else if (POINTER_TYPE_P (t)
-	   && t != TYPE_CANONICAL (ptr_type_node) && in_lto_p)
-    set = get_alias_set (TYPE_CANONICAL (ptr_type_node));
 
   /* Otherwise make a new alias set for this type.  */
   else

Re: Enable pointer TBAA for LTO

[Richard Biener]

On Sun, 8 Nov 2015, Jan Hubicka wrote:

> Hi,
> this patch adds basic TBAA for pointers to LTO.  The basic scheme is simple;
> because TYPE_CANONICAL is not really needed by get_alias_set, we completely
> drop the caluclation of these (which also saves about 50% canonical type hash
> searches) and update get_alias_set to not punt on pointers with
> TYPE_STRUCTURAL_EQUALITY.
> 
> The patch makes quite nice improvements (32%) on number of disambiguations on
> dealII (that is my random C++ testbed):
> 
> Before:
> [WPA] GIMPLE canonical type table: size 16381, 817 elements, 35453 searches, 91 collisions (ratio: 0.002567)
> [WPA] GIMPLE canonical type pointer-map: 817 elements, 15570 searches           
> 
> after:
> [WPA] GIMPLE canonical type table: size 16381, 822 elements, 14863 searches, 114 collisions (ratio: 0.007670)
> [WPA] GIMPLE canonical type pointer-map: 822 elements, 12663 searches           
> 
> The number of disambiguations goes 1713472->2331078 (32%)
> and number of queries goes 3387753->3669698 (8%)
> We get code size growth 677527->701782 (3%)
> 
> Also a query is disambiguated 63% of the time instead of 50% we had before.
> 
> Clearly there are many areas for improvements (since functions are
> TYPE_STRUCTURAL_EQUALITY in LTO we ptr_type_node alias set on them), but that
> M
> can wait for next stage1.
> 
> lto-bootstrapped/regtested x86_64-linux and also used it in my tree for quite
> a while, so the patch was tested on Firefox and other applications.
> 
> OK?
> Honza
> 
> 	* alias.c (get_alias_set): Do structural equality for pointer types;
> 	drop LTO specific path.
> 	* lto.c (iterative_hash_canonical_type): Do not compute TYPE_CANONICAL
> 	for pointer types.
> 	(gimple_register_canonical_type_1): Likewise.
> 	(gimple_register_canonical_type): Likewise.
> 	(lto_register_canonical_types): Do not clear canonical types of pointer
> 	types.
> Index: lto/lto.c
> ===================================================================
> --- lto/lto.c	(revision 229968)
> +++ lto/lto.c	(working copy)
> @@ -396,8 +396,13 @@ iterative_hash_canonical_type (tree type
>  
>    /* All type variants have same TYPE_CANONICAL.  */
>    type = TYPE_MAIN_VARIANT (type);
> +
> +  /* We do not compute TYPE_CANONICAl of POINTER_TYPE becuase the aliasing
> +     code never use it anyway.  */
> +  if (POINTER_TYPE_P (type))
> +    v = hash_canonical_type (type);
>    /* An already processed type.  */
> -  if (TYPE_CANONICAL (type))
> +  else if (TYPE_CANONICAL (type))
>      {
>        type = TYPE_CANONICAL (type);
>        v = gimple_canonical_type_hash (type);
> @@ -445,7 +450,9 @@ gimple_register_canonical_type_1 (tree t
>  {
>    void **slot;
>  
> -  gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t));
> +  gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t)
> +		       && type_with_alias_set_p (t)
> +		       && TREE_CODE (t) != POINTER_TYPE);

POINTER_TYPE_P

>  
>    slot = htab_find_slot_with_hash (gimple_canonical_types, t, hash, INSERT);
>    if (*slot)
> @@ -478,7 +485,7 @@ gimple_register_canonical_type_1 (tree t
>  static void
>  gimple_register_canonical_type (tree t)
>  {
> -  if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t))
> +  if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t) || POINTER_TYPE_P (t))
>      return;
>  
>    /* Canonical types are same among all complete variants.  */
> @@ -498,14 +505,13 @@ static void
>  lto_register_canonical_types (tree node, bool first_p)
>  {
>    if (!node
> -      || !TYPE_P (node))
> +      || !TYPE_P (node) || POINTER_TYPE_P (node))
>      return;
>  
>    if (first_p)
>      TYPE_CANONICAL (node) = NULL_TREE;
>  
> -  if (POINTER_TYPE_P (node)
> -      || TREE_CODE (node) == COMPLEX_TYPE
> +  if (TREE_CODE (node) == COMPLEX_TYPE
>        || TREE_CODE (node) == ARRAY_TYPE)
>      lto_register_canonical_types (TREE_TYPE (node), first_p);

Hmm, here we'll miss registering canoncial types for the
pointed-to type.  I believe this will miss FILE for example but also
some va_list types?  Please drop this change.

> Index: tree.c
> ===================================================================
> --- tree.c	(revision 229968)
> +++ tree.c	(working copy)
> @@ -13198,6 +13198,7 @@ gimple_canonical_types_compatible_p (con
>    /* If the types have been previously registered and found equal
>       they still are.  */
>    if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t2)
> +      && !POINTER_TYPE_P (t1) && !POINTER_TYPE_P (t2)

But TYPE_CANONICAL (t1) should be NULL_TREE for POINTER_TYPE_P?

>        && trust_type_canonical)
>      return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
>  
> Index: alias.c
> ===================================================================
> --- alias.c	(revision 229968)
> +++ alias.c	(working copy)
> @@ -869,13 +874,19 @@ get_alias_set (tree t)
>        set = lang_hooks.get_alias_set (t);
>        if (set != -1)
>  	return set;
> -      return 0;
> +      /* LTO frontend does not assign canonical types to pointers (which we
> +	 ignore anyway) and we compute them.  The following path may be
> +	 probably enabled for non-LTO, too, and it may improve TBAA for
> +	 pointers to types with structural equality.  */
> +      if (!in_lto_p || !POINTER_TYPE_P (t))
> +        return 0;

No new LTO paths please, do the suggested change immediately.

> +    }
> +  else
> +    {
> +      t = TYPE_CANONICAL (t);
> +      /* The canonical type should not require structural equality checks.  */
> +      gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
>      }
> -
> -  t = TYPE_CANONICAL (t);
> -
> -  /* The canonical type should not require structural equality checks.  */
> -  gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
>  
>    /* If this is a type with a known alias set, return it.  */
>    if (TYPE_ALIAS_SET_KNOWN_P (t))
> @@ -952,20 +963,23 @@ get_alias_set (tree t)
>       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)
> +  else if (POINTER_TYPE_P (t) && t != ptr_type_node)
>      {
>        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.  */
> +	 We also want to make pointer to array/vector equivalent to pointer to
> +	 its element (see the reasoning above). Skip all those types, too.  */
>        for (p = t; POINTER_TYPE_P (p)
> -	   || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p));
> +	   || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p))
> +	   || TREE_CODE (p) == VECTOR_TYPE;
>  	   p = TREE_TYPE (p))
>  	{
>  	  if (TREE_CODE (p) == REFERENCE_TYPE)
> -	    reference.safe_push (true);
> +	    /* In LTO we want languages that use references to be compatible
> + 	       with languages that use pointers.  */
> +	    reference.safe_push (true && !in_lto_p);
>  	  if (TREE_CODE (p) == POINTER_TYPE)
>  	    reference.safe_push (false);
>  	}
> @@ -998,9 +1012,23 @@ get_alias_set (tree t)
>  		p = build_reference_type (p);
>  	      else
>  		p = build_pointer_type (p);
> -	      p = TYPE_CANONICAL (TYPE_MAIN_VARIANT (p));
> +	      p = TYPE_MAIN_VARIANT (p);
> +	      /* Normally all pointer types are built by
> + 		 build_pointer_type_for_mode which ensures they have canonical
> +		 type unless they point to type with structural equality.
> +		 LTO frontend produce pointer types without TYPE_CANONICAL
> +		 that are then added to TYPE_POINTER_TO lists and 
> +		 build_pointer_type_for_mode will end up picking one for us.
> +		 Declare it the canonical one.  This is the same as
> +		 build_pointer_type_for_mode would do. */
> +	      if (!TYPE_CANONICAL (p))
> +		{
> +		  TYPE_CANONICAL (p) = p;
> +		  gcc_checking_assert (in_lto_p);
> +		}
> +	      else
> +	        gcc_checking_assert (p == TYPE_CANONICAL (p));

The assert can trigger as
build_pointer_type_for_mode builds SET_TYPE_STRUCTURAL_EQUALITY pointer
types for SET_TYPE_STRUCTURAL_EQUALITY pointed-to types.  Ah,
looking up more context reveals

      if (TREE_CODE (p) == VOID_TYPE || TYPE_STRUCTURAL_EQUALITY_P (p))
        set = get_alias_set (ptr_type_node);

Not sure why you adjust TYPE_CANONICAL here at all either.

Otherwise looks ok.

RIchard.


>  	    }
> -          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
> @@ -1015,11 +1043,6 @@ get_alias_set (tree t)
>  	    }
>  	}
>      }
> -  /* In LTO the rules above needs to be part of canonical type machinery.
> -     For now just punt.  */
> -  else if (POINTER_TYPE_P (t)
> -	   && t != TYPE_CANONICAL (ptr_type_node) && in_lto_p)
> -    set = get_alias_set (TYPE_CANONICAL (ptr_type_node));
>  
>    /* Otherwise make a new alias set for this type.  */
>    else
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Re: Enable pointer TBAA for LTO

[Jan Hubicka]

> > Index: tree.c
> > ===================================================================
> > --- tree.c	(revision 229968)
> > +++ tree.c	(working copy)
> > @@ -13198,6 +13198,7 @@ gimple_canonical_types_compatible_p (con
> >    /* If the types have been previously registered and found equal
> >       they still are.  */
> >    if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t2)
> > +      && !POINTER_TYPE_P (t1) && !POINTER_TYPE_P (t2)
> 
> But TYPE_CANONICAL (t1) should be NULL_TREE for POINTER_TYPE_P?

The reason is that TYPE_CANONICAL is initialized in get_alias_set that may be
called before we finish all merging and then it is more fine grained than what
we need here (i.e. TYPE_CANONICAL of pointers to two differnt types will be
different, but here we want them to be equal so we can match:

struct aa { void *ptr;};
struct bb { int * ptr;};

Which is actually required for Fortran interoperability.

Removing this hunk triggers false type incompatibility warning in one of the
interoperability testcases I added.

Even if I drop the code bellow setting TYPE_CANOINCAL, I think I need to keep
this conditional: the types may be built in and those get TYPE_CANONICAL set as
they are constructed by build_pointer_type.  I can gcc_checking_assert for this
scenario and see.  Perhaps we never build LTO type from builtin type and this
won't happen. If we did, we would probably have a trouble with false negatives
in return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2); on non-pointers anyway.
> 
> >        && trust_type_canonical)
> >      return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
> >  
> > Index: alias.c
> > ===================================================================
> > --- alias.c	(revision 229968)
> > +++ alias.c	(working copy)
> > @@ -869,13 +874,19 @@ get_alias_set (tree t)
> >        set = lang_hooks.get_alias_set (t);
> >        if (set != -1)
> >  	return set;
> > -      return 0;
> > +      /* LTO frontend does not assign canonical types to pointers (which we
> > +	 ignore anyway) and we compute them.  The following path may be
> > +	 probably enabled for non-LTO, too, and it may improve TBAA for
> > +	 pointers to types with structural equality.  */
> > +      if (!in_lto_p || !POINTER_TYPE_P (t))
> > +        return 0;
> 
> No new LTO paths please, do the suggested change immediately.

OK, I originally tested the patch without if and there was no problems.
Just chickened out before preparing final version of the patch.
> > +	      p = TYPE_MAIN_VARIANT (p);
> > +	      /* Normally all pointer types are built by
> > + 		 build_pointer_type_for_mode which ensures they have canonical
> > +		 type unless they point to type with structural equality.
> > +		 LTO frontend produce pointer types without TYPE_CANONICAL
> > +		 that are then added to TYPE_POINTER_TO lists and 
> > +		 build_pointer_type_for_mode will end up picking one for us.
> > +		 Declare it the canonical one.  This is the same as
> > +		 build_pointer_type_for_mode would do. */
> > +	      if (!TYPE_CANONICAL (p))
> > +		{
> > +		  TYPE_CANONICAL (p) = p;
> > +		  gcc_checking_assert (in_lto_p);
> > +		}
> > +	      else
> > +	        gcc_checking_assert (p == TYPE_CANONICAL (p));
> 
> The assert can trigger as
> build_pointer_type_for_mode builds SET_TYPE_STRUCTURAL_EQUALITY pointer
> types for SET_TYPE_STRUCTURAL_EQUALITY pointed-to types.  Ah,
> looking up more context reveals
> 
>       if (TREE_CODE (p) == VOID_TYPE || TYPE_STRUCTURAL_EQUALITY_P (p))
>         set = get_alias_set (ptr_type_node);

Yep, we don't get here.
> 
> Not sure why you adjust TYPE_CANONICAL here at all either.

You are right, I may probably just drop all the code and just do:
gcc_checking_assert (!TYPE_CANONICAL || p == TYPE_CANONICAL (p));
I will test this and re-think the build_pointer_type code to be sure that we
won't get into a problem there.

As I recall, the original code
  p = TYPE_CANONICAL (p);
was there to permit frontends to glob two pointers by setting same canonical
type to them.  My original plan was to use this for LTO frotnend and make
gimple_compare_canonical_types to do the right thing for pointers and this would
follow gimple_compare_canonical_types globbing then.

This idea was wrong: since pointer rules are not transitive (i.e. void
* alias them all), we can't model that by an equivalence produced by
gimple_compare_canonical_types.

Since the assert does not trigger, seems no frontend is doing that and moreover
I do not see how that would be useful (well, perhaps for some kind of internal
bookeeping when build TYPE_CANONICAL of more complex types from pointer types,
like arrays, but for those we ignore TYPE_CANONICAL anyway).  Grepping over
TYPE_CANONICAL sets in frotneds, I see no code that I would suspect from doing
something like this.

Thank you!
Honza
> 
> Otherwise looks ok.
> 
> RIchard.
> 
> 
> >  	    }
> > -          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
> > @@ -1015,11 +1043,6 @@ get_alias_set (tree t)
> >  	    }
> >  	}
> >      }
> > -  /* In LTO the rules above needs to be part of canonical type machinery.
> > -     For now just punt.  */
> > -  else if (POINTER_TYPE_P (t)
> > -	   && t != TYPE_CANONICAL (ptr_type_node) && in_lto_p)
> > -    set = get_alias_set (TYPE_CANONICAL (ptr_type_node));
> >  
> >    /* Otherwise make a new alias set for this type.  */
> >    else
> > 
> > 
> 
> -- 
> Richard Biener <rguenther@suse.de>
> SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Re: Enable pointer TBAA for LTO

[Richard Biener]

On Tue, 10 Nov 2015, Jan Hubicka wrote:

> > > Index: tree.c
> > > ===================================================================
> > > --- tree.c	(revision 229968)
> > > +++ tree.c	(working copy)
> > > @@ -13198,6 +13198,7 @@ gimple_canonical_types_compatible_p (con
> > >    /* If the types have been previously registered and found equal
> > >       they still are.  */
> > >    if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t2)
> > > +      && !POINTER_TYPE_P (t1) && !POINTER_TYPE_P (t2)
> > 
> > But TYPE_CANONICAL (t1) should be NULL_TREE for POINTER_TYPE_P?
> 
> The reason is that TYPE_CANONICAL is initialized in get_alias_set that may be
> called before we finish all merging and then it is more fine grained than what
> we need here (i.e. TYPE_CANONICAL of pointers to two differnt types will be
> different, but here we want them to be equal so we can match:
> 
> struct aa { void *ptr;};
> struct bb { int * ptr;};
> 
> Which is actually required for Fortran interoperability.
> 
> Removing this hunk triggers false type incompatibility warning in one of the
> interoperability testcases I added.

Ok, I see.

> Even if I drop the code bellow setting TYPE_CANOINCAL, I think I need to keep
> this conditional: the types may be built in and those get TYPE_CANONICAL set as
> they are constructed by build_pointer_type.  I can gcc_checking_assert for this
> scenario and see.  Perhaps we never build LTO type from builtin type and this
> won't happen. If we did, we would probably have a trouble with false negatives
> in return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2); on non-pointers anyway.

Hmm, indeed.  The various type builders might end up setting 
TYPE_CANONICAL if you ever run into a pre-defined pointer type
(ptr_type_node for example).

> > 
> > >        && trust_type_canonical)
> > >      return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
> > >  
> > > Index: alias.c
> > > ===================================================================
> > > --- alias.c	(revision 229968)
> > > +++ alias.c	(working copy)
> > > @@ -869,13 +874,19 @@ get_alias_set (tree t)
> > >        set = lang_hooks.get_alias_set (t);
> > >        if (set != -1)
> > >  	return set;
> > > -      return 0;
> > > +      /* LTO frontend does not assign canonical types to pointers (which we
> > > +	 ignore anyway) and we compute them.  The following path may be
> > > +	 probably enabled for non-LTO, too, and it may improve TBAA for
> > > +	 pointers to types with structural equality.  */
> > > +      if (!in_lto_p || !POINTER_TYPE_P (t))
> > > +        return 0;
> > 
> > No new LTO paths please, do the suggested change immediately.
> 
> OK, I originally tested the patch without if and there was no problems.
> Just chickened out before preparing final version of the patch.
> > > +	      p = TYPE_MAIN_VARIANT (p);
> > > +	      /* Normally all pointer types are built by
> > > + 		 build_pointer_type_for_mode which ensures they have canonical
> > > +		 type unless they point to type with structural equality.
> > > +		 LTO frontend produce pointer types without TYPE_CANONICAL
> > > +		 that are then added to TYPE_POINTER_TO lists and 
> > > +		 build_pointer_type_for_mode will end up picking one for us.
> > > +		 Declare it the canonical one.  This is the same as
> > > +		 build_pointer_type_for_mode would do. */
> > > +	      if (!TYPE_CANONICAL (p))
> > > +		{
> > > +		  TYPE_CANONICAL (p) = p;
> > > +		  gcc_checking_assert (in_lto_p);
> > > +		}
> > > +	      else
> > > +	        gcc_checking_assert (p == TYPE_CANONICAL (p));
> > 
> > The assert can trigger as
> > build_pointer_type_for_mode builds SET_TYPE_STRUCTURAL_EQUALITY pointer
> > types for SET_TYPE_STRUCTURAL_EQUALITY pointed-to types.  Ah,
> > looking up more context reveals
> > 
> >       if (TREE_CODE (p) == VOID_TYPE || TYPE_STRUCTURAL_EQUALITY_P (p))
> >         set = get_alias_set (ptr_type_node);
> 
> Yep, we don't get here.
> > 
> > Not sure why you adjust TYPE_CANONICAL here at all either.
> 
> You are right, I may probably just drop all the code and just do:
> gcc_checking_assert (!TYPE_CANONICAL || p == TYPE_CANONICAL (p));
> I will test this and re-think the build_pointer_type code to be sure that we
> won't get into a problem there.
> 
> As I recall, the original code
>   p = TYPE_CANONICAL (p);
> was there to permit frontends to glob two pointers by setting same canonical
> type to them.

Yes.

>  My original plan was to use this for LTO frotnend and make
> gimple_compare_canonical_types to do the right thing for pointers and this would
> follow gimple_compare_canonical_types globbing then.
> 
> This idea was wrong: since pointer rules are not transitive (i.e. void
> * alias them all), we can't model that by an equivalence produced by
> gimple_compare_canonical_types.
> 
> Since the assert does not trigger, seems no frontend is doing that and moreover
> I do not see how that would be useful (well, perhaps for some kind of internal
> bookeeping when build TYPE_CANONICAL of more complex types from pointer types,
> like arrays, but for those we ignore TYPE_CANONICAL anyway).  Grepping over
> TYPE_CANONICAL sets in frotneds, I see no code that I would suspect from doing
> something like this.

Ok.  Let's see what your experiment shows, otherwise the original patch
is ok.

Thanks,
Richard.

> Thank you!
> Honza
> > 
> > Otherwise looks ok.
> > 
> > RIchard.
> > 
> > 
> > >  	    }
> > > -          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
> > > @@ -1015,11 +1043,6 @@ get_alias_set (tree t)
> > >  	    }
> > >  	}
> > >      }
> > > -  /* In LTO the rules above needs to be part of canonical type machinery.
> > > -     For now just punt.  */
> > > -  else if (POINTER_TYPE_P (t)
> > > -	   && t != TYPE_CANONICAL (ptr_type_node) && in_lto_p)
> > > -    set = get_alias_set (TYPE_CANONICAL (ptr_type_node));
> > >  
> > >    /* Otherwise make a new alias set for this type.  */
> > >    else
> > > 
> > > 
> > 
> > -- 
> > Richard Biener <rguenther@suse.de>
> > SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Re: Enable pointer TBAA for LTO

[Bernd Schmidt]

On 11/11/2015 10:21 AM, Richard Biener wrote:
> On Tue, 10 Nov 2015, Jan Hubicka wrote:
>> The reason is that TYPE_CANONICAL is initialized in get_alias_set that may be
>> called before we finish all merging and then it is more fine grained than what
>> we need here (i.e. TYPE_CANONICAL of pointers to two differnt types will be
>> different, but here we want them to be equal so we can match:
>>
>> struct aa { void *ptr;};
>> struct bb { int * ptr;};
>>
>> Which is actually required for Fortran interoperability.

Just curious, is this sort of thing documented anywhere?


Bernd

Re: Enable pointer TBAA for LTO

[Jan Hubicka]

> On 11/11/2015 10:21 AM, Richard Biener wrote:
> >On Tue, 10 Nov 2015, Jan Hubicka wrote:
> >>The reason is that TYPE_CANONICAL is initialized in get_alias_set that may be
> >>called before we finish all merging and then it is more fine grained than what
> >>we need here (i.e. TYPE_CANONICAL of pointers to two differnt types will be
> >>different, but here we want them to be equal so we can match:
> >>
> >>struct aa { void *ptr;};
> >>struct bb { int * ptr;};
> >>
> >>Which is actually required for Fortran interoperability.
> 
> Just curious, is this sort of thing documented anywhere?

See http://www.j3-fortran.org/doc/year/10/10-007.pdf, section 15 (interoperability with C).
It defines that C_PTR is compatible with any C non-function pointer.

Honza
> 
> 
> Bernd

Re: Enable pointer TBAA for LTO

[Jan Hubicka]

> > On 11/11/2015 10:21 AM, Richard Biener wrote:
> > >On Tue, 10 Nov 2015, Jan Hubicka wrote:
> > >>The reason is that TYPE_CANONICAL is initialized in get_alias_set that may be
> > >>called before we finish all merging and then it is more fine grained than what
> > >>we need here (i.e. TYPE_CANONICAL of pointers to two differnt types will be
> > >>different, but here we want them to be equal so we can match:
> > >>
> > >>struct aa { void *ptr;};
> > >>struct bb { int * ptr;};
> > >>
> > >>Which is actually required for Fortran interoperability.
> > 
> > Just curious, is this sort of thing documented anywhere?
> 
> See http://www.j3-fortran.org/doc/year/10/10-007.pdf, section 15 (interoperability with C).
> It defines that C_PTR is compatible with any C non-function pointer.

.. and if you ask about GCC side documentation, I added testcases that should
trigger if the Fortran interoperability breaks.  I do not think we want to
document the above compatibility explicitly, because in future we may want to
have more fine grained TBAA for types that are not shared across fortran and C
code (= most types in practice)

Honza
> 
> Honza
> > 
> > 
> > Bernd

Re: Enable pointer TBAA for LTO

[Jan Hubicka]

Hi,
here is updated patch which I finally comitted today.  It addresses all the comments
and also fixes one nasty bug that really cost me a lot of time to understand. 

+	  /* LTO type merging does not make any difference between 
+	     component pointer types.  We may have
+
+	     struct foo {int *a;};
+
+	     as TYPE_CANONICAL of 
+
+	     struct bar {float *a;};
+
+	     Because accesses to int * and float * do not alias, we would get
+	     false negative when accessing the same memory location by
+	     float ** and bar *. We thus record the canonical type as:
+
+	     struct {void *a;};
+
+	     void * is special cased and works as a universal pointer type.
+	     Accesses to it conflicts with accesses to any other pointer
+	     type.  */

This problem manifested itself only as a lto-bootstrap miscompare on 32bit
build and I spent a lot of time localizing the wrong code since it reproduces
only in quite large programs where we get conficts in canonical type merging
like this.

The patch thus updates record_component_aliases to substitute void_ptr_type for
all pointer types. I re-did the stats.  Now the improvement on dealII is 14%
that is quite a bit lower than earlier, but still substantial.  Since we have
voidptr globing counter, I know that the number of disambiguations would go at
least 19% up if we did not do it.

THere is a lot of low hanging fruit in that area now, but the real solution is to
track types that needs to be merge by fortran rules and don't do all this fancy
globing for C/C++ types.  I will open branch for IPA work and try to prepare this
for next stage 1.

bootstrapped/regtested x86_64-linux and ppc64-linux, earlier version tested on i386-linux
and also on some bigger apps, committed

Note that we still have bootstrap miscompare with LTO build and --disable-checking,
I am looking for that now.  Additoinally after fixing the ICEs preventing us to build
the gnat1 binary, gnat1 aborts. Both these are independent of the patch.

Honza
	* lto.c (iterative_hash_canonical_type): Always recurse for pointers.
	(gimple_register_canonical_type_1): Check that pointers do not get
	canonical types.
	(gimple_register_canonical_type): Do not register pointers.

	* tree.c (build_pointer_type_for_mode,build_reference_type_for_mode):
	In LTO we do not compute TYPE_CANONICAL of pointers.
	(gimple_canonical_types_compatible_p): Improve coments; sanity check
	that pointers do not have canonical type that would make us believe
	they are different.
	* alias.c (get_alias_set): Do structural type equality on pointers;
	enable pointer path for LTO; also glob pointer to vector with pointer
	to vector element; glob pointers and references for LTO; do more strict
	sanity checking about build_pointer_type returning the canonical type
	which is also the main variant.
	(record_component_aliases): When component type is pointer and we
	do LTO; record void_type_node alias set.
Index: tree.c
===================================================================
--- tree.c	(revision 230714)
+++ tree.c	(working copy)
@@ -7919,7 +7919,8 @@ build_pointer_type_for_mode (tree to_typ
   TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
   TYPE_POINTER_TO (to_type) = t;
 
-  if (TYPE_STRUCTURAL_EQUALITY_P (to_type))
+  /* During LTO we do not set TYPE_CANONICAL of pointers and references.  */
+  if (TYPE_STRUCTURAL_EQUALITY_P (to_type) || in_lto_p)
     SET_TYPE_STRUCTURAL_EQUALITY (t);
   else if (TYPE_CANONICAL (to_type) != to_type || could_alias)
     TYPE_CANONICAL (t)
@@ -7987,7 +7988,8 @@ build_reference_type_for_mode (tree to_t
   TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
   TYPE_REFERENCE_TO (to_type) = t;
 
-  if (TYPE_STRUCTURAL_EQUALITY_P (to_type))
+  /* During LTO we do not set TYPE_CANONICAL of pointers and references.  */
+  if (TYPE_STRUCTURAL_EQUALITY_P (to_type) || in_lto_p)
     SET_TYPE_STRUCTURAL_EQUALITY (t);
   else if (TYPE_CANONICAL (to_type) != to_type || could_alias)
     TYPE_CANONICAL (t)
@@ -13224,7 +13226,9 @@ type_with_interoperable_signedness (cons
    TBAA is concerned.  
    This function is used both by lto.c canonical type merging and by the
    verifier.  If TRUST_TYPE_CANONICAL we do not look into structure of types
-   that have TYPE_CANONICAL defined and assume them equivalent.  */
+   that have TYPE_CANONICAL defined and assume them equivalent.  This is useful
+   only for LTO because only in these cases TYPE_CANONICAL equivalence
+   correspond to one defined by gimple_canonical_types_compatible_p.  */
 
 bool
 gimple_canonical_types_compatible_p (const_tree t1, const_tree t2,
@@ -13265,9 +13269,19 @@ gimple_canonical_types_compatible_p (con
 	      || (type_with_alias_set_p (t1) && type_with_alias_set_p (t2)));
   /* If the types have been previously registered and found equal
      they still are.  */
+
   if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t2)
       && trust_type_canonical)
-    return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
+    {
+      /* Do not use TYPE_CANONICAL of pointer types.  For LTO streamed types
+	 they are always NULL, but they are set to non-NULL for types
+	 constructed by build_pointer_type and variants.  In this case the
+	 TYPE_CANONICAL is more fine grained than the equivalnce we test (where
+	 all pointers are considered equal.  Be sure to not return false
+	 negatives.  */
+      gcc_checking_assert (!POINTER_TYPE_P (t1) && !POINTER_TYPE_P (t2));
+      return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
+    }
 
   /* Can't be the same type if the types don't have the same code.  */
   enum tree_code code = tree_code_for_canonical_type_merging (TREE_CODE (t1));
Index: lto/lto.c
===================================================================
--- lto/lto.c	(revision 230714)
+++ lto/lto.c	(working copy)
@@ -388,8 +388,13 @@ iterative_hash_canonical_type (tree type
 
   /* All type variants have same TYPE_CANONICAL.  */
   type = TYPE_MAIN_VARIANT (type);
+
+  /* We do not compute TYPE_CANONICAl of POINTER_TYPE because the aliasing
+     code never use it anyway.  */
+  if (POINTER_TYPE_P (type))
+    v = hash_canonical_type (type);
   /* An already processed type.  */
-  if (TYPE_CANONICAL (type))
+  else if (TYPE_CANONICAL (type))
     {
       type = TYPE_CANONICAL (type);
       v = gimple_canonical_type_hash (type);
@@ -437,7 +442,9 @@ gimple_register_canonical_type_1 (tree t
 {
   void **slot;
 
-  gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t));
+  gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t)
+		       && type_with_alias_set_p (t)
+		       && !POINTER_TYPE_P (t));
 
   slot = htab_find_slot_with_hash (gimple_canonical_types, t, hash, INSERT);
   if (*slot)
@@ -470,7 +477,7 @@ gimple_register_canonical_type_1 (tree t
 static void
 gimple_register_canonical_type (tree t)
 {
-  if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t))
+  if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t) || POINTER_TYPE_P (t))
     return;
 
   /* Canonical types are same among all complete variants.  */
Index: alias.c
===================================================================
--- alias.c	(revision 230714)
+++ alias.c	(working copy)
@@ -869,13 +869,23 @@ get_alias_set (tree t)
       set = lang_hooks.get_alias_set (t);
       if (set != -1)
 	return set;
-      return 0;
+      /* Handle structure type equality for pointer types.  This is easy
+	 to do, because the code bellow ignore canonical types on these anyway.
+	 This is important for LTO, where TYPE_CANONICAL for pointers can not
+	 be meaningfuly computed by the frotnend.  */
+      if (!POINTER_TYPE_P (t))
+	{
+	  /* In LTO we set canonical types for all types where it makes
+	     sense to do so.  Double check we did not miss some type.  */
+	  gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t));
+          return 0;
+	}
+    }
+  else
+    {
+      t = TYPE_CANONICAL (t);
+      gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
     }
-
-  t = TYPE_CANONICAL (t);
-
-  /* The canonical type should not require structural equality checks.  */
-  gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
 
   /* If this is a type with a known alias set, return it.  */
   if (TYPE_ALIAS_SET_KNOWN_P (t))
@@ -952,20 +962,23 @@ get_alias_set (tree t)
      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)
+  else if (POINTER_TYPE_P (t) && t != ptr_type_node)
     {
       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.  */
+	 We also want to make pointer to array/vector equivalent to pointer to
+	 its element (see the reasoning above). Skip all those types, too.  */
       for (p = t; POINTER_TYPE_P (p)
-	   || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p));
+	   || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p))
+	   || TREE_CODE (p) == VECTOR_TYPE;
 	   p = TREE_TYPE (p))
 	{
 	  if (TREE_CODE (p) == REFERENCE_TYPE)
-	    reference.safe_push (true);
+	    /* In LTO we want languages that use references to be compatible
+ 	       with languages that use pointers.  */
+	    reference.safe_push (true && !in_lto_p);
 	  if (TREE_CODE (p) == POINTER_TYPE)
 	    reference.safe_push (false);
 	}
@@ -981,7 +994,7 @@ get_alias_set (tree t)
 	set = get_alias_set (ptr_type_node);
       else
 	{
-	  /* Rebuild pointer type from starting from canonical types using
+	  /* Rebuild pointer type 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.
@@ -998,9 +1011,15 @@ get_alias_set (tree t)
 		p = build_reference_type (p);
 	      else
 		p = build_pointer_type (p);
-	      p = TYPE_CANONICAL (TYPE_MAIN_VARIANT (p));
+	      gcc_checking_assert (p == TYPE_MAIN_VARIANT (p));
+	      /* build_pointer_type should always return the canonical type.
+		 For LTO TYPE_CANOINCAL may be NULL, because we do not compute
+		 them.  Be sure that frontends do not glob canonical types of
+		 pointers in unexpected way and that p == TYPE_CANONICAL (p)
+		 in all other cases.  */
+	      gcc_checking_assert (!TYPE_CANONICAL (p)
+				   || p == TYPE_CANONICAL (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
@@ -1015,11 +1034,12 @@ get_alias_set (tree t)
 	    }
 	}
     }
-  /* In LTO the rules above needs to be part of canonical type machinery.
-     For now just punt.  */
-  else if (POINTER_TYPE_P (t)
-	   && t != TYPE_CANONICAL (ptr_type_node) && in_lto_p)
-    set = get_alias_set (TYPE_CANONICAL (ptr_type_node));
+  /* Alias set of ptr_type_node is special and serve as universal pointer which
+     is TBAA compatible with every other pointer type.  Be sure we have the
+     alias set built even for LTO which otherwise keeps all TYPE_CANONICAL
+     of pointer types NULL.  */
+  else if (t == ptr_type_node)
+    set = new_alias_set ();
 
   /* Otherwise make a new alias set for this type.  */
   else
@@ -1155,7 +1175,42 @@ record_component_aliases (tree type)
     case QUAL_UNION_TYPE:
       for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field))
 	if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field))
-	  record_alias_subset (superset, get_alias_set (TREE_TYPE (field)));
+	  {
+	    /* LTO type merging does not make any difference between 
+	       component pointer types.  We may have
+
+	       struct foo {int *a;};
+
+	       as TYPE_CANONICAL of 
+
+	       struct bar {float *a;};
+
+	       Because accesses to int * and float * do not alias, we would get
+	       false negative when accessing the same memory location by
+	       float ** and bar *. We thus record the canonical type as:
+
+	       struct {void *a;};
+
+	       void * is special cased and works as a universal pointer type.
+	       Accesses to it conflicts with accesses to any other pointer
+	       type.  */
+	    tree t = TREE_TYPE (field);
+	    if (in_lto_p)
+	      {
+		/* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
+		   element type and that type has to be normalized to void *,
+		   too, in the case it is a pointer. */
+		while ((TREE_CODE (t) == ARRAY_TYPE
+			&& (!COMPLETE_TYPE_P (t)
+			    || TYPE_NONALIASED_COMPONENT (t)))
+		       || TREE_CODE (t) == VECTOR_TYPE)
+		  t = TREE_TYPE (t);
+		if (POINTER_TYPE_P (t))
+		  t = ptr_type_node;
+	      }
+	   
+	    record_alias_subset (superset, get_alias_set (t));
+	  }
       break;
 
     case COMPLEX_TYPE:

Re: Enable pointer TBAA for LTO

[Eric Botcazou]

> +	    tree t = TREE_TYPE (field);
> +	    if (in_lto_p)
> +	      {
> +		/* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
> +		   element type and that type has to be normalized to void *,
> +		   too, in the case it is a pointer. */
> +		while ((TREE_CODE (t) == ARRAY_TYPE
> +			&& (!COMPLETE_TYPE_P (t)
> +			    || TYPE_NONALIASED_COMPONENT (t)))
> +		       || TREE_CODE (t) == VECTOR_TYPE)
> +		  t = TREE_TYPE (t);
> +		if (POINTER_TYPE_P (t))
> +		  t = ptr_type_node;
> +	      }
> +
> +	    record_alias_subset (superset, get_alias_set (t));
> +	  }
>        break;

Are you sure that it's not !TYPE_NONALIASED_COMPONENT (t) here?

-- 
Eric Botcazou

Re: Enable pointer TBAA for LTO

[Jan Hubicka]

> > +	    tree t = TREE_TYPE (field);
> > +	    if (in_lto_p)
> > +	      {
> > +		/* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
> > +		   element type and that type has to be normalized to void *,
> > +		   too, in the case it is a pointer. */
> > +		while ((TREE_CODE (t) == ARRAY_TYPE
> > +			&& (!COMPLETE_TYPE_P (t)
> > +			    || TYPE_NONALIASED_COMPONENT (t)))
> > +		       || TREE_CODE (t) == VECTOR_TYPE)
> > +		  t = TREE_TYPE (t);
> > +		if (POINTER_TYPE_P (t))
> > +		  t = ptr_type_node;
> > +	      }
> > +
> > +	    record_alias_subset (superset, get_alias_set (t));
> > +	  }
> >        break;
> 
> Are you sure that it's not !TYPE_NONALIASED_COMPONENT (t) here?

You are right, TYPE_NONALIASED_COMPONENT is the wrong way.  I will fix it and try to come up
with a testcase (TYPE_NONALIASED_COMPONENT is quite rarely used beast)

Honza
> 
> -- 
> Eric Botcazou

Re: Enable pointer TBAA for LTO

[Eric Botcazou]

> You are right, TYPE_NONALIASED_COMPONENT is the wrong way.  I will fix it
> and try to come up with a testcase (TYPE_NONALIASED_COMPONENT is quite
> rarely used beast)

It's only used in Ada as far as I know, but is quite sensitive and quickly 
leads to wrong code if not handled properly in my experience, so this could 
well be responsible for the gnat1 miscompilation.

-- 
Eric Botcazou

Re: Enable pointer TBAA for LTO

[Richard Biener]

On Mon, 23 Nov 2015, Jan Hubicka wrote:

> Hi,
> here is updated patch which I finally comitted today.  It addresses all the comments
> and also fixes one nasty bug that really cost me a lot of time to understand. 
> 
> +	  /* LTO type merging does not make any difference between 
> +	     component pointer types.  We may have
> +
> +	     struct foo {int *a;};
> +
> +	     as TYPE_CANONICAL of 
> +
> +	     struct bar {float *a;};
> +
> +	     Because accesses to int * and float * do not alias, we would get
> +	     false negative when accessing the same memory location by
> +	     float ** and bar *. We thus record the canonical type as:
> +
> +	     struct {void *a;};
> +
> +	     void * is special cased and works as a universal pointer type.
> +	     Accesses to it conflicts with accesses to any other pointer
> +	     type.  */
> 
> This problem manifested itself only as a lto-bootstrap miscompare on 32bit
> build and I spent a lot of time localizing the wrong code since it reproduces
> only in quite large programs where we get conficts in canonical type merging
> like this.
> 
> The patch thus updates record_component_aliases to substitute 
> void_ptr_type for all pointer types. I re-did the stats.  Now the 
> improvement on dealII is 14% that is quite a bit lower than earlier, but 
> still substantial.  Since we have voidptr globing counter, I know that 
> the number of disambiguations would go at least 19% up if we did not do 
> it.

Please in future leave patches for review again if you do such
big changes before committing...

I don't understand why we need this (testcase?) because get_alias_set ()
is supposed to do the alias-set of pointer globbing for us.

Thanks,
Richard.

> THere is a lot of low hanging fruit in that area now, but the real 
> solution is to track types that needs to be merge by fortran rules and 
> don't do all this fancy globing for C/C++ types.  I will open branch for 
> IPA work and try to prepare this for next stage 1.
> 
> bootstrapped/regtested x86_64-linux and ppc64-linux, earlier version tested on i386-linux
> and also on some bigger apps, committed
> 
> Note that we still have bootstrap miscompare with LTO build and --disable-checking,
> I am looking for that now.  Additoinally after fixing the ICEs preventing us to build
> the gnat1 binary, gnat1 aborts. Both these are independent of the patch.
> 
> Honza
> 	* lto.c (iterative_hash_canonical_type): Always recurse for pointers.
> 	(gimple_register_canonical_type_1): Check that pointers do not get
> 	canonical types.
> 	(gimple_register_canonical_type): Do not register pointers.
> 
> 	* tree.c (build_pointer_type_for_mode,build_reference_type_for_mode):
> 	In LTO we do not compute TYPE_CANONICAL of pointers.
> 	(gimple_canonical_types_compatible_p): Improve coments; sanity check
> 	that pointers do not have canonical type that would make us believe
> 	they are different.
> 	* alias.c (get_alias_set): Do structural type equality on pointers;
> 	enable pointer path for LTO; also glob pointer to vector with pointer
> 	to vector element; glob pointers and references for LTO; do more strict
> 	sanity checking about build_pointer_type returning the canonical type
> 	which is also the main variant.
> 	(record_component_aliases): When component type is pointer and we
> 	do LTO; record void_type_node alias set.
> Index: tree.c
> ===================================================================
> --- tree.c	(revision 230714)
> +++ tree.c	(working copy)
> @@ -7919,7 +7919,8 @@ build_pointer_type_for_mode (tree to_typ
>    TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
>    TYPE_POINTER_TO (to_type) = t;
>  
> -  if (TYPE_STRUCTURAL_EQUALITY_P (to_type))
> +  /* During LTO we do not set TYPE_CANONICAL of pointers and references.  */
> +  if (TYPE_STRUCTURAL_EQUALITY_P (to_type) || in_lto_p)
>      SET_TYPE_STRUCTURAL_EQUALITY (t);
>    else if (TYPE_CANONICAL (to_type) != to_type || could_alias)
>      TYPE_CANONICAL (t)
> @@ -7987,7 +7988,8 @@ build_reference_type_for_mode (tree to_t
>    TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
>    TYPE_REFERENCE_TO (to_type) = t;
>  
> -  if (TYPE_STRUCTURAL_EQUALITY_P (to_type))
> +  /* During LTO we do not set TYPE_CANONICAL of pointers and references.  */
> +  if (TYPE_STRUCTURAL_EQUALITY_P (to_type) || in_lto_p)
>      SET_TYPE_STRUCTURAL_EQUALITY (t);
>    else if (TYPE_CANONICAL (to_type) != to_type || could_alias)
>      TYPE_CANONICAL (t)
> @@ -13224,7 +13226,9 @@ type_with_interoperable_signedness (cons
>     TBAA is concerned.  
>     This function is used both by lto.c canonical type merging and by the
>     verifier.  If TRUST_TYPE_CANONICAL we do not look into structure of types
> -   that have TYPE_CANONICAL defined and assume them equivalent.  */
> +   that have TYPE_CANONICAL defined and assume them equivalent.  This is useful
> +   only for LTO because only in these cases TYPE_CANONICAL equivalence
> +   correspond to one defined by gimple_canonical_types_compatible_p.  */
>  
>  bool
>  gimple_canonical_types_compatible_p (const_tree t1, const_tree t2,
> @@ -13265,9 +13269,19 @@ gimple_canonical_types_compatible_p (con
>  	      || (type_with_alias_set_p (t1) && type_with_alias_set_p (t2)));
>    /* If the types have been previously registered and found equal
>       they still are.  */
> +
>    if (TYPE_CANONICAL (t1) && TYPE_CANONICAL (t2)
>        && trust_type_canonical)
> -    return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
> +    {
> +      /* Do not use TYPE_CANONICAL of pointer types.  For LTO streamed types
> +	 they are always NULL, but they are set to non-NULL for types
> +	 constructed by build_pointer_type and variants.  In this case the
> +	 TYPE_CANONICAL is more fine grained than the equivalnce we test (where
> +	 all pointers are considered equal.  Be sure to not return false
> +	 negatives.  */
> +      gcc_checking_assert (!POINTER_TYPE_P (t1) && !POINTER_TYPE_P (t2));
> +      return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
> +    }
>  
>    /* Can't be the same type if the types don't have the same code.  */
>    enum tree_code code = tree_code_for_canonical_type_merging (TREE_CODE (t1));
> Index: lto/lto.c
> ===================================================================
> --- lto/lto.c	(revision 230714)
> +++ lto/lto.c	(working copy)
> @@ -388,8 +388,13 @@ iterative_hash_canonical_type (tree type
>  
>    /* All type variants have same TYPE_CANONICAL.  */
>    type = TYPE_MAIN_VARIANT (type);
> +
> +  /* We do not compute TYPE_CANONICAl of POINTER_TYPE because the aliasing
> +     code never use it anyway.  */
> +  if (POINTER_TYPE_P (type))
> +    v = hash_canonical_type (type);
>    /* An already processed type.  */
> -  if (TYPE_CANONICAL (type))
> +  else if (TYPE_CANONICAL (type))
>      {
>        type = TYPE_CANONICAL (type);
>        v = gimple_canonical_type_hash (type);
> @@ -437,7 +442,9 @@ gimple_register_canonical_type_1 (tree t
>  {
>    void **slot;
>  
> -  gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t));
> +  gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t)
> +		       && type_with_alias_set_p (t)
> +		       && !POINTER_TYPE_P (t));
>  
>    slot = htab_find_slot_with_hash (gimple_canonical_types, t, hash, INSERT);
>    if (*slot)
> @@ -470,7 +477,7 @@ gimple_register_canonical_type_1 (tree t
>  static void
>  gimple_register_canonical_type (tree t)
>  {
> -  if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t))
> +  if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t) || POINTER_TYPE_P (t))
>      return;
>  
>    /* Canonical types are same among all complete variants.  */
> Index: alias.c
> ===================================================================
> --- alias.c	(revision 230714)
> +++ alias.c	(working copy)
> @@ -869,13 +869,23 @@ get_alias_set (tree t)
>        set = lang_hooks.get_alias_set (t);
>        if (set != -1)
>  	return set;
> -      return 0;
> +      /* Handle structure type equality for pointer types.  This is easy
> +	 to do, because the code bellow ignore canonical types on these anyway.
> +	 This is important for LTO, where TYPE_CANONICAL for pointers can not
> +	 be meaningfuly computed by the frotnend.  */
> +      if (!POINTER_TYPE_P (t))
> +	{
> +	  /* In LTO we set canonical types for all types where it makes
> +	     sense to do so.  Double check we did not miss some type.  */
> +	  gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t));
> +          return 0;
> +	}
> +    }
> +  else
> +    {
> +      t = TYPE_CANONICAL (t);
> +      gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
>      }
> -
> -  t = TYPE_CANONICAL (t);
> -
> -  /* The canonical type should not require structural equality checks.  */
> -  gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
>  
>    /* If this is a type with a known alias set, return it.  */
>    if (TYPE_ALIAS_SET_KNOWN_P (t))
> @@ -952,20 +962,23 @@ get_alias_set (tree t)
>       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)
> +  else if (POINTER_TYPE_P (t) && t != ptr_type_node)
>      {
>        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.  */
> +	 We also want to make pointer to array/vector equivalent to pointer to
> +	 its element (see the reasoning above). Skip all those types, too.  */
>        for (p = t; POINTER_TYPE_P (p)
> -	   || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p));
> +	   || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p))
> +	   || TREE_CODE (p) == VECTOR_TYPE;
>  	   p = TREE_TYPE (p))
>  	{
>  	  if (TREE_CODE (p) == REFERENCE_TYPE)
> -	    reference.safe_push (true);
> +	    /* In LTO we want languages that use references to be compatible
> + 	       with languages that use pointers.  */
> +	    reference.safe_push (true && !in_lto_p);
>  	  if (TREE_CODE (p) == POINTER_TYPE)
>  	    reference.safe_push (false);
>  	}
> @@ -981,7 +994,7 @@ get_alias_set (tree t)
>  	set = get_alias_set (ptr_type_node);
>        else
>  	{
> -	  /* Rebuild pointer type from starting from canonical types using
> +	  /* Rebuild pointer type 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.
> @@ -998,9 +1011,15 @@ get_alias_set (tree t)
>  		p = build_reference_type (p);
>  	      else
>  		p = build_pointer_type (p);
> -	      p = TYPE_CANONICAL (TYPE_MAIN_VARIANT (p));
> +	      gcc_checking_assert (p == TYPE_MAIN_VARIANT (p));
> +	      /* build_pointer_type should always return the canonical type.
> +		 For LTO TYPE_CANOINCAL may be NULL, because we do not compute
> +		 them.  Be sure that frontends do not glob canonical types of
> +		 pointers in unexpected way and that p == TYPE_CANONICAL (p)
> +		 in all other cases.  */
> +	      gcc_checking_assert (!TYPE_CANONICAL (p)
> +				   || p == TYPE_CANONICAL (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
> @@ -1015,11 +1034,12 @@ get_alias_set (tree t)
>  	    }
>  	}
>      }
> -  /* In LTO the rules above needs to be part of canonical type machinery.
> -     For now just punt.  */
> -  else if (POINTER_TYPE_P (t)
> -	   && t != TYPE_CANONICAL (ptr_type_node) && in_lto_p)
> -    set = get_alias_set (TYPE_CANONICAL (ptr_type_node));
> +  /* Alias set of ptr_type_node is special and serve as universal pointer which
> +     is TBAA compatible with every other pointer type.  Be sure we have the
> +     alias set built even for LTO which otherwise keeps all TYPE_CANONICAL
> +     of pointer types NULL.  */
> +  else if (t == ptr_type_node)
> +    set = new_alias_set ();
>  
>    /* Otherwise make a new alias set for this type.  */
>    else
> @@ -1155,7 +1175,42 @@ record_component_aliases (tree type)
>      case QUAL_UNION_TYPE:
>        for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field))
>  	if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field))
> -	  record_alias_subset (superset, get_alias_set (TREE_TYPE (field)));
> +	  {
> +	    /* LTO type merging does not make any difference between 
> +	       component pointer types.  We may have
> +
> +	       struct foo {int *a;};
> +
> +	       as TYPE_CANONICAL of 
> +
> +	       struct bar {float *a;};
> +
> +	       Because accesses to int * and float * do not alias, we would get
> +	       false negative when accessing the same memory location by
> +	       float ** and bar *. We thus record the canonical type as:
> +
> +	       struct {void *a;};
> +
> +	       void * is special cased and works as a universal pointer type.
> +	       Accesses to it conflicts with accesses to any other pointer
> +	       type.  */
> +	    tree t = TREE_TYPE (field);
> +	    if (in_lto_p)
> +	      {
> +		/* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
> +		   element type and that type has to be normalized to void *,
> +		   too, in the case it is a pointer. */
> +		while ((TREE_CODE (t) == ARRAY_TYPE
> +			&& (!COMPLETE_TYPE_P (t)
> +			    || TYPE_NONALIASED_COMPONENT (t)))
> +		       || TREE_CODE (t) == VECTOR_TYPE)
> +		  t = TREE_TYPE (t);
> +		if (POINTER_TYPE_P (t))
> +		  t = ptr_type_node;
> +	      }
> +	   
> +	    record_alias_subset (superset, get_alias_set (t));
> +	  }
>        break;
>  
>      case COMPLEX_TYPE:
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Re: Enable pointer TBAA for LTO

[Martin Jambor]

Hi,

On Mon, Nov 23, 2015 at 12:00:25AM +0100, Jan Hubicka wrote:
> Hi,
> here is updated patch which I finally comitted today.  It addresses all the comments
> and also fixes one nasty bug that really cost me a lot of time to understand. 
> 
> +	  /* LTO type merging does not make any difference between 
> +	     component pointer types.  We may have
> +
> +	     struct foo {int *a;};
> +
> +	     as TYPE_CANONICAL of 
> +
> +	     struct bar {float *a;};
> +
> +	     Because accesses to int * and float * do not alias, we would get
> +	     false negative when accessing the same memory location by
> +	     float ** and bar *. We thus record the canonical type as:
> +
> +	     struct {void *a;};
> +
> +	     void * is special cased and works as a universal pointer type.
> +	     Accesses to it conflicts with accesses to any other pointer
> +	     type.  */
> 
> This problem manifested itself only as a lto-bootstrap miscompare on 32bit
> build and I spent a lot of time localizing the wrong code since it reproduces
> only in quite large programs where we get conficts in canonical type merging
> like this.
> 
> The patch thus updates record_component_aliases to substitute void_ptr_type for
> all pointer types. I re-did the stats.  Now the improvement on dealII is 14%
> that is quite a bit lower than earlier, but still substantial.  Since we have
> voidptr globing counter, I know that the number of disambiguations would go at
> least 19% up if we did not do it.
> 
> THere is a lot of low hanging fruit in that area now, but the real solution is to
> track types that needs to be merge by fortran rules and don't do all this fancy
> globing for C/C++ types.  I will open branch for IPA work and try to prepare this
> for next stage 1.
> 
> bootstrapped/regtested x86_64-linux and ppc64-linux, earlier version tested on i386-linux
> and also on some bigger apps, committed
> 
> Note that we still have bootstrap miscompare with LTO build and --disable-checking,
> I am looking for that now.  Additoinally after fixing the ICEs preventing us to build
> the gnat1 binary, gnat1 aborts. Both these are independent of the patch.
> 
> Honza
> 	* lto.c (iterative_hash_canonical_type): Always recurse for pointers.
> 	(gimple_register_canonical_type_1): Check that pointers do not get
> 	canonical types.
> 	(gimple_register_canonical_type): Do not register pointers.
> 
> 	* tree.c (build_pointer_type_for_mode,build_reference_type_for_mode):
> 	In LTO we do not compute TYPE_CANONICAL of pointers.
> 	(gimple_canonical_types_compatible_p): Improve coments; sanity check
> 	that pointers do not have canonical type that would make us believe
> 	they are different.
> 	* alias.c (get_alias_set): Do structural type equality on pointers;
> 	enable pointer path for LTO; also glob pointer to vector with pointer
> 	to vector element; glob pointers and references for LTO; do more strict
> 	sanity checking about build_pointer_type returning the canonical type
> 	which is also the main variant.
> 	(record_component_aliases): When component type is pointer and we
> 	do LTO; record void_type_node alias set.

...

> Index: alias.c
> ===================================================================
> --- alias.c	(revision 230714)
> +++ alias.c	(working copy)
> @@ -869,13 +869,23 @@ get_alias_set (tree t)
>        set = lang_hooks.get_alias_set (t);
>        if (set != -1)
>  	return set;
> -      return 0;
> +      /* Handle structure type equality for pointer types.  This is easy
> +	 to do, because the code bellow ignore canonical types on these anyway.
> +	 This is important for LTO, where TYPE_CANONICAL for pointers can not
> +	 be meaningfuly computed by the frotnend.  */
> +      if (!POINTER_TYPE_P (t))
> +	{
> +	  /* In LTO we set canonical types for all types where it makes
> +	     sense to do so.  Double check we did not miss some type.  */
> +	  gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t));
> +          return 0;

I have hit this assert on our LTO tests when doing a merge from trunk
to the HSA branch.  On the branch, we generate very simple static
constructors/destructors which just call libgomp (un)registration
routines to which we pass data in static variables of artificial
types.  The assert happens inside varpool_node::finalize_decl calls on
those variables, e.g.:

lto1: internal compiler error: in get_alias_set, at alias.c:880
0x613650 get_alias_set(tree_node*)
        /home/mjambor/gcc/branch/src/gcc/alias.c:880
0x71d2c7 set_mem_attributes_minus_bitpos(rtx_def*, tree_node*, int, long)
        /home/mjambor/gcc/branch/src/gcc/emit-rtl.c:1772
0xd2d2f0 make_decl_rtl(tree_node*)
        /home/mjambor/gcc/branch/src/gcc/varasm.c:1473
0xd310c7 assemble_variable(tree_node*, int, int, int)
        /home/mjambor/gcc/branch/src/gcc/varasm.c:2144
0xd37b32 varpool_node::assemble_decl()
        /home/mjambor/gcc/branch/src/gcc/varpool.c:580
0x6896aa varpool_node::finalize_decl(tree_node*)
        /home/mjambor/gcc/branch/src/gcc/cgraphunit.c:820
0x844da1 hsa_output_kernels
        /home/mjambor/gcc/branch/src/gcc/hsa-brig.c:1954
0x849f04 hsa_output_libgomp_mapping
        /home/mjambor/gcc/branch/src/gcc/hsa-brig.c:2116
0x849f04 hsa_output_brig()
        /home/mjambor/gcc/branch/src/gcc/hsa-brig.c:2356
(hsa_output_brig is called from compile_file in toplev.c)

I am going to commit the following hunk to the branch so that I can
get on with the merge.  If you think it is wrong in any way, please
let me know so that we can find a proper solution.

Thanks,

Martin


--- /home/mjambor/gcc/trunk/src/gcc/alias.c     2015-11-23 11:45:27.850846512 +0100
+++ gcc/alias.c 2015-11-23 14:37:32.098133073 +0100
@@ -877,7 +877,9 @@ get_alias_set (tree t)
        {
          /* In LTO we set canonical types for all types where it makes
             sense to do so.  Double check we did not miss some type.  */
-         gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t));
+         gcc_checking_assert (!in_lto_p
+                              || !type_with_alias_set_p (t)
+                              || TYPE_ARTIFICIAL (t));
           return 0;
        }
     }


> +	}
> +    }
> +  else
> +    {
> +      t = TYPE_CANONICAL (t);
> +      gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
>      }
> -
> -  t = TYPE_CANONICAL (t);
> -
> -  /* The canonical type should not require structural equality checks.  */
> -  gcc_checking_assert (!TYPE_STRUCTURAL_EQUALITY_P (t));
>  
>    /* If this is a type with a known alias set, return it.  */
>    if (TYPE_ALIAS_SET_KNOWN_P (t))

...

Re: Enable pointer TBAA for LTO

[Richard Biener]

On Mon, 23 Nov 2015, Martin Jambor wrote:

> Hi,
> 
> On Mon, Nov 23, 2015 at 12:00:25AM +0100, Jan Hubicka wrote:
> > Hi,
> > here is updated patch which I finally comitted today.  It addresses all the comments
> > and also fixes one nasty bug that really cost me a lot of time to understand. 
> > 
> > +	  /* LTO type merging does not make any difference between 
> > +	     component pointer types.  We may have
> > +
> > +	     struct foo {int *a;};
> > +
> > +	     as TYPE_CANONICAL of 
> > +
> > +	     struct bar {float *a;};
> > +
> > +	     Because accesses to int * and float * do not alias, we would get
> > +	     false negative when accessing the same memory location by
> > +	     float ** and bar *. We thus record the canonical type as:
> > +
> > +	     struct {void *a;};
> > +
> > +	     void * is special cased and works as a universal pointer type.
> > +	     Accesses to it conflicts with accesses to any other pointer
> > +	     type.  */
> > 
> > This problem manifested itself only as a lto-bootstrap miscompare on 32bit
> > build and I spent a lot of time localizing the wrong code since it reproduces
> > only in quite large programs where we get conficts in canonical type merging
> > like this.
> > 
> > The patch thus updates record_component_aliases to substitute void_ptr_type for
> > all pointer types. I re-did the stats.  Now the improvement on dealII is 14%
> > that is quite a bit lower than earlier, but still substantial.  Since we have
> > voidptr globing counter, I know that the number of disambiguations would go at
> > least 19% up if we did not do it.
> > 
> > THere is a lot of low hanging fruit in that area now, but the real solution is to
> > track types that needs to be merge by fortran rules and don't do all this fancy
> > globing for C/C++ types.  I will open branch for IPA work and try to prepare this
> > for next stage 1.
> > 
> > bootstrapped/regtested x86_64-linux and ppc64-linux, earlier version tested on i386-linux
> > and also on some bigger apps, committed
> > 
> > Note that we still have bootstrap miscompare with LTO build and --disable-checking,
> > I am looking for that now.  Additoinally after fixing the ICEs preventing us to build
> > the gnat1 binary, gnat1 aborts. Both these are independent of the patch.
> > 
> > Honza
> > 	* lto.c (iterative_hash_canonical_type): Always recurse for pointers.
> > 	(gimple_register_canonical_type_1): Check that pointers do not get
> > 	canonical types.
> > 	(gimple_register_canonical_type): Do not register pointers.
> > 
> > 	* tree.c (build_pointer_type_for_mode,build_reference_type_for_mode):
> > 	In LTO we do not compute TYPE_CANONICAL of pointers.
> > 	(gimple_canonical_types_compatible_p): Improve coments; sanity check
> > 	that pointers do not have canonical type that would make us believe
> > 	they are different.
> > 	* alias.c (get_alias_set): Do structural type equality on pointers;
> > 	enable pointer path for LTO; also glob pointer to vector with pointer
> > 	to vector element; glob pointers and references for LTO; do more strict
> > 	sanity checking about build_pointer_type returning the canonical type
> > 	which is also the main variant.
> > 	(record_component_aliases): When component type is pointer and we
> > 	do LTO; record void_type_node alias set.
> 
> ...
> 
> > Index: alias.c
> > ===================================================================
> > --- alias.c	(revision 230714)
> > +++ alias.c	(working copy)
> > @@ -869,13 +869,23 @@ get_alias_set (tree t)
> >        set = lang_hooks.get_alias_set (t);
> >        if (set != -1)
> >  	return set;
> > -      return 0;
> > +      /* Handle structure type equality for pointer types.  This is easy
> > +	 to do, because the code bellow ignore canonical types on these anyway.
> > +	 This is important for LTO, where TYPE_CANONICAL for pointers can not
> > +	 be meaningfuly computed by the frotnend.  */
> > +      if (!POINTER_TYPE_P (t))
> > +	{
> > +	  /* In LTO we set canonical types for all types where it makes
> > +	     sense to do so.  Double check we did not miss some type.  */
> > +	  gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t));
> > +          return 0;
> 
> I have hit this assert on our LTO tests when doing a merge from trunk
> to the HSA branch.  On the branch, we generate very simple static
> constructors/destructors which just call libgomp (un)registration
> routines to which we pass data in static variables of artificial
> types.  The assert happens inside varpool_node::finalize_decl calls on
> those variables, e.g.:
> 
> lto1: internal compiler error: in get_alias_set, at alias.c:880
> 0x613650 get_alias_set(tree_node*)
>         /home/mjambor/gcc/branch/src/gcc/alias.c:880
> 0x71d2c7 set_mem_attributes_minus_bitpos(rtx_def*, tree_node*, int, long)
>         /home/mjambor/gcc/branch/src/gcc/emit-rtl.c:1772
> 0xd2d2f0 make_decl_rtl(tree_node*)
>         /home/mjambor/gcc/branch/src/gcc/varasm.c:1473
> 0xd310c7 assemble_variable(tree_node*, int, int, int)
>         /home/mjambor/gcc/branch/src/gcc/varasm.c:2144
> 0xd37b32 varpool_node::assemble_decl()
>         /home/mjambor/gcc/branch/src/gcc/varpool.c:580
> 0x6896aa varpool_node::finalize_decl(tree_node*)
>         /home/mjambor/gcc/branch/src/gcc/cgraphunit.c:820
> 0x844da1 hsa_output_kernels
>         /home/mjambor/gcc/branch/src/gcc/hsa-brig.c:1954
> 0x849f04 hsa_output_libgomp_mapping
>         /home/mjambor/gcc/branch/src/gcc/hsa-brig.c:2116
> 0x849f04 hsa_output_brig()
>         /home/mjambor/gcc/branch/src/gcc/hsa-brig.c:2356
> (hsa_output_brig is called from compile_file in toplev.c)

I think it also causes the following and one related ICE

FAIL: gcc.dg/vect/pr62021.c -flto -ffat-lto-objects (internal compiler 
error)

/space/rguenther/src/svn/trunk3/gcc/testsuite/gcc.dg/vect/pr62021.c:7:1: 
internal compiler error: in get_alias_set, at alias.c:880^M
0x7528a7 get_alias_set(tree_node*)^M
        /space/rguenther/src/svn/trunk3/gcc/alias.c:880^M
0x751ce5 component_uses_parent_alias_set_from(tree_node const*)^M
        /space/rguenther/src/svn/trunk3/gcc/alias.c:635^M
0x7522ad reference_alias_ptr_type_1^M
        /space/rguenther/src/svn/trunk3/gcc/alias.c:747^M
0x752683 get_alias_set(tree_node*)^M
...

Richard.

Re: Enable pointer TBAA for LTO

[Ilya Verbin]

On Mon, Nov 23, 2015 at 16:31:42 +0100, Richard Biener wrote:
> I think it also causes the following and one related ICE
> 
> FAIL: gcc.dg/vect/pr62021.c -flto -ffat-lto-objects (internal compiler 
> error)
> 
> /space/rguenther/src/svn/trunk3/gcc/testsuite/gcc.dg/vect/pr62021.c:7:1: 
> internal compiler error: in get_alias_set, at alias.c:880^M
> 0x7528a7 get_alias_set(tree_node*)^M
>         /space/rguenther/src/svn/trunk3/gcc/alias.c:880^M
> 0x751ce5 component_uses_parent_alias_set_from(tree_node const*)^M
>         /space/rguenther/src/svn/trunk3/gcc/alias.c:635^M
> 0x7522ad reference_alias_ptr_type_1^M
>         /space/rguenther/src/svn/trunk3/gcc/alias.c:747^M
> 0x752683 get_alias_set(tree_node*)^M
> ...

And an ICE in intelmicemul offloading compiler:

FAIL: libgomp.c++/for-11.C (internal compiler error)
FAIL: libgomp.c++/for-13.C (internal compiler error)
FAIL: libgomp.c++/for-14.C (internal compiler error)
FAIL: libgomp.c/for-3.c (internal compiler error)
FAIL: libgomp.c/for-5.c (internal compiler error)
FAIL: libgomp.c/for-6.c (internal compiler error)

libgomp/testsuite/libgomp.c/for-2.h:201:9: internal compiler error: in get_alias_set, at alias.c:880
0x710eef get_alias_set(tree_node*)
        gcc/alias.c:880
0x71032d component_uses_parent_alias_set_from(tree_node const*)
        gcc/alias.c:635
0x7108f5 reference_alias_ptr_type_1
        gcc/alias.c:747
0x710ccb get_alias_set(tree_node*)
        gcc/alias.c:843
0x89d208 expand_assignment(tree_node*, tree_node*, bool)
        gcc/expr.c:5020
0x768ff7 expand_gimple_stmt_1
        gcc/cfgexpand.c:3592
0x7693e2 expand_gimple_stmt
        gcc/cfgexpand.c:3688
0x7704ed expand_gimple_basic_block
        gcc/cfgexpand.c:5694
0x771ff1 execute
        gcc/cfgexpand.c:6309
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.

  -- Ilya

Re: Enable pointer TBAA for LTO

[Jan Hubicka]

> 
> I think it also causes the following and one related ICE
> 
> FAIL: gcc.dg/vect/pr62021.c -flto -ffat-lto-objects (internal compiler 
> error)
> 
> /space/rguenther/src/svn/trunk3/gcc/testsuite/gcc.dg/vect/pr62021.c:7:1: 
> internal compiler error: in get_alias_set, at alias.c:880^M
> 0x7528a7 get_alias_set(tree_node*)^M
>         /space/rguenther/src/svn/trunk3/gcc/alias.c:880^M

Does this one reproduce with mainline? All thee ICEs are on the sanity check:
gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t));
which check that in LTO all types that ought to have CANONICAL_TYPE gets CANONICAL_TYPE
computed.  ICE here probalby means that the type somehow bypassed LTO canonical type merging
as well as the TYPE_CANONICAL=MAIN_VARIANT set in lto-streamer.c

Honza

Re: Enable pointer TBAA for LTO

[Jan Hubicka]

> 
> Please in future leave patches for review again if you do such
> big changes before committing...

Uhm, sorry, next time I will be more cureful.  It seemed rather easy after
debugging it but indeed it is somewhat surprising issue.
> 
> I don't understand why we need this (testcase?) because get_alias_set ()
> is supposed to do the alias-set of pointer globbing for us.

The situation is as follows.  You can have

struct a {
  int *ptr;
}

struct b {
  float *ptr;
}

Now, if becase type is ignored by TYPE_CANONICAL, we have

   TYPE_CANONICAL (sturct b) = struct a.

and while building alias set of "struct a" we record compoents as:

   struct a
      ^
      |
    int *

Now do

struct b b = {NULL};
float *p=&b->ptr;
*p=nonnull;
return b.ptr;

Now alias set of the initialization is alias set of "struct a". The alias set
of of the pointer store is "float *".  We ask alias oracle if "struct a" can
conflict with "float *" and answer is no, because "int *" (component of struct
b) and "float *" are not conflicting.  With the change we record component
alias as follows:

   struct a
      ^
      |
   void *

which makes the answer to be correct, because "int *" conflicts with all pointers,
so all such queries about a structure gimple_canonical_types_compatible with "struct a"
will be handled correctly.

I will add aritifical testcase for this after double checking that the code above
miscompiles without that conditional.

I found that having warning about TBAA incompatibility when doing merigng in
lto-symtab is great to catch issues like this.

I had this patch for quite some time, but it was producing obviously wrong
positives (in Fortran, Ada and also sometimes in Firefox on array initializes
of style int a[]={1,2,3}).  I wrongly assumed tha the bug is because we compute
TYPE_CANONICAL sensitively to array size and there are permited transitions
of array sizes between units.  THis is not the case.

Yesterday I found that the problem is with interaction of get_alias_set
globbing and gimple_canonical_types_compatible globbing.  We can't have
get_alias_set globbing more or less coarse than
gimple_canonical_types_compatible does.

Here the situation is reverse to the case above : because array type is
inherited from element type, we can't have TYPE_CANONICAL more globbed for
array than we have get_alias_set.  In this case the problem appeared when
TYPE_NONALIASED_COMPONENT array previaled in type merging other arrays.  The
situation got worse with pointer, becuase array of pointers of one type could
prevail array of pointers of other type and then the array type gets different
alias sets in different units.  This seems to work for C programs, but is
wrong.  I will send patch and separate explanation after re-testing final
version shortly.

Honza

Re: Enable pointer TBAA for LTO

[Richard Biener]

On November 23, 2015 5:50:25 PM GMT+01:00, Jan Hubicka <hubicka@ucw.cz> wrote:
>> 
>> I think it also causes the following and one related ICE
>> 
>> FAIL: gcc.dg/vect/pr62021.c -flto -ffat-lto-objects (internal
>compiler 
>> error)
>> 
>>
>/space/rguenther/src/svn/trunk3/gcc/testsuite/gcc.dg/vect/pr62021.c:7:1:
>
>> internal compiler error: in get_alias_set, at alias.c:880^M
>> 0x7528a7 get_alias_set(tree_node*)^M
>>         /space/rguenther/src/svn/trunk3/gcc/alias.c:880^M
>
>Does this one reproduce with mainline?

Yes, testsuite run on x86_64

 All thee ICEs are on the sanity
>check:
>gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t));
>which check that in LTO all types that ought to have CANONICAL_TYPE
>gets CANONICAL_TYPE
>computed.  ICE here probalby means that the type somehow bypassed LTO
>canonical type merging
>as well as the TYPE_CANONICAL=MAIN_VARIANT set in lto-streamer.c
>
>Honza

Re: Enable pointer TBAA for LTO

[Jan Hubicka]

> > You are right, TYPE_NONALIASED_COMPONENT is the wrong way.  I will fix it
> > and try to come up with a testcase (TYPE_NONALIASED_COMPONENT is quite
> > rarely used beast)
> 
> It's only used in Ada as far as I know, but is quite sensitive and quickly 
> leads to wrong code if not handled properly in my experience, so this could 
> well be responsible for the gnat1 miscompilation.

Build fialed same way before my patch. Moreover the problem can only happen on
array of pointers that are type punned (i.e.  using store like 
(void *[r])array = [NULL, NULL, NULL]
and then accessing it as (int *[r]) array.   I do not think C or Ada can produce
code like that.

I am re-testing with the fix to TYPE_NONALIASED_COMPONENT arrays I explained in
other email. Perhaps that helps, or perhaps it is one of those Ada/C type puning
glues getting miscompiled?  Other Ada binaries (gnatbind) seems to work fine.
I will post backtrace once my testing gets to the ICE again.

Honza
> 
> -- 
> Eric Botcazou

Re: Enable pointer TBAA for LTO

[Jan Hubicka]

> I don't understand why we need this (testcase?) because get_alias_set ()
> is supposed to do the alias-set of pointer globbing for us.
Hi,
After some experimentation I managed to derive self contained testcase (other than GCC itself).
struct a/b/c gets the same TYPE_CANONICAL which is different from struct b. Without that
change in recording component aliases then the alias_set of struct b has component float *
instead of int *. Eventually in main we optimize out the store to int * because we do not
see the conflict.

One needs to add the extra garbage around to be sure that things are streamed
in proper order and also in proper order shipped to ltrans and finally the
gimple optimizers are not smart enough to get the propagation without TBAA
oracle help.

Comitted.

	* gcc.c-torture/execute/lto-tbaa-1.c: New testcase.
Index: gcc.c-torture/execute/lto-tbaa-1.c
===================================================================
--- gcc.c-torture/execute/lto-tbaa-1.c	(revision 0)
+++ gcc.c-torture/execute/lto-tbaa-1.c	(revision 0)
@@ -0,0 +1,42 @@
+/* { dg-additional-options "-fno-early-inlining -fno-ipa-cp" }  */
+struct a {
+  float *b;
+} *a;
+struct b {
+  int *b;
+} b;
+struct c {
+  float *b;
+} *c;
+int d;
+use_a (struct a *a)
+{
+}
+set_b (int **a)
+{
+  *a=&d;
+}
+use_c (struct c *a)
+{
+}
+__attribute__ ((noinline)) int **retme(int **val)
+{
+  return val;
+}
+int e;
+struct b b= {&e};
+struct b b2;
+struct b b3;
+int **ptr = &b2.b;
+main ()
+{
+  a= (void *)0;
+  b.b=&e;
+  ptr =retme ( &b.b);
+  set_b (ptr);
+  b3=b;
+  if (b3.b != &d)
+  __builtin_abort ();
+  c= (void *)0;
+  return 0;
+}

Re: Enable pointer TBAA for LTO

[Jan Hubicka]

> On November 23, 2015 5:50:25 PM GMT+01:00, Jan Hubicka <hubicka@ucw.cz> wrote:
> >> 
> >> I think it also causes the following and one related ICE
> >> 
> >> FAIL: gcc.dg/vect/pr62021.c -flto -ffat-lto-objects (internal
> >compiler 
> >> error)
> >> 
> >>
> >/space/rguenther/src/svn/trunk3/gcc/testsuite/gcc.dg/vect/pr62021.c:7:1:
> >
> >> internal compiler error: in get_alias_set, at alias.c:880^M
> >> 0x7528a7 get_alias_set(tree_node*)^M
> >>         /space/rguenther/src/svn/trunk3/gcc/alias.c:880^M
> >
> >Does this one reproduce with mainline?
> 
> Yes, testsuite run on x86_64
> 
>  All thee ICEs are on the sanity
> >check:
> >gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t));
> >which check that in LTO all types that ought to have CANONICAL_TYPE
> >gets CANONICAL_TYPE
> >computed.  ICE here probalby means that the type somehow bypassed LTO
> >canonical type merging
> >as well as the TYPE_CANONICAL=MAIN_VARIANT set in lto-streamer.c

Hi,
all the ICE seems to be caused by fact that the simd streaming code creates
array of pointers at ltrans time. Because pointers are now
TYPE_STRUCTURAL_EQUALITY_P, we get array with TYPE_STRUCTURAL_EQUALITY_P
and that sanity check is there to verify that this doesn't happen (because
we lose optimization then)

This patch makes arrays and vectors to be handled same way as pointers:
the canonical type is not computed because it is unused by get_alias_set
anyway.

I implemented it for different reason - my TBAA checking in lto-symtab got
false positives on arrays during the LTO bootstrap.  THe problem was again
the overly generous globbing of TYPE_CANONICAL.

get_alias_set first does

 t = TYPE_CANONICAL (t)

and then for arrays recurses

 set = get_alias_set (TREE_TYPE (t));

Now we can have type

 int *[10];

with TYPE_CANONICAL

 float *[10];

and then get_alias_set (int *[10]) will return get_alias_set (float *)
which is wrong, because then the array does not conflict with its elements.
I did not managed to get any wrong code out of this, but it is an obvious bug.
This problem reproduced prior the pointer patch, too, on other types which are
globed at TYPE_CANONICAL computation.

This also fixeds semi-latent bug with Ada where TYPE_STRUCTURAL_EQUALITY_P type
may win the merging and turn all interoperable arrays into
TYPE_STRUCTURAL_EQUALITY_P.

For next stage1 I think I can move frontends away from computing TYPE_CANONICAL
for those types. At least my initial test for C and C++ seemed to work just fine.

Bootstrapped/regtested x86_64-linux, OK?

	* lto-streamer-in.c (lto_read_body_or_constructor): Set TYPE_CANONICAL
	only for types where LTO sets them.
	* tree.c (build_array_type_1): Do ont set TYPE_CANONICAL for LTO.
	(make_vector_type): Likewise.
	(gimple_canonical_types_compatible_p): Use canonical_type_used_p.
	* tree.h (canonical_type_used_p): New inline.
	* alias.c (get_alias_set): Handle structural equality for all
	types that pass canonical_type_used_p.
	(record_component_aliases): Look through all types with
	record_component_aliases for possible pointers; sanity check that
	the alias sets match.

	* lto.c (iterative_hash_canonical_type): Recruse for all types
	which pass !canonical_type_used_p.
	(gimple_register_canonical_type_1): Sanity check we do not compute
	canonical type of anything with !canonical_type_used_p.
	(gimple_register_canonical_type): Skip all types that are
	!canonical_type_used_p

Index: lto-streamer-in.c
===================================================================
--- lto-streamer-in.c	(revision 230718)
+++ lto-streamer-in.c	(working copy)
@@ -1231,7 +1231,9 @@ lto_read_body_or_constructor (struct lto
 	      if (TYPE_P (t))
 		{
 		  gcc_assert (TYPE_CANONICAL (t) == NULL_TREE);
-		  TYPE_CANONICAL (t) = TYPE_MAIN_VARIANT (t);
+		  if (type_with_alias_set_p (t)
+		      && canonical_type_used_p (t))
+		    TYPE_CANONICAL (t) = TYPE_MAIN_VARIANT (t);
 		  if (TYPE_MAIN_VARIANT (t) != t)
 		    {
 		      gcc_assert (TYPE_NEXT_VARIANT (t) == NULL_TREE);
Index: tree.c
===================================================================
--- tree.c	(revision 230718)
+++ tree.c	(working copy)
@@ -8236,7 +8243,8 @@ build_array_type_1 (tree elt_type, tree
   if (TYPE_CANONICAL (t) == t)
     {
       if (TYPE_STRUCTURAL_EQUALITY_P (elt_type)
-	  || (index_type && TYPE_STRUCTURAL_EQUALITY_P (index_type)))
+	  || (index_type && TYPE_STRUCTURAL_EQUALITY_P (index_type))
+	  || in_lto_p)
 	SET_TYPE_STRUCTURAL_EQUALITY (t);
       else if (TYPE_CANONICAL (elt_type) != elt_type
 	       || (index_type && TYPE_CANONICAL (index_type) != index_type))
@@ -9849,13 +9857,13 @@ make_vector_type (tree innertype, int nu
   SET_TYPE_VECTOR_SUBPARTS (t, nunits);
   SET_TYPE_MODE (t, mode);
 
-  if (TYPE_STRUCTURAL_EQUALITY_P (innertype))
+  if (TYPE_STRUCTURAL_EQUALITY_P (innertype) || in_lto_p)
     SET_TYPE_STRUCTURAL_EQUALITY (t);
   else if ((TYPE_CANONICAL (innertype) != innertype
 	    || mode != VOIDmode)
 	   && !VECTOR_BOOLEAN_TYPE_P (t))
     TYPE_CANONICAL (t)
-      = make_vector_type (TYPE_CANONICAL (innertype), nunits, VOIDmode);
+      = make_vector_type (TYPE_CANONICAL (innertype), nunits, VOIDmode);
 
   layout_type (t);
 
@@ -13279,7 +13292,8 @@ gimple_canonical_types_compatible_p (con
 	 TYPE_CANONICAL is more fine grained than the equivalnce we test (where
 	 all pointers are considered equal.  Be sure to not return false
 	 negatives.  */
-      gcc_checking_assert (!POINTER_TYPE_P (t1) && !POINTER_TYPE_P (t2));
+      gcc_checking_assert (canonical_type_used_p (t1)
+			   && canonical_type_used_p (t2));
       return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
     }
 
Index: tree.h
===================================================================
--- tree.h	(revision 230718)
+++ tree.h	(working copy)
@@ -4807,7 +4807,9 @@ extern void DEBUG_FUNCTION verify_type (
 extern bool gimple_canonical_types_compatible_p (const_tree, const_tree,
 						 bool trust_type_canonical = true);
 extern bool type_with_interoperable_signedness (const_tree);
-/* Return simplified tree code of type that is used for canonical type merging.  */
+
+/* Return simplified tree code of type that is used for canonical type
+   merging.  */
 inline enum tree_code
 tree_code_for_canonical_type_merging (enum tree_code code)
 {
@@ -4829,6 +4831,23 @@ tree_code_for_canonical_type_merging (en
   return code;
 }
 
+/* Return ture if get_alias_set care about TYPE_CANONICAL of given type.
+   We don't define the types for pointers, arrays and vectors.  The reason is
+   that pointers are handled specially: ptr_type_node accesses conflict with
+   accesses to all other pointers.  This is done by alias.c.
+   Because alias sets of arrays and vectors are the same as types of their
+   elements, we can't compute canonical type either.  Otherwise we could go
+   form void *[10] to int *[10] (because they are equivalent for canonical type
+   machinery) and get wrong TBAA.  */
+
+inline bool
+canonical_type_used_p (const_tree t)
+{
+  return !(POINTER_TYPE_P (t)
+	   || TREE_CODE (t) == ARRAY_TYPE
+	   || TREE_CODE (t) == VECTOR_TYPE);
+}
+
 #define tree_map_eq tree_map_base_eq
 extern unsigned int tree_map_hash (const void *);
 #define tree_map_marked_p tree_map_base_marked_p
Index: alias.c
===================================================================
--- alias.c	(revision 230718)
+++ alias.c	(working copy)
@@ -869,11 +870,11 @@ get_alias_set (tree t)
       set = lang_hooks.get_alias_set (t);
       if (set != -1)
 	return set;
-      /* Handle structure type equality for pointer types.  This is easy
-	 to do, because the code bellow ignore canonical types on these anyway.
-	 This is important for LTO, where TYPE_CANONICAL for pointers can not
-	 be meaningfuly computed by the frotnend.  */
-      if (!POINTER_TYPE_P (t))
+      /* Handle structure type equality for pointer types, arrays and vectors.
+	 This is easy to do, because the code bellow ignore canonical types on
+	 these anyway.  This is important for LTO, where TYPE_CANONICAL for
+	 pointers can not be meaningfuly computed by the frotnend.  */
+      if (canonical_type_used_p (t))
 	{
 	  /* In LTO we set canonical types for all types where it makes
 	     sense to do so.  Double check we did not miss some type.  */
@@ -929,7 +931,9 @@ get_alias_set (tree t)
      integer(kind=4)[4] the same alias set or not.
      Just be pragmatic here and make sure the array and its element
      type get the same alias set assigned.  */
-  else if (TREE_CODE (t) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (t))
+  else if (TREE_CODE (t) == ARRAY_TYPE
+	   && (!TYPE_NONALIASED_COMPONENT (t)
+	       || TYPE_STRUCTURAL_EQUALITY_P (t)))
     set = get_alias_set (TREE_TYPE (t));
 
   /* From the former common C and C++ langhook implementation:
@@ -971,7 +975,10 @@ get_alias_set (tree t)
 	 We also want to make pointer to array/vector equivalent to pointer to
 	 its element (see the reasoning above). Skip all those types, too.  */
       for (p = t; POINTER_TYPE_P (p)
-	   || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p))
+	   || (TREE_CODE (p) == ARRAY_TYPE
+	       && (!TYPE_NONALIASED_COMPONENT (p)
+		   || !COMPLETE_TYPE_P (p)
+		   || TYPE_STRUCTURAL_EQUALITY_P (p)))
 	   || TREE_CODE (p) == VECTOR_TYPE;
 	   p = TREE_TYPE (p))
 	{
@@ -1195,20 +1203,23 @@ record_component_aliases (tree type)
 	       Accesses to it conflicts with accesses to any other pointer
 	       type.  */
 	    tree t = TREE_TYPE (field);
-	    if (in_lto_p)
+	    if (in_lto_p)
 	      {
 		/* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
 		   element type and that type has to be normalized to void *,
 		   too, in the case it is a pointer. */
-		while ((TREE_CODE (t) == ARRAY_TYPE
-			&& (!COMPLETE_TYPE_P (t)
-			    || TYPE_NONALIASED_COMPONENT (t)))
-		       || TREE_CODE (t) == VECTOR_TYPE)
-		  t = TREE_TYPE (t);
+		while (!canonical_type_used_p (t) && !POINTER_TYPE_P (t))
+		  {
+		    gcc_checking_assert (TYPE_STRUCTURAL_EQUALITY_P (t));
+		    t = TREE_TYPE (t);
+		  }
 		if (POINTER_TYPE_P (t))
 		  t = ptr_type_node;
+		else if (flag_checking)
+		  gcc_checking_assert (get_alias_set (t)
+				       == get_alias_set (TREE_TYPE (field)));
 	      }
-	   
+
 	    record_alias_subset (superset, get_alias_set (t));
 	  }
       break;
Index: lto/lto.c
===================================================================
--- lto/lto.c	(revision 230718)
+++ lto/lto.c	(working copy)
@@ -389,9 +389,7 @@ iterative_hash_canonical_type (tree type
   /* All type variants have same TYPE_CANONICAL.  */
   type = TYPE_MAIN_VARIANT (type);
 
-  /* We do not compute TYPE_CANONICAl of POINTER_TYPE because the aliasing
-     code never use it anyway.  */
-  if (POINTER_TYPE_P (type))
+  if (!canonical_type_used_p (type))
     v = hash_canonical_type (type);
   /* An already processed type.  */
   else if (TYPE_CANONICAL (type))
@@ -444,7 +442,7 @@ gimple_register_canonical_type_1 (tree t
 
   gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t)
 		       && type_with_alias_set_p (t)
-		       && !POINTER_TYPE_P (t));
+		       && canonical_type_used_p (t));
 
   slot = htab_find_slot_with_hash (gimple_canonical_types, t, hash, INSERT);
   if (*slot)
@@ -477,7 +475,8 @@ gimple_register_canonical_type_1 (tree t
 static void
 gimple_register_canonical_type (tree t)
 {
-  if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t) || POINTER_TYPE_P (t))
+  if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t)
+      || !canonical_type_used_p (t))
     return;
 
   /* Canonical types are same among all complete variants.  */

Re: Enable pointer TBAA for LTO

[Richard Biener]

On Mon, 23 Nov 2015, Jan Hubicka wrote:

> > 
> > Please in future leave patches for review again if you do such
> > big changes before committing...
> 
> Uhm, sorry, next time I will be more cureful.  It seemed rather easy after
> debugging it but indeed it is somewhat surprising issue.
> > 
> > I don't understand why we need this (testcase?) because get_alias_set ()
> > is supposed to do the alias-set of pointer globbing for us.
> 
> The situation is as follows.  You can have
> 
> struct a {
>   int *ptr;
> }
> 
> struct b {
>   float *ptr;
> }
> 
> Now, if becase type is ignored by TYPE_CANONICAL, we have
> 
>    TYPE_CANONICAL (sturct b) = struct a.
> 
> and while building alias set of "struct a" we record compoents as:
> 
>    struct a
>       ^
>       |
>     int *
> 
> Now do
> 
> struct b b = {NULL};
> float *p=&b->ptr;
> *p=nonnull;
> return b.ptr;
> 
> Now alias set of the initialization is alias set of "struct a". The alias set
> of of the pointer store is "float *".  We ask alias oracle if "struct a" can
> conflict with "float *" and answer is no, because "int *" (component of struct
> b) and "float *" are not conflicting.  With the change we record component
> alias as follows:

Ah, with my original pointer globbing I side-stepped this.  So are
you _really_ sure that we want to handle int * different from float *?
Because that makes the situation much more complicated in these cases.

> 
>    struct a
>       ^
>       |
>    void *
> 
> which makes the answer to be correct, because "int *" conflicts with all 
> pointers, so all such queries about a structure 
> gimple_canonical_types_compatible with "struct a" will be handled 
> correctly.
>
> I will add aritifical testcase for this after double checking that the code above
> miscompiles without that conditional.
> 
> I found that having warning about TBAA incompatibility when doing merigng in
> lto-symtab is great to catch issues like this.
> 
> I had this patch for quite some time, but it was producing obviously wrong
> positives (in Fortran, Ada and also sometimes in Firefox on array initializes
> of style int a[]={1,2,3}).  I wrongly assumed tha the bug is because we compute
> TYPE_CANONICAL sensitively to array size and there are permited transitions
> of array sizes between units.  THis is not the case.
> 
> Yesterday I found that the problem is with interaction of get_alias_set
> globbing and gimple_canonical_types_compatible globbing.  We can't have
> get_alias_set globbing more or less coarse than
> gimple_canonical_types_compatible does.
> 
> Here the situation is reverse to the case above : because array type is
> inherited from element type, we can't have TYPE_CANONICAL more globbed for
> array than we have get_alias_set.  In this case the problem appeared when
> TYPE_NONALIASED_COMPONENT array previaled in type merging other arrays.  The
> situation got worse with pointer, becuase array of pointers of one type could
> prevail array of pointers of other type and then the array type gets different
> alias sets in different units.  This seems to work for C programs, but is
> wrong.  I will send patch and separate explanation after re-testing final
> version shortly.

I feel we need to document all this somewhere.

Richard.
 
> Honza
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Re: Enable pointer TBAA for LTO

[Richard Biener]

On Tue, 24 Nov 2015, Jan Hubicka wrote:

> > On November 23, 2015 5:50:25 PM GMT+01:00, Jan Hubicka <hubicka@ucw.cz> wrote:
> > >> 
> > >> I think it also causes the following and one related ICE
> > >> 
> > >> FAIL: gcc.dg/vect/pr62021.c -flto -ffat-lto-objects (internal
> > >compiler 
> > >> error)
> > >> 
> > >>
> > >/space/rguenther/src/svn/trunk3/gcc/testsuite/gcc.dg/vect/pr62021.c:7:1:
> > >
> > >> internal compiler error: in get_alias_set, at alias.c:880^M
> > >> 0x7528a7 get_alias_set(tree_node*)^M
> > >>         /space/rguenther/src/svn/trunk3/gcc/alias.c:880^M
> > >
> > >Does this one reproduce with mainline?
> > 
> > Yes, testsuite run on x86_64
> > 
> >  All thee ICEs are on the sanity
> > >check:
> > >gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t));
> > >which check that in LTO all types that ought to have CANONICAL_TYPE
> > >gets CANONICAL_TYPE
> > >computed.  ICE here probalby means that the type somehow bypassed LTO
> > >canonical type merging
> > >as well as the TYPE_CANONICAL=MAIN_VARIANT set in lto-streamer.c
> 
> Hi,
> all the ICE seems to be caused by fact that the simd streaming code creates
> array of pointers at ltrans time. Because pointers are now
> TYPE_STRUCTURAL_EQUALITY_P, we get array with TYPE_STRUCTURAL_EQUALITY_P
> and that sanity check is there to verify that this doesn't happen (because
> we lose optimization then)
> 
> This patch makes arrays and vectors to be handled same way as pointers:
> the canonical type is not computed because it is unused by get_alias_set
> anyway.
> 
> I implemented it for different reason - my TBAA checking in lto-symtab got
> false positives on arrays during the LTO bootstrap.  THe problem was again
> the overly generous globbing of TYPE_CANONICAL.
> 
> get_alias_set first does
> 
>  t = TYPE_CANONICAL (t)
> 
> and then for arrays recurses
> 
>  set = get_alias_set (TREE_TYPE (t));
> 
> Now we can have type
> 
>  int *[10];
> 
> with TYPE_CANONICAL
> 
>  float *[10];
> 
> and then get_alias_set (int *[10]) will return get_alias_set (float *)
> which is wrong, because then the array does not conflict with its elements.
> I did not managed to get any wrong code out of this, but it is an obvious bug.
> This problem reproduced prior the pointer patch, too, on other types which are
> globed at TYPE_CANONICAL computation.
> 
> This also fixeds semi-latent bug with Ada where TYPE_STRUCTURAL_EQUALITY_P type
> may win the merging and turn all interoperable arrays into
> TYPE_STRUCTURAL_EQUALITY_P.
> 
> For next stage1 I think I can move frontends away from computing TYPE_CANONICAL
> for those types. At least my initial test for C and C++ seemed to work just fine.
> 
> Bootstrapped/regtested x86_64-linux, OK?

I don't like the in_lto_p checks in tree.c but as you say they'll be 
removed next stage1 ok.

Thanks,
Richard.

> 	* lto-streamer-in.c (lto_read_body_or_constructor): Set TYPE_CANONICAL
> 	only for types where LTO sets them.
> 	* tree.c (build_array_type_1): Do ont set TYPE_CANONICAL for LTO.
> 	(make_vector_type): Likewise.
> 	(gimple_canonical_types_compatible_p): Use canonical_type_used_p.
> 	* tree.h (canonical_type_used_p): New inline.
> 	* alias.c (get_alias_set): Handle structural equality for all
> 	types that pass canonical_type_used_p.
> 	(record_component_aliases): Look through all types with
> 	record_component_aliases for possible pointers; sanity check that
> 	the alias sets match.
> 
> 	* lto.c (iterative_hash_canonical_type): Recruse for all types
> 	which pass !canonical_type_used_p.
> 	(gimple_register_canonical_type_1): Sanity check we do not compute
> 	canonical type of anything with !canonical_type_used_p.
> 	(gimple_register_canonical_type): Skip all types that are
> 	!canonical_type_used_p
> 
> Index: lto-streamer-in.c
> ===================================================================
> --- lto-streamer-in.c	(revision 230718)
> +++ lto-streamer-in.c	(working copy)
> @@ -1231,7 +1231,9 @@ lto_read_body_or_constructor (struct lto
>  	      if (TYPE_P (t))
>  		{
>  		  gcc_assert (TYPE_CANONICAL (t) == NULL_TREE);
> -		  TYPE_CANONICAL (t) = TYPE_MAIN_VARIANT (t);
> +		  if (type_with_alias_set_p (t)
> +		      && canonical_type_used_p (t))
> +		    TYPE_CANONICAL (t) = TYPE_MAIN_VARIANT (t);
>  		  if (TYPE_MAIN_VARIANT (t) != t)
>  		    {
>  		      gcc_assert (TYPE_NEXT_VARIANT (t) == NULL_TREE);
> Index: tree.c
> ===================================================================
> --- tree.c	(revision 230718)
> +++ tree.c	(working copy)
> @@ -8236,7 +8243,8 @@ build_array_type_1 (tree elt_type, tree
>    if (TYPE_CANONICAL (t) == t)
>      {
>        if (TYPE_STRUCTURAL_EQUALITY_P (elt_type)
> -	  || (index_type && TYPE_STRUCTURAL_EQUALITY_P (index_type)))
> +	  || (index_type && TYPE_STRUCTURAL_EQUALITY_P (index_type))
> +	  || in_lto_p)
>  	SET_TYPE_STRUCTURAL_EQUALITY (t);
>        else if (TYPE_CANONICAL (elt_type) != elt_type
>  	       || (index_type && TYPE_CANONICAL (index_type) != index_type))
> @@ -9849,13 +9857,13 @@ make_vector_type (tree innertype, int nu
>    SET_TYPE_VECTOR_SUBPARTS (t, nunits);
>    SET_TYPE_MODE (t, mode);
>  
> -  if (TYPE_STRUCTURAL_EQUALITY_P (innertype))
> +  if (TYPE_STRUCTURAL_EQUALITY_P (innertype) || in_lto_p)
>      SET_TYPE_STRUCTURAL_EQUALITY (t);
>    else if ((TYPE_CANONICAL (innertype) != innertype
>  	    || mode != VOIDmode)
>  	   && !VECTOR_BOOLEAN_TYPE_P (t))
>      TYPE_CANONICAL (t)
> -      = make_vector_type (TYPE_CANONICAL (innertype), nunits, VOIDmode);
> +      = make_vector_type (TYPE_CANONICAL (innertype), nunits, VOIDmode);
>  
>    layout_type (t);
>  
> @@ -13279,7 +13292,8 @@ gimple_canonical_types_compatible_p (con
>  	 TYPE_CANONICAL is more fine grained than the equivalnce we test (where
>  	 all pointers are considered equal.  Be sure to not return false
>  	 negatives.  */
> -      gcc_checking_assert (!POINTER_TYPE_P (t1) && !POINTER_TYPE_P (t2));
> +      gcc_checking_assert (canonical_type_used_p (t1)
> +			   && canonical_type_used_p (t2));
>        return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
>      }
>  
> Index: tree.h
> ===================================================================
> --- tree.h	(revision 230718)
> +++ tree.h	(working copy)
> @@ -4807,7 +4807,9 @@ extern void DEBUG_FUNCTION verify_type (
>  extern bool gimple_canonical_types_compatible_p (const_tree, const_tree,
>  						 bool trust_type_canonical = true);
>  extern bool type_with_interoperable_signedness (const_tree);
> -/* Return simplified tree code of type that is used for canonical type merging.  */
> +
> +/* Return simplified tree code of type that is used for canonical type
> +   merging.  */
>  inline enum tree_code
>  tree_code_for_canonical_type_merging (enum tree_code code)
>  {
> @@ -4829,6 +4831,23 @@ tree_code_for_canonical_type_merging (en
>    return code;
>  }
>  
> +/* Return ture if get_alias_set care about TYPE_CANONICAL of given type.
> +   We don't define the types for pointers, arrays and vectors.  The reason is
> +   that pointers are handled specially: ptr_type_node accesses conflict with
> +   accesses to all other pointers.  This is done by alias.c.
> +   Because alias sets of arrays and vectors are the same as types of their
> +   elements, we can't compute canonical type either.  Otherwise we could go
> +   form void *[10] to int *[10] (because they are equivalent for canonical type
> +   machinery) and get wrong TBAA.  */
> +
> +inline bool
> +canonical_type_used_p (const_tree t)
> +{
> +  return !(POINTER_TYPE_P (t)
> +	   || TREE_CODE (t) == ARRAY_TYPE
> +	   || TREE_CODE (t) == VECTOR_TYPE);
> +}
> +
>  #define tree_map_eq tree_map_base_eq
>  extern unsigned int tree_map_hash (const void *);
>  #define tree_map_marked_p tree_map_base_marked_p
> Index: alias.c
> ===================================================================
> --- alias.c	(revision 230718)
> +++ alias.c	(working copy)
> @@ -869,11 +870,11 @@ get_alias_set (tree t)
>        set = lang_hooks.get_alias_set (t);
>        if (set != -1)
>  	return set;
> -      /* Handle structure type equality for pointer types.  This is easy
> -	 to do, because the code bellow ignore canonical types on these anyway.
> -	 This is important for LTO, where TYPE_CANONICAL for pointers can not
> -	 be meaningfuly computed by the frotnend.  */
> -      if (!POINTER_TYPE_P (t))
> +      /* Handle structure type equality for pointer types, arrays and vectors.
> +	 This is easy to do, because the code bellow ignore canonical types on
> +	 these anyway.  This is important for LTO, where TYPE_CANONICAL for
> +	 pointers can not be meaningfuly computed by the frotnend.  */
> +      if (canonical_type_used_p (t))
>  	{
>  	  /* In LTO we set canonical types for all types where it makes
>  	     sense to do so.  Double check we did not miss some type.  */
> @@ -929,7 +931,9 @@ get_alias_set (tree t)
>       integer(kind=4)[4] the same alias set or not.
>       Just be pragmatic here and make sure the array and its element
>       type get the same alias set assigned.  */
> -  else if (TREE_CODE (t) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (t))
> +  else if (TREE_CODE (t) == ARRAY_TYPE
> +	   && (!TYPE_NONALIASED_COMPONENT (t)
> +	       || TYPE_STRUCTURAL_EQUALITY_P (t)))
>      set = get_alias_set (TREE_TYPE (t));
>  
>    /* From the former common C and C++ langhook implementation:
> @@ -971,7 +975,10 @@ get_alias_set (tree t)
>  	 We also want to make pointer to array/vector equivalent to pointer to
>  	 its element (see the reasoning above). Skip all those types, too.  */
>        for (p = t; POINTER_TYPE_P (p)
> -	   || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p))
> +	   || (TREE_CODE (p) == ARRAY_TYPE
> +	       && (!TYPE_NONALIASED_COMPONENT (p)
> +		   || !COMPLETE_TYPE_P (p)
> +		   || TYPE_STRUCTURAL_EQUALITY_P (p)))
>  	   || TREE_CODE (p) == VECTOR_TYPE;
>  	   p = TREE_TYPE (p))
>  	{
> @@ -1195,20 +1203,23 @@ record_component_aliases (tree type)
>  	       Accesses to it conflicts with accesses to any other pointer
>  	       type.  */
>  	    tree t = TREE_TYPE (field);
> -	    if (in_lto_p)
> +	    if (in_lto_p)
>  	      {
>  		/* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
>  		   element type and that type has to be normalized to void *,
>  		   too, in the case it is a pointer. */
> -		while ((TREE_CODE (t) == ARRAY_TYPE
> -			&& (!COMPLETE_TYPE_P (t)
> -			    || TYPE_NONALIASED_COMPONENT (t)))
> -		       || TREE_CODE (t) == VECTOR_TYPE)
> -		  t = TREE_TYPE (t);
> +		while (!canonical_type_used_p (t) && !POINTER_TYPE_P (t))
> +		  {
> +		    gcc_checking_assert (TYPE_STRUCTURAL_EQUALITY_P (t));
> +		    t = TREE_TYPE (t);
> +		  }
>  		if (POINTER_TYPE_P (t))
>  		  t = ptr_type_node;
> +		else if (flag_checking)
> +		  gcc_checking_assert (get_alias_set (t)
> +				       == get_alias_set (TREE_TYPE (field)));
>  	      }
> -	   
> +
>  	    record_alias_subset (superset, get_alias_set (t));
>  	  }
>        break;
> Index: lto/lto.c
> ===================================================================
> --- lto/lto.c	(revision 230718)
> +++ lto/lto.c	(working copy)
> @@ -389,9 +389,7 @@ iterative_hash_canonical_type (tree type
>    /* All type variants have same TYPE_CANONICAL.  */
>    type = TYPE_MAIN_VARIANT (type);
>  
> -  /* We do not compute TYPE_CANONICAl of POINTER_TYPE because the aliasing
> -     code never use it anyway.  */
> -  if (POINTER_TYPE_P (type))
> +  if (!canonical_type_used_p (type))
>      v = hash_canonical_type (type);
>    /* An already processed type.  */
>    else if (TYPE_CANONICAL (type))
> @@ -444,7 +442,7 @@ gimple_register_canonical_type_1 (tree t
>  
>    gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t)
>  		       && type_with_alias_set_p (t)
> -		       && !POINTER_TYPE_P (t));
> +		       && canonical_type_used_p (t));
>  
>    slot = htab_find_slot_with_hash (gimple_canonical_types, t, hash, INSERT);
>    if (*slot)
> @@ -477,7 +475,8 @@ gimple_register_canonical_type_1 (tree t
>  static void
>  gimple_register_canonical_type (tree t)
>  {
> -  if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t) || POINTER_TYPE_P (t))
> +  if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t)
> +      || !canonical_type_used_p (t))
>      return;
>  
>    /* Canonical types are same among all complete variants.  */
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Re: Enable pointer TBAA for LTO

[Jan Hubicka]

> > Now alias set of the initialization is alias set of "struct a". The alias set
> > of of the pointer store is "float *".  We ask alias oracle if "struct a" can
> > conflict with "float *" and answer is no, because "int *" (component of struct
> > b) and "float *" are not conflicting.  With the change we record component
> > alias as follows:
> 
> Ah, with my original pointer globbing I side-stepped this.  So are
> you _really_ sure that we want to handle int * different from float *?
> Because that makes the situation much more complicated in these cases.

Yep, keeping track of different pointer types in C++ is really important
and moreover the old globbing was not able to deal with C/Fortran compatibility
fun anyway.

Average higher level C++ code has dozen of differently typed containers for
random stuff and shuffles the pointers around them in memory.  Without being
able to track down pointers stored in memory  there is no hope to optimize the
code.

This very basic pointer LTO reduced rodata cc1 binary by 7% which I think are
from 99% the removed sanity checking __FUNCTION__ locators. 

Globing all pointers to void * is just part of the problem anyway. The previous
code did not implemented Fortran/C interoperability correctly anyway.  I hope
that with these changes we have infrastructure robust and flexible enough
to model more precisely what we really want.

> > Here the situation is reverse to the case above : because array type is
> > inherited from element type, we can't have TYPE_CANONICAL more globbed for
> > array than we have get_alias_set.  In this case the problem appeared when
> > TYPE_NONALIASED_COMPONENT array previaled in type merging other arrays.  The
> > situation got worse with pointer, becuase array of pointers of one type could
> > prevail array of pointers of other type and then the array type gets different
> > alias sets in different units.  This seems to work for C programs, but is
> > wrong.  I will send patch and separate explanation after re-testing final
> > version shortly.
> 
> I feel we need to document all this somewhere.

Yeah, that would be a good idea.  Probably comment at beggining of alias.c?
I was thinking of moving the code to one place, perhaps moving 
gimple_canonical_type from tree.c to alias.c would make sense, or inventing
new place for this.

Moreover I was thinking of extending type verifier to check that all components
of a type alias with the whole tihng, so we do not run into bugs like this again.
Together with the TBAA checking in lto-symtab.c it should make it pretty
hard to make nasty bugs like this.

Thanks,
Honza
> 
> Richard.
>  
> > Honza
> > 
> > 
> 
> -- 
> Richard Biener <rguenther@suse.de>
> SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Re: Enable pointer TBAA for LTO

[James Greenhalgh]

On Tue, Nov 24, 2015 at 07:10:01AM +0100, Jan Hubicka wrote:
> > On November 23, 2015 5:50:25 PM GMT+01:00, Jan Hubicka <hubicka@ucw.cz> wrote:
> > >> 
> > >> I think it also causes the following and one related ICE
> > >> 
> > >> FAIL: gcc.dg/vect/pr62021.c -flto -ffat-lto-objects (internal
> > >compiler 
> > >> error)
> > >> 
> > >>
> > >/space/rguenther/src/svn/trunk3/gcc/testsuite/gcc.dg/vect/pr62021.c:7:1:
> > >
> > >> internal compiler error: in get_alias_set, at alias.c:880^M
> > >> 0x7528a7 get_alias_set(tree_node*)^M
> > >>         /space/rguenther/src/svn/trunk3/gcc/alias.c:880^M
> > >
> > >Does this one reproduce with mainline?
> > 
> > Yes, testsuite run on x86_64
> > 
> >  All thee ICEs are on the sanity
> > >check:
> > >gcc_checking_assert (!in_lto_p || !type_with_alias_set_p (t));
> > >which check that in LTO all types that ought to have CANONICAL_TYPE
> > >gets CANONICAL_TYPE
> > >computed.  ICE here probalby means that the type somehow bypassed LTO
> > >canonical type merging
> > >as well as the TYPE_CANONICAL=MAIN_VARIANT set in lto-streamer.c
> 
> 
> 	* lto-streamer-in.c (lto_read_body_or_constructor): Set TYPE_CANONICAL
> 	only for types where LTO sets them.
> 	* tree.c (build_array_type_1): Do ont set TYPE_CANONICAL for LTO.
> 	(make_vector_type): Likewise.
> 	(gimple_canonical_types_compatible_p): Use canonical_type_used_p.
> 	* tree.h (canonical_type_used_p): New inline.
> 	* alias.c (get_alias_set): Handle structural equality for all
> 	types that pass canonical_type_used_p.
> 	(record_component_aliases): Look through all types with
> 	record_component_aliases for possible pointers; sanity check that
> 	the alias sets match.
> 
> 	* lto.c (iterative_hash_canonical_type): Recruse for all types
> 	which pass !canonical_type_used_p.
> 	(gimple_register_canonical_type_1): Sanity check we do not compute
> 	canonical type of anything with !canonical_type_used_p.
> 	(gimple_register_canonical_type): Skip all types that are
> 	!canonical_type_used_p

Hi,

This patch introduces an ICE for an AArch64 testcase:

  FAIL: gcc.target/aarch64/advsimd-intrinsics/vstX_lane.c   -O2 -flto -fno-use-linker-plugin -flto-partition=none  (internal compiler error)

  Excess errors:
  ...../gcc/testsuite/gcc.target/aarch64/advsimd-intrinsics/vstX_lane.c:260:6: internal compiler error: in record_component_aliases, at alias.c:1219
  0x5ae2a5 record_component_aliases(tree_node*)
  	.../gcc/alias.c:1218
  0x5aed46 get_alias_set(tree_node*)
  	.../gcc/alias.c:1068
  0x5afe2a get_deref_alias_set(tree_node*)
  	.../gcc/alias.c:697
  0x5ae408 get_alias_set(tree_node*)
  	.../gcc/alias.c:845
  0xb6bfd7 vn_reference_lookup(tree_node*, tree_node*, vn_lookup_kind, vn_reference_s**)
  	.../gcc/tree-ssa-sccvn.c:2250
  0xb7026f visit_reference_op_store
  	.../gcc/tree-ssa-sccvn.c:3310
  0xb7026f visit_use
  	.../gcc/tree-ssa-sccvn.c:3558
  0xb716b4 process_scc
  	.../gcc/tree-ssa-sccvn.c:3800
  0xb716b4 extract_and_process_scc_for_name
  	.../gcc/tree-ssa-sccvn.c:3887
  0xb716b4 DFS
  	.../gcc/tree-ssa-sccvn.c:3939
  0xb729db sccvn_dom_walker::before_dom_children(basic_block_def*)
  	.../gcc/tree-ssa-sccvn.c:4427
  0xec017f dom_walker::walk(basic_block_def*)
  	.../gcc/domwalk.c:176
  0xb73aaa run_scc_vn(vn_lookup_kind)
  	.../gcc/tree-ssa-sccvn.c:4550
  0xb48278 execute
  	.../gcc/tree-ssa-pre.c:4891

Thanks,
James

> 
> Index: lto-streamer-in.c
> ===================================================================
> --- lto-streamer-in.c	(revision 230718)
> +++ lto-streamer-in.c	(working copy)
> @@ -1231,7 +1231,9 @@ lto_read_body_or_constructor (struct lto
>  	      if (TYPE_P (t))
>  		{
>  		  gcc_assert (TYPE_CANONICAL (t) == NULL_TREE);
> -		  TYPE_CANONICAL (t) = TYPE_MAIN_VARIANT (t);
> +		  if (type_with_alias_set_p (t)
> +		      && canonical_type_used_p (t))
> +		    TYPE_CANONICAL (t) = TYPE_MAIN_VARIANT (t);
>  		  if (TYPE_MAIN_VARIANT (t) != t)
>  		    {
>  		      gcc_assert (TYPE_NEXT_VARIANT (t) == NULL_TREE);
> Index: tree.c
> ===================================================================
> --- tree.c	(revision 230718)
> +++ tree.c	(working copy)
> @@ -8236,7 +8243,8 @@ build_array_type_1 (tree elt_type, tree
>    if (TYPE_CANONICAL (t) == t)
>      {
>        if (TYPE_STRUCTURAL_EQUALITY_P (elt_type)
> -	  || (index_type && TYPE_STRUCTURAL_EQUALITY_P (index_type)))
> +	  || (index_type && TYPE_STRUCTURAL_EQUALITY_P (index_type))
> +	  || in_lto_p)
>  	SET_TYPE_STRUCTURAL_EQUALITY (t);
>        else if (TYPE_CANONICAL (elt_type) != elt_type
>  	       || (index_type && TYPE_CANONICAL (index_type) != index_type))
> @@ -9849,13 +9857,13 @@ make_vector_type (tree innertype, int nu
>    SET_TYPE_VECTOR_SUBPARTS (t, nunits);
>    SET_TYPE_MODE (t, mode);
>  
> -  if (TYPE_STRUCTURAL_EQUALITY_P (innertype))
> +  if (TYPE_STRUCTURAL_EQUALITY_P (innertype) || in_lto_p)
>      SET_TYPE_STRUCTURAL_EQUALITY (t);
>    else if ((TYPE_CANONICAL (innertype) != innertype
>  	    || mode != VOIDmode)
>  	   && !VECTOR_BOOLEAN_TYPE_P (t))
>      TYPE_CANONICAL (t)
> -      = make_vector_type (TYPE_CANONICAL (innertype), nunits, VOIDmode);
> +      = make_vector_type (TYPE_CANONICAL (innertype), nunits, VOIDmode);
>  
>    layout_type (t);
>  
> @@ -13279,7 +13292,8 @@ gimple_canonical_types_compatible_p (con
>  	 TYPE_CANONICAL is more fine grained than the equivalnce we test (where
>  	 all pointers are considered equal.  Be sure to not return false
>  	 negatives.  */
> -      gcc_checking_assert (!POINTER_TYPE_P (t1) && !POINTER_TYPE_P (t2));
> +      gcc_checking_assert (canonical_type_used_p (t1)
> +			   && canonical_type_used_p (t2));
>        return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
>      }
>  
> Index: tree.h
> ===================================================================
> --- tree.h	(revision 230718)
> +++ tree.h	(working copy)
> @@ -4807,7 +4807,9 @@ extern void DEBUG_FUNCTION verify_type (
>  extern bool gimple_canonical_types_compatible_p (const_tree, const_tree,
>  						 bool trust_type_canonical = true);
>  extern bool type_with_interoperable_signedness (const_tree);
> -/* Return simplified tree code of type that is used for canonical type merging.  */
> +
> +/* Return simplified tree code of type that is used for canonical type
> +   merging.  */
>  inline enum tree_code
>  tree_code_for_canonical_type_merging (enum tree_code code)
>  {
> @@ -4829,6 +4831,23 @@ tree_code_for_canonical_type_merging (en
>    return code;
>  }
>  
> +/* Return ture if get_alias_set care about TYPE_CANONICAL of given type.
> +   We don't define the types for pointers, arrays and vectors.  The reason is
> +   that pointers are handled specially: ptr_type_node accesses conflict with
> +   accesses to all other pointers.  This is done by alias.c.
> +   Because alias sets of arrays and vectors are the same as types of their
> +   elements, we can't compute canonical type either.  Otherwise we could go
> +   form void *[10] to int *[10] (because they are equivalent for canonical type
> +   machinery) and get wrong TBAA.  */
> +
> +inline bool
> +canonical_type_used_p (const_tree t)
> +{
> +  return !(POINTER_TYPE_P (t)
> +	   || TREE_CODE (t) == ARRAY_TYPE
> +	   || TREE_CODE (t) == VECTOR_TYPE);
> +}
> +
>  #define tree_map_eq tree_map_base_eq
>  extern unsigned int tree_map_hash (const void *);
>  #define tree_map_marked_p tree_map_base_marked_p
> Index: alias.c
> ===================================================================
> --- alias.c	(revision 230718)
> +++ alias.c	(working copy)
> @@ -869,11 +870,11 @@ get_alias_set (tree t)
>        set = lang_hooks.get_alias_set (t);
>        if (set != -1)
>  	return set;
> -      /* Handle structure type equality for pointer types.  This is easy
> -	 to do, because the code bellow ignore canonical types on these anyway.
> -	 This is important for LTO, where TYPE_CANONICAL for pointers can not
> -	 be meaningfuly computed by the frotnend.  */
> -      if (!POINTER_TYPE_P (t))
> +      /* Handle structure type equality for pointer types, arrays and vectors.
> +	 This is easy to do, because the code bellow ignore canonical types on
> +	 these anyway.  This is important for LTO, where TYPE_CANONICAL for
> +	 pointers can not be meaningfuly computed by the frotnend.  */
> +      if (canonical_type_used_p (t))
>  	{
>  	  /* In LTO we set canonical types for all types where it makes
>  	     sense to do so.  Double check we did not miss some type.  */
> @@ -929,7 +931,9 @@ get_alias_set (tree t)
>       integer(kind=4)[4] the same alias set or not.
>       Just be pragmatic here and make sure the array and its element
>       type get the same alias set assigned.  */
> -  else if (TREE_CODE (t) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (t))
> +  else if (TREE_CODE (t) == ARRAY_TYPE
> +	   && (!TYPE_NONALIASED_COMPONENT (t)
> +	       || TYPE_STRUCTURAL_EQUALITY_P (t)))
>      set = get_alias_set (TREE_TYPE (t));
>  
>    /* From the former common C and C++ langhook implementation:
> @@ -971,7 +975,10 @@ get_alias_set (tree t)
>  	 We also want to make pointer to array/vector equivalent to pointer to
>  	 its element (see the reasoning above). Skip all those types, too.  */
>        for (p = t; POINTER_TYPE_P (p)
> -	   || (TREE_CODE (p) == ARRAY_TYPE && !TYPE_NONALIASED_COMPONENT (p))
> +	   || (TREE_CODE (p) == ARRAY_TYPE
> +	       && (!TYPE_NONALIASED_COMPONENT (p)
> +		   || !COMPLETE_TYPE_P (p)
> +		   || TYPE_STRUCTURAL_EQUALITY_P (p)))
>  	   || TREE_CODE (p) == VECTOR_TYPE;
>  	   p = TREE_TYPE (p))
>  	{
> @@ -1195,20 +1203,23 @@ record_component_aliases (tree type)
>  	       Accesses to it conflicts with accesses to any other pointer
>  	       type.  */
>  	    tree t = TREE_TYPE (field);
> -	    if (in_lto_p)
> +	    if (in_lto_p)
>  	      {
>  		/* VECTOR_TYPE and ARRAY_TYPE share the alias set with their
>  		   element type and that type has to be normalized to void *,
>  		   too, in the case it is a pointer. */
> -		while ((TREE_CODE (t) == ARRAY_TYPE
> -			&& (!COMPLETE_TYPE_P (t)
> -			    || TYPE_NONALIASED_COMPONENT (t)))
> -		       || TREE_CODE (t) == VECTOR_TYPE)
> -		  t = TREE_TYPE (t);
> +		while (!canonical_type_used_p (t) && !POINTER_TYPE_P (t))
> +		  {
> +		    gcc_checking_assert (TYPE_STRUCTURAL_EQUALITY_P (t));
> +		    t = TREE_TYPE (t);
> +		  }
>  		if (POINTER_TYPE_P (t))
>  		  t = ptr_type_node;
> +		else if (flag_checking)
> +		  gcc_checking_assert (get_alias_set (t)
> +				       == get_alias_set (TREE_TYPE (field)));
>  	      }
> -	   
> +
>  	    record_alias_subset (superset, get_alias_set (t));
>  	  }
>        break;
> Index: lto/lto.c
> ===================================================================
> --- lto/lto.c	(revision 230718)
> +++ lto/lto.c	(working copy)
> @@ -389,9 +389,7 @@ iterative_hash_canonical_type (tree type
>    /* All type variants have same TYPE_CANONICAL.  */
>    type = TYPE_MAIN_VARIANT (type);
>  
> -  /* We do not compute TYPE_CANONICAl of POINTER_TYPE because the aliasing
> -     code never use it anyway.  */
> -  if (POINTER_TYPE_P (type))
> +  if (!canonical_type_used_p (type))
>      v = hash_canonical_type (type);
>    /* An already processed type.  */
>    else if (TYPE_CANONICAL (type))
> @@ -444,7 +442,7 @@ gimple_register_canonical_type_1 (tree t
>  
>    gcc_checking_assert (TYPE_P (t) && !TYPE_CANONICAL (t)
>  		       && type_with_alias_set_p (t)
> -		       && !POINTER_TYPE_P (t));
> +		       && canonical_type_used_p (t));
>  
>    slot = htab_find_slot_with_hash (gimple_canonical_types, t, hash, INSERT);
>    if (*slot)
> @@ -477,7 +475,8 @@ gimple_register_canonical_type_1 (tree t
>  static void
>  gimple_register_canonical_type (tree t)
>  {
> -  if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t) || POINTER_TYPE_P (t))
> +  if (TYPE_CANONICAL (t) || !type_with_alias_set_p (t)
> +      || !canonical_type_used_p (t))
>      return;
>  
>    /* Canonical types are same among all complete variants.  */
> 

Re: Enable pointer TBAA for LTO

[Richard Biener]

On Tue, 24 Nov 2015, Jan Hubicka wrote:

> > > Now alias set of the initialization is alias set of "struct a". The alias set
> > > of of the pointer store is "float *".  We ask alias oracle if "struct a" can
> > > conflict with "float *" and answer is no, because "int *" (component of struct
> > > b) and "float *" are not conflicting.  With the change we record component
> > > alias as follows:
> > 
> > Ah, with my original pointer globbing I side-stepped this.  So are
> > you _really_ sure that we want to handle int * different from float *?
> > Because that makes the situation much more complicated in these cases.
> 
> Yep, keeping track of different pointer types in C++ is really important
> and moreover the old globbing was not able to deal with C/Fortran compatibility
> fun anyway.
> 
> Average higher level C++ code has dozen of differently typed containers for
> random stuff and shuffles the pointers around them in memory.  Without being
> able to track down pointers stored in memory  there is no hope to optimize the
> code.
> 
> This very basic pointer LTO reduced rodata cc1 binary by 7% which I think are
> from 99% the removed sanity checking __FUNCTION__ locators. 
> 
> Globing all pointers to void * is just part of the problem anyway. The previous
> code did not implemented Fortran/C interoperability correctly anyway.  I hope
> that with these changes we have infrastructure robust and flexible enough
> to model more precisely what we really want.
> 
> > > Here the situation is reverse to the case above : because array type is
> > > inherited from element type, we can't have TYPE_CANONICAL more globbed for
> > > array than we have get_alias_set.  In this case the problem appeared when
> > > TYPE_NONALIASED_COMPONENT array previaled in type merging other arrays.  The
> > > situation got worse with pointer, becuase array of pointers of one type could
> > > prevail array of pointers of other type and then the array type gets different
> > > alias sets in different units.  This seems to work for C programs, but is
> > > wrong.  I will send patch and separate explanation after re-testing final
> > > version shortly.
> > 
> > I feel we need to document all this somewhere.
> 
> Yeah, that would be a good idea.  Probably comment at beggining of alias.c?

Yes, that sounds good.

> I was thinking of moving the code to one place, perhaps moving 
> gimple_canonical_type from tree.c to alias.c would make sense, or inventing
> new place for this.

Didn't like tree.c for this anyway and yes, alias.c sounds better
given its connection to alias.

> Moreover I was thinking of extending type verifier to check that all 
> components of a type alias with the whole tihng, so we do not run into 
> bugs like this again. Together with the TBAA checking in lto-symtab.c it 
> should make it pretty hard to make nasty bugs like this.

Might be a bit expensive though.  It also reminds me of all the
ICEs we have PRs for WRT the type verifier.  Remember we are in stage3
now so rather than introducing new issues you should spend some time
fixing the existing ones you caused ;))  (just look for bugs
CCed to hubicka@gcc.gnu.org)

Thanks,
Richard.

Re: Enable pointer TBAA for LTO

[Jan Hubicka]

> 
> Might be a bit expensive though.  It also reminds me of all the
> ICEs we have PRs for WRT the type verifier.  Remember we are in stage3
> now so rather than introducing new issues you should spend some time
> fixing the existing ones you caused ;))  (just look for bugs
> CCed to hubicka@gcc.gnu.org)

Yep, I already fixed some of these, will push out patches today.

Honza
> 
> Thanks,
> Richard.

Re: Enable pointer TBAA for LTO

[Thomas Schwinge]

Hi!

On Mon, 23 Nov 2015 18:34:30 +0300, Ilya Verbin <iverbin@gmail.com> wrote:
> On Mon, Nov 23, 2015 at 16:31:42 +0100, Richard Biener wrote:
> > I think it also causes the following and one related ICE
> > 
> > FAIL: gcc.dg/vect/pr62021.c -flto -ffat-lto-objects (internal compiler 
> > error)
> > 
> > /space/rguenther/src/svn/trunk3/gcc/testsuite/gcc.dg/vect/pr62021.c:7:1: 
> > internal compiler error: in get_alias_set, at alias.c:880^M
> > 0x7528a7 get_alias_set(tree_node*)^M
> >         /space/rguenther/src/svn/trunk3/gcc/alias.c:880^M
> > 0x751ce5 component_uses_parent_alias_set_from(tree_node const*)^M
> >         /space/rguenther/src/svn/trunk3/gcc/alias.c:635^M
> > 0x7522ad reference_alias_ptr_type_1^M
> >         /space/rguenther/src/svn/trunk3/gcc/alias.c:747^M
> > 0x752683 get_alias_set(tree_node*)^M
> > ...
> 
> And an ICE in intelmicemul offloading compiler:
> 
> FAIL: libgomp.c++/for-11.C (internal compiler error)
> FAIL: libgomp.c++/for-13.C (internal compiler error)
> FAIL: libgomp.c++/for-14.C (internal compiler error)
> FAIL: libgomp.c/for-3.c (internal compiler error)
> FAIL: libgomp.c/for-5.c (internal compiler error)
> FAIL: libgomp.c/for-6.c (internal compiler error)
> 
> libgomp/testsuite/libgomp.c/for-2.h:201:9: internal compiler error: in get_alias_set, at alias.c:880
> 0x710eef get_alias_set(tree_node*)
>         gcc/alias.c:880
> 0x71032d component_uses_parent_alias_set_from(tree_node const*)
>         gcc/alias.c:635
> 0x7108f5 reference_alias_ptr_type_1
>         gcc/alias.c:747
> 0x710ccb get_alias_set(tree_node*)
>         gcc/alias.c:843
> 0x89d208 expand_assignment(tree_node*, tree_node*, bool)
>         gcc/expr.c:5020
> 0x768ff7 expand_gimple_stmt_1
>         gcc/cfgexpand.c:3592
> 0x7693e2 expand_gimple_stmt
>         gcc/cfgexpand.c:3688
> 0x7704ed expand_gimple_basic_block
>         gcc/cfgexpand.c:5694
> 0x771ff1 execute
>         gcc/cfgexpand.c:6309

Belatedly confirmed, and also confirmed fixed with trunk r230835,
<http://news.gmane.org/find-root.php?message_id=%3C20151124061000.GA4494%40kam.mff.cuni.cz%3E>.


Grüße
 Thomas