On Jan 19, 2015, at 4:34 PM, Alexander Monakov <amona...@ispras.ru> wrote:
> On Mon, 19 Jan 2015, 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. >> >> Presence or absence of DEBUG_INSNs in the ready list can change the >> comparison order, and cause slightly different instruction schedules. > > Could you please provide a bit more detail here? Looking at > rank_for_schedule, I see that it considers insn pairs when at least one of > them is DEBUG_INSN, first. Debug insns are always moved to front, sorted > within themselves by luid, and not considered in the rest of > rank_for_schedule. I don't see how rank_for_schedule with DEBUG_INSN can > arrive at a A < B < C < A situation. In A < B < C < A case all A, B and C are normal instructions. It is a pre-existing condition. When compiling without debug information we have ready list "A, B, C". When compiling with debug information, we have ready list "A, B, C, D" where "D" is DEBUG_INSN. Because we now have 4 elements to sort instead of 3, qsort can choose a different order of comparison _among_ A, B and C. Since order of comparison matters (due to pre-existing condition of A < B < C < D) we can get a differently-sorted list. > > (btw, nitpicking, a "partial order" is when incomparable pairs are possible > (i.e. none of A == B, A < B, B < A is true), a "total order" is when all > pairs are comparable, and when you can have A < B < C < A, it's not a > mathematical order relation) You've got good grades in the Uni, didn't you :-). -- Maxim Kuvyrkov www.linaro.org
