proj-oot-ootAssemblyNotes29

ok i'm trying to understand which calling convention we should have, and tail calls, etc.

i've read two things:

• ppl say you should have callee cleanup if you have tail calls
• but this seems inefficient to me, because it prevents the same buffer from being reused by the caller to pass arguments to multiple callees over time, doesn't it? Maybe if things are always passed on the stack rather than in a 'buffer' it's not as much of a problem...
• ppl say you should have pascal order of arguments (i assume this means left-to-right) instead of C order (right-to-left). need to see why they say that [1] -- mb they really just meant the pascal calling convention in general?
• someone also said that caller-cleanup is needed for varargs ( https://stackoverflow.com/questions/27596248/why-languages-such-as-c-pascal-cannot-implement-tail-recursion )

ok, on the callee cleanup:

• at first i wasn't seeing it, because i think thinking tail call = reusing the stack frame and then skipping intermediate returns that shared a stack frame. So if A calls B and B calls C, and A allocates a stack frame for the arguments it's passing to B, and B reuses that same stack frame to call C, then C can return directly to A, skipping B, and then A can deallocate the stack frame. This works the same if the arguments are passed in some other heap-allocated activation record instead of on the stack.
• but after reading a little bit i think what they mean is: if the convention is that the caller cleans up then, by that convention, B should be given the chance to do some cleanup after C returns, since conceptually what is happening is C returning to B and B returning to A. So, remember that tail-call optimization is only allowed when the call is in tail position; in this case the call from B to C isn't "really" in tail position because B has a hidden operation after the call to C (namely, to cleanup)
• so the tail call elimination is being imagined to work like this: the compiler detects a call in tail position in B to C; to compile the call, instead of creating a new stack frame it overwrites its own, and instead of pushing the current address into the link register, and then jumping, it just jumps (so the link register still contains the return address from A).
• compared to how i imagined it worked (with caller cleanup): the compiler detects that the call from B to C is in tail position, and also that B and C share the same stack frame layout; so instead of creating a new stack frame it overwrites its own, and instead of overwriting the link register it just jumps, and instead of cleaning up after the call, it doesn't.

perhaps the 'share the same stack frame layout' is at fault. Imagine that C takes more arguments than B. So eg to cleanup B's stack frame, maybe you have to bump up the stack pointer by 10, but to clean up C's stack frame, you have to bump it up by 20. Now if control is returned directly from C to A, and if A is supposed to do cleanup, all A knows is that it called B, so it'll bump up the stack pointer by 10, which is wrong, because the size 20 stack frame is in effect because of the call to C.

ok so this makes the vararg thing almost but not quite make sense, i think. if A decides to call B with a size 30 stack this time, and then B calls C, and we have callee cleanup, then C cleans up its own stack and jumps back to A, but no one cleans up B's stack, because B was supposed to clean that up but B got skipped.

i think we may need a bigger example to demonstrate. A->B->C->D. All in tail position, so we want to return directly to A. B->C is a vararg call. So the two ppl in a position to know about the size of the vararg stack frame are B and C, but both of them got skipped on the return.

this still doesn't quite make sense though, because what is preventing C from cleaning up the vararg stack frame before the call to D?

https://stackoverflow.com/questions/35626835/make-a-variable-argument-function-callee-cleanup maybe sheds some light here. it seems like the convention is to put the return address last (at the top of the stack/bottom of memory), below the arguments. So maybe you don't want to bump up the stack pointer before returning because then the return address is in the de-allocated-ish area below the stack pointer. And i guess the compiler can't be bothered to just manually move the return address up, overwriting earlier arguments. There is apparently an instruction in x86, 'RET #x', with #x immediate, that reads the return address, moves the stack pointer up by x, and then jumps to the return address which was read. But if it's a vararg then x is only known dynamically, not staticly, and it's an immediate, so it doesn't work.

so that last bit about the vararg sounds like it's something specific to limitations in the x86 convention, conveniences in the instruction set, and the way that compilers (and probably branch predictors) insist on using that.

more about vararg stuff [2]

so it sounds like callee cleanup is the way to go.

other notes i found while reading about this:

• if the caller cleans up, then every call to a given function has to have cleanup instruction(s) after the call; whereas if the callee cleans up, the cleanup has to appear only once, in the callee, just before the return. Assuming that CALLs are (staticly) more frequent than RETs, it's more code dense to put the cleanup instructions in the callee, next to the RET [3] [4]
• however, caller clean up can be more efficient in a similar way if it doesn't clean up after every call, but instead calls a bunch of things (bumping the stack down each time) and then cleans up all at once (so only one 'cleanup' stack bump up, at the end). [5] " Quote Originally Posted by gcc manual -fno-defer-pop Always pop the arguments to each function call as soon as that function returns. For machines which must pop arguments after a function call, the compiler normally lets arguments accumulate on the stack for several function calls and pops them all at once. " " The x86 core has a feature called "esp folding" which allows the processor to delay making visible changes to esp when it is altered implicitly by push and pop instructions. An explicit argument cleanup, by adding a constant value to esp, interferes with this deferral and causes pipeline stalls.

The fewer times you modify the value of esp explicitly, the better. There is more going on in these instructions than meets the eye. " -- https://cboard.cprogramming.com/tech-board/117965-callee-cleanup-variable-number-parameters.html - that's nice but it sounds fancy -- and if we're doing fancy stuff i'm betting tail call elimination is more important

• ppl here suggest that the x86 convention gives the callee no definite way to even know how many varargs there are [6]
• this again sounds like a deficiency of x86 conventions rather than something inherent in callee cleanup to me

strangely https://www.agner.org/optimize/calling_conventions.pdf doesn't have much to say about this.

https://github.com/microsoft/ChakraCore/issues/796 has a good point about another way to do varargs with TCO: with caller-cleanup, if A->B->C->D and B->C is vararg and D skips over B right back to A when returning, it's true that A doesn't know how much stack B allocated to hold the varargs, but A can still make things right just by remembering what its stack pointer was before the call (that is, treating SP as caller-save instead of callee-save) -- of course since it's the stack pointer itself that is being lost, it has to save it in some other callee-save register, rather than on the stack. They don't like doing this because it uses up another callee-save register on each such function call (so one less register, and also all those saves and restores). They seem to think a better alternative would be callee-save, but they have a lot of vararg code that would need to be rewritten or something. Sounds like they decided to do nothing in the end (not support TCO).

Q: "Everywhere it says that the called function doesn't know how many parameters have been passed, but in that case why isn't it possible to simply put that data into a register or push it onto the top of the stack for the called function to use?"

A: " There is no fundamental reason why the callee couldn't clean up space for variables. In most architectures, the standard calling convention doesn't handle variables this way, but that doesn't mean it's not possible to do so. For variable-length argument lists, you could either pass data about the number of arguments as a hidden parameter (like how this is handled in many object-oriented languages), or put a pointer on the stack that shows where the arguments end, etc. " -- https://stackoverflow.com/questions/19822045/what-prevents-the-callee-from-cleaning-up-the-stack

"The callee can clean variable arguments from the stack. I made it once, actually. But the code is pretty big.

Anyway, the main reason why in cdecl convention, the caller cleans the stack is other ...On some architectures (usually very small, as the old 8080 or 6800), there is no ret n instruction that to automate the stack cleaning and as a rule they can't make arithmetics with the stack pointer as well.

So, the callee have to first pop the return address from the stack in order to reach the arguments, then to pop all arguments and then push back the return address....When cdecl convention is used 2 instructions and one register use are spared:...And because for single language it is better to use single calling convention on all platforms, the CCALL as more simple and universal looks better. (C language is created in times when 6800 was a high tech).

But notice, that on these platforms, the assembly programs and the native languages (for example different kind of BASICs) usually use register argument passing which is of course much more faster on such small systems. " -- https://stackoverflow.com/questions/19822045/what-prevents-the-callee-from-cleaning-up-the-stack

some languages put (RAIIish?) destructors in their (caller?) cleanup routines, preventing TCO:

" Many Perl idioms rely on strict stack discipline. For example, implementing cleanup code as the destructor of an object held in a lexical variable in a particular stack frame. The result is that implicit tail-call optimisation would break all sorts of things. Hence tail-call semantics are only safe to invoke *explicitly*, which is what Sub::Call::Tail provides. " [7]

---

it sounds to me like callee cleanup is the way to go. TCO may be important, varargs probably not (can always store those in memory).

---

next question: store the first few regs in registers in Boot calling convention?

pro: faster, if regs are really regs

pro: this allows Boot syscalls with few arguments to avoid hitting 'main memory' (until we're in the actual implementation of the call)

con: in LOVM, seems cleaner to put args in smallstacks. That way they can be shifted similarly to 'input argument' and 'output argument' register window sections. if we have the first few args in registers and the rest in smallstacks, that's confusing

my leaning: at first i was leaning to not use regs at all (just stack) for cleaner transition to lovm, but it galls me to have to hit memory just to do a syscall. So now i'm leaning towards using regs. I kinda think there might be a way to may the register window thing work cleanly anyway with the regs.. after all if you need to preserve the input args while you are writing the output args you'd just move them onto the stack right? So mb it's not that much worse. So i kinda think the thing to do is try using regs and reconsider if necessary after implementing x86_64 assembly version of Boot and LOVM (in the far far distant future).

decision: for now, use regs

---

next question: how many regs?

so, should we pass 2 or 3 args in registers?

if 3, then no space for a temp, and maybe we should add instructions: push-int-to-SP-and-decrement-SP push-ptr-to-SP-and-decrement-SP

or at least add back in:

• appm &dest &src1 #imm7: &dest = &src1 + #imm7*PTRD_SIZE
• ap32m &dest &src1 #imm7: &dest = &src1 + #imm7*INT32_SIZE

because currently, without a free temp register, in Boot, you can't even push to stack (you can't predecrement the SP without loading an immediate into a register)

otoh mb most of the syscalls we want to make can use only 2 (remember we have 2 banks, so 4 spots in total, so as long as both integers and ptrs are being passed, you get more than 2 arguments), so maybe it's okay to just pass 2 args in registers and leave a scratch register.

also, it sucks to add appm and ap32m in Boot, b/c (a) you may want to add two versions of them b/c we don't have signed immediates in oot, and (b) in LOVM they are a duplication because we can have a general instruction like this with both an immediate and register addr mode for op2.

regarding (a), well i guess an upward-growing stack is POSTincrement, which isn't a problem (copy the argument to the stack, then overwrite that register with the immediate, then add that immediate to the stack (postincrement); now you have one free register); it's the predecrement convention in the downward-growing stack that's a problem. So you don't really need to add one version for each direction, even if the immediate imm7 is unsigned. So it's only 2 more instructions, and hey maybe they will be useful anyways b/c they will have a 7-bit unsigned immediate range rather than a 6-bit signed immediate range (so 5-bit unsigned).

so far i've looked a few syscalls tho and none really need more than 2 args of one type for the most basic functionality:

open read malloc

i'm leaning towards just using 2 regs for arguments:

• my sampling of those syscalls makes it seem like you can go pretty far with just 2 regs of each type
• if you care about efficiency, there's always LOVM, with a lot more regs
• if you did fill all 3 regs of one type, there's not much you could do anyhow, because computation within the function would probably need to use one reg of that type, and then you end up pushing something onto the stack, so why not just put it on the stack in the first place?

decision: 2 regs for now

---

next question (which arose while researching the previous one):

what to do when, depending on platform, APIs might return an integer or a pointer?

For example, on Linux, the open() syscall returns an integer file descriptor. On Windows, the CreateFileA? syscall returns a ('file'?) handle, and the (older?) winbase.h OpenFile? also returns a file handle.

https://stackoverflow.com/questions/902967/what-is-a-windows-handle

https://www.codeproject.com/Articles/1044/A-Handy-Guide-To-Handling-Handles

what does windows API mean by 'handle'? I like Dan Moulding's stackoverflow answer:

" A HANDLE is a context-specific unique identifier. By context-specific, I mean that a handle obtained from one context cannot necessarily be used in any other aribtrary context that also works on HANDLEs.

For example, GetModuleHandle? returns a unique identifier to a currently loaded module. The returned handle can be used in other functions that accept module handles. It cannot be given to functions that require other types of handles. For example, you couldn't give a handle returned from GetModuleHandle? to HeapDestroy? and expect it to do something sensible.

The HANDLE itself is just an integral type. Usually, but not necessarily, it is a pointer to some underlying type or memory location. For example, the HANDLE returned by GetModuleHandle? is actually a pointer to the base virtual memory address of the module. But there is no rule stating that handles must be pointers. A handle could also just be a simple integer (which could possibly be used by some Win32 API as an index into an array). "

This resurfaces the motivation for the ANY type registers that i had in there awhile ago but removed. Here we have a something that:

• can't be arithmetic'd
• can't be dereferenced
• might be as large as a pointer

interestingly, we already have something like this: codeptrs. If you think about it, in an interpreter a codeptr could be represented as an integer index into a list of instructions, rather than as an actual pointer into memory (with 'instructions' conceptually residing in a special 'code memory' which is not part of or accessible from data memory).

so should we (re)create a third register bank for these guys (what i used to call ANY type)? it might be sort of nice for the implementation to distinguish between these guys and dereferencable pointers: for garbage collection purposes. These guys could be 'boxed' with additional bits that say whether they are really integers or really pointers.

Disadvantages:

• as we see, having all these register banks leads to inefficiency:
• e.g. when trying to specify how many register spaces you need, eg. for ENTRY, you end up having to duplicate all of these config info, one for each bank
• when these are mapped directly into physical registers (or into a fixed layout register bank in cached main memory), you end up having unused registers because some algorithms need more integers and less pointers, etc
• could a sufficiently smart compiler fix this? Well.. maybe? I guess if these things were represented as just variables that needed to be stored, the compiler could transform to SSA (to separate the lifetimes of the distinct values being stored in the same Boot register), and then not waste space storing anything when the Boot register is unused.
• and it's better in LOVM, when some of the registers are 'turned on' and 'turned off' by ENTRY
• an in some ways, having 3 register banks is especially bad b/c it's not even a power of 2
• could add an additional bank for labels/codeptrs tho, so then 4
• one of the original reasons to separate ints and ptrs was just to allow them to be different sizes. That isn't needed here, as we could just assume that ptrs are at least as large as ints, and so everything fits within a pointer-space
• counting all registers and smallstacks, we're up to ~256 words of register state (32*4 regs + 32*4 smallstacks). On a 64-bit system that's 2k of state!

Advantages:

• encoding-wise, you get to encode more variables in the same amount of operand bits, with the cost in an inflation of opcodes
• for adding an ANY type (mb we should call it 'handle' type?) this isn't so bad, b/c all we can really do with them is cp, ld, st
• 'type safety' for free, up to a point
• as i noted above, the implementation can represent the ANY type differently, eg by boxing and providing further info about whether it's really a pointer (or, in the case of blind memory copies, that could itself be unknown). This could help in the OVM level, when the implementation will do GC
• 'cleaner' in the sense that it really just follows the same set of principals that led us to separate ints and ptrs in the first place -- and everything is better typed
• we could do blind copying of memory without relying only on memcpy
• actually, mb not: "Do not use byte-by-byte memory copies to copy pointer values. This may result in intermediate conditions where there is not a valid pointer, and if the gc pauses the thread in such a condition, it can corrupt memory. Most implementations of memcpy() will work since the internal implementation of it does the copy in aligned chunks greater than or equal to the pointer size, but since this kind of implementation is not guaranteed by the C standard, use memcpy() only with extreme caution. " -- https://dlang.org/spec/garbage.html
• our 'memcpy' syscall would guarantee not to have this problem
• otoh we could simply guarantee that loading/storeing to 'any' type "does the copy in aligned chunks greater than or equal to the pointer size". Not sure if that always works tho, what if the program asks for an unaligned ANY read?

out of these, i think the most important considerations are:

• we lose any hope of naive implementations that map all of the registers directly to x86_64's 16 registers. Since with 4 banks of 8 we'd have 32 regs, we probably have a lot of trouble even mapping this into other ISAs' 32 registers.
• we could reduce the number of registers further. But if it's not a power of two that doesn't help us fit in operands. Could we go down to 4 regs of each type? Possibly; the stack pointer would remain a pointer, but the link register would be a codeptr, so each of those two banks would have: a zero register, a TOS, a special register, and a free register. Between the TOS and the free register, that's two of them. That gives us 12 regs (b/c we don't have to store the zero regs) to put in the 16 x86_64 regs (some of which can be shared, eg stack pointer).
• we could add the concept of turning on and turning off registers to Boot. In a 32-bit integer, we have 4 sets of 8 bits. So one 32-bit integer could specify how many of each register bank we need, from 0 to 255. To specify from 0 to 64, we need just 6*4 = 24, which is conveniently 3 bytes. To specify from 0 to 32, we need 5*4 = 20, which conveniently can fit within the 21 operand bits available for a LOVM immediate.
• can't that just be an annotation?
• for now it could be, but in LOVM, where we have ENTRY that pushes things onto the stack in a defined manner, the visible state of the stack could depend on this state
• well, not necessarily; we could encode that stuff in ENTRY instead (and we probably will)
• an annotation with a 20 bit immediate takes up too much of ANN's "opcode space"; we want to have room for many different types of annotations
• what if we only allow registers in each bank to turn on and off in powers of 2?
• we need to count from 0 to 5 in each of 4 banks. So 3 bits per bank. So 12 bits total.
• this could fit in ANN's 'opcode space'
• what would the sigils be? * for any? That might confuse C ppl, and we might want to use it later in Lo or Loot for dereferencing (is there the same consideration for & as a ptrregister sigil? Maybe not, because you can't take the address of a register; &(&3) wouldn't make sense). Maybe ! for any, or mb ~. For codeptrs (labels), maybe @.
• what would the zero regs be? $0 is 0, &0 is null ptr, i don't know what ~0 is, and @0 is either the beginning of the program, or the PC.
• does it make sense to have the '8 register' restriction in Boot if we're going to do this? Maybe not. The restriction should either be 4 registers, or no restriction (32 registers).
• in that case, is Boot really that different from LOVM? All that we're holding back seems to be:
• smallstacks
• addr modes
• variable-length instruction encoding
• more instructions
• this is actually a good thing, b/c it means a porter can more easily start with Boot and then expand their implementation incrementally to LOVM
• we might want to just rename LOVM to BootX? in this case
• altho i guess the smallstacks make them still pretty different

so the proposal is:

• add 2 more register banks (codeptrs/labels and (handles? any? opaque?))
• remove the 8 register restriction (so up to 32 regs in each bank, from 0 to 31)
• add the additional instructions we need (cp ld st for each bank)
• ?add an instruction to specify how many registers of each type are currently alive? or an annotation? or a HINT instruction?

i'm leaning towards this.

---

we may want to introduce alignment restrictions to prevent the problem noted above about another thread seeing an invalid pointer in the middle of write? otoh if each thread has its own GC then the GC and the implementation can have a mutex when the implementation main thread is writing to memory. if ptrs are opaque, how to align? mb would need an instruction for that

done

the stack also has align restrictions on some targets (eg 16-bit on x86 at least on x64 windows)

• eg i think this isnt even windows: https://research.csiro.au/tsblog/debugging-stories-stack-alignment-matters/
• "GCC in MinGW? uses Linux ABI that requires stack to be 16-byte aligned" https://github.com/uTox/uTox/issues/1304
• https://refspecs.linuxfoundation.org/elf/x86_64-abi-0.98.pdf says "The end of the input argument area shall be aligned on a 16 byte boundary."

i think that's an ABI thing though, so i guess we can ignore it in Boot (where we have Boot's own convention, rather than trying to interop with the underlying platform convention). And in LOVM we can abstract it.

---

what do garbage collectors do about pointers that may be invalid (e.g. a C pointer that points past the end of an array)?

https://www.hboehm.info/gc/04tutorial.pdf says

" Pointer validity check

• Get page descriptor. Valid heap page? •About three memory references. Simple top level hashing scheme for 64-bit addresses. •Two with a small cache. If not first page of object, adjust. Valid offset in valid object? •Remainder computation on offset in page gives object start. •Remainder can be looked up in table of ìvalid offsetsî. •Allows pointers to only certain offsets in object to be considered valid. Check is constant time. •Small constant number of memory references "

elsewhere in those slides it's clear that memory allocation is done thru the GC, so the GC is aware of where the valid memory is

"Unlike [BoehmChase?92] we start with the assumptionthat the garbage collector recognizes all pointers to theinterior of an object, not just to the first byte of the object.Recent experience suggests that this is the right framework,particularly for typical C++ implementations whichimplicitly generate pointers to the interior of an object. Thetechniques of [Boehm93] can greatly reduce the danger ofspace leakage that we previously associated with thisapproach. This new assumption greatly simplifies our task.Unfortunately, it also usually invalidates assumption (A) of[BoehmChase?92], so our correctness argument has to bedifferent

...

We assume that the garbage collector recognizes anyaddress corresponding to some place inside a heap allocatedobject as a valid pointer. ([Boehm95] satisfies theseassumptions in its default configuration"

[8] "Simple Garbage-Collector-SafetyHans?-J. Boehm"

so it looks like it actually checks potential ptrs to see if they are in valid memory before it derefs them. oh man what a pain (but oh man so amazing)

---

"OurMagpietool? converts C source programs to cooperatewith precise GC ... Some constraints on the C program depend on the specific GCimplementation that is used with Magpie-converted code. The GCmay supportinterior pointers, i.e., pointers into the middle of a GC-allocated object, including to the end of the object. In practice, wefind that interior pointers are common in real C programs, whileprograms specifically adjusted to work with precise GC (such asthe PLT Scheme runtime system) can avoid them to help improveGC performance. Note that a pointer just past the end of an arrayis legal according to the C standard, and Magpie considers suchpointers to be valid interior pointers " [9]

---

also, mb i should allow <= comparison on pointer values. I didn't use to allow it because it may not make sense. But there are times (e.g. sort a list of pointers so that you can do binary search to determine the presence of a pointer in that list) when you really want to compare pointers, and you don't care if the comparison has any other meaning aside from being a total ordering.

what do other languages with opaque pointers/no pointer arithmetic do about pointer comparison? e.g. what does Golang do?

golang allows equality comparison only, but not greater-than, less-than: https://stackoverflow.com/questions/45818964/how-can-i-compare-pointers-in-go

---

later i decided to remove register/smallstack banking again -- see discussion in [[ootBootNotes1?]].

---

so what about unified register files with floating point as ordinary gprs?

https://stackoverflow.com/questions/51471978/is-there-any-architecture-that-uses-the-same-register-space-for-scalar-integer-a

sounds contentious but seems like today's best practice is to bank them, eg separate floating point

also most mechanical sympathy on popular archs is to bank fp

so bank the fp regs, but not the smallstacks (b/c fps on the stack are in the same linear memory substacks as everything else). btw https://stackoverflow.com/a/52175510/171761 suggests having more caller-save registers in the fp bank, and less callee-save regs, unlike his suggestion for integer

--- old

maybe we can get away with having the primary stack be above the stack pointer in the output stack be below the stack pointer, and pushing to the output stack all at once in a calling sequence. Alternately, since the primary stock can output stock capacities are fixed, If you save those capacities in a register then you can offset the beginning of the output stack from The frame pointer.

yeah I think we need to register to hold The frame allocation information in. At least this is cheaper than a fixed sized register windows where you always have to push a Certain window size onto the Stack. Again consider making those allocation quantities powers of two -- Then maybe we really can fit in All the variables we may need. I think we do need an extra register for holding the primary stack position. Maybe reserve a register for the PC. I'm still thinking if there's a way for the boot calling convention to put arguments in registers. I guess one way is just to use the out stack addr mode as registers! That would imply that the recipient not the caller is the one who shifts out to Local. Also maybe out should be registers not stack even in lovm. Consider however that a Nice thing About Forth was that function calling was cheap (eg no callee-saving etc to be done).

Maybe you can simplify all of this by having one stack and specify how many output args when you call th next function

mb don't even let the program Read the stack pointer that when the stock is not flushed that way we don't have to have an extra register for the tip of the cached stack

The thing is if it's one stack and that stack is interrupted by the return address and the frame pointer And any other callee saves, local variables, or other junk we have in the stack frame. So that makes it Inefficient to translate a stack position to an address. If it's two stacks then it's inefficient to push more to the argument input Stack, Because directly after that is the stuff in our stack frame. This suggests that the argument input stack Should be mapped to registers, And the only snack should be the out Stack

So Callee clean up means that the input arguments are cleaned up too right?? so our output arguments passed where the input arguments were on the stack.?

I think what you're looking for is that out could really be registers. We could rely on the callee to flush out to the stack if needed.

But in that case, how do we use the stack pointer in boot?

I guess maybe if the program never touches the stack pointer then this stuff is abstract

---

i can't think of a good way for the LOVM calling convention to match up with a Boot all-register calling convention without actually moving the smallstack addr modes from LOVM to Boot. In which case we could do this:

• 'input stack addr mode' addresses the things above the frame pointer. Note that this is also where the return arguments can go.
• 'output stack addr mode' addresses the things above the stack pointer
• swapping output to input is done by the callee when the frame pointer is moved to the stack pointer, and the stack pointer is moved down to allocate the new frame
• flushing to memory is done immediately prior to this, by the callee
• sibling tail calls might not have to flush nor allocate a new frame nor swap
• SS addr mode moves the stack pointer (and so affects the out stack, not the in stack)
• caching non-guarantees and flushes need to be a part of Boot semantics

caching non-guarantees:

• if the stack pointer is moved up or down, the smallstack items 'move' as appropriate, however the 'new' items (in the empty smallstack slots exposed by the move) may or may not take on the values they have in memory, until a stackFlushFromMemory is executed
• if the memory above the various stack/frame pointers is modified, this may or many not be reflected in the corresponding smallstack locations, until a stackFlushFromMemory is executed
• if the smallstacks are modified, this may or many not be reflected in memory, until a stackFlushToMemory is executed
• if in between flushes, both the memory above the various stack/frame pointers is modified, and the smallstacks are modified, then upon flushing, each location may take either value (which may be mixed, eg some locs may take their values from memory and some from the smallstacks)
• bank the FP regs, but not the FP smallstacks. Have almost all caller-save fp regs as per https://stackoverflow.com/a/52175510/171761 's suggestion.

some benefits to this:

• the implementation can decide whether argument passing is actually in registers or actually in memory (same with return values)
• the implementation doesn't need to do any additional tracking of the input and output stack tops beyond what is in the program-visible registers
• using the naive stack cache implementation style, calls to leaf functions dont touch main memory to pass arguments

done

---

so is there a way to do the previous without actually importing stack cache addr mode semantics into Boot?

The issue is probably that we want to allow the implementation to choose to store the smallstacks in memory, or to store them in regs (or in a memory cache). But if they are in memory then that's visible to Boot. But they may or may not be in memory. This indeterminacy is visible and so must be mentioned in the spec.

Can we just tell Boot to put things on the stack in memory? If we want interoperability (programs mixing Boot and LOVM functions), that's hard for the implementation to detect and map into smallstacks. Imagine if a Boot function called a LOVM leaf function. The LOVM leaf function would not feel a need to flush anything (and we don't want to make it), because it wants to just use the output stack as its arguments, since it doesn't need fresh output stack for its own outgoing arguments. It can just not adjust the frame pointer, and offset its own locals off the stack pointer. But the Boot program put the input arguments onto the stack in memory.

Is there any point keeping LOVM separate from BootX? if we are putting all these complicated semantics into Boot?

There may be another way. It may be hard to detect a write to the stack pointer in general, but if we have a PUSH instruction, or even better a PUSHMEMSTACK instruction, and a POPMEMSTACK instruction, that is easier to detect. The implementation could intercept that instruction and have it write to the output smallstack cache instead. We could have flushStackToMemory and flushMemoryToStacks instructions and specify that until the are called, as above there are caching non-guarantees. The benefit of these gymnastics is that we maintain our load-store architecture and our address-mode-less architecture in Boot, rather than having these memory-associated locations be targettable by any operand.

why just push and pop? perhaps push, pop, read, and write. In fact, maybe just read and write -- then we can add the requirement that you flush before moving the stack pointer, which may make things even simpler for the implementation, b/c it doesn't have to keep track of stack ptr moves. Then we can drop this requirement for LOVM.

seems like this may make it harder to abstract stack frames later though? but maybe we are saving that for OVM.

i feel like there is a more abstract way to do this. But i can't think of anything that wouldn't be too abstract for Boot.

done (register-associated cache) ---

LOVM is looking more and more similar to Boot. Maybe just merge LOVM and BootX? (could use the name LOVM for something further up the stack later, as previously planned)

---

so i was thinking about calling conventions. I was hoping there was a way to do all of:

• allow Boot not to have CALL, RET, etc instructions, but to have a calling convention
• allow calling conventions to be abstract in LOVM (or, i guess i'm moving LOVM back into BootX?)
• allow Boot and LOVM to interoperate
• allow at least a few arguments to be passed in registers for syscalls
• not have addressing modes in Boot

i don't think it's possible. In fact, i don't think even the first three are possible simultaneously:

• if Boot has a calling convention, but not CALL, RET, etc, then that calling convention must be concrete
• if LOVM must interoperate with Boot, then LOVM must adhere to the same calling convention as Boot
• but if LOVM's calling convention is abstract, then CALL, RET, etc must be free to do something different than Boot's concrete calling convention

now, the main issue of them having different calling conventions is: what about the syscalls? Boot is supposed to be a subset of LOVM, so the syscalls should work the same in both cases.

which is also the reason we wanted to pass arguments in registers

so, we could just say that Boot passes stuff on the stack, but that means you have to have available stack memory to do a syscall, and also that you have to take the performance hit of hitting memory to do a syscall.

---

how does linux do syscalls on x86?

there are three types: legacy syscalls with the 'int' instruction, 'fast' 32-bit syscalls with the SYSENTER instruction, and 'fast' 32-bit system calls with the SYSCALL instruction.

With legacy syscalls, the syscall number and up to 6 args are passed in registers [10]

with fast 32-bit system calls, the syscall number and up to 5 args are passed in registers [11]

with fast 32-bit system calls, the syscall number and up to 6 args are passed in registers [12]