RAFTS beyond basic blocks; handling phi

From	"Alex McDonald" <blog@rivadpm.com>
Newsgroups	comp.lang.forth
Subject	RAFTS beyond basic blocks; handling phi
Date	2013-09-10 16:46 +0100
Organization	A noiseless patient Spider
Message-ID	<l0neru$oj5$1@dont-email.me> (permalink)

Show all headers | View raw

After struggling for some time with how to calculate which phi statements
were required on entry to a basic block, reading some of the esoteric
literature on the subject really didn't help since they discuss non-stack
based languages. Then it became blindingly obvious. 

The only traffic out of a basic block and into a subsequent basic block
is through the stack. Phi statements are only required when referring to
stack elements modified by prior basic blocks. 

For example where ( xxx ) represents stack on entry and exit;

: x 10 y @ if z ! else drop then ... ;

Block 1  ( -- )   10 y @          ( a b )
Block 2  ( a b )  z !             ( -- )
Block 3  ( a b )  drop            ( a )
Block 4 has either ( -- ) or ( a ) on entry. 

The first method is <d> pop inserted in block 2 to match the stacks, and
a phi in block 4:

Block 2  ( a b )  z ! <d> pop     ( d )
Block 4  ( a|d )  <e> phi <a> <d> ( e )

Alternatively, we could have inserted a push <a> in block 1's exit and
avoided the phi; block 4 on entry would be ( -- ).

The decision is which to choose.

Back to comp.lang.forth | Previous | Next — 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