This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[lto] Merge types read from different TUs


This patch adds a type merging phase to the streamer.  When the
same type is read from two different files, it is instantiated as
two type objects T1 and T2.

This is wasteful and it also can cause problems during
optimization because T1 and T2 may both receive different alias
sets, which causes us to think that they are not compatible.  In
the testcase included with the patch, it was causing an assertion
in PRE to trigger.

The idea is to introduce a global type table hashed by type
compatibility.  When a new type T is registered, the table is
scanned for an existing type that is compatible with T.  If we
find a T' compatible with T, then T' is used, otherwise, T is
registered as a new gimple type.

This allows us to merge types from all TUs in a link set so that
the rest of the compiler can keep using pointer equivalence as
the basic compatibility test.  This also helps aliasing not give
out two different alias sets for the same type.

The hashing function is not ideal, as it produces many clashes.
We'll have to iterate over it a couple more times.  I've added
statistics on it to -flto-report.

The patch also adds pretty printing for FUNCTION_TYPE and
METHOD_TYPE and fixes a bug in gimple_compare_types for types
with different addressability settings.

Bootstrapped and tested on x86_64.


Diego.

2009-03-16  Diego Novillo  <dnovillo@google.com>

	* tree-pretty-print.c (dump_generic_node): Merge handler
	for METHOD_TYPE and FUNCTION_TYPE.  Dump type arguments.
	* gimple.c (gimple_compare_types): Do not test
	TYPE_MAIN_VARIANT.
	if T1 and T2 have different addressability, consider them
	different.

2009-03-15  Diego Novillo  <dnovillo@google.com>
            Simon Baldwin  <simonb@google.com>

	* gimple.c (gimple_types): New.
	(gimple_type_hash): New.
	(gimple_type_eq): New.
	(gimple_register_type): New.
	(print_gimple_types_stats): New.
	* gimple.h (gimple_register_type): Declare.
	(print_gimple_types_stats): Declare.
	* lto-utils.c: Include gimple.h.
	(print_lto_report): Call print_gimple_stats.
	* Makefile.in (lto-utils.o): Add dependency on GIMPLE_H.

lto/ChangeLog

	* lto.c: Include gimple.h.
	(lto_read_in_decl_state): Call gimple_register_type for
	every type in every stream.
	(lto_fixup_common): Call gimple_register_type if T has a
	type.
	* Make-lang.in (lto.o): Add dependency on GIMPLE_H.

2009-03-16  Simon Baldwin  <simonb@google.com>

	* g++.dg/lto/20090315_0.C:
	* g++.dg/lto/20090315_1.C:

Index: tree-pretty-print.c
===================================================================
--- tree-pretty-print.c	(revision 144872)
+++ tree-pretty-print.c	(working copy)
@@ -618,14 +618,6 @@ dump_generic_node (pretty_printer *buffe
       NIY;
       break;
 
-    case METHOD_TYPE:
-      if (TYPE_METHOD_BASETYPE (node))
-        dump_decl_name (buffer, TYPE_NAME (TYPE_METHOD_BASETYPE (node)), flags);
-      else
-        pp_string (buffer, "<null method basetype>");
-      pp_string (buffer, "::");
-      break;
-
     case TARGET_MEM_REF:
       {
 	const char *sep = "";
@@ -850,6 +842,23 @@ dump_generic_node (pretty_printer *buffe
       break;
 
     case FUNCTION_TYPE:
+    case METHOD_TYPE:
+      dump_generic_node (buffer, TREE_TYPE (node), spc, flags, false);
+      pp_space (buffer);
+      if (TREE_CODE (node) == METHOD_TYPE)
+	{
+	  if (TYPE_METHOD_BASETYPE (node))
+	    dump_decl_name (buffer, TYPE_NAME (TYPE_METHOD_BASETYPE (node)),
+			    flags);
+	  else
+	    pp_string (buffer, "<null method basetype>");
+	  pp_string (buffer, "::");
+	}
+      if (TYPE_NAME (node) && DECL_NAME (TYPE_NAME (node)))
+	dump_decl_name (buffer, TYPE_NAME (node), flags);
+      else
+	pp_printf (buffer, "<T%x>", TYPE_UID (node));
+      dump_function_declaration (buffer, node, spc, flags);
       break;
 
     case FUNCTION_DECL:
Index: testsuite/g++.dg/lto/20090315_0.C
===================================================================
--- testsuite/g++.dg/lto/20090315_0.C	(revision 0)
+++ testsuite/g++.dg/lto/20090315_0.C	(revision 0)
@@ -0,0 +1,9 @@
+// { dg-do run }
+struct Foo {
+  bool Mumble() { return true; }
+  static void Bar() { if (foo_->Mumble()) foo_ = 0; }
+  static void Baz() { Bar(); }
+  static Foo *foo_;
+};
+Foo *Foo::foo_;
+main() { return 0; }
Index: testsuite/g++.dg/lto/20090315_1.C
===================================================================
--- testsuite/g++.dg/lto/20090315_1.C	(revision 0)
+++ testsuite/g++.dg/lto/20090315_1.C	(revision 0)
@@ -0,0 +1,7 @@
+struct Foo {
+  bool Mumble() { return true; }
+  static void Bar() { if (foo_->Mumble()) foo_ = 0; }
+  static void Baz() { Bar(); }
+  static Foo *foo_;
+};
+void Unused() { Foo::Bar(); Foo::Baz(); }
Index: lto/lto.c
===================================================================
--- lto/lto.c	(revision 144872)
+++ lto/lto.c	(working copy)
@@ -48,6 +48,7 @@ Boston, MA 02110-1301, USA.  */
 #include "ipa-prop.h"
 #include "common.h"
 #include "timevar.h"
+#include "gimple.h"
 
 /* This needs to be included after config.h.  Otherwise, _GNU_SOURCE will not
    be defined in time to set __USE_GNU in the system headers, and strsignal
@@ -201,7 +202,15 @@ lto_read_in_decl_state (struct data_in *
       tree *decls = (tree *) xcalloc (size, sizeof (tree));
 
       for (j = 0; j < size; j++)
-        decls[j] = VEC_index (tree, data_in->globals_index, data[j]);
+	{
+	  decls[j] = VEC_index (tree, data_in->globals_index, data[j]);
+
+	  /* Register every type in the global type table.  If the
+	     type existed already, use the existing type.  */
+	  if (TYPE_P (decls[j]))
+	    decls[j] = gimple_register_type (decls[j]);
+	}
+
       state->streams[i].size = size;
       state->streams[i].trees = decls;
       data += size;
@@ -1071,6 +1080,11 @@ no_fixup_p (tree t)
 static void
 lto_fixup_common (tree t, void *data)
 {
+  /* If T has a type, make sure it is registered in the global type
+     table.  If the type existed already, use the existing one.  */
+  if (TREE_TYPE (t))
+    TREE_TYPE (t) = gimple_register_type (TREE_TYPE (t));
+
   LTO_FIXUP_SUBTREE (TREE_TYPE (t));
   /* This is not very efficient because we cannot do tail-recursion with
      a long chain of trees. */
Index: lto/Make-lang.in
===================================================================
--- lto/Make-lang.in	(revision 144872)
+++ lto/Make-lang.in	(working copy)
@@ -97,7 +97,7 @@ lto/lto.o: lto/lto.c $(CONFIG_H) $(CGRAP
 	$(LTO_TREE_H) dwarf2out.h tree-ssa-operands.h gt-lto-lto.h \
 	lto-section.h $(LTO_SECTION_IN_H) tree-pass.h $(LTO_SECTION_OUT_H) \
 	pointer-set.h vec.h $(BITMAP_H) $(IPA_PROP_H) lto/common.h \
-	diagnostic.h lto-utils.h timevar.h lto-opts.h
+	diagnostic.h lto-utils.h timevar.h lto-opts.h $(GIMPLE_H)
 lto/lto-elf.o: lto/lto-elf.c $(CONFIG_H) coretypes.h $(SYSTEM_H) \
 	toplev.h $(LTO_H) $(TM_H)
 lto/common.o: lto/common.h
Index: Makefile.in
===================================================================
--- Makefile.in	(revision 144872)
+++ Makefile.in	(working copy)
@@ -2119,7 +2119,8 @@ lto-opts.o: lto-opts.c $(CONFIG_H) $(SYS
    $(TARGET_H) $(TOPLEV_H) $(LTO_SECTION_OUT_H) $(LTO_SECTION_IN_H) \
    lto-utils.h $(LTO_OPTS_H)
 lto-utils.o: lto-utils.c $(CONFIG_H) $(SYSTEM_H) coretypes.h   \
-   $(TM_H) $(TREE_H) $(BITMAP_H) vec.h lto-header.h lto-utils.h
+   $(TM_H) $(TREE_H) $(BITMAP_H) vec.h lto-header.h lto-utils.h \
+   $(GIMPLE_H)
 lto-wpa-fixup.o: lto-wpa-fixup.c $(CONFIG_H) $(SYSTEM_H) coretypes.h   \
    $(TM_H) $(TOPLEV_H) $(TREE_H) $(EXPR_H) $(FLAGS_H) tree-pass.h \
    $(CGRAPH_H) $(FUNCTION_H) $(DIAGNOSTIC_H) vec.h $(BITMAP_H) $(TIMEVAR_H) \
Index: gimple.c
===================================================================
--- gimple.c	(revision 144872)
+++ gimple.c	(working copy)
@@ -34,6 +34,9 @@ along with GCC; see the file COPYING3.  
 #include "value-prof.h"
 #include "flags.h"
 
+/* Global type table.  */
+static htab_t gimple_types;
+
 #define DEFGSCODE(SYM, NAME, STRUCT)	NAME,
 const char *const gimple_code_name[] = {
 #include "gimple.def"
@@ -3324,8 +3327,7 @@ gimple_compare_types (tree t1, tree t2, 
   type_pair_t p = NULL;
 
   /* Check first for the obvious case of pointer identity.  */
-  if (t1 == t2
-      || TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2))
+  if (t1 == t2)
     goto same_types;
 
   /* Check that we have two types to compare.  */
@@ -3344,6 +3346,10 @@ gimple_compare_types (tree t1, tree t2, 
   if (TYPE_QUALS (t1) != TYPE_QUALS (t2))
     goto different_types;
 
+  /* Can't be the same type if they have different addressability.  */
+  if (TREE_ADDRESSABLE (t1) != TREE_ADDRESSABLE (t2))
+    goto different_types;
+
   /* If we've visited this type pair before (in the case of aggregates
      with self-referntial types), and we made a decision, return it.  */
   p = lookup_type_pair (t1, t2, visited_p);
@@ -3643,5 +3649,89 @@ gimple_types_compatible_p (tree t1, tree
 
   return same_p;
 }
-  
+
+
+/* Returns a hash value for P (assumed to be a type).  The hash value
+   is computed using some distinguishing features of the type.  Note
+   that we cannot use pointer hashing here as we may be dealing with
+   two distinct instances of the same type.  */
+
+static hashval_t
+gimple_type_hash (const void *p)
+{
+  hashval_t v;
+  const_tree type = (const_tree) p;
+
+  /* Combine a few common features of types so that types are grouped into
+     smaller sets; when searching for existing matching types to merge,
+     only existing types having the same features as the new type will be
+     checked.  */
+  if (TYPE_SIZE (type) != NULL_TREE)
+    v = (hashval_t) (int_cst_value (TYPE_SIZE (type)) * NUM_TREE_CODES
+	             + TREE_CODE (type));
+  else
+    v = (hashval_t) TREE_CODE (type);
+
+  /* For pointer and reference types, fold in information about the type
+     pointed to.  This helps to stop all pointers and references returning
+     the same bucket.  */
+  if (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE)
+    {
+      v <<= sizeof (v) * (CHAR_BIT >> 1);
+      v ^= gimple_type_hash (TREE_TYPE (type));
+    }
+
+  return v;
+}
+
+
+/* Returns nonzero if P1 and P2 are equal.  */
+
+static int
+gimple_type_eq (const void *p1, const void *p2)
+{
+  const_tree t1 = (const_tree) p1;
+  const_tree t2 = (const_tree) p2;
+  return gimple_types_compatible_p (CONST_CAST_TREE (t1), CONST_CAST_TREE (t2));
+}
+
+
+/* Register type T in the global type table gimple_types.
+   
+   If another type T', compatible with T, already existed in
+   gimple_types then return T', otherwise return T.  This is used by
+   LTO to merge identical types read from different TUs.  */
+
+tree
+gimple_register_type (tree t)
+{
+  void **slot;
+
+  if (gimple_types == NULL)
+    gimple_types = htab_create (1001, gimple_type_hash, gimple_type_eq, 0);
+
+  slot = htab_find_slot (gimple_types, t, INSERT);
+  if (*slot)
+    t = (tree) *((tree *) slot);
+  else
+    *slot = (void *) t;
+
+  return t;
+}
+
+
+/* Show statistics on references to the global type table gimple_types.  */
+
+void
+print_gimple_types_stats (void)
+{
+  fprintf (stderr, "GIMPLE type table: size %ld, %ld elements, "
+	   "%ld searches, %ld collisions (%d%%)\n",
+	   (long) htab_size (gimple_types),
+	   (long) htab_elements (gimple_types),
+	   (long) gimple_types->searches,
+	   (long) gimple_types->collisions,
+	   (int) (htab_collisions (gimple_types) * 100));
+}
+
 #include "gt-gimple.h"
Index: gimple.h
===================================================================
--- gimple.h	(revision 144872)
+++ gimple.h	(working copy)
@@ -916,6 +916,8 @@ extern tree get_call_expr_in (tree t);
 
 extern void recalculate_side_effects (tree);
 extern int gimple_types_compatible_p (tree, tree);
+extern tree gimple_register_type (tree);
+extern void print_gimple_types_stats (void);
 
 /* In gimplify.c  */
 extern tree create_tmp_var_raw (tree, const char *);
Index: lto-utils.c
===================================================================
--- lto-utils.c	(revision 144872)
+++ lto-utils.c	(working copy)
@@ -26,6 +26,7 @@ Boston, MA 02110-1301, USA.  */
 #include "coretypes.h"
 #include "tm.h"
 #include "tree.h"
+#include "gimple.h"
 #include "bitmap.h"
 #include "vec.h"
 #include "lto-header.h"
@@ -153,6 +154,9 @@ print_lto_report (void)
 	   HOST_WIDE_INT_PRINT_UNSIGNED "\n", s,
 	   lto_stats.num_function_bodies);
 
+  fprintf (stderr, "[%s] ", s);
+  print_gimple_types_stats ();
+
   for (i = 0; i < NUM_TREE_CODES; i++)
     if (lto_stats.num_trees[i])
       fprintf (stderr, "[%s] # of '%s' objects read: "


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]