Re: disabling branch probability guessing (patch)

Re: disabling branch probability guessing (patch)

[Andi Kleen]

Aldy Hernandez <aldyh@redhat.com> writes:

> hi guys.
> 
> Here is a patch that adds an option to disable guessing of branch
> probabilities (-fno-guess-branch-probability).
> 
> One of our clients is trying to use __builtin_expect and is getting
> unexpected results because estimate_probability() in predict.c is 
> guessing the branch probability in an undetermined way.  This patch
> solves the problem by providing an option to disable the probability
> guessing altogether.

Cool. This is useful for the linux kernel too. I found out that the 
prediction guessing undoes some of the carefully crafted goto woods
to keep fast paths jumpless.


e.g.

f()
{
        int err = -EBLA; 
        if (unlikely error case) 
                goto error;
        ...


        err = 0; 
out:
        return err;
}
   
is turned by 2.97 when the error test isn't liked by predict.c 
into

f()
{
        if (error case) { 
                return -EBLA;   
        } 

        ...
} 
  
which involves a jump in the common path.


-Andi

Re: disabling branch probability guessing (patch)

[Aldy Hernandez]

> > One of our clients is trying to use __builtin_expect and is getting
> > unexpected results because estimate_probability() in predict.c is 
> > guessing the branch probability in an undetermined way.  This patch
> > solves the problem by providing an option to disable the probability
> > guessing altogether.
> 
> Cool. This is useful for the linux kernel too. I found out that the 
> prediction guessing undoes some of the carefully crafted goto woods
> to keep fast paths jumpless.
> 
> 
> e.g.
> 
> f()
> {
>         int err = -EBLA; 
>         if (unlikely error case) 
>                 goto error;

Why don't you use __builtin_expect() for this?

ala:

	if (__builtin_expect(unlikely error case, 0))
		goto error;
	blah blah

This will place the code in "blah blah" in the fall through path which
is the expected path.  Of course, I have a test case for the i960 in which
this isn't working as advertised, but at least it seems to working fine
for the x86. :-)

Cheers.
Aldy

Re: disabling branch probability guessing (patch)

[Joe Buck]

> > Here is a patch that adds an option to disable guessing of branch
> > probabilities (-fno-guess-branch-probability).

Ouch.  The user has to enter a flag to get the right thing.

Andi Kleen writes:
> Cool. This is useful for the linux kernel too. I found out that the 
> prediction guessing undoes some of the carefully crafted goto woods
> to keep fast paths jumpless.

I'm not sure that this is really the right solution.  In all examples
in which I've seen gotos used by good programmers, the goto is an
exceptional condition and should be predicted not-taken.  Can't we
just flag branches originally entered as gotos?

Re: disabling branch probability guessing (patch)

[Andi Kleen]

On Tue, Jan 16, 2001 at 08:55:36AM -0800, Joe Buck wrote:
> Andi Kleen writes:
> > Cool. This is useful for the linux kernel too. I found out that the 
> > prediction guessing undoes some of the carefully crafted goto woods
> > to keep fast paths jumpless.
> 
> I'm not sure that this is really the right solution.  In all examples
> in which I've seen gotos used by good programmers, the goto is an
> exceptional condition and should be predicted not-taken.  Can't we
> just flag branches originally entered as gotos?

I agree that that would be a good heuristic. Assume goto as not taken. 


-Andi

Re: disabling branch probability guessing (patch) [another patch]

[Aldy Hernandez]

>>>>> "Andi" == Andi Kleen <ak@suse.de> writes:

 > On Tue, Jan 16, 2001 at 08:55:36AM -0800, Joe Buck wrote:
 >> Andi Kleen writes:
 >> > Cool. This is useful for the linux kernel too. I found out that the 
 >> > prediction guessing undoes some of the carefully crafted goto woods
 >> > to keep fast paths jumpless.
 >> 
 >> I'm not sure that this is really the right solution.  In all examples
 >> in which I've seen gotos used by good programmers, the goto is an
 >> exceptional condition and should be predicted not-taken.  Can't we
 >> just flag branches originally entered as gotos?

 > I agree that that would be a good heuristic. Assume goto as not taken. 

Alright.  I did some playing around to predict gotos as not taken
(patch below).  It seems to work pretty good.

I have a few questions though...

I tested this on a couple of x86 bootstraps.  My "benchmark" was
running a freshly built gcc (with and without the new prediction)
against "gcc/stmt.i" and timing the compilations.

The patch below speeds things up by a few nanoseconds-- if that.  The
unix "time" doesn't seem to be very good for benchmarks.

What program can I use to time other programs?

What's a good way of doing benchmarks?

Is there some kind free benchmarking program I can use?

What's a good architecture to test this out-- preferable one with a
high penalty for missed branch predictions?

And finally, is the patch below correct?  I deduct that gotos are
jumps with text labels.

Cheers.
Aldy

Index: predict.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/predict.c,v
retrieving revision 1.13
diff -c -r1.13 predict.c
*** predict.c	2000/05/19 22:27:26	1.13
--- predict.c	2001/01/20 06:47:42
***************
*** 111,117 ****
    for (i = 0; i < n_basic_blocks - 1; i++)
      {
        rtx last_insn = BLOCK_END (i);
!       rtx cond, earliest;
        int prob;
        edge e;
  
--- 111,117 ----
    for (i = 0; i < n_basic_blocks - 1; i++)
      {
        rtx last_insn = BLOCK_END (i);
!       rtx cond, earliest, label;
        int prob;
        edge e;
  
***************
*** 121,126 ****
--- 121,135 ----
  
        if (find_reg_note (last_insn, REG_BR_PROB, 0))
  	continue;
+ 
+       /* Predict gotos as false.  */
+       label = JUMP_LABEL (last_insn);
+       if (GET_CODE (label) == CODE_LABEL
+ 	  && XSTR (label, 6))
+ 	{
+ 	  prob = PROB_UNLIKELY;
+ 	  goto emitnote;
+ 	}
  
        cond = get_condition (last_insn, &earliest);
        if (! cond)

Re: disabling branch probability guessing (patch) [another patch]

[Richard Henderson]

On Sat, Jan 20, 2001 at 03:03:30AM -0400, Aldy Hernandez wrote:
>  > I agree that that would be a good heuristic. Assume goto as not taken. 
> 
> Alright.  I did some playing around to predict gotos as not taken
> (patch below).  It seems to work pretty good.

I don't necessarily agree that this is a good heuristic.  It assumes
a rather rigid adherence to one programming style.  One that doesn't
apply at all to machine generated code I might add.

Placed as this check is, we get no chance to make potentially better
guesses based on the shape of the CFG or other tell-tales.  I wouldn't
mind this test as one of several being combined, but on its own I'm
dubious.


r~

Re: disabling branch probability guessing (patch) [another patch]

[Aldy Hernandez]

On Mon, Jan 22, 2001 at 02:17:31PM -0800, Richard Henderson wrote:
> On Sat, Jan 20, 2001 at 03:03:30AM -0400, Aldy Hernandez wrote:
> >  > I agree that that would be a good heuristic. Assume goto as not taken. 
> > 
> > Alright.  I did some playing around to predict gotos as not taken
> > (patch below).  It seems to work pretty good.
> 
> I don't necessarily agree that this is a good heuristic.  It assumes
> a rather rigid adherence to one programming style.  One that doesn't
> apply at all to machine generated code I might add.
> 
> Placed as this check is, we get no chance to make potentially better
> guesses based on the shape of the CFG or other tell-tales.  I wouldn't
> mind this test as one of several being combined, but on its own I'm
> dubious.

i'm been thinking about this and i would have to agree with this...

the few times when this might be useful is when we do not use any of the
other predictors.  stuff like this:

	if (foo > 0)
		goto blah;

this gets missed because we predict >= 0 to be true-- so in this case the
goto heuristic might win, but i'm guessing that that rarely happens.

i'm still kinda wanting to get better benchmarking software so i can try
a few other heuristics.

aldy

Re: disabling branch probability guessing (patch) [another patch]

[Tim Prince]

I've been fighting a lonely battle for "predicting" (or favoring) the
branch which leads to iteration.  Some of the current compilers do a
lousy job of

for( ; ; ){
....
if(done){
    .....
    break;}
.....
}

as the scheme of always assuming forward jumps not taken implies in this
common situation that the loop never repeats.  Until I saw the current
crop of compilers, I thought that favoring the branch which leads to
continued iteration was a usual practice.  Yes, there's are work-around,
always place a break in an else branch, but I never before saw code
written in this style:

.....
if(!done);
else {
....
break;}
.....

----- Original Message -----
From: "Richard Henderson" <rth@redhat.com>
To: "Aldy Hernandez" <aldyh@redhat.com>
Cc: "Andi Kleen" <ak@suse.de>; "Joe Buck" <jbuck@racerx.synopsys.com>;
<gcc@gcc.gnu.org>
Sent: Monday, January 22, 2001 2:17 PM
Subject: Re: disabling branch probability guessing (patch) [another
patch]


> On Sat, Jan 20, 2001 at 03:03:30AM -0400, Aldy Hernandez wrote:
> >  > I agree that that would be a good heuristic. Assume goto as not
taken.
> >
> > Alright.  I did some playing around to predict gotos as not taken
> > (patch below).  It seems to work pretty good.
>
> I don't necessarily agree that this is a good heuristic.  It assumes
> a rather rigid adherence to one programming style.  One that doesn't
> apply at all to machine generated code I might add.
>
> Placed as this check is, we get no chance to make potentially better
> guesses based on the shape of the CFG or other tell-tales.  I wouldn't
> mind this test as one of several being combined, but on its own I'm
> dubious.
>
>
> r~

Re: disabling branch probability guessing (patch) [another patch]

[Aldy Hernandez]

On Mon, Jan 22, 2001 at 08:51:58PM -0800, Tim Prince wrote:
> I've been fighting a lonely battle for "predicting" (or favoring) the
> branch which leads to iteration.  Some of the current compilers do a
> lousy job of

The Ball and Larus paper referenced in predict.c has a heuristic (loop
heuristic) for choosing the path that executes rather than avoids a loop--
regardless of loop direction.

This will probably do what you want and I'm going to start working on
loop, call, and return heuristics "real soon now" :).

aldy