On 01/22/15 12:01, Maxim Kuvyrkov wrote:
On Jan 22, 2015, at 8:11 PM, Jeff Law <l...@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.
THanks,
Jeff
