Saturday, May 31, 2014

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.

No comments:

Post a Comment