[PATCH] Drop topological sort for PRE phi-translation

[PATCH] Drop topological sort for PRE phi-translation

[Richard Biener]

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.

Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.

2020-11-11  Richard Biener  <rguenther@suse.de>

	* 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<pre_expr> 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<expr_pred_trans_d> (2 * exprs.length ());
-  FOR_EACH_VEC_ELT (exprs, i, expr)
+    PHI_TRANS_TABLE (e->src) = new hash_table<expr_pred_trans_d>
+				   (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.26.2