On Jan 31, 2015, at 7:33 AM, Jeff Law <l...@redhat.com> wrote: > 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.
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
