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.
