[PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

[Richard Biener]

On January 31, 2015 9:01:02 AM CET, Maxim Kuvyrkov <maxim.kuvyrkov@linaro.org> wrote:
>On Jan 31, 2015, at 7:33 AM, Jeff Law <law@redhat.com> wrote:
>
>> On 01/22/15 12:01, Maxim Kuvyrkov wrote:
>>> 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.
>> Again, thanks for taking the time to go into the gory details.
>> 
>> ISTM the core issues are that we have heuristics in the comparison
>routine that apply to some insns and not others and we get a different
>pivot-point in the qsort because of the presence of debug insns.
>> 
>> Your solution seems as reasonable as anything.
>> 
>> Approved.
>
>Richard,
>
>Since this patches fixes a bootstrap miscompare on primary architecture
>(arm-linux-gnuebihf/-mcpu=cortex-a15) I think it qualifies for stage 4.
>Any objections to committing the patch?  It will be
>re-bootstrapped/re-tested on fresh trunk for x86_64-linux-gnu and
>arm-linux-gnueabihf before commit.

It's fine to commit.

Richard.

>Thank you,
>
>--
>Maxim Kuvyrkov
>www.linaro.org