[PATCH] Remove TREE_COMPLEXITY, take 2

[Paolo Bonzini <paolo dot bonzini at lu dot unisi dot ch>]

This patch, based on the outcome of the thread between Steven Bosscher 
and Richard Kenner, is another attempt at removing TREE_COMPLEXITY. 
While this patch is not based on Steven's, the credit goes undoubtedly 
to him for his "nursing" GCC until this little field could be removed.

I found that the required hash table functions are actually already 
present in tree.c.  There we have an implementation of a tree -> 
unsigned short hash table; we need tree -> unsigned int instead but it 
is not a problem to widen the values' type.  The hash table uses 
htab_hash_pointer to compute the hash value, which means that it does 
not dive into the values that it holds.

Since Richard K. is a GWP, and since by now TREE_COMPLEXITY is an 
Ada-only thing (gigi-only) I placed in this patch also the actual 
removal of TREE_COMPLEXITY.

Boostrapped/regtested C/C++/Ada, i686-pc-linux-gnu, ok for mainline?

Paolo
2007-02-02  Paolo Bonzini  <bonzini@gnu.org>

	* tree.c (tree_int_map_hash, tree_int_map_eq, tree_int_map_marked_p):
	Remove prototypes and make them non-static.
	(struct tree_int_map): Remove.
	* tree.h (struct tree_int_map): Move here, turning TO into an
	unsigned int.
	(tree_int_map_hash, tree_int_map_eq, tree_int_map_marked_p): Declare.
	* ada/decl.c (annotate_value_cache): New.
	(annotate_value): Use it instead of TREE_COMPLEXITY.

	* tree.h (TREE_COMPLEXITY): Remove.
	(struct tree_exp): Remove complexity field.
	* tree.c (build1_stat): Don't set it.

Index: tree.c
===================================================================
--- tree.c	(revision 121500)
+++ tree.c	(working copy)
@@ -150,14 +150,6 @@
 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;
-  unsigned short to;
-};
-static unsigned int tree_int_map_hash (const void *);
-static int tree_int_map_eq (const void *, const void *);
-static int tree_int_map_marked_p (const void *);
 static void set_type_quals (tree, int);
 static int type_hash_eq (const void *, const void *);
 static hashval_t type_hash_hash (const void *);
@@ -2931,7 +2923,6 @@
 #else
   SET_EXPR_LOCUS (t, NULL);
 #endif
-  TREE_COMPLEXITY (t) = 0;
   TREE_OPERAND (t, 0) = node;
   TREE_BLOCK (t) = NULL_TREE;
   if (node && !TYPE_P (node))
@@ -4184,7 +4175,7 @@
 
 /* Return true if the trees in the tree_int_map *'s VA and VB are equal.  */
 
-static int
+int
 tree_int_map_eq (const void *va, const void *vb)
 {
   const struct tree_int_map  *a = va, *b = vb;
@@ -4193,7 +4184,7 @@
 
 /* Hash a from tree in the tree_int_map * ITEM.  */
 
-static unsigned int
+unsigned int
 tree_int_map_hash (const void *item)
 {
   return htab_hash_pointer (((const struct tree_int_map *)item)->from);
@@ -4203,7 +4194,7 @@
    purposes.  We simply return true if the from tree_int_map *P's from tree is marked, so that this
    structure goes away when the from tree goes away.  */
 
-static int
+int
 tree_int_map_marked_p (const void *p)
 {
   tree from = ((struct tree_int_map *) p)->from;
Index: tree.h
===================================================================
--- tree.h	(revision 121500)
+++ tree.h	(working copy)
@@ -1498,7 +1498,6 @@
 
 /* In ordinary expression nodes.  */
 #define TREE_OPERAND(NODE, I) TREE_OPERAND_CHECK (NODE, I)
-#define TREE_COMPLEXITY(NODE) (EXPR_CHECK (NODE)->exp.complexity)
 
 /* In gimple statements.  */
 #define GIMPLE_STMT_OPERAND(NODE, I) GIMPLE_STMT_OPERAND_CHECK (NODE, I)
@@ -1724,7 +1723,6 @@
 {
   struct tree_common common;
   source_locus locus;
-  int complexity;
   tree block;
   tree GTY ((special ("tree_exp"),
 	     desc ("TREE_CODE ((tree) &%0)")))
@@ -4718,6 +4716,7 @@
 /* In tree-vectorizer.c.  */
 extern void vect_set_verbosity_level (const char *);
 
+/* In tree.c.  */
 struct tree_map GTY(())
 {
   unsigned int hash;
@@ -4729,6 +4728,16 @@
 extern int tree_map_marked_p (const void *);
 extern int tree_map_eq (const void *, const void *);
 
+struct tree_int_map GTY(())
+{
+  tree from;
+  unsigned int to;
+};
+
+extern unsigned int tree_int_map_hash (const void *);
+extern int tree_int_map_eq (const void *, const void *);
+extern int tree_int_map_marked_p (const void *);
+
 /* In tree-ssa-address.c.  */
 extern tree tree_mem_ref_addr (tree, tree);
 extern void copy_mem_ref_info (tree, tree);
Index: ada/decl.c
===================================================================
--- ada/decl.c	(revision 121287)
+++ ada/decl.c	(working copy)
@@ -50,6 +50,7 @@
 #include "fe.h"
 #include "sinfo.h"
 #include "einfo.h"
+#include "hashtab.h"
 #include "ada-tree.h"
 #include "gigi.h"
 
@@ -80,6 +81,10 @@ static struct incomplete
 static int defer_debug_level = 0;
 static tree defer_debug_incomplete_list;
 
+/* A hash table used as to cache the result of annotate_value.  */
+static GTY ((if_marked ("tree_int_map_marked_p"), param_is (struct tree_int_map)))
+  htab_t annotate_value_cache;
+
 static void copy_alias_set (tree, tree);
 static tree substitution_list (Entity_Id, Entity_Id, tree, bool);
 static bool allocatable_size_p (tree, bool);
@@ -5876,11 +5881,23 @@ annotate_value (tree gnu_size)
   Node_Ref_Or_Val ops[3], ret;
   int i;
   int size;
+  struct tree_int_map **h = NULL;
 
   /* See if we've already saved the value for this node.  */
-  if (EXPR_P (gnu_size) && TREE_COMPLEXITY (gnu_size))
-    return (Node_Ref_Or_Val) TREE_COMPLEXITY (gnu_size);
+  if (EXPR_P (gnu_size))
+    {
+      struct tree_int_map in;
+      if (!annotate_value_cache)
+        annotate_value_cache = htab_create_ggc (512, tree_int_map_hash,
+					        tree_int_map_eq, 0);
+      in.from = gnu_size;
+      h = (struct tree_int_map **)
+	    htab_find_slot (annotate_value_cache, &in, INSERT);
 
+      if (*h)
+	return (Node_Ref_Or_Val) (*h)->to;
+    }
+
   /* If we do not return inside this switch, TCODE will be set to the
      code to use for a Create_Node operand and LEN (set above) will be
      the number of recursive calls for us to make.  */
@@ -5994,7 +6012,15 @@ annotate_value (tree gnu_size)
     }
 
   ret = Create_Node (tcode, ops[0], ops[1], ops[2]);
-  TREE_COMPLEXITY (gnu_size) = ret;
+
+  /* Save the result in the cache.  */
+  if (h)
+    {
+      *h = ggc_alloc (sizeof (struct tree_int_map));
+      (*h)->from = gnu_size;
+      (*h)->to = ret;
+    }
+
   return ret;
 }
 
@@ -6847,3 +6873,5 @@ concat_id_with_name (tree gnu_id, const 
   strcpy (Name_Buffer + len, suffix);
   return get_identifier (Name_Buffer);
 }
+
+#include "gt-ada-decl.h"