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

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

Code generation, in particular for iForth

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

Contents

  Code generation, in particular for iForth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-07-24 06:22 +0000
    Re: Code generation, in particular for iForth albert@SPENARNC.XS4ALL.NL - 2026-07-24 13:43 +0200
    Re: Code generation, in particular for iForth Hans Bezemer <the.beez.speaks@gmail.com> - 2026-07-24 16:05 +0200
    Re: Code generation, in particular for iForth marcel hendrix <mhx@iae.nl> - 2026-07-24 18:06 +0200
    Re: Code generation, in particular for iForth Paul Rubin <no.email@nospam.invalid> - 2026-07-24 15:58 -0700
      Re: Code generation, in particular for iForth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-07-25 04:21 +0000
    Re: Code generation, in particular for iForth albert@SPENARNC.XS4ALL.NL - 2026-07-25 15:47 +0200
    Re: Code generation, in particular for iForth antispam@fricas.org (Waldek Hebisch) - 2026-07-25 19:28 +0000

#135250 — Code generation, in particular for iForth

Paul Curtis has a code generator for his Forth implementation that is
much more sophisticated than what I have seen on other Forth
implementations.  He asked me about the other Forth implementations,
which resulted in me investigating iForth.  And while I am at it,
here's a review of what I know about the code generators of several
Forth systems.

SwiftForth 4.0 represents the data stack with the top-of-stack in RBX,
the rest in memory, and the stack pointer in RBP.  The return stack is
completely in memory, with RSP as return stack pointer; locals are on
the return stack.  SwifthForth generates code for individual words and
for several hundred sequences of words (superinstructions), but
returns to the canonical stack representation at the boundary between
these pieces; SwiftForth also performs tail-call elimination.

Gforth has a canonical representation of the data stack and return
stack like SwifthForth, but the registers are often different (and
depend on how Gforth is built).  Locals are in memory accessed through
a local-stack pointer.  Gforth uses additional representations of the
data stack (in the development version for AMD64 with 0-3 data stack
items in registers) between words, and has versions of many words for
the different representations.  It also has has about 50
superinstructions, but they currently only work with the canonical
stack representation.  It uses a shortest-path algorithm for selecting
the optimal sequence of versions for different stack representations,
and superinstructions.  It performs neither tail-call elimination nor
inlining.  Gforth uses a threaded-code substrate and performs all
literal accesses and control flow through threaded-code mechanisms.

VFX Forth 64 has the same canonical representations for the data
stack, return stack, and locals as SwiftForth, but performs register
allocation for data stack items (but not for return stack items or
locals) for straight-line code sequences (basic blocks), and only
returns to the canonical representation at the boundary between basic
blocks.  VFX uses inlining, which has synergistic effects with the
register allocation in basic blocks (inlining leads to longer basic
blocks).

32-bit lxf (1.6-982-823) has the same canonical stack representation
as SwiftForth and VFX (except that it uses the 32-bit registers EBX
and EBP).  It performs register allocation for data stack items,
return stack items and locals within a basic block, but it does not
perform inlining.

Now on to iForth (using iForth-5.1-mini, which is quite old; if the
code generation has changed substantially in the meantime, my results
may be outdated):

iForth uses RSP as data-stack pointer, RBP as return-stack pointer,
and in the canonical representation at definition boundaries all stack
items are in memory.  iForth disassembles

: square dup * ;

as

$10226580  : square                     488BC04883ED088F4500      H.@H.m..E.
$1022658A  pop           rbx            5B                        [
$1022658B  imul          rbx, rbx       480FAFDB                  H./[
$1022658F  push          rbx            53                        S
$10226590  ;                            488B45004883C508FFE0      H.E.H.E..` ok

Note the 10 bytes each at the : and the ; lines; these are the
definition prologue and epilogue that allows to use CALL for the call
despite not using RSP for the return stack.  When disassembling this
word fully, we get:

   0x10226580:  mov    %rax,%rax
   0x10226583:  sub    $0x8,%rbp
   0x10226587:  pop    0x0(%rbp)
   0x1022658a:  pop    %rbx
   0x1022658b:  imul   %rbx,%rbx
   0x1022658f:  push   %rbx
   0x10226590:  mov    0x0(%rbp),%rax
   0x10226594:  add    $0x8,%rbp
   0x10226598:  jmp    *%rax

The first three instructions are the prologue; I don't know what the
first instruction is good for, the second updates the return stack
pointer, and the third moves the return address from the data stack
(where CALL put it) to the return stack.  The last three instructions
implement the epilogue (EXIT compiles a jump to the epilogue): get the
return address from the return stack into rax, update the return
stack, and jump to the return address.  iForth performs inlining, so
the prologue and epilogue costs do not occur on every source-level
call.

We also see in this example that iForth first brings the stack item
into a register, then performs the computation in registers, then
pushes the result.  Does it do that in general, does it do that for
return-stack items, does it do that for locals?  Let's look at the
following words to answer that:

: /string.1  tuck - -rot + swap ;
: /string.2  tuck - >r + r> ; 
: /string.3 locals| n u c-addr | c-addr n + u n - ;

I'll show the code without prologue and epilogue:

/string.1               /string.2               /string.3
pop  %rbx               pop  %rbx               pop  %rbx
pop  %rdi               pop  %rdi               lea  -0x10(%rsi),%rsi
sub  %rbx,%rdi          sub  %rbx,%rdi          mov  %rbx,(%rsi)
pop  %rax               pop  %rax               pop  %rbx
lea  (%rax,%rbx,1),%rbx lea  (%rax,%rbx,1),%rbx lea  -0x10(%rsi),%rsi
push %rbx               push %rbx               mov  %rbx,(%rsi)
push %rdi               push %rdi               pop  %rbx
                                                lea  -0x10(%rsi),%rsi
                                                mov  %rbx,(%rsi)
                                                mov  (%rsi),%rbx
                                                add  0x20(%rsi),%rbx
                                                mov  0x10(%rsi),%rdi
                                                sub  0x20(%rsi),%rdi
                                                push %rbx
                                                push %rdi
                                                add  $0x30,%rsi

It looks like iForth keeps data and return-stack items in registers in
straight-line code and pops a stack item into a register only when it
is first needed.

For locals, it seems that there is a locals stack with RSI as locals
stack pointer, and each local is pushed there separately (with its
separate locals-stack update); each local also gets 16 byte, probably
to keep the locals-stack pointer 16-byte aligned.  After setting up
the locals, they are accessed through RSI, and just before the
epilogue, RSI is restored.

Does iForth use its definition-boundary stack representation also at
basic block boundaries, or does it preserve stuff in registers across
basic block boundaries?

For BEGIN it seems to always keep the top-of-stack in RBX, even if the
loop body does not access any data stack items coming from outside the
loop:

variable a
: y begin 1 cells a +! a @ @ until ;

   0x1022728a:  pop    %rbx
   0x1022728b:  lea    0x0(%rax),%rax
   0x10227290:  addq   $0x8,-0x458(%rip)        # 0x10226e40
   0x10227298:  mov    -0x45f(%rip),%rdi        # 0x10226e40
   0x1022729f:  cmpq   $0x0,(%rdi)
   0x102272a3:  je     0x10227290
   0x102272a9:  push   %rbx

Before the loop, the TOS is popped, then not accessed in the loop,
then pushed afterwards.  The second instruction is a nop that aligns
the loop head to an 8-byte boundary.

For IF, things are a little more varied:

: max 2dup < if swap then drop ;

   0x1022730a:  pop    %rbx
   0x1022730b:  pop    %rdi
   0x1022730c:  cmp    %rdi,%rbx
   0x1022730f:  push   %rdi
   0x10227310:  jle    0x1022731e
   0x10227316:  pop    %rdi
   0x10227317:  mov    %rbx,%rcx
   0x1022731a:  mov    %rdi,%rbx
   0x1022731d:  push   %rcx
   0x1022731e:  epilogue

Here the top-of-stack is passed across the IF in %RBX, but the second
stack item, which is in a register at the IF, is pushed back into
memory, only to be popped in the code right after the IF.  In this
case the top-of-stack is dropped at the end, so there is no pushing of
RBX in the end (if you leave the DROP away, there is such a push at
the end).

But iForth does not always keep the TOS in EBX across IF:

: bar if swap then drop ;

   0x1022738a:  pop    %rbx
   0x1022738b:  cmp    $0x0,%rbx
   0x1022738f:  je     0x1022739f
   0x10227395:  pop    %rbx
   0x10227396:  pop    %rdi
   0x10227397:  mov    %rbx,%rcx
   0x1022739a:  mov    %rdi,%rbx
   0x1022739d:  push   %rcx
   0x1022739e:  push   %rbx
   0x1022739f:  pop    %rbx

Here we see no push between the cmp and the conditional branch; all
stack items are in memory across the IF, and the code after the IF has
to pop both of the items it reads from memory.  Because the stack
representation has to be the same at the THEN, iForth pushes both
stack items involved at the end of the block; and the following DROP
then pops one of them.

The code for BAR also shows that iForth keeps TOS in RBX right before
pushing it, so it needs to use the two mov instructions to arrange the
registers appropriately.  Interestingly, for the second stack item it
is more flexible, and can push it from a different register than the
one it popped it into (otherwise a third mov would be needed).

Let's see if it can keep a return-stack item in a register across
basic blocks:

: baz >r if r@ + then r> ;

   0x1022748a:  pop    %rbx
   0x1022748b:  pop    %rdi
   0x1022748c:  cmp    $0x0,%rdi
   0x10227490:  lea    -0x8(%rbp),%rbp
   0x10227494:  mov    %rbx,0x0(%rbp)
   0x10227498:  mov    %rcx,%rbx
   0x1022749b:  je     0x102274ab
   0x102274a1:  mov    0x0(%rbp),%rbx
   0x102274a5:  pop    %rdi
   0x102274a6:  lea    (%rdi,%rbx,1),%rbx
   0x102274aa:  push   %rbx
   0x102274ab:  mov    0x0(%rbp),%rbx
   0x102274af:  lea    0x8(%rbp),%rbp
   0x102274b3:  push   %rbx
  
So the top of the return stack is not kept in a register across the
IF, but instead moved into memory, and the return-stack pointer
updated.  The R@ then copies that return stack item into rbx, and the
r> also gets the return stack item from memory and updates RBP.

Bottom line: iForth uses RSP as data-stack pointer, in order to use
push and pop, but pays for that with definition prologues and
epilogues.  It keeps everything in memory at definition boundaries,
but often keeps the TOS in RBX at basic block boundaries; no such
optimization exists for return-stack items.  Within basic blocks it
can keep data and return-stack items in registers.

Overall, iForth is a little bit more sophisticated than VFX by keeping
return-stack items in registers within basic blocks, with similar
sophistication elsewhere.  I am not sure if its stack representations
at definition and basic block boundaries is a good idea; in
particular, the use of indirect jumps for the returns may result in
worse branch prediction accuracy for the returns in some cases.

- 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: https://forth-standard.org/
EuroForth 2026 CFP: http://www.euroforth.org/ef26/cfp.html

[toc] | [next] | [standalone]

#135253

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> Paul Curtis has a code generator for his Forth implementation that is
> much more sophisticated than what I have seen on other Forth
> implementations.  He asked me about the other Forth implementations,
> which resulted in me investigating iForth.  And while I am at it,
> here's a review of what I know about the code generators of several
> Forth systems.

Thanks for an excellent overview of optimisation in Forth.
Apart from not looking too shabby compared to c, I think it doesn't
matters too much.

Python is eating our lunch as far as simple interpreters is concerned.

<SNIP>
> - anton

Groetjes Albert
--
The glass is half empty. There is no such thing as a free world.
This is the first day of the end of your life.
If you can't beat them, ... too bad.

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

#135256

On 24-07-2026 08:22, Anton Ertl wrote:
4tH does peephole optimization - constant folding, tail-call 
elimination, dead code elimination, strength reduction. That kind of stuff.

Hans Bezemer

> Paul Curtis has a code generator for his Forth implementation that is
> much more sophisticated than what I have seen on other Forth
> implementations.  He asked me about the other Forth implementations,
> which resulted in me investigating iForth.  And while I am at it,
> here's a review of what I know about the code generators of several
> Forth systems.
> 
> SwiftForth 4.0 represents the data stack with the top-of-stack in RBX,
> the rest in memory, and the stack pointer in RBP.  The return stack is
> completely in memory, with RSP as return stack pointer; locals are on
> the return stack.  SwifthForth generates code for individual words and
> for several hundred sequences of words (superinstructions), but
> returns to the canonical stack representation at the boundary between
> these pieces; SwiftForth also performs tail-call elimination.
> 
> Gforth has a canonical representation of the data stack and return
> stack like SwifthForth, but the registers are often different (and
> depend on how Gforth is built).  Locals are in memory accessed through
> a local-stack pointer.  Gforth uses additional representations of the
> data stack (in the development version for AMD64 with 0-3 data stack
> items in registers) between words, and has versions of many words for
> the different representations.  It also has has about 50
> superinstructions, but they currently only work with the canonical
> stack representation.  It uses a shortest-path algorithm for selecting
> the optimal sequence of versions for different stack representations,
> and superinstructions.  It performs neither tail-call elimination nor
> inlining.  Gforth uses a threaded-code substrate and performs all
> literal accesses and control flow through threaded-code mechanisms.
> 
> VFX Forth 64 has the same canonical representations for the data
> stack, return stack, and locals as SwiftForth, but performs register
> allocation for data stack items (but not for return stack items or
> locals) for straight-line code sequences (basic blocks), and only
> returns to the canonical representation at the boundary between basic
> blocks.  VFX uses inlining, which has synergistic effects with the
> register allocation in basic blocks (inlining leads to longer basic
> blocks).
> 
> 32-bit lxf (1.6-982-823) has the same canonical stack representation
> as SwiftForth and VFX (except that it uses the 32-bit registers EBX
> and EBP).  It performs register allocation for data stack items,
> return stack items and locals within a basic block, but it does not
> perform inlining.
> 
> Now on to iForth (using iForth-5.1-mini, which is quite old; if the
> code generation has changed substantially in the meantime, my results
> may be outdated):
> 
> iForth uses RSP as data-stack pointer, RBP as return-stack pointer,
> and in the canonical representation at definition boundaries all stack
> items are in memory.  iForth disassembles
> 
> : square dup * ;
> 
> as
> 
> $10226580  : square                     488BC04883ED088F4500      H.@H.m..E.
> $1022658A  pop           rbx            5B                        [
> $1022658B  imul          rbx, rbx       480FAFDB                  H./[
> $1022658F  push          rbx            53                        S
> $10226590  ;                            488B45004883C508FFE0      H.E.H.E..` ok
> 
> Note the 10 bytes each at the : and the ; lines; these are the
> definition prologue and epilogue that allows to use CALL for the call
> despite not using RSP for the return stack.  When disassembling this
> word fully, we get:
> 
>     0x10226580:  mov    %rax,%rax
>     0x10226583:  sub    $0x8,%rbp
>     0x10226587:  pop    0x0(%rbp)
>     0x1022658a:  pop    %rbx
>     0x1022658b:  imul   %rbx,%rbx
>     0x1022658f:  push   %rbx
>     0x10226590:  mov    0x0(%rbp),%rax
>     0x10226594:  add    $0x8,%rbp
>     0x10226598:  jmp    *%rax
> 
> The first three instructions are the prologue; I don't know what the
> first instruction is good for, the second updates the return stack
> pointer, and the third moves the return address from the data stack
> (where CALL put it) to the return stack.  The last three instructions
> implement the epilogue (EXIT compiles a jump to the epilogue): get the
> return address from the return stack into rax, update the return
> stack, and jump to the return address.  iForth performs inlining, so
> the prologue and epilogue costs do not occur on every source-level
> call.
> 
> We also see in this example that iForth first brings the stack item
> into a register, then performs the computation in registers, then
> pushes the result.  Does it do that in general, does it do that for
> return-stack items, does it do that for locals?  Let's look at the
> following words to answer that:
> 
> : /string.1  tuck - -rot + swap ;
> : /string.2  tuck - >r + r> ;
> : /string.3 locals| n u c-addr | c-addr n + u n - ;
> 
> I'll show the code without prologue and epilogue:
> 
> /string.1               /string.2               /string.3
> pop  %rbx               pop  %rbx               pop  %rbx
> pop  %rdi               pop  %rdi               lea  -0x10(%rsi),%rsi
> sub  %rbx,%rdi          sub  %rbx,%rdi          mov  %rbx,(%rsi)
> pop  %rax               pop  %rax               pop  %rbx
> lea  (%rax,%rbx,1),%rbx lea  (%rax,%rbx,1),%rbx lea  -0x10(%rsi),%rsi
> push %rbx               push %rbx               mov  %rbx,(%rsi)
> push %rdi               push %rdi               pop  %rbx
>                                                  lea  -0x10(%rsi),%rsi
>                                                  mov  %rbx,(%rsi)
>                                                  mov  (%rsi),%rbx
>                                                  add  0x20(%rsi),%rbx
>                                                  mov  0x10(%rsi),%rdi
>                                                  sub  0x20(%rsi),%rdi
>                                                  push %rbx
>                                                  push %rdi
>                                                  add  $0x30,%rsi
> 
> It looks like iForth keeps data and return-stack items in registers in
> straight-line code and pops a stack item into a register only when it
> is first needed.
> 
> For locals, it seems that there is a locals stack with RSI as locals
> stack pointer, and each local is pushed there separately (with its
> separate locals-stack update); each local also gets 16 byte, probably
> to keep the locals-stack pointer 16-byte aligned.  After setting up
> the locals, they are accessed through RSI, and just before the
> epilogue, RSI is restored.
> 
> Does iForth use its definition-boundary stack representation also at
> basic block boundaries, or does it preserve stuff in registers across
> basic block boundaries?
> 
> For BEGIN it seems to always keep the top-of-stack in RBX, even if the
> loop body does not access any data stack items coming from outside the
> loop:
> 
> variable a
> : y begin 1 cells a +! a @ @ until ;
> 
>     0x1022728a:  pop    %rbx
>     0x1022728b:  lea    0x0(%rax),%rax
>     0x10227290:  addq   $0x8,-0x458(%rip)        # 0x10226e40
>     0x10227298:  mov    -0x45f(%rip),%rdi        # 0x10226e40
>     0x1022729f:  cmpq   $0x0,(%rdi)
>     0x102272a3:  je     0x10227290
>     0x102272a9:  push   %rbx
> 
> Before the loop, the TOS is popped, then not accessed in the loop,
> then pushed afterwards.  The second instruction is a nop that aligns
> the loop head to an 8-byte boundary.
> 
> For IF, things are a little more varied:
> 
> : max 2dup < if swap then drop ;
> 
>     0x1022730a:  pop    %rbx
>     0x1022730b:  pop    %rdi
>     0x1022730c:  cmp    %rdi,%rbx
>     0x1022730f:  push   %rdi
>     0x10227310:  jle    0x1022731e
>     0x10227316:  pop    %rdi
>     0x10227317:  mov    %rbx,%rcx
>     0x1022731a:  mov    %rdi,%rbx
>     0x1022731d:  push   %rcx
>     0x1022731e:  epilogue
> 
> Here the top-of-stack is passed across the IF in %RBX, but the second
> stack item, which is in a register at the IF, is pushed back into
> memory, only to be popped in the code right after the IF.  In this
> case the top-of-stack is dropped at the end, so there is no pushing of
> RBX in the end (if you leave the DROP away, there is such a push at
> the end).
> 
> But iForth does not always keep the TOS in EBX across IF:
> 
> : bar if swap then drop ;
> 
>     0x1022738a:  pop    %rbx
>     0x1022738b:  cmp    $0x0,%rbx
>     0x1022738f:  je     0x1022739f
>     0x10227395:  pop    %rbx
>     0x10227396:  pop    %rdi
>     0x10227397:  mov    %rbx,%rcx
>     0x1022739a:  mov    %rdi,%rbx
>     0x1022739d:  push   %rcx
>     0x1022739e:  push   %rbx
>     0x1022739f:  pop    %rbx
> 
> Here we see no push between the cmp and the conditional branch; all
> stack items are in memory across the IF, and the code after the IF has
> to pop both of the items it reads from memory.  Because the stack
> representation has to be the same at the THEN, iForth pushes both
> stack items involved at the end of the block; and the following DROP
> then pops one of them.
> 
> The code for BAR also shows that iForth keeps TOS in RBX right before
> pushing it, so it needs to use the two mov instructions to arrange the
> registers appropriately.  Interestingly, for the second stack item it
> is more flexible, and can push it from a different register than the
> one it popped it into (otherwise a third mov would be needed).
> 
> Let's see if it can keep a return-stack item in a register across
> basic blocks:
> 
> : baz >r if r@ + then r> ;
> 
>     0x1022748a:  pop    %rbx
>     0x1022748b:  pop    %rdi
>     0x1022748c:  cmp    $0x0,%rdi
>     0x10227490:  lea    -0x8(%rbp),%rbp
>     0x10227494:  mov    %rbx,0x0(%rbp)
>     0x10227498:  mov    %rcx,%rbx
>     0x1022749b:  je     0x102274ab
>     0x102274a1:  mov    0x0(%rbp),%rbx
>     0x102274a5:  pop    %rdi
>     0x102274a6:  lea    (%rdi,%rbx,1),%rbx
>     0x102274aa:  push   %rbx
>     0x102274ab:  mov    0x0(%rbp),%rbx
>     0x102274af:  lea    0x8(%rbp),%rbp
>     0x102274b3:  push   %rbx
>    
> So the top of the return stack is not kept in a register across the
> IF, but instead moved into memory, and the return-stack pointer
> updated.  The R@ then copies that return stack item into rbx, and the
> r> also gets the return stack item from memory and updates RBP.
> 
> Bottom line: iForth uses RSP as data-stack pointer, in order to use
> push and pop, but pays for that with definition prologues and
> epilogues.  It keeps everything in memory at definition boundaries,
> but often keeps the TOS in RBX at basic block boundaries; no such
> optimization exists for return-stack items.  Within basic blocks it
> can keep data and return-stack items in registers.
> 
> Overall, iForth is a little bit more sophisticated than VFX by keeping
> return-stack items in registers within basic blocks, with similar
> sophistication elsewhere.  I am not sure if its stack representations
> at definition and basic block boundaries is a good idea; in
> particular, the use of indirect jumps for the returns may result in
> worse branch prediction accuracy for the returns in some cases.
> 
> - anton

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

#135258

On 7/24/2026 8:22 AM, Anton Ertl wrote:
> Paul Curtis has a code generator for his Forth implementation that is
> much more sophisticated than what I have seen on other Forth
> implementations.  He asked me about the other Forth implementations,
> which resulted in me investigating iForth. 
[..]> Now on to iForth (using iForth-5.1-mini, which is quite old; if the
> code generation has changed substantially in the meantime, my results
> may be outdated):
> 
> iForth uses RSP as data-stack pointer, RBP as return-stack pointer,
> and in the canonical representation at definition boundaries all stack
> items are in memory.  iForth disassembles
[..]> - anton

Some comments.

The R-stack is used as the data stack to make the interface to
the OS / C server easier. It is a requirement that Forth can call
C and C can call Forth without too many restrictions.

iForth tokenizes words (when not larger than a certain size).
On definition, words are recursively expanded. This process stops
prematurely when input/output is detected. There is no need to
try and make I/O fast: it is limited by the OS interface anyway.

The fact that a word is present in the kernel ( like "+" ) is no
guarantee that that code is actually used in new words.
The kernel code for "+" has to be there so that it is possible to
use " ' + " interpretively.
The compiler breaks down kernel words to the smallest possible
primitive sequence (i.e. it looks at the type of arguments).

FORTH> : square dup * ;  ' square idis
$01455680  : square
$0145568A  pop           rbx
$0145568B  imul          rbx, rbx
$0145568F  push          rbx
$01455690  ;

FORTH> : ^4 square square ; ' ^4 idis
$01457F00  : ^4
$01457F0A  pop           rbx
$01457F0B  imul          rbx, rbx
$01457F0F  imul          rbx, rbx
$01457F13  push          rbx
$01457F14  ;

FORTH> : test 33 ^4 . ;  ok
FORTH> see test
Flags: ANSI
$01457F80  : test
$01457F8A  push          $00121881 d#
$01457F8F  jmp           .+10 ( $0124A102 ) offset NEAR

FORTH> : ^4+square+33  ^4 square 33 + ; see ^4+square+33
Flags: TOKENIZE, ANSI
: ^4+square+33  [trashed] [trashed] 33 + ;  ok

FORTH> : ttest 33 ^4+square+33 . ; see ttest
Flags: ANSI
$01458040  : ttest
$0145804A  mov           r8, $00000147:747C7122 q#
$01458054  push          r8
$01458056  jmp           .+10 ( $0124A102 ) offset NEAR
$0145805B  ;

A call to a word normally skips the first 10 bytes of the code (the
epilog cancels the intro).
Thus "jmp .+10" means "call ." .

FORTH> 8 VALUE input  : tttest input  ^4+square+33 dup + . ; see tttest
Flags: ANSI
$014588C0  : tttest
$014588CA  mov           rbx, $01458480 qword-offset
$014588D1  imul          rbx, $01458480 qword-offset
$014588D9  imul          rbx, rbx
$014588DD  imul          rbx, rbx
$014588E1  lea           rdi, [rbx #33 +] qword
$014588E5  lea           rax, [rbx #33 +] qword
$014588E9  lea           rbx, [rax rdi*1] qword
$014588ED  push          rbx
$014588EE  jmp           .+10 ( $0124A102 ) offset NEAR
$014588F3  ;

FORTH> : 2in ( a b -- c ) + ;  ok
FORTH> : t1 33 44 2in drop ;  ok
FORTH> : t2 input dup 2in ;  ok

When there are no memory references, sometimes code can be
optimized away completely:

FORTH> see t1
Flags: TOKENIZE, ANSI
: t1  33 44 [trashed] DROP ;  ok
FORTH> ' t1 idis
$01458A00  : t1
$01458A0A  ;

When there *are* memory references, iForth refetches the data as
it could have been changed by a different process or I/O operation.

FORTH> ' t2 idis
$01458A80  : t2
$01458A8A  mov           rbx, $01458480 qword-offset
$01458A91  add           rbx, $01458480 qword-offset
$01458A98  push          rbx
$01458A99  ;

There is no real register analysis. The assembler tries to match
certain patterns for which a nice binary code sequence is known:

FORTH> create ape 1 , 2 , 3 ,  ok
FORTH> : t4 ape swap cells + @ ; ' t4 idis
$014593C0  : t4
$014593CA  pop           rbx
$014593CB  push          [rbx*8 $01458F80 +] qword
$014593D2  ;

FORTH> : t5 t4 drop ; ' t5 idis
$01459440  : t5
$0145944A  pop           rbx
$0145944B  ;

-marcel

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

#135259

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> Paul Curtis has a code generator for his Forth implementation 

Can I ask which implementation that is?  I found him mentioned on a few
Forth-related web pages, but nothing about his compiler.

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

#135260

Paul Rubin <no.email@nospam.invalid> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> Paul Curtis has a code generator for his Forth implementation 
>
>Can I ask which implementation that is?

It is a Forth front end for the compiler back end that his company
SEGGER <https://www.segger.com/> has for their embedded CPUs (the
commercial front ends are apparently for C and C++).  I asked him for
a copy, but the compiler only generates code for their architectures,
which means that most people can only run it (or its output, if it is
a batch compiler) on an emulator, and it is harder to compare to
others.

He asked me whether I would be coming to EuroForth in Cardiff (I
will), so maybe he plans to come there, too and talk about his
compiler.

- 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: https://forth-standard.org/
EuroForth 2026 CFP: http://www.euroforth.org/ef26/cfp.html

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

#135262

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> Paul Curtis has a code generator for his Forth implementation that is
> much more sophisticated than what I have seen on other Forth
> implementations.  He asked me about the other Forth implementations,
> which resulted in me investigating iForth.  And while I am at it,
> here's a review of what I know about the code generators of several
> Forth systems.

There is a contrast with the ciforth approach. I don't do code generation.
I analyse the code afterwards.
Note about the square example, my Forth uses the irregular 64x64 to 128
instruction, following the classic detour with M* .
There is no special knowledge about IMUL|AD , for example
that it overwrite register D , that could be used to remove an
assignment to D.
The following examples are used
: SQUARE DUP * ;
: test3a 4 SQUARE SQUARE ;
: test3b SQUARE SQUARE ;
Note that test3a can be optimised in high level, using folding properties.
Note that this approach is handicapped by IMUL|AD . It is an irregular
instruction, and the optimiser has no knowledge how to handle it.

####################
BEFORE

: test3a    \ square
DUP   *
;
AFTER
DUP
*
test3a

: test3a
DUP   M*   DROP
;
Report about return stack usage
new report

   POP|X,   AX|
   Q:    MOV,   X|   F|   AX'|   R|   BX|
   Q:    IMUL|AD,   X|   R|   BX|
   Q:    XCHG|AX,   DX|
   PUSH|X,   DX|
####################
BEFORE

: test3b
4  SQUARE   SQUARE
;
AFTER
LIT
DUP
*
SQUARE
SQUARE
test3b

: test3b
100
;
Report about return stack usage
new report

   PUSHI|X, 256 IL,

####################
BEFORE

: test3c
SQUARE   SQUARE
;
AFTER
DUP
*
SQUARE
SQUARE
test3c

: test3c
DUP   M*   DROP   DUP   M*   DROP
;
Report about return stack usage
new report

   POP|X,   AX|
    Q:    MOV,   X|   F|   AX'|   R|   BX|
    Q:    IMUL|AD,   X|   R|   BX|
    Q:    XCHG|AX,   DX|                       1}
    Q:    MOV,   X|   F|   DX'|   R|   AX|     1}
    Q:    MOV,   X|   F|   DX'|   R|   BX|
    Q:    IMUL|AD,   X|   R|   BX|
    Q:    XCHG|AX,   DX|                       2}
   PUSH|X,   DX|                               2}

----------------

Obviously 1 can be replaced by
    Q:    MOV,   X|   F|   AX'|   R|   DX|
Obviously 2 can be replaced by
   PUSH|X,   AX|                               2}

Q: is a prefix for 64 bits. X is 16/32/64 hence xell.

Intel is actually a dead end. Too few registers and too irregular.
I'm now working on riscv.

For example the optbb_expand.frt takes care of the following:

\ This file contains uniformisation of the code, so as to minimize the set
\ of instructions the peephole optimiser has to deal with.
\         A replace byte with xell in data and indices
\         B replace short branches with long
\         C replace one byte instruction reg A with regular instruction
\         D replace 32 bit with 64 bits
\         E replace T| R| by F| R|  where possible
\         F get Q: before all pushes and pops.
\         G replace SUB or XOR that zeroes a register by MOVI.
\         H replace register register moves by pushes and pops.

This is before you can get to work! Afterwards you can compress
the code, an equal amount of work.

An example of transformation rules.
"
   \ Replace a byte operand with a xell operand.
   \ This replacement is special because it works for all opcodes.
   <! !Q! XXX, BO| !!T   $00 C, ~!!T !>
   <A Q: ADD, XO| 0 L, !TALLY A>
   {   bufv 1+ L@  $FFFF AND   bufc 1+ OR!U
       bufv 3 + C@   C>S bufc 3 + L! }
   optimisation oprboxo-pattern
"
optimisation is a class. It receives a source pattern with wild
cards, a replace pattern, and a xt to perform the transformation.
The source pattern is matched first.

I succeeded to optimise a return-stack based DO-LOOP to only use
registers, such that the byte sieve approaches vfx forth speed.

For the examples several dozen of code pattern matches are tried,
recursively.

> - anton

--
The glass is half empty. There is no such thing as a free world.
This is the first day of the end of your life.
If you can't beat them, ... too bad.

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

#135269

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> Paul Curtis has a code generator for his Forth implementation that is
> much more sophisticated than what I have seen on other Forth
> implementations.  He asked me about the other Forth implementations,
> which resulted in me investigating iForth.  And while I am at it,
> here's a review of what I know about the code generators of several
> Forth systems.

Maybe of some interst is Poplog code generator.  Poplog is a higher
level system but its code generator is rather close to what is
needed by Forth.  Poplog uses RSP as control stack pointer and
RBX as data stack pointer.  r8, r10, r11, r12, r13, r14 and r15
are used for caller-save local variables.  rbp is used as pointer
to function metadata (this presumably would be not needed by
Forth and could be reused).  rdx is reserved for holding target
access of tail calls. r9 is reserved for temporary 64-bit
constants.  rax, rcx, rsi, rdi are temporary work registers
utilized by code generator.

Logically from higher level point of view code generator suports
only a handful of operations: calls, basic stack operations,
function entry and exit, declarations of local variables.
There are some low hunderds of built in operations that are
expanded inline, so that things like aritmetic do not require
a function call and instead end up as a single machine instruction.

First stage of compiler is responsible for stack tracking and
if possible allocates stack entries to work registers.  This
is not very sophisticated, basicaly intended to forward
result from one operation to the next one without trip via
memory.  However, for code written using local variables it
is quite effective.  Traditional Forth stack juggling is
likely to lead to much worse code because in such case stack
tracking may be unable to follow changes to the stack or
may simply run out of work register to keep stack entries
there.

Updates to data stack pointers are batched so that stright
line sequence of accesses to the data stack leads to a
single update to data stack pointer.  Control flow
including function calls forces syncing of actual data
stack and data stack pointer (registers caching stack
entries are spilled and data stack pointer in made to
point to the top of the data stack).

Overall code generator is rather simple and for low level
source generated code is not great but reasonable.

-- 
                              Waldek Hebisch

[toc] | [prev] | [standalone]

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

csiph-web