Re: Native Code Generation from Abstract Stack Machine

Kevin Albrecht wrote:
> I am looking for research or implementations on how to generate
> efficient machine code from abstract stack machines. It seems like
> most resources on machine code generation from intermediate languages
> focuses on translation from register-based intermediate languages.
>
> -- Kevin
> [I suspect the advice is turn it into abstract register code, then
> optimize. Optimizing stack code is a pain because of all of the
> bookkeeping you have to do for common subexpressions. -John]




One technique is described in


          Ali-Reza Adl-Tabatabai, Michael Cierniak, Guei-Yuan Lueh,
          Vishesh M. Parikh, James M. Stichnoth,
          "Fast, Effective Code Generation in a Just-In-Time Java Compiler",
          In Proceedings of the SIGPLAN `98 Conference on Programming Language
          Design and Implementation, p. 280-290.
          Published as SIGPLAN Notices 33(5), May 1998.


The idea is to make a single pass over the abstract stack code for a
single function, deferring code generation until encountering an
operator. When the abstract stack code references an operand, a
descriptor of the operand is pushed on an operand stack that mimics
the abstract stack during the compile pass. When an operator is
encountered code is generated by examining the relevant stacked
operand descriptors, and those operands are then replaced by a
descriptor describing the result.


One can generate acceptable register-based code this way. For
example, a typical operator might be implemented as a function call
and the result descriptor might reference a specific register holding
the result.


This is actually not a new technique. Peter Deutsch used it in the
ParcPlace Smalltalk virtual machines, inventing it in about 1986/87,
but he didn't publish because he considered it worth keeping secret.
We still use the same framework in the current VisualWorks Smalltalk
VMs.


Independently, and without knowledge of Peter Deutsch's scheme, Ian
Piumarta did a native code compiler for Smalltalk that he wrote up in
his thesis at Manchester University, which is called something like
"Deferred Code generation in a Smalltalk-80 Compiler". Its a very
similar idea.
--
_______________,,,^..^,,,____________________________
Eliot Miranda Smalltalk - Scene not herd

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