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