GCC ILP instruction scheduling?

GCC ILP instruction scheduling?

[Yang Yang]

hi folks:
	I'm reading something on ILP and instruction scheduling,
	while instruction scheduling is done by hardware 
	in out-of-order machines, I'm thinking doing so first in
	software statically might introduce more opportunities 
	for the hardware to find independent instructions, because
	independent insts are already scheduled closer

	a slide at the IMPACT site shows that gcc has very low ILP 
	optimization. I'm not sure if this software/hardware combined
	approach would help.

	thanks

	Yang

Re: GCC ILP instruction scheduling?

[Vladimir Makarov]

Yang Yang wrote:
> 
> hi folks:
>         I'm reading something on ILP and instruction scheduling,
>         while instruction scheduling is done by hardware
>         in out-of-order machines, I'm thinking doing so first in
>         software statically might introduce more opportunities
>         for the hardware to find independent instructions, because
>         independent insts are already scheduled closer
> 

  Yes, it is a general approach to help the hardware, e.g. Bob Morgan
wrote it in his book.  The hardware has some constraints too, e.g. it
can only look through a few branches (therefore software pipelining has
more potential in improving code for OOO than just insn scheduling). 
Also the hardware has constraints on renaming registers and retiring
queues.

  Gcc by default makes insn scheduling for OOO processors too.  It is
switched off before register allocation for some OOO processors because
the insn scheduler has tendency to increase register pressure and as
consequence spilling and restoring registers is generated.  Currently
the insn scheduler don't follow register pressure in its decisions. 
Although some work is done here, e.g. Sanjiv Gupta's patch for sh4
scheduler.

>         a slide at the IMPACT site shows that gcc has very low ILP
>         optimization. I'm not sure if this software/hardware combined
>         approach would help.
> 

I do not know what slide are you talking about (it is better have a link
for it).  Gcc has a global instruction scheduler without insn cloning. 
more ILP is exposed when the dependencies are found more accurately. 
There are the following areas where it could be improved:

  1. more accurate aliasing analysis.  gcc has a simple control flow
insensitive algorithm for this.  Probably the situation could be
improved when alias information will be taken from upper passes (please
look at SSA project).

  2.  Register renaming to remove anti-dependencies.  Actually it is
implemented for the 2nd insn scheduling (it is default by -O3).  The
same could be done for the 1st insn scheduling.  I have a patch for it
(pseudo register renaming) which should improve register allocation (now
old global register allocator allocates a register for all
pseudo-register living ranges) and the 1st insn scheduling.  I'll try to
submit the patch when the mainline will be in an appropriate stage. 
Although we should be precautious here because as I wrote the insn
scheduler does not have code to take the register pressure into account.

  3. more insn scheduling transformations like insn cloning which
permits to remove some dependencies on some paths and improve code on
the paths.

Vlad

Re: GCC ILP instruction scheduling?

[tm_gccmail]

On Fri, 5 Dec 2003, Yang Yang wrote:

> hi folks:
> 	I'm reading something on ILP and instruction scheduling,
> 	while instruction scheduling is done by hardware 
> 	in out-of-order machines, I'm thinking doing so first in
> 	software statically might introduce more opportunities 
> 	for the hardware to find independent instructions, because
> 	independent insts are already scheduled closer
> 
> 	a slide at the IMPACT site shows that gcc has very low ILP 
> 	optimization. I'm not sure if this software/hardware combined
> 	approach would help.
> 
> 	thanks
> 
> 	Yang

You would be better off looking at the output code to determine why the
ILP is low instead of randomly hypothesizing the reasons for the symptoms.

Toshi