[Bug tree-optimization/62291] PRE uses too much memory and compile-time

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62291

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
So what remains is insertion computing whether a value is available on some
predecessor (partial redundancy) or all (full redundancy) which needs AVAIL_OUT
for the predecessors and the immediate dominator.

Then the actual insertion code needs to lookup leaders for expression operands
it wants to insert.  I think this part can be easily delayed until eliminate
if we store all necessary information in some new data structure.

The first part is harder - especially as it is that what needs to be iterated
(with taking into account newly inserted stuff).  One could imagine
iterating over sucessors of a block (and immediate dominated-bys) and compute
"candidate" sets, both pruning and extending it during the iteration.