Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

[Maxim Kuvyrkov <maxim dot kuvyrkov at linaro dot org>]

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.

Thank you,

--
Maxim Kuvyrkov
www.linaro.org