Re: Compiling C for stack engines

Philip Koopman, Jr. (koopman+@cs.cmu.edu) in 92-05-152
writes about Compiling C for stack engines in a forthcoming paper:


>A Preliminary Exploration of Optimized Stack Code Generation


>ABSTRACT


>This paper presents an experimental code generator that performs
>intra-block stack scheduling for a stack-based execution model. For small
>test programs, 91% to 100% of redundant local variable accesses were
>eliminated using this compiler. Compiled intra-block stack scheduling and
>hand-performed global stack scheduling show that significant opportunities
>exist to keep temporary variable values on the expression evaluation stack
>when compiling conventional languages.


I have just obtained the paper, and it looks like this research indicates
that intra-block and global stack scheduling may overcome restrictions
regarding lost opportunities for exploiting data locality based
optimizations wrt stack based models, in particular to runtime execution
stack models. In order to retain the opportunity, the data must be kept
on the stack, as indicated in the above abstract - and is well documented
in the paper!


A related area for which the identical criticisms exist is relative to
stack based ILs. The criticism which has driven this new research is
therefore not specific to runtime stack execution models, but to the
interpretation of stack based ILs as well.


The following reference is paraphrased, with apologies to the authors:
[Ref: Interpretation and Instruction Path Coprocessing by Debaere and Van
Campenhout, MIT Press, 1990, ISBN 0-262-04107-3, p100]


Begin Ref Paraphrase:


Stack based architectures act to inhibit a compiler from generating code
which exploits data locality. Effectively, when a piece of data is popped
from the stack, one loses the opportunity to exploit data locality based
optimizations, i.e. the data is no longer able to be referenced. On a
register architecture, the compiler can track the validity of register
contents after the data is used, and then reuse the contents of the
register later without reloading (the data) from memory.


end Ref Paraphrase.


I wonder whether the new findings in the paper can be applied to stack
based ILs in order to speed up an interpreter implementation of a
language? Even though most IL-to-IL transformations are accomplished in
terms of pattern matching onto tree transformations, I see no reason not
to explore stack based ILs to see if these new results in the area of
runtime stack models can some- how be applied to the IL level stack. If
successful, speedier interpretation might result - i.e. the interpretation
of the modified stack based IL is faster than without modification.


The above reference also includes discussions about Forth.


Thomas Watt
Open Software Foundation
11 Cambridge Center
Cambridge, MA 02142
Phone: (617) 621-8711
Internet: watt@osf.org


--

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