Re: Superblock Instruction Scheduling in GCC

[Jan Hubicka <hubicka at ucw dot cz>]

> Jan and Vladimir,
> 
> Thank you guys for the immediate and very helpful responses. I have just
> tried the -fsched2-use-superblocks on vresion 3.3.1 that I currently have,
> but it did not work. Is this version supposed to have it or I have to
> download version 3.3.2 in order to get this feature?
The -fsched2-use-superblocks is only in mainline (development version of
3.4).  So you will need to either download snapshot of it or backport
the changes, if you want to experiment.
I would guess that using snapshot of 3.4 would be easier for you :)
> 
> Also, what's exactly the difference between -fsched2-use-superblocks and
> -fsched2-use-traces? As far as I know, a superblock is a single-entry
> multiple-exit region that is formed from a trace using tail duplication.
> This means that superblocks are more likely (but not necessarily) to
> increase code size due to tail duplication. This also implies that
> superblock scheduling is simpler than trace scheduling. Is this consistent
> with what the above two gcc comman-line options mean?
At the moment, superblocks scheduling and trace scheduling is same, jus
ttrace sheduling does tail duplication just before scheduling so
superblocks are really traces.
The algorithm is very primitive, in particular it does not do any
scheduling requiring compoensation code to be produced. This may be
reason why it does not bring very much.
> 
> As far as experimentation is concerned, let me give some background about
> what I am doing and what kind of input I might be able to provide:
> 
> I am doing research on optimal superblock scheduling and I need to import
> superblocks (more precisely, superblock data dependence graphs) from gcc to
> run them through my optimal solver (my research group currently has a way
> to import basic blocks and I am trying to extend that to superblocks).
> Even though this optimal solver is currently too slow to be included in a
> production compiler like gcc, it will be useful for studying the quality
> of gcc's schedules by comparing them against optimal. It will probably
> take me two or three months to get to that point for the very simplistic
> machine models that we are working with, but I'll be more than happy to
> provide you with any interesting results that I might come up with.

Yes, this looks interesting.  I would be curious how much gap there is
in between current scheduling and optimal one deifnitly.
On GCC mainline, you may also want to experiment with multipass
scheduling that (to my understanding) given large enought limits should
produce optimal schedules, but this is Vladimir's domain.

Honza
> 
> Regards
> 
> -Ghassan
> 
> 
> 
> On Thu, 4 Dec 2003, Jan Hubicka wrote:
> 
> > > Ghassan Shobaki wrote:
> > >
> > > > I know how to get gcc to form superblocks (by using the -ftracer
> > > > command-line switch), but is there a way to get it to use these
> > > > superblocks as scheduling regions in the instruction scheduling pass?
> > > > Currently, the instruction scheduling module forms regions that are totally
> > > > different from the superblocks that are formed in the tracer module
> > > > even though each superblock is a valid scheduling region.
> > > > Any idea how I can achieve this? Or are there any plans to do superblock
> > > > instruction scheduling in the near future?
> > >
> > > There was Jan Hubicka's patch for this.  Please look at it
> > >
> > > http://gcc.gnu.org/ml/gcc-patches/2003-02/msg00499.html
> > >
> > > This patch should work for all platforms except for IA64 whose the second
> > > scheduling is made on EBB.
> >
> > This patch is currently in the mainline tree, so you can simply use
> > -fsched2-use-traces / -fsched2-use-superblocks
> > >
> > > I tried trace scheduling for IA64 (but I did not post the patch for ia64).
> > > Here the results are
> > >
> > > http://gcc.gnu.org/ml/gcc-patches/2003-02/msg00499.html
> > >
> > > The problem with trace scheduling is that the generated code is bigger, the
> > > compiler is slower and the code improvement is insignificant.
> > >
> > >   If you manage to achieve an improvement for a platform on a credible
> > > benchmark (SPEC95, SPEC2000), we could consider to add the patch to gcc at
> > > least for given platform for -O3.   Because the compiler changed since the
> > > patch was posted, there is a probability that you could achieve this.
> >
> > Yes, we need experimenting here.
> > I was quite surprised that the benefits wasn't too noticeable on
> > in-order architecture and I would like to hear about any results
> > (positive or negative).
> > -fsched2-use-superblocks should bring most of benefits at no code size
> > costs, while -fsched2-use-traces is more experimental and probably needs
> > profile feedback to do somethign usefull.  (I managed to get some
> > speedups using this on Athlon but the benefits wasn't considerable
> > enought to discuss inclusion in -O3 -fbranch-probabilities combination)
> >
> > Honza
> > >
> > >
> > > Vlad
> > >
> >