* [var-tracking] [not-good!] disable shared_hash and other simplifications
2011-08-22 11:38 [var-tracking] small speed-ups Dimitrios Apostolou
@ 2011-08-22 12:21 ` Dimitrios Apostolou
2011-08-22 12:57 ` Jakub Jelinek
2011-08-22 13:44 ` [var-tracking] small speed-ups Jakub Jelinek
1 sibling, 1 reply; 9+ messages in thread
From: Dimitrios Apostolou @ 2011-08-22 12:21 UTC (permalink / raw)
To: Dimitrios Apostolou; +Cc: gcc-patches, Steven Bosscher, Alexandre Oliva
[-- Attachment #1: Type: TEXT/PLAIN, Size: 1685 bytes --]
Hello,
the attached patch applies after my previous one, and actually cancels all
runtime gains from it. It doesn't make things worse than initially, so
it's not *that* bad.
While trying to understand var-tracking I deleted the whole shared hash
table concept and some other indirections. It didn't make things much
worse, and it makes me think that getting rid of other indirections like
shared variables reference counting would actually help. But it got too
complicated and I had to give up.
While I don't understand variable tracking, I couldn't help but notice
some things that could be discussed:
* This is the part of the compiler that makes the heaviest use of hash
tables. htab_traverse(), htab_delete(), FOR_EACH_HTAB_ELEMENT (should that
be moved in libiberty?) all iterate way too many times over hash tables.
This is all because decl/value UIDs are sparse.
* Since var-tracking is happening per-function, is there a way to produce
per-function UIDs and use those in a regular array instead of a sparse
hash table? These UIDs could be produced at tree/rtx level, and I bet
other parts in the compiler could make good use of them.
* Another alternative would be to store variables in a vector, sorted by
UID value. That way checking if it's there would be O(logn) but merging
would be a very simple operation. Still, merging dataflow sets is way to
complex to follow so I didn't manage to change this.
* From a very wide field of view, all this DF solving reminded me a lot of
what I've seen in df-*.c. Why can't variable tracking be integrated in the
main DF pass of the compiler, the one that happens *after* register
allocation?
Thanks,
Dimitris
[-- Attachment #2: Type: TEXT/plain, Size: 40881 bytes --]
=== modified file 'gcc/var-tracking.c'
--- gcc/var-tracking.c 2011-08-22 08:27:47 +0000
+++ gcc/var-tracking.c 2011-08-22 10:36:15 +0000
@@ -233,17 +233,6 @@ typedef struct attrs_def
HOST_WIDE_INT offset;
} *attrs;
-/* Structure holding a refcounted hash table. If refcount > 1,
- it must be first unshared before modified. */
-typedef struct shared_hash_def
-{
- /* Reference count. */
- int refcount;
-
- /* Actual hash table. */
- htab_t htab;
-} *shared_hash;
-
/* Structure holding the IN or OUT set for a basic block. */
typedef struct dataflow_set_def
{
@@ -253,11 +242,11 @@ typedef struct dataflow_set_def
/* Attributes for registers (lists of attrs). */
attrs regs[FIRST_PSEUDO_REGISTER];
- /* Variable locations. */
- shared_hash vars;
+ /* Variable locations, stored in a hash table. */
+ htab_t vars;
/* Vars that is being traversed. */
- shared_hash traversed_vars;
+ htab_t traversed_vars;
} dataflow_set;
/* The structure (one for each basic block) containing the information
@@ -379,9 +368,6 @@ static alloc_pool valvar_pool;
/* Alloc pool for struct location_chain_def. */
static alloc_pool loc_chain_pool;
-/* Alloc pool for struct shared_hash_def. */
-static alloc_pool shared_hash_pool;
-
/* Alloc pool for struct value_chain_def. */
static alloc_pool value_chain_pool;
@@ -395,7 +381,7 @@ static htab_t value_chains;
static bool emit_notes;
/* Empty shared hashtable. */
-static shared_hash empty_shared_hash;
+static htab_t empty_htab;
/* Scratch register bitmap used by cselib_expand_value_rtx. */
static bitmap scratch_regs = NULL;
@@ -478,7 +464,7 @@ static void **delete_slot_part (dataflow
static void delete_variable_part (dataflow_set *, rtx,
decl_or_value, HOST_WIDE_INT);
static int emit_note_insn_var_location (void **, void *);
-static void emit_notes_for_changes (rtx, enum emit_note_where, shared_hash);
+static void emit_notes_for_changes (rtx, enum emit_note_where, htab_t);
static int emit_notes_for_differences_1 (void **, void *);
static int emit_notes_for_differences_2 (void **, void *);
static void emit_notes_for_differences (rtx, dataflow_set *, dataflow_set *);
@@ -1370,164 +1356,30 @@ attrs_list_mpdv_union (attrs *dstp, attr
}
}
-/* Shared hashtable support. */
-
-/* Return true if VARS is shared. */
-
-static inline bool
-shared_hash_shared (shared_hash vars)
-{
- return vars->refcount > 1;
-}
-
-/* Return the hash table for VARS. */
-
-static inline htab_t
-shared_hash_htab (shared_hash vars)
-{
- return vars->htab;
-}
-
/* Return true if VAR is shared, or maybe because VARS is shared. */
static inline bool
-shared_var_p (variable var, shared_hash vars)
+shared_var_p (variable var)
{
/* Don't count an entry in the changed_variables table as a duplicate. */
- return ((var->refcount > 1 + (int) var->in_changed_variables)
- || shared_hash_shared (vars));
+ return (var->refcount - (int) var->in_changed_variables) > 1;
}
-/* Copy all variables from hash table SRC to hash table DST without rehashing
- any values. */
-
-static htab_t
-htab_dup (htab_t src)
-{
- htab_t dst;
-
- dst = (htab_t) xmalloc (sizeof (*src));
- memcpy (dst, src, sizeof (*src));
- dst->entries = (void **) xmalloc (src->size * sizeof (*src->entries));
- memcpy (dst->entries, src->entries,
- src->size * sizeof (*src->entries));
- return dst;
-}
-
-/* Copy variables into a new hash table. */
-
-static shared_hash
-shared_hash_unshare (shared_hash vars)
-{
- variable var;
- htab_iterator hi;
- shared_hash new_vars = (shared_hash) pool_alloc (shared_hash_pool);
-
- gcc_assert (vars->refcount > 1);
- new_vars->refcount = 1;
- new_vars->htab = htab_dup (vars->htab);
- FOR_EACH_HTAB_ELEMENT (new_vars->htab, var, variable, hi)
- {
- var->refcount++;
- }
- vars->refcount--;
-
- return new_vars;
-}
-
-/* Increment reference counter on VARS and return it. */
-
-static inline shared_hash
-shared_hash_copy (shared_hash vars)
-{
- vars->refcount++;
- return vars;
-}
-
-/* Decrement reference counter and destroy hash table if not shared
- anymore. */
-
-static void
-shared_hash_destroy (shared_hash vars, bool do_free)
-{
- gcc_checking_assert (vars->refcount > 0);
- if (--vars->refcount == 0)
- {
- if (!do_free)
- /* Dirty hack to prevent htab_delete() iterating over all elements */
- vars->htab->del_f = NULL;
- htab_delete (vars->htab);
- if (do_free)
- pool_free (shared_hash_pool, vars);
- }
-}
-
-/* Unshare *PVARS if shared and return slot for DV. If INS is
- INSERT, insert it if not already present. */
+/* Search for a dv in a hash table of variables/value_chains, return its
+ slot. */
static inline void **
-shared_hash_find_slot_unshare_1 (shared_hash *pvars, decl_or_value dv,
- hashval_t dvhash, enum insert_option ins)
+htab_slot_dv (htab_t vars, decl_or_value dv, enum insert_option ins)
{
- if (shared_hash_shared (*pvars))
- *pvars = shared_hash_unshare (*pvars);
- return htab_find_slot_with_hash (shared_hash_htab (*pvars), dv, dvhash, ins);
+ return htab_find_slot_with_hash (vars, dv, dv_htab_hash (dv), ins);
}
-static inline void **
-shared_hash_find_slot_unshare (shared_hash *pvars, decl_or_value dv,
- enum insert_option ins)
-{
- return shared_hash_find_slot_unshare_1 (pvars, dv, dv_htab_hash (dv), ins);
-}
-
-/* Return slot for DV, if it is already present in the hash table.
- If it is not present, insert it only VARS is not shared, otherwise
- return NULL. */
-
-static inline void **
-shared_hash_find_slot_1 (shared_hash vars, decl_or_value dv, hashval_t dvhash)
-{
- return htab_find_slot_with_hash (shared_hash_htab (vars), dv, dvhash,
- shared_hash_shared (vars)
- ? NO_INSERT : INSERT);
-}
-
-static inline void **
-shared_hash_find_slot (shared_hash vars, decl_or_value dv)
-{
- return shared_hash_find_slot_1 (vars, dv, dv_htab_hash (dv));
-}
-
-/* Return slot for DV only if it is already present in the hash table. */
-
-static inline void **
-shared_hash_find_slot_noinsert_1 (shared_hash vars, decl_or_value dv,
- hashval_t dvhash)
-{
- return htab_find_slot_with_hash (shared_hash_htab (vars), dv, dvhash,
- NO_INSERT);
-}
-
-static inline void **
-shared_hash_find_slot_noinsert (shared_hash vars, decl_or_value dv)
-{
- return shared_hash_find_slot_noinsert_1 (vars, dv, dv_htab_hash (dv));
-}
-
-/* Return variable for DV or NULL if not already present in the hash
- table. */
+/* Search for a dv in a hash table of variables. */
static inline variable
-shared_hash_find_1 (shared_hash vars, decl_or_value dv, hashval_t dvhash)
+htab_find_dv (htab_t vars, decl_or_value dv)
{
- return (variable) htab_find_with_hash (shared_hash_htab (vars), dv, dvhash);
-}
-
-static inline variable
-shared_hash_find (shared_hash vars, decl_or_value dv)
-{
- return shared_hash_find_1 (vars, dv, dv_htab_hash (dv));
+ return (variable) htab_find_with_hash (vars, dv, dv_htab_hash (dv));
}
/* Return true if TVAL is better than CVAL as a canonival value. We
@@ -1546,8 +1398,6 @@ canon_value_cmp (rtx tval, rtx cval)
|| CSELIB_VAL_PTR (tval)->uid < CSELIB_VAL_PTR (cval)->uid;
}
-static bool dst_can_be_shared;
-
/* Return a copy of a variable VAR and insert it to dataflow set SET. */
static void **
@@ -1599,17 +1449,13 @@ unshare_variable (dataflow_set *set, voi
new_var->var_part[i].cur_loc = var->var_part[i].cur_loc;
}
- dst_can_be_shared = false;
- if (shared_hash_shared (set->vars))
- slot = shared_hash_find_slot_unshare (&set->vars, var->dv, NO_INSERT);
- else if (set->traversed_vars && set->vars != set->traversed_vars)
- slot = shared_hash_find_slot_noinsert (set->vars, var->dv);
+ if (set->traversed_vars && set->vars != set->traversed_vars)
+ slot = htab_slot_dv (set->vars, var->dv, NO_INSERT);
*slot = new_var;
if (var->in_changed_variables)
{
void **cslot
- = htab_find_slot_with_hash (changed_variables, var->dv,
- dv_htab_hash (var->dv), NO_INSERT);
+ = htab_slot_dv (changed_variables, var->dv, NO_INSERT);
gcc_assert (*cslot == (void *) var);
var->in_changed_variables = false;
variable_htab_free (var);
@@ -1680,7 +1526,7 @@ get_init_value (dataflow_set *set, rtx l
if (! flag_var_tracking_uninit)
return VAR_INIT_STATUS_INITIALIZED;
- var = shared_hash_find (set->vars, dv);
+ var = htab_find_dv (set->vars, dv);
if (var)
{
for (i = 0; i < var->n_var_parts && ret_val == VAR_INIT_STATUS_UNKNOWN; i++)
@@ -1910,7 +1756,7 @@ val_store (dataflow_set *set, rtx val, r
static void
val_reset (dataflow_set *set, decl_or_value dv)
{
- variable var = shared_hash_find (set->vars, dv) ;
+ variable var = htab_find_dv (set->vars, dv);
location_chain node;
rtx cval;
@@ -2043,7 +1889,8 @@ dataflow_set_init (dataflow_set *set)
{
/* Initialize the set (array) SET of attrs to empty lists. */
memset (set->regs, 0, sizeof (set->regs));
- set->vars = shared_hash_copy (empty_shared_hash);
+ set->vars = htab_create (5, variable_htab_hash, variable_htab_eq,
+ variable_htab_free);
set->stack_adjust = 0;
set->traversed_vars = NULL;
}
@@ -2058,8 +1905,23 @@ dataflow_set_clear (dataflow_set *set)
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
attrs_list_clear (&set->regs[i]);
- shared_hash_destroy (set->vars, true);
- set->vars = shared_hash_copy (empty_shared_hash);
+ htab_empty (set->vars);
+}
+
+/* Copy all variables from hash table SRC to hash table DST without rehashing
+ any values. */
+
+static htab_t
+htab_dup (htab_t src)
+{
+ htab_t dst;
+
+ dst = (htab_t) xmalloc (sizeof (*src));
+ memcpy (dst, src, sizeof (*src));
+ dst->entries = (void **) xmalloc (src->size * sizeof (*src->entries));
+ memcpy (dst->entries, src->entries,
+ src->size * sizeof (*src->entries));
+ return dst;
}
/* Copy the contents of dataflow set SRC to DST. */
@@ -2067,14 +1929,19 @@ dataflow_set_clear (dataflow_set *set)
static void
dataflow_set_copy (dataflow_set *dst, dataflow_set *src)
{
+ htab_iterator hi;
+ variable var;
int i;
+ /* TODO memcpy */
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
attrs_list_copy (&dst->regs[i], src->regs[i]);
- shared_hash_destroy (dst->vars, true);
- dst->vars = shared_hash_copy (src->vars);
+ htab_delete (dst->vars);
dst->stack_adjust = src->stack_adjust;
+ dst->vars = htab_dup (src->vars);
+ FOR_EACH_HTAB_ELEMENT (dst->vars, var, variable, hi)
+ var->refcount++;
}
/* Information for merging lists of locations for a given offset of variable.
@@ -2128,22 +1995,17 @@ variable_union (variable src, dataflow_s
void **dstp;
int i, j, k;
- dstp = shared_hash_find_slot (set->vars, src->dv);
- if (!dstp || !*dstp)
+ dstp = htab_slot_dv (set->vars, src->dv, INSERT);
+ if (*dstp == HTAB_EMPTY_ENTRY)
{
src->refcount++;
-
- dst_can_be_shared = false;
- if (!dstp)
- dstp = shared_hash_find_slot_unshare (&set->vars, src->dv, INSERT);
-
*dstp = src;
/* Continue traversing the hash table. */
return 1;
}
- else
- dst = (variable) *dstp;
+
+ dst = (variable) *dstp;
gcc_assert (src->n_var_parts);
@@ -2172,7 +2034,7 @@ variable_union (variable src, dataflow_s
{
location_chain nnode;
- if (shared_var_p (dst, set->vars))
+ if (shared_var_p (dst))
{
dstp = unshare_variable (set, dstp, dst,
VAR_INIT_STATUS_INITIALIZED);
@@ -2224,7 +2086,7 @@ variable_union (variable src, dataflow_s
thus there are at most MAX_VAR_PARTS different offsets. */
gcc_assert (dv_onepart_p (dst->dv) ? k == 1 : k <= MAX_VAR_PARTS);
- if (dst->n_var_parts != k && shared_var_p (dst, set->vars))
+ if (dst->n_var_parts != k && shared_var_p (dst))
{
dstp = unshare_variable (set, dstp, dst, VAR_INIT_STATUS_UNKNOWN);
dst = (variable)*dstp;
@@ -2251,7 +2113,7 @@ variable_union (variable src, dataflow_s
/* If DST is shared compare the location chains.
If they are different we will modify the chain in DST with
high probability so make a copy of DST. */
- if (shared_var_p (dst, set->vars))
+ if (shared_var_p (dst))
{
for (node = src->var_part[i].loc_chain,
node2 = dst->var_part[j].loc_chain; node && node2;
@@ -2490,24 +2352,15 @@ variable_union (variable src, dataflow_s
static void
dataflow_set_union (dataflow_set *dst, dataflow_set *src)
{
+ htab_iterator hi;
+ variable var;
int i;
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
attrs_list_union (&dst->regs[i], src->regs[i]);
- if (dst->vars == empty_shared_hash)
- {
- shared_hash_destroy (dst->vars, true);
- dst->vars = shared_hash_copy (src->vars);
- }
- else
- {
- htab_iterator hi;
- variable var;
-
- FOR_EACH_HTAB_ELEMENT (shared_hash_htab (src->vars), var, variable, hi)
- variable_union (var, dst);
- }
+ FOR_EACH_HTAB_ELEMENT (src->vars, var, variable, hi)
+ variable_union (var, dst);
}
/* Whether the value is currently being expanded. */
@@ -2605,7 +2458,7 @@ find_loc_in_1pdv (rtx loc, variable var,
gcc_checking_assert (!node->next);
dv = dv_from_value (node->loc);
- rvar = (variable) htab_find_with_hash (vars, dv, dv_htab_hash (dv));
+ rvar = htab_find_dv (vars, dv);
return find_loc_in_1pdv (loc, rvar, vars);
}
@@ -2694,8 +2547,7 @@ intersect_loc_chains (rtx val, location_
if (s1node->loc == val)
continue;
- if ((found = find_loc_in_1pdv (s1node->loc, s2var,
- shared_hash_htab (s2set->vars))))
+ if ((found = find_loc_in_1pdv (s1node->loc, s2var, s2set->vars)))
{
insert_into_intersection (dest, s1node->loc,
MIN (s1node->init, found->init));
@@ -2706,7 +2558,7 @@ intersect_loc_chains (rtx val, location_
&& !VALUE_RECURSED_INTO (s1node->loc))
{
decl_or_value dv = dv_from_value (s1node->loc);
- variable svar = shared_hash_find (s1set->vars, dv);
+ variable svar = htab_find_dv (s1set->vars, dv);
if (svar)
{
if (svar->n_var_parts == 1)
@@ -2924,8 +2776,7 @@ add_value_chain (rtx *loc, void *dvp)
return 0;
dv = (decl_or_value) dvp;
- slot = htab_find_slot_with_hash (value_chains, ldv, dv_htab_hash (ldv),
- INSERT);
+ slot = htab_slot_dv (value_chains, ldv, INSERT);
if (!*slot)
{
vc = (value_chain) pool_alloc (value_chain_pool);
@@ -3013,8 +2864,7 @@ remove_value_chain (rtx *loc, void *dvp)
return 0;
dv = (decl_or_value) dvp;
- slot = htab_find_slot_with_hash (value_chains, ldv, dv_htab_hash (ldv),
- NO_INSERT);
+ slot = htab_slot_dv (value_chains, ldv, NO_INSERT);
for (vc = (value_chain) *slot; vc->next; vc = vc->next)
if (dv_as_opaque (vc->next->dv) == dv_as_opaque (dv))
{
@@ -3128,7 +2978,7 @@ canonicalize_values_mark (void **slot, v
else
{
decl_or_value odv = dv_from_value (node->loc);
- void **oslot = shared_hash_find_slot_noinsert (set->vars, odv);
+ void **oslot = htab_slot_dv (set->vars, odv, NO_INSERT);
set_slot_part (set, val, oslot, odv, 0,
node->init, NULL_RTX);
@@ -3209,7 +3059,7 @@ canonicalize_values_star (void **slot, v
restart_with_cval:
VALUE_RECURSED_INTO (cval) = false;
dv = dv_from_value (cval);
- slot = shared_hash_find_slot_noinsert (set->vars, dv);
+ slot = htab_slot_dv (set->vars, dv, NO_INSERT);
if (!slot)
{
gcc_assert (dv_is_decl_p (var->dv));
@@ -3233,7 +3083,7 @@ canonicalize_values_star (void **slot, v
/* Push values to the canonical one. */
cdv = dv_from_value (cval);
- cslot = shared_hash_find_slot_noinsert (set->vars, cdv);
+ cslot = htab_slot_dv (set->vars, cdv, NO_INSERT);
for (node = var->var_part[0].loc_chain; node; node = node->next)
if (node->loc != cval)
@@ -3393,7 +3243,7 @@ canonicalize_vars_star (void **slot, voi
/* Push values to the canonical one. */
cdv = dv_from_value (cval);
- cslot = shared_hash_find_slot_noinsert (set->vars, cdv);
+ cslot = htab_slot_dv (set->vars, cdv, NO_INSERT);
if (!cslot)
return 1;
cvar = (variable)*cslot;
@@ -3454,10 +3304,9 @@ variable_merge_over_cur (variable s1var,
else
val = NULL;
- s2var = shared_hash_find_1 (dsm->src->vars, dv, dvhash);
+ s2var = (variable) htab_find_with_hash (dsm->src->vars, dv, dvhash);
if (!s2var)
{
- dst_can_be_shared = false;
return 1;
}
@@ -3466,7 +3315,7 @@ variable_merge_over_cur (variable s1var,
&& s2var->n_var_parts == 1
&& s2var->var_part[0].offset == 0);
- dstslot = shared_hash_find_slot_noinsert_1 (dst->vars, dv, dvhash);
+ dstslot = htab_find_slot_with_hash (dst->vars, dv, dvhash, NO_INSERT);
if (dstslot)
{
dvar = (variable)*dstslot;
@@ -3483,15 +3332,13 @@ variable_merge_over_cur (variable s1var,
if (!dstslot && !onepart_variable_different_p (s1var, s2var))
{
- dstslot = shared_hash_find_slot_unshare_1 (&dst->vars, dv,
- dvhash, INSERT);
+ dstslot = htab_find_slot_with_hash (dst->vars, dv,
+ dvhash, INSERT);
*dstslot = dvar = s2var;
dvar->refcount++;
}
else
{
- dst_can_be_shared = false;
-
intersect_loc_chains (val, nodep, dsm,
s1var->var_part[0].loc_chain, s2var);
@@ -3509,9 +3356,8 @@ variable_merge_over_cur (variable s1var,
dvar->var_part[0].loc_chain = node;
dvar->var_part[0].cur_loc = NULL;
- dstslot
- = shared_hash_find_slot_unshare_1 (&dst->vars, dv, dvhash,
- INSERT);
+ dstslot = htab_find_slot_with_hash (dst->vars, dv,
+ dvhash, INSERT);
gcc_assert (!*dstslot);
*dstslot = dvar;
}
@@ -3581,12 +3427,12 @@ variable_merge_over_cur (variable s1var,
node->init, NULL, INSERT);
}
- dstslot = shared_hash_find_slot_noinsert_1 (dst->vars, dv, dvhash);
+ dstslot = htab_find_slot_with_hash (dst->vars, dv, dvhash, NO_INSERT);
gcc_assert (*dstslot == dvar);
canonicalize_values_star (dstslot, dst);
gcc_checking_assert (dstslot
- == shared_hash_find_slot_noinsert_1 (dst->vars,
- dv, dvhash));
+ == htab_find_slot_with_hash (dst->vars, dv,
+ dvhash, NO_INSERT));
dvar = (variable)*dstslot;
}
else
@@ -3625,11 +3471,10 @@ variable_merge_over_cur (variable s1var,
decl_or_value dv = dv_from_value (node->loc);
void **slot = NULL;
- if (shared_hash_shared (dst->vars))
- slot = shared_hash_find_slot_noinsert (dst->vars, dv);
- if (!slot)
- slot = shared_hash_find_slot_unshare (&dst->vars, dv,
- INSERT);
+ /* if (shared_hash_shared (dst->vars)) */
+ /* slot = shared_hash_find_slot_noinsert (dst->vars, dv); */
+ /* if (!slot) */
+ slot = htab_slot_dv (dst->vars, dv, INSERT);
if (!*slot)
{
variable var = (variable) pool_alloc (dv_pool (dv));
@@ -3648,12 +3493,12 @@ variable_merge_over_cur (variable s1var,
}
}
- dstslot = shared_hash_find_slot_noinsert_1 (dst->vars, dv, dvhash);
+ dstslot = htab_find_slot_with_hash (dst->vars, dv, dvhash, NO_INSERT);
gcc_assert (*dstslot == dvar);
canonicalize_values_star (dstslot, dst);
gcc_checking_assert (dstslot
- == shared_hash_find_slot_noinsert_1 (dst->vars,
- dv, dvhash));
+ == htab_find_slot_with_hash (dst->vars, dv,
+ dvhash, NO_INSERT));
dvar = (variable)*dstslot;
}
}
@@ -3669,10 +3514,7 @@ variable_merge_over_cur (variable s1var,
variable_htab_free (dvar);
*dstslot = dvar = s1var;
dvar->refcount++;
- dst_can_be_shared = false;
}
- else
- dst_can_be_shared = false;
return 1;
}
@@ -3691,7 +3533,7 @@ variable_merge_over_src (variable s2var,
if (!onepart)
{
- void **dstp = shared_hash_find_slot (dst->vars, dv);
+ void **dstp = htab_slot_dv (dst->vars, dv, INSERT);
*dstp = s2var;
s2var->refcount++;
return 1;
@@ -3707,7 +3549,7 @@ variable_merge_over_src (variable s2var,
static void
dataflow_set_merge (dataflow_set *dst, dataflow_set *src2)
{
- dataflow_set cur = *dst;
+ dataflow_set cur = *dst; /* Keep original dst as src1 */
dataflow_set *src1 = &cur;
struct dfset_merge dsm;
int i;
@@ -3715,16 +3557,15 @@ dataflow_set_merge (dataflow_set *dst, d
htab_iterator hi;
variable var;
- src1_elems = htab_elements (shared_hash_htab (src1->vars));
- src2_elems = htab_elements (shared_hash_htab (src2->vars));
- dataflow_set_init (dst);
+ src1_elems = htab_elements (src1->vars);
+ src2_elems = htab_elements (src2->vars);
+
+ memset (dst->regs, 0, sizeof (dst->regs));
+ /* htab_empty (dst->vars); */
+ dst->vars = htab_create (2 * MAX (src1_elems, src2_elems), variable_htab_hash,
+ variable_htab_eq, variable_htab_free);
+ dst->traversed_vars = NULL;
dst->stack_adjust = cur.stack_adjust;
- shared_hash_destroy (dst->vars, true);
- dst->vars = (shared_hash) pool_alloc (shared_hash_pool);
- dst->vars->refcount = 1;
- dst->vars->htab
- = htab_create (2 * MAX (src1_elems, src2_elems), variable_htab_hash,
- variable_htab_eq, variable_htab_free);
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
attrs_list_mpdv_union (&dst->regs[i], src1->regs[i], src2->regs[i]);
@@ -3734,14 +3575,11 @@ dataflow_set_merge (dataflow_set *dst, d
dsm.cur = src1;
dsm.src_onepart_cnt = 0;
- FOR_EACH_HTAB_ELEMENT (shared_hash_htab (dsm.src->vars), var, variable, hi)
+ FOR_EACH_HTAB_ELEMENT (dsm.src->vars, var, variable, hi)
variable_merge_over_src (var, &dsm);
- FOR_EACH_HTAB_ELEMENT (shared_hash_htab (dsm.cur->vars), var, variable, hi)
+ FOR_EACH_HTAB_ELEMENT (dsm.cur->vars, var, variable, hi)
variable_merge_over_cur (var, &dsm);
- if (dsm.src_onepart_cnt)
- dst_can_be_shared = false;
-
dataflow_set_destroy (src1, true);
}
@@ -3818,7 +3656,7 @@ dataflow_set_equiv_regs (dataflow_set *s
continue;
}
- slot = shared_hash_find_slot_noinsert (set->vars, list->dv);
+ slot = htab_slot_dv (set->vars, list->dv, NO_INSERT);
canonicalize_values_star (slot, set);
if (*listp != list)
list = NULL;
@@ -4032,8 +3870,7 @@ variable_post_merge_perm_vals (void **ps
&& REG_P (pnode->loc));
dv = pvar->dv;
-
- var = shared_hash_find (set->vars, dv);
+ var = htab_find_dv (set->vars, dv);
if (var)
{
/* Although variable_post_merge_new_vals may have made decls
@@ -4042,7 +3879,7 @@ variable_post_merge_perm_vals (void **ps
REG, so they are canonical as well. Since VAR has the
location list for a VALUE, using find_loc_in_1pdv for it is
fine, since VALUEs don't map back to DECLs. */
- if (find_loc_in_1pdv (pnode->loc, var, shared_hash_htab (set->vars)))
+ if (find_loc_in_1pdv (pnode->loc, var, set->vars))
return 1;
val_reset (set, dv);
}
@@ -4083,13 +3920,11 @@ dataflow_post_merge_adjust (dataflow_set
dfpm.set = set;
dfpm.permp = permp;
- htab_traverse (shared_hash_htab (set->vars), variable_post_merge_new_vals,
- &dfpm);
+ htab_traverse (set->vars, variable_post_merge_new_vals, &dfpm);
if (*permp)
- htab_traverse (shared_hash_htab ((*permp)->vars),
- variable_post_merge_perm_vals, &dfpm);
- htab_traverse (shared_hash_htab (set->vars), canonicalize_values_star, set);
- htab_traverse (shared_hash_htab (set->vars), canonicalize_vars_star, set);
+ htab_traverse ((*permp)->vars, variable_post_merge_perm_vals, &dfpm);
+ htab_traverse (set->vars, canonicalize_values_star, set);
+ htab_traverse (set->vars, canonicalize_vars_star, set);
}
/* Return a node whose loc is a MEM that refers to EXPR in the
@@ -4111,7 +3946,7 @@ find_mem_expr_in_1pdv (tree expr, rtx va
&& !VALUE_RECURSED_INTO (val));
dv = dv_from_value (val);
- var = (variable) htab_find_with_hash (vars, dv, dv_htab_hash (dv));
+ var = htab_find_dv (vars, dv);
if (!var)
return NULL;
@@ -4187,7 +4022,7 @@ dataflow_set_preserve_mem_locs (void **s
gcc_assert (var->n_var_parts == 1);
- if (shared_var_p (var, set->vars))
+ if (shared_var_p (var))
{
for (loc = var->var_part[0].loc_chain; loc; loc = loc->next)
{
@@ -4199,8 +4034,7 @@ dataflow_set_preserve_mem_locs (void **s
break;
/* We want to move here MEMs that do refer to DECL. */
else if (GET_CODE (loc->loc) == VALUE
- && find_mem_expr_in_1pdv (decl, loc->loc,
- shared_hash_htab (set->vars)))
+ && find_mem_expr_in_1pdv (decl, loc->loc, set->vars))
break;
}
@@ -4219,8 +4053,7 @@ dataflow_set_preserve_mem_locs (void **s
if (GET_CODE (old_loc) == VALUE)
{
location_chain mem_node
- = find_mem_expr_in_1pdv (decl, loc->loc,
- shared_hash_htab (set->vars));
+ = find_mem_expr_in_1pdv (decl, loc->loc, set->vars);
/* ??? This picks up only one out of multiple MEMs that
refer to the same variable. Do we ever need to be
@@ -4298,7 +4131,7 @@ dataflow_set_remove_mem_locs (void **slo
gcc_assert (var->n_var_parts == 1);
- if (shared_var_p (var, set->vars))
+ if (shared_var_p (var))
{
for (loc = var->var_part[0].loc_chain; loc; loc = loc->next)
if (GET_CODE (loc->loc) == MEM
@@ -4365,11 +4198,9 @@ dataflow_set_clear_at_call (dataflow_set
if (MAY_HAVE_DEBUG_INSNS)
{
set->traversed_vars = set->vars;
- htab_traverse (shared_hash_htab (set->vars),
- dataflow_set_preserve_mem_locs, set);
+ htab_traverse (set->vars, dataflow_set_preserve_mem_locs, set);
set->traversed_vars = set->vars;
- htab_traverse (shared_hash_htab (set->vars), dataflow_set_remove_mem_locs,
- set);
+ htab_traverse (set->vars, dataflow_set_remove_mem_locs, set);
set->traversed_vars = NULL;
}
}
@@ -4470,15 +4301,12 @@ dataflow_set_different (dataflow_set *ol
if (old_set->vars == new_set->vars)
return false;
- if (htab_elements (shared_hash_htab (old_set->vars))
- != htab_elements (shared_hash_htab (new_set->vars)))
+ if (htab_elements (old_set->vars) != htab_elements (new_set->vars))
return true;
- FOR_EACH_HTAB_ELEMENT (shared_hash_htab (old_set->vars), var1, variable, hi)
+ FOR_EACH_HTAB_ELEMENT (old_set->vars, var1, variable, hi)
{
- htab_t htab = shared_hash_htab (new_set->vars);
- variable var2 = (variable) htab_find_with_hash (htab, var1->dv,
- dv_htab_hash (var1->dv));
+ variable var2 = htab_find_dv (new_set->vars, var1->dv);
if (!var2)
{
if (dump_file && (dump_flags & TDF_DETAILS))
@@ -4519,7 +4347,10 @@ dataflow_set_destroy (dataflow_set *set,
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
attrs_list_clear (&set->regs[i]);
- shared_hash_destroy (set->vars, do_free);
+ if (!do_free)
+ /* Dirty hack to prevent htab_delete() iterating over all elements */
+ set->vars->del_f = NULL;
+ htab_delete (set->vars);
set->vars = NULL;
}
@@ -6039,7 +5870,7 @@ find_src_set_src (dataflow_set *set, rtx
{
decl_or_value dv = dv_from_decl (decl);
- var = shared_hash_find (set->vars, dv);
+ var = htab_find_dv (set->vars, dv);
if (var)
{
found = false;
@@ -6338,13 +6169,10 @@ compute_bb_dataflow (basic_block bb)
if (MAY_HAVE_DEBUG_INSNS)
{
dataflow_set_equiv_regs (out);
- htab_traverse (shared_hash_htab (out->vars), canonicalize_values_mark,
- out);
- htab_traverse (shared_hash_htab (out->vars), canonicalize_values_star,
- out);
+ htab_traverse (out->vars, canonicalize_values_mark, out);
+ htab_traverse (out->vars, canonicalize_values_star, out);
#if ENABLE_CHECKING
- htab_traverse (shared_hash_htab (out->vars),
- canonicalize_loc_order_check, out);
+ htab_traverse (out->vars, canonicalize_loc_order_check, out);
#endif
}
changed = dataflow_set_different (&old_out, out);
@@ -6415,27 +6243,24 @@ vt_find_locations (void)
if (VTI (bb)->in.vars)
{
- htabsz
- -= (htab_size (shared_hash_htab (VTI (bb)->in.vars))
- + htab_size (shared_hash_htab (VTI (bb)->out.vars)));
- oldinsz
- = htab_elements (shared_hash_htab (VTI (bb)->in.vars));
- oldoutsz
- = htab_elements (shared_hash_htab (VTI (bb)->out.vars));
+ htabsz -= (htab_size (VTI (bb)->in.vars)
+ + htab_size (VTI (bb)->out.vars));
+ oldinsz = htab_elements (VTI (bb)->in.vars);
+ oldoutsz = htab_elements (VTI (bb)->out.vars);
}
else
oldinsz = oldoutsz = 0;
if (MAY_HAVE_DEBUG_INSNS)
{
- dataflow_set *in = &VTI (bb)->in, *first_out = NULL;
+ dataflow_set *in = &VTI (bb)->in;
+ /* dataflow_set *first_out = NULL; */
bool first = true, adjust = false;
/* Calculate the IN set as the intersection of
predecessor OUT sets. */
dataflow_set_clear (in);
- dst_can_be_shared = true;
FOR_EACH_EDGE (e, ei, bb->preds)
if (!VTI (e->src)->flooded)
@@ -6444,7 +6269,7 @@ vt_find_locations (void)
else if (first)
{
dataflow_set_copy (in, &VTI (e->src)->out);
- first_out = &VTI (e->src)->out;
+ /* first_out = &VTI (e->src)->out; */
first = false;
}
else
@@ -6459,15 +6284,9 @@ vt_find_locations (void)
#if ENABLE_CHECKING
/* Merge and merge_adjust should keep entries in
canonical order. */
- htab_traverse (shared_hash_htab (in->vars),
- canonicalize_loc_order_check,
+ htab_traverse (in->vars, canonicalize_loc_order_check,
in);
#endif
- if (dst_can_be_shared)
- {
- shared_hash_destroy (in->vars, true);
- in->vars = shared_hash_copy (first_out->vars);
- }
}
VTI (bb)->flooded = true;
@@ -6481,8 +6300,8 @@ vt_find_locations (void)
}
changed = compute_bb_dataflow (bb);
- htabsz += (htab_size (shared_hash_htab (VTI (bb)->in.vars))
- + htab_size (shared_hash_htab (VTI (bb)->out.vars)));
+ htabsz += (htab_size (VTI (bb)->in.vars)
+ + htab_size (VTI (bb)->out.vars));
if (htabmax && htabsz > htabmax)
{
@@ -6529,11 +6348,11 @@ vt_find_locations (void)
fprintf (dump_file,
"BB %i: in %i (was %i), out %i (was %i), rem %i + %i, tsz %i\n",
bb->index,
- (int)htab_elements (shared_hash_htab (VTI (bb)->in.vars)),
+ (int) htab_elements (VTI (bb)->in.vars),
oldinsz,
- (int)htab_elements (shared_hash_htab (VTI (bb)->out.vars)),
+ (int) htab_elements (VTI (bb)->out.vars),
oldoutsz,
- (int)worklist->nodes, (int)pending->nodes, htabsz);
+ (int) worklist->nodes, (int) pending->nodes, htabsz);
if (dump_file && (dump_flags & TDF_DETAILS))
{
@@ -6664,7 +6483,7 @@ dump_dataflow_set (dataflow_set *set)
dump_attrs_list (set->regs[i]);
}
}
- dump_vars (shared_hash_htab (set->vars));
+ dump_vars (set->vars);
fprintf (dump_file, "\n");
}
@@ -6745,14 +6564,9 @@ variable_was_changed (variable var, data
void **slot;
drop_var:
- slot = shared_hash_find_slot_noinsert (set->vars, var->dv);
+ slot = htab_slot_dv (set->vars, var->dv, NO_INSERT);
if (slot)
- {
- if (shared_hash_shared (set->vars))
- slot = shared_hash_find_slot_unshare (&set->vars, var->dv,
- NO_INSERT);
- htab_clear_slot (shared_hash_htab (set->vars), slot);
- }
+ htab_clear_slot (set->vars, slot);
}
}
}
@@ -6913,7 +6727,7 @@ set_slot_part (dataflow_set *set, rtx lo
if (r == 0)
return slot;
- if (shared_var_p (var, set->vars))
+ if (shared_var_p (var))
{
slot = unshare_variable (set, slot, var, initialized);
var = (variable)*slot;
@@ -6952,7 +6766,7 @@ set_slot_part (dataflow_set *set, rtx lo
else
{
/* We have to make a copy of a shared variable. */
- if (shared_var_p (var, set->vars))
+ if (shared_var_p (var))
{
slot = unshare_variable (set, slot, var, initialized);
var = (variable)*slot;
@@ -6964,7 +6778,7 @@ set_slot_part (dataflow_set *set, rtx lo
/* We have not found the location part, new one will be created. */
/* We have to make a copy of the shared variable. */
- if (shared_var_p (var, set->vars))
+ if (shared_var_p (var))
{
slot = unshare_variable (set, slot, var, initialized);
var = (variable)*slot;
@@ -7049,14 +6863,8 @@ set_variable_part (dataflow_set *set, rt
{
void **slot;
- if (iopt == NO_INSERT)
- slot = shared_hash_find_slot_noinsert (set->vars, dv);
- else
- {
- slot = shared_hash_find_slot (set->vars, dv);
- if (!slot)
- slot = shared_hash_find_slot_unshare (&set->vars, dv, iopt);
- }
+ slot = htab_slot_dv (set->vars, dv, iopt);
+
set_slot_part (set, loc, slot, dv, offset, initialized, set_src);
}
@@ -7134,7 +6942,7 @@ clobber_variable_part (dataflow_set *set
|| (!dv_is_value_p (dv) && ! DECL_P (dv_as_decl (dv))))
return;
- slot = shared_hash_find_slot_noinsert (set->vars, dv);
+ slot = htab_slot_dv (set->vars, dv, NO_INSERT);
if (!slot)
return;
@@ -7158,7 +6966,7 @@ delete_slot_part (dataflow_set *set, rtx
location_chain *nextp;
bool changed;
- if (shared_var_p (var, set->vars))
+ if (shared_var_p (var))
{
/* If the variable contains the location part we have to
make a copy of the variable. */
@@ -7233,7 +7041,7 @@ static void
delete_variable_part (dataflow_set *set, rtx loc, decl_or_value dv,
HOST_WIDE_INT offset)
{
- void **slot = shared_hash_find_slot_noinsert (set->vars, dv);
+ void **slot = htab_slot_dv (set->vars, dv, NO_INSERT);
if (!slot)
return;
@@ -7330,7 +7138,7 @@ vt_expand_loc_callback (rtx x, bitmap re
if (VALUE_RECURSED_INTO (x))
return NULL;
- var = (variable) htab_find_with_hash (elcd->vars, dv, dv_htab_hash (dv));
+ var = htab_find_dv (elcd->vars, dv);
if (!var)
{
@@ -7710,19 +7518,18 @@ static VEC (rtx, heap) *changed_values_s
/* Helper function for check_changed_vars_1 and check_changed_vars_2. */
static void
-check_changed_vars_0 (decl_or_value dv, htab_t htab)
+check_changed_vars_0 (decl_or_value dv, htab_t vars)
{
value_chain vc
- = (value_chain) htab_find_with_hash (value_chains, dv, dv_htab_hash (dv));
+ = (value_chain) htab_find_with_hash (value_chains, dv,
+ dv_htab_hash (dv));
if (vc == NULL)
return;
for (vc = vc->next; vc; vc = vc->next)
if (!dv_changed_p (vc->dv))
{
- variable vcvar
- = (variable) htab_find_with_hash (htab, vc->dv,
- dv_htab_hash (vc->dv));
+ variable vcvar = htab_find_dv (vars, vc->dv);
if (vcvar)
{
set_dv_changed (vc->dv, true);
@@ -7733,7 +7540,7 @@ check_changed_vars_0 (decl_or_value dv,
set_dv_changed (vc->dv, true);
VEC_safe_push (rtx, heap, changed_values_stack,
dv_as_value (vc->dv));
- check_changed_vars_0 (vc->dv, htab);
+ check_changed_vars_0 (vc->dv, vars);
}
}
}
@@ -7813,11 +7620,9 @@ check_changed_vars_3 (void **slot, void
shall be emitted before of after instruction INSN. */
static void
-emit_notes_for_changes (rtx insn, enum emit_note_where where,
- shared_hash vars)
+emit_notes_for_changes (rtx insn, enum emit_note_where where, htab_t vars)
{
emit_note_data data;
- htab_t htab = shared_hash_htab (vars);
if (!htab_elements (changed_variables))
return;
@@ -7827,19 +7632,19 @@ emit_notes_for_changes (rtx insn, enum e
/* Unfortunately this has to be done in two steps, because
we can't traverse a hashtab into which we are inserting
through variable_was_changed. */
- htab_traverse (changed_variables, check_changed_vars_1, htab);
+ htab_traverse (changed_variables, check_changed_vars_1, vars);
while (VEC_length (variable, changed_variables_stack) > 0)
check_changed_vars_2 (VEC_pop (variable, changed_variables_stack),
- htab);
+ vars);
while (VEC_length (rtx, changed_values_stack) > 0)
set_dv_changed (dv_from_value (VEC_pop (rtx, changed_values_stack)),
false);
- htab_traverse (changed_variables, check_changed_vars_3, htab);
+ htab_traverse (changed_variables, check_changed_vars_3, vars);
}
data.insn = insn;
data.where = where;
- data.vars = htab;
+ data.vars = vars;
htab_traverse (changed_variables, emit_note_insn_var_location, &data);
}
@@ -7854,8 +7659,7 @@ emit_notes_for_differences_1 (void **slo
variable old_var, new_var;
old_var = (variable) *slot;
- new_var = (variable) htab_find_with_hash (new_vars, old_var->dv,
- dv_htab_hash (old_var->dv));
+ new_var = htab_find_dv (new_vars, old_var->dv);
if (!new_var)
{
@@ -7947,8 +7751,7 @@ emit_notes_for_differences_2 (void **slo
variable old_var, new_var;
new_var = (variable) *slot;
- old_var = (variable) htab_find_with_hash (old_vars, new_var->dv,
- dv_htab_hash (new_var->dv));
+ old_var = htab_find_dv(old_vars, new_var->dv);
if (!old_var)
{
int i;
@@ -7977,12 +7780,8 @@ static void
emit_notes_for_differences (rtx insn, dataflow_set *old_set,
dataflow_set *new_set)
{
- htab_traverse (shared_hash_htab (old_set->vars),
- emit_notes_for_differences_1,
- shared_hash_htab (new_set->vars));
- htab_traverse (shared_hash_htab (new_set->vars),
- emit_notes_for_differences_2,
- shared_hash_htab (old_set->vars));
+ htab_traverse (old_set->vars, emit_notes_for_differences_1, new_set->vars);
+ htab_traverse (new_set->vars, emit_notes_for_differences_2, old_set->vars);
emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN, new_set->vars);
}
@@ -8011,8 +7810,7 @@ emit_notes_in_bb (basic_block bb, datafl
while (*p)
{
XEXP (XEXP (*p, 0), 1)
- = vt_expand_loc (XEXP (XEXP (*p, 0), 1),
- shared_hash_htab (set->vars), true);
+ = vt_expand_loc (XEXP (XEXP (*p, 0), 1), set->vars, true);
/* If expansion is successful, keep it in the list. */
if (XEXP (XEXP (*p, 0), 1))
p = &XEXP (*p, 1);
@@ -8339,9 +8137,7 @@ vt_emit_notes (void)
dataflow_set_clear (&VTI (bb)->in);
}
#ifdef ENABLE_CHECKING
- htab_traverse (shared_hash_htab (cur.vars),
- emit_notes_for_differences_1,
- shared_hash_htab (empty_shared_hash));
+ htab_traverse (cur.vars, emit_notes_for_differences_1, empty_htab);
if (MAY_HAVE_DEBUG_INSNS)
{
unsigned int i;
@@ -8703,13 +8499,9 @@ vt_initialize (void)
loc_chain_pool = create_alloc_pool ("location_chain_def pool",
sizeof (struct location_chain_def),
1024);
- shared_hash_pool = create_alloc_pool ("shared_hash_def pool",
- sizeof (struct shared_hash_def), 256);
- empty_shared_hash = (shared_hash) pool_alloc (shared_hash_pool);
- empty_shared_hash->refcount = 1;
- empty_shared_hash->htab
- = htab_create (1, variable_htab_hash, variable_htab_eq,
- variable_htab_free);
+ /* htab_pool = create_alloc_pool ("htab pool", sizeof (*htab_t), 256); */
+ empty_htab = htab_create (1, variable_htab_hash, variable_htab_eq,
+ variable_htab_free);
changed_variables = htab_create (10, variable_htab_hash, variable_htab_eq,
variable_htab_free);
if (MAY_HAVE_DEBUG_INSNS)
@@ -9017,12 +8809,11 @@ vt_finalize (void)
}
}
free_aux_for_blocks ();
- htab_delete (empty_shared_hash->htab);
+ htab_delete (empty_htab);
htab_delete (changed_variables);
free_alloc_pool (attrs_pool);
free_alloc_pool (var_pool);
free_alloc_pool (loc_chain_pool);
- free_alloc_pool (shared_hash_pool);
if (MAY_HAVE_DEBUG_INSNS)
{
^ permalink raw reply [flat|nested] 9+ messages in thread