Re: Native Code Generation from Abstract Stack Machine

"Peter Seibel" <peter@javamonkey.com> wrote
> I assume there are standard techniques for turning stack machine code
> into abstract register code. Are there any good references where I can
> read about them?


The IP Pascal compiler goes from stack machine to register code. The
first step is to turn the intermediate code into acyclic graph with
expression trees, then the trees are colored with registers. The stack
code to tree transisition is fairly trivial. I keep a stack with
leaves, and each operator consumes contents of the stack and places
new leaves there. The trees are constructed by poping the leaves from
the stack. Even instructions like "duplicate stack" and "exchange top
and next" can be handled by just manipulating the stack. The only
tricky part was that the intermediate had file operators that worked
by leaving the file on the stack and chaining operators, such as
write(f, a, b, c) becomes wrt f, a wrt f, b, etc. These were done by a
routine that duplicates the file reference as a full tree, which
sounds bad, but ends up being a fairly small routine.


IP Pascal's intermediate was designed to be general purpose, but be
able to handle any type of code generation. The intermediate is a
stack execute model heavily decorated with types. The first version
fed a VM just to prove the system out, using the stack architecture (a
stackitecture :) This was followed by a "check encoder" that generated
real machine code, but used the CPU stack in the same way as the VM
stack, and thus generated code that followed the stack architecture
form. The final encoder then performed a full graph based optimize and
code generate. I still use the VM as the core of a IDE/Simulator
system for enhanced diagnostics. I.e., the user need not know or care
that module X got piped to a VM.


To me the bottom line is, get the code in graph form, then you can
massage it any way you want. I keep the entire graph for the current
function/procedure in memory at once, and keep a select series of
short, older functions/procedures around for inlining. Yes, it sucks
up memory, but compilation no longer even qualifies as a heavy
application nowadays.


x Scott

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