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

[law at redhat dot com]

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

--- Comment #23 from Jeffrey A. Law <law at redhat dot com> ---
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.