New optimizations coming in ZILF 0.8

Left: Code generated by ZILF 0.7 (11 instructions).
Right: Code after new optimizations (1 instruction).

How ZILF turns the nasty code on the left into a single instruction, using three new optimizations:

==1==

?L14: BAND STACK,2048 >STACK

BAND STACK,32767 >STACK

ZERO? STACK /?L12

PUSH 1

JUMP ?L13

?L12: PUSH 0

?L13: ZERO? STACK \?L6

PUSH 1

JUMP ?L7

?L6:  PUSH 0

?L7: ZERO? STACK \FALSE

Combine sequential bitwise operations (this is new). BAND STACK,32767 goes away, because 2048 & 32767 == 2048.

==2==

?L14: BAND STACK,2048 >STACK

ZERO? STACK /?L12

PUSH 1

JUMP ?L13

?L12: PUSH 0

?L13: ZERO? STACK \?L6

PUSH 1

JUMP ?L7

?L6: PUSH 0

?L7:  ZERO? STACK \FALSE

Convert single-bit BAND+ZERO? test to BTST (this is new). BAND STACK,2048 >STACK followed by ZERO? STACK /?L12 becomes BTST STACK,2048 \?L12, because 2048 is a power of two.

==3==

?L14: BTST STACK,2048 \?L12

PUSH 1

JUMP ?L13

?L12: PUSH 0

?L13: ZERO? STACK \?L6

PUSH 1

JUMP ?L7

?L6: PUSH 0

?L7:  ZERO? STACK \FALSE

Bypass controlled conditional branch (this is new). PUSH 1 followed by a JUMP to ZERO? STACK \?L6 becomes JUMP ?L6, because we know the negative ZERO? branch will be taken.

==4==

?L14: BTST STACK,2048 \?L12

JUMP ?L6

JUMP ?L13

?L12: PUSH 0

?L13: ZERO? STACK \?L6

PUSH 1

JUMP ?L7

?L6:  PUSH 0

?L7:  ZERO? STACK \FALSE

Bypass controlled conditional branch. PUSH 0 followed by ZERO? STACK \?L6 becomes a JUMP to the new ?L15 (the instruction after ZERO?), because we know the negative branch won't be taken.

==5==

?L14: BTST STACK,2048 \?L12

JUMP ?L6

JUMP ?L13

?L12: JUMP ?L15

?L13: ZERO? STACK \?L6

?L15: PUSH 1

JUMP ?L7

?L6: PUSH 0

?L7: ZERO? STACK \FALSE

Bypass controlled conditional branch. PUSH 1 followed by a JUMP to ZERO? STACK \FALSE becomes RFALSE, because we know the negative branch will be taken.

==6==

?L14: BTST STACK,2048 \?L12

JUMP ?L6

JUMP ?L13

?L12: JUMP ?L15

?L13: ZERO? STACK \?L6

?L15: RFALSE

JUMP ?L7

?L6: PUSH 0

?L7: ZERO? STACK \FALSE

Bypass controlled conditional branch. PUSH 0 followed by ZERO? STACK \FALSE becomes a JUMP to the new ?L16, because we know the negative branch won't be taken.

==7==

?L14: BTST STACK,2048 \?L12

JUMP ?L6

JUMP ?L13

?L12: JUMP ?L15

?L13: ZERO? STACK \?L6

?L15: RFALSE

JUMP ?L7

?L6: JUMP ?L16

?L7: ZERO? STACK \FALSE

?L16: ...

Eliminate dead code and unused labels.

==8==

?L14: BTST STACK,2048 \?L12

JUMP ?L6

?L12: JUMP ?L15

?L15: RFALSE

?L6:  JUMP ?L16

ZERO? STACK \FALSE

?L16: ...

Eliminate branch to next instruction. JUMP ?L15 goes away; ?L15 merges with ?L12.

==9==

?L14: BTST STACK,2048 \?L12

JUMP ?L6

?L12: RFALSE

?L6: JUMP ?L16

ZERO? STACK \FALSE

?L16: ...

Disintermediate branch. BTST STACK,2048 \?L12 becomes BTST STACK,2048 \FALSE, because the instruction at ?L12 is RFALSE.

==10==

?L14: BTST STACK,2048 \FALSE

JUMP ?L6

?L12: RFALSE

?L6: JUMP ?L16

ZERO? STACK \FALSE

?L16: ...

Disintermediate branch. JUMP ?L6 becomes JUMP ?L16, because the instruction at ?L6 is JUMP ?L16.

==11==

?L14: BTST STACK,2048 \FALSE

JUMP ?L16

?L12: RFALSE

?L6: JUMP ?L16

ZERO? STACK \FALSE

?L16: ...

Eliminate dead code and unused labels.

==12==

?L14: BTST STACK,2048 \FALSE

JUMP ?L16

?L16: ...

Eliminate branch to next instruction. JUMP ?L16 goes away.

==13==

?L14: BTST STACK,2048 \FALSE

Generating better code in ZILF 0.5

I've done a lot of work on the code generator and optimizer for the upcoming version of ZILF. Here's one example of how the generated code has been improved.

Parser.zil has a routine called TAKE-CONT-SEARCH, which helps V-TAKE determine whether the object being taken is in a container:

<ROUTINE TAKE-CONT-SEARCH (A "AUX" H)  
    <OBJECTLOOP I .A
        <COND (<OR <FSET? .I ,CONTBIT> <==? .I ,WINNER>>
                <COND (<IN? ,PRSO .I>
                        <SET H .I>
                        <RETURN>)
                    (ELSE
                        <SET H <TAKE-CONT-SEARCH .I>>
                        <AND .H <RETURN>>)>)>>
    <AND .H <RETURN .H>>>

In ZILF 0.4, that turned into 14 instructions:

      .FUNCT TAKE-CONT-SEARCH,A,H,I FIRST? A >I /?L1 ?L1: ZERO? I /?L3 FSET? I,CONTBIT /?L8 EQUAL? I,WINNER \?L12 ?L8: IN? PRSO,I \?L9 SET 'H,I JUMP ?L3 ?L9: CALL TAKE-CONT-SEARCH,I >H ZERO? H \?L3 ?L12: NEXT? I >I /?L1 JUMP ?L1 ?L3: ZERO? H \?L18 RETURN H ?L18: RETURN H 

In ZILF 0.5, it's only 11 after eliminating a ZERO?, a JUMP, and the duplicate RETURN:

.FUNCT TAKE-CONT-SEARCH,A,H,I
FIRST? A >I \?L3
?L19: FSET? I,CONTBIT /?L8
EQUAL? I,WINNER \?L12
?L8: IN? PRSO,I \?L9
SET 'H,I
JUMP ?L3
?L9: CALL TAKE-CONT-SEARCH,I >H
ZERO? H \?L18
?L12: NEXT? I >I /?L19
?L3: ZERO? H /FALSE
?L18: RETURN H

Here's another example. The REFERS? routine checks whether a noun, or adjective-noun pair, matches the vocabulary of some object:

<ROUTINE REFERS? (A N O)
    <AND <OR <0? .A> <IN-PB/WTBL? .O ,P?ADJECTIVE .A>>
         <IN-PWTBL? .O ,P?SYNONYM .N>>>

The ZIL code is pretty simple, but ZILF 0.4 handled it poorly, needing 12 instructions and a temporary variable:

.FUNCT REFERS?,A,N,O,?TMP
ZERO? A /?L5
PUSH 0
JUMP ?L6
?L5: PUSH 1
?L6: POP '?TMP
ZERO? ?TMP /?L4
PUSH ?TMP
JUMP ?L3
?L4: CALL IN-PBTBL?,O,P?ADJECTIVE,A >STACK
?L3: ZERO? STACK /FALSE
CALL IN-PWTBL?,O,P?SYNONYM,N >STACK
RSTACK

Nasty! ZILF 0.5 does it in five instructions, eliminating the temp variable and a whole lot of nonsense:

.FUNCT REFERS?,A,N,O
ZERO? A /?L2
CALL IN-PBTBL?,O,P?ADJECTIVE,A >STACK
ZERO? STACK /FALSE
?L2: CALL IN-PWTBL?,O,P?SYNONYM,N >STACK
RSTACK

Much of the benefit comes from better understanding the relationship between values and conditions, such as knowing when a value is immediately going to be tested against zero, or which branch instructions are testing conditions that have already been tested. The Cloak example is smaller by more than 200 bytes thanks to these optimizations.

Branch optimization in ZAPF

I recently moved some unfinished changes from ZAPF's trunk into a development branch. Some have asked what these changes are all about, anyway, so here's an explanation.

The Z-machine's branch instructions, of which there are many, can take an offset in either "long" or "short" form. Long form takes two bytes and can hold any signed 14 bit offset, whereas short form takes one byte but can only hold an unsigned 6 bit offset. In order to save space, we always want to use the short form wherever possible: that is, whenever an instruction branches forward by up to 61 bytes. (Not 63: these offsets are biased by +2.)

But branching forward means we encounter the branch instruction before its target label, so how do we know how far it's branching? It's not easy, especially if there are other branch instructions in between this one and its target -- we can't know the true distance until we know what form those will be assembled in.

ZAPF's current approach is to make repeated passes over each function until all the label positions are discovered. When it sees a branch instruction targeting a label that hasn't been defined yet, it remembers the name of that label, then assembles the branch in long mode. Once the label's definition is encountered, ZAPF remembers its location and rewinds to the beginning of the function.

The next time it encounters the branch instruction, it can make a better judgment of the distance, which may allow it to use short mode. The next time it encounters the label definition, it compares the new location to the old location; if it has changed, it remembers the new position and rewinds again. It only reaches the end of the function once every label's final location has been discovered and every branch has been assembled correctly.

Unfortunately, this approach doesn't always work. Some inputs cause ZAPF to get stuck in a function and never reach the end. I haven't investigated too thoroughly because the algorithm is hard to reason about, inefficient, and silly enough that I decided to just rewrite it.

I found an interesting replacement algorithm in a 1978 paper by Thomas G. Szymanski called "Assembling Code for Machines with Span-Dependent Instructions". The paper proves that minimizing program length is NP-complete in the general case, when branch targets are allowed to be specified as arbitrary expressions of constants and labels, but presents an efficient algorithm for a restricted subset of expressions -- which works just fine for ZAPF.

The algorithm works by assuming in a first pass that all instructions can be assembled in short form, and remembering the location of every label and every branch instruction, then studying them after that pass to trace the dependencies between branch instructions, and forcing into long mode only the instructions that need it. The label locations are adjusted -- advanced forward by one byte for every preceding branch that was changed from short to long -- and the set of adjusted locations is used in a second pass to assemble each branch in the correct mode.

There's one more complication, though: the Z-machine's packed address system. Every routine must begin at an address divisible by 2, 4, or 8 (depending on the Z-code version), so there are usually a few padding bytes between routines. The algorithm works on all labels in the game at once, but because of the padding issue, forcing a branch into long mode doesn't actually push every following label ahead by one byte: for labels in subsequent routines, it's either zero bytes (when the extra byte can be absorbed by the next padding section) or 2/4/8 bytes (when it can't). And that's the part that isn't finished yet.