Drop topological sort for PRE phi-translation
authorRichard Biener <rguenther@suse.de>
Wed, 11 Nov 2020 09:18:47 +0000 (10:18 +0100)
committerRichard Biener <rguenther@suse.de>
Wed, 11 Nov 2020 10:50:17 +0000 (11:50 +0100)
commit57f076655eaaa03ae4b63408e25438d3caa20b4d
tree6264b1dd475400a36d8b2495421b5a13c5f5bc5a
parentc76c23a0da27f6a5583490893b82a82002691a90
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  <rguenther@suse.de>

* tree-ssa-pre.c (phi_translate_set): Do not sort the
expression set topologically.
gcc/tree-ssa-pre.c