Re: Superblock Scheduling Alg in GCC

[Jan Hubicka <hubicka at ucw dot cz>]

> Vladimir Makarov wrote:
> 
> >Ghassan Shobaki wrote:
> >
> >>Are there any documents describing the algorithm used in the 
> >>superblock instruction scheduler?
> >>
> >I don't know one.
> >
> >>Does it use any (or a combination of) of published techniques such as 
> >>critical path and speculative hedge and successive retirement ..etc? 
> >>Or it just has its own algorithm?
> >>
> >>
> >>
> >It uses own algorithm which was grown from original haifa-scheduler.   
> >Earlier it was one file which was divided.  Superblock scheduler uses 
> >code of sched-deps.c and haifa-sched.c and directs them through a few 
> >hooks.
> >
> >Generally speaking suberblock is believed to be a basic block to which 
> >list scheduling is applied.  The superblock scheduler just checks that 
> >the insn can be issued speculatively and prefer to issue more 
> >frequently executed insns when the priority is the same (and now when 
> >insn register weights are the same).  But calculation of insn 
> >priorities does not take basic block frequencies (or belonging to 
> >different basic blocks) into account.  So the algorithm is very simple.
> >
> >No more advanced approaches like heuristics based on critical path to 
> >the last exit of superblock, dependence height and speculative yeild 
> >(taking block excution probability into account when the insn priority 
> >is calculated), sucessive retirment (preference of non-speculative 
> >insn movement first), or speculative hedge aiming to achieve minimal 
> >delay to all exits are used.
> >
> >So there are a lot of things to improve the code.  But it will be not 
> >easy to add them because big part of code is used by the region based 
> >scheduler too.
> 
> Sorry, I forgot too add that what I wrote is about extended basic block 
> scheduler (file sched-ebb.c) which is used for Itanium as a default 
> after the register allocation.  If you are intersting in Jan Hubicka's 
> trace scheduler, I think that Jan's answer will be more competent.

I really didn't changed much in the algorithm.  All I was interested in
was to make it work with CFG and plugged in the tail duplication pass.
So your description is still valid.
The code has little logic to avoid moving instructions too much up and
adding some extra heuristics shall not be that dificult, but I didn't
read the papers on topic very curefully :)


Honza
> 
> Vlad
>