Re: Trace Scheduling in GCC

[Jan Hubicka <jh@suse.cz>]

> Vladimir,
> 
> No problem at all! I am currently working on the much harder problem of
> trace scheduling (again, to the best of my knowledge, there has been no
> optimal solution for it). That's why I need to get actual traces from a
> production compiler to experimentally evaluate my algorithm. It looks
> that what I need to do is examine the trace formation code in gcc and see
> if I can eliminate the tail duplication step.

This should be fairly easy - see function find_trace that given a seed
BB will return you fully grown trace.  The algorithm match pretty
closely what Impact folks describe in their papers.

Honza
> 
> Thank you!
> 
> -Ghassan
> 
> 
> On Tue, 15 Feb 2005, Vladimir Makarov wrote:
> 
> > Vladimir Makarov wrote:
> >
> > > Ghassan Shobaki wrote:
> > >
> > >> Hi,
> > >>
> > >> I have previously studied superblock scheduling by importing
> > >> superblock DAGs from gcc and feeding them into my scheduler (I have
> > >> published my results at Micro in case you are interested:
> > >> http://www.microarch.org/micro37/papers/25_Shobaki-Superblock.pdf)
> > >>
> > > Thanks for the article, Ghassan.  But I don't think this is the first
> > > optimal algorithm as you wrote in your introdauction.  I implemented
> > > an analogous approach about seven years ago.  And I am sure I am not
> > > the first.
> > >
> > Ghassan, my appologies.  I've read your article.  What I wrote was about
> > optimal basic blocks scheduling.  I've not seen articles about optimal
> > scheduling beyond basic blocks.  So most probably your article is really
> > the first published work about optimal scheduling of superblocks.
> >
> > My appologies again.
> >
> > Vlad
> >
> >