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

Groups > comp.lang.forth > #25622

Re: RAFTS beyond basic blocks; handling phi

Show all headers | View raw

"Alex McDonald" <blog@rivadpm.com> writes:
>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.

I think that, unless you want to do something SSA-specific, you don't
need to think much about phi statements.  Better think of what comes
out of phi removal, i.e., in general a register-register move at the
end of each joining basic block for each affected stack item.  And
then you can think of whether and how some of these moves can be
removed.

>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. 

Yes.  

>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. 

Block 2 has ( a ) on exit, and block 4 has ( a ) on entry.  No phi
nodes or moves necessary here.

The case where the stack depths differ is rare, but has also to be
supported by a standard Forth compiler.  And there what you have to do
is not just phi removal, you have to reconcile depths of the two
stacks.  I sketched that in my first RAFTS paper.

>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 ( -- ).

Yes, assuming that the original Block 2 is "!", not "z !".

>The decision is which to choose.

If there are loop back-edges involved, always choose to put the action
on the back edge.

Otherwise, if you don't want to do any additional analysis (and why do
analysis for such a rare case?), choose the one that stores to memory
("push" in your intermediate representation); this may reduce the
register pressure and reduce the number of phi nodes (or moves from
phi removal before optimization).

- 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 2013: http://www.euroforth.org/ef13/

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