Boot (Oot Boot) reference

:hardbreaks: :toc: macro :toclevels: 1

Version: unreleased/in-progress/under development (0.0.0-0)

THIS DOCUMENT IS OUT OF DATE. The markdown version, boot_reference.md, has replaced it (although that's not finished yet).

Boot is a low-level 'assembly language' virtual machine (VM) that is easy to implement.

toc::[]

TODO rewrite to current design -- the pyboot implementation, particularly the instruction listings in constants.py, is (mostly) more up to date than this document. Note also that a simpler 32-bit encoding has been introduced; this 16-bit encoding has been made an optional 'compressed' encoding (mb since it's optional, it should be moved to BootX?) later: actually now i'm thinking of simplifying even further and removing stacks, and adding floating point, see ootAssemblyNotes26.txt

TODO actually let's go back to defining int32 as '32-bits OR MORE' and make integer overflow fully undefined behavior. This is because signed integer overflow is undefined behavior in C and we want to allow porters to compile arithmetic straightforwardly to their unchecked C equivalents; and also because [1] says that in many cases it's much more efficient for variables to be register width. I also made a note about this at the end.

Introduction

Boot's purpose is to promote the portability of OVM (Oot Virtual Machine) by serving as a portable target language underneath it.

The reason for writing a new assembly language, rather than adopting LLVM or Webassembly or similar, is that we want the entire Oot toolchain to run on top of many platforms, including 'on top of'/within existing high-level languages such as Python. This means that the entire Boot implementation needs to be quick and easy to port (not just retarget to a new backend, but entirely port), and it needs to support opaque platform-native pointers of unknown size.

Highlights:

• 3-operand fixed-length register machine
• about 40 TODO instructions
• instructions include TODO signed 32-bit integer arithmetic, stack operations, I/O and memory allocation
• RISC-like; no addressing modes (or rather, each instruction has one fixed addressing mode), and only a few instructions access (non-register) memory
• 16 registers, including 10 GPRs and 6 special-purpose registers
• two fixed-capacity 8 element stacks (one for ints, one for ptrs) with opaque representation
  • todo: remember we need 6 items on ea. stack for implementation usage. If each stack is o.w. 16 items, that's 22 items total. These are not for user use, only for the toolchain (e.g. compilation of BootX? into Boot)! The 'user' program should only assume 16 items are available.
• opaque pointer representation
• instructions for compare-and-swap and memory fence
• instructions for I/O and memory allocation

Cheatsheet

Instruction encoding: 16 bits, little endian. LSB bit (the 'instruction encoding length format bit') is always 0.

Four formats:

• I11: 2 I11-opcodes, one 11-bit immediate operand
• I8: 2 I8-opcodes, one register operand which can address 8 registers, and one 8-bit immediate operand
• R-format: 32 opcodes, two register operands which can each address 16 registers
• P-format: 32 opcodes, three register operands which can each address 8 registers

For each format, from LSB to MSB, the fields are:

• I11-format (11-bit Immediates): 0000, I11-opcode (1 bit), signed immediate operand (11 bits)
• I8-format (8-bit Immediates): 0001, I8-opcode (1 bit), signed immediate operand op1 (8 bits), operand 0 (3 bits)
• R-format (many Registers): 001, R-opcode (5 bits), operand 0/1 (4 bits), operand 0 (4 bits)
• P-format (many oPerands): 01, O-opcode (5 bits), operand 2 (3 bits), operand 1 (3 bits), operand 0 (3 bits).

In graphical form (from MSB to LSB) (0,1 = constants, o = opcode, x = operand 2, y = operand 1, z = operand 0:

I-formats:

• I11-format: iiiiiiiiiiio0000
• I8-format: xxxiiiiiiiio1000

R-formats:

• R2-format: xxxxzzzzooooo100 (operand 1, yyyy, is not encoded because it is assumed to be the same as operand 0)
• R1-format: xxxxoooo11111100
• R0-format: oooo111111111100

P-formats:

• P3-format: xxxyyyzzzooooo10
• P2-format: xxxyyyooo1111110
• P1-format: xxxooo1111111110
• P0-format: ooo1111111111110

TODO out of data; this is now the 'compact' format, which should go in a different document

Note that some implementation could choose to consider the subinstructions of otwo, oone, ozero as separate encoding formats.

Note that some implementation could choose to consider the I-format as consisting of two subformats, depending on how many bits the immediate constant is.

The I11 and I8 instructions are:

• I11: jpc and jk (jumping)
• I8: ldi sai (loading constants)

Datatypes: int32, ptr

Registers: two banks of 16 registers each; one for int, one for ptr. The first 5 registers in each bank are special. The next 3 are GPRs. Some operations are only available on the first 8 registers.

Instructions:

TODO: add the other new instructions

other ideas: in out push pop dup drop swap over read write halt impdep poll sysinfo xcall devop, CAP register/stack cmov select call ret cmov malloc dealloc realloc

In the following, #X is an immediate constant, $X is an integer register, &X is a pointer register, and x is an untyped argument. All immediate constants are signed two's-complement ints.

From left to right, the arguments go into operands op0, op1, op2. Immediate operands are always on the right (the highest-numbered operand). When two immediate operands are combined into an #imm6 (as with instruction jd), op1 is the high-order bits and op2 is the low order bits (imm6 = (op1 << 3) + op2).

The branch immediates have a special coding, because -2, -1, 0 are not needed; at the time of branch instruction execution the PC is pointing to the beginning of the instruction after the branch instruction. Since instructions are 16-bits, -2 would branch right back to the branch instruction itself, causing an infinite loop; -1 would branch into the middle of the branch instruction; and 0 would cause the branch to end up at the same place as if there were no branch. Therefor the branch instructions interpret the numbers 0..7 in op2's binary representation to code for: [-6, -5, -4, -3, 1, 2, 3, 4]. The program counter is in units of bytes, and instructions are 16-bits (2 bytes), so a branch immediate of +2 skips over one instruction, and a branch of +4 skips over two instructions, and a branch of -4 skips backwards two instructions, and a branch of -6 skips backwards three instructions. The odd-numbered branch immediates (-5, -3, 1, 3) are illegal in Boot but are present for compatibility with BootX?, which is a variable-length instruction set including some 1-byte instructions.

Jump and branch offsets are in units such that an offset of 2 represents one Boot instruction. Platforms which represent Boot code in memory in ways such that one instruction spans more or less than 2 memory locations should adjust the jump and branch offsets accordingly when executing instructions jpc beq beqp bne blt, and also should emit the correct INSTRUCTION_SIZE in SYSINFO. Program code which dynamically computes code pointer by adding integers to the PC or to other code pointers should be sure to take account of INSTRUCTION_SIZE.

meta:

• ann #imm9: ANNotation; no effect on execution

constants:

• li $reg #imm8: LoaD? 8-bit Immediate int constant
• sai $reg #imm8: Shift left 8-bits then Add 8-bit Immediate int constant
• lk $k: LoaD? K-th ptr constant and push to &stack. The pointer constants can range from -32768 to 32767 (some Boot implementations may support a larger range). The positive pointer constants are pointers to the program locations corresponding to the jump table (these are suitable to be fed to JY instructions). The negative pointer constants are defined in an implementation-dependent manner (these could be used for external function entry points, constant data pools, special platform-specific memory locations, etc).

register loads and stores and moves:

• lw $dest &addr: LoaD? 32-bit int from memory (or stack index) to register
• lh $dest &addr: LoaD? 16-bit int from memory (or stack index) to register
• lhu $dest &addr: LoaD? 16-bit unsigned int from memory (or stack index) to register
• lb $dest &addr: LoaD? 8-bit int from memory (or stack index) to register
• lbu $dest &addr #imm3: LoaD? 8-bit unsigned int from memory (or stack index) to register
• lp &dest &addr #imm5: LoaD? Pointer from memory (or stack index) to register
• sw &addr $src #imm3: STore 32-bit int from register (or stack index) to memory
• sh &addr $src #imm3: STore 16-bit int from register (or stack index) to memory
• sb &addr $src #imm3: STore 8-bit int from register (or stack index) to memory
• sp &addr &src #imm3: STore pointer from register (or stack index) to memory
• cp $dest $src: CoPY? int from register to register
• cpp &dest &src: CoPY? Pointer from register to register

stack and register/stack loads and stores and moves:

• lsi $dest #imm3: Load from int Stack, Integer (copy a value from deep in int_stack without popping)
• lsp &dest #imm3: Load from ptr Stack, Pointer (copy a value from deep in ptr_stack without popping)
• ssi $src #imm3: Store to int Stack, Integer (overwrite a value deep in int_stack without pushing)
• ssp &src #imm3: Store to ptr Stack, Integer (overwrite a value deep in ptr_stack without pushing)
• swapi $reg: swap two items (note: can be used as swapi $s $s to swap top two items on intstack)
• swapp &reg: swap two items (note: can be used as swapp &s &s to swap top two items on ptrstack)

(note: you can use 'cp' and 'cpp' to achieve DUP, and by also using the zero register, DROP)

arithmetic of ints:

• add $dest $src1 $src2: $dest = $src1 + $src2 mod 2^32
• addi $dest $src1 #imm3: $dest = $src1 + #imm3 mod 2^32
• sub $dest $src1 $src2: $dest = $src1 - $src2 mod 2^32
• mul $dest $src1 $src2: $dest = $src1 * $src2 mod 2^32

bitwise arithmetic:

• sll $dest $shiftamount $src: shift left
• sru $dest $shiftamount $src: shift right unsigned
• srs $dest $shiftamount $src: shift right signed
• and $dest $src1 $src2
• or $dest $src1 $src2
• xor $dest $src1 $src2

arithmetic of pointers:

• ap &dest $src1 &src2: &dest = $src1 + &src2 (Add to Pointer) (note: some pointers may not be able to be added to)

(?: i'm not sure if these are worth including; the idea is to make up for the fact that the platform word size and pointer size is not known at compile time. Note also that a fancy VM could easily search for these at loadtime and substitute in the appropriate platform-specific immediate constants. These also serve to provide an ADDI on pointers, which is probably very useful)

• appi &dest &src #imm3: &dest = &src + #imm3*PTR_SIZE (Add to Pointer, units of Pointer, Immediate)
• apwi &dest &src #imm3: &dest = &src + #imm3*I32_SIZE (Add to Pointer, units of Word, Immediate)

conditional branches:

• beq $src0 $src1 #imm5: branch-if-equal
• beqp &src0 &src1 #imm5: branch-if-equal on ptrs
• bne $src0 $src1 #imm5: branch-if-not-equal
• blt $src0 $src1 #imm3: branch-if-less-than

unconditional jumps:

• jpc #imm11: jump (PC-relative)
• jy &target: dYnamic (indirect) jump. &target must be a code pointer provided at runtime (either by PUSHPC or by platform-specific or foreign code or lk) and which did not have further pointer arithmetic performed on it; otherwise, results are implementation-dependent (note that dynamic pointer arithmetic on code locations is non-portable because a compiler may translate Boot instructions into platform instructions of unknown and differing size).
• jk $reg #imm11: Jump to the pointer that would be loaded by "lk $imm11". $imm11 is signed (so, it can reach the first 1KiB? entries in the global jump table, and the first 1KiB?