Re: Extended Optimization using Peephole strategy

Zoltan Somogyi wrote:
> The compiler for the pure logic programming language Mercury uses a
> technique that sounds similar to what you are describing. At certain
> points in the IR code, the code generator includes pseudoinstructions
> that give information such as which registers are live at that point.
> Some of the optimizations that transform the IR depend on this information.
> In fact, in my other window I am working on fixing a bug caused by these
> annotations not being kept up to date by another optimization.


The TIL/ML compiler (see PLDI'96) uses a similar methodology, but
instead of passing down psuedo-instructions, it annotates the
intermediate form with advanced type information. The type
information is used for various kinds of data representation
transformations and to accomodate certain kinds of control-flow
optimizations. For example, we were able to get branch prediction
right for loops that crawl over lists -- of course, other techniques
can do this, it's just that it was dirt easy with the type information
lying around.


Furthermore, the type information is used to support tag-free garbage
collection. So, the type information from the front-end is
effectively passed all the way through the compilation process to the
back-end and indeed, to the runtime.


As Zoltan suggests, maintaining this auxiliary information can be
quite difficult if you treat the annotations as "second-class". We
found that by building a type-checker for our intermediate form, we
were able to verify after each optimization/transformation that the
annotations were correct. Conversely, when a bug manifested itself,
we found that the typechecker was an excellent tool for isolating the
bug. In particular, it was often the case that the typechecker was
able to determine that there was a bug, and where it was introduced.


For more information on compiling with type information, I humbly
suggest taking a peek at my PhD dissertation, "Compiling with Types".


    http://www.cs.cornell.edu/Info/People/jgm/thesis_ps.zip


-Greg Morrisett
  jgm@cs.cornell.edu
--

Return to the comp.compilers page.
Search the comp.compilers archives again.