public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* Use ODR for canonical types construction in LTO
@ 2019-06-03 13:30 Jan Hubicka
  2019-06-14  9:49 ` Jan Hubicka
                   ` (2 more replies)
  0 siblings, 3 replies; 50+ messages in thread
From: Jan Hubicka @ 2019-06-03 13:30 UTC (permalink / raw)
  To: gcc-patches, rguenther, d, mliska

Hi,
this patch makes LTO to use ODR names when building canonical types.
Theoretically this is easy task because every ODR type is unique and
it is enough to fill in the hash with the ODR names and compare them.

In reality we want to be more careful and detect situation when non-ODR
type is structurally equivalent to ODR type so C++ code and non-C++ code
can co-exist.

I have implemented it as follows
 1) at stream in time populate canonical type hash by non-ODR types
    only.  Also register all ODR types into so we detect ODR violations.
 2) once all streaming is done we process all ODR types, lookup each
    of them in the canonical type hash and if structurally compatible
    type is present default to normal canonical type calculation.
    Otherwise canonical type of ODR type is the prevailing ODR variant.

Now the problem is that in C++ some structures can be non-ODR. For
example

struct A {int a;} a;
struct {int b;} b;

Here the second structure has no name and we have no way to tell if it
is C++ or non-C++ code at LTO time.  I tought that perhaps such conflicts
would be rare, but in reality most of types conflicts this way
(C++ FE seems to generate non-ODR types of same strucutre as ODR
types and they do get streamed, I am looking into this).
So more careful approach is needed.

I extende extend step 1 to also postpone types that reffers to ODR types (those
are known to originate from C++ translation units and do not need to be unified
by structurally equivalent ODR types).

This is tested by odr_or_derived_type_p which is kind of hack and perhaps we
should get around streaming this info somehow (but i would preffer to do that
incrementally)

Step 2 remain same.
Additional step 3 registers all odr derived types into canonical type hash.
This requires canonical type hash to play well with ODR types (i.e. not
consider them equivalent based on structural equivalety).

The decision on whether given type has ODR based canonical
type is stored in odr_based_tbaa_p and is used
 1) by gimple_canonical_types_compatible_p so the comparsion is
    behaving well after ODR types are inserted into the hash
 2) by alias.c to be build more precise alias sets - for ODR types
    it is not necessary to glob pointers into void *.
There is no need to update canonical type hash since I simply insert
hash codes of ODR names into canonical type hash cache.


LTO linking cc1plus there are 3317 ODR types that gets their own
canonical type and 876 which have conflict.  For example:

ODR and non-ODR type conflict: union ssa_name_info_type and union 
{
  const void * cv;
  void * v;
}
ODR and non-ODR type conflict: struct ht_identifier and struct 
{
  union byte_fail_stack_elt_t * stack;
  unsigned int size;
  unsigned int avail;
}
ODR and non-ODR type conflict: struct lang_hooks_for_tree_dump and struct 
{
  struct demangle_component * left;
  struct demangle_component * right;
}
ODR and non-ODR type conflict: struct call_site_record_d and struct 
{
  struct demangle_component * sub;
  int num;
}

etc.

So mostly random conflict induced by the C compiled liberty and other bits.
Clearly most common issue is globing of pointers and lack of field names
which is needed primarily for Fortran and is easy to disable for translation units
not having Fortran modules in them.

Canonical type hash stats for cc1plus build:

[WPA] GIMPLE canonical type table: size 16381, 1590 elements, 6797 searches, 88 collisions (ratio: 0.012947)
[WPA] GIMPLE canonical type pointer-map: 1590 elements, 15494 searches

to:

[WPA] GIMPLE canonical type table: size 16381, 755 elements, 6311 searches, 57 collisions (ratio: 0.009032)
[WPA] GIMPLE canonical type pointer-map: 755 elements, 15553 searches

So without patch there are 1590 distinct canonical types, with the patch there
are 755 non-ODR and 3317 odr types, about 2.5 times more.

And alias oracle stats for -flto-partition=none cc1plus build:

Alias oracle query stats:
  refs_may_alias_p: 39227004 disambiguations, 47344870 queries
  ref_maybe_used_by_call_p: 57815 disambiguations, 39808081 queries
  call_may_clobber_ref_p: 5511 disambiguations, 8287 queries
  aliasing_component_ref_p: 90654 disambiguations, 269895 queries
  TBAA oracle: 11130153 disambiguations 34368560 queries
               14199938 are in alias set 0
               5193428 queries asked about the same object
               147 queries asked about the same alias set
               0 access volatile
               1665979 are dependent in the DAG
               2178915 are aritificially in conflict with void *

PTA query stats:
  pt_solution_includes: 464074 disambiguations, 7105649 queries
  pt_solutions_intersect: 355139 disambiguations, 6952492 queries


Alias oracle query stats:
  refs_may_alias_p: 39682205 disambiguations, 47774305 queries
  ref_maybe_used_by_call_p: 58390 disambiguations, 40265537 queries
  call_may_clobber_ref_p: 5619 disambiguations, 8397 queries
  aliasing_component_ref_p: 61523 disambiguations, 240208 queries
  TBAA oracle: 11691755 disambiguations 34552651 queries
               14233568 are in alias set 0
               5230754 queries asked about the same object
               147 queries asked about the same alias set
               0 access volatile
               2433081 are dependent in the DAG
               963346 are aritificially in conflict with void *

PTA query stats:
  pt_solution_includes: 457871 disambiguations, 7044729 queries
  pt_solutions_intersect: 367701 disambiguations, 6859208 queries

So about 455k new disambiguations or 5% more TBAA ones.
It is about half of what PTA oracle stats shows, so it seems
reasibale improvement to me.

The patch results in about 1% cc1plus code size increase.
(mostly because of less ICF)

For tramp3d the stats are:

  refs_may_alias_p: 3252729 disambiguations, 3587196 queries
  ref_maybe_used_by_call_p: 7018 disambiguations, 3280028 queries
  call_may_clobber_ref_p: 883 disambiguations, 883 queries
  aliasing_component_ref_p: 549 disambiguations, 17885 queries
  TBAA oracle: 1644568 disambiguations 3261681 queries
               555812 are in alias set 0
               680883 queries asked about the same object
               0 queries asked about the same alias set
               0 access volatile
               248396 are dependent in the DAG
               132022 are aritificially in conflict with void *

PTA query stats:
  pt_solution_includes: 641563 disambiguations, 921034 queries
  pt_solutions_intersect: 115861 disambiguations, 501205 queries

Alias oracle query stats:
  refs_may_alias_p: 3016277 disambiguations, 3316301 queries
  ref_maybe_used_by_call_p: 7134 disambiguations, 3042055 queries
  call_may_clobber_ref_p: 817 disambiguations, 817 queries
  aliasing_component_ref_p: 495 disambiguations, 14565 queries
  TBAA oracle: 1416803 disambiguations 2911585 queries
               552489 are in alias set 0
               567158 queries asked about the same object
               0 queries asked about the same alias set
               0 access volatile
               259923 are dependent in the DAG
               115212 are aritificially in conflict with void *

PTA query stats:
  pt_solution_includes: 668779 disambiguations, 949986 queries
  pt_solutions_intersect: 96232 disambiguations, 436617 queries

About 7% difference. 

I did Firefox stats with earlier variant of this patch and difference was about 12%.
It takes about a day for lto1-ltrans with one partition to converge (and two
days for for gas) so I did not re-run it with final version.  Code size
difference is about 4%.

Notice also that access path oracle now suceeds less often since
we less often mix up unrealted types. In general with more precist
TBAA lookups the oracle should be bit cheaper by avoiding more complex
tests.

lto-bootstrapped/regtested x86_64-linux with all languages and also
tested on few extra C++ apps.

	* alias.c (record_component_aliases): Honor odr_based_tbaa_p.
	* ipa-devirt.c (odr_type_d): Add tbaa_enabled field.
	(get_odr_type): Return NULL when odr_type_hash is NULL.
	(enable_odr_based_tbaa): New function.
	(odr_based_tbaa_p): New function.
	(set_type_canonical_for_odr_type): New function.
	* ipa-utils.h (enable_odr_based_tbaa, odr_based_tbaa_p,
	set_type_canonical_for_odr_type): Declare.
	* lto-common.c: Update copyright; include tree-pretty-print.h.
	(types_to_register): New static var.
	(iterative_hash_canonical_type): Add new parameter INSERT.
	(hash_canonical_type): Likewise.
	(lookup_canonical_type): New function.
	(lto_register_canonical_types_for_odr_types): New.
	(odr_or_derived_type_p): New function.
	(lto_read_decls): Deffer ODR and ODR derived types
	to later canonical type calculation.
	* tree.c (gimple_canonical_types_compatible_p): Honnor
	odr_based_tbaa_p.
Index: alias.c
===================================================================
--- alias.c	(revision 271843)
+++ alias.c	(working copy)
@@ -1202,47 +1202,52 @@ record_component_aliases (tree type)
     case RECORD_TYPE:
     case UNION_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))
-	  {
-	    /* 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 (!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));
-	  }
+      {
+	/* LTO non-ODR 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.  */
+	bool void_pointers = in_lto_p
+			     && (!odr_type_p (type)
+				 || !odr_based_tbaa_p (type));
+	for (field = TYPE_FIELDS (type); field != 0; field = DECL_CHAIN (field))
+	  if (TREE_CODE (field) == FIELD_DECL && !DECL_NONADDRESSABLE_P (field))
+	    {
+	      tree t = TREE_TYPE (field);
+	      if (void_pointers)
+		{
+		  /* 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 (!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;
 
     case COMPLEX_TYPE:
Index: ipa-devirt.c
===================================================================
--- ipa-devirt.c	(revision 271843)
+++ ipa-devirt.c	(working copy)
@@ -213,6 +213,8 @@ struct GTY(()) odr_type_d
   bool odr_violated;
   /* Set when virtual table without RTTI previaled table with.  */
   bool rtti_broken;
+  /* Set when we need to give up on ODR based TBAA info.  */
+  bool tbaa_enabled;
 };
 
 /* Return TRUE if all derived types of T are known and thus
@@ -2045,6 +2047,9 @@ get_odr_type (tree type, bool insert)
   if (!in_lto_p && !TYPE_STRUCTURAL_EQUALITY_P (type))
     type = TYPE_CANONICAL (type);
 
+  if (!odr_hash)
+    return NULL;
+
   gcc_checking_assert (can_be_name_hashed_p (type)
 		       || can_be_vtable_hashed_p (type));
 
@@ -2182,6 +2187,45 @@ prevailing_odr_type (tree type)
   return t->type;
 }
 
+/* Set tbaa_enabled flag for TYPE.  */
+
+void
+enable_odr_based_tbaa (tree type)
+{
+  odr_type t = get_odr_type (type, true);
+  t->tbaa_enabled = true;
+}
+
+/* Return type that in ODR type hash prevailed TYPE.  Be careful and punt
+   on ODR violations.  */
+
+bool
+odr_based_tbaa_p (const_tree type)
+{
+  odr_type t = get_odr_type (const_cast <tree> (type), false);
+  if (!t || !t->tbaa_enabled)
+    return false;
+  return true;
+}
+
+/* Set TYPE_CANONICAL of type and all its variants and duplicates
+   to CANONICAL.  */
+
+void
+set_type_canonical_for_odr_type (tree type, tree canonical)
+{
+  odr_type t = get_odr_type (type, false);
+  unsigned int i;
+  tree tt;
+
+  for (tree t2 = t->type; t2; t2 = TYPE_NEXT_VARIANT (t2))
+    TYPE_CANONICAL (t2) = canonical;
+  if (t->types)
+    FOR_EACH_VEC_ELT (*t->types, i, tt)
+      for (tree t2 = tt; t2; t2 = TYPE_NEXT_VARIANT (t2))
+        TYPE_CANONICAL (t2) = canonical;
+}
+
 /* Return true if we reported some ODR violation on TYPE.  */
 
 bool
Index: ipa-utils.h
===================================================================
--- ipa-utils.h	(revision 271843)
+++ ipa-utils.h	(working copy)
@@ -93,6 +93,9 @@ bool odr_or_derived_type_p (const_tree t
 bool odr_types_equivalent_p (tree type1, tree type2);
 bool odr_type_violation_reported_p (tree type);
 tree prevailing_odr_type (tree type);
+void enable_odr_based_tbaa (tree type);
+bool odr_based_tbaa_p (const_tree type);
+void set_type_canonical_for_odr_type (tree type, tree canonical);
 
 /* Return vector containing possible targets of polymorphic call E.
    If COMPLETEP is non-NULL, store true if the list is complete. 
Index: lto/lto-common.c
===================================================================
--- lto/lto-common.c	(revision 271843)
+++ lto/lto-common.c	(working copy)
@@ -1,5 +1,5 @@
 /* Top-level LTO routines.
-   Copyright (C) 2009-2018 Free Software Foundation, Inc.
+   Copyright (C) 2009-2019 Free Software Foundation, Inc.
    Contributed by CodeSourcery, Inc.
 
 This file is part of GCC.
@@ -56,6 +56,7 @@ along with GCC; see the file COPYING3.
 #include "attribs.h"
 #include "builtins.h"
 #include "lto-common.h"
+#include "tree-pretty-print.h"
 
 GTY(()) tree first_personality_decl;
 
@@ -212,22 +213,26 @@ lto_read_in_decl_state (struct data_in *
 
 
 /* Global canonical type table.  */
+static GTY(()) vec<tree, va_gc> *types_to_register = NULL;
 static htab_t gimple_canonical_types;
 static hash_map<const_tree, hashval_t> *canonical_type_hash_cache;
 static unsigned long num_canonical_type_hash_entries;
 static unsigned long num_canonical_type_hash_queries;
 
-static void iterative_hash_canonical_type (tree type, inchash::hash &hstate);
+static void iterative_hash_canonical_type (tree type, inchash::hash &hstate, bool);
 static hashval_t gimple_canonical_type_hash (const void *p);
 static void gimple_register_canonical_type_1 (tree t, hashval_t hash);
 
 /* Returning a hash value for gimple type TYPE.
 
    The hash value returned is equal for types considered compatible
-   by gimple_canonical_types_compatible_p.  */
+   by gimple_canonical_types_compatible_p.
+ 
+   If INSERT is true, also populate canonical type hash by all
+   types TYPE is derived from.  */
 
 static hashval_t
-hash_canonical_type (tree type)
+hash_canonical_type (tree type, bool insert)
 {
   inchash::hash hstate;
   enum tree_code code;
@@ -293,7 +298,7 @@ hash_canonical_type (tree type)
   if (TREE_CODE (type) == ARRAY_TYPE
       || TREE_CODE (type) == COMPLEX_TYPE
       || TREE_CODE (type) == VECTOR_TYPE)
-    iterative_hash_canonical_type (TREE_TYPE (type), hstate);
+    iterative_hash_canonical_type (TREE_TYPE (type), hstate, insert);
 
   /* Incorporate function return and argument types.  */
   if (TREE_CODE (type) == FUNCTION_TYPE || TREE_CODE (type) == METHOD_TYPE)
@@ -301,11 +306,11 @@ hash_canonical_type (tree type)
       unsigned na;
       tree p;
 
-      iterative_hash_canonical_type (TREE_TYPE (type), hstate);
+      iterative_hash_canonical_type (TREE_TYPE (type), hstate, insert);
 
       for (p = TYPE_ARG_TYPES (type), na = 0; p; p = TREE_CHAIN (p))
 	{
-	  iterative_hash_canonical_type (TREE_VALUE (p), hstate);
+	  iterative_hash_canonical_type (TREE_VALUE (p), hstate, insert);
 	  na++;
 	}
 
@@ -322,7 +327,7 @@ hash_canonical_type (tree type)
 	    && (! DECL_SIZE (f)
 		|| ! integer_zerop (DECL_SIZE (f))))
 	  {
-	    iterative_hash_canonical_type (TREE_TYPE (f), hstate);
+	    iterative_hash_canonical_type (TREE_TYPE (f), hstate, insert);
 	    nf++;
 	  }
 
@@ -332,10 +337,11 @@ hash_canonical_type (tree type)
   return hstate.end();
 }
 
-/* Returning a hash value for gimple type TYPE combined with VAL.  */
+/* Returning a hash value for gimple type TYPE combined with VAL.
+   If INSERT is true possibly insert TYPE to canonical type hash.  */
 
 static void
-iterative_hash_canonical_type (tree type, inchash::hash &hstate)
+iterative_hash_canonical_type (tree type, inchash::hash &hstate, bool insert)
 {
   hashval_t v;
 
@@ -343,7 +349,7 @@ iterative_hash_canonical_type (tree type
   type = TYPE_MAIN_VARIANT (type);
 
   if (!canonical_type_used_p (type))
-    v = hash_canonical_type (type);
+    v = hash_canonical_type (type, insert);
   /* An already processed type.  */
   else if (TYPE_CANONICAL (type))
     {
@@ -355,9 +361,11 @@ iterative_hash_canonical_type (tree type
       /* Canonical types should not be able to form SCCs by design, this
 	 recursion is just because we do not register canonical types in
 	 optimal order.  To avoid quadratic behavior also register the
-	 type here.  */
-      v = hash_canonical_type (type);
-      gimple_register_canonical_type_1 (type, v);
+	 type here.  Do not assign canonical types to ODR types - this
+	 is done later using ODR name hash.  */
+      v = hash_canonical_type (type, insert);
+      if (insert)
+        gimple_register_canonical_type_1 (type, v);
     }
   hstate.add_int (v);
 }
@@ -437,12 +445,26 @@ gimple_register_canonical_type (tree t)
     TYPE_CANONICAL (t) = TYPE_CANONICAL (TYPE_MAIN_VARIANT (t));
   else
     {
-      hashval_t h = hash_canonical_type (TYPE_MAIN_VARIANT (t));
+      hashval_t h = hash_canonical_type (TYPE_MAIN_VARIANT (t), true);
       gimple_register_canonical_type_1 (TYPE_MAIN_VARIANT (t), h);
       TYPE_CANONICAL (t) = TYPE_CANONICAL (TYPE_MAIN_VARIANT (t));
     }
 }
 
+/* See if structurally equivalent type to T is in the canonical type hash and
+   return it.  Return NULL otherwise.
+   No changes to canonical hash are made during the lookup.  */
+
+static tree
+lookup_canonical_type (tree t)
+{
+  hashval_t h = hash_canonical_type (TYPE_MAIN_VARIANT (t), false);
+  void **slot = htab_find_slot_with_hash (gimple_canonical_types, t, h, NO_INSERT);
+  if (!slot)
+    return NULL;
+  return (tree)(*slot);
+}
+
 /* Re-compute TYPE_CANONICAL for NODE and related types.  */
 
 static void
@@ -464,6 +486,107 @@ lto_register_canonical_types (tree node,
     gimple_register_canonical_type (node);
 }
 
+/* Finish canonical type calculation: after all units has been streamed in we
+   can check if given ODR type structurally conflicts with a non-ODR type.  In
+   the first case we set type canonical according to the canonical type hash.
+   In the second case we use type names.  */
+
+static void
+lto_register_canonical_types_for_odr_types ()
+{
+  tree t;
+  unsigned int i;
+
+  if (!types_to_register)
+    return;
+
+  /* Be sure that no types derived from ODR types was
+     not inserted into the hash table.  */
+  if (flag_checking)
+    FOR_EACH_VEC_ELT (*types_to_register, i, t)
+      gcc_assert (!TYPE_CANONICAL (t));
+
+  FOR_EACH_VEC_ELT (*types_to_register, i, t)
+    if (odr_type_p (t) && !TYPE_CANONICAL (t))
+      {
+	/* Punt on ODR violations - if there are structurally different
+	   types of the same name we are better to not try too hard to
+	   use TBAA.  */
+	if (odr_type_violation_reported_p (t))
+	  {
+	    if (symtab->dump_file)
+	      {
+		fprintf (symtab->dump_file,
+			 "Disabling ODR TBAA because of ODR violation: ");
+		print_generic_expr (symtab->dump_file, t);
+		fprintf (symtab->dump_file, "\n");
+	      }
+	  }
+	else
+	  {
+	    tree nonodr = type_in_anonymous_namespace_p (t)
+			  ? NULL : lookup_canonical_type (t);
+
+	    /* If there is non-ODR type matching T, use its canonical
+	       type.  We can still propagate it to all variants of T
+	       including incomplete ones.  */
+	    if (nonodr)
+	      {
+		gcc_checking_assert (!odr_type_p (nonodr));
+		if (symtab->dump_file)
+		  {
+		    fprintf (symtab->dump_file,
+			     "ODR and non-ODR type conflict: ");
+		    print_generic_expr (symtab->dump_file, t);
+		    fprintf (symtab->dump_file, " and ");
+		    print_generic_expr (symtab->dump_file, nonodr);
+		    fprintf (symtab->dump_file, "\n");
+		  }
+		set_type_canonical_for_odr_type (t, nonodr);
+	      }
+	    else
+	      {
+		if (symtab->dump_file)
+		  {
+		    fprintf (symtab->dump_file,
+			     "New canonical ODR type: ");
+		    print_generic_expr (symtab->dump_file, t);
+		    fprintf (symtab->dump_file, "\n");
+		  }
+
+		tree prevail = prevailing_odr_type (t);
+		gcc_checking_assert (TYPE_CANONICAL (prevail) == NULL);
+
+		/* Populate canonical type hash with type name.  */
+		bool existed = canonical_type_hash_cache->put
+		 		 (prevail,
+				  htab_hash_string
+				    (IDENTIFIER_POINTER
+				       (DECL_ASSEMBLER_NAME
+				         (TYPE_NAME (prevail)))));
+		gcc_assert (!existed);
+		/* Set TYPE_CANONICAL for all variants and duplicates of T
+		   including incompete ones.  */
+		set_type_canonical_for_odr_type (t, prevail);
+		/* And inform gimple_canonical_types_compatible_p that
+		   it should rely on TYPE_CANONICAL compares only.  */
+		enable_odr_based_tbaa (t);
+		gcc_checking_assert (TYPE_CANONICAL (t) = prevail);
+	      }
+	  }
+      }
+
+  /* Now compute canonical types for all ODR derived types.  */
+  FOR_EACH_VEC_ELT (*types_to_register, i, t)
+    if (!TYPE_CANONICAL (t))
+      {
+        gimple_register_canonical_type (t);
+	/* We store only main variants; propagate info to all variants.  */
+	for (tree t2 = TYPE_NEXT_VARIANT (t); t2; t2 = TYPE_NEXT_VARIANT (t2))
+	  TYPE_CANONICAL (t2) = TYPE_CANONICAL (t);
+      }
+}
+
 
 /* Remember trees that contains references to declarations.  */
 vec <tree, va_gc> *tree_with_vars;
@@ -1655,6 +1778,33 @@ unify_scc (struct data_in *data_in, unsi
 }
 
 
+/* TYPE is expected to be record or union.  Figure out if it is an ODR
+   type or derived from it.  This is intended to be used only from
+   stream in process and rely on fact that all types with TYPE_CANONICAL
+   set are not ODR derived.  This reducts most of recursive lookups.  */
+
+static bool
+odr_or_derived_type_p (tree type)
+{
+  if (TYPE_CANONICAL (type))
+    return false;
+  if (odr_type_p (TYPE_MAIN_VARIANT (type))
+      || (TYPE_CONTEXT (type)
+	  && TYPE_P (TYPE_CONTEXT (type))
+	  && odr_type_p (TYPE_CONTEXT (type))))
+    return true;
+  for (tree f = TYPE_FIELDS (type); f; f = TREE_CHAIN (f))
+    {
+      tree t = TREE_TYPE (f);
+      while (TREE_CODE (t) == ARRAY_TYPE)
+	t = TREE_TYPE (t);
+      if (RECORD_OR_UNION_TYPE_P (t)
+	  && odr_or_derived_type_p (t))
+	return true;
+    }
+  return false;
+}
+
 /* Read all the symbols from buffer DATA, using descriptors in DECL_DATA.
    RESOLUTIONS is the set of symbols picked by the linker (read from the
    resolution file when the linker plugin is being used).  */
@@ -1747,12 +1897,24 @@ lto_read_decls (struct lto_file_decl_dat
 		  num_prevailing_types++;
 		  lto_fixup_prevailing_type (t);
 
-		  /* Compute the canonical type of all types.
+		  /* Compute the canonical type of all non-ODR types.
+		     Delay ODR types for the end of merging process - the canonical
+		     type for those can be computed using the (unique) name however
+		     we want to do this only if units in other languages do not
+		     contain structurally equivalent type.
+
 		     Because SCC components are streamed in random (hash) order
 		     we may have encountered the type before while registering
 		     type canonical of a derived type in the same SCC.  */
 		  if (!TYPE_CANONICAL (t))
-		    gimple_register_canonical_type (t);
+		    {
+		      if (!RECORD_OR_UNION_TYPE_P (t)
+			  || !odr_or_derived_type_p (t))
+		        gimple_register_canonical_type (t);
+		      else if (COMPLETE_TYPE_P (t)
+			       && TYPE_MAIN_VARIANT (t) == t)
+			vec_safe_push (types_to_register, t);
+		    }
 		  if (TYPE_MAIN_VARIANT (t) == t && odr_type_p (t))
 		    register_odr_type (t);
 		}
@@ -2602,6 +2764,8 @@ read_cgraph_and_symbols (unsigned nfiles
   ggc_free(decl_data);
   real_file_decl_data = NULL;
 
+  lto_register_canonical_types_for_odr_types ();
+
   if (resolution_file_name)
     fclose (resolution);
 
Index: testsuite/g++.dg/lto/alias-2_0.C
===================================================================
--- testsuite/g++.dg/lto/alias-2_0.C	(nonexistent)
+++ testsuite/g++.dg/lto/alias-2_0.C	(working copy)
@@ -0,0 +1,31 @@
+/* { dg-lto-do run } */
+/* { dg-lto-options { { -O2 -flto } } } */
+
+/* With LTO we consider all pointers to incomplete types to be possibly
+   aliasing.  This makes *bptr to alias with aptr.
+   For C++ ODR types we however can work out that they are actually
+   different.  */
+
+#include <string.h>
+
+typedef int (*fnptr) ();
+
+__attribute__ ((used))
+struct a *aptr;
+
+__attribute__ ((used))
+struct b **bptr = (struct b**)&aptr;
+extern void init ();
+extern void inline_me_late (int);
+
+
+int
+main (int argc, char **argv)
+{
+  init ();
+  aptr = 0;
+  inline_me_late (argc);
+  if (!__builtin_constant_p (aptr == 0))
+    __builtin_abort ();
+  return (size_t)aptr;
+}
Index: testsuite/g++.dg/lto/alias-2_1.C
===================================================================
--- testsuite/g++.dg/lto/alias-2_1.C	(nonexistent)
+++ testsuite/g++.dg/lto/alias-2_1.C	(working copy)
@@ -0,0 +1,16 @@
+#include <string.h>
+struct a {int a;} a;
+struct b {int b;} b;
+extern struct b **bptr;
+void
+inline_me_late (int argc)
+{
+  if (argc == -1)
+    *bptr = (struct b *)(size_t)1;
+}
+void
+init()
+{
+  a.a=1;
+  b.b=2;
+}
Index: tree.c
===================================================================
--- tree.c	(revision 271843)
+++ tree.c	(working copy)
@@ -14083,6 +14083,7 @@ gimple_canonical_types_compatible_p (con
 
   gcc_assert (!trust_type_canonical
 	      || (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.  */
 
@@ -14100,6 +14101,14 @@ gimple_canonical_types_compatible_p (con
       return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
     }
 
+  /* For types where we do ODR based TBAA the canonical type is always
+     set correctly, so we know that types are different if their
+     canonical types does not match.  */
+  if (trust_type_canonical
+      && (odr_type_p (t1) && odr_based_tbaa_p (t1))
+	  != (odr_type_p (t2) && odr_based_tbaa_p (t2)))
+    return false;
+
   /* 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));
   if (code != tree_code_for_canonical_type_merging (TREE_CODE (t2)))

^ permalink raw reply	[flat|nested] 50+ messages in thread

end of thread, other threads:[~2019-07-23 11:23 UTC | newest]

Thread overview: 50+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-06-03 13:30 Use ODR for canonical types construction in LTO Jan Hubicka
2019-06-14  9:49 ` Jan Hubicka
2019-06-14 11:06 ` Richard Biener
2019-06-14 11:23   ` Jan Hubicka
2019-06-16 20:04   ` Jan Hubicka
2019-06-24 10:45     ` Jan Hubicka
2019-06-24 13:42       ` Richard Biener
2019-06-25  8:17     ` Eric Botcazou
2019-06-25  8:20       ` Jan Hubicka
2019-06-25 12:29         ` Christophe Lyon
2019-06-27  2:26           ` JiangNing OS
2019-06-27  6:29             ` Jan Hubicka
2019-06-27 13:47               ` JiangNing OS
2019-07-01 12:22           ` Jan Hubicka
2019-07-02  2:14             ` JiangNing OS
2019-06-18 16:10   ` Jan Hubicka
2019-06-19  8:59     ` Jan Hubicka
2019-06-19  9:47       ` Jan Hubicka
2019-06-19 13:28         ` Jan Hubicka
2019-06-19 14:24           ` Nathan Sidwell
2019-06-19 17:53             ` Jan Hubicka
2019-06-19 18:47               ` Nathan Sidwell
2019-06-20  4:34                 ` Jason Merrill
2019-06-20 11:01                   ` Nathan Sidwell
2019-06-20 13:37                   ` Richard Biener
2019-06-20 13:52                     ` Jan Hubicka
2019-06-20 14:07                     ` Nathan Sidwell
2019-06-20 15:49                       ` Richard Biener
2019-06-20 17:17                         ` Nathan Sidwell
2019-06-24 10:51                     ` Jan Hubicka
2019-06-24 11:28                       ` Richard Biener
2019-06-24 11:39                         ` Jan Hubicka
2019-06-24 14:52                         ` Jason Merrill
2019-06-24 15:57                           ` Jan Hubicka
2019-06-24 16:40                             ` Jason Merrill
2019-06-24 16:56                               ` Jason Merrill
2019-06-24 17:23                                 ` Richard Biener
2019-06-24 17:42                                   ` Jason Merrill
2019-06-24 17:46                               ` Jan Hubicka
2019-06-27 18:00                                 ` Jason Merrill
2019-06-27  9:44                         ` Jan Hubicka
2019-06-27 10:25                           ` Richard Biener
2019-06-27 10:45                             ` Jan Hubicka
2019-06-27 10:48                               ` Richard Biener
2019-06-27 10:49                                 ` Jan Hubicka
2019-06-27 11:05                                 ` Jan Hubicka
2019-06-27 11:16                                   ` Richard Biener
2019-06-27 11:40                                     ` Jan Hubicka
2019-06-20 12:38                 ` Jan Hubicka
2019-07-23 11:55 ` Martin Liška

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).