From 77e8ce989010fbd94080e780fb0b5cb6c10434e8 Mon Sep 17 00:00:00 2001 From: Irene Knapp Date: Mon, 28 Sep 2026 18:07:52 -0700 Subject: move all the source files into subdirectories and rename one, linux-dynamic.e to language/dynamic/linux.e. also make sure all references in comments and documentation refer to the new locations and names. this directory structure reflects code organization which had existed in Irenes' head, but was likely not obvious to other readers. now hopefully it is more discoverable. Force-Push: yes Change-Id: Icfef3eae812a50fe20202191999e68e1f7db445a --- compilation/labels.e | 296 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 296 insertions(+) create mode 100644 compilation/labels.e (limited to 'compilation/labels.e') diff --git a/compilation/labels.e b/compilation/labels.e new file mode 100644 index 0000000..2a02a4c --- /dev/null +++ b/compilation/labels.e @@ -0,0 +1,296 @@ +~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +~ ~~ Machine label facility ~~ +~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +~ +~ Compilers and assemblers always have a need to resolve symbolic names for +~ parts of their code to numeric values. Usually, these symbolic names are +~ called labels. +~ +~ It's a surprisingly deep problem. The output itself can end up depending +~ on the actual values, for a variety of reasons. For example, the size of +~ a relative-jump instruction may vary depending on how far away its target +~ is, which changes the position of everything after. Or, there may be a size +~ limit on some particular segment and code may have to be entirely +~ reorganized to make things fit, splitting it into pieces or adding +~ trampolines. +~ +~ Often, this winds up being a hidden layer with immense complexity, +~ implemented as part of a linker, that even compiler maintainers find obscure +~ and confusing. +~ +~ It's Irenes' position that we should engage with complexity rather than +~ encysting it. So, in Evocation we take a different approach, heavily +~ inspired by the semantics of a tool called flatassembler. We provide +~ downstream code with the basic operations set-label and use-label which it +~ can combine in whatever order it wants. We also provide a harness, +~ label-loop, which takes an execution token for the downstream code +~ generator and runs it over and over, computing the mathematical fixed point +~ of the label assignments. +~ +~ On the first pass, label-loop guesses a value of zero for any label that's +~ used before it's set. On subsequent passes, each label starts with the value +~ it had on the previous pass. When we have a pass where labels end with the +~ same value they started with, we say they've converged, and we announce +~ success. If a hundred passes go by without convergence, we fail instead. +~ +~ Importantly, the label facility does not have an opinion on where or how +~ the values of labels should be output, nor does it have concepts of +~ dependency tracking or topological sorting. It only cares about the sequence +~ of set- and use-operations. Code relying on the facility is free to make +~ arbitrarily complex decisions about the layout, size, contents etc of its +~ output, and to use label values as part of those decisions. It is the +~ responsibility of this relying code to ensure the process converges, by +~ whatever means it wishes. +~ +~ Since the label facility is not directly involved in output, it is also +~ permissible for code relying on it to make retroactive changes to the +~ output, as long as all such changes are completed before returning control +~ to label-loop. +~ +~ Most of the time, the shorthand words L@' and L!' will be all you need to +~ use from your own code. + +~ The labels data structure is a linked list of dictionary entries, with +~ the same header format as the main Evocation dictionary, but instead of +~ being executable, each holds two words of data: status bits, and a value, +~ in that order. There's no "docol" pointer or anything of the sort. +~ +~ Status is a bit field: +~ bit zero is whether it's been used +~ bit one is whether it's been defined +~ bit two is whether it was used before being defined +~ bit three is whether the guessed value wound up equaling the actual value +~ +~ Just as the Evocation dictionary uses the global variable "latest" as a +~ handle (a pointer to a pointer) beginning a linked list of entries, so the +~ label dictionary also uses a handle variable, named "labels". We initialize +~ it here. +8 allocate s" labels" variable 0 labels ! + +~ This is analogous to word-heading, but prints label information. +~ (entry pointer --) +: label-heading + dup entry-to-name dup emitstring space + stringlen 1+ 54 swap - 0 max indent + entry-to-execution-token dup 8 + @ .hex64 space @ .hex8 + newline ; + +~ This prints the headings for all the labels that have been created. Note +~ that labels that have been created once stay in the dictionary forever, even +~ if subsequent passes neither use nor define them. That's because the control +~ loop has no way to know if they're still important; it's up to downstream +~ code to decide that. Everything has been carefully set up so that disused +~ labels don't hurt anything. +: list-labels + labels oldest-entry-in { dup } + { dup label-heading labels next-newer-entry-in } while drop ; + +~ This looks up a label by name if it exists, or returns 0 if it doesn't. +~ The return value if it's found is an entry pointer. +~ +~ Keep in mind that this is a pointer to the entry in the label dictionary, +~ not the label's value. It's common for a label's value to itself be a +~ pointer to a dictionary entry, in the program being compiled, so it's easy +~ to confuse that. +~ +~ (name string pointer -- label entry pointer) +: find-label labels swap find-in ; + +~ This creates a new label given a name for it, initializing its value and +~ status to zero and adding it to the label dictionary. This is responsible +~ for the initial guess of zero on the first pass. +~ +~ (name string pointer -- ) +: new-label labels create-in 0 , 0 , ; + +~ These helpers take a label entry pointer and return pointers to the status +~ and value fields. +: label-status entry-to-execution-token ; +: label-value entry-to-execution-token 8 + ; + +~ This looks up a label by name if it exists, or creates it if it doesn't. +~ Either way, it returns an entry pointer. It's named after the function +~ "intern" that many Lisp dialects have. +~ +~ (name string pointer -- label entry pointer) +: intern-label + dup find-label + dup { swap drop } + { drop dup new-label labels swap find-in } if-else ; + +~ This returns the value of a label, also doing all necessary status checks +~ and updates to keep track of the circumstances under which it was used. The +~ label loop relies on all read accesses going through this word. +~ +~ (label entry pointer -- label value) +: use-label + ~ If it hasn't been defined yet, mark it used-before-set. + dup label-status dup @ dup 0x02 & not + { 0x04 | swap ! } { drop drop } if-else + + ~ Mark it used. It's faster to just do this than to check if it's needed. + dup label-status dup @ 0x01 | swap ! + + ~ TODO putting a provide-label magic comment command here would be lovely + + ~ Return the guessed value. + label-value @ ; + +~ This overwrites the value of a label, also doing all necessary status +~ checks and updates to keep track of the cirumstances under which it was +~ set. The label loop relies on all write accesses going through this word. +~ +~ (new label value, label entry pointer --) +: set-label + dup label-status @ + ~ (new value, entry, initial status) + + ~ Exit, and print a diagnostic, if the label was already set on this pass. + ~ + ~ Without cooperation from user code, there's no great way to communicate + ~ up the call stack that execution should stop, so we don't try to. + dup 0x02 & { drop swap drop + ." Failed by attempting to redefine " + entry-to-name emitstring newline exit } if + + ~ We always set the defined bit to true. We leave the other status bits + ~ as-is, except that we check whether it's unused up to now, and whether + ~ the previous value equals the new value. If either of those holds, we set + ~ the guessed-equals-actual bit to true. + 0x02 | + ~ (new value, entry, updated status) + 3unroll dup 4 unroll label-value @ swap dup 3unroll = + ~ (entry, updated status, new value, equality) + 3roll dup 4 unroll 0x01 & not + ~ (entry, updated status, new value, equality, unused) + || { swap 0x08 | swap } if + ~ (entry, updated status, new value) + 3roll dup 3unroll + ~ (updated status, entry, new value, entry) + label-value ! label-status ! ; + +~ Since labels have dictionary entry headers but aren't in the main +~ dictionary, we get to use the entry flag bits for other things. The only one +~ we have right now is a feature that acts as a hint to anything trying to +~ display metadata about labels, to the effect that this one represents +~ something other than an offset in the file. +~ +~ (label entry pointer --) +: set-label-non-offset dup entry-flags@ 0x01 | swap entry-flags! ; +~ (label entry pointer -- boolean) +: is-label-non-offset entry-flags@ 0x01 & ; + +~ This is a convenience helper which downstream code can use to check how +~ many bytes it has output thus-far. +~ (output memory start, current output point +~ -- output memory start, current output point, offset) +: current-offset 2dup swap - ; + +~ This is a concise syntax for referencing the entry pointer of a label, +~ when you know its name statically. It reads a word of text input and calls +~ intern-label on it. +: L' + word value@ + interpreter-flags @ 0x01 & + { ' litstring entry-to-execution-token , + here @ swap packstring 8 packalign here ! + ' intern-label entry-to-execution-token , + dropstring } + { intern-label dropstring-with-result } if-else + ; make-immediate + +~ This is a concise syntax for calling use-label with a label whose name +~ you know statically. It performs L', then calls use-label. +: L@' + ' L' entry-to-execution-token execute + interpreter-flags @ 1 & + { ' use-label entry-to-execution-token , } + { use-label } if-else + ; make-immediate + +~ This is a concise syntax for calling set-label with a label whose name +~ you know statically. It performs L', then calls set-label. +: L!' + ' L' entry-to-execution-token execute + interpreter-flags @ 1 & + { ' set-label entry-to-execution-token , } + { set-label } if-else + ; make-immediate + +~ This is an internal helper that label-loop uses to check if a specific +~ label entry has "converged", based on its status bits. Downstream code won't +~ need to call this directly. +~ +~ For a label to have "converged", at least one of the following must be +~ true: +~ +~ 1. The label must never have been used (bit zero clear); +~ 2. The label was both used and defined, but not used before it was defined +~ (bits zero and one set; bit two clear); +~ 3. The label was both used and defined, and the guessed value equalled the +~ actual value (bits zero, one, and three set). +~ +~ (label entry pointer -- boolean) +: check-label-converged + label-status @ + dup 0x01 & not swap + dup 0x03 & 0x03 = swap dup 0x04 & not swap 3unroll && swap + 0x0b & 0x0b = + || || ; + +~ This is an internal helper that label-loop uses to check if the overall +~ label assignments have converged, based on their status bits. Downstream +~ code won't need to call this directly. +~ +~ This returns true if and only if check-label-converged returns true for +~ all the labels that have been created. +~ +~ (-- boolean) +: check-labels-converged + 1 + labels @ { dup } + { dup check-label-converged 3roll && swap + @ } while drop ; + +~ This is an internal helper that label-loop calls between passes, to update +~ the status bits and get ready for the next one. Downstream code won't need +~ to call this directly. +~ +: reset-labels + labels @ { dup } + { dup label-status 0 swap ! + @ } while drop ; + +~ This is the top-level word that invokes the entire label system. All the +~ code generation happens inside it. +~ +~ The execution token it's passed should have the interface: +~ +~ (output start, current output pointer +~ -- output start, current output pointer) +~ +~ In general, this is the same interface that code generation words should +~ use to communicate with each other. For example, all the words in +~ compilation/elf.e use this interface. +~ +~ (execution token -- output start, output length) +: label-loop + 0 swap + ~ TODO every time you double this to fix a crash, you must publicly + ~ apologize for deferring a real fix. those are the rules + 0x80000 allocate dup + ~ (iteration count, execution token, output start, output point) + { 3 pick 100 > } + { 2 pick execute 4 roll 1+ 4 unroll + + check-labels-converged + { 4 roll drop + 3 roll drop + current-offset swap drop + exit } if + drop dup + reset-labels } while + ~ TODO run some analysis on the labels to detect labels that are never + ~ defined, but are referenced. List them. + drop drop drop ." Failed after " . ." iterations." newline ; + -- cgit 1.4.1