Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

2015-01-31 Thread Richard Biener
On January 31, 2015 9:01:02 AM CET, Maxim Kuvyrkov wrote: >On Jan 31, 2015, at 7:33 AM, Jeff Law wrote: > >> On 01/22/15 12:01, Maxim Kuvyrkov wrote: >>> On Jan 22, 2015, at 8:11 PM, Jeff Law wrote: >>> On 01/19/15 06:07, Maxim Kuvyrkov wrote: > > The underlying problem is that t

Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

2015-01-31 Thread Maxim Kuvyrkov
On Jan 31, 2015, at 7:33 AM, Jeff Law wrote: > On 01/22/15 12:01, Maxim Kuvyrkov wrote: >> On Jan 22, 2015, at 8:11 PM, Jeff Law 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 t

Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

2015-01-30 Thread Jeff Law
On 01/22/15 12:01, Maxim Kuvyrkov wrote: On Jan 22, 2015, at 8:11 PM, Jeff Law 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 heurist

Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

2015-01-28 Thread Maxim Kuvyrkov
On Jan 29, 2015, at 10:36 AM, Alexandre Oliva wrote: > On Jan 19, 2015, Maxim Kuvyrkov wrote: > >> Presence or absence of DEBUG_INSNs in the ready list can change the >> comparison order, and cause slightly different instruction schedules. > >> The solution that I propose (and that the patch i

Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

2015-01-28 Thread Alexandre Oliva
On Jan 19, 2015, Maxim Kuvyrkov wrote: > Presence or absence of DEBUG_INSNs in the ready list can change the > comparison order, and cause slightly different instruction schedules. > The solution that I propose (and that the patch implements) is to sort > DEBUG_INSNs separately from normal insns

Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

2015-01-22 Thread Jeff Law
On 01/22/15 12:01, Maxim Kuvyrkov wrote: 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 in

Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

2015-01-22 Thread Maxim Kuvyrkov
On Jan 22, 2015, at 8:11 PM, Jeff Law 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

Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

2015-01-22 Thread Jeff Law
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 i

Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

2015-01-19 Thread Maxim Kuvyrkov
On Jan 20, 2015, at 6:32 AM, Mike Stump wrote: > On Jan 19, 2015, at 1:28 PM, Maxim Kuvyrkov wrote: >> >> Yes, the ordering relation is screwed, as you put it. With the number of >> independent heuristics that rank_for_schedule has to consider there is no >> other way then to have a "screwed

Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

2015-01-19 Thread Mike Stump
On Jan 19, 2015, at 1:28 PM, Maxim Kuvyrkov wrote: > > Yes, the ordering relation is screwed, as you put it. With the number of > independent heuristics that rank_for_schedule has to consider there is no > other way then to have a "screwed" ordering. I have not seen a proof that an working co

Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

2015-01-19 Thread Maxim Kuvyrkov
On Jan 20, 2015, at 12:11 AM, Mike Stump wrote: > On Jan 19, 2015, at 10:14 AM, Maxim Kuvyrkov > wrote: >> On Jan 19, 2015, at 6:48 PM, Mike Stump wrote: >>> On Jan 19, 2015, at 5:41 AM, Maxim Kuvyrkov >>> wrote: In A < B < C < A case all A, B and C are normal instructions. It is a >>

Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

2015-01-19 Thread Mike Stump
On Jan 19, 2015, at 10:14 AM, Maxim Kuvyrkov wrote: > On Jan 19, 2015, at 6:48 PM, Mike Stump wrote: >> On Jan 19, 2015, at 5:41 AM, Maxim Kuvyrkov >> wrote: >>> In A < B < C < A case all A, B and C are normal instructions. It is a >>> pre-existing condition. When compiling without debug inf

Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

2015-01-19 Thread Maxim Kuvyrkov
On Jan 19, 2015, at 6:48 PM, Mike Stump wrote: > On Jan 19, 2015, at 5:41 AM, Maxim Kuvyrkov wrote: >> 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 wi

Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

2015-01-19 Thread Mike Stump
On Jan 19, 2015, at 5:41 AM, Maxim Kuvyrkov wrote: > 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,

Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

2015-01-19 Thread Maxim Kuvyrkov
On Jan 19, 2015, at 4:34 PM, Alexander Monakov 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

Re: [PATCH] Fix scheduling undeterminism from sorting with DEBUG_INSNs

2015-01-19 Thread Alexander Monakov
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 w