proj-oot-ootAssemblyNotes24

---

190529

we need to take a hard look at if Boot is meeting its goals: i'm not sure that it's any easier to implement than RISC-V RV32I.

it provides other benefits:

• the only thing that depends on native pointer size is pointer size
• it's 32-bit
• pointers are opaque
• it will incorporate opcodes for all the syscall primitives necessary for bootstrapping and core interop
• because of the secondary registers and smallstack, you can probably write a bunch of core algorithms in it directly
• it's a 16-bit encoding instead of 32-bits
• it has that cool Smallstack, which probably increases code density
• it's a stepping stone to BootX?, which is pretty expressive

it's better than WASM (no weird structured control flow), simpler than JVM, much simpler than CIL, simpler and lower level than Lua, and simpler than ARM (esp. in instruction encoding). But it may be more complicated than RISC-V. And RISC-V is more popular, so even if it were equal complexity, RISC-V should win.

i used to be scared of RISC-V's instruction encoding variants, but now we have a bunch of those too! And ours are (right now, at least) even less regular than theirs, and also theirs are more thought out and have a bunch of properties that they claim are important for simple, efficient hardware decoding:

• their register operands are always in the same place
• the high bit (sign bit) of their immediate operand is always in the MSb bit (bit 31)
• also, they didn't mention this, but i notice that their rd (destination register) is nearest to the opcode, whereas we have it in the other order -- not sure if that's important though

Yes, their 32-bit and 64-bit platforms are different not only in pointer size, which makes it harder for us to write code targeting both. But we already have an unknown pointer size in Boot, is it really that much trouble to have distinct 32-bit and 64-bit targets? And it's probably not so much trouble to make it worth it to have to start from scratch toolchain-wise with a new assembly language.

Yes, for our purposes, it's slightly simpler to include the necessary syscalls as opcodes. But again, not worth the complexity of introducting a new assembly language.

the only thing that i think might really be important is pointer opaqueness. I'm imagining interop situations where we are running inside a high-level platform like Python, and we want to interoperate with its data structures. In this context we don't have pointers, we have opaque references. We can store them, but not in integers. We can't do pointer arithmetic on them even if we want to. I'm imagining that we will be accessing struct fields (e.g. objects) by assigning a numerical offset for each field and then adding that offset to the base 'reference's, which is why i include the operation of adding an int to a pointer. (now that i say this, it strikes me that even blt-ptr (bltp) is too much, ok i just took that out).

in older versions of Boot we had systems that made the pointer size totally opaque; the program didn't even have to know it for memory layout b/c memory was accessed in terms of pointer-sized words. Should we go back to that?

In any case, we should at least work on our instruction encoding to make it more regular, more like RISC-V.

i think the takeaways are:

• yes, it may still be worth it to do Boot, because pointer opaqueness is a big deal
• i took out blt-ptr just now
• need to improve instruction encoding. Probably should split up the opcodes, like RISC-V does, and also put high bits of immediates at the end, they seem to think that's important.
• consider going back to memory operations that operate in terms of words (slots) of the same size as the ptr. we can still have quantities restricted to 32 bits... this would allow us to have programs that are completely architecture-independent, which is a big win

---

ok so thinking a little more, we need to go back a little to the more complex system where memory was a linear sequence of locations of opaque type and size. The reason is that the whole reason that we want totally opaque pointers is in order to use Boot code in situations like when we are running on top of Python; memory we allocate is Python arrays and we access Python objects by assigning a numbering to their fields and then treating the object reference as a pointer and adding integers to that pointer to specify the fields. The ability to do this is why Boot is more useful for interop than RISC-V.

so some considerations:

• we need to bring back the OTHER type that i took out. Namely, Boot memory locations and registers (which register bank? they might be big, like pointers, but they can't be dereferenced) can hold opaque values of unknown type (these represent objects in some type that the underlying platform knows about but that the Boot implementor hasn't yet made interoperable with Boot). All you can do with these guys is copy them around.
• we may need to go back to making int registers of an unknown bitwidth which is >= 32 bits. The semantics of arithmetic may need to change so that wrapping at 2^32 is no longer guaranteed. This would introduce issues; now it's hard to check for overflow (you can't just see if the resulting value is too small), so we may need to go back to arithmetic with overflow checks, but then that can't be compiled to efficient code on many platforms. Alternately, we can keep int registers at 32 bits, which is what i'm leaning towards. This would imply that OTHERs definitely go in ptr regs.
• we need to bring back the more complicated semantics that i just deleted from the previous version about how it's an error to try and dereference OTHER types or ints
• it's not as easy as just saying that every addressable memory location can hold a pointer. Sometimes you want to navigate memory in smaller chunks than that, for example, when navigating the Boot instruction stream you want offsets in units of one byte because of the BootX? 8-bit instructions. If the pointer size is 64 bits, you don't want to spend 8 bytes to represent each byte of Boot code just because the smallest size that you can address is one pointer-word. Before i had this additional type called CODEPTR. Now i think we don't need CODEPTR, we just need to have a single general system for addressing memory.
• should we rethink dual register banks? No, i still like them; (a) if we do go with 32-bit arithmetic then we definitely need one bank that does that and another bank that can hold ptrs+OTHERs (b) prevents programmer errors (c) simplifies implementation when refs are weird (you're not always special-case checking if the value of your int register is actually some other type) (d) i was going to say it makes semantics simpler, but now that we have OTHERS in one or the other of the banks too it's not so simple
• i guess mainly what we need, in addition to a way to get the PTRSZ, is a fix for the issue mentioned above, when each addressable memory location can already hold an i32; you don't want to take up 4 of these for each 32-bit number in such a case.
• Note that perhaps the amount that each memory location can hold might change for different (base) pointers! For example, one pointer may refer to a Boot-allocated array of bytes (that would be good for holding Boot instruction code); another pointer may refer to a Python object (each of whose fields might hold a reference). These two examples bring up another issue; some pointers might refer to memory locations that cannot hold pointers or OTHERs no matter how many adjacent memory locations you smash together

So, TODO:

• need to improve instruction encoding. Probably should split up the opcodes, like RISC-V does, and also put high bits of immediates at the end, they seem to think that's important.
• think about memory addressing and pointer sizes
  • can the values in INT registers sometimes be >2^32? i'm thinking NO
  • keep in mind the running-on-top-of-Python-memory-offsets-are-struct-fields case
  • some pointers but not others may refer to byte-addressed regions of memory?
  • some pointers but not others may refer to regions of memory in which ptrs cant be stored? for example if we are running on top of Python, so 'pointers' are opaque references, but we have a pointer to an array of bytes to put Boot code into...
  • the issue where, if each addressable memory loc can hold 64-bits, we waste 4 x 64-bits to hold each 32-bit quantity
  • do we want to bring back PEEK and POKE?
• bring back OTHER, and bring back the semantics wording relating to that (about when you try to dereference an OTHER, etc)

---

so far i'm leaning towards/TODO:

• having the int registers really only be 32 bits no matter what (this allows you to use typical operations to check for overflow, which means code will translate efficiently into assembly/contemporary platform primitives)
• having a way to query any pointer and get: whether pointers can be stored here, how many locs are needed for each of: i8, i16, i32, ptr (and is there an assumption that any address you can get by adding to that pointer has the same properties? i think so). Should this be a compile-time or run-time operation? If compile-time it can't really vary by pointer, can it?
• lb lh lw lp sb sh sw sp all read from/write to as many adjacent locations as are needed
• still need to improve instruction encoding: see about having simple opcodes split into multiple places, keeping registers in the same place, having the immediate at the end instead of the middle

---

if our memory locations could literally even be references to consecutive fields in a C struct, then some of those C struct fields can hold i32s, some can't, some can hold pointers, some can't, and this changes for different types of structs. So in that case, either you can to check the size of things at every single location, or the program has to have some knowledge at compile-time.

And if you are relying on the program to have compile-time knowledge about what fits where, then is there anything left to be done? And in that case, are we really any better off than RISC-V?

Perhaps we want the Boot program to have the POSSIBILTY of doing low-level interfacing like this, but to also have a sort of 'general case' memory type that it can do internal computations in, which is more predictable?

here's a few cases to consider:

• memories that can hold i32 values, possibly using more than one memory loc, but not ptrs at all
• memories that can hold both i32 values and ptrs, possible with different sizes
• memories whose sizes are uniform
• memories whose sizes are idiosyncratic at each location (e.g. typed structs)

If we rule out the idiosyncratic memories then things probably become more tractable. This means that memory locations never refer to things like references to consecutive fields in a C struct -- you would treat such things as fields of bytes, instead. But in this case how would we interop with structs on top of a typed HLL language, like Haskell?

---

so, i think that direct interop with external data structure layout is always going to require either program knowledge, or a debilitating amount of runtime introspection. When we say that we want Boot programs to be universal, all that we can really ask for is for the existence of uniform memory for internal data structures -- so e.g. if a hash map library is written in Boot, we want to be able to re-use that same code when running on top of Haskell, on top of Python, or on top of raw assembly. Now again, we can do this at compile time (have constants for the size of ptrs, the sizeof i323s, the size of i16s), or we can do this at runtime (introspection/sysinfo, possibly additional instructions such as addsizeof to make it easier to iterate through memory, although we still need to do other stuff when we need to e.g. compute how many memory locations an array of 100 ptrs takes up).

so, can we/should we just use RISC-V for this? maybe... the semantics we are using are pretty different (pointer arithmetic is invalid) but that may not be a problem. should think further. my instinct is no, the semantics are so different that you don't gain much by using it, so just make something new, it'll confuse ppl less anyways. but that may just be Not Invented Here syndrome.

---

okay i've thought about this a little today, i think it's still worth doing, and here's why:

the other option we are considering is just using RISC-V, but adapted for our case.

this means just specifying that pointers are opaque.

so what happens when you load a pointer? what instruction do you use? We need to add a 'load pointer' instruction, and a 'store pointer' instruction.

and what happens when you add an int to a pointer? what instruction do you use? You could just use 'add'. But then the VM has to check what type is in the registers each type it encounters an 'add', in order to know whether we are adding integers, or adding one pointer and one integer. it would be better to have an add-int-ptr, like Boot.

what happens if you try to do pointer arithmetic? it fails at runtime.

So, we need at least some new instructions (load and store pointer) and could really use some others (add int to pointer). That's already probably enough to make us think about a new language. And pointer registers seem to fit really well too.

we could always do an extension to RISC-V tho...

and there are other minor reasons to go with a new language. We're going to have to redefine the RISC-V semantics a little (no pointer arithmetic), and we're going to have to add the syscall fns. It's more confusing to have an overlay like this than just to make our own new thing.

---

can we make better immediate formats? actually i don't buy RISC-V's idea of splitting the immediates to keep the sign bit in the most-significant-bit. I think it's simpler to keep them together.

---

this 'BootX? should have no runtime requirement over Boot' is getting too expensive. I put in a special 32-to-8 and 8-to-32 cpy (mov) instruction (with its own instruction format) so we could access all 32 BootX? registers from Boot. And i put in extra cpfis, cptis, cpfps, cptps (cpy from int stack, cpy to int stack, cp from pointer stack, cpy to pointer stack) instructions so that we could access deep into the stack without pushing and popping. And i kept the intstack and ptrstack at capacity 8 so that those instructions can access all of it.

But this is getting ridiculous. I'm going to take all that out and assume that BootX?