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

Groups > comp.lang.forth > #7763

Re: Help with RAFTS-like optimiser

Show all headers | View raw

Alex McDonald <blog@rivadpm.com> writes:
>X Y TUCK 1 +
>
>results in the forest Y X Y+1, and the result of the tree at leftmost
>Y needs to be available as a subtree of rightmost Y+1.
...
>The entry at (-1 $806450) is a subtree of (-3 $806448) for the IL at
>$144B28. In fact, anything that moves a stack entry "leftwards" --
>swap, tuck, rot and so on -- can generate these dependencies. What's
>the best way of managing these subtrees; marking with a reference
>count?

I am not sure what you mean with "managing" here.

Anyway, I guess one thing you are wondering about is how to generate
code if you allocate the stack items in a way that leads to cycles in
the dependence graph coming from write-after-read dependences.  That's
what Stephen Pelc calls the generic stack shuffle or somesuch.

I asked the question many years ago in comp.compilers, but cannot find
the thread now.  Anyway, the answer I got pointed to [burger+95] IIRC.
"Greedy shuffling" is the interesting part here: Build a dependence
graph; if there are no cycles, do a topological sort and process the
nodes in that order.  If there is a cycle, you have to break it by
introducing a move of one of the things in the cycle to a temporary
location; repeat until you have no more cycles, then do the
topological sort etc.

An alternative, simpler approach that might avoid the need for
complicated graph algorithms, but typically introduce more moves is to
introduce moves from all the input items to temporary locations (or
from temporary locations to the output items) right at the start, then
generate code, and try to put the temporary location in the
corresponding input (or output) location during register allocation
(this is called coalescing in register allocation literature) if
possible (it's not possible for all temporary locations if there are
cycles).

@InProceedings{burger+95,
  author = 	 {Robert G. Burger and Oscar Waddell and R. Kent Dybvig},
  title = 	 {Register Allocation Using Lazy Saves, Eager
                  Restores, and Greedy Shuffling},
  crossref =	 "sigplan95",
  pages =	 {130--138}
}

@Proceedings{sigplan95,
  booktitle = 	 "SIGPLAN '95 Conference on Programming Language
		  Design and Implementation",
  title = 	 "SIGPLAN '95 Conference on Programming Language
		  Design and Implementation",
  year = 	 "1995",
  key = 	 "SIGPLAN '95"
}

- 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 2011: http://www.euroforth.org/ef11/

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Help with RAFTS-like optimiser Alex McDonald <blog@rivadpm.com> - 2011-11-30 14:52 -0800
  Re: Help with RAFTS-like optimiser anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-02 16:36 +0000
    Re: Help with RAFTS-like optimiser Alex McDonald <blog@rivadpm.com> - 2011-12-02 12:43 -0800
      Re: Help with RAFTS-like optimiser Pablo Hugo Reda <pabloreda@gmail.com> - 2011-12-02 14:42 -0800
        Re: Help with RAFTS-like optimiser Alex McDonald <blog@rivadpm.com> - 2011-12-02 14:47 -0800
          Re: Help with RAFTS-like optimiser Pablo Hugo Reda <pabloreda@gmail.com> - 2011-12-02 15:02 -0800
      Re: Help with RAFTS-like optimiser Alex McDonald <blog@rivadpm.com> - 2011-12-04 18:00 -0800
      Re: Help with RAFTS-like optimiser anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-06 15:44 +0000
        Re: Help with RAFTS-like optimiser Alex McDonald <blog@rivadpm.com> - 2011-12-06 12:27 -0800
          Re: Help with RAFTS-like optimiser Alex McDonald <blog@rivadpm.com> - 2011-12-06 14:27 -0800
          Re: Help with RAFTS-like optimiser anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-07 13:15 +0000
      Re: Help with RAFTS-like optimiser (long-ish) Alex McDonald <blog@rivadpm.com> - 2012-01-09 05:50 -0800
        Re: Help with RAFTS-like optimiser (long-ish) Alex McDonald <blog@rivadpm.com> - 2012-01-09 06:09 -0800
        Re: Help with RAFTS-like optimiser (long-ish) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-01-09 15:07 +0000
          Re: Help with RAFTS-like optimiser (long-ish) Alex McDonald <blog@rivadpm.com> - 2012-01-09 13:17 -0800
            Re: Help with RAFTS-like optimiser (long-ish) Alex McDonald <blog@rivadpm.com> - 2012-01-10 08:53 -0800
          Re: Help with RAFTS-like optimiser (long-ish) Alex McDonald <blog@rivadpm.com> - 2012-01-16 07:14 -0800
    Re: Help with RAFTS-like optimiser George Hubert <georgeahubert@yahoo.co.uk> - 2011-12-04 02:37 -0800
      Re: Help with RAFTS-like optimiser Alex McDonald <blog@rivadpm.com> - 2011-12-04 11:13 -0800
      Re: Help with RAFTS-like optimiser anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-12-06 17:43 +0000
  Re: Help with RAFTS-like optimiser Alex McDonald <blog@rivadpm.com> - 2011-12-19 07:28 -0800
    Re: Help with RAFTS-like optimiser Alex McDonald <blog@rivadpm.com> - 2011-12-19 09:29 -0800

csiph-web