some old notes that led me to break out BootX? from Boot:
- actually let's reduce it to 16 instructions:
- 3 operands:
- annotate (and CRASH, if all zeros)
- loadi
- load, store
- add-uint, sub-uint, leq-uint
- skipz
- jrel
- TWO (pseudoinstruction)
- 2 operands:
- push, pop
- cpy
- ONE (pseudoinstruction)
- 1 operand:
- jd
- ZERO (pseudoinstruction)
- 0 operand:
- mb we should give up push, pop, and have malloc, mdealloc instead? i'm leaning towards no.. the main argument against is that we want the VM to be able to provide opaque 'hardware stacks' that don't reside in 'memory' and can only be accessed via push/pop. Also, malloc, mdealloc isn't found universally in computing environments, eg it's not in some embedded systems with little memory. If malloc, mdealloc aren't there, then either the program is just given a chunk of memory at the beginning and must stay within that, or memory autoexpands. If the former, though, then the program needs a way to see how much memory it has (to prevent the implementation from having to do bounds-checking on every memory read, assuming it's willing to trust the program), which should probably be a SYSINFO call, but we don't have room for SYSINFO. I suppose we could always use the convention that when the program starts, memory location 0x0001 contains a pointer to a table of library functions, and memory location 0x0002 contains a uint representing the amount of memory (0x0000 is illegal to access).
- the previous suggests that maybe we should have a LOADROM instruction (this is similar to SYSINFO i guess..)
- we could also pass the amount of basememory on TOS of SMALLSTACK. But it seems like we might like to preserve that as a way for the implementation to pass in input arguments
- the problem with saying that 0x0002 contains the amount of memory is that this means that the implementation has to do one extra operation during setup, and the result of this probably won't even be used in most cases (cases where the program just assumes a fixed amount of memory, and the implementation guarantees this), even if it is used in the important case of the self-hosting compiler
- we could always cheat a little and replace 'halt' with 'library', then put 'halt' and 'sysinfo' in the library functions.
- or we could give up on the stupid insistence of a limit of 16, and add a few more instructions
- or we could stop counting ANNOTATE as an instruction
- or we could combine SYSINFO and ANNOTATE -- the problem here is that this prevents the VM from quickly skipping ANNOTATE
- giving up on the limit of 16 is probably the best idea. Because of our use of TWO, ONE, ZERO, we have room for more than 16 instructions, and as noted elsewhere, if you really had a 2-bit opcode field you'd have to leave room for TWO, ONE, ZERO so you'd have 13 opcodes left, not 16, anyways. So 16 is really just an aesthetic choice, not a design necessity.
- ok, i think i've decided. Don't do 8-bit instructions, just stick with 16-bit instructions (long analysis on this in ootAssemblyNotes17; basically, due to the need for more instructions, 8-bit doesn't save much space, and of course it adds complexity). And add a few more instructions; probably at least SYSINFO, MALLOC, MDEALLOC. consider also adding back open, close, poll, library, mul, skipnz, fence-seq, cas-atomic, loadlo.
- still wondering if we should have an add-ptr, sub-ptr, leq-ptr
The rest should be moved into an optional extension, Boot Extended (BootX?, not to be confused with BootY?). In Ovm SHORT these should be mapped as follows; three operand instructions (including TWO) map to opcodes 0-15, two operand instructions map to 16-31, one operand instructions map to 32-47, and zero operand instructions map to 48-63.
note: let's choose the opcodes so that annotate, TWO, loadi, load, store, skipz, jrel, add-uint are all with a leading 0, so that they can appear in any position; then only sub-uint and leq-uint cannot appear as the first instructions in a quad.
- JREL should be +-2 (and should exclude 0 and +1 and maybe -1), not +-8, b/c we need to save 2 more bits (after the initial 8 bits) for the implementation to store offsets. Is a +-2 JREL even useful? Maybe it should be -4, -8, +4, +8 or something like that (-128, -16, +16, +128? -16, -4, +4, +16?), b/c we can always add NOPs; alternately we can decrease Ovm's max length of fully expanded custom instructions from 256 to 64, which gives us 4 bits instead of 2 (+-8 instead of +-2). Currently, i'm leaning towards -16, -4, +4, +16, but since this would probably greatly increase code size, limiting custom instructions to 64 is tempting too. Otoh limiting JREL to -4,+4 and multiples of that limit it to jumping to 64-bit aligned locations (sort of; if we specify that eg +4 is just the start of the next quad, rather than actually +4 in 16-bit terms...), which might be a good idea anyways, esp if in Ovm MEDIUM we specify that JREL is in terms of 64-bit quads or MEDIUM instructions, not potential 16-bit SHORT instructions. Is there another solution? (also, i guess that in Ovm MEDIUM, since we have 3 8-bit operands, we only need one of those for the initial 8 bits, and then of the others we can use one for us and one for the implementation, so we'll get +-128 JREL there).
- the question of whether SKIPs and JRELs (and JDs for that matter) should be to quads or to individual 16-bit instructions is tricky. If to quads, then in some cases we can jump over more instructions, but in some cases less, so either the compiler has to do some calculations (are these somewhat tricky, or easy?) to pad with NOPs, or we have to just assume that in the worst case each SKIP can skip only 1 instruction anyways (i think?). Otoh if we allow jumps to individual 16-bit instructions then in Ovm when SHORT and MEDIUM code will be mixed, either a SHORT SKIP won't be able to reach over the next MEDIUM instruction, or the meaning of a SHORT SKIP won't be determined until we know if the next instruction is a new quad and whether that new quad is MEDIUM or not.
- would it suffice to have jumps to quads, to say that SKIPs can only skip 1 instruction (so pad skips and the next instruction with NOPs), and JRELs can skip exactly 4 instructions (so again, pad with NOPs)?
- or, can we allow SKIPs, in textual assembly, to skip 1-3 instructions, and express this in the actual Boot code using NOPs (when skipping instructions is desired, padding BEFORE the SKIP with NOPs, then placing the instructions to be skipped after it but in the same quad) (in this case perhaps there would also be a compiler directive in the assembly that says "pad with NOPs if needed so that the next instruction is the n-th instruction of a new quad")? a complication is that, what if you had two such SKIPs, and the first one want to jump over the second one and then over one more instruction? This wouldn't be possible if the second one is NOP padded -- but that's simple enough, just say that you can't SKIP a SKIP (or a JREL; what about a JD?) -- but overall this seems to be getting complicated....also, you really need to at least be able to JREL over a SKIP (note: in Ovm MEDIUM, the SKIPZ instruction only needs 1 operand to hold the initial 256-bits for the implementation to cache the jump target address, so we'll have 8 bits free, which can be used to have 4 bits to conditionally JREL +-8 MEDIUM instructions, and 4 more bits fo the implementation for the jump target; so, skipping 1-4 instructions in the textual assembly can still be translated to 1 MEDIUM instruction)
- i guess another solution here is to realize that in MEDIUM mode, we'll only need to save 1 operand for the initial 256 bits for the implementation, not 2 -- so maybe just do that here? so now JREL has 1 implementation-reserved operand, and out of the remaining 2 operands, 1 is for us and 1 is for the implementation; so now we get 4 bits (+-8) instead of 2. Similarly, for SKIP we would ultimately reserve 1.5 operands, leaving .5 for us (the other one is the comparison target operand), so now we have 2 bits to specify a tiny JREL (so mb -3 -2 +2 +3? or -4 -2 +2 +4?). And now say that the quantities in the "for us" operands are 16-bit instructions, not 64-bit quads; and furthermore that in a mixed format stream in Ovm, these are interpreted as 16-bit lengths (at least when found in a SHORT SKIP or JREL; the jumps in MEDIUM SKIPs and JRELs would be interpreted as 64-bit lengths), NOT reinterpreted as a count of 'instructions' each of which could be either SHORT or MEDIUM; and jumping into the middle of a MEDIUM instruction is simply an error (note that, except for JD, such errors could be checked at compile-time). And maybe JD is different, and targets quads rather than instructions.
- but that would prevent smooth interoperation between SHORT and MEDIUM code, since skips and jrels in SHORT could onot jump over MEDIUM custom instructions
- i'm leaning towards saying that SKIPs and JRELs and JDs should be in units of single instructions (16-bit instruction words), with no interaction with the concept of quads, except that it is illegal to transfer control to the middle of a quad whose leading bit is 1 (that is, to instructions of a format not defined by Boot; Ovm MEDIUM and Ovm LONG). However, an implementation is not required to check for this, so the result is undefined (it should be simple for the compiler to prove that this won't happen, that is, that each jump is to a labeled Boot instruction, as long as some restrictions are placed on arithmetic of the variables that will be used as future targets of a JD).
- continuing the previous bullet point, and therefore, as explained above, JREL reserves two operands for the implementation (b/c this is what Ovm MEDIUM will need; one for the initial 256 expansion, and then split the bits in the other two operands between reserved and non-reserved) and uses one (4 bits, so has a range of approximately +-8 (adjusted, like SKIP, to exclude -1 and 0, see the rest of this sentence: -9 -8 -7 -6 -5 -4 -3 -2 1 2 3 4 5 6 7 8)); and SKIPZ reserves one and one half operand, and uses one half (2 bits, so has a range of -3, -2, 1, 2; these are increments to the PC; recall that the PC starts pointing to the next instruction, so -2 points it to the instruction before the SKIPZ, and 1 skips one instruction). Mb rename SKIPZ to BZ.
- i considered saying that you can only JD to the first instruction of a quad, but i guess we don't really need that restriction (except when a quad's leading bit is 1, as noted above).
- perhaps there should be an .align64 assembler directive, which places the next instruction in the first position in a quad? i guess this isnt needed if we can jump into the middle of quads, but mb it'll still be useful somehow?
- i'm leaning towards saying that SKIPs and JRELs and JDs should be in units of single instructions (16-bit instruction words), with no interaction with the concept of quads, except that it is illegal to transfer control to the middle of a quad whose leading bit is 1 (that is, to instructions of a format not defined by Boot; Ovm MEDIUM and Ovm LONG). However, an implementation is not required to check for this, so the result is undefined (it should be simple for the compiler to prove that this won't happen, that is, that each jump is to a labeled Boot instruction, as long as some restrictions are placed on arithmetic of the variables that will be used as future targets of a JD).