Re: Optimizing stack access for a stack based VM

Jiri Svoboda <jirik.svoboda@seznam.cz> writes:
>I'm working on a compiler of a Pascal-like language for a specific
>stack-based virtual machine. To produce small code, I would like to
>optimize the storage of variables and temporaries akin to register
>allocation on a register-based machine.
>
>Local variables should occur as natural operands of instructions (on
>the stack top) as much as possible, removing the need to fetch them
>from the middle of the stack (and encode displacement values).
>
>(More detailed description below.)
>
>Do you know if anyone already tried something like this, can you point me
>to any algorithms/articles/software?


Global stack allocation has the potential for significant savings by
reducing the number of instructions in addition to their size, but is
hard, and I know only one paper that attacked this[shannon&bailey06].
Note that even with optimal global stack allocation, the result will
only reduce non-stack accesses by a similar amount that a global
register allocator with very few global registers does.


There is also local stack allocation [maierhofer97,maierhofer&ertl98],
but it typically does not reduce the number of instructions, so the
only benefit you can expect is from converting larger instructions
(with a local index) to smaller ones (without a local index).


@InProceedings{shannon&bailey06,
    author = {Mark Shannon and Chris Bailey},
    title = {Register Allocation for Stack Machines},
    crossref = {euroforth06},
    pages = {13--20},
    url = {http://www.complang.tuwien.ac.at/anton/euroforth2006/papers/shannon.pdf},
    OPTnote = {refereed},
    abstract = {Register allocation is a critical part of any
                                    compiler, yet register allocation for stack machines
                                    has received little attention in the past. We
                                    present a framework for the analysis of register
                                    allocation methods for stack machines which has
                                    allowed us to analyse current methods. We have used
                                    this framework to design the first truly global
                                    register allocation methods. We have designed two
                                    such methods, both of which outperform current
                                    techniques.}
}
@Proceedings{euroforth06,
    title = {22nd EuroForth Conference},
    booktitle = {22nd EuroForth Conference},
    year = {2006},
    key = {EuroForth'06},
    url = {http://www.complang.tuwien.ac.at/anton/euroforth2006/papers/proceedings.pdf}
}


@MastersThesis{maierhofer97,
    author = {Martin Maierhofer},
    title = {Erzeugung optimierten Codes f\"{u}r Stackmaschinen},
    school = {{Technische Universit\"{a}t Wien}},
    type = {Diplomarbeit},
    year = {1997},
    address = {Austria},
    url = {http://www.complang.tuwien.ac.at/Diplomarbeiten/maierhofer97.ps.gz},
    abstract = {The success of the Java programming language and the
                                    underlying stack architecture (the JavaVM) recently
                                    have caused renewed interest in stack architectures.
                                    New and special techniques are required to provide
                                    support for the efficient execution of Algol-like
                                    high level languages on stack machines. An optimizing
                                    compiler should be able to eliminate dispensable
                                    accesses to main memory when loading and storing local
                                    variables by temporarily keeping a copy of their value
                                    on the stack. This technique, however, is only
                                    meaningful for machines that can handle
                                    stackmanipulations faster than accesses to main
                                    memory. \par This thesis presents two solutions for
                                    the problem and compares the results that can be
                                    achieved for two stack architectures (one of them is
                                    the JavaVM). Both techniques work on a ``local'' level,
                                    meaning that each basic block is considered separately.
                                    Phil Koopman's ``stack scheduling'' performs well in
                                    cooperation with a simple instruction scheduling
                                    strategy (a depth first postorder traversal of the
                                    dependency graph is used). The second technique
                                    (``{\scshape Dag} scheduling'') reorders the
                                    instructions (i.e. it schedules the instructions) in
                                    order to minimize accesses to local variables and
                                    leads to optimal code. \par The efficiency of Koopman's
                                    algorithm can be assessed with respect to the results
                                    achieved by {\scshape Dag} scheduling: stack scheduling
                                    leads to results that come quite near the optimum.
                                    Accesses to variables can be reduced from around 40\%
                                    (in code produced by the Java compiler \texttt{javac})
                                    to some 30\% (after optimization) of the total
                                    instructions in JavaVM code. Instructions for
                                    stackmanipulation, however, increase from about 5\% to
                                    up to 15\% of the total.},
    note = {In German}
}


@InProceedings{maierhofer&ertl98,
    author = "Martin Maierhofer and M. Anton Ertl",
    title = "Local Stack Allocation",
    crossref = "cc98",
    pages = "189--203",
    url = "http://www.complang.tuwien.ac.at/papers/maierhofer%26ertl98.ps.gz",
    abstract = "Considering the renewed interest in stack machines
(in particular, the Java Virtual Machine), efficient
execution of Algol-family languages on this class of
hardware becomes increasingly important. Local
variable accesses in the source language should be
translated into stack accesses on the target machine
(in analogy to register allocation on register
machines).\par In this paper we explore such stack
allocation techniques for basic blocks. We present
some improvements to Phil Koopman's \emph{stack
scheduling}, add an instruction scheduler and
compare the result with an optimal stack allocation
and instruction scheduling strategy. Stack
scheduling in cooperation with depth first postorder
instruction scheduling produces results close to the
optimum. The optimizations discussed in this paper
are profitable only for stack hardware where stack
manipulation operations are faster than local
variable accesses."
}


@Proceedings{cc98,
    title = "Compiler Construction (CC'98)",
    booktitle = "Compiler Construction (CC'98)",
    year = "1998",
    key = "CC'98",
    editor = "Kai Koskimies",
    OPTvolume = "1383",
    OPTseries = "LNCS",
    publisher = "Springer LNCS~1383",
    address = "Lisbon"
}


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

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