6 ms·

As others have pointed out, Apple Pascal was a bytecode interpreter, not compiled to native 6502 code. Even worse, the bytecode was standard UCSD Pascal, desig

As others have pointed out, Apple Pascal was a bytecode interpreter, not compiled to native 6502 code. Even worse, the bytecode was standard UCSD Pascal, designed for mainframes, and not really how you'd design bytecode if you knew you were going to implement it on a 6502. We can actually compile Pascal / C style languages to the 6502 pretty well these days. The way to do it is treat it the same as a RISC machine with a lot of registers (let's say 32 2-byte pairs in zero page, leaving 75% of ZP for globals and a handful of important runtime functions that benefit from self-modifying code). Split the 32 pseudo-registers up into A, S, T registers the same as you do for any RISC (or x86_64 for that matter). It's problem to handle recursion. Just the same as any function call, put anything you still want after the function call into S registers, and in the called function if it needs to use S registers then it needs to save them on a stack (NOT the 256 byte hardware stack) first and restore them after. For more than one or two saved registers it's better to use a runtime function for this -- 12 cycles overhead, but lots of bytes of code saved. RISC-V's -msave-restore provides a good model for this. You can make a nice set of 2-address arithmetic routines between 16 or 32 bit Zero-Page registers by using the X and Y registers to pass which locations to work on. add16: clc lda 0,x adc 0,y sta 0,x lda 1,x adc 1,y sta 1,x ret ... ldx #dst ldy #src jsr add16 This reduces the call site from 13 bytes to 7 bytes (and you can often reuse an X or Y), while increasing the execution time for an inline add from 20 cycles to 42 (1 cycle extra per instruction for the indexed addressing = 6, 4 cycles for loading X and Y, 12 cycles for the jsr/ret) For 32 bit arithmetic the time overhead is much reduced. For floating point it would be negligable! There is no convenient way to make 3-address routines, but `mov16` is only 5 instructions and 28 cycles. Or just 4 instructions (8 bytes) and 12 cycles if inlined, which might be a better tradeoff i.e. lda src1 sta dst lda src1+1 sta dst+1 ldx #dst ldx #src2 jsr add16 vs ldx #dst ldy #src1 jsr mov16 ldy #src2 jsr add16 Stack-based 6502 code is both bigger and slower than (pseudo) register-based code -- a zero-argument `jsr add16` itself is smaller, but it's significantly slower, and loading and storing values between stack and somewhere else will be much more code and much slower. Stack-based bytecode has a whole lot more overhead again to fetch the next instruction and dispatch to the correct code for it. Register-based bytecode would be a much better idea, as it uses several times fewer bytecode instructions, and is more compact to boot (see Dalvik vs JVM ... sad that webasm didn't pay attention).

kragen 1y ago
Typically I've found that stack-based bytecode uses about twice as many instructions as register-based bytecode but significantly less space. (I'm sorry that's kind of handwavy; I'd be delighted to see a more rigorous study of the question.) For Wasm I don't think the number of instructions was a concern, since that only affects the time to "load" it by compiling to native code, but size seems to have been a primary concern. I agree about the general approach to taking advantage of the zero page, but I don't have the 6502 competency to comment on your proposed instruction sequences.
- brucehoult 1y ago
  > stack-based bytecode uses about twice as many instructions as register-based bytecode but significantly less space That's not my experience, and I don't see how it can be true, even theoretically, for typical programs. I don't at all mind more instructions, if that works out smaller or at least not bigger. E.g. RISC-V using `c.slli; c.srli` or `c.slli; c.srai` (all 2-byte opcodes) to extract unsigned or signed bitfields instead of having a 4-byte "extract field" instruction. It is true that a stack-based ISA can have a size advantage in evaluating very complex expressions, such as those typical in scientific / engineering computing, when you get a lot of arithmetic operators in a row with no arguments needed. But in general purpose programs the vast majority of lines of C code have only very simple expressions. `x=x+y`. `x=x+10`. `if x<y`. Register ISAs provide short addressing for the most frequently-used 8 or 16 or 32 variables in a function (the registers). Experience shows 8 isn't really enough, 32 is usually a little more than you need -- I think some study showed 24 was enough but you don't get a code size advantage from that, so ... Stack based ISAs do similarly. JVM can load or store any of four local variables within a 1-byte instruction. For more than than you can refer to 256 variables with a 2-byte instruction. Four really isn't enough, but 256 is a waste of code size. WASM doesn't have any option to include a variable number in the main opcode byte -- `local.get 1` is two bytes. A very typical statement in programs is `x += y`. JVM 4 bytes: iload 0 // 1A iload 1 // 1B iadd // 60 istore 0 // 3B If x and y aren't in the first 4 locals then it's 7 bytes WASM 7 bytes: (local.get 0) // 20 00 (local.get 1) // 20 01 (i32.add) // 6A (local.set 0) // 21 00 ARMv7 / ARMv6-M / ARMv4T 2 bytes: add r0, r0, r1 // 08 44 RISC-V with C extension 2 bytes: add a0, a0, a1 // 2E 95 The Arm example works with 16 local variables (only the most common operations MOV, ADD, and CMP can use all 16 registers, other operations can only use 8), the RISC-V example works with all 32 registers (again only C.MV, C.ADD, C.ADDI, C.SLLI work with all 32 registers, other 2-byte opcodes use only 8). 8086, M68k, PDP-11, Super-H, MSP430 can all also do this very common operation with a 2-byte instruction, with anything from 8 to 16 local variables. Exactly the same analysis applies to `x += 10`. Most programs consist almost entirely of statements like these, not things like `det = a(ei − fh) − b(di − fg) + c(dh − e*g)` There are two main problems with stack code: - you need four opcodes: `load`, `load`, `add`, `store`. Each opcode needs at minimum 3 or 4 bits, so no matter what you do you're going to have 12-16 bits to specify four actions. In contrast, the register machine can just use a single `add` opcode, again using 3 or 4 bits. - all the common stack ISAs use a minimum of 8 bits for an instruction (even the extremely common `iadd` or `i32.add` and use a multiple of 8 bits for every instruction. Four instructions is going to be minimum 4 bytes. - the register machine needs only one 3 or 4 bit opcode for `add` AND can pack the other operands arbitrarily into a 16-bit instruction, using whatever field size and position makes sense. - the register machine needs to mention the dst/rs1 variable only once. Stack machine code could be improved in size a little if you bit-packed the instructions, but you'll still have the problems of needing more opcode fields and needing to repeat variable names. Perhaps ironically, some accumulator machines do better. For example the much-hated PIC microcontroller actually does this well: MOVF 0x21, W ; Load y (from address 0x21) into W register ADDWF 0x20, F ; Add W (containing y) to x (at address 0x20), store result in x Instructions such as ADDWF have a bit to specify whether to put the result of the add into W (the accumulator) or the source register. On the smaller chips each of those instructions is 12 bits (with 32 registers, many with special purposes), though those are very limited and most applications use mid-range chips with 14 bit instructions (allowing 128 directly accessible registers). So this is 24 or 28 bits of code, still not as compact as the 16 bits for that extensive list of register machines: RISC-V, Arm Thumb, 8086, M68k, PDP-11, Super-H, MSP430.

kragen 1y ago

Typically I've found that stack-based bytecode uses about twice as many instructions as register-based bytecode but significantly less space. (I'm sorry that's kind of handwavy; I'd be delighted to see a more rigorous study of the question.) For Wasm I don't think the number of instructions was a concern, since that only affects the time to "load" it by compiling to native code, but size seems to have been a primary concern. I agree about the general approach to taking advantage of the zero page, but I don't have the 6502 competency to comment on your proposed instruction sequences.

brucehoult 1y ago
> stack-based bytecode uses about twice as many instructions as register-based bytecode but significantly less space That's not my experience, and I don't see how it can be true, even theoretically, for typical programs. I don't at all mind more instructions, if that works out smaller or at least not bigger. E.g. RISC-V using `c.slli; c.srli` or `c.slli; c.srai` (all 2-byte opcodes) to extract unsigned or signed bitfields instead of having a 4-byte "extract field" instruction. It is true that a stack-based ISA can have a size advantage in evaluating very complex expressions, such as those typical in scientific / engineering computing, when you get a lot of arithmetic operators in a row with no arguments needed. But in general purpose programs the vast majority of lines of C code have only very simple expressions. `x=x+y`. `x=x+10`. `if x<y`. Register ISAs provide short addressing for the most frequently-used 8 or 16 or 32 variables in a function (the registers). Experience shows 8 isn't really enough, 32 is usually a little more than you need -- I think some study showed 24 was enough but you don't get a code size advantage from that, so ... Stack based ISAs do similarly. JVM can load or store any of four local variables within a 1-byte instruction. For more than than you can refer to 256 variables with a 2-byte instruction. Four really isn't enough, but 256 is a waste of code size. WASM doesn't have any option to include a variable number in the main opcode byte -- `local.get 1` is two bytes. A very typical statement in programs is `x += y`. JVM 4 bytes: iload 0 // 1A iload 1 // 1B iadd // 60 istore 0 // 3B If x and y aren't in the first 4 locals then it's 7 bytes WASM 7 bytes: (local.get 0) // 20 00 (local.get 1) // 20 01 (i32.add) // 6A (local.set 0) // 21 00 ARMv7 / ARMv6-M / ARMv4T 2 bytes: add r0, r0, r1 // 08 44 RISC-V with C extension 2 bytes: add a0, a0, a1 // 2E 95 The Arm example works with 16 local variables (only the most common operations MOV, ADD, and CMP can use all 16 registers, other operations can only use 8), the RISC-V example works with all 32 registers (again only C.MV, C.ADD, C.ADDI, C.SLLI work with all 32 registers, other 2-byte opcodes use only 8). 8086, M68k, PDP-11, Super-H, MSP430 can all also do this very common operation with a 2-byte instruction, with anything from 8 to 16 local variables. Exactly the same analysis applies to `x += 10`. Most programs consist almost entirely of statements like these, not things like `det = a(ei − fh) − b(di − fg) + c(dh − e*g)` There are two main problems with stack code: - you need four opcodes: `load`, `load`, `add`, `store`. Each opcode needs at minimum 3 or 4 bits, so no matter what you do you're going to have 12-16 bits to specify four actions. In contrast, the register machine can just use a single `add` opcode, again using 3 or 4 bits. - all the common stack ISAs use a minimum of 8 bits for an instruction (even the extremely common `iadd` or `i32.add` and use a multiple of 8 bits for every instruction. Four instructions is going to be minimum 4 bytes. - the register machine needs only one 3 or 4 bit opcode for `add` AND can pack the other operands arbitrarily into a 16-bit instruction, using whatever field size and position makes sense. - the register machine needs to mention the dst/rs1 variable only once. Stack machine code could be improved in size a little if you bit-packed the instructions, but you'll still have the problems of needing more opcode fields and needing to repeat variable names. Perhaps ironically, some accumulator machines do better. For example the much-hated PIC microcontroller actually does this well: MOVF 0x21, W ; Load y (from address 0x21) into W register ADDWF 0x20, F ; Add W (containing y) to x (at address 0x20), store result in x Instructions such as ADDWF have a bit to specify whether to put the result of the add into W (the accumulator) or the source register. On the smaller chips each of those instructions is 12 bits (with 32 registers, many with special purposes), though those are very limited and most applications use mid-range chips with 14 bit instructions (allowing 128 directly accessible registers). So this is 24 or 28 bits of code, still not as compact as the 16 bits for that extensive list of register machines: RISC-V, Arm Thumb, 8086, M68k, PDP-11, Super-H, MSP430.