a practical UNCOL

The work of Davidson and Fraser points the way to a practical UNCOL.
We have been using a register transfer langauge as an intermediate
language in an optimizing compiler for Smalltalk. Davidson and Fraser
designed a machine independent peephole optimizer that would translate
a machine language program into register transfers, optimize the
resulting program, and combine the transfers back into machine language.
They claimed that register transfers can be a useful UNCOL. Early
attempts at UNCOLs, they claimed, were essentially union languages
that tried to include all the features that any machine might have.
In contrast, register transfers contain only the intersection of
features that any machine might have. They claimed that their
combining algorithm would reconstruct more complicated instructions.


Our use of register transfers as an intermediate language has been
very successful. Our original system was quite similar to PO, which
Davidson wrote. The main difference was that we generated register
transfers directly. Also, we attempted more global optimizations
and better register assignment, though this was not significantly
better than what Davidson and Fraser did. Our version of the
combining algorithm was much faster than theirs because we could
use a lot of tricks in Smalltalk. However, we gradually changed
our code generator until it is now quite different from PO. In
particular, our intermediate data structure is similar to Static
Single Assignment (SSA), invented by folks at IBM. We think that
we now have a very elegant and reasonably efficient low-level
representation for programs that is easy to retarget to different
machines.


The code generator has only been targeted to two different machines,
so we don't yet have proof that it is really portable. One of the
machines is the 68020 and the other is a local horizontally microcoded
machine. However, our model stretches to fit both those machines,
which is a pretty good sign. I don't think we will have any trouble
with RISC machines.


In summary, I think that a very simple-minded register transfer language
is a good candidate for an UNCOL, using a combining algorithm similar
to that of Davidson and Fraser for converting UNCOL programs into machine
language for each kind of machine.


Ralph Johnson
[Isn't this the same model that GCC uses, fairly successfully? In any event,
I wonder how well it addresses machines like the 360 and to some extent the
PDP-10 where there are register asymmetries, e.g. the famous 360 BXLE
instruction which does "r1 += r2, if r1 <= r3 goto x", but r2 and r3 have to
be in an even-odd register pair. I know that IBM's PL.8 uses a similar
scheme to generate 370 code, but believe that it has a lot of hints to help
put things in the right registers. I know that such instructions are now
considered old-fashioned, but there are a lot of old-fashioned machines. -John]
certain registers in
[From Ralph Johnson <johnson@p.cs.uiuc.edu>]
--

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