PATCH RFA: Increase support for restrict qualifier

[Ian Lance Taylor <ian at airs dot com>]

Daniel Berlin <dberlin@dberlin.org> writes:

> First, i'd rather see this named something that implies it's only used
> for restrict.  Otherwise, people are going to start using it for other
> things (the other possible uses i can think of, which possibly include
> debug info, are already taken care of by DECL_VALUE_EXPR and
> DECL_DEBUG_EXPR).
> 
> second, how often does this actually set anything useful with restrict
> types (I assume the value is not interesting in any other cases)?
> 
> ISTM you'd be better off doing what we do with DECL_VALUE_EXPR,
> DECL_DEBUG_EXPR, and DECL_INIT_PRIORITY, which is to use 1 bit to say
> whether it has an "underlying nonscalar decl", and a side hashtable to
> store the actual value.
> 
> I say this because I imagine the number of DECL's which are restrict
> qualified, and thus, should have an underlying nonscalar-decl, is very
> small, and yet, you've added a field that is there for *all* decl's with
> rtl attached to them.
> 
> This would also solve your field-decl problem, since you could throw the
> bit in the common part.

Thanks for the suggestions.  I modified the patch to work along those
lines.  There has been one report of positive effects.  The cost of
this reworked patch should be reasonably low: basically a call to
walk_tree for each temporary variable based on an expression, where
the expression is generally going to be very simple.

Tested with a bootstrap and testsuite run on i686-pc-linux-gnu.

OK for mainline?

Ian


2005-09-27  Ian Lance Taylor  <ian@airs.com>

	* gimplify.c (struct find_decl): Define.
	(find_single_nonscalar_decl_1): New static function.
	(find_single_nonscalar_decl): New static function.
	(internal_get_tmp_var): For a formal variable, set restrict base
	information if appropriate.
	* alias.c (find_base_decl): If a VAR_DECL has a restrict base,
	return it.
	* tree.h (DECL_BASED_ON_RESTRICT_P): Define.
	(DECL_GET_RESTRICT_BASE): Define.
	(SET_DECL_RESTRICT_BASE): Define.
	(decl_restrict_base_lookup): Declare.
	(decl_restrict_base_insert): Declare.
	(struct tree_decl_with_vis): Add based_on_restrict_p field.
	* tree.c (restrict_base_for_decl): New static variable.
	(init_ttree): Initialize restrict_base_for_decl.
	(copy_node_stat): Copy restrict base information.
	(decl_restrict_base_lookup): New function.
	(decl_restrict_base_insert): New function.
	(print_restrict_base_statistics): New static function.
	(dump_tree_statistics): Call print_restrict_base_statistics.


Index: alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/alias.c,v
retrieving revision 1.254
diff -p -u -r1.254 alias.c
--- alias.c	21 Jul 2005 22:34:33 -0000	1.254
+++ alias.c	28 Sep 2005 04:29:13 -0000
@@ -395,9 +395,14 @@ find_base_decl (tree t)
   if (t == 0 || t == error_mark_node || ! POINTER_TYPE_P (TREE_TYPE (t)))
     return 0;
 
-  /* If this is a declaration, return it.  */
+  /* If this is a declaration, return it.  If T is based on a restrict
+     qualified decl, return that decl.  */
   if (DECL_P (t))
-    return t;
+    {
+      if (TREE_CODE (t) == VAR_DECL && DECL_BASED_ON_RESTRICT_P (t))
+	t = DECL_GET_RESTRICT_BASE (t);
+      return t;
+    }
 
   /* Handle general expressions.  It would be nice to deal with
      COMPONENT_REFs here.  If we could tell that `a' and `b' were the
Index: gimplify.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gimplify.c,v
retrieving revision 2.154
diff -p -u -r2.154 gimplify.c
--- gimplify.c	24 Sep 2005 16:21:43 -0000	2.154
+++ gimplify.c	28 Sep 2005 04:29:14 -0000
@@ -298,6 +298,46 @@ create_artificial_label (void)
   return lab;
 }
 
+/* Subroutine for find_single_nonscalar_decl.  */
+
+struct find_decl
+{
+  int c;
+  tree decl;
+};
+
+static tree
+find_single_nonscalar_decl_1 (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
+			       void *data)
+{
+  struct find_decl *pfd = (struct find_decl *) data;
+
+  if (DECL_P (*tp)
+      && !INTEGRAL_TYPE_P (TREE_TYPE (*tp))
+      && !SCALAR_FLOAT_TYPE_P (TREE_TYPE (*tp)))
+    {
+      ++pfd->c;
+      pfd->decl = *tp;
+    }
+
+  return NULL_TREE;
+}
+
+/* Find the single DECL of non-scalar type in the tree T and return
+   it.  If there are zero or more than one such DECLs, return
+   NULL.  */
+
+static tree
+find_single_nonscalar_decl (tree t)
+{
+  struct find_decl fd;
+
+  fd.c = 0;
+  fd.decl = NULL_TREE;
+  walk_tree (&t, find_single_nonscalar_decl_1, &fd, NULL);
+  return fd.c == 1 ? fd.decl : NULL_TREE;
+}
+
 /* Create a new temporary name with PREFIX.  Returns an identifier.  */
 
 static GTY(()) unsigned int tmp_var_id_num;
@@ -470,6 +510,24 @@ internal_get_tmp_var (tree val, tree *pr
 
   t = lookup_tmp_var (val, is_formal);
 
+  if (is_formal)
+    {
+      tree u = find_single_nonscalar_decl (val);
+
+      if (u && TREE_CODE (u) == VAR_DECL && DECL_BASED_ON_RESTRICT_P (u))
+	u = DECL_GET_RESTRICT_BASE (u);
+      if (u && TYPE_RESTRICT (TREE_TYPE (u)))
+	{
+	  if (DECL_BASED_ON_RESTRICT_P (t))
+	    gcc_assert (u == DECL_GET_RESTRICT_BASE (t));
+	  else
+	    {
+	      DECL_BASED_ON_RESTRICT_P (t) = 1;
+	      SET_DECL_RESTRICT_BASE (t, u);
+	    }
+	}
+    }
+
   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE)
     DECL_COMPLEX_GIMPLE_REG_P (t) = 1;
 
Index: tree.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.c,v
retrieving revision 1.505
diff -p -u -r1.505 tree.c
--- tree.c	14 Sep 2005 15:04:56 -0000	1.505
+++ tree.c	28 Sep 2005 04:29:15 -0000
@@ -144,6 +144,9 @@ static GTY ((if_marked ("tree_map_marked
 static GTY ((if_marked ("tree_int_map_marked_p"), param_is (struct tree_int_map)))
   htab_t init_priority_for_decl;
 
+static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
+  htab_t restrict_base_for_decl;
+
 struct tree_int_map GTY(())
 {
   tree from;
@@ -187,6 +190,8 @@ init_ttree (void)
 					 tree_map_eq, 0);
   init_priority_for_decl = htab_create_ggc (512, tree_int_map_hash,
 					    tree_int_map_eq, 0);
+  restrict_base_for_decl = htab_create_ggc (256, tree_map_hash,
+					    tree_map_eq, 0);
 
   int_cst_hash_table = htab_create_ggc (1024, int_cst_hash_hash,
 					int_cst_hash_eq, NULL);
@@ -568,7 +573,11 @@ copy_node_stat (tree node MEM_STAT_DECL)
 	  SET_DECL_INIT_PRIORITY (t, DECL_INIT_PRIORITY (node));
 	  DECL_HAS_INIT_PRIORITY_P (t) = 1;
 	}
-      
+      if (TREE_CODE (node) == VAR_DECL && DECL_BASED_ON_RESTRICT_P (node))
+	{
+	  SET_DECL_RESTRICT_BASE (t, DECL_GET_RESTRICT_BASE (node));
+	  DECL_BASED_ON_RESTRICT_P (t) = 1;
+	}
     }
   else if (TREE_CODE_CLASS (code) == tcc_type)
     {
@@ -3777,6 +3786,36 @@ decl_init_priority_insert (tree from, un
   *(struct tree_int_map **) loc = h;
 }  
 
+/* Look up a restrict qualified base decl for FROM.  */
+
+tree
+decl_restrict_base_lookup (tree from)
+{
+  struct tree_map *h;
+  struct tree_map in;
+
+  in.from = from;
+  h = htab_find_with_hash (restrict_base_for_decl, &in,
+			   htab_hash_pointer (from));
+  return h ? h->to : NULL_TREE;
+}
+
+/* Record the restrict qualified base TO for FROM.  */
+
+void
+decl_restrict_base_insert (tree from, tree to)
+{
+  struct tree_map *h;
+  void **loc;
+
+  h = ggc_alloc (sizeof (struct tree_map));
+  h->hash = htab_hash_pointer (from);
+  h->from = from;
+  h->to = to;
+  loc = htab_find_slot_with_hash (restrict_base_for_decl, h, h->hash, INSERT);
+  *(struct tree_map **) loc = h;
+}
+
 /* Print out the statistics for the DECL_DEBUG_EXPR hash table.  */
 
 static void
@@ -3798,6 +3837,21 @@ print_value_expr_statistics (void)
 	   (long) htab_elements (value_expr_for_decl),
 	   htab_collisions (value_expr_for_decl));
 }
+
+/* Print out statistics for the RESTRICT_BASE_FOR_DECL hash table, but
+   don't print anything if the table is empty.  */
+
+static void
+print_restrict_base_statistics (void)
+{
+  if (htab_elements (restrict_base_for_decl) != 0)
+    fprintf (stderr,
+	     "RESTRICT_BASE    hash: size %ld, %ld elements, %f collisions\n",
+	     (long) htab_size (restrict_base_for_decl),
+	     (long) htab_elements (restrict_base_for_decl),
+	     htab_collisions (restrict_base_for_decl));
+}
+
 /* Lookup a debug expression for FROM, and return it if we find one.  */
 
 tree 
@@ -5725,6 +5779,7 @@ dump_tree_statistics (void)
   print_type_hash_statistics ();
   print_debug_expr_statistics ();
   print_value_expr_statistics ();
+  print_restrict_base_statistics ();
   lang_hooks.print_statistics ();
 }
 
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.756
diff -p -u -r1.756 tree.h
--- tree.h	19 Sep 2005 14:54:28 -0000	1.756
+++ tree.h	28 Sep 2005 04:29:16 -0000
@@ -2425,6 +2425,20 @@ struct tree_parm_decl GTY(())
    an address constant.  */
 #define DECL_NON_ADDR_CONST_P(NODE) (DECL_WITH_VIS_CHECK (NODE)->decl_with_vis.non_addr_const_p)
 
+/* DECL_BASED_ON_RESTRICT_P records whether a VAR_DECL is a temporary
+   based on a variable with a restrict qualified type.  If it is,
+   DECL_RESTRICT_BASE returns the restrict qualified variable on which
+   it is based.  */
+
+#define DECL_BASED_ON_RESTRICT_P(NODE) \
+  (VAR_DECL_CHECK (NODE)->decl_with_vis.based_on_restrict_p)
+#define DECL_GET_RESTRICT_BASE(NODE) \
+  (decl_restrict_base_lookup (VAR_DECL_CHECK (NODE)))
+#define SET_DECL_RESTRICT_BASE(NODE, VAL) \
+  (decl_restrict_base_insert (VAR_DECL_CHECK (NODE), (VAL)))
+
+extern tree decl_restrict_base_lookup (tree);
+extern void decl_restrict_base_insert (tree, tree);
 
 /* Used in a DECL to indicate that, even if it TREE_PUBLIC, it need
    not be put out unless it is needed in this translation unit.
@@ -2500,7 +2514,8 @@ struct tree_decl_with_vis GTY(())
  unsigned common_flag:1; 
  unsigned in_text_section : 1;
  unsigned gimple_formal_temp : 1;
- unsigned non_addr_const_p : 1; 
+ unsigned non_addr_const_p : 1;
+ unsigned based_on_restrict_p : 1;
  /* Used by C++.  Might become a generic decl flag.  */
  unsigned shadowed_for_var_p : 1;
  
@@ -2517,7 +2532,7 @@ struct tree_decl_with_vis GTY(())
 
  /* Belongs to VAR_DECL exclusively.  */
  ENUM_BITFIELD(tls_model) tls_model : 3;
- /* 13 unused bits. */
+ /* 11 unused bits. */
 };
 
 /* In a VAR_DECL that's static,