Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #135256
| From | Hans Bezemer <the.beez.speaks@gmail.com> |
|---|---|
| Newsgroups | comp.lang.forth |
| Subject | Re: Code generation, in particular for iForth |
| Date | 2026-07-24 16:05 +0200 |
| Organization | A noiseless patient Spider |
| Message-ID | <113vrer$o5hh$1@dont-email.me> (permalink) |
| References | <2026Jul24.082234@mips.complang.tuwien.ac.at> |
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
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web