Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #36318 > unrolled thread

Static Single Assignment form to Stack allocation

Back to article view | Back to comp.lang.forth

Contents

  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

Page 1 of 6  [1] 2 3 4 5 6  Next page →

#36318 — Static Single Assignment form to Stack allocation

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 looking for innovative algorithms for stack allocation working out of SSA. I am interested in any single or multi-stack allocation techniques using Forth style stack manipulations, Constant PICK, R> >R, etc. I would appreciate any references or ideas on this front.

--Alexey

[toc] | [next] | [standalone]

#36320

Aliaksei Chapyzhenka <alex.drom@gmail.com> writes:
> I am interested in any single or multi-stack allocation techniques
> using Forth style stack manipulations, Constant PICK, R> >R, etc. I
> would appreciate any references or ideas on this front.

Look at Philip Koopman's book "Stack Machines" (find online) and
also Tikhon Jelvis's papers about compiling for the GreenArrays chip.
There's also another paper or two that I'm not remembering now.

[toc] | [prev] | [next] | [standalone]

#36321

On Fri, 06 Feb 2015 00:00:08 -0500, Paul Rubin <no.email@nospam.invalid>  
wrote:
> Aliaksei Chapyzhenka <alex.drom@gmail.com> writes:

>> I am interested in any single or multi-stack allocation techniques
>> using Forth style stack manipulations, Constant PICK, R> >R, etc. I
>> would appreciate any references or ideas on this front.
>
> Look at Philip Koopman's book "Stack Machines" (find online) and
> also Tikhon Jelvis's papers about compiling for the GreenArrays chip.
...

> There's also another paper or two that I'm not remembering now.

Really?  You don't know who here would write such a paper?  Are you joking?

Everyone here could guess it's was probably by Anton Ertl, if anyone ...

Read the description for:

"A New Approach to Forth Native Code Generation" A.E. 1992
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.3854&rank=1

There are a number of other papers on Citeseer which cite his paper
for JIT Java compilation.  Search for "ertl" and "rafts".

CiteseerX
http://citeseerx.ist.psu.edu/index


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

#36339

"Rod Pemberton" <buzz@notnotnontnooatno.cmm> writes:
>> There's also another paper or two that I'm not remembering now.
> Really?  You don't know who here would write such a paper?  Are you joking?
> Everyone here could guess it's was probably by Anton Ertl, if anyone ...
> Read the description for:
> "A New Approach to Forth Native Code Generation" A.E. 1992

That wasn't the paper I was thinking of.  The paper that Anton wrote
with Martin Maierhofer might be the one.  The topic isn't compiling
Forth to conventional cpu's, but rather, compiling conventional
(non-stack-oriented) code to stack hardware architectures.

[toc] | [prev] | [next] | [standalone]

#36397

On Fri, 06 Feb 2015 12:07:24 -0800
Paul Rubin <no.email@nospam.invalid> wrote:

> "Rod Pemberton" <buzz@notnotnontnooatno.cmm> writes:
> > "A New Approach to Forth Native Code Generation" A.E. 1992
> 
> That wasn't the paper I was thinking of.  The paper that Anton wrote
> with Martin Maierhofer might be the one.  The topic isn't compiling
> Forth to conventional cpu's, but rather, compiling conventional
> (non-stack-oriented) code to stack hardware architectures.


Maybe this one?  It interested me enough to keep a copy. 

A Preliminary Exploration of
Optimized Stack Code
Generation

Philip Koopman, Jr.
1992 ROCHESTER FORTH CONFERENCE


Jan Coombs. 
-- 
email valid, else fix dots and hyphen
jan4clf2014@murrayhyphenmicroftdotcodotuk

[toc] | [prev] | [next] | [standalone]

#36398

Jan Coombs <Jan-54 <jenfhaomndgfwutc@murmic.plus.com>> writes:
> Maybe this one?  It interested me enough to keep a copy. 
> A Preliminary Exploration of Optimized Stack Code Generation
> Philip Koopman, Jr.

Yeah, that was probably it.  Easy to find online with web search.

http://www.sciencedirect.com/science/article/pii/S1571066111001538

May also be of interest.

[toc] | [prev] | [next] | [standalone]

#36404

On Sunday, February 8, 2015 at 2:55:38 PM UTC-8, Paul Rubin wrote:
> Jan Coombs <Jan-54 <jenfhaomndgfwutc@murmic.plus.com>> writes:
> > Maybe this one?  It interested me enough to keep a copy. 
> > A Preliminary Exploration of Optimized Stack Code Generation
> > Philip Koopman, Jr.
> 
> Yeah, that was probably it.  Easy to find online with web search.
> 
> http://www.sciencedirect.com/science/article/pii/S1571066111001538
> 
> May also be of interest.
Thank you. Looks interesting.

[toc] | [prev] | [next] | [standalone]

#36326

on 06/02/2015 04:01:37, Aliaksei Chapyzhenka wrote:
> 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.
> 
> --Alexey
> 

Are you trying to go from SSA to stack form?

[toc] | [prev] | [next] | [standalone]

#36328

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/

[toc] | [prev] | [next] | [standalone]

#36335

Thank you ALL for the responses,

To clarify my intent:
* I am trying to construct Stack machine code from SSA representation.
* I do want allocate local variables (and phi points) on the stack across the control flow.
* I try staing with core Forth vocabulary (DROP, SWAP, DUP, Constant_PICK, >R, R>, ...)

For more details welcome to my project page: https://github.com/drom/shift-forth

I am aware of most references above:

Philip Koopman:
 * Stack Computers (89) - great book
 * A Preliminary Exploration of Optimized Stack Code Generation (95) -- does provide basic algorithm for stack scheduling of numbered local variables that can be used for the basic block

Anton Ertl: A New Approach to Forth Native Code Generation (92) -- describes how SSA form can be produced from Forth program and then used for the Register Allocation.

Martin Maierhofer: Diplomarbeit (97), Martin Maierhofer & Anton Ertl: Local Stack Allocation (98) -- Mostly focused on Stack form to Stack form optimization via DAG form. I havn't found any SSA references.

Anton Ertl: Domination-Based Scoping and Static Single Assignment Languages (07) -- 
very interesting SSA related paper but with unrelated to Stack machine.

[toc] | [prev] | [next] | [standalone]

#36337

Aliaksei Chapyzhenka <alex.drom@gmail.com> writes:
> * I try staing with core Forth vocabulary (DROP, SWAP, DUP,
> Constant_PICK, >R, R>, ...)

Constant_PICK is certainly not part of the core Forth vocabulary.  Once
you have it, locals are basically free.  The difficulties come from
being able to access only the top one or two stack elements.

> I am aware of most references above: ...

I don't think Jelvis's compiler uses SSA, but it goes to some pretty
extreme optimization measures and the techniques may be relevant.
See: http://jelv.is/chlorophyll.pdf

[toc] | [prev] | [next] | [standalone]

#36340

On Friday, February 6, 2015 at 12:16:37 PM UTC-7, Aliaksei Chapyzhenka wrote:
> Anton Ertl: A New Approach to Forth Native Code Generation (92) -- describes how SSA form can be produced from Forth program and then used for the Register Allocation.

I'm pretty dubious of Anton Ertl knowing anything about how to allocate registers, because:
1.) Gforth was written in C and hence doesn't have direct access to the registers --- people program in C to avoid register-allocation issues.
2.) He is now talking up PAF in which he supposedly can "abstract away the register set size" --- so he is still avoiding registers-allocation issues.

Still though, the subject matter is something I'm very interested in, and so I would be willing to read the paper --- give him a chance to show his stuff --- where can I get it?

[toc] | [prev] | [next] | [standalone]

#36343

On Fri, 06 Feb 2015 19:44:10 -0500, <hughaguilar96@gmail.com> wrote:

> I'm pretty dubious of Anton Ertl knowing anything about how to allocate  
> registers, because:
...

> 1.) Gforth was written in C and hence doesn't have direct access to the
> registers --- people program in C to avoid register-allocation issues.

True, unless they use inlined assembly.

> 2.) He is now talking up PAF in which he supposedly can "abstract away
> the register set size" --- so he is still avoiding registers-allocation
> issues.

That could be done with SSA or register renaming of the register file.

http://en.wikipedia.org/wiki/Register_file
http://en.wikipedia.org/wiki/Register_renaming
http://en.wikipedia.org/wiki/Static_single_assignment_form

> Still though, the subject matter is something I'm very interested in,
> and so I would be willing to read the paper --- give him a chance to
> show his stuff --- where can I get it?

Links were posted by Anton and me to various papers of Anton's.
You don't have us filtered do you Hugh?  Your loss ...


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

#36344

On Fri, 06 Feb 2015 14:16:36 -0500, Aliaksei Chapyzhenka  
<alex.drom@gmail.com> wrote:

> To clarify my intent:
> * I do want allocate local variables (and phi points) on the stack  
> across the control flow.

Forth usually uses two stacks, one for data and another for control
flow.  The control flow stack is called the "return" stack.  C usually
uses one stack for both data and control flow.  So, control flow is
*not* interleaved on a single stack like for C.  It's on it's own stack.

> * I am trying to construct Stack machine code from SSA representation.

Does your SSA representation use stack locations like registers,
or more like a LIFO stack?  If it's for a typical language, it'll
be more like registers.

Forth uses the data stack like a LIFO stack.  C uses the data stack
like an addressable array of registers, but also pushes and pops
data items.  Forth uses the return stack for control flow and
temporary storage.  If you want to use the Forth stack like an
array of registers, you'll need PICK and the reverse operation,
which you may name something like ... "PLACE".

> * [I'm trying to stay] with core Forth vocabulary (DROP, SWAP, DUP,  
> Constant_PICK, >R, R>, ...)

For the most part in Forth, the control stack, accessed by >R and R> ,
acts like a single, temporary, storage register.  I.e., just by having
fetch @ and store ! on a temporary register, e.g., A@ and A! , you can
eliminate much of the need for the return stack, but not all use of
the return stack.  Any double operations, 2SWAP, etc, and loop operations
will need to use multiple items on the return stack.


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

#36362

on 07/02/2015 04:41:13, "Rod Pemberton" wrote:
> On Fri, 06 Feb 2015 14:16:36 -0500, Aliaksei Chapyzhenka
> <alex.drom@gmail.com> wrote:
> 
>> To clarify my intent:
>> * I do want allocate local variables (and phi points) on the stack
>> across the control flow.
> 
> Forth usually uses two stacks, one for data and another for control
> flow. The control flow stack is called the "return" stack. C usually
> uses one stack for both data and control flow. So, control flow is
> *not* interleaved on a single stack like for C. It's on it's own
> stack.

The Forth control flow stack and the return stack (or rstack, rack) are
not the same. The control flow stack exists only at compile time.

> 
>> * I am trying to construct Stack machine code from SSA representation.
> 
> Does your SSA representation use stack locations like registers,
> or more like a LIFO stack?  If it's for a typical language, it'll
> be more like registers.

SSA form is language neutral, and assumes an infinite memory space. It
says nothing about registers or stacks since it can't express those
concepts directly.

> 
> Forth uses the data stack like a LIFO stack.  C uses the data stack
> like an addressable array of registers, but also pushes and pops
> data items.  Forth uses the return stack for control flow and
> temporary storage.  If you want to use the Forth stack like an
> array of registers, you'll need PICK and the reverse operation,
> which you may name something like ... "PLACE".
> 
>> * [I'm trying to stay] with core Forth vocabulary (DROP, SWAP, DUP,
>> Constant_PICK, >R, R>, ...)
> 
> For the most part in Forth, the control stack, accessed by >R and R> ,
> acts like a single, temporary, storage register. I.e., just by having
> fetch @ and store ! on a temporary register, e.g., A@ and A! , you can
> eliminate much of the need for the return stack, but not all use of
> the return stack. Any double operations, 2SWAP, etc, and loop
> operations will need to use multiple items on the return stack.

Why would double operations use multiple items on the return stack?

> 
> 
> Rod Pemberton
> 

[toc] | [prev] | [next] | [standalone]

#36363

On Saturday, February 7, 2015 at 11:22:14 AM UTC-8, Alex McDonald wrote:
> on 07/02/2015 04:41:13, "Rod Pemberton" wrote:
> > On Fri, 06 Feb 2015 14:16:36 -0500, Aliaksei Chapyzhenka
> > <alex.drom@gmail.com> wrote:
> >> * [I'm trying to stay] with core Forth vocabulary (DROP, SWAP, DUP,
> >> Constant_PICK, >R, R>, ...)
> > 
> > For the most part in Forth, the control stack, accessed by >R and R> ,
> > acts like a single, temporary, storage register. I.e., just by having
> > fetch @ and store ! on a temporary register, e.g., A@ and A! , you can
> > eliminate much of the need for the return stack, but not all use of
> > the return stack. Any double operations, 2SWAP, etc, and loop
> > operations will need to use multiple items on the return stack.
> 
> Why would double operations use multiple items on the return stack?

Forth uses Return Stack as the universal storage. It is common to store return address or loop counter there, but also temporal shuffling data from parameter stack and back : 2SWAP ROT >R ROT R> ;
Compiler can use these >R R> operations to overcome luck of PICK operation in order to allocate multiple local variables. It costs more in general but possible to the arbitrary depth.
I am providing the compiler a set of heuristics that it can use on the target machine and the cost of every sequence (representing the code size, cycle count, or energy consumption). Including all return stack tricks. Compiler will map SSA form into the sequence of steps. It will also try minimizing the cost of such solution.

--Alexey

[toc] | [prev] | [next] | [standalone]

#36366

On 2/7/15 11:09 AM, Aliaksei Chapyzhenka wrote:
> On Saturday, February 7, 2015 at 11:22:14 AM UTC-8, Alex McDonald wrote:
>> on 07/02/2015 04:41:13, "Rod Pemberton" wrote:
>>> On Fri, 06 Feb 2015 14:16:36 -0500, Aliaksei Chapyzhenka
>>> <alex.drom@gmail.com> wrote:
>>>> * [I'm trying to stay] with core Forth vocabulary (DROP, SWAP, DUP,
>>>> Constant_PICK, >R, R>, ...)
>>>
>>> For the most part in Forth, the control stack, accessed by >R and R> ,
>>> acts like a single, temporary, storage register. I.e., just by having
>>> fetch @ and store ! on a temporary register, e.g., A@ and A! , you can
>>> eliminate much of the need for the return stack, but not all use of
>>> the return stack. Any double operations, 2SWAP, etc, and loop
>>> operations will need to use multiple items on the return stack.
>>
>> Why would double operations use multiple items on the return stack?
>
> Forth uses Return Stack as the universal storage.

"Universal" is surely an overstatement. The return stack has specific 
uses (including return addresses in *some* implementations and loop 
counters), and is occasionally convenient for temporary storage under 
tightly specified conditions.

> It is common to store return address or loop counter there, but also temporal shuffling data from parameter stack and back...

: 2SWAP ROT >R ROT R> ;

That is a singularly awkward and inefficient definition of 2SWAP.

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[toc] | [prev] | [next] | [standalone]

#36367

On Saturday, February 7, 2015 at 1:25:31 PM UTC-8, Elizabeth D. Rather wrote:
> On 2/7/15 11:09 AM, Aliaksei Chapyzhenka wrote:
> > It is common to store return address or loop counter there, but also temporal shuffling data from parameter stack and back...
> 
> : 2SWAP ROT >R ROT R> ;
> 
> That is a singularly awkward and inefficient definition of 2SWAP.
Yes, especially I we define : ROT >R SWAP R> SWAP ;

But what eles would you do on the stack machine without PICK with core set of Forth words: DROP DUP SWAP OVER >R R> R@ ?

[toc] | [prev] | [next] | [standalone]

#36369

on 07/02/2015 22:09:07, Aliaksei Chapyzhenka wrote:
> On Saturday, February 7, 2015 at 1:25:31 PM UTC-8, Elizabeth D. Rather
> > wrote:
>> On 2/7/15 11:09 AM, Aliaksei Chapyzhenka wrote:
>> > It is common to store return address or loop counter there, but also temporal shuffling data from 
parameter stack and back...
>>
>> : 2SWAP ROT >R ROT R> ;
>>
>> That is a singularly awkward and inefficient definition of 2SWAP.
> wrote: Yes, especially I we define : ROT >R SWAP R> SWAP ;
> 
> But what eles would you do on the stack machine without PICK with core
> set of Forth words: DROP DUP SWAP OVER >R R> R@ ?
> 

You only require DUP SWAP >R R> and DROP. OVER and R@ along with all
other stack juggling words can be constructed from them.

[toc] | [prev] | [next] | [standalone]

#36370

On Saturday, February 7, 2015 at 2:32:22 PM UTC-8, Alex McDonald wrote:
> on 07/02/2015 22:09:07, Aliaksei Chapyzhenka wrote:
> > On Saturday, February 7, 2015 at 1:25:31 PM UTC-8, Elizabeth D. Rather
> > > wrote:
> >> On 2/7/15 11:09 AM, Aliaksei Chapyzhenka wrote:
> >> > It is common to store return address or loop counter there, but also temporal shuffling data from 
> parameter stack and back...
> >>
> >> : 2SWAP ROT >R ROT R> ;
> >>
> >> That is a singularly awkward and inefficient definition of 2SWAP.
> > wrote: Yes, especially I we define : ROT >R SWAP R> SWAP ;
> > 
> > But what eles would you do on the stack machine without PICK with core
> > set of Forth words: DROP DUP SWAP OVER >R R> R@ ?
> > 
> 
> You only require DUP SWAP >R R> and DROP. OVER and R@ along with all
> other stack juggling words can be constructed from them.

: SWAP OVER >R >R DROP R> R> ;
: DUP >R R@ R> ;
: DROP DUP XOR XOR ;

[toc] | [prev] | [next] | [standalone]

Page 1 of 6  [1] 2 3 4 5 6  Next page →

Back to top | Article view | comp.lang.forth

csiph-web