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

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

RAFTS-like compiler; some progress

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

Contents

  RAFTS-like compiler; some progress Alex McDonald <blog@rivadpm.com> - 2013-02-06 15:55 -0800
    Re: RAFTS-like compiler; some progress Spam@ControlQ.com - 2013-02-08 16:16 -0500
      Re: RAFTS-like compiler; some progress Alex McDonald <blog@rivadpm.com> - 2013-02-08 14:40 -0800
        Re: RAFTS-like compiler; some progress mhx@iae.nl (Marcel Hendrix) - 2013-02-09 10:37 +0200
          Re: RAFTS-like compiler; some progress Roelf Toxopeus <rt4all@notthis.hetnet.nl> - 2013-02-09 12:06 +0100
            Re: RAFTS-like compiler; some progress albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-02-09 15:46 +0000
          Re: RAFTS-like compiler; some progress anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-02-09 14:38 +0000
            Re: RAFTS-like compiler; some progress Brad Eckert <hwfwguy@gmail.com> - 2013-02-11 08:57 -0800
              Re: RAFTS-like compiler; some progress anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-02-11 17:39 +0000
                Re: RAFTS-like compiler; some progress Brad Eckert <hwfwguy@gmail.com> - 2013-02-11 10:48 -0800
                  Re: RAFTS-like compiler; some progress Alex McDonald <blog@rivadpm.com> - 2013-02-11 18:56 -0800
                    Re: RAFTS-like compiler; some progress Alex McDonald <blog@rivadpm.com> - 2013-02-11 18:58 -0800
                    Re: RAFTS-like compiler; some progress anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-02-14 12:55 +0000
        Re: RAFTS-like compiler; some progress anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-02-09 14:44 +0000
          Re: RAFTS-like compiler; some progress Alex McDonald <blog@rivadpm.com> - 2013-02-11 19:09 -0800

#19520 — RAFTS-like compiler; some progress

I've made a small amount of progress with the analytic compiler.
Here's the IL with hand edited comments;


: testif 1 2 if 3 4 if 5 then then 6 ;

block ( S: 0 -- 1 R: 0 -- 0 )            \ stack is 0 in, and 1 out
$2A40020 (1)     block-begin
$2A40044 (1) [5] literal $1              \ [5] represents register 5
$2A40068 (1) [4] literal $2              \ (n) represents the use
count
$2A4008C (1)     sput [5] S[-1]          \ puts reg 5 on the stack
$2A400B0 (1)     sptr+ -1                \ adjust stack
$2A400D4 (1)     bra-z [4] --> $2A40314
$2A400F8 (1)     block-end
$2A4011C (1)     block-begin
$2A40140 (1) [3] literal $3
$2A40164 (1) [2] literal $4
$2A40188 (1)     sput [3] S[-1]
$2A401AC (1)     sptr+ -1
$2A401D0 (1)     bra-z [2] --> $2A402CC
$2A401F4 (1)     block-end
$2A40218 (1)     block-begin
$2A4023C (1) [1] literal $5
$2A40260 (1)     sput [1] S[-1]
$2A40284 (1)     sptr+ -1
$2A402A8 (1)     block-end
$2A402CC (1)     block-begin             \ empty; nothing between
"then then"
$2A402F0 (1)     block-end
$2A40314 (1)     block-begin
$2A40338 (1) [6] literal $6
$2A4035C (1)     sput [6] S[-1]
$2A40380 (1)     sptr+ -1
$2A403A4 (1)     block-end


Progress, since the prior version didn't support conditionals. The
burg is also making (very slow) progress.

[toc] | [next] | [standalone]

#19560

On Wed, 6 Feb 2013, Alex McDonald wrote:

> Date: Wed, 6 Feb 2013 15:55:13 -0800 (PST)
> From: Alex McDonald <blog@rivadpm.com>
> Newsgroups: comp.lang.forth
> Subject: RAFTS-like compiler; some progress
> 
> I've made a small amount of progress with the analytic compiler.
> Here's the IL with hand edited comments;
>
>
> : testif 1 2 if 3 4 if 5 then then 6 ;
>
> block ( S: 0 -- 1 R: 0 -- 0 )            \ stack is 0 in, and 1 out
> $2A40020 (1)     block-begin
> $2A40044 (1) [5] literal $1              \ [5] represents register 5
> $2A40068 (1) [4] literal $2              \ (n) represents the use
> count
> $2A4008C (1)     sput [5] S[-1]          \ puts reg 5 on the stack
> $2A400B0 (1)     sptr+ -1                \ adjust stack
> $2A400D4 (1)     bra-z [4] --> $2A40314
> $2A400F8 (1)     block-end
> $2A4011C (1)     block-begin
> $2A40140 (1) [3] literal $3
> $2A40164 (1) [2] literal $4
> $2A40188 (1)     sput [3] S[-1]
> $2A401AC (1)     sptr+ -1
> $2A401D0 (1)     bra-z [2] --> $2A402CC
> $2A401F4 (1)     block-end
> $2A40218 (1)     block-begin
> $2A4023C (1) [1] literal $5
> $2A40260 (1)     sput [1] S[-1]
> $2A40284 (1)     sptr+ -1
> $2A402A8 (1)     block-end
> $2A402CC (1)     block-begin             \ empty; nothing between
> "then then"
> $2A402F0 (1)     block-end
> $2A40314 (1)     block-begin
> $2A40338 (1) [6] literal $6
> $2A4035C (1)     sput [6] S[-1]
> $2A40380 (1)     sptr+ -1
> $2A403A4 (1)     block-end
>
>
> Progress, since the prior version didn't support conditionals. The
> burg is also making (very slow) progress.
>

Alex,

I'm not entirely sure I understand what a RAFTS-like compiler is.  Do you 
have pointers/references??  Is this a virtual assembler language?  My 
miniforth interpreter generates the following for your testif word, and 
the stack is shown below ... I guess I'm trying to find the point of your 
exercise, and where you're heading with this ... seems intriguing 8-).

Cheers,
Rob.

-- MiniForth-Hosted alpha Version: 00.01.16D
-- www.ControlQ.com
ok : testif 1 2 if 3 4 if 5 then then 6 ;
ok ' testif see
-- testif (627A60) word flg: 0.
607A60  (literal) = 1
607A70  (literal) = 2
607A80  ?branch -> 607AD0
607A90  (literal) = 3
607AA0  (literal) = 4
607AB0  ?branch -> 607AD0
607AC0  (literal) = 5
607AD0  (literal) = 6
607AE0  next
ok testif .s
4  : 1 3 5 6 ok

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

#19563

On Feb 8, 9:16 pm, S...@ControlQ.com wrote:
> On Wed, 6 Feb 2013, Alex McDonald wrote:
> > Date: Wed, 6 Feb 2013 15:55:13 -0800 (PST)
> > From: Alex McDonald <b...@rivadpm.com>
> > Newsgroups: comp.lang.forth
> > Subject: RAFTS-like compiler; some progress
>
> > I've made a small amount of progress with the analytic compiler.
> > Here's the IL with hand edited comments;
>
> > : testif 1 2 if 3 4 if 5 then then 6 ;
>
> > block ( S: 0 -- 1 R: 0 -- 0 )            \ stack is 0 in, and 1 out
> > $2A40020 (1)     block-begin
> > $2A40044 (1) [5] literal $1              \ [5] represents register 5
> > $2A40068 (1) [4] literal $2              \ (n) represents the use
> > count
> > $2A4008C (1)     sput [5] S[-1]          \ puts reg 5 on the stack
> > $2A400B0 (1)     sptr+ -1                \ adjust stack
> > $2A400D4 (1)     bra-z [4] --> $2A40314
> > $2A400F8 (1)     block-end
> > $2A4011C (1)     block-begin
> > $2A40140 (1) [3] literal $3
> > $2A40164 (1) [2] literal $4
> > $2A40188 (1)     sput [3] S[-1]
> > $2A401AC (1)     sptr+ -1
> > $2A401D0 (1)     bra-z [2] --> $2A402CC
> > $2A401F4 (1)     block-end
> > $2A40218 (1)     block-begin
> > $2A4023C (1) [1] literal $5
> > $2A40260 (1)     sput [1] S[-1]
> > $2A40284 (1)     sptr+ -1
> > $2A402A8 (1)     block-end
> > $2A402CC (1)     block-begin             \ empty; nothing between
> > "then then"
> > $2A402F0 (1)     block-end
> > $2A40314 (1)     block-begin
> > $2A40338 (1) [6] literal $6
> > $2A4035C (1)     sput [6] S[-1]
> > $2A40380 (1)     sptr+ -1
> > $2A403A4 (1)     block-end
>
> > Progress, since the prior version didn't support conditionals. The
> > burg is also making (very slow) progress.
>
> Alex,
>
> I'm not entirely sure I understand what a RAFTS-like compiler is.  Do you
> have pointers/references??  Is this a virtual assembler language?  My
> miniforth interpreter generates the following for your testif word, and
> the stack is shown below ... I guess I'm trying to find the point of your
> exercise, and where you're heading with this ... seems intriguing 8-).
>
> Cheers,
> Rob.
>
> -- MiniForth-Hosted alpha Version: 00.01.16D
> --www.ControlQ.com
> ok : testif 1 2 if 3 4 if 5 then then 6 ;
> ok ' testif see
> -- testif (627A60) word flg: 0.
> 607A60  (literal) = 1
> 607A70  (literal) = 2
> 607A80  ?branch -> 607AD0
> 607A90  (literal) = 3
> 607AA0  (literal) = 4
> 607AB0  ?branch -> 607AD0
> 607AC0  (literal) = 5
> 607AD0  (literal) = 6
> 607AE0  next
> ok testif .s
> 4  : 1 3 5 6 ok

RAFTS is explained on Anton Ertl's website; see
http://www.complang.tuwien.ac.at/projects/backends.html

Forth native code generation.
    (Anton Ertl, Christian Pirker). Paper (EuroForth'92); Diplomarbeit
(in German); Ph.D. Thesis chapter; a paper on the basic block part,
with results (EuroForth'96); the paper on the internal organization of
the compiler (EuroForth '97) may also be interesting to people not
interested in Forth. Status report. The FWF (Austrian Science
Foundation) supported this work (project number P11231).

This code was discussed here; http://groups.google.com/group/comp.lang.forth/msg/ce281a35d6e083b8

begin-structure point
  field: .x
  field: .y
end-structure
: test ( addr -- ) >r r@ .x @ r@ .y @ 2dup + r@ .x ! - r> .y ! ;

for which I generate

$29B0020 (1)     block-begin ( S: 1 -- 0 R: 0 -- 0 )
$29B0044 (4) [3] sget S[0]
$29B0068 (2) [7] @ [3]
$29B008C (2) [2] literal $4
$29B00B0 (1) [6] + [2] [3]
$29B00D4 (2) [5] @ [6]
$29B00F8 (1) [8] + [5] [7]
$29B011C (1)     ! [3] [8]
$29B0140 (1) [4] - [5] [7]
$29B0164 (1) [1] + [2] [3]
$29B0188 (1)     ! [1] [4]
$29B01AC (1)     sptr+ 1
$29B01D0 (1)     block-end

The code generator using a burg is not complete. Without it, even a
naive generation (one line of code per IL) would be relatively
efficient. VFX generated 21 instructions and BigForth generated 22. I
reckon the above is 11 or 12 instructions assuming 5 free registers.
Spills if there fewer regs would increase that number. A good burg
should generate around 7 to 8 instructions.

Certainly this is more efficient than an ITC or my current STC which
generates

see test
: test ( ? -- ? )
\ std call compiles; code=$41ADB2 len=99 type=1
\ defined in (console)
( $0 )    push    eax                               \ 50
( $1 )    mov     eax dword { $0 ebp }              \ 8B4500
( $4 )    add     ebp $4                            \ 83C504
( $7 )    mov     dword { $-4 ebp } eax             \ 8945FC
( $A )    mov     eax dword { esp }                 \ 8B0424
( $D )    sub     ebp $4                            \ 83ED04
( $10 )   mov     eax dword { eax }                 \ 8B00
( $12 )   mov     dword { $-4 ebp } eax             \ 8945FC
( $15 )   mov     eax dword { esp }                 \ 8B0424
( $18 )   sub     ebp $4                            \ 83ED04
( $1B )   add     eax $4                            \ 83C004
( $1E )   mov     eax dword { eax }                 \ 8B00
( $20 )   mov     ecx dword { $0 ebp }              \ 8B4D00
( $23 )   mov     dword { $-4 ebp } eax             \ 8945FC
( $26 )   mov     dword { $-8 ebp } ecx             \ 894DF8
( $29 )   sub     ebp $8                            \ 83ED08
( $2C )   add     eax dword { $0 ebp }              \ 034500
( $2F )   add     ebp $4                            \ 83C504
( $32 )   mov     dword { $-4 ebp } eax             \ 8945FC
( $35 )   mov     eax dword { esp }                 \ 8B0424
( $38 )   sub     ebp $4                            \ 83ED04
( $3B )   mov     ecx dword { $0 ebp }              \ 8B4D00
( $3E )   mov     dword { eax } ecx                 \ 8908
( $40 )   mov     eax dword { $4 ebp }              \ 8B4504
( $43 )   add     ebp $8                            \ 83C508
( $46 )   neg     eax                               \ F7D8
( $48 )   add     eax dword { $0 ebp }              \ 034500
( $4B )   add     ebp $4                            \ 83C504
( $4E )   mov     dword { $-4 ebp } eax             \ 8945FC
( $51 )   pop     eax                               \ 58
( $52 )   sub     ebp $4                            \ 83ED04
( $55 )   add     eax $4                            \ 83C004
( $58 )   mov     ecx dword { $0 ebp }              \ 8B4D00
( $5B )   mov     dword { eax } ecx                 \ 8908
( $5D )   mov     eax dword { $4 ebp }              \ 8B4504
( $60 )   add     ebp $8                            \ 83C508
( $63 )   ret                                       \ C3 ( end ) ok

Too many.

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

#19572

Alex McDonald <blog@rivadpm.com> writes Re: RAFTS-like compiler; some progress
[..]
>> > I've made a small amount of progress with the analytic compiler.
>> > Here's the IL with hand edited comments;
>>
>> > : testif 1 2 if 3 4 if 5 then then 6 ;
>>
There is a typical Forth problem with this definition.

This is how iForth translates

: testif2 1 0 if 3 0 if 5 then then 6 ;

$014049C0  : [trashed]
$014049CA  cmp           rbx, rbx
$014049CD  mov           rdi, 1 d#
$014049D4  mov           rcx, rdi
$014049D7  mov           rbx, rcx
$014049DA  je            $014049F9 offset NEAR
$014049E0  cmp           rcx, rcx
$014049E3  push          rbx
$014049E4  mov           rbx, 3 d#
$014049EB  je            $014049F9 offset NEAR
$014049F1  push          rbx
$014049F2  mov           rbx, 5 d#
$014049F9  push          rbx
$014049FA  push          6 b#
$014049FC  ;

Apparently the optimizer sees that "2/4 if" can be evaluated at compile-time.
Why didn't it just compile 

$01404A80  : [trashed]
$01404A8A  push          1 b#
$01404A8C  push          6 b#
$01404A8E  ;

The iForth reason is that authors expect to be able to write

0 value addr
: tt 0 if [ 3 , here cell- TO addr ]  then  addr @ . ;

-marcel

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

#19575

In article <84669394018434@frunobulax.edu>, mhx@iae.nl (Marcel Hendrix) 
wrote:
 
> The iForth reason is that authors expect to be able to write
> 
> 0 value addr
> : tt 0 if [ 3 , here cell- TO addr ]  then  addr @ . ;

Yes, allthough I never used 0 IF, but AHEAD. No test, jump over 
unconditionally (also the intention is clearer for some ;0).

-r

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

#19583

In article <rt4all-0CC20C.12061309022013@[10.12.75.213]>,
Roelf Toxopeus  <rt4all@notthis.hetnet.nl> wrote:
>In article <84669394018434@frunobulax.edu>, mhx@iae.nl (Marcel Hendrix)
>wrote:
>
>> The iForth reason is that authors expect to be able to write
>>
>> 0 value addr
>> : tt 0 if [ 3 , here cell- TO addr ]  then  addr @ . ;
>
>Yes, allthough I never used 0 IF, but AHEAD. No test, jump over
>unconditionally (also the intention is clearer for some ;0).

I use the same trick, but everywhere it is used I compile SKIP
which is an alias of BRANCH, to indicate the purpose.

: test [ "aap" ] DLITERAL ;

>
>-r

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]

#19577

mhx@iae.nl (Marcel Hendrix) writes:
>0 value addr
>: tt 0 if [ 3 , here cell- TO addr ]  then  addr @ . ;

This can still work in a compiler that optimizes 0 IF to AHEAD and
eliminates unreachable code: The code just needs to be in a different
area than the data dictionary managed with ALLOT and HERE.  That's a
good idea anyway, to avoid cache consistency slowdowns.

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

#19635

On Saturday, February 9, 2013 7:38:19 AM UTC-7, Anton Ertl wrote:
> 
> This can still work in a compiler that optimizes 0 IF to AHEAD and
> eliminates unreachable code

That's what [IF] and [THEN] are for.

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

#19636

Brad Eckert <hwfwguy@gmail.com> writes:
>On Saturday, February 9, 2013 7:38:19 AM UTC-7, Anton Ertl wrote:
>> 
>> This can still work in a compiler that optimizes 0 IF to AHEAD and
>> eliminates unreachable code
>
>That's what [IF] and [THEN] are for.

Is your argument that a compiler should not try to eliminate
unreachable code because we have [IF] and [THEN]?  Maybe, but
apparently Marcel was disappointed that his compiler did not perform
the 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]

#19637

On Monday, February 11, 2013 10:39:44 AM UTC-7, Anton Ertl wrote:
> 
> Is your argument that a compiler should not try to eliminate
> unreachable code because we have [IF] and [THEN]?  
> 
Yes. Why spend time working on an optimization the compiler will probably never encounter in real code?

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

#19660

On Feb 11, 10:48 am, Brad Eckert <hwfw...@gmail.com> wrote:
> On Monday, February 11, 2013 10:39:44 AM UTC-7, Anton Ertl wrote:
>
> > Is your argument that a compiler should not try to eliminate
> > unreachable code because we have [IF] and [THEN]?
>
> Yes. Why spend time working on an optimization the compiler will probably never encounter in real code?


Unreachable and/or dead code can also be generated by compiler
optimizations that the programmer didn't explicitly write. Here's a
non-branching example.

: calc-a&b ( n -- n n ) ( this is in a library )
    dup 0> if 1 else -1 then swap * ;
...
: doit calc-a&b nip ;
( : doit * ; \ what the compiler generates. )

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

#19661

On Feb 11, 6:56 pm, Alex McDonald <b...@rivadpm.com> wrote:
> On Feb 11, 10:48 am, Brad Eckert <hwfw...@gmail.com> wrote:
>
> > On Monday, February 11, 2013 10:39:44 AM UTC-7, Anton Ertl wrote:
>
> > > Is your argument that a compiler should not try to eliminate
> > > unreachable code because we have [IF] and [THEN]?
>
> > Yes. Why spend time working on an optimization the compiler will probably never encounter in real code?
>
> Unreachable and/or dead code can also be generated by compiler
> optimizations that the programmer didn't explicitly write. Here's a
> non-branching example.
>
> : calc-a&b ( n -- n n ) ( this is in a library )
>     dup 0> if 1 else -1 then swap * ;
> ...
> : doit calc-a&b nip ;
> ( : doit * ; \ what the compiler generates. )

s/generated/eliminated/

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

#19727

Alex McDonald <blog@rivadpm.com> writes:
>Unreachable and/or dead code can also be generated by compiler
>optimizations that the programmer didn't explicitly write. Here's a
>non-branching example.
>
>: calc-a&b ( n -- n n ) ( this is in a library )
>    dup 0> if 1 else -1 then swap * ;
>...
>: doit calc-a&b nip ;
>( : doit * ; \ what the compiler generates. )

The other test of compiler optimization here is the "SWAP *".  Before
anybody says that this is contrived, there used to be (maybe still is)
an occurence of "SWAP +" in the FSL.

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

#19578

Alex McDonald <blog@rivadpm.com> writes:
>RAFTS is explained on Anton Ertl's website; see
>http://www.complang.tuwien.ac.at/projects/backends.html

An even better link is:

http://www.complang.tuwien.ac.at/projects/rafts.html

These days, I would leave the instruction scheduling part away, which
should simplify things and should make little difference on the
out-of-order CPUs whe have had since about 1995.

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

#19662

On Feb 9, 6:44 am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:
> Alex McDonald <b...@rivadpm.com> writes:
> >RAFTS is explained on Anton Ertl's website; see
> >http://www.complang.tuwien.ac.at/projects/backends.html
>
> An even better link is:
>
> http://www.complang.tuwien.ac.at/projects/rafts.html

Thanks.

>
> These days, I would leave the instruction scheduling part away, which
> should simplify things and should make little difference on the
> out-of-order CPUs whe have had since about 1995.

I've a way to go.

1. Generating the correct PHI constructions, particularly for blocks
entry & exit for IF/THEN/ELSE is taxing my brain. For example, this
unbalanced definition    : x if 6 y else z then ! ;    I can see a
solution, though.

2. Writing the equivalent of iburg. There are lost of Forthish tricks
that C can't do that make this quite an interesting project. In
particular, generating tree matching code to then include (or
evaluate) that code doesn't seem to be the best way of doing this; it
may be possible to do the matching dynamically directly from the
grammar.

3. Writing the grammar rules.

4. and so on...

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