Monday, November 30, 2015

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