[PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

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

Hi,

Even though I have bootstrapped and tested the autoprefetch patch before checking it in, I missed the -mcpu=cortex-a15 setting, so I bootstrapped without autoprefetch model being active.  Turning the autoprefetch on revealed an interesting bootstrap miscompare problem.  I'm sorry I didn't spot this before checking in autoprefetch patch.

The bug this patch fixes was latent since introduction of DEBUG_INSNs.  It can be reproduced on, at least, ia64, and, I believe, most other targets too.  The bug can't cause wrong code, and only affects code "sameness" with and without debugging information enabled.

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.

Presence or absence of DEBUG_INSNs in the ready list can change the comparison order, and cause slightly different instruction schedules.

I have thought what the best fix is, and it seems unrealistic to convert rank_for_schedule into a absolute-order heuristic without sacrificing its performance.

The solution that I propose (and that the patch implements) is to sort DEBUG_INSNs separately from normal insns.  If DEBUG_INSNs are present in the ready_list, sort the DEBUG_INSNs only among themselves, while preserving order of the normal insns.  Once there are no DEBUG_INSNs in the ready list, sort using the rank_for_schedule heuristic, just as when we would when compiling without debug info.

Bootstrapped and regtested on arm-linux-gnueabihf/cortex-a15.

OK to commit?

Thank you,

--
Maxim Kuvyrkov
www.linaro.org

Attachment: 0001-Fix-scheduling-undeterminism-from-sorting-with-DEBUG.patch
Description: Binary data