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?]]