From 57f076655eaaa03ae4b63408e25438d3caa20b4d Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Wed, 11 Nov 2020 10:18:47 +0100 Subject: [PATCH] Drop topological sort for PRE phi-translation The topological sort sorted_array_from_bitmap_set is supposed to provide isn't one since quite some time since value_ids are assigned first to SSA names in the order of SSA_NAME_VERSION and then to hashtable entries in the order they appear in the table. One can even argue that expression-ids provide a closer approximation of a topological sort since those are assigned during AVAIL_OUT computation which is done in a dominator walk. Now - phi-translation is not even depending on topological sorting but it essentially does a DFS walk, phi-translating expressions it depends on and relying on phi-translation caching to avoid doing redundant work. So this patch drops the use of sorted_array_from_bitmap_set from phi_translate_set because this function is quite expensive. 2020-11-11 Richard Biener * tree-ssa-pre.c (phi_translate_set): Do not sort the expression set topologically. --- gcc/tree-ssa-pre.c | 17 +++++++---------- 1 file changed, 7 insertions(+), 10 deletions(-) diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index 90877e3c68e..da2b68909d9 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -1762,9 +1762,8 @@ phi_translate (bitmap_set_t dest, pre_expr expr, static void phi_translate_set (bitmap_set_t dest, bitmap_set_t set, edge e) { - vec exprs; - pre_expr expr; - int i; + bitmap_iterator bi; + unsigned int i; if (gimple_seq_empty_p (phi_nodes (e->dest))) { @@ -1772,24 +1771,22 @@ phi_translate_set (bitmap_set_t dest, bitmap_set_t set, edge e) return; } - exprs = sorted_array_from_bitmap_set (set); /* Allocate the phi-translation cache where we have an idea about its size. hash-table implementation internals tell us that allocating the table to fit twice the number of elements will make sure we do not usually re-allocate. */ if (!PHI_TRANS_TABLE (e->src)) - PHI_TRANS_TABLE (e->src) - = new hash_table (2 * exprs.length ()); - FOR_EACH_VEC_ELT (exprs, i, expr) + PHI_TRANS_TABLE (e->src) = new hash_table + (2 * bitmap_count_bits (&set->expressions)); + FOR_EACH_EXPR_ID_IN_SET (set, i, bi) { - pre_expr translated; - translated = phi_translate (dest, expr, set, NULL, e); + pre_expr expr = expression_for_id (i); + pre_expr translated = phi_translate (dest, expr, set, NULL, e); if (!translated) continue; bitmap_insert_into_set (dest, translated); } - exprs.release (); } /* Find the leader for a value (i.e., the name representing that -- 2.30.2