slack: first page rendering of real FoC data - mu - Soul of a tiny new machine. More thorough tests → More comprehensible and rewrite-friendly software → More resilient society.

diff options

author	Kartik K. Agaram <vc@akkartik.com>	2021-08-10 22:44:49 -0700
committer	Kartik K. Agaram <vc@akkartik.com>	2021-08-10 22:44:49 -0700
commit	76eceb2ca3efb63a8978da15257438ed0b02a867 (patch)
tree	9697d8f8f3eeec584e05784c42c0d0c278c6210a /browse-slack
parent	c407d842a4195a90e4e2bf5cbe14a6104a21142f (diff)
download	mu-76eceb2ca3efb63a8978da15257438ed0b02a867.tar.gz

slack: first page rendering of real FoC data

https://futureofcoding.org/community

Diffstat (limited to 'browse-slack')

-rw-r--r--

browse-slack/main.mu

1 files changed, 3 insertions, 3 deletions

=== Goal A memory-safe language with a simple translator to x86 that can be feasibly written without itself needing a translator. Memory-safe: it should be impossible to: a) create a pointer out of arbitrary data, or b) to access heap memory after it's been freed. Simple: do all the work in a 2-pass translator: Pass 1: check each instruction's types in isolation. Pass 2: emit code for each instruction in isolation. === Overview of the language A program consists of a series of type, function and global variable declarations. (Also constants and tests, but let's focus on these.) Type declarations basically follow Hindley-Milner with product and (tagged) sum types. Types are written in s-expression form. There's a `ref` type that's a type-safe fat pointer, with an alloc id that gets incremented after each allocation. Memory allocation and reclamation is manual. Dereferencing a ref after its underlying memory is reclaimed (pointer alloc id no longer matches payload alloc id) is guaranteed to immediately kill the program (like a segfault). # product type type foo [ x : int y : (ref int) z : bar ] # sum type choice bar [ x : int y : point ] Functions have a header and a series of instructions in the body: fn f a : int -> b : int [ ... ] Instructions have the following format: io1, io2, ... <- operation i1, i2, ... i1, i2 operands on the right hand side are immutable. io1, io2 are in-out operands. They're written to, and may also be read. User-defined functions will be called with the same syntax. They'll translate to a sequence of push instructions (one per operand, both in and in-out), a call instruction, and a sequence of pop instructions, either to a black hole (in operands) or a location (in-out operands). This follows the standard Unix calling convention. Each operand needs to be something push/pop can accept. Primitive operations depend on the underlying processor. We'd like each primitive operation supported by the language to map to a single instruction in the ISA. Sometimes we have to violate that (see below), but we definitely won't be writing to any temporary locations behind the scenes. The language affords control over registers, and tracking unused registers gets complex, and besides we may have no unused registers at a specific point. Instructions only modify their operands. In most ISAs, instructions operate on at most a word of data at a time. They also tend to not have more than 2-3 operands, and not modify more than 2 locations in memory. Since the number of reads from memory is limited, we break up complex high-level operations using a special type called `address`. Addresses are strictly short-term entities. They can't be stored in a compound type, and they can't be passed into or returned from a user-defined function. They also can't be used after a function call (because it could free the underlying memory) or label (because it gets complex to check control flow, and we want to translate each instruction simply and in isolation). === Compilation to 32-bit x86 Values can be stored: in code (literals) in registers on the stack on the global segment Variables on the stack are stored at *(ESP+n) Global variables are stored at *disp32, where disp32 is statically known Address variables have to be in a register. - You need them in a register to do a lookup, and - Saving them to even the stack increases the complexity of checks needed on function calls or labels. Compilation proceeds by pattern matching over an instruction along with knowledge about the types of its operands, as well as where they're stored (register/stack/global). We now enumerate mappings for various categories of instructions, based on the type and location of their operands. Where types of operands aren't mentioned below, all operands of an instruction should have the same (word-length) type. Lots of special cases because of limitations of the x86 ISA. Beware. A. x : int <- add y Requires y to be scalar. Result will always be an int. No pointer arithmetic. reg <- add literal => 81 0/subop 3/mod ...(0) reg <- add reg => 01 3/mod ...(1) reg <- add stack => 03 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 reg/r32 ...(2) reg <- add global => 03 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(3) stack <- add literal => 81 0/subop 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 literal/imm32 ...(4) stack <- add reg => 01 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 reg/r32 ...(5) stack <- add stack => disallowed stack <- add global => disallowed global <- add literal => 81 0/subop 0/mod 5/rm32/include-disp32 global/disp32 literal/imm32 ...(6) global <- add reg => 01 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(7) global <- add stack => disallowed global <- add global => disallowed Similarly for sub, and, or, xor and even copy. Replace the opcodes above with corresponding ones from this table: add sub and or xor copy/mov reg <- op literal 81 0/subop 81 5/subop 81 4/subop 81 1/subop 81 6/subop c7 reg <- op reg 01 or 03 29 or 2b 21 or 23 09 or 0b 31 or 33 89 or 8b reg <- op stack 03 2b 23 0b 33 8b reg <- op global 03 2b 23 0b 33 8b stack <- op literal 81 0/subop 81 5/subop 81 4/subop 81 1/subop 81 6/subop c7 stack <- op reg 01 29 21 09 31 89 global <- op literal 81 0/subop 81 5/subop 81 4/subop 81 1/subop 81 6/subop c7 global <- op reg 01 29 21 09 31 89 B. x/reg : int <- mul y Requires both y to be scalar. x must be in a register. Multiplies can't write to memory. reg <- mul literal => 69 ...(8) reg <- mul reg => 0f af 3/mod ...(9) reg <- mul stack => 0f af 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 reg/r32 ...(10) reg <- mul global => 0f af 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(11) C. x/EAX/quotient : int, y/EDX/remainder : int <- idiv z # divide EAX by z; store the result in EAX and EDX Requires source x and z to both be scalar. x must be in EAX and y must be in EDX. Divides can't write anywhere else. First clear EDX (we don't support ints larger than 32 bits): 31/xor 3/mod 2/rm32/EDX 2/r32/EDX then: EAX, EDX <- idiv literal => disallowed EAX, EDX <- idiv reg => f7 7/subop 3/mod ...(12) EAX, EDX <- idiv stack => f7 7/subop 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 ...(13) EAX, EDX <- idiv global => f7 7/subop 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(14) D. x : int <- not Requires x to be an int. reg <- not => f7 3/mod ...(15) stack <- not => f7 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 ...(16) global <- not => f7 0/mod 5/rm32/include-disp32 global/disp32 reg/r32 ...(17) E. x : (address t) <- get o : T, %f (Assumes T.f has type t.) o can't be on a register since it's a non-primitive (likely larger than a word) f is a literal x must be in a register (by definition for an address) below '*' works on either address or ref types For raw stack values we want to read *(ESP+n) For raw global values we want to read *disp32 For address stack values we want to read *(ESP+n)+ *(ESP+n) contains an address so we want to compute *(ESP+n) + literal reg1 <- get reg2, literal => 8d/lea 1/mod reg2/rm32 literal/disp8 reg1/r32 ...(18) reg <- get stack, literal => 8d/lea 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n+literal/disp8 reg/r32 ...(19) (simplifying assumption: stack frames can't be larger than 256 bytes) reg <- get global, literal => 8d/lea 0/mod 5/rm32/include-disp32 global+literal/disp32, reg/r32 ...(20) F. x : (offset T) <- index i : int, %size(T) reg1 <- index reg2, literal => 69/mul 3/mod reg2/rm32 literal/imm32 -> reg1/r32 or 68/mul 3/mod reg2/rm32 literal/imm8 -> reg1/r32 ...(21) reg1 <- index stack, literal => 69/mul 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n/disp8 literal/imm32 -> reg1/r32 ...(22) reg1 <- index global, literal => 69/mul 0/mod 5/rm32/include-disp32 global/disp32 literal/imm32 -> reg1/r32 ...(23) optimization: avoid multiply if literal is a power of 2 use SIB byte if literal is 2, 4 or 8 or left shift G. x : (address T) <- advance o : (array T), idx : (offset T) reg <- advance a/reg, idx/reg => 8d/lea 0/mod 4/rm32/SIB a/base idx/index 0/scale reg/r32 ...(24) reg <- advance stack, literal => 8d/lea 1/mod 4/rm32/SIB 4/base/ESP 4/index/none 0/scale n+literal/disp8 reg/r32 ...(25) reg <- advance stack, reg2 => 8d/lea 1/mod 4/rm32/SIB 4/base/ESP reg2/index 0/scale n/disp8 reg/r32 ...(26) reg <- advance global, literal => 8d/lea 0/mod 5/rm32/include-disp32 global+literal/disp32, reg/r32 ...(27) also instructions for runtime bounds checking === Example Putting it all together: code generation for `a[i].y = 4` where a is an array of 2-d points with x, y coordinates. If a is allocated on the stack, say of type (array point 6) at (ESP+4): offset/EAX : (offset point) <- index i, 8 # (22) tmp/EBX : (address point) <- advance a : (array point 6), offset/EAX # (26) tmp2/ECX : (address number) <- get tmp/EBX : (address point), 4/y # (18) *tmp2/ECX <- copy 4 # (5 for copy/mov with 0 disp8) Many instructions, particularly variants of 'get' and 'advance' -- end up encoding the exact same instructions. But the types differ, and the type-checker checks them differently. === Advanced checks Couple of items require inserting mapping to multiple instructions: bounds checking against array length in 'advance' dereferencing 'ref' types (see type list up top) A. Dereferencing a ref tmp/EDX <- advance *s, tmp0/EDI => compare (ESP+4), *(ESP+8) ; '*' from compiler2 jump-unless-equal panic EDX <- add ESP, 8 EDX <- copy *EDX EDX <- add EDX, 4 EDX <- 8d/lea EDX + result === More speculative ideas Initialize data segment with special extensible syntax for literals. All literals except numbers and strings start with %. %size(type) => compiler replaces with size of type %point(3, 4) => two words and so on. === Credits Forth C Rust Lisp qhasm


context:
space:
mode: