haifa-sched: fix autopref_rank_for_schedule qsort comparator

Hello,

The autopref_rank_for_schedule qsort sub-comparator is not actually a proper
comparator.  For instance, it lacks transitivity: if there's insns A, B, C
such that B has AUTOPREF_MULTUPASS_DATA_IRRELEVANT status, but A and C
compare such that C < A, we can have A == B == C < A according to this
sub-comparator, and A < B < C < A if the following tie-breakers order
A before B and B before C.

I'm not sure this heuristic fits well into the overall scheduler sorting,
but if we want to just fix this comparison step, we should never skip
calls to autopref_rank_data.

Bootstrapped and regtested on x86-64 with PARAM_SCHED_AUTOPREF_QUEUE_DEPTH
set to '0' (otherwise this sub-comparator is unused).  OK to apply?

Thanks.
Alexander

	* haifa-sched.c (autopref_rank_for_schedule): Always invoke
	autopref_rank_data.

> On Sep 19, 2017, at 2:21 PM, Alexander Monakov <amonakov@ispras.ru> wrote:
> 
> Hello,
> 
> The autopref_rank_for_schedule qsort sub-comparator is not actually a proper
> comparator.  For instance, it lacks transitivity: if there's insns A, B, C
> such that B has AUTOPREF_MULTUPASS_DATA_IRRELEVANT status, but A and C
> compare such that C < A, we can have A == B == C < A according to this
> sub-comparator, and A < B < C < A if the following tie-breakers order
> A before B and B before C.
> 
> I'm not sure this heuristic fits well into the overall scheduler sorting,
> but if we want to just fix this comparison step, we should never skip
> calls to autopref_rank_data.
> 
> Bootstrapped and regtested on x86-64 with PARAM_SCHED_AUTOPREF_QUEUE_DEPTH
> set to '0' (otherwise this sub-comparator is unused).  OK to apply?

Thanks for investigating this.  Indeed there is a problem, but your patch looks wrong.  The "irrelevant" instructions can't be meaningfully compared with "relevant" ones, so calling autopref_rank_data on "irrelevant" instruction doesn't look right.

How about the following:
1. if both instructions are "irrelevant", then return "0".
2. if one instruction is "relevant" and another is "irrelevant", then "relevant" instruction is always greater (or lesser) than the non-relevant. 
3. if both instructions are "relevant", then call autopref_rank_data.

I don't have immediate answer on whether "relevant" or "irrelevant" instructions should be pushed towards beginning of the ready list.  Possibly, we want to delay "relevant" instructions and push "irrelevant" towards beginning of ready list so that more "relevant" instructions can enter ready list as their dependencies are resolved from scheduling "irrelevant" instructions.

WDYT?

--
Maxim Kuvyrkov
www.linaro.org


> Thanks.
> Alexander
> 
> 	* haifa-sched.c (autopref_rank_for_schedule): Always invoke
> 	autopref_rank_data.
> 
> diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
> index af0ed27b18f..031a0af96db 100644
> --- a/gcc/haifa-sched.c
> +++ b/gcc/haifa-sched.c
> @@ -5707,7 +5707,8 @@ autopref_rank_data (autopref_multipass_data_t data1,
> static int
> autopref_rank_for_schedule (const rtx_insn *insn1, const rtx_insn *insn2)
> {
> -  for (int write = 0; write < 2; ++write)
> +  int r = 0;
> +  for (int write = 0; write < 2 && !r; ++write)
>     {
>       autopref_multipass_data_t data1
> 	= &INSN_AUTOPREF_MULTIPASS_DATA (insn1)[write];
> @@ -5716,21 +5717,14 @@ autopref_rank_for_schedule (const rtx_insn *insn1, const rtx_insn *insn2)
> 
>       if (data1->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
> 	autopref_multipass_init (insn1, write);
> -      if (data1->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
> -	continue;
> 
>       if (data2->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
> 	autopref_multipass_init (insn2, write);
> -      if (data2->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
> -	continue;
> 
> -      if (!rtx_equal_p (data1->base, data2->base))
> -	continue;
> -
> -      return autopref_rank_data (data1, data2);
> +      r = autopref_rank_data (data1, data2);
>     }
> 
> -  return 0;
> +  return r;
> }
> 
> /* True if header of debug dump was printed.  */

On Tue, 19 Sep 2017, Maxim Kuvyrkov wrote:
> How about the following:
> 1. if both instructions are "irrelevant", then return "0".
> 2. if one instruction is "relevant" and another is "irrelevant", then
> "relevant" instruction is always greater (or lesser) than the non-relevant. 
> 3. if both instructions are "relevant", then call autopref_rank_data.

Sounds good, the following patch implements this (with 'relevant' greater).

> I don't have immediate answer on whether "relevant" or "irrelevant"
> instructions should be pushed towards beginning of the ready list.  Possibly,
> we want to delay "relevant" instructions and push "irrelevant" towards
> beginning of ready list so that more "relevant" instructions can enter ready
> list as their dependencies are resolved from scheduling "irrelevant"
> instructions.
> 
> WDYT?

*nod*, this makes sense.

(bootstrap/regtest running on x86-64)

Thanks!

	* haifa-sched.c (autopref_rank_for_schedule): Order 'irrelevant' insns
	first, always call autopref_rank_data otherwise.

diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
index af0ed27b18f..8f006de2319 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -5707,7 +5707,8 @@ autopref_rank_data (autopref_multipass_data_t data1,
 static int
 autopref_rank_for_schedule (const rtx_insn *insn1, const rtx_insn *insn2)
 {
-  for (int write = 0; write < 2; ++write)
+  int r = 0;
+  for (int write = 0; write < 2 && !r; ++write)
     {
       autopref_multipass_data_t data1
 	= &INSN_AUTOPREF_MULTIPASS_DATA (insn1)[write];
@@ -5716,21 +5717,20 @@ autopref_rank_for_schedule (const rtx_insn *insn1, const rtx_insn *insn2)
 
       if (data1->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
 	autopref_multipass_init (insn1, write);
-      if (data1->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
-	continue;
 
       if (data2->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
 	autopref_multipass_init (insn2, write);
-      if (data2->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
-	continue;
 
-      if (!rtx_equal_p (data1->base, data2->base))
-	continue;
+      int irrel1 = data1->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT;
+      int irrel2 = data2->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT;
 
-      return autopref_rank_data (data1, data2);
+      if (!irrel1 && !irrel2)
+	r = autopref_rank_data (data1, data2);
+      else
+	r = irrel2 - irrel1;
     }
 
-  return 0;
+  return r;
 }
 
 /* True if header of debug dump was printed.  */

> On Sep 19, 2017, at 5:25 PM, Alexander Monakov <amonakov@ispras.ru> wrote:
> 
> On Tue, 19 Sep 2017, Maxim Kuvyrkov wrote:
>> How about the following:
>> 1. if both instructions are "irrelevant", then return "0".
>> 2. if one instruction is "relevant" and another is "irrelevant", then
>> "relevant" instruction is always greater (or lesser) than the non-relevant. 
>> 3. if both instructions are "relevant", then call autopref_rank_data.
> 
> Sounds good, the following patch implements this (with 'relevant' greater).
> 
>> I don't have immediate answer on whether "relevant" or "irrelevant"
>> instructions should be pushed towards beginning of the ready list.  Possibly,
>> we want to delay "relevant" instructions and push "irrelevant" towards
>> beginning of ready list so that more "relevant" instructions can enter ready
>> list as their dependencies are resolved from scheduling "irrelevant"
>> instructions.
>> 
>> WDYT?
> 
> *nod*, this makes sense.
> 
> (bootstrap/regtest running on x86-64)
> 
> Thanks!
> 
> 	* haifa-sched.c (autopref_rank_for_schedule): Order 'irrelevant' insns
> 	first, always call autopref_rank_data otherwise.
> 
> diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
> index af0ed27b18f..8f006de2319 100644
> --- a/gcc/haifa-sched.c
> +++ b/gcc/haifa-sched.c
> @@ -5707,7 +5707,8 @@ autopref_rank_data (autopref_multipass_data_t data1,
> static int
> autopref_rank_for_schedule (const rtx_insn *insn1, const rtx_insn *insn2)
> {
> -  for (int write = 0; write < 2; ++write)
> +  int r = 0;
> +  for (int write = 0; write < 2 && !r; ++write)
>     {
>       autopref_multipass_data_t data1
> 	= &INSN_AUTOPREF_MULTIPASS_DATA (insn1)[write];
> @@ -5716,21 +5717,20 @@ autopref_rank_for_schedule (const rtx_insn *insn1, const rtx_insn *insn2)
> 
>       if (data1->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
> 	autopref_multipass_init (insn1, write);
> -      if (data1->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
> -	continue;
> 
>       if (data2->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
> 	autopref_multipass_init (insn2, write);
> -      if (data2->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
> -	continue;
> 
> -      if (!rtx_equal_p (data1->base, data2->base))
> -	continue;
> +      int irrel1 = data1->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT;
> +      int irrel2 = data2->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT;
> 
> -      return autopref_rank_data (data1, data2);
> +      if (!irrel1 && !irrel2)
> +	r = autopref_rank_data (data1, data2);
> +      else
> +	r = irrel2 - irrel1;

I'd like to keep read/write processing balanced.  In the above "read" analysis has greater weight than "write" analysis.  Also, autopref_rank_data() should not be called if !rtx_equal_p (data1->base, data2->base).

How about the attached patch?

--
Maxim Kuvyrkov
www.linaro.org

> I'd like to keep read/write processing balanced.  In the above "read" analysis
> has greater weight than "write" analysis.  Also, autopref_rank_data() should
> not be called if !rtx_equal_p (data1->base, data2->base).

I'm afraid this doesn't work.  Consider you have insns A, B, C such that all
are relevant (so that irr1, irr2 stay 0), A and C have the same base and
compare such that C < A, B has a different base and therefore according
to this subcomparator you can have A == B == C < A and with following
tiebreakers A < B < C < A.

In other words, if your comparison tries to subdivide input set into equivalence
classes (here you want to introduce equivalence classes based on 'base'), then
you should introduce ordering between classes (i.e. for two items with a 
different 'base' say if one is greater than the other).

Alexander

> On Sep 19, 2017, at 6:20 PM, Alexander Monakov <amonakov@ispras.ru> wrote:
> 
>> I'd like to keep read/write processing balanced.  In the above "read" analysis
>> has greater weight than "write" analysis.  Also, autopref_rank_data() should
>> not be called if !rtx_equal_p (data1->base, data2->base).
> 
> I'm afraid this doesn't work.  Consider you have insns A, B, C such that all
> are relevant (so that irr1, irr2 stay 0), A and C have the same base and
> compare such that C < A, B has a different base and therefore according
> to this subcomparator you can have A == B == C < A and with following
> tiebreakers A < B < C < A.
> 
> In other words, if your comparison tries to subdivide input set into equivalence
> classes (here you want to introduce equivalence classes based on 'base'), then
> you should introduce ordering between classes (i.e. for two items with a 
> different 'base' say if one is greater than the other).

Right.  Let me meditate for couple of days on this :-) .

--
Maxim Kuvyrkov
www.linaro.org

On Tue, 19 Sep 2017, Alexander Monakov wrote:
> 	* haifa-sched.c (autopref_rank_for_schedule): Order 'irrelevant' insns
> 	first, always call autopref_rank_data otherwise.

May I apply this patch now to unblock qsort checking?  Further changes or
adjustments can then go in independently at a later time.

Thanks.
Alexander

> --- a/gcc/haifa-sched.c
> +++ b/gcc/haifa-sched.c
> @@ -5707,7 +5707,8 @@ autopref_rank_data (autopref_multipass_data_t data1,
>  static int
>  autopref_rank_for_schedule (const rtx_insn *insn1, const rtx_insn *insn2)
>  {
> -  for (int write = 0; write < 2; ++write)
> +  int r = 0;
> +  for (int write = 0; write < 2 && !r; ++write)
>      {
>        autopref_multipass_data_t data1
>  	= &INSN_AUTOPREF_MULTIPASS_DATA (insn1)[write];
> @@ -5716,21 +5717,20 @@ autopref_rank_for_schedule (const rtx_insn *insn1, const rtx_insn *insn2)
>  
>        if (data1->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
>  	autopref_multipass_init (insn1, write);
> -      if (data1->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
> -	continue;
>  
>        if (data2->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
>  	autopref_multipass_init (insn2, write);
> -      if (data2->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
> -	continue;
>  
> -      if (!rtx_equal_p (data1->base, data2->base))
> -	continue;
> +      int irrel1 = data1->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT;
> +      int irrel2 = data2->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT;
>  
> -      return autopref_rank_data (data1, data2);
> +      if (!irrel1 && !irrel2)
> +	r = autopref_rank_data (data1, data2);
> +      else
> +	r = irrel2 - irrel1;
>      }
>  
> -  return 0;
> +  return r;
>  }
>  
>  /* True if header of debug dump was printed.  */
>

> On Sep 22, 2017, at 4:18 AM, Alexander Monakov <amonakov@ispras.ru> wrote:
> 
> On Tue, 19 Sep 2017, Alexander Monakov wrote:
>> 	* haifa-sched.c (autopref_rank_for_schedule): Order 'irrelevant' insns
>> 	first, always call autopref_rank_data otherwise.
> 
> May I apply this patch now to unblock qsort checking?  Further changes or
> adjustments can then go in independently at a later time.


Yes, feel free to commit one of your versions.

--
Maxim Kuvyrkov
www.linaro.org



> Thanks.
> Alexander
> 
>> --- a/gcc/haifa-sched.c
>> +++ b/gcc/haifa-sched.c
>> @@ -5707,7 +5707,8 @@ autopref_rank_data (autopref_multipass_data_t data1,
>> static int
>> autopref_rank_for_schedule (const rtx_insn *insn1, const rtx_insn *insn2)
>> {
>> -  for (int write = 0; write < 2; ++write)
>> +  int r = 0;
>> +  for (int write = 0; write < 2 && !r; ++write)
>>     {
>>       autopref_multipass_data_t data1
>> 	= &INSN_AUTOPREF_MULTIPASS_DATA (insn1)[write];
>> @@ -5716,21 +5717,20 @@ autopref_rank_for_schedule (const rtx_insn *insn1, const rtx_insn *insn2)
>> 
>>       if (data1->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
>> 	autopref_multipass_init (insn1, write);
>> -      if (data1->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
>> -	continue;
>> 
>>       if (data2->status == AUTOPREF_MULTIPASS_DATA_UNINITIALIZED)
>> 	autopref_multipass_init (insn2, write);
>> -      if (data2->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT)
>> -	continue;
>> 
>> -      if (!rtx_equal_p (data1->base, data2->base))
>> -	continue;
>> +      int irrel1 = data1->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT;
>> +      int irrel2 = data2->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT;
>> 
>> -      return autopref_rank_data (data1, data2);
>> +      if (!irrel1 && !irrel2)
>> +	r = autopref_rank_data (data1, data2);
>> +      else
>> +	r = irrel2 - irrel1;
>>     }
>> 
>> -  return 0;
>> +  return r;
>> }
>> 
>> /* True if header of debug dump was printed.  */
>>