[Bug tree-optimization/69580] [6 Regression] From 26 seconds to 10 minutes moving from gcc 5.3.1 to gcc 6.0.0

["law at redhat dot com" <gcc-bugzilla at gcc dot gnu dot org>]

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

--- Comment #4 from Jeffrey A. Law <law at redhat dot com> ---
So for the testcase we've got merge points with huge numbers of predecessors,
which as I mentioned before we dutifully try finding paths through each one.

I instrumented the compiler a bit to see what kind of distribution we see in
this code.  I was interested primarily interested in the number of PHI
arguments, but also the number of threaded paths was recorded.

Not surprisingly, the distribution is heavily skewed towards small numbers of
PHI arguments (ie, 2-5).  The largest PHI in GCC an its shared libraries was on
the order of 256 entries, but it was pretty clear handling cases up to 100
would catch the overwhelming majority of cases.  That also sets the bar at one
order of magnitude lower than what the attached testcase needs to not explode.

In terms of # paths threaded in those big nodes, it tends to be either a bunch
(roughly half) or none.  I didn't investigate the bi-modal nature, though I do
know in the provided testcase the thread paths require memory simplifications
to be able to see the jump thread path.  That means they'll need to be picked
up by the old threader when called from DOM,   DOM threads ~2600 paths, so it
seems to be doing its job.

In general, the number of threaded paths wasn't all that interesting as a
datapoint.

With the limiter, the time should come back down into the reasonable range and
I'm going drop this to a P4 once that change goes in.  However, I'm going to
keep this open because I think fsm_find_thread_path is horrible in the amount
of work it duplicates and needs to be rewritten.  It likely accounts for the
remainder of the compile-time performance issues with this test when compared
to gcc-4.9.