website statistics

Forth loop inversionΒΆ

A “while” loop in C:

while (condition)
  body();

has the Forth equivalent:

begin
    condition
while
    body
repeat

This compiles as a loop with two jumps the the body. The first jump is the conditional forward branch, and the second is the unconditional backwards branch. So for a hypothetical CPU we might get this instruction sequence from the Forth compiler:

L_0:
    call    condition
    jz      L_1
    call    body
    jmp     L_0
L_1:

As any experienced assembly-language programmer will tell you, this is functionally identical to:

    jmp     L_0
L_1:
    call    body
L_0:
    call    condition
    jnz     L_1

This version is the same size, but executes one fewer instruction for each loop iteration. This is a variation on Loop inversion, differing because it avoids duplicating the condition. The only disadvantage is that the case where the condition is always false executes one more instruction.

So how do we persuade the Forth compiler to generate code like this?

Fortunately, the building blocks are already available in ANS Forth. This loop:

begin
    body
    condition
until

is already quite close to what we want – we just need to add an extra forward jump before the begin. Here is a first version:

: count-to-5
    0
    ahead                   \ unconditional forward jump
    begin
        dup . 1+
        [ 1 cs-roll ] then  \ resolve the forward jump
        dup 6 =
    until
;

count-to-5
0 1 2 3 4 5

The [ 1 cs-roll ] swaps the two outstanding unresolved references, and then resolves the forward jump from the preceding ahead. With a couple of helpful words, we can now write inverted loops:

: iwhile
    postpone ahead
    postpone begin
; immediate

: condition
    1 cs-roll
    postpone then
; immediate

: count-to-5
    0
    iwhile
        dup . 1+
    condition
        dup 6 =
    until
;

count-to-5
0 1 2 3 4 5

Compiling this code with VFX Forth (an optimizing native Forth for x86) gives the inverted while loop, exactly as intended:

( 080B9DB6    BB00000000 )            MOV       EBX, 00000000
( 080B9DBB    E90C000000 )            JMP       080B9DCC
( 080B9DC0    8D6DFC )                LEA       EBP, [EBP+-04]
( 080B9DC3    895D00 )                MOV       [EBP], EBX
( 080B9DC6    E8DD8EF9FF )            CALL      08052CA8        .
( 080B9DCB    43 )                    INC       EBX
( 080B9DCC    83FB06 )                CMP       EBX, 06
( 080B9DCF    75EF )                  JNZ/NE    080B9DC0