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. -- Maxim Kuvyrkov www.linaro.org
