Hit the Ceiling – Going Virtual

End April i hit the ceiling. I'm very tall, but that's not the reason – the code size for the z80 system reached 32 kBytes.
I was working on the file system and when it was in a state where it compiled – just half way done – the resulting rom size was only a tiny amount below 32 kB.

So what could i do?

I could remove all test code, and then i could use z88dk which allegedly creates slightly smaller code, but that would probably not really help: I'd just die later.

I could write everything in assembler.

Or i could finish the z80 backend for Vcc, my 'virtual code compiler'.

I couldn't decide on whether to create real z80 code or virtual code for a Forth-style interpreter. So i implemented them both, mostly. While programming i made some measurements.

Compare virtual code with native z80 code, running the opcode test program:

                virtual code    z80 code
total rom size  10935           11455 bytes
= code blob     5811            4428 bytes  
+ test code     5128            7027 bytes
time            3.630s          2.376s

In this not representative program the z80 code is 37% bigger and 35% faster than virtual code. (The 'code blob' is the support library; 'test code' is what grows.)

I have also compiled my serial driver in various versions.

sdcc                1974 bytes
Vcc z80 code        1520 bytes
Vcc virtual code    1169 bytes

The z80 code generated by Vcc is 23% shorter than that of sdcc, and the virtual code is even 40% shorter than sdcc z80 code or 23% shorter than Vcc z80 code.

When i worked on the z80 backend, i was a little bit frustrated about the little amount of code size reduction i could achieve, though i used all 'illegal' tricks, e.g. i use the RST opcodes for the most frequent building blocks to reduce code size.

The code shrink of approx. 25% is simply not enough, because it does not take into account the size of the static support code blob. This is currently at 4428 bytes and i expect a final size of around 8 kB, after adding all int32 code and if i leave out floating point. That is 25% of the rom size of 32 kB. So before i actually save space, the code size must be reduced by at least 25%. And this looks like the maximum i can achieve with my z80 backend. (though 'nothing saved' is only true for code in rom. Any program loaded into ram will see the full size reduction. And i neglect that sdcc pulls in some library code as well…)

The code shrink of 40% of the virtual code version looks much better, though it will have a slightly larger support code blob. And it will come at a price: Speed…

Before i go into details here a comparison of the compiler outputs of a simple function:

Vcc:

uint8 avail_out(SerialDevice¢ channel) 
{ 
    return obusz - (channel.obuwi-channel.oburi); 
}

C:

uint8 sio_avail_out(SerialDevice* channel) 
{ 
    return obusz - (channel->obuwi - channel->oburi); 
}

This function determines how many free space is left in a sio output buffer. The Vcc function is a member function. 'channel' is a struct, 'obuwi' = output buffer write index, 'oburi' = output buffer read index, 'obusz' = output buffer size. I hope you get it.

sdcc: In the case of such a short function, sdcc creates very good code. But don't be fooled: if it can no longer keep everything in registers, the code becomes ugly… So this is actually not a representative example for sdcc. [25 bytes total]

_sio_avail_out::
    pop    de            ; return address
    pop    bc            ; 'channel'
    push   bc            ; everything back:
    push   de            ;     caller is responsible for cleaning up the stack…
    push   bc
    pop    iy            ; iy = 'channel'
    ld     e,15 (iy)
    ld     l, c          ; superfluous
    ld     h, b          ; superfluous
    ld     bc, #0x0010   ; load into hl instead
    add    hl, bc
    ld     c,(hl)
    ld     a,e
    sub    a, c
    ld     c,a
    ld     a,#0x40
    sub    a, c
    ld     l,a
    ret

hand-coded assembler: This is for the Vcc memory model with 'handles', so i must dereference a pointer to a pointer to the struct data. And as i see by the last instruction, it's for the virtual code machine: [19 bytes total]

sio_avail_out::          ; in: de -> -> channel    
    ex     hl,de         ; hl -> -> channel
    ld     e,(hl)
    inc    hl
    ld     d,(hl)        ; de -> channel
    ld     a,obusz       ; a=obusz
    ld     hl,obuwi
    add    hl,de         ; hl -> channel.obuwi
    sub    a,(hl)        ; a=obusz-obuwi
    inc    hl            ; hl -> oburi
    add    a,(hl)        ; a=obusz-obuwi+oburi
    ld     e,a
    ld     d,0           ; out: de = return value
    jp     next          ; jump to next opcode

Z80 code created by Vcc. It's an early state and there are some optimizations left. It looks poor when compared with the sdcc generated code, but as already said, things become different for functions with more than one line of code. Then this code is still representative but sdcc looks poor too. The first line is a program label, though a little bit longish. :-) But if you compare it with the function's signature then it hopefully makes sense. [total 36 bytes]

SerialDevice.avail_out__12SerialDeviceC_5uint8:
    pop     hl           ; move the return address to the VM's return stack
    call    pushr_hl    
    rst     ivalu8       ; push obusz: 'ivalu8' = immediate uint8 value
    db      64
    push    de
    ld      l,2+2        ; get local variable 'channel'
    rst     lget         ;    'lget' = get local variable
    ld      hl,15        ; get item 'obuwi' at offset 15
    rst     igetu8       ;    'igetu8' = get uint8 struct item
    push    de        
    ld      l,4+2        ; get local variable 'channel'
    rst     lget    
    ld      hl,16        ; get item 'oburi' at offset 16
    rst     igetu8
    pop     hl        
    and     a            ; subtract obuwi - oburi
    sbc     hl,de
    ex      hl,de
    pop     hl
    and     a            ; subtract obusz - (obuwi - oburi)
    sbc     hl,de
    ex      hl,de    
    pop     af           ; discard 2nd value on stack (the 'channel') 
    jp      return       ; get back the return address and return

Virtual code created by Vcc with minimum optimization: [29 bytes total]

SerialDevice.avail_out__12SerialDeviceC_5uint8:
    rst  p_enter         ; the proc is entered in z80 code: switch to virtual code
    dw   IVAL, 64        ; push obusz
    dw   LGET            ; get local variable 'channel'
    db   2
    dw   IGETu8          ; get item 'obuwi' at offset 15
    db   15
    dw   LGET            ; get local variable 'channel'
    db   4
    dw   IGETu8          ; get item 'oburi' at offset 16
    db   16
    dw   SUB             ; subtract obuwi - oburi
    dw   SUB             ; subtract obusz - (obuwi - oburi)
    dw   TOR             ; nip 2nd value on stack (the 'channel') 
    dw   DROP            ;     by temporarily moving the top value to the return stack
    dw   FROMR           ;    and droping the 'channel'
    dw   RETURN

Virtual code created by Vcc after proper optimization: [20 bytes total]

SerialDevice.avail_out__12SerialDeviceC_5uint8:
    rst  p_enter
    dw   IVALu8          ; uint8 opcode with 1-byte argument
    db   64
    dw   OVER            ; instead of LGET 2
    dw   IGETu8        
    db   15
    dw   OVER2           ; instead of LGET 4
    dw   IGETu8
    db   16
    dw   SUB
    dw   SUB
    dw   NIP0RETURN - 1  ; nip one value (the 'channel') and return

One astonishing difference between z80 code and virtual code is: optimization.

When you optimize z80 code, the following equation is true:

codesize = speed

The bigger your code, the higher the speed. Every effort to increase speed results in bigger code.

When you optimize virtual code, this equation is true:

codesize = 1 / speed

Whenever you reduce code size, the speed goes up. This is because the standard method to optimize virtual code is to create 'combi opcodes' for frequently occurring opcode pairs, which eliminates one opcode fetch. As a result it is much more fun to optimize virtual code because you are rewarded twice. :-) Though caveat: the size of the support code blob grows! :-(