path: root/transect/compiler10

=== Goal

A memory-safe language with a simple translator to x86 that can be feasibly written without itself needing a translator/compiler.

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 statement's types in isolation.
  Pass 2: emit code for each statement in isolation.

=== Language summary

Program organization is going to be fairly conventional and in the spirit of C: programs will consist of a series of type, global and function declarations. More details below. Functions will consist of a list of statements, each containing a single operation. Since we try to map directly to x86 instructions, combinations of operations and operands will not be orthogonal. You won't be able to operate at once on two memory locations, for example, since no single x86 instruction can do that.

Statement operands will be tagged with where they lie. This mostly follows C: local variables are on the stack, and variables not on the stack are in the global segment. The one addition is that you can lay out (only word-size) variables on registers. This is kinda like C's `register` keyword, but not quite: if you don't place a variable on a register, you are *guaranteed* it won't be allocated a register. Programmers do register allocation in this language.

The other memorable feature of the language is two kinds of pointers: a 'ref' is a fat pointer manually allocated on the heap, and an 'address' is a far more ephemeral thing described below.

--- Ref

Refs are used to manage heap allocations. They are fat pointers that augment the address of a payload with an allocation id. On x86 a ref requires 8 bytes: 4 for the address, and 4 for the alloc id. Refs can only ever point to the start of a heap allocation. Never within a heap allocation, and *certainly* never to the stack or global segment.

How alloc ids work: Every heap allocation allocates an additional word of space for an alloc id in the payload, and stores a unique alloc id in the payload as well as the pointer returned to the caller. Reclaiming an allocation resets the payload's alloc id. As long as alloc ids are always unique, and as long as refs can never point to within a heap allocation, we can be guaranteed that a stale pointer whose payload has been reclaimed will end up with a mismatch between pointer alloc id and payload alloc id.

  x <- alloc   # x's alloc id and *x's alloc id will be the same, say A
  y <- copy x  # y also has alloc id A
  free x       # x's alloc id is now 0, as is *x's alloc id
  ..*y..       # y's alloc id is A, but *y's alloc id is 0, so we can signal an error
  z <- alloc   # say z reuses the same address, but now with a new alloc id A'
  ..*y..       # y's alloc id is A, but *y's alloc id is A', so we can signal an error

--- Address

Since our statements are really simple, many operations may take multiple statements. To stitch a more complex computation like `A[i].f = 34` across multiple statements, we need addresses.

Addresses can be used to manage any memory address. They can point inside objects, on the stack, heap or global segment. Since they are so powerful we greatly restrict their use. Addresses can only be stored in a register, never in memory on the stack or global segment. Since user-defined types will usually not fit on a register, we forbid addresses in any user-defined types. Since an address may point inside a heap allocation that can be freed, and since `free` will be a function call, addresses will not persist across function calls. Analyzing control flow to find intervening function calls can be complex, so addresses will not persist across basic block boundaries.

The key open question with this language: can we find *clear* rules of address use that *don't complicate* programs, and that keep the type system *sound*?

=== Language syntax

The type system basically follows Hindley-Milner with product and (tagged) sum types. In addition we have address and ref types. Type declarations have the following syntax:

  # 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 statements in the body:

  fn f a : int b : int -> b : int [
    ...
  ]

Statements 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.

Two example programs:

  i) Factorial:

    fn factorial n : int -> result/EAX : int [
      result/EAX <- copy 1
      {
        compare n, 1
        break-if <=
        var tmp/EBX : int
        tmp/EBX <- copy n
        tmp/EBX <- subtract 1
        var tmp2/EAX : int
        tmp2/EAX <- call factorial, tmp/EBX
        result/EAX <- multiply tmp2/EAX, n
      }
      return result/EAX
    ]

  ii) Writing to a global variable:

    var x : char

    fn main [
      call read, 0/stdin, x, 1/size
      result/EAX <- call write, 1/stdout, x, 1/size
      call exit, result/EAX
    ]

One thing to note: variables refer to addresses (not to be confused with the `address` type) just like in Assembly. We'll uniformly use '*' to indicate getting at the value in an address. This will also provide a consistent hint of the addressing mode.

=== Compilation strategy

--- User-defined statements

User-defined functions will be called with the same syntax as primitives. 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:

  push EBP
  copy ESP to EBP
  push arg 1
  push arg 2
  ...
  call
  pop arg n
  ...
  pop arg 1
  copy EBP to ESP
  pop ESP

Implication: each function argument needs to be something push/pop can accept. It can't be an address, so arrays and structs will either have to be passed by value, necessitating copies, or allocated on the heap. We may end up allocating members of structs in separate heap allocations just so we can pass them piecemeal to helper functions. (Mu has explored this trade-off in the past.)

--- Primitive statements

Operands may be:
  in code (literals)
  in registers
  on the stack
  on the global segment

Operands are always scalar. Variables on the stack or global segment are immutable references.

  - Variables on the stack are stored at addresses like *(EBP+n)
  - Global variables are stored at addresses like *disp32, where disp32 is a statically known constant

  #define local(n)  1/mod 4/rm32/SIB 5/base/EBP 4/index/none 0/scale n/disp8
  #define disp32(N) 0/mod 5/rm32/include-disp32 N/disp32

Since the language will not be orthogonal, compilation proceeds by pattern matching over a statement 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 statements, based on the type and location of their operands.

Many statements will end up encoding to the exact same x86 instructions. But the types differ, and they get type-checked differently along the way.

A. x : int <- add y

  Requires y to be scalar (32 bits). 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 5/base/EBP 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 5/base/EBP 4/index/none 0/scale n/disp8 literal/imm32                          ...(4)
  stack <- add reg      => 01 1/mod 4/rm32/SIB 5/base/EBP 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 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 5/base/EBP 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 results 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 5/base/EBP 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 (weird syntax, but we'll ignore that)

  Requires x to be an int.

  reg <- not                => f7 3/mod                                                                                               ...(15)
  stack <- not              => f7 1/mod 4/rm32/SIB 5/base/EBP 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)

  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 5/base/EBP 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)

  This statement is used to translate an array index (denominated in the type of array elements) into an offset (denominated in bytes). It's just a multiply but with a new type for the result so that we can keep the type system sound.

  Since index statements translate to multiplies, 'x' must be a register.
  The %size(T) argument is statically known, so will always be a literal.

  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 5/base/EBP 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)

G. x : (address T) <- advance a : (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 5/base/EBP 4/index/none 0/scale n+literal/disp8 reg/r32                  ...(25)
  reg <- advance stack, reg2      => 8d/lea 1/mod 4/rm32/SIB 5/base/EBP 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)

=== 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):

  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)

=== More complex statements

A couple of statement types expand to multiple instructions:
  Function calls. We've already seen these above.
  Bounds checking against array length in 'advance'
  Dereferencing 'ref' types (see type list up top). Requires an alloc id check.

G'. Bounds checking the 'advance' statement begins with a few extra instructions. For example:

  x/EAX : (address T) <- advance a : (array T), literal

Suppose array 'a' lies on the stack starting at EBP+4. Its length will be at EBP+4, and the actual contents of the array will start from EBP+8.

 compare *(EBP+4), literal
 jump-if-greater panic          # rudimentary error handling

Now we're ready to perform the actual 'lea':

  lea EBP+8 + literal, reg      # line 25 above

H. Dereferencing a 'ref' needs to be its own statement, yielding an address. This statement has two valid forms:

  reg : (address T) <- deref stack : (ref T)
  reg : (address T) <- deref global : (ref T)

Since refs need 8 bytes they can't be in a register. And of course the output is an address so it must be in a register.

Compiling 'deref' will take a few instructions. Consider the following example where 's' is on the stack, say starting at EBP+4:

  EDX : (address T) <- deref s : (ref T)

The alloc id of 's' is at *(EBP+4) and the actual address is at *(EBP+8). The above statement will compile down to the following:

  EDX/s <- copy *(EBP+8)         # the address stored in s
  EDX/alloc-id <- copy *EDX      # alloc id of payload *s
  compare EDX, *(EBP+4)          # compare with alloc id of pointer
  jump-unless-equal panic        # rudimentary error handling
  # compute *(EBP+8) + 4
  EDX <- copy *(EBP+8)           # recompute the address in s because we can't save the value anywhere)
  EDX <- add EDX, 4              # skip alloc id this time

Subtleties:
  a) if the alloc id of the payload is 0, then the payload is reclaimed
  b) looking up the payload's alloc id *could* cause a segfault. What to do?

=== More speculative ideas

Initialize data segment with special extensible syntax for literals. All literals except numbers and strings start with %. Global variable declarations would now look like:

  var s : (array character) = "abc"  # exception to the '%' convention
  var p : point = %point(3, 4)

=== Credits

Forth
C
Rust
Lisp
qhasm