Re: Superblock Scheduling Alg in GCC

[Vladimir Makarov <vmakarov at redhat dot com>]

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.

Vlad.