On 1/18/07, Richard Kenner <[EMAIL PROTECTED]> wrote:
> I had thought of a hash table, too, but I couldn't figure out where to
> initialize and free it (i.e. where it is a "live" table, so to speak). For
> example, I don't know if this table would be required after gimplification,
> and I also don't even know how GNAT translates its own representation to
> GIMPLE (whole translation unit at once? function at a time?).
It's fairly conventional in that part.
But that's not relevant here. This is used for transmitting location
information on FIELD_DECLs back to the front end. Most records in Ada are
defined at GCC's global level, so there's little point in doing anything
other than a hash table that's initialized early on (e.g., in the routine
"gigi") and never freed. Also, the current code just saves the result for
EXPR_P nodes since only those have TREE_COMPLEXITY, but if you're switching
to a hash table, it's probably best just to record *all* results in it.
OK, attached is the preliminary hack I created some time ago. After
some changes, it now bootstraps, but I haven't tested it yet. I'm
passing it as an RFC.
I did not go as far as what you suggested, because I don't want to
change code I don't really understand. This is the minimum patch I
would need to remove the complexity field from struct tree_exp. If
one of you can do better than this, for the purpose of GNAT, please go
ahead and change it any way you see fit ;-)
No point in getting too sophisticated here: this is just a small hack to
avoid pathalogical compile-time behavior when compiling certain very complex
record types.
Are these test cases in the FSF test suite?
Thanks,
Gr.
Steven
2007-xx-xx Steven Bosscher <[EMAIL PROTECTED]>
gcc/
* tree.c (iterative_hash_expr): Handle types generically.
Also handle PLACEHOLDER_EXPR nodes.
ada/
* decl.c: Include hashtab.h and gt-ada-decl.h
(struct cached_annotate_value_t, cached_annotate_value_tab,
cached_annotate_value_hash, cached_annotate_value_eq,
cached_annotate_value_marked_p, cached_annotate_value_lookup,
cached_annotate_value_insert): New data structures and support
functions to implement a cache for annotate_value results.
(annotate_value): Use the hash table as a cache, instead of
using TREE_COMPLEXITY.
Index: tree.c
===================================================================
--- tree.c (revision 121230)
+++ tree.c (working copy)
@@ -5158,12 +5158,21 @@ iterative_hash_expr (tree t, hashval_t v
/* DECL's have a unique ID */
val = iterative_hash_host_wide_int (DECL_UID (t), val);
}
+ else if (class == tcc_type)
+ {
+ /* TYPEs also have a unique ID. */
+ val = iterative_hash_host_wide_int (TYPE_UID (t), val);
+ }
else
{
- gcc_assert (IS_EXPR_CODE_CLASS (class));
-
val = iterative_hash_object (code, val);
+ /* The tree must be a placeholder now, or an expression.
+ For anything else, die. */
+ if (code == PLACEHOLDER_EXPR)
+ return val;
+ gcc_assert (IS_EXPR_CODE_CLASS (class));
+
/* Don't hash the type, that can lead to having nodes which
compare equal according to operand_equal_p, but which
have different hash codes. */
Index: ada/decl.c
===================================================================
--- ada/decl.c (revision 121230)
+++ ada/decl.c (working copy)
@@ -34,6 +34,7 @@
#include "convert.h"
#include "ggc.h"
#include "obstack.h"
+#include "hashtab.h"
#include "target.h"
#include "expr.h"
@@ -5864,6 +5865,104 @@ compare_field_bitpos (const PTR rt1, con
return 1;
}
+
+/* In annotate_value, we compute an Uint to be placed into an Esize,
+ Component_Bit_Offset, or Component_Size value in the GNAT tree.
+ Because re-computing the value is expensive, we cache the unique
+ result for each tree in a hash table. The hash table key is the
+ hashed GNU tree, and the hash table value is the useful data in
+ the buckets.
+
+ The hash table entries are pointers to cached_annotate_value_t.
+ We hash GNU_SIZE in the insert and lookup functions for this
+ the hash table, using iterative_hash_expr. Caching the hash
+ value on the bucket entries speeds up the hash table quite a
+ bit during resizing. */
+
+struct cached_annotate_value_t GTY(())
+{
+ /* Cached hash value for this table entry. */
+ hashval_t hashval;
+
+ /* The cached value.
+ ??? This should be an Uint but gengtype choques on that. */
+ int value;
+
+ /* The tree that the value was computed for. */
+ tree gnu_size;
+};
+
+/* The hash table used as the annotate_value cache. */
+static GTY ((if_marked ("cached_annotate_value_marked_p"),
+ param_is (struct cached_annotate_value_t)))
+ htab_t cached_annotate_value_tab;
+
+/* Hash an annotate_value result for the annotate_value cache.
+ But actually, we've stored the hash value on the cache entry. */
+
+static unsigned int
+cached_annotate_value_hash (const void *pa)
+{
+ const struct cached_annotate_value_t *a = pa;
+ return a->hashval;
+}
+
+/* Return true if the tree in the annotate_value cache entries are equal. */
+
+static int
+cached_annotate_value_eq (const void *pa, const void *pb)
+{
+ const struct cached_annotate_value_t *a = pa, *b = pb;
+ int equal = (a->gnu_size == b->gnu_size);
+ return equal;
+}
+
+/* Return true if the tree in a annotate_value cache entry was marked
+ during a ggc_collect. */
+static int
+cached_annotate_value_marked_p (const void *p)
+{
+ tree gnu_size = ((struct cached_annotate_value_t *) p)->gnu_size;
+ return ggc_marked_p (gnu_size);
+}
+
+/* Lookup a cached annotate_value for GNU_SIZE.
+ If a cache entry is found, return TRUE and set the value of
+ the cache entry in VALUEP.
+ Return FALSE if none was found. */
+
+static bool
+cached_annotate_value_lookup (tree gnu_size, Uint *valuep)
+{
+ struct cached_annotate_value_t *entry, in;
+ in.gnu_size = gnu_size;
+ entry = htab_find_with_hash (cached_annotate_value_tab, &in,
+ iterative_hash_expr (gnu_size, 0));
+ if (!entry)
+ return false;
+
+ *valuep = entry->value;
+ return true;
+}
+
+/* Insert a mapping GNU_SIZE->ANNOTATE_VALUE in the annotate_value cache. */
+
+static void
+cached_annotate_value_insert (tree gnu_size, Uint value)
+{
+ struct cached_annotate_value_t *entry;
+ void **loc;
+
+ entry = ggc_alloc (sizeof (struct cached_annotate_value_t));
+ entry->hashval = iterative_hash_expr (gnu_size, 0);
+ entry->value = value;
+ entry->gnu_size = gnu_size;
+
+ loc = htab_find_slot_with_hash (cached_annotate_value_tab, entry,
+ entry->hashval, INSERT);
+ *(struct cached_annotate_value_t**) loc = entry;
+}
+
/* Given GNU_SIZE, a GCC tree representing a size, return a Uint to be
placed into an Esize, Component_Bit_Offset, or Component_Size value
in the GNAT tree. */
@@ -5876,10 +5975,20 @@ annotate_value (tree gnu_size)
Node_Ref_Or_Val ops[3], ret;
int i;
int size;
+ Uint value;
+
+ /* If the hash table to cache results of this function does not
+ already exist, create it now. */
+ if (!cached_annotate_value_tab)
+ {
+ cached_annotate_value_tab =
+ htab_create_ggc (512, cached_annotate_value_hash,
+ cached_annotate_value_eq, 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 (cached_annotate_value_lookup (gnu_size, &value))
+ return value;
/* 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
@@ -5994,7 +6103,7 @@ annotate_value (tree gnu_size)
}
ret = Create_Node (tcode, ops[0], ops[1], ops[2]);
- TREE_COMPLEXITY (gnu_size) = ret;
+ cached_annotate_value_insert (gnu_size, ret);
return ret;
}
@@ -6847,3 +6956,5 @@ concat_id_with_name (tree gnu_id, const
strcpy (Name_Buffer + len, suffix);
return get_identifier (Name_Buffer);
}
+
+#include "gt-ada-decl.h"
