Re: Superblock Scheduling Alg in GCC

[Ghassan Shobaki <gshobaki at ece dot ucdavis dot edu>]

I am currently writing a paper on optimal superblock scheduling in 
which I compare optimal vs three heuristics (CP, DHASY and SR). In 
the experimental section, it would be nice if I can make a statement about
which heuristic is the closest to what gcc does. However, I am 
confused about your description below and have a few questions:  

- You are saying that it chooses the inst which has higher frequency of 
execution, but it does not take block execution frequency into account. 
This sounds contradictory to me! Is there a difference between instruction 
frequency and block frequency? Don't all insts within a basic block have 
the same frequency of execution?

- You are saying that the priority does not depend on the critical path 
from the last exit, but critical path is the primary and most 
effective priority scheme in list scheduling and without it I don't think 
the scheduler will behave well. Did I misunderstand this? Is it true that 
critical path is not used at all?

- You are saying that it does not favor local insts to insts from other 
basic blocks (speculative insts). However, I am under the impression that 
the Haifa scheduler does favor local instructions (useful code motion) to 
external instructions (speculative code motion). This impression comes 
from reaading the "Brenstein and Rodeh" paper on which the Haifa scheduler 
is most likely based. If the superblock scheduler was based on the Haifa 
scheduler then it will probably be giving lower priority to speculative 
motions. Is this true?

Thanks

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