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

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

RAFTS beyond basic blocks; handling phi

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

Contents

  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

#25611 — RAFTS beyond basic blocks; handling phi

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.

 

[toc] | [next] | [standalone]

#25613

Alex McDonald <blog@rivadpm.com> wrote:

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

Ouch!
The esoterics must have confused you..

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

#25618

on 10/09/2013 22:30:17,  wrote:
> Alex McDonald <blog@rivadpm.com> wrote:
> 
>> 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.
> 
> Ouch!
> The esoterics must have confused you..

:-)

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. 

Where the "esoteric" literature will help is in machine code generation
from SSA. I've still an SSA -> code (a BURG) and register allocation
pieces to research & write.

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

#25619

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.

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

#25621

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.
 

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

#25623

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.

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

#25627

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

That's not domination.  I guess you mean that a basic block B has at
most two preceding basic blocks, i.e., basic blocks that jump or fall
through to B.  Yes, you can organize your control-flow graph in that
way (and you will have empty basic blocks in some cases), or you can
eliminate empty basic blocks and have more than two preceding blocks
in some cases.

Anyway, a basic block A dominates a basic block B if every path to B
goes through A.  There can be more than two basic blocks that dominate
a basic block, e.g.:

C: if ... goto X
D: if ... goto X
E: if ... goto X
F: ...
X:

Here F is dominated by C, D, and E.  Note that domination is a
transitive relation.  One can represent domination as directed tree,
in this case:

C -> D -> E -> F
  \> X

Note that each basic block has only one immediate dominator.

The basic block at the start of a loop back edge (defined in the usual
way) cannot dominate the basic block at the end of the back edge
(except through self-domination, but the back edge is not involved in
that).

This comes from the definition of the back edge, but one can write
standard Forth code where the normal compiler construction definitions
of back edge runs counter to the intuition of the Forth programmer
(but that kind of code is not idiomatic):

( bb1 )
ahead
begin
( bb2 )
...
[ 1 cs-roll ]
then
( bb3 )
...
until
( bb4 )

In this loop the back edge is the fall-through from bb2 to bb3; and
bb3 dominates bb2, not the other way round.  The more usual way to
write this is as follows, however:

( bb1 )
begin
 ( bb3 )
 ... 0= while
  ( bb2 )
  ...
repeat
( bb4 )

and here the Forth and compiler notions of loop back edge agree.

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

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

#25622

"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/

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

#25624

on 11/09/2013 11:55:06, Anton wrote:

[snip] 

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

Yes, my error. Only "!".

> 
>>The decision is which to choose.
> 
> If there are loop back-edges involved, always choose to put the action
> on the back edge.

OK. I presume there's a good reason for this; reduction in traffic?

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

I'm going to start with phi and see where that takes me when it comes to
phi removal and copy insertion; I'll let the resulting quality of the SSA
decide.

Since I'm going to generate for the x86, register pressure will be a
serious concern. And my first attempts at register allocation using naive
methods are pretty poor. My simple approach works OK for free+2 or +3
registers; beyond 3, the spilling becomes a horrendous cascade of
shuffling, partly because of the necessity to use specific registers for
certain operations. Some SSA reordering would help in any case, since
final virtual register references in the SSA can be a long way from their
previous references or definitions.

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

#25634

Alex McDonald wrote:
> Since I'm going to generate for the x86, register pressure will be a
> serious concern.

Indeed, the question is: Why don't you just target x64?  8 more registers, 
and since Windows XP is reaching EOL very soon, there is little incentive to 
stay with 32 bits, even on Windows.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

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

#25635

on 11/09/2013 19:33:36, Bernd Paysan wrote:
> Alex McDonald wrote:
>> Since I'm going to generate for the x86, register pressure will be a
>> serious concern.
> 
> Indeed, the question is: Why don't you just target x64? 8 more
> registers, and since Windows XP is reaching EOL very soon, there is
> little incentive to stay with 32 bits, even on Windows.
> 

The underlying Forth doesn't support it yet, and it's a non-trivial task
as the meta- compiler is self hosting. However, code generators are
"plugable", so it doesn't preclude it at a later date.

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

#25638

Alex McDonald wrote:

> on 11/09/2013 19:33:36, Bernd Paysan wrote:
>> Alex McDonald wrote:
>>> Since I'm going to generate for the x86, register pressure will be a
>>> serious concern.
>> 
>> Indeed, the question is: Why don't you just target x64? 8 more
>> registers, and since Windows XP is reaching EOL very soon, there is
>> little incentive to stay with 32 bits, even on Windows.
>> 
> 
> The underlying Forth doesn't support it yet, and it's a non-trivial task
> as the meta- compiler is self hosting.

We meta-compiled 64 bit Gforth on the 32 bit Gforth, too, because there was, 
once upon a time, no 64 bit machine.  Even the 32 bit Forth system 
(bigForth) that created the first Gforth images was once metacompiled from a 
16 bit system.

> However, code generators are
> "plugable", so it doesn't preclude it at a later date.

Yes, but wrangling with 8 registers on a RAFTS-like compiler seems to be a 
waste of time, at least IMHO.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

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

#25654

Bernd Paysan <bernd.paysan@gmx.de> writes:
>Alex McDonald wrote:
>> However, code generators are
>> "plugable", so it doesn't preclude it at a later date.
>
>Yes, but wrangling with 8 registers on a RAFTS-like compiler seems to be a 
>waste of time, at least IMHO.

Reducing the number of registers is useful for testing spilling.
Working on optimizations that are useful only for few-register
machines is of questionable value, though.

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

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

#25639

In article <l0qd20$ta6$1@online.de>, Bernd Paysan  <bernd.paysan@gmx.de> wrote:
>Alex McDonald wrote:
>> Since I'm going to generate for the x86, register pressure will be a
>> serious concern.
>
>Indeed, the question is: Why don't you just target x64?  8 more registers,
>and since Windows XP is reaching EOL very soon, there is little incentive to
>stay with 32 bits, even on Windows.

Indeed. If I add floating point to ciforth, I need an extra stack pointer.
I don't even contemplate to try that on a 32 bit machine.

>
>--
>Bernd Paysan
>

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#25646

on 11/09/2013 13:10:16, "Alex McDonald" wrote:
> on 11/09/2013 11:55:06, Anton wrote:

>>
>> If there are loop back-edges involved, always choose to put the action
>> on the back edge.
> 
> OK. I presume there's a good reason for this; reduction in traffic?
> 

Yes, from what I can see; but that brings me to a problem with generating
back edges. Consider

: foo begin + again ;

If we don't insert a phi on the back edge, but simply balance the stack;

B[1] <1> pop           ( a )
B[1] <2> pop           ( a|c b )
B[1] <3> + <1> <2>     ( c )
B[1]     push <3>      ( -- )
B[1]     jmp <1>

OK, but inefficent. Better is

B[1] <1> pop           ( a )
B[1] <2> pop           ( a|c b )
B[1] <4> +   <2> <3>   ( c )
B[1] <3> phi <1> <4>   ( a|c )  
B[1]     jmp <2>

A few issues. Now I have a DCG rather than a DAG. That can be resolved by
marking visits while walking what is now a DCG.

The other issue is determining that we need a B[1] jmp <2>; that is, not
to the head of the block. Either that or the block is split between <1>
and <2>; but again, how do we determine that? Can we use the left operand
of <3> phi <1> <4> (the <1>, what would be the block entry) to select the
split or branch point?

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

#25647

on 12/09/2013 23:53:05, "Alex McDonald" wrote:
> on 11/09/2013 13:10:16, "Alex McDonald" wrote:
>> on 11/09/2013 11:55:06, Anton wrote:
> 
>>>
>>> If there are loop back-edges involved, always choose to put the action
>>> on the back edge.
>>
>> OK. I presume there's a good reason for this; reduction in traffic?
>>
> 
> Yes, from what I can see; but that brings me to a problem with
> generating back edges. Consider
> 
>: foo begin + again ;
> 
> If we don't insert a phi on the back edge, but simply balance the
> stack;
> 
> B[1] <1> pop           ( a )
> B[1] <2> pop           ( a|c b )
> B[1] <3> + <1> <2>     ( c )
> B[1]     push <3>      ( -- )
> B[1]     jmp <1>
> 
> OK, but inefficent. Better is
> 
> B[1] <1> pop           ( a )
> B[1] <2> pop           ( a|c b )
> B[1] <4> +   <2> <3>   ( c )
> B[1] <3> phi <1> <4>   ( a|c )
> B[1]     jmp <2>
> 
> A few issues. Now I have a DCG rather than a DAG. That can be resolved
> by marking visits while walking what is now a DCG.
> 
> The other issue is determining that we need a B[1] jmp <2>; that is,
> not to the head of the block. Either that or the block is split
> between <1> and <2>; but again, how do we determine that? Can we use
> the left operand of <3> phi <1> <4> (the <1>, what would be the block
> entry) to select the split or branch point?

Clarification; that is, select <2> which follows <1>.

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

#25648

on 12/09/2013 23:55:49, "Alex McDonald" wrote:
> on 12/09/2013 23:53:05, "Alex McDonald" wrote:
>> on 11/09/2013 13:10:16, "Alex McDonald" wrote:
>>> on 11/09/2013 11:55:06, Anton wrote:
>>
>>>>
>>>> If there are loop back-edges involved, always choose to put the action
>>>> on the back edge.
>>>
>>> OK. I presume there's a good reason for this; reduction in traffic?
>>>
>>
>> Yes, from what I can see; but that brings me to a problem with
>> generating back edges. Consider
>>
>>: foo begin + again ;
>>
>> If we don't insert a phi on the back edge, but simply balance the
>> stack;
>>
>> B[1] <1> pop           ( a )
>> B[1] <2> pop           ( a|c b )
>> B[1] <3> + <1> <2>     ( c )
>> B[1]     push <3>      ( -- )
>> B[1]     jmp <1>
>>
>> OK, but inefficent. Better is
>>
>> B[1] <1> pop           ( a )
>> B[1] <2> pop           ( a|c b )
>> B[1] <4> +   <2> <3>   ( c )
>> B[1] <3> phi <1> <4>   ( a|c )
>> B[1]     jmp <2>
>>
>> A few issues. Now I have a DCG rather than a DAG. That can be resolved
>> by marking visits while walking what is now a DCG.
>>
>> The other issue is determining that we need a B[1] jmp <2>; that is,
>> not to the head of the block. Either that or the block is split
>> between <1> and <2>; but again, how do we determine that? Can we use
>> the left operand of <3> phi <1> <4> (the <1>, what would be the block
>> entry) to select the split or branch point?
> 
> Clarification; that is, select <2> which follows <1>.

Ah, skip that, I see my mistake; hand generating code leads to all sorts
of assumptions. The stack gets adjusted, hence the TOS is <2>.

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

#25656

"Alex McDonald" <blog@rivadpm.com> writes:
>: foo begin + again ;
...
>B[1] <1> pop           ( a )
>B[1] <2> pop           ( a|c b )
>B[1] <4> +   <2> <3>   ( c )
>B[1] <3> phi <1> <4>   ( a|c )  
>B[1]     jmp <2>

Yes, since there is a jmp to <2>, a new BB starts there.  Also, phi
instructions are at the start of the BB.  I.e., it should look as
follows:

>B[1] <1> pop           ( a )
>B[2] <3> phi <1> <4>   ( a|c )  
>B[2] <2> pop           ( a|c b )
>B[2] <4> +   <2> <3>   ( c )
>B[2]     jmp <3>

After phi removal, this is:

>B[1] <1> pop           ( a )
>B[1] <3> mov <1>
>B[2] <2> pop           ( a|c b )
>B[2] <4> +   <2> <3>   ( c )
>B[2] <3> mov <4>
>B[2]     jmp <2>

>A few issues. Now I have a DCG rather than a DAG.

Yes, if you look at the data flow graph including phi nodes and their
edges, you can get cycles.

>The other issue is determining that we need a B[1] jmp <2>; that is, not
>to the head of the block. Either that or the block is split between <1>
>and <2>; but again, how do we determine that?

Every branch target starts a new basic block.  Or maybe I
misunderstand your problem.

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

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

#25691

on 13/09/2013 14:19:23,  wrote:
> "Alex McDonald" <blog@rivadpm.com> writes:
>>: foo begin + again ;
> ...
>>B[1] <1> pop           ( a )
>>B[1] <2> pop           ( a|c b )
>>B[1] <4> +   <2> <3>   ( c )
>>B[1] <3> phi <1> <4>   ( a|c )
>>B[1]     jmp <2>
> 
> Yes, since there is a jmp to <2>, a new BB starts there.  Also, phi
> instructions are at the start of the BB.  I.e., it should look as
> follows:


Yes, classically they do. But practically they can be anywhere in the
block as long as the copies (the <3> mov <x>s below) are generated at the
correct point in the tree.


> 
>>B[1] <1> pop           ( a )
>>B[2] <3> phi <1> <4>   ( a|c )
>>B[2] <2> pop           ( a|c b )
>>B[2] <4> +   <2> <3>   ( c )
>>B[2]     jmp <3>
> 
> After phi removal, this is:
> 
>>B[1] <1> pop           ( a )
>>B[1] <3> mov <1>
>>B[2] <2> pop           ( a|c b )
>>B[2] <4> +   <2> <3>   ( c )
>>B[2] <3> mov <4>
>>B[2]     jmp <2>

Thaks, that's a good clarification.

> 
>>A few issues. Now I have a DCG rather than a DAG.
> 
> Yes, if you look at the data flow graph including phi nodes and their
> edges, you can get cycles.
> 
>>The other issue is determining that we need a B[1] jmp <2>; that is, not
>>to the head of the block. Either that or the block is split between <1>
>>and <2>; but again, how do we determine that?
> 
> Every branch target starts a new basic block.  Or maybe I
> misunderstand your problem.

It's how to determine the branch targets; I think I may have worked it
out however.

> 
> - anton

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

#25650

"Alex McDonald" <blog@rivadpm.com> writes:
>on 11/09/2013 11:55:06, Anton wrote:
>> If there are loop back-edges involved, always choose to put the action
>> on the back edge.
>
>OK. I presume there's a good reason for this; reduction in traffic?

That's the only way it works.

E.g.,, if you have a loop

: foo ( u -- ... ) begin dup 1- dup 0= until ;

If you don't put a store and a stack pointer update on the back edge,
the code will not be correct.

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

[toc] | [prev] | [standalone]

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

csiph-web