Superblock Instruction Scheduling in GCC

Superblock Instruction Scheduling in GCC

[Ghassan Shobaki]

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?

Thanks

-Ghassan

Re: Superblock Instruction Scheduling in GCC

[Vladimir N. Makarov]

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.

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.


Vlad

Re: Superblock Instruction Scheduling in GCC

[Jan Hubicka]

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

Re: Superblock Instruction Scheduling in GCC

[Ghassan Shobaki]

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?

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?

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.

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

Re: Superblock Instruction Scheduling in GCC

[Jan Hubicka]

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

Re: Superblock Instruction Scheduling in GCC

[Vladimir Makarov]

Jan Hubicka wrote:
> 
> >
> > 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.
> 

  Actually the first cycle multipass instruction scheduling tries only
to maximize number of insns issued on the current cycle.  An optimal
insn scheduling should minimize execution time of scheduled code which
means it might require to issue not maximal number of insns on a cycle. 
Also the first cycle multipass insn scheduling solves the task in a
primitive way (just trying part of permutations of ready insns without
reusing already evaluated information from other tried permutation). 
This algorithm was just a demonstration of fast work DFA hazard
recognizer.  It improves code for Itanium (as I remember about 2% for
SPECINT2000).

  As for optimal insn scheduling, I wrote a prototype for BB 2-3 years
ago.  It was based on a dynamic programing approach (reusing already
evaluated information about scheduled insn subsequences).  It worked
fast for sequences up to 15-20 insns for ultrasparc.  I see some
improvements (say 7 cycles instead of 9 cycles) for about 30% of bbs on
small benchmarks.  I see the following problem with this approach for
gcc as an industrial compiler:

   1. Gcc has a lot of scheduler hooks which are oriented to list insn
scheduling algorithm.  Many ports uses them.  It is practically
impossible to embed these hooks into an optimal insn scheduling
algorithm.

   2. Long sequences of insns should be divided to keep the algorithm
speed acceptable.  Simple approach to this might work even worse than
list insn scheduling.  Some information (like when data from previous
subsequence will be ready) should be transferred from one subsequence to
another sequence.

  3.  Modern insn scheduling algorithms are now not only about insn
rearranging (in linear code) but can include many other transformations
like code cloning, predication, data/control flow speculation.  I don't
see how these transformations could be a part of an optimal insn
scheduling).  And I think there is more code improving potential using
these transformations than an optimal scheduling.  Although there is
definitely some areas where an optimal scheduling could be useful.

In any case, it would be very interesting to see the results of your
research.  We should encourage people to make researches on gcc.

Vlad

Re: Superblock Instruction Scheduling in GCC

[Ghassan Shobaki]

I could not check out the integrated patch since the cvs server is
currently down. On the other hand, when I tried to add the patch (as
published on the web) manually on top of release 3.3.1 the resulting
binary failed. I am not sure if I did something wrong or just needed
to do that on top of a more recent version of the gcc code.
So, I am kind of stuck at this point. Do you have any source files that I
can add on top of release 3.3.1 or 3.3.2 to enable superblock scheduling?

Thanks

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

Superblock Instruction Scheduling in GCC 3.4

[Ghassan Shobaki]

Hi,

I am currently experimenting with superblock scheduling in a prerelease
version (20040114) of gcc 3.4 on the spec2000 benchmarks. I have
a few questions:

The version that I have does not seem to accept the
-fsched2-use-traces command line switch. So I went a head and set the
following global variables in toplev.c in order to enforce superblock
formation and scheduling:

int flag_optimize = 1;
int flag_schedule_insns = 1;
int flag_schedule_insns_after_reload = 1;
int flag_sched2_use_traces = 1;

Q1. Is there a known bug in version 3.4 related to command-line options?
    Or I am doing something wrong?

Q2. Should I set the following flag as well?
int flag_branch_probabilities = ?;
I tried it both ways and the superblocks generated when this flag is
RESET are on average larger and have more branches in them (they are much
harder to schedule), which does not make sense to me. What is superblock
formation based on when branch probablities are not computed? It seems to
me that setting this flag should be necessary!

Q3. Are there any other flags that I need to set in order to ensure
proper superblock formation?

Q3. I have looked into the trace formation code in tracer.c and was
confused about three different terms related to about the same
concept : probability, count and frequency. Is there a documention that
precisely defines each of these three terms and how they are used in
trace formation?

Thanks

-Ghassan

Re: Superblock Instruction Scheduling in GCC 3.4

[Jan Hubicka]

> Hi,
> 
> I am currently experimenting with superblock scheduling in a prerelease
> version (20040114) of gcc 3.4 on the spec2000 benchmarks. I have
> a few questions:
> 
> The version that I have does not seem to accept the
> -fsched2-use-traces command line switch. So I went a head and set the
> following global variables in toplev.c in order to enforce superblock
> formation and scheduling:
> 
> int flag_optimize = 1;
> int flag_schedule_insns = 1;
> int flag_schedule_insns_after_reload = 1;
> int flag_sched2_use_traces = 1;
> 
> Q1. Is there a known bug in version 3.4 related to command-line options?
>     Or I am doing something wrong?

I jus ttested and -fsched2-use-traces seems to just work for me.  What
kind of problems do you get?
> 
> Q2. Should I set the following flag as well?
> int flag_branch_probabilities = ?;
> I tried it both ways and the superblocks generated when this flag is
> RESET are on average larger and have more branches in them (they are much
> harder to schedule), which does not make sense to me. What is superblock
> formation based on when branch probablities are not computed? It seems to
> me that setting this flag should be necessary!

Yes, however it should be implied by -O2 flag.
You also may want the profile feedback.  Without -fbranch-probabilities
you won't get any superblocks formed.
> 
> Q3. Are there any other flags that I need to set in order to ensure
> proper superblock formation?

I think -O2 -fsched2-use-traces shall do what you want.
> 
> Q3. I have looked into the trace formation code in tracer.c and was
> confused about three different terms related to about the same
> concept : probability, count and frequency. Is there a documention that
> precisely defines each of these three terms and how they are used in
> trace formation?

You may take a look at cfg.texi documentation I sent to mailing list
year or two ago, but it never went into official sources.
In general the count represent number of execution of given edge/block
when profile is read from feedback.  It is 64bit number.
Each basic block has frequence that represent how commonly it is
executed relative to REG_FREQ_BASE.  It is 32bit number and the most
frequent basic block is known to have REG_FREQ_BASE frequency at the
time profile was built, so it is easier to manipulate with when you
don't care about exactness and it is also available without profile
feedback based on guesses made by compiler.
Probablity is set for edges and represent probability that control flow
will leave basic block via that edge, again relative to REG_FREQ_BASE.

Honza
> 
> Thanks
> 
> -Ghassan

Re: Superblock Instruction Scheduling in GCC 3.4

[Ghassan Shobaki]

Ok, I have just verified that gcc DOES accept the -fsched2-use-tracer and
invoke the ebb scheduler as expected. However, it does not set the
flag_branch_probabilities automatically. It only sets it when I
explicitly use the -fbranch-probabilities command-line switch. Here are
the two cases that I have tried:

g++ -O3 -fsched2-use-traces
Generates ~151K superblocks on my benchmark suite with lots of large
superblocks that include 10 basic blocks or more

g++ -O3 -fsched2-use-traces -fbranch-probabilities
Generates only ~123K superblocks on my benchmark suite with the vast
majority of superblocks consisting of less than 10 basic blocks

So, the question is: Why did the compiler generate more superblocks
when branch probabilities were not computed? Do the superblocks generated
in that case make any sense?
And the bottom line question for me is: which setting should I use in my
research on superblocks?

Thanks

-Ghassan


On Wed, 28 Jan 2004, Jan Hubicka wrote:

> > Hi,
> >
> > I am currently experimenting with superblock scheduling in a prerelease
> > version (20040114) of gcc 3.4 on the spec2000 benchmarks. I have
> > a few questions:
> >
> > The version that I have does not seem to accept the
> > -fsched2-use-traces command line switch. So I went a head and set the
> > following global variables in toplev.c in order to enforce superblock
> > formation and scheduling:
> >
> > int flag_optimize = 1;
> > int flag_schedule_insns = 1;
> > int flag_schedule_insns_after_reload = 1;
> > int flag_sched2_use_traces = 1;
> >
> > Q1. Is there a known bug in version 3.4 related to command-line options?
> >     Or I am doing something wrong?
>
> I jus ttested and -fsched2-use-traces seems to just work for me.  What
> kind of problems do you get?
> >
> > Q2. Should I set the following flag as well?
> > int flag_branch_probabilities = ?;
> > I tried it both ways and the superblocks generated when this flag is
> > RESET are on average larger and have more branches in them (they are much
> > harder to schedule), which does not make sense to me. What is superblock
> > formation based on when branch probablities are not computed? It seems to
> > me that setting this flag should be necessary!
>
> Yes, however it should be implied by -O2 flag.
> You also may want the profile feedback.  Without -fbranch-probabilities
> you won't get any superblocks formed.
> >
> > Q3. Are there any other flags that I need to set in order to ensure
> > proper superblock formation?
>
> I think -O2 -fsched2-use-traces shall do what you want.
> >
> > Q3. I have looked into the trace formation code in tracer.c and was
> > confused about three different terms related to about the same
> > concept : probability, count and frequency. Is there a documention that
> > precisely defines each of these three terms and how they are used in
> > trace formation?
>
> You may take a look at cfg.texi documentation I sent to mailing list
> year or two ago, but it never went into official sources.
> In general the count represent number of execution of given edge/block
> when profile is read from feedback.  It is 64bit number.
> Each basic block has frequence that represent how commonly it is
> executed relative to REG_FREQ_BASE.  It is 32bit number and the most
> frequent basic block is known to have REG_FREQ_BASE frequency at the
> time profile was built, so it is easier to manipulate with when you
> don't care about exactness and it is also available without profile
> feedback based on guesses made by compiler.
> Probablity is set for edges and represent probability that control flow
> will leave basic block via that edge, again relative to REG_FREQ_BASE.
>
> Honza
> >
> > Thanks
> >
> > -Ghassan
>

Re: Superblock Instruction Scheduling in GCC 3.4

[Jan Hubicka]

> 
> Ok, I have just verified that gcc DOES accept the -fsched2-use-tracer and
> invoke the ebb scheduler as expected. However, it does not set the
> flag_branch_probabilities automatically. It only sets it when I
> explicitly use the -fbranch-probabilities command-line switch. Here are
> the two cases that I have tried:
> 
> g++ -O3 -fsched2-use-traces
> Generates ~151K superblocks on my benchmark suite with lots of large
> superblocks that include 10 basic blocks or more
> 
> g++ -O3 -fsched2-use-traces -fbranch-probabilities
> Generates only ~123K superblocks on my benchmark suite with the vast
> majority of superblocks consisting of less than 10 basic blocks

-fbranch-probabilities can be accpeted only when program has been
earlier profiled.  GCC does have logic for statically guessing the
branch outcomes when these are not available
(-fguess-branch-probability) so the superblocks can be built, just they
are inferrior to those built with feedback available.
> 
> So, the question is: Why did the compiler generate more superblocks
> when branch probabilities were not computed? Do the superblocks generated
> in that case make any sense?
> And the bottom line question for me is: which setting should I use in my
> research on superblocks?

It is always better to use the profile, so I would recommend you
-fbranch-probabilities unless you are interested in experiments with
static prediction algorithms.

Honza

Re: Superblock Instruction Scheduling in GCC 3.4

[Ghassan Shobaki]

Eventually, I will be doing profile-based experiments. However, at this
point I am interested in static probabilities because it is an easier option
that will allow me to get some initial results more quickly.
Now, my question is: when I used the f-branch-probablities switch without
doing profiling first, gcc still accepted it and generated some
superblocks. Were these invalid superblocks or what?

Thanks

-Ghassan


On Thu, 29 Jan 2004, Jan Hubicka wrote:

> >
> > Ok, I have just verified that gcc DOES accept the -fsched2-use-tracer and
> > invoke the ebb scheduler as expected. However, it does not set the
> > flag_branch_probabilities automatically. It only sets it when I
> > explicitly use the -fbranch-probabilities command-line switch. Here are
> > the two cases that I have tried:
> >
> > g++ -O3 -fsched2-use-traces
> > Generates ~151K superblocks on my benchmark suite with lots of large
> > superblocks that include 10 basic blocks or more
> >
> > g++ -O3 -fsched2-use-traces -fbranch-probabilities
> > Generates only ~123K superblocks on my benchmark suite with the vast
> > majority of superblocks consisting of less than 10 basic blocks
>
> -fbranch-probabilities can be accpeted only when program has been
> earlier profiled.  GCC does have logic for statically guessing the
> branch outcomes when these are not available
> (-fguess-branch-probability) so the superblocks can be built, just they
> are inferrior to those built with feedback available.
> >
> > So, the question is: Why did the compiler generate more superblocks
> > when branch probabilities were not computed? Do the superblocks generated
> > in that case make any sense?
> > And the bottom line question for me is: which setting should I use in my
> > research on superblocks?
>
> It is always better to use the profile, so I would recommend you
> -fbranch-probabilities unless you are interested in experiments with
> static prediction algorithms.
>
> Honza
>

Re: Superblock Instruction Scheduling in GCC 3.4

[Jan Hubicka]

> 
> Eventually, I will be doing profile-based experiments. However, at this
> point I am interested in static probabilities because it is an easier option
> that will allow me to get some initial results more quickly.
> Now, my question is: when I used the f-branch-probablities switch without
> doing profiling first, gcc still accepted it and generated some
> superblocks. Were these invalid superblocks or what?

With -fbranch-probabilities and no profile, GCC will assume that all the
blocks were never executed and conclude that they are cold.  This limits
several algorithms to more or less optimize for size rather than speed.
So if you want traces based on static predictions, you should be using
-fguess-branch-probability (default by -O2) and not
-fbranch-probabilities.

Honza
> 
> Thanks
> 
> -Ghassan
> 
> 
> On Thu, 29 Jan 2004, Jan Hubicka wrote:
> 
> > >
> > > Ok, I have just verified that gcc DOES accept the -fsched2-use-tracer and
> > > invoke the ebb scheduler as expected. However, it does not set the
> > > flag_branch_probabilities automatically. It only sets it when I
> > > explicitly use the -fbranch-probabilities command-line switch. Here are
> > > the two cases that I have tried:
> > >
> > > g++ -O3 -fsched2-use-traces
> > > Generates ~151K superblocks on my benchmark suite with lots of large
> > > superblocks that include 10 basic blocks or more
> > >
> > > g++ -O3 -fsched2-use-traces -fbranch-probabilities
> > > Generates only ~123K superblocks on my benchmark suite with the vast
> > > majority of superblocks consisting of less than 10 basic blocks
> >
> > -fbranch-probabilities can be accpeted only when program has been
> > earlier profiled.  GCC does have logic for statically guessing the
> > branch outcomes when these are not available
> > (-fguess-branch-probability) so the superblocks can be built, just they
> > are inferrior to those built with feedback available.
> > >
> > > So, the question is: Why did the compiler generate more superblocks
> > > when branch probabilities were not computed? Do the superblocks generated
> > > in that case make any sense?
> > > And the bottom line question for me is: which setting should I use in my
> > > research on superblocks?
> >
> > It is always better to use the profile, so I would recommend you
> > -fbranch-probabilities unless you are interested in experiments with
> > static prediction algorithms.
> >
> > Honza
> >

Re: Superblock Instruction Scheduling in GCC 3.4

[Ghassan Shobaki]

That explains the results the I am getting. Things make sense to me now.

Thank you very much!

-Ghassan

On Sun, 1 Feb 2004, Jan Hubicka wrote:

> >
> > Eventually, I will be doing profile-based experiments. However, at this
> > point I am interested in static probabilities because it is an easier option
> > that will allow me to get some initial results more quickly.
> > Now, my question is: when I used the f-branch-probablities switch without
> > doing profiling first, gcc still accepted it and generated some
> > superblocks. Were these invalid superblocks or what?
>
> With -fbranch-probabilities and no profile, GCC will assume that all the
> blocks were never executed and conclude that they are cold.  This limits
> several algorithms to more or less optimize for size rather than speed.
> So if you want traces based on static predictions, you should be using
> -fguess-branch-probability (default by -O2) and not
> -fbranch-probabilities.
>
> Honza
> >
> > Thanks
> >
> > -Ghassan
> >
> >
> > On Thu, 29 Jan 2004, Jan Hubicka wrote:
> >
> > > >
> > > > Ok, I have just verified that gcc DOES accept the -fsched2-use-tracer and
> > > > invoke the ebb scheduler as expected. However, it does not set the
> > > > flag_branch_probabilities automatically. It only sets it when I
> > > > explicitly use the -fbranch-probabilities command-line switch. Here are
> > > > the two cases that I have tried:
> > > >
> > > > g++ -O3 -fsched2-use-traces
> > > > Generates ~151K superblocks on my benchmark suite with lots of large
> > > > superblocks that include 10 basic blocks or more
> > > >
> > > > g++ -O3 -fsched2-use-traces -fbranch-probabilities
> > > > Generates only ~123K superblocks on my benchmark suite with the vast
> > > > majority of superblocks consisting of less than 10 basic blocks
> > >
> > > -fbranch-probabilities can be accpeted only when program has been
> > > earlier profiled.  GCC does have logic for statically guessing the
> > > branch outcomes when these are not available
> > > (-fguess-branch-probability) so the superblocks can be built, just they
> > > are inferrior to those built with feedback available.
> > > >
> > > > So, the question is: Why did the compiler generate more superblocks
> > > > when branch probabilities were not computed? Do the superblocks generated
> > > > in that case make any sense?
> > > > And the bottom line question for me is: which setting should I use in my
> > > > research on superblocks?
> > >
> > > It is always better to use the profile, so I would recommend you
> > > -fbranch-probabilities unless you are interested in experiments with
> > > static prediction algorithms.
> > >
> > > Honza
> > >
>

Superblock Scheduling Alg in GCC

[Ghassan Shobaki]

Are there any documents describing the algorithm used in the superblock instruction 
scheduler? 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?

Thanks

-Ghassan
 

Re: Superblock Scheduling Alg in GCC

[Vladimir Makarov]

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.

Re: Superblock Scheduling Alg in GCC

[Vladimir Makarov]

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.

Vlad

Re: Superblock Scheduling Alg in GCC

[Jan Hubicka]

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

Re: Superblock Scheduling Alg in GCC

[Ghassan Shobaki]

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

Re: Superblock Scheduling Alg in GCC

[Vladimir Makarov]

Ghassan Shobaki wrote:

>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.
>
>  
>
Yes, I am interesting in this.  Could you give me the reference to WCP 
details (I can not find the document on the Internet).   I could give it 
a try.  May be this approach will work.

Vlad

Re: Superblock Scheduling Alg in GCC

[Ghassan Shobaki]

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