optimization hints?

optimization hints?

[Alfred Perlstein]

It has always seemed weird that C, the langue usually chosen because
it's closeness to the machine level wouldn't have a hint like 
system for doing branches.

Is there such a way to do this?

case in point:


  do {
    if ((ret = poll(pfds, num_pfds, INFTIM)) == -1)
        switch(ret = errno) {
        case EINTR:
             continue;
        default:
             panic("internal poll error %s", strerror(ret));
        }
    }
  ......
  } while (...);

just the fact that I don't expect an error (poll() returning -1),
I was hoping to be able to tell it that this code isn't likely to
execute and perhaps even move it someplace else to maximize the
instruction cache utilization of my code.

does this make sense?  is there anything in the works to do this, or
perhaps something I missed?

isn't it about time C developers had this kind of control over thier
code?

it'd be nice to have a "maybe((ret = poll(pfds, num_pfds, INFTIM)) == -1)"
or something :)

thanks,
-Alfred 

Re: optimization hints?

[Jeffrey A Law]

  In message < Pine.BSF.3.96.990611035502.14320R-100000@cygnus.rush.net >you writ
e:
  > 
  > It has always seemed weird that C, the langue usually chosen because
  > it's closeness to the machine level wouldn't have a hint like 
  > system for doing branches.
  > 
  > Is there such a way to do this?
Not a good way.  Cygnus did something for a customer called __builtin_expect,
but it has some serious problems, so we never contributed the code.

For your particular case, a reasonable static branch predictor would catch
it since most would predict a return value of -1 has highly unlikely since
it's an extremely common error code.

Instead of building a lot of crud for programmer directed info, we're better
off putting in a real static branch predictor as well as beefing up the
code to provide runtime branch prediction to the compiler.

Once we hae that, then you can look at optimizations based on that information
like basic block reordering.

jeff

Re: optimization hints?

[Jeffrey A Law]

  In message < Pine.BSF.3.96.990611035502.14320R-100000@cygnus.rush.net >you writ
e:
  > 
  > It has always seemed weird that C, the langue usually chosen because
  > it's closeness to the machine level wouldn't have a hint like 
  > system for doing branches.
  > 
  > Is there such a way to do this?
Not a good way.  Cygnus did something for a customer called __builtin_expect,
but it has some serious problems, so we never contributed the code.

For your particular case, a reasonable static branch predictor would catch
it since most would predict a return value of -1 has highly unlikely since
it's an extremely common error code.

Instead of building a lot of crud for programmer directed info, we're better
off putting in a real static branch predictor as well as beefing up the
code to provide runtime branch prediction to the compiler.

Once we hae that, then you can look at optimizations based on that information
like basic block reordering.

jeff

Re: optimization hints?

[Robert Lipe]

> It has always seemed weird that C, the langue usually chosen because
> it's closeness to the machine level wouldn't have a hint like 
> system for doing branches.
> [ munch ] 
> I was hoping to be able to tell it that this code isn't likely to
> execute and perhaps even move it someplace else to maximize the
> instruction cache utilization of my code.

It sounds like you're asking about runtime directed feedback
optimizations.

They can make a huge win on code by reducing paging, reducing cache
footprint, improving burst read/pipelining, improving branch prediction,
and so on.  It's really quite amazing to watch such an optimizer run
around your basic blocks, flipping the polarity of tests, gluing "hot
spots" together, and so on.

In SCO parlance, one such utility is 'fur', the FUnction Rearranger.

  http://uw7doc.sco.com/SDK_cdebug/_Using_fur_to_Perform_Block_Prof.html

Re: optimization hints?

[Joe Buck]

Robert Lipe writes:

> It sounds like you're asking about runtime directed feedback
> optimizations.
> 
> They can make a huge win on code by reducing paging, reducing cache
> footprint, improving burst read/pipelining, improving branch prediction,
> and so on.  It's really quite amazing to watch such an optimizer run
> around your basic blocks, flipping the polarity of tests, gluing "hot
> spots" together, and so on.
> 
> In SCO parlance, one such utility is 'fur', the FUnction Rearranger.

There is a project called GNU Rope, or "grope", for this purpose, by
Nat Friedman.  I have no idea about how good it is.

The web site for it seems to be down; all I can find on it is this
article:
http://lwn.net/1998/1029/als/rope.html

Re: optimization hints?

[Joe Buck]

Robert Lipe writes:

> It sounds like you're asking about runtime directed feedback
> optimizations.
> 
> They can make a huge win on code by reducing paging, reducing cache
> footprint, improving burst read/pipelining, improving branch prediction,
> and so on.  It's really quite amazing to watch such an optimizer run
> around your basic blocks, flipping the polarity of tests, gluing "hot
> spots" together, and so on.
> 
> In SCO parlance, one such utility is 'fur', the FUnction Rearranger.

There is a project called GNU Rope, or "grope", for this purpose, by
Nat Friedman.  I have no idea about how good it is.

The web site for it seems to be down; all I can find on it is this
article:
http://lwn.net/1998/1029/als/rope.html

Re: optimization hints?

[Benjamin Scherrey]

Is there source available for these tools? Preferably something that
would build under Linux? Anything equivalent out there?

	thanx & later,

		Ben Scherrey

Robert Lipe wrote:
> In SCO parlance, one such utility is 'fur', the FUnction Rearranger.
> 
>   http://uw7doc.sco.com/SDK_cdebug/_Using_fur_to_Perform_Block_Prof.html

Re: optimization hints?

[Robert Lipe]

Benjamin Scherrey wrote:
> Is there source available for these tools? Preferably something that
> would build under Linux? Anything equivalent out there?

Source for this one isn't widely available, but binaries are on the Free
UnixWare distribution.   See:
	http://www.sco.com/freeunix/

I've heard rumours that fur runs on Linux with the ibc2 modules and
works on Linux ELF binaries.  I can neither confirm nor deny that rumor
and the licensing issues make my head hurt. :-)

Earlier a URL was cited
	http://lwn.net/1998/1029/als/rope.html
the project that it refers to may be dead.

> Robert Lipe wrote:
> > In SCO parlance, one such utility is 'fur', the FUnction Rearranger.
> > 
> >   http://uw7doc.sco.com/SDK_cdebug/_Using_fur_to_Perform_Block_Prof.html

Re: optimization hints?

[Robert Lipe]

Benjamin Scherrey wrote:
> Is there source available for these tools? Preferably something that
> would build under Linux? Anything equivalent out there?

Source for this one isn't widely available, but binaries are on the Free
UnixWare distribution.   See:
	http://www.sco.com/freeunix/

I've heard rumours that fur runs on Linux with the ibc2 modules and
works on Linux ELF binaries.  I can neither confirm nor deny that rumor
and the licensing issues make my head hurt. :-)

Earlier a URL was cited
	http://lwn.net/1998/1029/als/rope.html
the project that it refers to may be dead.

> Robert Lipe wrote:
> > In SCO parlance, one such utility is 'fur', the FUnction Rearranger.
> > 
> >   http://uw7doc.sco.com/SDK_cdebug/_Using_fur_to_Perform_Block_Prof.html

Re: optimization hints?

[Benjamin Scherrey]

Is there source available for these tools? Preferably something that
would build under Linux? Anything equivalent out there?

	thanx & later,

		Ben Scherrey

Robert Lipe wrote:
> In SCO parlance, one such utility is 'fur', the FUnction Rearranger.
> 
>   http://uw7doc.sco.com/SDK_cdebug/_Using_fur_to_Perform_Block_Prof.html

Re: optimization hints?

[Robert Lipe]

> It has always seemed weird that C, the langue usually chosen because
> it's closeness to the machine level wouldn't have a hint like 
> system for doing branches.
> [ munch ] 
> I was hoping to be able to tell it that this code isn't likely to
> execute and perhaps even move it someplace else to maximize the
> instruction cache utilization of my code.

It sounds like you're asking about runtime directed feedback
optimizations.

They can make a huge win on code by reducing paging, reducing cache
footprint, improving burst read/pipelining, improving branch prediction,
and so on.  It's really quite amazing to watch such an optimizer run
around your basic blocks, flipping the polarity of tests, gluing "hot
spots" together, and so on.

In SCO parlance, one such utility is 'fur', the FUnction Rearranger.

  http://uw7doc.sco.com/SDK_cdebug/_Using_fur_to_Perform_Block_Prof.html

optimization hints?

[Alfred Perlstein]

It has always seemed weird that C, the langue usually chosen because
it's closeness to the machine level wouldn't have a hint like 
system for doing branches.

Is there such a way to do this?

case in point:


  do {
    if ((ret = poll(pfds, num_pfds, INFTIM)) == -1)
        switch(ret = errno) {
        case EINTR:
             continue;
        default:
             panic("internal poll error %s", strerror(ret));
        }
    }
  ......
  } while (...);

just the fact that I don't expect an error (poll() returning -1),
I was hoping to be able to tell it that this code isn't likely to
execute and perhaps even move it someplace else to maximize the
instruction cache utilization of my code.

does this make sense?  is there anything in the works to do this, or
perhaps something I missed?

isn't it about time C developers had this kind of control over thier
code?

it'd be nice to have a "maybe((ret = poll(pfds, num_pfds, INFTIM)) == -1)"
or something :)

thanks,
-Alfred 

Re: optimization hints?

[Mike Stump]

> Date: Fri, 11 Jun 1999 04:06:15 -0500 (EST)
> From: Alfred Perlstein <bright@rush.net>

> It has always seemed weird that C, the langue usually chosen because
> it's closeness to the machine level wouldn't have a hint like system
> for doing branches.

>     if ((ret = poll(pfds, num_pfds, INFTIM)) == -1)

> isn't it about time C developers had this kind of control over thier
> code?

Yes and no.  gcc is better off if in this one case, gcc developers can
tag `known' functions with expected results (or unexpected results as
the case may be), and let the optimizer use this to rearrange code.

For example, the simple rule that compares to -1 are usually false,
even as a general optimization rule, would go a long way to doing the
right thing in most C code I have seen.

The results one gets from that one general rule I feel would be better
than littering C code with attributes, pragma and the like.

Also note that you can get most of the benefit by using
-fbranch-probabilities, from the doc:

@item -fbranch-probabilities
After running a program compiled with @samp{-fprofile-arcs}
(@pxref{Debugging Options,, Options for Debugging Your Program or
@code{gcc}}), you can compile it a second time using
@samp{-fbranch-probabilities}, to improve optimizations based on
guessing the path a branch might take.

if your port doesn't yet support this, maybe you want to contribute
support for this?

Re: optimization hints?

[Alfred Perlstein]

On Fri, 11 Jun 1999, Mike Stump wrote:

> > Date: Fri, 11 Jun 1999 04:06:15 -0500 (EST)
> > From: Alfred Perlstein <bright@rush.net>
> 
> > It has always seemed weird that C, the langue usually chosen because
> > it's closeness to the machine level wouldn't have a hint like system
> > for doing branches.
> 
> >     if ((ret = poll(pfds, num_pfds, INFTIM)) == -1)
> 
> > isn't it about time C developers had this kind of control over thier
> > code?
> 
> Yes and no.  gcc is better off if in this one case, gcc developers can
> tag `known' functions with expected results (or unexpected results as
> the case may be), and let the optimizer use this to rearrange code.
> 
> For example, the simple rule that compares to -1 are usually false,
> even as a general optimization rule, would go a long way to doing the
> right thing in most C code I have seen.
> 
> The results one gets from that one general rule I feel would be better
> than littering C code with attributes, pragma and the like.
> 
> Also note that you can get most of the benefit by using
> -fbranch-probabilities, from the doc:
> 
> @item -fbranch-probabilities
> After running a program compiled with @samp{-fprofile-arcs}
> (@pxref{Debugging Options,, Options for Debugging Your Program or
> @code{gcc}}), you can compile it a second time using
> @samp{-fbranch-probabilities}, to improve optimizations based on
> guessing the path a branch might take.

doh, I didn't realize that was available.

> if your port doesn't yet support this, maybe you want to contribute
> support for this?

I'm using i386-freebsd, it probably does, if not i'm pretty certain
I don't have the time or understanding of gcc to do this right now.

thanks for the advice.
-Alfred 

Re: optimization hints?

[Alfred Perlstein]

On Fri, 11 Jun 1999, Mike Stump wrote:

> > Date: Fri, 11 Jun 1999 04:06:15 -0500 (EST)
> > From: Alfred Perlstein <bright@rush.net>
> 
> > It has always seemed weird that C, the langue usually chosen because
> > it's closeness to the machine level wouldn't have a hint like system
> > for doing branches.
> 
> >     if ((ret = poll(pfds, num_pfds, INFTIM)) == -1)
> 
> > isn't it about time C developers had this kind of control over thier
> > code?
> 
> Yes and no.  gcc is better off if in this one case, gcc developers can
> tag `known' functions with expected results (or unexpected results as
> the case may be), and let the optimizer use this to rearrange code.
> 
> For example, the simple rule that compares to -1 are usually false,
> even as a general optimization rule, would go a long way to doing the
> right thing in most C code I have seen.
> 
> The results one gets from that one general rule I feel would be better
> than littering C code with attributes, pragma and the like.
> 
> Also note that you can get most of the benefit by using
> -fbranch-probabilities, from the doc:
> 
> @item -fbranch-probabilities
> After running a program compiled with @samp{-fprofile-arcs}
> (@pxref{Debugging Options,, Options for Debugging Your Program or
> @code{gcc}}), you can compile it a second time using
> @samp{-fbranch-probabilities}, to improve optimizations based on
> guessing the path a branch might take.

doh, I didn't realize that was available.

> if your port doesn't yet support this, maybe you want to contribute
> support for this?

I'm using i386-freebsd, it probably does, if not i'm pretty certain
I don't have the time or understanding of gcc to do this right now.

thanks for the advice.
-Alfred 

Re: optimization hints?

[Mike Stump]

> Date: Fri, 11 Jun 1999 04:06:15 -0500 (EST)
> From: Alfred Perlstein <bright@rush.net>

> It has always seemed weird that C, the langue usually chosen because
> it's closeness to the machine level wouldn't have a hint like system
> for doing branches.

>     if ((ret = poll(pfds, num_pfds, INFTIM)) == -1)

> isn't it about time C developers had this kind of control over thier
> code?

Yes and no.  gcc is better off if in this one case, gcc developers can
tag `known' functions with expected results (or unexpected results as
the case may be), and let the optimizer use this to rearrange code.

For example, the simple rule that compares to -1 are usually false,
even as a general optimization rule, would go a long way to doing the
right thing in most C code I have seen.

The results one gets from that one general rule I feel would be better
than littering C code with attributes, pragma and the like.

Also note that you can get most of the benefit by using
-fbranch-probabilities, from the doc:

@item -fbranch-probabilities
After running a program compiled with @samp{-fprofile-arcs}
(@pxref{Debugging Options,, Options for Debugging Your Program or
@code{gcc}}), you can compile it a second time using
@samp{-fbranch-probabilities}, to improve optimizations based on
guessing the path a branch might take.

if your port doesn't yet support this, maybe you want to contribute
support for this?

Re: optimization hints?

[Alex Rosenberg]

> just the fact that I don't expect an error (poll() returning -1),
> I was hoping to be able to tell it that this code isn't likely to
> execute and perhaps even move it someplace else to maximize the
> instruction cache utilization of my code.

Apple's MrC compiler has two pragmas for this:

#pragma seldom

This moves the marked block to the end of the function (after the exit
node).

#pragma outofline

This puts the marked block in a seperate GL function in the XCOFF, which
results in placement at the end of the file by the linker.

Both would be straight-forward to implement in egcs, but pragmas have been
shunned in the past. No keyword alternative approach comes to mind.

A particularly useful variant would be to automatically move C++ catch
blocks.

+------------------------------------------------------------+
| Alexander M. Rosenberg           < mailto:alexr@_spies.com > |
| Nobody cares what I say. Remove the underscore to mail me. |

Re: optimization hints?

[Alex Rosenberg]

> just the fact that I don't expect an error (poll() returning -1),
> I was hoping to be able to tell it that this code isn't likely to
> execute and perhaps even move it someplace else to maximize the
> instruction cache utilization of my code.

Apple's MrC compiler has two pragmas for this:

#pragma seldom

This moves the marked block to the end of the function (after the exit
node).

#pragma outofline

This puts the marked block in a seperate GL function in the XCOFF, which
results in placement at the end of the file by the linker.

Both would be straight-forward to implement in egcs, but pragmas have been
shunned in the past. No keyword alternative approach comes to mind.

A particularly useful variant would be to automatically move C++ catch
blocks.

+------------------------------------------------------------+
| Alexander M. Rosenberg           < mailto:alexr@_spies.com > |
| Nobody cares what I say. Remove the underscore to mail me. |

Re: optimization hints?

[Mike Stump]

> Date: Fri, 11 Jun 1999 16:49:48 -0700
> From: "Alex Rosenberg" <alexr@spies.com>
> To: egcs@egcs.cygnus.com

> A particularly useful variant would be to automatically move C++ catch
> blocks.

They are already move to the end of the function (as I recall).  If
the infrastructure was in the compiler to move them farther, I would
have used it.  I thought about it, but didn't take the hit to add the
infrastructure.

Generally speaking, I think this type of thing is good.  Also,
coverage feedback to reorder hot spots for the cache would be nice,
seems we may already have most of the code to do that already.

Re: optimization hints?

[Mike Stump]

> Date: Fri, 11 Jun 1999 16:49:48 -0700
> From: "Alex Rosenberg" <alexr@spies.com>
> To: egcs@egcs.cygnus.com

> A particularly useful variant would be to automatically move C++ catch
> blocks.

They are already move to the end of the function (as I recall).  If
the infrastructure was in the compiler to move them farther, I would
have used it.  I thought about it, but didn't take the hit to add the
infrastructure.

Generally speaking, I think this type of thing is good.  Also,
coverage feedback to reorder hot spots for the cache would be nice,
seems we may already have most of the code to do that already.