Re: AST optimizer in C++?

[Chris Lattner <sabre at nondot dot org>]

On Sat, 24 Aug 2002, Dave Hudson wrote:
> 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.

Binary translation is a hard problem, as I'm sure you know.  I'm don't
know if the strategy used by our level raising pass will help you at all,
but this is the basic idea.  Essentially, we have our RTL->LLVM
pass (built into GCC) do a very simple-minded translation.  All pointer
arithmetic has been lowered at this point (by GCC), and all pointers are
effectively void*'s.

LLVM is a typed representation, so this means that we have to insert cast
instructions to reflect the semantics of the underlying RTL.  For example,
in RTL there may be an HI mode load.  The LLVM produced would basically
looks like this:

  %newptr = cast ubyte* to ushort*
  %val    = load ushort*

Which captures the fact that the load is loading two bytes, not one or 4
or some other number.  From this we get our LLVM file, which is in SSA
form and has other nice properties.  We use these hints implicitly
embedded in the code (for example, a two byte load, a signed division, a
sign extending shift right) to build up constraints on the representation.

Level-raising then becomes a matter of trying to eliminate these cast
instructions.  We basically unify constraints wherever possible, trying to
identify fields of structures from memory accesses, sign properties of
values, and whether or not something is a pointer vs an integer.  When
conflicts in the constraints are detected, we fall back to inserting a
cast.  For example X = (sdiv (udiv A, B), C) requires a cast.

Unfortunately I don't have a really good solution for your binary
translation project: most of the hard stuff is interpreting the actual
machine instructions and figuring out side effects I imagine...

> > 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.

Definately.  One of the reasons I chose compilers as my field was because
I'm interested in making the programmer's job easier.  :)

> > What kind of example are you interested in?  LICM is a pretty well studied

> 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.

If this is the case, it may be that GCC isn't really the right compiler
for you to use.  It really is designed for architectures with "enough"
registers, and that fit a certain design model.  With only a single GPR,
you are probably better off using a custom register allocator, for
example...

-Chris

http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/