Re: Superblock Scheduling Alg in GCC

[Ghassan Shobaki <gshobaki@ece.ucdavis.edu>]

Guys,

I have done some experiments on two different heuristics for superblock 
scheduling by comparing them with optimal scheduling. The two heuristics 
are simple critical path CP (priority is the CP from the last branch only) 
and weighted critical path WCP (priority is a weighted sum of critical pahts 
from all branches below an instruction, with the branch weight being the 
probability of exiting the superblock at that branch). On the simple 
machine model that I am using, I got the following results: 

fp2000 benchmark: CP is optimal on 72% of the superblocks and WCP is 
optimal on 84% of the superblocks

int2000 benchmark: CP is optimal on 83% of the superblocks and WCP is 
optimal on 94% of the superblocks

These numbers do not necessarily reflect actual run-time performance 
improvements, since they were collected in a standalone setup were 
superblock data dependence graphs were extracted from gcc and scheduled
separately for a simple machine model (dual issue in which one int and one 
fp instruction can issue in each cycle). However, these results 
do suggest that the WCP heuristic is significantly better than the simple CP.

The reference for the WCP heuristic is:
R. Bringmann, Compiler-Controlled Speculation, PHD thesis, Dept. of CS, 
UIUC, IL 1995. (where the technique is called Dependence Height and 
Speculative Yield DHASY).

However, you don't really need to go there since the heuristic itself is 
so simple and intuitive that my description above is almost sufficient. 
Let me know if you are interested and I'll give you the details and 
explain one particular subtility about it.

Regards

-Ghassan



On Tue, 10 Feb 2004, Jan Hubicka wrote:

> > 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
> > 
>