Re: [PATCH] haifa-sched: fix autopref_rank_for_schedule qsort comparator

[Maxim Kuvyrkov <maxim dot kuvyrkov at linaro dot org>]

> 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.  */