Re: __builtin_expect for indirect function calls

Re: __builtin_expect for indirect function calls

[Ross Ridge]

Mark Mitchell writes:
> What do people think?  Do we have the leeway to change this?

If it were just cases where using __builtin_expect is pointless that
would break, like function overloading and sizeof then I don't think
it would be a problem.  However, it would change behaviour when C++
conversion operators are used and I can see these being legitimately
used with __builtin_expect.  Something like:

	struct C {
		operator long();
	};

	int foo() {
		if (__builtin_expect(C(), 0))
			return 1;
		return 2;
	}

If cases like these are rare enough it's probably an acceptable change
if they give an error because the argument types don't match.

					Ross Ridge

__builtin_expect for indirect function calls

[trevor_smigiel]

Hi,

I'm looking for comments on a possible GCC extensions described below.

For the target I'm interested in, Cell SPU, taken branches are only
predicted correctly by explicitly inserting a specific instructions (a
hint instruction) that says "the branch at address A is branching to
address B".  This allows the processor to prefetch the instructions at
B, potentially with no penalty.

For indirect function calls, the ideal case is we know the target soon
enough at run-time that the hint instruction simply specifies the real
target.  Soon enough means about 18 cycles before the execution of the
branch.  I don't have any numbers as to how often this happens, but
there are enough cases where it doesn't.

When we can't hint the real target, we want to hint the most common
target.   There are potentially clever ways for the compiler to do this
automatically, but I'm most interested in giving the user some way to do
it explicitly.  One possiblity is to have something similar to
__builtin_expect, but for functions.  For example, I propose:

  __builtin_expect_call (FP, PFP)

which returns the value of FP with the same type as FP, and tells the
compiler that PFP is the expected target of FP.  Trival examples:

  typedef void (*fptr_t)(void);

  extern void foo(void);

  void
  call_fp (fptr_t fp)
  {
    /* Call the function pointed to by fp, but predict it as if it is
       calling foo() */
    __builtin_expect_call (fp, foo)();
  }

  void
  call_fp_predicted (fptr_t fp, fptr_t predicted)
  {
    /* same as above but the function we are calling doesn't have to be
       known at compile time */
    __builtin_expect_call (fp, predicted)();
  }

I believe I can add this just for the SPU target without effecting
anything else, but it could be useful for other targets.

Are there any comments about the name, semantics, or usefulness of this
extension?

Thanks,
Trevor

Re: __builtin_expect for indirect function calls

[Jonathan Adamczewski]

trevor_smigiel@playstation.sony.com wrote:
> Are there any comments about the name, semantics, or usefulness of this
> extension?
>   

Sounds very useful for SPU code. I look forward to trying it out.


Toying with the idea, the following seems like a potentially useful C++
form of the proposed extension :

struct A {
virtual void foo();
};

struct B : public A {
virtual void foo();
};

A* a;

...

__builtin_expect_call (a->foo, B::foo)();



jonathan.

Re: __builtin_expect for indirect function calls

[Hans-Peter Nilsson]

On Mon, 17 Dec 2007, trevor_smigiel@playstation.sony.com wrote:
> When we can't hint the real target, we want to hint the most common
> target.   There are potentially clever ways for the compiler to do this
> automatically, but I'm most interested in giving the user some way to do
> it explicitly.  One possiblity is to have something similar to
> __builtin_expect, but for functions.  For example, I propose:
>
>   __builtin_expect_call (FP, PFP)

Is there a hidden benefit?  I mean, isn't this really
expressable using builtin_expect as-is, at least when it comes
to the syntax?  Like:

>
> which returns the value of FP with the same type as FP, and tells the
> compiler that PFP is the expected target of FP.  Trival examples:
>
>   typedef void (*fptr_t)(void);
>
>   extern void foo(void);
>
>   void
>   call_fp (fptr_t fp)
>   {
>     /* Call the function pointed to by fp, but predict it as if it is
>        calling foo() */
>     __builtin_expect_call (fp, foo)();

__builtin_expect (fp, foo);  /* alt __builtin_expect (fp == foo, 1); */
fp ();

>   }
>
>   void
>   call_fp_predicted (fptr_t fp, fptr_t predicted)
>   {
>     /* same as above but the function we are calling doesn't have to be
>        known at compile time */
>     __builtin_expect_call (fp, predicted)();

__builtin_expect (fp, predicted);
fp();

I guess the information just isn't readily available in the
preferred form when needed and *that* part could more or less
simply be fixed?

brgds, H-P

Re: __builtin_expect for indirect function calls

[Mark Mitchell]

Hans-Peter Nilsson wrote:
> On Mon, 17 Dec 2007, trevor_smigiel@playstation.sony.com wrote:
>> When we can't hint the real target, we want to hint the most common
>> target.   There are potentially clever ways for the compiler to do this
>> automatically, but I'm most interested in giving the user some way to do
>> it explicitly.  One possiblity is to have something similar to
>> __builtin_expect, but for functions.  For example, I propose:
>>
>>   __builtin_expect_call (FP, PFP)
> 
> Is there a hidden benefit?  I mean, isn't this really
> expressable using builtin_expect as-is, at least when it comes
> to the syntax?  

That was my first thought as well.  Before we add __builtin_expect_call,
I think there needs to be a justification of why this can't be done with
__builtin_expect as-is.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: __builtin_expect for indirect function calls

[trevor_smigiel]

If possible, I agree it seems natural to extend __builtin_expect.  My
concern would be backwards compatibility.

Currently, the prototype for __builtin_expect is

    long __builtin_expect (long expression, long constant);

Extending it to functions would change it to

    T __builtin_expect (T expression, T expected);

With these additional semantics and restrictions:
    - when the return value is being used as a call expression:
      * T is the type of 'expression'
      * 'expected' is allowed to be a non-constant
    - when the return value is not being used as a call expression:
      * T is type 'long;
      * 'expected' must be a compile-time constant

Given the above definition, I don't think there is any backwards
compatibility issues because we are inspecting the context of the
use of __builtin_expect.

Rather than the above definition, we could choose not to inspect the
context and just say:
    * T is the type of 'expression'
    * 'expected' is allowed to be a non-constant

In this case I think there would only be compatibility issues with
unusual uses of __builtin_expect, for example, if it was being used in a
function argument and its type effected overload resolution. Or if the
argument was a float and was being implicitly converted to a long (with
a warning).  There would also be code which previously gave warnings but
does not with the extended __builtin_expect.

I'm ok with either of these definitions, if extending __builtin_expect
is the preferred way to go.

Are either of these definitions ok?  Or are there other ideas how to
define it?

Trevor

* Mark Mitchell <mark@codesourcery.com> [2008-01-03 12:12]:
> Hans-Peter Nilsson wrote:
> > On Mon, 17 Dec 2007, trevor_smigiel@playstation.sony.com wrote:
> >> When we can't hint the real target, we want to hint the most common
> >> target.   There are potentially clever ways for the compiler to do this
> >> automatically, but I'm most interested in giving the user some way to do
> >> it explicitly.  One possiblity is to have something similar to
> >> __builtin_expect, but for functions.  For example, I propose:
> >>
> >>   __builtin_expect_call (FP, PFP)
> > 
> > Is there a hidden benefit?  I mean, isn't this really
> > expressable using builtin_expect as-is, at least when it comes
> > to the syntax?  
> 
> That was my first thought as well.  Before we add __builtin_expect_call,
> I think there needs to be a justification of why this can't be done with
> __builtin_expect as-is.
> 
> -- 
> Mark Mitchell
> CodeSourcery
> mark@codesourcery.com
> (650) 331-3385 x713

Re: __builtin_expect for indirect function calls

[Mark Mitchell]

trevor_smigiel@playstation.sony.com wrote:

> Currently, the prototype for __builtin_expect is
> 
>     long __builtin_expect (long expression, long constant);
> 
> Extending it to functions would change it to
> 
>     T __builtin_expect (T expression, T expected);

Yes, it really makes more sense for __builtin_expect to be polymorphic
in this way anyhow.  I consider it a design wart that it's defined in
terms of "long".  (For example, this means you can't use it for "long
long"!)

> Rather than the above definition, we could choose not to inspect the
> context and just say:
>     * T is the type of 'expression'
>     * 'expected' is allowed to be a non-constant
> 
> In this case I think there would only be compatibility issues with
> unusual uses of __builtin_expect, for example, if it was being used in a
> function argument and its type effected overload resolution.

I think this is the abstractly right approach.  However, you're right
that there are backwards-compatibility issues.  Another issue is that on
platforms where "long" and "int" do not have the same width, something like:

  sizeof(__builtin_expect(1, 1))

will change its value.  And, the current prototype is documented in the
manual.

What do people think?  Do we have the leeway to change this?  Or should
we add __builtin_expect2?  Or add an -fno-polymorphic-builtin-expect?
Or...?

Thanks,

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: __builtin_expect for indirect function calls

[Richard Guenther]

On Jan 5, 2008 6:43 AM, Mark Mitchell <mark@codesourcery.com> wrote:
> trevor_smigiel@playstation.sony.com wrote:
>
> > Currently, the prototype for __builtin_expect is
> >
> >     long __builtin_expect (long expression, long constant);
> >
> > Extending it to functions would change it to
> >
> >     T __builtin_expect (T expression, T expected);
>
> Yes, it really makes more sense for __builtin_expect to be polymorphic
> in this way anyhow.  I consider it a design wart that it's defined in
> terms of "long".  (For example, this means you can't use it for "long
> long"!)
>
> > Rather than the above definition, we could choose not to inspect the
> > context and just say:
> >     * T is the type of 'expression'
> >     * 'expected' is allowed to be a non-constant
> >
> > In this case I think there would only be compatibility issues with
> > unusual uses of __builtin_expect, for example, if it was being used in a
> > function argument and its type effected overload resolution.
>
> I think this is the abstractly right approach.  However, you're right
> that there are backwards-compatibility issues.  Another issue is that on
> platforms where "long" and "int" do not have the same width, something like:
>
>   sizeof(__builtin_expect(1, 1))
>
> will change its value.  And, the current prototype is documented in the
> manual.
>
> What do people think?  Do we have the leeway to change this?  Or should
> we add __builtin_expect2?  Or add an -fno-polymorphic-builtin-expect?
> Or...?

I think we should simply make __builtin_expect polymorphic, but make sure
to promote integral arguments with rank less than long to long.

Richard.

Re: __builtin_expect for indirect function calls

[Mark Mitchell]

Richard Guenther wrote:

>> What do people think?  Do we have the leeway to change this?  Or should
>> we add __builtin_expect2?  Or add an -fno-polymorphic-builtin-expect?
>> Or...?
> 
> I think we should simply make __builtin_expect polymorphic, but make sure
> to promote integral arguments with rank less than long to long.

I thought of that, but I hadn't suggested this idea because it seemed so
weird.  Promoting to int would not be odd, but promoting to long is
weird.  Anyhow, you're right; that's another option, and, despite
weirdness, plausible.  I can't think of a way in which it changes
current behavior, unless you call __builtin_expect with a long long, and
that's probably not going to do what you expect right now anyhow.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: __builtin_expect for indirect function calls

[Mark Mendell]

The frontends here would prefer to just implement __builtin_expect_call
(fp,foo), and leave __builtin_expect as it is now.  We don't see a need for
a polymorphic __builtin_expect, as we are worried about backwards
compatibility.

A question was raised:  Are side effects in the second parameter guaranteed
to be executed?  Is it valid for a compiler to ignore any side effects?

Mark Mendell

TOBEY Team Lead
IBM Toronto Laboratory, 8200 Warden Ave, Markham, Ontario, Canada, L6G 1C7
Tel:  905-413-3485    Tie:  313-3485    Internet:  mendell@ca.ibm.com


                                                                                                                     
  From:       Mark Mitchell <mark@codesourcery.com>                                                                  
                                                                                                                     
  To:         Richard Guenther <richard.guenther@gmail.com>                                                          
                                                                                                                     
  Cc:         trevor_smigiel@playstation.sony.com, Hans-Peter Nilsson <hp@bitrange.com>, gcc <gcc@gcc.gnu.org>,      
              Russell_Olsen@playstation.sony.com, Andrew_Pinski@playstation.sony.com, Mark Mendell/Toronto/IBM@IBMCA 
                                                                                                                     
  Date:       06/01/2008 02:42 PM                                                                                    
                                                                                                                     
  Subject:    Re: __builtin_expect for indirect function calls                                                       
                                                                                                                     





Richard Guenther wrote:

>> What do people think?  Do we have the leeway to change this?  Or should
>> we add __builtin_expect2?  Or add an -fno-polymorphic-builtin-expect?
>> Or...?
>
> I think we should simply make __builtin_expect polymorphic, but make sure
> to promote integral arguments with rank less than long to long.

I thought of that, but I hadn't suggested this idea because it seemed so
weird.  Promoting to int would not be odd, but promoting to long is
weird.  Anyhow, you're right; that's another option, and, despite
weirdness, plausible.  I can't think of a way in which it changes
current behavior, unless you call __builtin_expect with a long long, and
that's probably not going to do what you expect right now anyhow.

--
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

RE: __builtin_expect for indirect function calls

[Dave Korn]

On 07 January 2008 21:15, Mark Mendell wrote:

> A question was raised:  Are side effects in the second parameter guaranteed
> to be executed?  Is it valid for a compiler to ignore any side effects?

  That perked up my curiosity:

"  The value of C must be a compile-time constant.  "

  Can a compile-time constant have run-time side-effects?  I couldn't think up
an example off the top of my head...

    cheers,
      DaveK
-- 
Can't think of a witty .sigline today....

RE: __builtin_expect for indirect function calls

[Dave Korn]

On 08 January 2008 15:36, Dave Korn wrote:

> On 07 January 2008 21:15, Mark Mendell wrote:
> 
>> A question was raised:  Are side effects in the second parameter guaranteed
>> to be executed?  Is it valid for a compiler to ignore any side effects?
> 
>   That perked up my curiosity:
> 
> "  The value of C must be a compile-time constant.  "
> 
>   Can a compile-time constant have run-time side-effects?  I couldn't think
> up an example off the top of my head...


  Ah, I thought of one, nevermind, sorry for the noise...



    cheers,
      DaveK
-- 
Can't think of a witty .sigline today....

Re: __builtin_expect for indirect function calls

[trevor_smigiel]

> >
> > which returns the value of FP with the same type as FP, and tells the
> > compiler that PFP is the expected target of FP.  Trival examples:
> >
> >   typedef void (*fptr_t)(void);
> >
> >   extern void foo(void);
> >
> >   void
> >   call_fp (fptr_t fp)
> >   {
> >     /* Call the function pointed to by fp, but predict it as if it is
> >        calling foo() */
> >     __builtin_expect_call (fp, foo)();
> 
> __builtin_expect (fp, foo);  /* alt __builtin_expect (fp == foo, 1); */
> fp ();

> >   }
> >
> >   void
> >   call_fp_predicted (fptr_t fp, fptr_t predicted)
> >   {
> >     /* same as above but the function we are calling doesn't have to be
> >        known at compile time */
> >     __builtin_expect_call (fp, predicted)();
> 
> __builtin_expect (fp, predicted);
> fp();
> 
> I guess the information just isn't readily available in the
> preferred form when needed and *that* part could more or less
> simply be fixed?


The main reason I didn't like this is that in some other context 'fp'
could be any expression, potentially with side effects.  This would
require either special handling by the compiler, or the user would have
to be sure to write it such that the side effects only happen once.

Trevor