[Bug rtl-optimization/90001] Compile-time hog in swing modulo scheduler

[zhroma at ispras dot ru]

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

--- Comment #4 from Roman Zhuykov <zhroma at ispras dot ru> ---
Thanks for testcase.
2-3 weeks ago I already caught and fixed this on my local branch, see some info
in the bottom.

Current algorithm which finds recurrence_length for all DDG strongly connected
components works in like O(N^6) time, where N in the number of nodes in DDG.
The time is so bad mostly for graphs with lots of edges, like almost N^2 edges.
Richard's suggestion is right - it will be still something like O(N^5) in worst
case even without bitmap overhead for such graphs. My proposed algorithm works
in O(N^3). Algorithm of finding SCCs itself is also not optimal (maybe up to
O(N^4)), but here it left untouched.

For some situations, when amount of edges is smaller (like equal to N), new
algorithm can be unfortunately slower than old one. But I think it's better
here to add some bail-out when we got more than 1000 nodes for example.

Before creating this patch, I tested special version of it, where both
approaches were in action and asserts were inserted to check that algorithms
results (longest_simple_path values) are absolutely the same. I can publish
this special version if needed.

I wonder how regression test can be created for such a situation?

[Testing]
Proposed patch with a bunch of ~25 other patches was tested a lot:
*(1) Bootstrapped and regtested on x86_64
*(2) Cross-compiler regtest on aarch64, arm, powerpc, powerpc64, ia64 and s390
*(3) Also done (1) and (2) with -fmodulo-sched enabled by default
*(4) Also done (1) and (2) with -fmodulo-sched and
-fmodulo-sched-allow-regmoves enabled by default
*(5) Moreover, all (1-4) was also done with 4.9, 5, 6, 7, and 8 branches, on
active branches an trunk date was 20190327.

More than 250 compiler instances built and tested in total (counting
both "unpatched" vs "patched").
No new failures which can relate to this algorithm were found.
"Special version" was also tested in practically same scenarios (and one more
week before, like 20190320), but not exactly all of them.

But still have to retest it separately without all my stuff :)

[PS] Last month I spent a lot of time updating my patches described here
https://gcc.gnu.org/ml/gcc-patches/2017-02/msg01647.html and have locally added
several other patches, including this fix. My updated branches are not
published yet, because there are still some unsolved issues, I can't fix some
bugzilla PRs also. I'll try to add comments in another modulo-sched-related PRs
soon.