Turns out its size and time requirements can be stripped down
dramatically.
Bootstrap & regtest running on x86_64-unknown-linux-gnu.
2020-11-06 Richard Biener <rguent...@suse.de>
* tree-ssa-pre.c (expr_pred_trans_d): Modify so elements
are embedded rather than allocated. Remove hashval member,
make all members integers.
(phi_trans_add): Adjust accordingly.
(phi_translate): Likewise. Deal with re-allocation
of the table.
---
gcc/tree-ssa-pre.c | 104 +++++++++++++++++++++++++++++----------------
1 file changed, 68 insertions(+), 36 deletions(-)
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 65e8aaaca02..3496891f8b5 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -545,45 +545,74 @@ static bitmap_obstack grand_bitmap_obstack;
/* A three tuple {e, pred, v} used to cache phi translations in the
phi_translate_table. */
-typedef struct expr_pred_trans_d : free_ptr_hash<expr_pred_trans_d>
+typedef struct expr_pred_trans_d : public typed_noop_remove <expr_pred_trans_d>
{
- /* The expression. */
- pre_expr e;
+ typedef expr_pred_trans_d value_type;
+ typedef expr_pred_trans_d compare_type;
- /* The predecessor block along which we translated the expression. */
- basic_block pred;
+ /* The expression ID. */
+ unsigned e;
- /* The value that resulted from the translation. */
- pre_expr v;
+ /* The predecessor block index along which we translated the expression. */
+ int pred;
- /* The hashcode for the expression, pred pair. This is cached for
- speed reasons. */
- hashval_t hashcode;
+ /* The value expression ID that resulted from the translation. */
+ unsigned v;
/* hash_table support. */
- static inline hashval_t hash (const expr_pred_trans_d *);
- static inline int equal (const expr_pred_trans_d *, const expr_pred_trans_d
*);
+ static inline void mark_empty (expr_pred_trans_d &);
+ static inline bool is_empty (const expr_pred_trans_d &);
+ static inline void mark_deleted (expr_pred_trans_d &);
+ static inline bool is_deleted (const expr_pred_trans_d &);
+ static const bool empty_zero_p = true;
+ static inline hashval_t hash (const expr_pred_trans_d &);
+ static inline int equal (const expr_pred_trans_d &, const expr_pred_trans_d
&);
} *expr_pred_trans_t;
typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
+inline bool
+expr_pred_trans_d::is_empty (const expr_pred_trans_d &e)
+{
+ return e.e == 0;
+}
+
+inline bool
+expr_pred_trans_d::is_deleted (const expr_pred_trans_d &e)
+{
+ return e.e == -1u;
+}
+
+inline void
+expr_pred_trans_d::mark_empty (expr_pred_trans_d &e)
+{
+ e.e = 0;
+}
+
+inline void
+expr_pred_trans_d::mark_deleted (expr_pred_trans_d &e)
+{
+ e.e = -1u;
+}
+
inline hashval_t
-expr_pred_trans_d::hash (const expr_pred_trans_d *e)
+expr_pred_trans_d::hash (const expr_pred_trans_d &e)
{
- return e->hashcode;
+ return iterative_hash_hashval_t (e.e, e.pred);
}
inline int
-expr_pred_trans_d::equal (const expr_pred_trans_d *ve1,
- const expr_pred_trans_d *ve2)
+expr_pred_trans_d::equal (const expr_pred_trans_d &ve1,
+ const expr_pred_trans_d &ve2)
{
- basic_block b1 = ve1->pred;
- basic_block b2 = ve2->pred;
+ int b1 = ve1.pred;
+ int b2 = ve2.pred;
/* If they are not translations for the same basic block, they can't
be equal. */
if (b1 != b2)
return false;
- return pre_expr_d::equal (ve1->e, ve2->e);
+
+ return ve1.e == ve2.e;
}
/* The phi_translate_table caches phi translations for a given
@@ -596,24 +625,22 @@ static hash_table<expr_pred_trans_d> *phi_translate_table;
static inline bool
phi_trans_add (expr_pred_trans_t *entry, pre_expr e, basic_block pred)
{
- expr_pred_trans_t *slot;
+ expr_pred_trans_t slot;
expr_pred_trans_d tem;
- hashval_t hash = iterative_hash_hashval_t (pre_expr_d::hash (e),
- pred->index);
- tem.e = e;
- tem.pred = pred;
- tem.hashcode = hash;
- slot = phi_translate_table->find_slot_with_hash (&tem, hash, INSERT);
- if (*slot)
+ unsigned id = get_expression_id (e);
+ hashval_t hash = iterative_hash_hashval_t (id, pred->index);
+ tem.e = id;
+ tem.pred = pred->index;
+ slot = phi_translate_table->find_slot_with_hash (tem, hash, INSERT);
+ if (slot->e)
{
- *entry = *slot;
+ *entry = slot;
return true;
}
- *entry = *slot = XNEW (struct expr_pred_trans_d);
- (*entry)->e = e;
- (*entry)->pred = pred;
- (*entry)->hashcode = hash;
+ *entry = slot;
+ slot->e = id;
+ slot->pred = pred->index;
return false;
}
@@ -1675,6 +1702,7 @@ phi_translate (bitmap_set_t dest, pre_expr expr,
bitmap_set_t set1, bitmap_set_t set2, edge e)
{
expr_pred_trans_t slot = NULL;
+ size_t slot_size = 0;
pre_expr phitrans;
if (!expr)
@@ -1691,10 +1719,11 @@ phi_translate (bitmap_set_t dest, pre_expr expr,
if (expr->kind != NAME)
{
if (phi_trans_add (&slot, expr, e->src))
- return slot->v;
+ return slot->v == 0 ? NULL : expression_for_id (slot->v);
/* Store NULL for the value we want to return in the case of
recursing. */
- slot->v = NULL;
+ slot->v = 0;
+ slot_size = phi_translate_table->size ();
}
/* Translate. */
@@ -1705,12 +1734,15 @@ phi_translate (bitmap_set_t dest, pre_expr expr,
if (slot)
{
+ /* Check for reallocation. */
+ if (phi_translate_table->size () != slot_size)
+ phi_trans_add (&slot, expr, e->src);
if (phitrans)
- slot->v = phitrans;
+ slot->v = get_expression_id (phitrans);
else
/* Remove failed translations again, they cause insert
iteration to not pick up new opportunities reliably. */
- phi_translate_table->remove_elt_with_hash (slot, slot->hashcode);
+ phi_translate_table->clear_slot (slot);
}
return phitrans;
--
2.26.2
