[Bug tree-optimization/61515] [4.9/5 Regression] Extremely long compile time for generated code

["rguenth at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

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

--- Comment #26 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jeffrey A. Law from comment #25)
> So I think there's another approach.  invalidate_equivalences is passed in
> the stack of temporary equivalences, which include those created by jump
> threading as well as those created by DOM.
> 
> This means that in theory, we could walk that stack (in reverse order) to
> find all the equivalences we need to invalidate.  If the stack has fewer
> entries than we have SSA_NAMES, then we win.
> 
> For the stripped down testcase in this PR we go from ~40 seconds to ~1
> second in the relevant part of the compiler with a hack that does exactly
> what's described above.
> 
> I need to do a bit more review/research, but it looks like a promising
> alternative.

Huh, I thought I suggested that somewhere but you said the information is not
available here.

But yes, this sounds exactly what we want to do complexity-wise.  I suppose
we would need to amend the stack of tempoary equivalences to record the
basic-block we are creating the actual set of equivalences for (to be able
to terminate the walk?)