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

["law at redhat dot com" <gcc-bugzilla at gcc dot gnu dot org>]

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

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