[Bug rtl-optimization/117922] [15 Regression] 1000% compilation time slow down on the testcase from pr26854

[rguenth at gcc dot gnu.org]

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

--- Comment #24 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Paolo Bonzini from comment #22)
> Yes, I suggested the MD problem because it did solve gambit performance
> issues with fwprop for good, but RTL-SSA is certainly applicable.
> 
> Also, once all RD uses are converted to RTL-SSA it should really be removed
> from df.c as a bad idea (and probably also MD since it's unused *sheds a
> tear*).

Btw, all of UD/DU_CHAINS should be converted.

For the testcase at hand all 61152 blocks are in a single big cycle, so
optimizing the RD dataflow iteration looks difficult, it's just very
cache unfriendly.

df_worklist_dataflow_doublequeue: n_basic_blocks 61152 n_edges 48183769 count
378895 (  6.2)

it's the no longer factored computed goto that blows up the number of edges
and thus the computational complexity here.  See the bug about bb-reorder
where we'd suggested to keep the actual CFG representation factored but
have the computed goto instruction duplicated.