4 ms·

A few years ago a YouTube video about the movfuscator set me wondering about just how minimalist an instruction set could be without hurting code density (unsur

A few years ago a YouTube video about the movfuscator set me wondering about just how minimalist an instruction set could be without hurting code density (unsurprisingly programming with just MOVs yields spectacularly bad code density!) - and ultimately led to me embarking on my own toy CPU project!

retrac 4y ago
Some one-instruction machines are surprisingly code-efficient. Consider an instruction with four fields: A B C D. Words and addresses are normal two's-complement integers. Every cycle, the machine takes the value at address A, subtracts the value at address B, and stores it in address C. If the result of this, as a signed integer, is 0 or negative, it jumps to address D. Otherwise it take the next instruction. Using temporary values in RAM, self-modifying code and some constants, everything can be implemented with this single instruction. And a lot of it surprisingly efficiently. Some assembly-style syntax for such a machine: A B C D #0 #0 tmp destination Jump to destination. 0 - 0 = 0, so jump to D. The # is syntactic sugar for an immediate literal. The value is placed in an address and that address is used. Tmp is a memory address, a temporary scratch value. In my made-up syntax here this is implicit if there's no 4th field given: // move is simple src #0 dst // subtract srca srcb dst // negate #0 src dst Addition is an exercise left for the reader :) Let's use * as the current address in the program, known at compile/assembly time. We can do a cheap subroutine call: #0 (*+3) retaddress subroutine Negative of the return address of the next instruction is in retaddress. Result will always be negative for sensible addresses, so jump to subroutine. To return, just write the negative again back to the D field of an instruction: #0 retaddress (*+5) #0 #0 tmp tmp // last field will now have return address, jump Of course, writing self-modifying code without checking it is guaranteed to not work. I probably got the offsets and stuff wrong. But hopefully it gives the idea. Doing the same with the address fields lets you do arbitrary indirection and address calls and make a stack. Often 2 - 5 instructions. Everything a typical RISC machine can do can be done in 1 - 30 instructions. Except multiply, divide, and bitwise boolean operations on the whole word, because you have test and branch on each bit in an inconvenient way. I'm sure something more efficient is possible, but it's quite an improvement on the classic subleq code density. One-instruction set computer: https://esolangs.org/wiki/OISC https://esolangs.org/wiki/OISC
klelatti 4y ago
That’s a really interesting question (on code density) - can you share your conclusions or even your project?
- robinsonb5 4y ago
  The project was this: http://retroramblings.net/?page_id=1339 http://retroramblings.net/?page_id=1339 I ended up using a fixed instruction width of 8 bits, with eight classical registers (one of which is the program counter), and also a "temp" register which is used implicitly for opcodes which need a second operand. The code density is comparable to m68k and x86, better than 32-bit RISC ISAs, but not as good as the 16-bit compressed representations of 32-bit RISC ISAs.
  - klelatti 4y ago
    Thanks so much! Looks like a really great project. I'll have a full look through the blog later but just the summary of the code density results is very interesting (at http://retroramblings.net/?p=1414 http://retroramblings.net/?p=1414). Do you have a gut feel for what is happening here and why the compressed 32 RISC ISAs do so well compared to yours?
    - robinsonb5 4y ago
      I think there are three reasons: one is that the code my compiler backend produces is "ok" but not fantastic (though it's somewhat better now than it was when that article was written) - another is that I have only 8 registers, and only five are available for the code generator to play with, so I have to spill registers onto the stack sooner than more register-rich ISAs - and finally my simplistic 8-bit instructions don't do as much as a RISC ISA's 16-bit instructions, so some of the advantage of them being only a single byte is lost.
      - klelatti 4y ago
        That makes a lot of sense. Thanks again for sharing such an interesting project.

retrac 4y ago

Some one-instruction machines are surprisingly code-efficient. Consider an instruction with four fields: A B C D. Words and addresses are normal two's-complement integers. Every cycle, the machine takes the value at address A, subtracts the value at address B, and stores it in address C. If the result of this, as a signed integer, is 0 or negative, it jumps to address D. Otherwise it take the next instruction. Using temporary values in RAM, self-modifying code and some constants, everything can be implemented with this single instruction. And a lot of it surprisingly efficiently. Some assembly-style syntax for such a machine: A B C D #0 #0 tmp destination Jump to destination. 0 - 0 = 0, so jump to D. The # is syntactic sugar for an immediate literal. The value is placed in an address and that address is used. Tmp is a memory address, a temporary scratch value. In my made-up syntax here this is implicit if there's no 4th field given: // move is simple src #0 dst // subtract srca srcb dst // negate #0 src dst Addition is an exercise left for the reader :) Let's use * as the current address in the program, known at compile/assembly time. We can do a cheap subroutine call: #0 (*+3) retaddress subroutine Negative of the return address of the next instruction is in retaddress. Result will always be negative for sensible addresses, so jump to subroutine. To return, just write the negative again back to the D field of an instruction: #0 retaddress (*+5) #0 #0 tmp tmp // last field will now have return address, jump Of course, writing self-modifying code without checking it is guaranteed to not work. I probably got the offsets and stuff wrong. But hopefully it gives the idea. Doing the same with the address fields lets you do arbitrary indirection and address calls and make a stack. Often 2 - 5 instructions. Everything a typical RISC machine can do can be done in 1 - 30 instructions. Except multiply, divide, and bitwise boolean operations on the whole word, because you have test and branch on each bit in an inconvenient way. I'm sure something more efficient is possible, but it's quite an improvement on the classic subleq code density. One-instruction set computer: https://esolangs.org/wiki/OISC https://esolangs.org/wiki/OISC

klelatti 4y ago

That’s a really interesting question (on code density) - can you share your conclusions or even your project?

robinsonb5 4y ago
The project was this: http://retroramblings.net/?page_id=1339 http://retroramblings.net/?page_id=1339 I ended up using a fixed instruction width of 8 bits, with eight classical registers (one of which is the program counter), and also a "temp" register which is used implicitly for opcodes which need a second operand. The code density is comparable to m68k and x86, better than 32-bit RISC ISAs, but not as good as the 16-bit compressed representations of 32-bit RISC ISAs.
- klelatti 4y ago
  Thanks so much! Looks like a really great project. I'll have a full look through the blog later but just the summary of the code density results is very interesting (at http://retroramblings.net/?p=1414 http://retroramblings.net/?p=1414). Do you have a gut feel for what is happening here and why the compressed 32 RISC ISAs do so well compared to yours?
  - robinsonb5 4y ago
    I think there are three reasons: one is that the code my compiler backend produces is "ok" but not fantastic (though it's somewhat better now than it was when that article was written) - another is that I have only 8 registers, and only five are available for the code generator to play with, so I have to spill registers onto the stack sooner than more register-rich ISAs - and finally my simplistic 8-bit instructions don't do as much as a RISC ISA's 16-bit instructions, so some of the advantage of them being only a single byte is lost.
    - klelatti 4y ago
      That makes a lot of sense. Thanks again for sharing such an interesting project.