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

Groups > comp.lang.forth > #25623

Re: RAFTS beyond basic blocks; handling phi

Show all headers | View raw

on 11/09/2013 12:07:20, "Alex McDonald" wrote:
> on 11/09/2013 11:50:47, Andrew Haley wrote:
>> Alex McDonald <blog@rivadpm.com> wrote:
>>>
>>> One of the things I'm finding about stack based languages to SSA based
>>> intermediate code is that a lot of the literature on compiler
>>> construction just doesn't apply. The obvious one for Forth is parsing,
>>> where classical texts devote much of their bulk to building abstract
>>> syntax trees, but there are others that don't apply such as analysis for
>>> dead code elimination. With a stack based approach, < 1 2 3 + + drop >
>>> eliminates itself automatically. The same is true of phi placement;
>>> conceptually, it's hugely simplified and doesn't appear to require the
>>> complex algorithms I've been studying.
>>
>> Don't forget about locals: many Forth seem to regard them as
>> second-class citizens, but you don't have to,
>>
>> Andrew.
> 
> They turn out to be trivial. All that's required on declaration is an
> SSA entry for a fetch from the stack into a virtual register, and a
> dictionary entry for the name that returns the SSA entry when the
> local is referenced. The only complication is generating possible phi
> entries when reaching back into previous blocks for the SSA entry.
> 
>: x { a } a if 10 to a else 20 to a then ;
> 
> { a } generates the name and the fetch. The first reference to a is in
> the same entry block, but the second and third are in two dependent
> blocks (both dominated by block first).
> 
> The same phi mechanism used for managing block entries suffices.
> Locals just melt away; they're just labelled SSA rather than anonymous
> entries.
> 

To add:

If each block maintains a list of locals names, then searching for a
label becomes an exercise in looking in this block's list for the name
and any dominating blocks if not found. So

: x { a } a if { a b } a else b then ... ;

SSA entries maintain their defining block number. Since the SSA entries
will be different for "a" at different compilation points, we can be
assured we have the right SSA, since we search only in this block or
dominating blocks.

(We can also guarantee that a block is dominated by at most two other
blocks during the construction of the SSA, although one of them might be
on a path to itself; AGAIN (a backward loop) and LOOP will do that.
Searching requires a tree walk and marking visits.) 

The "a" in the if clause is a different "a" from the first declaration.
The "b" after the else is an error since the declaration block for "b"
doesn't dominate the else block; it won't be found.  

This permits multiple declarations of locals at the block level as
supported in Gforth.

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

Thread

RAFTS beyond basic blocks; handling phi "Alex McDonald" <blog@rivadpm.com> - 2013-09-10 16:46 +0100
  Re: RAFTS beyond basic blocks; handling phi awegel@arcor.de (Alex Wegel) - 2013-09-10 23:30 +0200
    Re: RAFTS beyond basic blocks; handling phi "Alex McDonald" <blog@rivadpm.com> - 2013-09-11 11:35 +0100
      Re: RAFTS beyond basic blocks; handling phi Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-11 05:50 -0500
        Re: RAFTS beyond basic blocks; handling phi "Alex McDonald" <blog@rivadpm.com> - 2013-09-11 12:07 +0100
          Re: RAFTS beyond basic blocks; handling phi "Alex McDonald" <blog@rivadpm.com> - 2013-09-11 12:50 +0100
            Re: RAFTS beyond basic blocks; handling phi anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-11 14:27 +0000
  Re: RAFTS beyond basic blocks; handling phi anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-11 10:55 +0000
    Re: RAFTS beyond basic blocks; handling phi "Alex McDonald" <blog@rivadpm.com> - 2013-09-11 13:10 +0100
      Re: RAFTS beyond basic blocks; handling phi Bernd Paysan <bernd.paysan@gmx.de> - 2013-09-11 20:33 +0200
        Re: RAFTS beyond basic blocks; handling phi "Alex McDonald" <blog@rivadpm.com> - 2013-09-11 19:53 +0100
          Re: RAFTS beyond basic blocks; handling phi Bernd Paysan <bernd.paysan@gmx.de> - 2013-09-11 21:57 +0200
            Re: RAFTS beyond basic blocks; handling phi anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-13 13:14 +0000
        Re: RAFTS beyond basic blocks; handling phi albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-09-12 10:39 +0000
      Re: RAFTS beyond basic blocks; handling phi "Alex McDonald" <blog@rivadpm.com> - 2013-09-12 23:53 +0100
        Re: RAFTS beyond basic blocks; handling phi "Alex McDonald" <blog@rivadpm.com> - 2013-09-12 23:55 +0100
          Re: RAFTS beyond basic blocks; handling phi "Alex McDonald" <blog@rivadpm.com> - 2013-09-13 10:16 +0100
        Re: RAFTS beyond basic blocks; handling phi anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-13 13:19 +0000
          Re: RAFTS beyond basic blocks; handling phi "Alex McDonald" <blog@rivadpm.com> - 2013-09-15 20:34 +0100
      Re: RAFTS beyond basic blocks; handling phi anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-13 11:38 +0000

csiph-web