Scheduler and GCC CFG

Scheduler and GCC CFG

[David Edelsohn]

	sched-rgn.c has a comments implying that it should be converted to
use the new cfg code and flow.c.  Is the current CFG code in GCC suppose
to be complete enough to express all of the dominance and successor
information needed by the scheduler or is CFG suppose to be expanded as
necessary?

Thanks, David

Re: Scheduler and GCC CFG

[Jan Hubicka]

> 	sched-rgn.c has a comments implying that it should be converted to
> use the new cfg code and flow.c.  Is the current CFG code in GCC suppose
> to be complete enough to express all of the dominance and successor
> information needed by the scheduler or is CFG suppose to be expanded as
> necessary?
There should be enought infrastructure to do that.
I did small experiment with converting the extended block scheduling to
the CFG code and it wasn't dificult, so I guess sched-rgn should be easy
too.

I dind't contributed superblock scheduling code yet, since I never was
able to benchmark it seriously (Athlon is not best platform for such a
kind of work and I get mixed results there).  I will try to take a look
after merging the register tracking bits into rtlopt branch.

Honza
> 
> Thanks, David

Re: Scheduler and GCC CFG

[Richard Henderson]

On Mon, Dec 16, 2002 at 12:46:31AM -0500, David Edelsohn wrote:
> Is the current CFG code in GCC suppose to be complete enough to
> express all of the dominance and successor information needed by
> the scheduler ...

Yes.  Indeed, it's more complete than the CFG used within the
scheduler.


r~

Re: Scheduler and GCC CFG

[David Edelsohn]

>>>>> Jan Hubicka writes:

Jan> I did small experiment with converting the extended block scheduling to
Jan> the CFG code and it wasn't dificult, so I guess sched-rgn should be easy
Jan> too.

Jan> I dind't contributed superblock scheduling code yet, since I never was
Jan> able to benchmark it seriously (Athlon is not best platform for such a
Jan> kind of work and I get mixed results there).  I will try to take a look
Jan> after merging the register tracking bits into rtlopt branch.

	If I understand correct, we have the current region scheduler, the
extended basic block scheduler, an extended basic block scheduler
converted to use CFG, and something you refer to as a superblock
scheduler.  May I please get access to your CFG-based EBB scheduler and
your superblock scheduler?  I am investigating how to improve the GCC
scheduler and would like to include your proposals.

Thanks, David

Re: Scheduler and GCC CFG

[Jan Hubicka]

> >>>>> Jan Hubicka writes:
> 
> Jan> I did small experiment with converting the extended block scheduling to
> Jan> the CFG code and it wasn't dificult, so I guess sched-rgn should be easy
> Jan> too.
> 
> Jan> I dind't contributed superblock scheduling code yet, since I never was
> Jan> able to benchmark it seriously (Athlon is not best platform for such a
> Jan> kind of work and I get mixed results there).  I will try to take a look
> Jan> after merging the register tracking bits into rtlopt branch.
> 
> 	If I understand correct, we have the current region scheduler, the
> extended basic block scheduler, an extended basic block scheduler
> converted to use CFG, and something you refer to as a superblock
Actually what I refer as supperblock scheduler is the EBB scheduler.
EBB scheduler really does schedule only superblck so I think it is
missnamed and I tend to think about it as about superblock scheduler.
Sorry for confusion.

CFG based EBB scheduler is present on cfg branch.  It is simply run
instead of current region based scheduler.  It is not completely
finished but basically working (ie for instance it rebulds complete
liveness info afterwards that can be done in smarter ways).

Honza
> scheduler.  May I please get access to your CFG-based EBB scheduler and
> your superblock scheduler?  I am investigating how to improve the GCC
> scheduler and would like to include your proposals.
> 
> Thanks, David

Re: Scheduler and GCC CFG

[David Edelsohn]

>>>>> Jan Hubicka writes:

Jan> CFG based EBB scheduler is present on cfg branch.  It is simply run
Jan> instead of current region based scheduler.  It is not completely
Jan> finished but basically working (ie for instance it rebulds complete
Jan> liveness info afterwards that can be done in smarter ways).

	Thanks for the clarification that EBB and superblock scheduler are
the same.

	What exactly do you mean by a CFG-based EBB scheduler?  The
cfg-branch has an option to run the EBB scheduler instead of the region
scheduler for the second scheduler pass.  It fixes up the CFG after
scheduling each block, but I do not see it using the CFG for scheduling
any more than sched-ebb on the trunk.  There is no change to the scheduler
analysis and dependence calculation infrastructure.

Thanks, David

Re: Scheduler and GCC CFG

[Jan Hubicka]

> >>>>> Jan Hubicka writes:
> 
> Jan> CFG based EBB scheduler is present on cfg branch.  It is simply run
> Jan> instead of current region based scheduler.  It is not completely
> Jan> finished but basically working (ie for instance it rebulds complete
> Jan> liveness info afterwards that can be done in smarter ways).
> 
> 	Thanks for the clarification that EBB and superblock scheduler are
> the same.
> 
> 	What exactly do you mean by a CFG-based EBB scheduler?  The
> cfg-branch has an option to run the EBB scheduler instead of the region
> scheduler for the second scheduler pass.  It fixes up the CFG after
> scheduling each block, but I do not see it using the CFG for scheduling
> any more than sched-ebb on the trunk.  There is no change to the scheduler
To my understanding the superblock scheduling algorithm as discussed in
literature consists of three main tricks - one is formation of traces
(superblocks) to schedule, other is scheduling the superblock as it if
were single basic block with few extra dependencies on jump boundaries
and last is insertion of compensation code to allow fewer dependencies
in the scheduling stage.

The first part is implemented by the tracer pass.  It is currently
merged into the trunk and run before 2nd cse pass to enable more
optimizations but the superblocks should remain conssitent until sched2
(or we can simply rerun it) as long as crossjumping is disabled.

EBB scheduler on trunk does basically the second step, so all I needed
is to allow it to integrate into normal compilation process (ie preserve
CFG) and slightly modify the superblock algorithm.

I didn't get into the compensation code.  As it is it already should be
enouth to test whether superblock scheduling can bring us something over
region based scheduler we have right now.  I tried that on Athlon and
the results are mostly random.  This is partly due to exact CPU model
(that has improved by DFA now), abd the fact that Athlon is not very
sensitive to scheduling.

I planned to play with this on some classic in-order machine but never
got into that since then.

Honza
> analysis and dependence calculation infrastructure.
> 
> Thanks, David

Re: Scheduler and GCC CFG

[David Edelsohn]

>>>>> Jan Hubicka writes:

Jan> ... it already should be
Jan> enough to test whether superblock scheduling can bring us something over
Jan> region based scheduler we have right now.  I tried that on Athlon and
Jan> the results are mostly random.  This is partly due to exact CPU model
Jan> (that has improved by DFA now), abd the fact that Athlon is not very
Jan> sensitive to scheduling.

	On the cfg-branch, you run EBB scheduler instead of the
post-reload region scheduler.  The tracer pass is run before the first
scheduling pass, so why not run EBB scheduler instead of first scheduling
pass?  Is this because first scheduling pass is disabled for x86?  I would
expect the first scheduling pass to have much more freedom to move
instructions within the superblocks.

David

Re: Scheduler and GCC CFG

[Jan Hubicka]

> >>>>> Jan Hubicka writes:
> 
> Jan> ... it already should be
> Jan> enough to test whether superblock scheduling can bring us something over
> Jan> region based scheduler we have right now.  I tried that on Athlon and
> Jan> the results are mostly random.  This is partly due to exact CPU model
> Jan> (that has improved by DFA now), abd the fact that Athlon is not very
> Jan> sensitive to scheduling.
> 
> 	On the cfg-branch, you run EBB scheduler instead of the
> post-reload region scheduler.  The tracer pass is run before the first
> scheduling pass, so why not run EBB scheduler instead of first scheduling
> pass?  Is this because first scheduling pass is disabled for x86?  I would
Yes, I just wanted to get something working on x86 first and test it.
It is all unfinished, sorry for that.  Soon, I hope, I will have ready
the Athlon model taking into account FIFO in between decoder and
execution units and then I would like to give it another shot.

I don't see any major reason why the EBB scheduling won't work before
reload.  However since traces may get large and it does a lot of
intrablock motion, number of it not necesary, it may increase register
liveness and turn many registers from local to global ones so this needs
experimentation.

Honza
> expect the first scheduling pass to have much more freedom to move
> instructions within the superblocks.
> 
> David