Re: AST optimizer in C++?

[Dave Hudson <dave at cyclicode dot net>]

Hi Chris,

Chris Lattner wrote:
> On Sat, 24 Aug 2002, Dave Hudson wrote:
>
> One of our future research problems is to see how well the LLVM "level
> raising" pass can process machine code, which has very little inherent
> type information available at all: there you don't even get function
> prototypes (but you can get the number of arguments).  If you want me to
> explain a bit more about how and what the level raising does, just let me
> know.
This has my attention right now as I started writing some code to try 
and do exactly this a couple of weeks ago.  As much of the 
microcontroller world revolves around code written with either 
proprietary processor-specific compilers, often using strange languages 
or subsets of languages then working from raw binaries is probably about 
the only real option.

> Sorta.  Here you can eliminate global variables, but can you change their
> type, data layout, or other properties?  Can you delete fields of global
> structures that are never used?
It's this that is the biggest nuissance to me in fact.  One obvious 
place where such ideas can be made to win is with code that can be 
compiled for say a single-threaded or multithreaded system.  Being able 
to always compile for the multithreaded case knowing that the compiler 
would optimize away things like unecessary lock fields would be very useful.

> > > * constantmerge       - Merge global variable constants (basically
> > >                         .rodata) with identical contents together.
> > This I could do with :-)
> :)  This actually is more or less possible with a smart binary linker
> though, isn't it?
I've thought about doing this but haven't so far - lazy aren't I :-)  I 
could make some of the gains I'm interested in by simply improving ld 
and indeed even quite small wins can have a disproportionate effect at 
times by helping our linker relaxation when it's stripping unecessary 
instructions from calls and jumps, but I'd rather look at places where 
much bigger wins can be achieved.

> What kind of example are you interested in?  LICM is a pretty well studied
> problem, and is actually a subset of a technique referred to as Partial
> Redundancy Elimination.  GCC actually has optimizers that can do this,
> it's just that it doesn't have the alias analysis infrastructure to
> disambiguate loads/stores very well.  RTL based optimizers also have
> problems inherent with working on a machine specific representation, but
> that if pretty much common to the backend (and is why transformations are
> being moved to the tree-ssa representation).
The major problem I've encountered with this as it stands is that the 
RTL coming out of the global register allocation pass for the IP2022 is 
truly awful - it has to be extremely pessimistic so that reload doesn't 
fail (sad consequence of only having one useful pointer register other 
than the stack pointer - I said this wasn't an obvious target for gcc 
:-)).  With that said however I still see quite a few bad things 
happening with the IP4k port of gcc and that doesn't have any 
significant restrictions in terms of pointer usage.  I will have to go 
and read some more papers I guess.


Regards,
Dave