Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #36328
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Newsgroups | comp.lang.forth |
| Subject | Re: Static Single Assignment form to Stack allocation |
| Date | 2015-02-06 13:22 +0000 |
| Organization | Institut fuer Computersprachen, Technische Universitaet Wien |
| Message-ID | <2015Feb6.142225@mips.complang.tuwien.ac.at> (permalink) |
| References | <82c4c3dc-7692-4d03-a447-9bdd54ff9387@googlegroups.com> |
Aliaksei Chapyzhenka <alex.drom@gmail.com> writes:
>Hi All,
>
>I am working on the JavaScript-based compiler for the stack (Forth) machine=
>. I use Single Static Assignment (SSA) form as the intermediate form and lo=
>oking for innovative algorithms for stack allocation working out of SSA. I =
>am interested in any single or multi-stack allocation techniques using Fort=
>h style stack manipulations, Constant PICK, R> >R, etc. I would appreciate =
>any references or ideas on this front.
The problem description is unclear. Assuming that you mean that the
source language is JavaScript and the target language is Forth, the
work by Martin Maierhofer is relevant: For straight-line code,
Koopman's relatively simple stack scheduling is close to optimal.
For code with control structures, one might want to allocate some
local variables on the stack across, e.g., a whole loop, but I don't
know of any work on that that targets Forth-like target languages. My
guess is that one could keep about two local variables on the stacks,
but one often wants more, so people who did such compilers introduced
additional mechanisms for doing that efficiently (such as the JavaVM's
iload instruction).
@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"
}
@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}
}
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2014: http://www.euroforth.org/ef14/
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Static Single Assignment form to Stack allocation Aliaksei Chapyzhenka <alex.drom@gmail.com> - 2015-02-05 20:01 -0800
Re: Static Single Assignment form to Stack allocation Paul Rubin <no.email@nospam.invalid> - 2015-02-05 21:00 -0800
Re: Static Single Assignment form to Stack allocation "Rod Pemberton" <buzz@notnotnontnooatno.cmm> - 2015-02-06 02:15 -0500
Re: Static Single Assignment form to Stack allocation Paul Rubin <no.email@nospam.invalid> - 2015-02-06 12:07 -0800
Re: Static Single Assignment form to Stack allocation Jan Coombs <Jan-54 <jenfhaomndgfwutc@murmic.plus.com>> - 2015-02-08 22:38 +0000
Re: Static Single Assignment form to Stack allocation Paul Rubin <no.email@nospam.invalid> - 2015-02-08 14:55 -0800
Re: Static Single Assignment form to Stack allocation Aliaksei Chapyzhenka <alex.drom@gmail.com> - 2015-02-08 19:59 -0800
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-06 13:15 +0000
Re: Static Single Assignment form to Stack allocation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-02-06 13:22 +0000
Re: Static Single Assignment form to Stack allocation Aliaksei Chapyzhenka <alex.drom@gmail.com> - 2015-02-06 11:16 -0800
Re: Static Single Assignment form to Stack allocation Paul Rubin <no.email@nospam.invalid> - 2015-02-06 12:05 -0800
Re: Static Single Assignment form to Stack allocation hughaguilar96@gmail.com - 2015-02-06 16:44 -0800
Re: Static Single Assignment form to Stack allocation "Rod Pemberton" <buzz@notnotnontnooatno.cmm> - 2015-02-06 23:41 -0500
Re: Static Single Assignment form to Stack allocation "Rod Pemberton" <buzz@notnotnontnooatno.cmm> - 2015-02-06 23:41 -0500
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-07 19:22 +0000
Re: Static Single Assignment form to Stack allocation Aliaksei Chapyzhenka <alex.drom@gmail.com> - 2015-02-07 13:09 -0800
Re: Static Single Assignment form to Stack allocation "Elizabeth D. Rather" <erather@forth.com> - 2015-02-07 11:25 -1000
Re: Static Single Assignment form to Stack allocation Aliaksei Chapyzhenka <alex.drom@gmail.com> - 2015-02-07 14:09 -0800
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-07 22:32 +0000
Re: Static Single Assignment form to Stack allocation Aliaksei Chapyzhenka <alex.drom@gmail.com> - 2015-02-07 14:51 -0800
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-08 00:04 +0000
Re: Static Single Assignment form to Stack allocation Aliaksei Chapyzhenka <alex.drom@gmail.com> - 2015-02-07 17:03 -0800
Re: Static Single Assignment form to Stack allocation "Rod Pemberton" <buzz@notnotnontnooatno.cmm> - 2015-02-07 21:04 -0500
Re: Static Single Assignment form to Stack allocation "Rod Pemberton" <buzz@notnotnontnooatno.cmm> - 2015-02-07 21:10 -0500
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-08 10:57 +0000
Re: Static Single Assignment form to Stack allocation "Rod Pemberton" <buzz@notnotnontnooatno.cmm> - 2015-02-07 21:05 -0500
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-07 22:24 +0000
Re: Static Single Assignment form to Stack allocation "Elizabeth D. Rather" <erather@forth.com> - 2015-02-07 11:21 -1000
Re: Static Single Assignment form to Stack allocation "Rod Pemberton" <buzz@notnotnontnooatno.cmm> - 2015-02-07 20:11 -0500
Re: Static Single Assignment form to Stack allocation "Elizabeth D. Rather" <erather@forth.com> - 2015-02-07 15:35 -1000
Re: Static Single Assignment form to Stack allocation "Elizabeth D. Rather" <erather@forth.com> - 2015-02-07 16:52 -1000
Re: Static Single Assignment form to Stack allocation hughaguilar96@gmail.com - 2015-02-08 10:21 -0800
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-08 20:09 +0000
Re: Static Single Assignment form to Stack allocation "Elizabeth D. Rather" <erather@forth.com> - 2015-02-08 17:15 -1000
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-09 12:00 +0000
Re: Static Single Assignment form to Stack allocation albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-02-09 13:05 +0000
Re: Static Single Assignment form to Stack allocation "HAA" <someone@microsoft.com> - 2015-02-10 16:01 +1100
Re: Static Single Assignment form to Stack allocation "Rod Pemberton" <buzz@notnotnontnooatno.cmm> - 2015-02-09 02:35 -0500
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-09 12:03 +0000
Re: Static Single Assignment form to Stack allocation hughaguilar96@gmail.com - 2015-02-08 10:13 -0800
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-08 20:21 +0000
Re: Static Single Assignment form to Stack allocation hughaguilar96@gmail.com - 2015-02-09 22:49 -0800
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-10 12:12 +0000
Re: Static Single Assignment form to Stack allocation albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-02-10 12:54 +0000
Re: Static Single Assignment form to Stack allocation Mark Wills <markwills1970@gmail.com> - 2015-02-10 06:30 -0800
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-10 14:53 +0000
Re: Static Single Assignment form to Stack allocation "Elizabeth D. Rather" <erather@forth.com> - 2015-02-10 08:20 -1000
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-10 14:33 +0000
Re: Static Single Assignment form to Stack allocation albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-02-10 19:09 +0000
Control-flow stack (was: Static Single Assignment ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-02-10 14:29 +0000
Re: Control-flow stack (was: Static Single Assignment ...) "Alex McDonald" <blog@rivadpm.com> - 2015-02-10 15:49 +0000
Re: Control-flow stack (was: Static Single Assignment ...) albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-02-10 17:56 +0000
Re: Control-flow stack (was: Static Single Assignment ...) "Alex McDonald" <blog@rivadpm.com> - 2015-02-10 20:53 +0000
Re: Control-flow stack "Elizabeth D. Rather" <erather@forth.com> - 2015-02-10 13:08 -1000
Re: Control-flow stack awegel@arcor.de (Alexander Wegel) - 2015-02-11 03:15 +0100
Re: Control-flow stack hughaguilar96@gmail.com - 2015-02-10 18:47 -0800
Re: Control-flow stack Unknown <dog@gmail.com> - 2015-02-17 07:13 +0000
Re: Control-flow stack anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-02-11 17:59 +0000
Re: Control-flow stack (was: Static Single Assignment ...) Raimond Dragomir <raimond.dragomir@gmail.com> - 2015-02-11 01:30 -0800
Re: Control-flow stack (was: Static Single Assignment ...) "Rod Pemberton" <buzz@notnotnontnooatno.cmm> - 2015-02-10 18:43 -0500
Re: Control-flow stack (was: Static Single Assignment ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-02-11 17:46 +0000
Re: Control-flow stack (was: Static Single Assignment ...) "Alex McDonald" <blog@rivadpm.com> - 2015-02-11 22:39 +0000
Re: Control-flow stack (was: Static Single Assignment ...) "Alex McDonald" <blog@rivadpm.com> - 2015-02-11 22:42 +0000
Re: Control-flow stack (was: Static Single Assignment ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-02-12 09:52 +0000
Re: Control-flow stack (was: Static Single Assignment ...) "Alex McDonald" <blog@rivadpm.com> - 2015-02-12 10:28 +0000
Re: Control-flow stack (was: Static Single Assignment ...) hughaguilar96@gmail.com - 2015-02-11 20:23 -0800
Re: Control-flow stack (was: Static Single Assignment ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-02-12 07:21 +0000
Re: Control-flow stack (was: Static Single Assignment ...) hughaguilar96@gmail.com - 2015-02-12 18:33 -0800
Re: Control-flow stack awegel@arcor.de (Alexander Wegel) - 2015-02-13 04:46 +0100
Re: Control-flow stack "Rod Pemberton" <buzz@notnotnontnooatno.cmm> - 2015-02-13 06:48 -0500
Re: Control-flow stack awegel@arcor.de (Alexander Wegel) - 2015-02-13 13:40 +0100
Re: Control-flow stack albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-02-13 15:49 +0000
Re: Control-flow stack awegel@arcor.de (Alexander Wegel) - 2015-02-14 03:47 +0100
Re: Control-flow stack anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-02-13 16:09 +0000
Re: Control-flow stack (was: Static Single Assignment ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-02-13 15:20 +0000
Re: Control-flow stack (was: Static Single Assignment ...) hughaguilar96@gmail.com - 2015-02-13 21:31 -0800
Re: Control-flow stack awegel@arcor.de (Alexander Wegel) - 2015-02-14 03:47 +0100
Re: Control-flow stack (was: Static Single Assignment ...) hughaguilar96@gmail.com - 2015-02-14 19:22 -0800
Re: Control-flow stack (was: Static Single Assignment ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-02-15 11:09 +0000
Re: Control-flow stack (was: Static Single Assignment ...) hughaguilar96@gmail.com - 2015-02-15 16:57 -0800
Re: Control-flow stack (was: Static Single Assignment ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-02-16 14:41 +0000
Re: Control-flow stack (was: Static Single Assignment ...) hughaguilar96@gmail.com - 2015-02-16 18:43 -0800
Re: Control-flow stack Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2015-02-10 22:04 +0000
Re: Control-flow stack Harold <hzrabbie@gmail.com> - 2015-02-10 16:58 -0800
Re: Control-flow stack Bernd Paysan <bernd.paysan@gmx.de> - 2015-02-11 02:51 +0100
Re: Control-flow stack albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-02-11 11:34 +0000
Re: Control-flow stack Harold <hzrabbie@gmail.com> - 2015-02-11 08:17 -0800
Re: Control-flow stack "Elizabeth D. Rather" <erather@forth.com> - 2015-02-10 16:37 -1000
Re: Control-flow stack hughaguilar96@gmail.com - 2015-02-10 18:57 -0800
Re: Static Single Assignment form to Stack allocation "Rod Pemberton" <buzz@notnotnontnooatno.cmm> - 2015-02-10 18:44 -0500
Re: Static Single Assignment form to Stack allocation "Elizabeth D. Rather" <erather@forth.com> - 2015-02-10 14:49 -1000
Re: Static Single Assignment form to Stack allocation hughaguilar96@gmail.com - 2015-02-10 18:16 -0800
Re: Static Single Assignment form to Stack allocation Mark Wills <markwills1970@gmail.com> - 2015-02-11 00:35 -0800
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-11 09:35 +0000
Re: Static Single Assignment form to Stack allocation Mark Wills <markwills1970@gmail.com> - 2015-02-11 03:06 -0800
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-11 14:27 +0000
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-11 14:40 +0000
Re: Static Single Assignment form to Stack allocation "Rod Pemberton" <buzz@notnotnontnooatno.cmm> - 2015-02-12 20:02 -0500
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-13 11:42 +0000
Re: Static Single Assignment form to Stack allocation "Rod Pemberton" <buzz@notnotnontnooatno.cmm> - 2015-02-13 07:44 -0500
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-13 14:20 +0000
Re: Static Single Assignment form to Stack allocation "Elizabeth D. Rather" <erather@forth.com> - 2015-02-13 10:32 -1000
Re: Static Single Assignment form to Stack allocation "Rod Pemberton" <bork@lllljunkqwer.cpm> - 2015-03-29 16:27 -0400
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-03-29 22:46 +0100
Re: Static Single Assignment form to Stack allocation "Elizabeth D. Rather" <erather@forth.com> - 2015-03-29 15:24 -1000
Re: Static Single Assignment form to Stack allocation hughaguilar96@gmail.com - 2015-03-30 04:44 -0700
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-03-30 15:33 +0100
Re: Static Single Assignment form to Stack allocation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-02-11 18:03 +0000
Re: Static Single Assignment form to Stack allocation Bernd Paysan <bernd.paysan@gmx.de> - 2015-02-12 00:16 +0100
Re: Static Single Assignment form to Stack allocation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-02-12 07:08 +0000
Re: Static Single Assignment form to Stack allocation "Alex McDonald" <blog@rivadpm.com> - 2015-02-08 10:51 +0000
csiph-web