[Bug tree-optimization/68654] [6 Regression] CoreMark Pro performance degradation

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

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu.org

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jeffrey A. Law from comment #14)
> Thanks.  This is definitely an issue with the changing version #s changing
> the ordering in which particular coalescing pairs are tried.
> 
> This is most likely coming from this (and related) code in
> tree-ssa-coalesce.c:
> 
>             case GIMPLE_ASSIGN:
>               {
>                 tree lhs = gimple_assign_lhs (stmt);
>                 tree rhs1 = gimple_assign_rhs1 (stmt);
>                 if (gimple_assign_ssa_name_copy_p (stmt)
>                     && gimple_can_coalesce_p (lhs, rhs1))
>                   {
>                     v1 = SSA_NAME_VERSION (lhs);
>                     v2 = SSA_NAME_VERSION (rhs1);
>                     cost = coalesce_cost_bb (bb);
>                     add_coalesce (cl, v1, v2, cost);
>                     bitmap_set_bit (used_in_copy, v1);
>                     bitmap_set_bit (used_in_copy, v2);
>                   }
> 
> Note how the version #s are passed into add_coalesce.
> 
> Those are then used to order the coalesce pair for hashing in
> find_coalesce_pair as well as in the qsort function compare_pairs.  They
> could easily be used elsewhere.
> 
> So while we do pull pairs out in a priority order, once the priorities are
> the same, the order selected is based on the SSA_NAME_VERSION, which, due to
> SSA_NAME recycling is effectively random.  You can see this by looking at
> the Sorted Coalesce list in the dumps.    The format is
> 
> (cost) obj1 <->obj2
> 
> If you compare the dumps you'll see that we have certain coalescing
> opportunities with the same cost, but which are ordered differently because
> of the SSA_NAME_VERSION differences.
> 
> The biggest obvious downside to coalescing  being dependent on
> SSA_NAME_VERSION is that a change in how names as returned to the name
> manager can affect code generation -- essentially causing code to improve or
> degrade in a random fashion.
> 
> One approach to fixing this problem might be to recompute the
> SSA_NAME_VERSION #s just prior to coalescing.
> 
> Essentially do a domwalk or some other walk of the IL reassigning version #s
> for the LHS operand.   This won't be 100% foolproof, but would probably be
> more stable than what we're doing now.  That may be possible in the gcc-6
> timeframe, I'm not really sure right now.

I think the easier solution is to preserve the order we created the coalesce
pairs by adding a "coalesce number" to sort against of the costs are equal.
coalesce_pair has three ints so on 64bit hosts there isn't any memory
wasted if adding another one given we go via glibc malloc for allocating
them (ugh).

Of course if that produces the desired order for the benchmark is another
question ;)  (it's really random before as well)

But comment #8 also still holds (keep the free ssa name list we allocate
from sorted to pack names dense).