Feedback-driven optimization

Feedback-driven optimization

[Robert Myers]

Hello,

Compiler-naive but hard-to-deter hacker would like to explore 
feedback-driven optimization as in

http://gcc.gnu.org/news/profiledriven.html

only  more so.  In particular, VLIW optimizations have never come 
anywhere near to theoretical oracle performance, but I can't see that 
anybody has ever really tried all that hard.

Would like to fiddle around with Bayesian experience-based optimization 
strategies for IA-64.  Not trying to build a realistic optimization 
scheme.  Pure research: given lots of experience how close can you get 
to oracle performance without cheating.

gcc is the perfect base for this enterprise because I have access to the 
source and it comes in an IA-64 flavor.

One problem: my instincts tell me I should be working with RTL, not 
binary, but gcc doesn't permit routine dump of RTL.

Another problem:  I don't have an IA-64 and probably don't want one.  
What I really want is an emulator that can be completely instrumented.

Suggestions, advice, feedback.  Are you completely mad is okay, as long 
as you have some helpful advice to go along  with it.

RM

Re: Feedback-driven optimization

[Richard Henderson]

On Sun, Feb 23, 2003 at 02:04:38AM -0500, Robert Myers wrote:
> One problem: my instincts tell me I should be working with RTL, not 
> binary, but gcc doesn't permit routine dump of RTL.

Nope.  You'll have to make your modifications within gcc itself.

> Another problem:  I don't have an IA-64 and probably don't want one.  
> What I really want is an emulator that can be completely instrumented.

There isn't a free ia64 simulator.  To my knowledge, there isn't
even a closed source simulator that is generally available.


r~

Re: Feedback-driven optimization

[Jan Hubicka]

> On Sun, Feb 23, 2003 at 02:04:38AM -0500, Robert Myers wrote:
> > One problem: my instincts tell me I should be working with RTL, not 
> > binary, but gcc doesn't permit routine dump of RTL.
> 
> Nope.  You'll have to make your modifications within gcc itself.

Also there is already support for profile feedback in number of
optimizers.  I am not sure how much more can be done in IA-64 specific
way - probably ifcvt can be made to use it better (there are papers
about profile based hyperblock formation, perhaps it is worthwhile to
implement this) and scheduler - there is already code for trace
schedling but it is not done on IA-64 compilation path as it does
scheduling.  The modification would be trivial.  I would be greatly
interested in results of these.

Honza
> 
> > Another problem:  I don't have an IA-64 and probably don't want one.  
> > What I really want is an emulator that can be completely instrumented.
> 
> There isn't a free ia64 simulator.  To my knowledge, there isn't
> even a closed source simulator that is generally available.
> 
> 
> r~

Re: Feedback-driven optimization

[Robert Myers]

Jan Hubicka wrote:

>>On Sun, Feb 23, 2003 at 02:04:38AM -0500, Robert Myers wrote:
>>    
>>
>>>One problem: my instincts tell me I should be working with RTL, not 
>>>binary, but gcc doesn't permit routine dump of RTL.
>>>      
>>>
>>Nope.  You'll have to make your modifications within gcc itself.
>>    
>>
>
>Also there is already support for profile feedback in number of
>optimizers.  I am not sure how much more can be done in IA-64 specific
>way - probably ifcvt can be made to use it better (there are papers
>about profile based hyperblock formation, perhaps it is worthwhile to
>implement this) and scheduler - there is already code for trace
>schedling but it is not done on IA-64 compilation path as it does
>scheduling.  The modification would be trivial.  I would be greatly
>interested in results of these.
>
>  
>
Thanks for all of your comments.  Trimaran, as suggested by Robert 
Dewar, looks like the right place to start.

As much as I'd like to be able to contribute something useful to gcc, 
I'm a long way from being ready even to try to do that.

What I'd like to know, from anybody who is willing to venture a guess, 
is how much of the point will I miss by working in the idealized 
environment of Trimaran.

What I want to know is how much of the disappointing performance of VLIW 
is fundamental: the information just isn't there, and how much is 
pragmatic: the information might be there but no one can imagine putting 
the effort in that would be necessary to exploit it.

RM

Re: Feedback-driven optimization

[Jim Wilson]

Robert Myers wrote:
> Another problem:  I don't have an IA-64 and probably don't want one.  
> What I really want is an emulator that can be completely instrumented.

There is a free simulator available from HP in binary form but not 
source form.  There is also some other stuff available from HP, such as 
environments for booting linux on the simulator, and for running IA-64 
binaries on x86 machines via the simulator.  See
	http://www.software.hp.com/products/LIA64

 >Thanks for all of your comments.  Trimaran, as suggested by Robert 
 >Dewar, looks like the right place to start.

Trimaran is an academic project.  There is also ORC (Open Research 
Compiler) which is based on the open-sourced SGI compiler.  Both are 
interesting places to look for Itanium compiler optimization info.

A good source of general info for Itanium Linux issues is
	http://www.gelato.org
It has more info about the simulators and compilers that are available.

Jim

Re: Feedback-driven optimization

[Robert Dewar]

> 
> What I want to know is how much of the disappointing performance of VLIW 
> is fundamental: the information just isn't there, and how much is 
> pragmatic: the information might be there but no one can imagine putting 
> the effort in that would be necessary to exploit it.

Many people have studied this question in great detail, so the first step for
you is a major effort cracking the existing literature.

Re: Feedback-driven optimization

[Robert Myers]

Robert Dewar wrote:

>>What I want to know is how much of the disappointing performance of VLIW 
>>is fundamental: the information just isn't there, and how much is 
>>pragmatic: the information might be there but no one can imagine putting 
>>the effort in that would be necessary to exploit it.
>>    
>>
>
>Many people have studied this question in great detail, so the first step for
>you is a major effort cracking the existing literature.
>
>  
>
There's alot to read, and I've scanned a fair bit of it.  No one seems 
to have tried anything as ambitious as what I have in mind, which, is 
given all the preconceptions and experience available, come up with a 
best expected strategy.  There are fairly straightforward recipes for  
doing this, but I don't think anybody has actually tried them.  What 
people *have* done is to use profiling to identify areas for increased  
scrutiny, but with only limited success.

RM

Re: Feedback-driven optimization

[Robert Dewar]

> There's alot to read, and I've scanned a fair bit of it.  No one seems 
> to have tried anything as ambitious as what I have in mind, which, is 
> given all the preconceptions and experience available, come up with a 
> best expected strategy.  There are fairly straightforward recipes for  
> doing this, but I don't think anybody has actually tried them.  What 
> people *have* done is to use profiling to identify areas for increased  
> scrutiny, but with only limited success.

That's very far from true, and indicates that you should do a bit more "scanning".
Have you read for example the basic work on trace scheduling (and in particular
the Multiflow technology -- there was a reason that Intel paid millions of dollars
for access to this technology!)

Re: Feedback-driven optimization

[Jakob Engblom]

>> Another problem:  I don't have an IA-64 and probably don't want one.

>> What I really want is an emulator that can be completely
instrumented.

> There isn't a free ia64 simulator.  To my knowledge, there isn't
> even a closed source simulator that is generally available.

Yes, there is one IA64 simulator that is generally available (but
unfortunately not free or gratis), check out www.simics.net.  It can
boot an IA64 linux and run real applications, not just user-level code. 

/jakob