RE: Superblock Instruction Scheduling in GCC 3.4

RE: Superblock Instruction Scheduling in GCC 3.4

[S. Bosscher]

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

A more up-to-date (but still unfinished) version of that text is here:
http://gcc.gnu.org/ml/gcc/2004-01/msg01130.html

Gr.
Steven

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

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]

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]

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

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]

> 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

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