From 600be7f09ea1ea4b59e4e733fda2aca3ba892a6b Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Fri, 6 Nov 2020 16:57:05 +0100 Subject: [PATCH] rework PRE PHI translation cache Turns out its size and time requirements can be stripped down dramatically. 2020-11-06 Richard Biener * 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 +typedef struct expr_pred_trans_d : public typed_noop_remove { - /* 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 *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.30.2