Superblock Scheduling Alg in GCC

[Vladimir Makarov]

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.

Vlad