Patch: scheduler heuristics

[Vladimir Makarov]

Dale Johannesen wrote:
> 
> Here are a couple of additional scheduler heuristics that do well on
> ppc Darwin:
> almost every Specmark shows a slight improvement, about 2% overall.

That is a big improvement!

Just for curiosity what benchmarks did you use?

> I'd certainly suggest trying this on another target or two before
> accepting.
>

 
> Index: haifa-sched.c
> ===================================================================
> RCS file: /cvs/gcc/gcc/gcc/haifa-sched.c,v
> retrieving revision 1.213
> diff -u -d -b -w -c -3 -p -r1.213 haifa-sched.c
> cvs server: conflicting specifications of output style
> *** haifa-sched.c       28 Sep 2002 15:29:34 -0000      1.213
> --- haifa-sched.c       1 Nov 2002 20:43:38 -0000
> *************** rank_for_schedule (x, y)
> *** 850,856 ****
> --- 850,874 ----
>      int val, priority_val, weight_val, info_val;
> 
>      /* Prefer insn with higher priority.  */
> + #if MAX_MULTIPLICITY > 1
> +   {
> +     /* decrease the priority of single-cycle instructions that can go
> on
> +        any of several functional units; these are less likely to lead
> to a
> +        stall if deferred.  */
> +     int pri = INSN_PRIORITY(tmp);
> +     int pri2 = INSN_PRIORITY(tmp2);
> +     if ( insn_unit(tmp) > 0 &&
> function_units[insn_unit(tmp)].multiplicity > 1
> +          && INSN_COST(tmp) == 1 )
> +       pri -= 1;
> +     if ( insn_unit(tmp2) > 0 &&
> function_units[insn_unit(tmp2)].multiplicity > 1
> +          && INSN_COST(tmp2) == 1 )
> +       pri2 -= 1;
> +     priority_val = pri2 - pri;
> +   }
> + #else
>      priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
> + #endif
> +
>      if (priority_val)
>        return priority_val;
>

FYI, the dfa scheduler has more general solution for this (look ahead
insn scheduling).
 
> *************** rank_for_schedule (x, y)
> *** 891,896 ****
> --- 909,932 ----
>          return val;
>        }
> 
> +   /* Prefer the insn which makes more later insns available for
> +      execution.  If we have, for example, a large number of
> +      equal-priority loads, it is good to have some non-load
> +      insns available to schedule opposite them.  */
> +   depend_count1 = 0;
> +   for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1))
> +     if (INSN_DEP_COUNT (XEXP (link, 0)) == 1)
> +       depend_count1++;
> +
> +   depend_count2 = 0;
> +   for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1))
> +     if (INSN_DEP_COUNT (XEXP (link, 0)) == 1)
> +       depend_count2++;
> +
> +   val = depend_count2 - depend_count1;
> +   if (val)
> +     return val;
> +
>      /* Prefer the insn which has more later insns that depend on it.
>         This gives the scheduler more freedom when scheduling later
>         instructions at the expense of added register pressure.  */

  Probably this heuristic will work well for superscalar RISC processors
with small latency times, but for classic RISC processors (e.g. which
can issue only one insn) it might result in worse code.

  So it would be better to provide an option/hook/macro to switch on/off
heuristics for targets.

  It would be great to know impact of each heuristic on code
improvement. 

  May be it will be interesting for you.  You could try another
heuristics using summary of critical path lengths of insns depending on
given insn instead of number of such insns.  Long ago I read a russian
article that this heuristics resulted in generation of better code for
Livermore loops for Cray-1.


Vlad