[PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

[Maxim Kuvyrkov]

On Jan 22, 2015, at 8:11 PM, Jeff Law <law@redhat.com> wrote:

> On 01/19/15 06:07, Maxim Kuvyrkov wrote:
>> 
>> The underlying problem is that the order in which elements of
>> ready_list are compared matters to the final result.  This is because
>> rank_for_schedule sorting heuristic establishes a partial order on
>> the set of instructions, and it can happen that with 3 instructions
>> A, B and C: A>B, B>C, C>A.  In this situation the order in which
>> qsort compares the elements affects the final result, it can be
>> either ABC or BCA or CAB.
> So how precisely do we get A > B, B > C and C > A?   Unless I'm missing something, that seems to be an extremely bad result from rank_for_schedule.

This happens when all 3 instructions have (1) same priority, and (2) only two of the three instructions are comparable on a "selective" heuristic.  "Selective" means that a heuristic only applies to a subset of instructions, e.g., comparing speculative instructions among themselves (ia64), or comparing memory operations among themselves (what ached auto-prefetcher model does).

Let's say that A and B are memory instructions and A < B as decided by autoprefetcher heuristic.  C is not a memory instruction, and its rank resolved by comparing number of forward dependencies to those of A and B.  Specifically, B has less forward dependencies than C, so B < C, but A has more forward dependencies than C, so C < A.

Code-quality-wise, this quirk of rank_for_schedule is harmless, since it occurs only for very similarly-ranked instructions.  The problem appears only when length of ready_list changes (due to DEBUG_INSNs) as that can cause different pairs of instructions to be compared.

--
Maxim Kuvyrkov
www.linaro.org