[Bug tree-optimization/64058] [5/6 Regression] Performance degradation after r216304

["rguenther at suse dot de" <gcc-bugzilla at gcc dot gnu dot org>]

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

--- Comment #15 from rguenther at suse dot de <rguenther at suse dot de> ---
On Wed, 9 Mar 2016, law at redhat dot com wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64058
> 
> --- Comment #13 from Jeffrey A. Law <law at redhat dot com> ---
> Stabilizing the sort is just one piece in the problem.  SSA_NAME_VERSIONs are
> also used as partition numbers.  That doesn't seem to impact code generation
> (so far), but it does make dump comparisons bloody difficult to really analyze.
> 
> That's what really got me thinking about this problem -- the fact that changes
> in the version #s not only affect code generation, but they make it orders of
> magnitude harder to evaluate whether or not stabilizing the sort is all that's
> needed to address the performance concerns due to gratutious changes in the
> dump files.
> 
> The result of those ponderings was the idea that changing SSA_NAME_VERSIONs
> should have zero impact on the code we generate.  We should be able to hand out
> names in a totally arbitrary order and ultimately get the same assembly code.
> 
> Reality is somewhat different.  Consider that in various places we canonicalize
> expression operands based on SSA_NAME_VERSIONs.  Those can and will get
> different code based on SSA_NAME_VERSIONs in use.  ie
> 
> if (a_1 == b_2)
> 
> if (a_2 == b_1)
> 
> Should generate the same assembly code, but won't because the second will get
> canonicalized into
> 
> if (b_1 == a_2)
> 
> And when we convert that to RTL, it'll generate different code than the
> original a_1 == b_2 version.
> 
> Similar situations occur due to canonicalization that happens during
> tree-ssa-reassoc and almost certainly other places.
> 
> It's pervasive enough that the goal of "no change in assembly output due to
> SSA_NAME_VERSION changes" may not be attainable in the immediate future.

Yes.  Same is true with pseudo numbers in RTL.  We even have code-gen
effects when you change DECL_UID ordering.

> Coming back to 64058 and 68654, it's not clear yet if just stabilizing the sort
> is sufficient.  I'm still evaluating that.

I still think stabilizing the sort is a good thing on its own, after that
we can look at walking the CFG in a more sensible order in
create_outofssa_var_map rather than with FOR_EACH_BB_FN.

Of course in the end to fix 64058 and 68654 reliably we need a way
to assign higher cost to the important coalesce or implement a
less greedy way of finding the optimal coalesce set thus don't always
just pick the highest cost coalesce but do something that gets closer
to the optimal overall "cost" achieved after all coalescing is done.
Of course we can't find the optimal solution as that is a NP hard
problem to solve.  Maybe for 64058 and 68654 it's enough to split
live-ranges of some SSA vars at strategic points (insert copies
that also get coalesce candidates but with lower priority than the
important ones).  We do that already in rewrite_out_of_ssa to avoid
copies on loop backedges by splitting the live-range in the loop
itself.  Similar logic (avoid splitting an edge) can be applied
to any PHI arg with a critical edge.

Still 64058 and 68654 lack proper analysis which coalesces are
important and no longer performed and why (thus a way to identify
those).

> FWIW, I've got a variant that just stabilizes the sort with just an index we
> record as we find a potential coalescing pair.  That's pretty trivial.

I think this would help debugging this kind of issues a lot already
(together with maybe changing the BB walk producing the coalesce pairs).

> I started down another path where I added a level of indirection between the
> SSA_NAME_VERSION and the associated partition maps.  My worry with the latter
> is interactions with tree-ssa-live.c.

Yeah, I think this would be over-engineering.