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

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

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

--- Comment #24 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jeffrey A. Law from comment #23)
> The piece you're missing in this is that when we seen an assignment to some
> SSA_NAME, call it LHS and we've traversed a backedge, then we have to walk
> through all the equivalences and see if there's anything that's been marked
> as equivalent to LHS and invalidate those.  Then we also ahve to invalidate
> LHS.
> 
>  for (unsigned int i = 1; i < num_ssa_names; i++)
>     if (ssa_name (i) && SSA_NAME_VALUE (ssa_name (i)) == lhs)
>       record_temporary_equivalence (ssa_name (i), NULL_TREE, stack);
> 
>   if (SSA_NAME_VALUE (lhs))
>     record_temporary_equivalence (lhs, NULL_TREE, stack);
> 
> 
> The loop finds handles things equivalent to LHS, the second handles LHS
> itself.  Both are required for correctness.
> 
> In the past there was a map similar to your implementation, but it's not
> sufficient.  See pr61289.C and pr61289-2.C.
> 
> The problem is you may need to invalidate equivalences that are created
> *outside* tree-ssa-threadedge.c.  So any attempts to track inside
> tree-ssa-threadedge are not sufficient for correctness.
> 
> What's still not clear to me here is *why* we're calling the invalidation
> code in the first place.  It's only supposed to be called when we encounter
> a statement which produces an output that we can't handle *and* we've
> traversed a backedge.  The combination of those two events is supposed to be
> very rare.  Otherwise the invalidation is obviously too expensive.  That's
> why I suggested in c#12 that we need to look at *why* we're calling the
> invalidation code at all.

Well, I don't know the code at all so I can just try to fix the complexity
in the present algorithm.

Please have a look here during stage3.