1 # The Mu computer's level-2 language, also called Mu.
   2 # http://akkartik.name/post/mu-2019-2
   3 #
   4 # To run:
   5 #   $ ./ntranslate init.linux 0*.subx apps/mu.subx
   6 
   7 # == Goals
   8 # 1. Be memory safe. It should be impossible to corrupt the heap, or to create
   9 # a bad pointer. (Requires strong type safety.)
  10 # 2. Do as little as possible to achieve goal 1.
  11 #   - runtime checks to avoid complex static analysis
  12 #   - minimize impedance mismatch between source language and SubX target
  13 
  14 # == Language description
  15 # A program is a sequence of function definitions.
  16 #
  17 # Function example:
  18 #   fn foo n: int -> result/eax: int {
  19 #     ...
  20 #   }
  21 #
  22 # Functions consist of a name, optional inputs, optional outputs and a block.
  23 #
  24 # Function inputs and outputs are variables. All variables have a type and
  25 # storage specifier. They can be placed either in memory (on the stack) or in
  26 # one of 6 named registers.
  27 #   eax ecx edx ebx esi edi
  28 # Variables in registers must be primitive 32-bit types.
  29 # Variables not explicitly placed in a register are on the stack.
  30 # Variables in registers need not have a name; in that case you refer to them
  31 # directly by the register name.
  32 #
  33 # Function inputs are always passed in memory (on the stack), while outputs
  34 # are always returned in registers.
  35 #
  36 # Blocks mostly consist of statements.
  37 #
  38 # Statements mostly consist of a name, optional inputs and optional outputs.
  39 #
  40 # Statement inputs are variables or literals. Variables need to specify type
  41 # (and storage) the first time they're mentioned but not later.
  42 #
  43 # Statement outputs, like function outputs, must be variables in registers.
  44 #
  45 # Statement names must be either primitives or user-defined functions.
  46 #
  47 # Primitives can write to any register.
  48 # User-defined functions only write to hard-coded registers. Outputs of each
  49 # call must have the same registers as in the function definition.
  50 #
  51 # There are some other statement types:
  52 #   - blocks. Multiple statements surrounded by '{...}' and optionally
  53 #     prefixed with a label name and ':'
  54 #       - {
  55 #           ...
  56 #         }
  57 #       - foo: {
  58 #           ...
  59 #         }
  60 #
  61 #   - variable definitions on the stack. E.g.:
  62 #       - var foo: int
  63 #       - var bar: (array int 3)
  64 #     There's no initializer; variables are automatically initialized.
  65 #
  66 #   - variables definitions in a register. E.g.:
  67 #       - var foo/eax : int <- add bar 1
  68 #     The initializer is mandatory and must be a valid instruction that writes
  69 #     a single output to the right register. In practice registers will
  70 #     usually be either initialized by primitives or copied from eax.
  71 #       - var eax : int <- foo bar quux
  72 #         var floo/ecx : int <- copy eax
  73 #
  74 # Still todo:
  75 #   global variables
  76 #   heap allocations (planned name: 'handle')
  77 #   user-defined types: 'type' for structs, 'choice' for unions
  78 #   short-lived 'address' type for efficiently writing inside nested structs
  79 #
  80 # Formal types:
  81 #   A program is a linked list of functions
  82 #   A function contains:
  83 #     name: string
  84 #     inouts: linked list of var-types  <-- 'inouts' is more precise than 'inputs'
  85 #     outputs: linked list of var-types
  86 #     body: block
  87 #   A var-type contains:
  88 #     name: string
  89 #     type: s-expression of type ids
  90 #   Statements are not yet fully designed.
  91 #   statement = var definition or simple statement or block
  92 #   block = linked list of statements
  93 
  94 # == Translation
  95 # Now that we know what the language looks like in the large, let's think
  96 # about how translation happens from the bottom up. The interplay between
  97 # variable scopes and statements using variables is the most complex aspect of
  98 # translation.
  99 #
 100 # Assume that we maintain a 'functions' list while parsing source code. And a
 101 # 'primitives' list is a global constant. Both these contain enough information
 102 # to perform type-checking on function calls or primitive statements, respectively.
 103 #
 104 # Defining variables pushes them on a stack with the current block depth and
 105 # enough information about their location (stack offset or register id).
 106 # Starting a block increments the current block id.
 107 # Each statement now has enough information to emit code for it.
 108 # Ending a block is where the magic happens:
 109 #   pop all variables at the current block depth
 110 #   emit code to restore all register variables introduced at the current depth
 111 #   emit code to clean up all stack variables at the current depth (just increment esp)
 112 #   decrement the current block depth
 113 #
 114 # One additional check we'll need is to ensure that a variable in a register
 115 # isn't shadowed by a different one. That may be worth a separate data
 116 # structure but for now repeatedly scanning the var stack should suffice.
 117 #
 118 # Formal types:
 119 #   functions, primitives: linked list of info
 120 #     name: string
 121 #     inouts: linked list of var-types
 122 #     outputs: linked list of var-types
 123 #   vars: linked list (stack) of info
 124 #     name: string
 125 #     type: s-expression? Just a type id for now.
 126 #     block: int
 127 #     location: int (negative numbers are on the stack;
 128 #                    0-7 are in registers;
 129 #                    higher positive numbers are currently invalid)
 130 
 131 # == Compiling a single instruction
 132 # Determine the function or primitive being called.
 133 #   If no matches, show all functions/primitives with the same name, along
 134 #   with reasons they don't match. (type and storage checking)
 135 #   It must be a function if:
 136 #     #outputs > 1, or
 137 #     #inouts > 2, or
 138 #     #inouts + #outputs > 2
 139 # If it's a function, emit:
 140 #   (low-level-name <rm32 or imm32>...)
 141 # Otherwise (it's a primitive):
 142 #   assert(#inouts <= 2 && #outs <= 1 && (#inouts + #outs) <= 2)
 143 #   emit opcode
 144 #   emit-rm32(inout[0])
 145 #   if out[0] exists: emit-r32(out[0])
 146 #   else if inout[1] is a literal: emit-imm32(inout[1])
 147 #   else: emit-rm32(inout[1])
 148 
 149 # emit-rm32 and emit-r32 should check that the variable they intend is still
 150 # available in the register.
 151 
 152 # == Emitting a block
 153 # Emit block name if necessary
 154 # Emit '{'
 155 # When you encounter a statement, emit it as above
 156 # When you encounter a variable declaration
 157 #   emit any code needed for it (bzeros)
 158 #   push it on the var stack
 159 #   update register dict if necessary
 160 # When you encounter '}'
 161 #   While popping variables off the var stack until block id changes
 162 #     Emit code needed to clean up the stack
 163 #       either increment esp
 164 #       or pop into appropriate register
 165 #   TODO: how to update the register dict? does it need to be a stack as well?
 166 
 167 # The rest is straightforward.
 168 
 169 == data
 170 
 171 Program:  # (address function)
 172   0/imm32
 173 
 174 == code
 175 
 176 Entry:
 177     # . prologue
 178     89/<- %ebp 4/r32/esp
 179     (new-segment Heap-size Heap)
 180     # if (argv[1] == "test') run-tests()
 181     {
 182       # if (argc <= 1) break
 183       81 7/subop/compare *ebp 1/imm32
 184       7e/jump-if-lesser-or-equal break/disp8
 185       # if (argv[1] != "test") break
 186       (kernel-string-equal? *(ebp+8) "test")  # => eax
 187       3d/compare-eax-and 0/imm32
 188       74/jump-if-equal break/disp8
 189       #
 190       (run-tests)
 191       # syscall(exit, *Num-test-failures)
 192       8b/-> *Num-test-failures 3/r32/ebx
 193       eb/jump $mu-main:end/disp8
 194     }
 195     # otherwise convert Stdin
 196     (convert-mu Stdin Stdout)
 197     (flush Stdout)
 198     # syscall(exit, 0)
 199     bb/copy-to-ebx 0/imm32
 200 $mu-main:end:
 201     b8/copy-to-eax 1/imm32/exit
 202     cd/syscall 0x80/imm8
 203 
 204 convert-mu:  # in : (address buffered-file), out : (address buffered-file)
 205     # . prologue
 206     55/push-ebp
 207     89/<- %ebp 4/r32/esp
 208     #
 209     (parse-mu *(ebp+8))
 210     (check-mu-types)
 211     (emit-subx *(ebp+0xc))
 212 $convert-mu:end:
 213     # . epilogue
 214     89/<- %esp 5/r32/ebp
 215     5d/pop-to-ebp
 216     c3/return
 217 
 218 test-convert-empty-input:
 219     # empty input => empty output
 220     # . prologue
 221     55/push-ebp
 222     89/<- %ebp 4/r32/esp
 223     # setup
 224     (clear-stream _test-input-stream)
 225     (clear-stream _test-input-buffered-file->buffer)
 226     (clear-stream _test-output-stream)
 227     (clear-stream _test-output-buffered-file->buffer)
 228     #
 229     (convert-mu _test-input-buffered-file _test-output-buffered-file)
 230     (flush _test-output-buffered-file)
 231     (check-stream-equal _test-output-stream "" "F - test-convert-empty-input")
 232     # . epilogue
 233     89/<- %esp 5/r32/ebp
 234     5d/pop-to-ebp
 235     c3/return
 236 
 237 test-convert-function-skeleton:
 238     # empty function decl => function prologue and epilogue
 239     #   fn foo {
 240     #   }
 241     # =>
 242     #   foo:
 243     #     # . prologue
 244     #     55/push-ebp
 245     #     89/<- %ebp 4/r32/esp
 246     #     # . epilogue
 247     #     89/<- %esp 5/r32/ebp
 248     #     5d/pop-to-ebp
 249     #     c3/return
 250     # . prologue
 251     55/push-ebp
 252     89/<- %ebp 4/r32/esp
 253     # setup
 254     (clear-stream _test-input-stream)
 255     (clear-stream _test-input-buffered-file->buffer)
 256     (clear-stream _test-output-stream)
 257     (clear-stream _test-output-buffered-file->buffer)
 258     #
 259     (write _test-input-stream "fn foo {\n")
 260     (write _test-input-stream "}\n")
 261     # convert
 262     (convert-mu _test-input-buffered-file _test-output-buffered-file)
 263     (flush _test-output-buffered-file)
 264 +--  6 lines: #?     # dump _test-output-stream --------------------------------------------------------------------------------------------------------------
 270     # check output
 271     (check-next-stream-line-equal _test-output-stream "foo:"                  "F - test-convert-function-skeleton/0")
 272     (check-next-stream-line-equal _test-output-stream "# . prologue"          "F - test-convert-function-skeleton/1")
 273     (check-next-stream-line-equal _test-output-stream "55/push-ebp"           "F - test-convert-function-skeleton/2")
 274     (check-next-stream-line-equal _test-output-stream "89/<- %ebp 4/r32/esp"  "F - test-convert-function-skeleton/3")
 275     (check-next-stream-line-equal _test-output-stream "# . epilogue"          "F - test-convert-function-skeleton/4")
 276     (check-next-stream-line-equal _test-output-stream "89/<- %esp 5/r32/ebp"  "F - test-convert-function-skeleton/5")
 277     (check-next-stream-line-equal _test-output-stream "5d/pop-to-ebp"         "F - test-convert-function-skeleton/6")
 278     (check-next-stream-line-equal _test-output-stream "c3/return"             "F - test-convert-function-skeleton/7")
 279     # . epilogue
 280     89/<- %esp 5/r32/ebp
 281     5d/pop-to-ebp
 282     c3/return
 283 
 284 test-convert-multiple-function-skeletons:
 285     # multiple functions correctly organized into a linked list
 286     #   fn foo {
 287     #   }
 288     #   fn bar {
 289     #   }
 290     # =>
 291     #   foo:
 292     #     # . prologue
 293     #     55/push-ebp
 294     #     89/<- %ebp 4/r32/esp
 295     #     # . epilogue
 296     #     89/<- %esp 5/r32/ebp
 297     #     5d/pop-to-ebp
 298     #     c3/return
 299     #   bar:
 300     #     # . prologue
 301     #     55/push-ebp
 302     #     89/<- %ebp 4/r32/esp
 303     #     # . epilogue
 304     #     89/<- %esp 5/r32/ebp
 305     #     5d/pop-to-ebp
 306     #     c3/return
 307     # . prologue
 308     55/push-ebp
 309     89/<- %ebp 4/r32/esp
 310     # setup
 311     (clear-stream _test-input-stream)
 312     (clear-stream _test-input-buffered-file->buffer)
 313     (clear-stream _test-output-stream)
 314     (clear-stream _test-output-buffered-file->buffer)
 315     #
 316     (write _test-input-stream "fn foo {\n")
 317     (write _test-input-stream "}\n")
 318     (write _test-input-stream "fn bar {\n")
 319     (write _test-input-stream "}\n")
 320     # convert
 321     (convert-mu _test-input-buffered-file _test-output-buffered-file)
 322     (flush _test-output-buffered-file)
 323 +--  6 lines: #?     # dump _test-output-stream --------------------------------------------------------------------------------------------------------------
 329     # check first function
 330     (check-next-stream-line-equal _test-output-stream "foo:"                  "F - test-convert-multiple-function-skeletons/0")
 331     (check-next-stream-line-equal _test-output-stream "# . prologue"          "F - test-convert-multiple-function-skeletons/1")
 332     (check-next-stream-line-equal _test-output-stream "55/push-ebp"           "F - test-convert-multiple-function-skeletons/2")
 333     (check-next-stream-line-equal _test-output-stream "89/<- %ebp 4/r32/esp"  "F - test-convert-multiple-function-skeletons/3")
 334     (check-next-stream-line-equal _test-output-stream "# . epilogue"          "F - test-convert-multiple-function-skeletons/4")
 335     (check-next-stream-line-equal _test-output-stream "89/<- %esp 5/r32/ebp"  "F - test-convert-multiple-function-skeletons/5")
 336     (check-next-stream-line-equal _test-output-stream "5d/pop-to-ebp"         "F - test-convert-multiple-function-skeletons/6")
 337     (check-next-stream-line-equal _test-output-stream "c3/return"             "F - test-convert-multiple-function-skeletons/7")
 338     # check second function
 339     (check-next-stream-line-equal _test-output-stream "bar:"                  "F - test-convert-multiple-function-skeletons/10")
 340     (check-next-stream-line-equal _test-output-stream "# . prologue"          "F - test-convert-multiple-function-skeletons/11")
 341     (check-next-stream-line-equal _test-output-stream "55/push-ebp"           "F - test-convert-multiple-function-skeletons/12")
 342     (check-next-stream-line-equal _test-output-stream "89/<- %ebp 4/r32/esp"  "F - test-convert-multiple-function-skeletons/13")
 343     (check-next-stream-line-equal _test-output-stream "# . epilogue"          "F - test-convert-multiple-function-skeletons/14")
 344     (check-next-stream-line-equal _test-output-stream "89/<- %esp 5/r32/ebp"  "F - test-convert-multiple-function-skeletons/15")
 345     (check-next-stream-line-equal _test-output-stream "5d/pop-to-ebp"         "F - test-convert-multiple-function-skeletons/16")
 346     (check-next-stream-line-equal _test-output-stream "c3/return"             "F - test-convert-multiple-function-skeletons/17")
 347     # . epilogue
 348     89/<- %esp 5/r32/ebp
 349     5d/pop-to-ebp
 350     c3/return
 351 
 352 test-convert-function-with-arg:
 353     # function with one arg and a copy instruction
 354     #   fn foo n : int -> result/eax : int {
 355     #     result <- copy n
 356     #   }
 357     # =>
 358     #   foo:
 359     #     # . prologue
 360     #     55/push-ebp
 361     #     89/<- %ebp 4/r32/esp
 362     #     {
 363     #     # result <- copy n
 364     #     8b/-> *(ebp+8) 0/r32/eax
 365     #     }
 366     #     # . epilogue
 367     #     89/<- %esp 5/r32/ebp
 368     #     5d/pop-to-ebp
 369     #     c3/return
 370     # . prologue
 371     55/push-ebp
 372     89/<- %ebp 4/r32/esp
 373     # setup
 374     (clear-stream _test-input-stream)
 375     (clear-stream _test-input-buffered-file->buffer)
 376     (clear-stream _test-output-stream)
 377     (clear-stream _test-output-buffered-file->buffer)
 378     #
 379     (write _test-input-stream "fn foo {\n")
 380     (write _test-input-stream "}\n")
 381     # convert
 382     (convert-mu _test-input-buffered-file _test-output-buffered-file)
 383     (flush _test-output-buffered-file)
 384 +--  6 lines: #?     # dump _test-output-stream --------------------------------------------------------------------------------------------------------------
 390     # check output
 391     (check-next-stream-line-equal _test-output-stream "foo:"                  "F - test-convert-function-skeleton/0")
 392     (check-next-stream-line-equal _test-output-stream "# . prologue"          "F - test-convert-function-skeleton/1")
 393     (check-next-stream-line-equal _test-output-stream "55/push-ebp"           "F - test-convert-function-skeleton/2")
 394     (check-next-stream-line-equal _test-output-stream "89/<- %ebp 4/r32/esp"  "F - test-convert-function-skeleton/3")
 395     (check-next-stream-line-equal _test-output-stream "# . epilogue"          "F - test-convert-function-skeleton/4")
 396     (check-next-stream-line-equal _test-output-stream "89/<- %esp 5/r32/ebp"  "F - test-convert-function-skeleton/5")
 397     (check-next-stream-line-equal _test-output-stream "5d/pop-to-ebp"         "F - test-convert-function-skeleton/6")
 398     (check-next-stream-line-equal _test-output-stream "c3/return"             "F - test-convert-function-skeleton/7")
 399     # . epilogue
 400     89/<- %esp 5/r32/ebp
 401     5d/pop-to-ebp
 402     c3/return
 403 
 404 parse-mu:  # in : (address buffered-file)
 405     # pseudocode
 406     #   var curr-function = Program
 407     #   var line : (stream byte 512)
 408     #   var word-slice : slice
 409     #   while true                                  # line loop
 410     #     clear-stream(line)
 411     #     read-line-buffered(in, line)
 412     #     if (line->write == 0) break               # end of file
 413     #     while true                                # word loop
 414     #       word-slice = next-word-or-string(line)
 415     #       if slice-empty?(word-slice)             # end of line
 416     #         break
 417     #       else if slice-starts-with?(word-slice, "#")  # comment
 418     #         break                                 # end of line
 419     #       else if slice-equal(word-slice, "fn")
 420     #         var new-function : (address function) = new function
 421     #         populate-mu-function(in, new-function)
 422     #         *curr-function = new-function
 423     #         curr-function = &new-function->next
 424     #       else
 425     #         abort()
 426     #
 427     # . prologue
 428     55/push-ebp
 429     89/<- %ebp 4/r32/esp
 430     # . save registers
 431     50/push-eax
 432     51/push-ecx
 433     52/push-edx
 434     57/push-edi
 435     # var line/ecx : (stream byte 512)
 436     81 5/subop/subtract %esp 0x200/imm32
 437     68/push 0x200/imm32/length
 438     68/push 0/imm32/read
 439     68/push 0/imm32/write
 440     89/<- %ecx 4/r32/esp
 441     # var word-slice/edx : slice
 442     68/push 0/imm32/end
 443     68/push 0/imm32/start
 444     89/<- %edx 4/r32/esp
 445     # var curr-function/edi : (address function) = Program
 446     bf/copy-to-edi Program/imm32
 447     {
 448 $parse-mu:line-loop:
 449       (clear-stream %ecx)
 450       (read-line-buffered *(ebp+8) %ecx)
 451       # if (line->write == 0) break
 452       81 7/subop/compare *ecx 0/imm32
 453       0f 84/jump-if-equal break/disp32
 454 +--  6 lines: #?       # dump line ---------------------------------------------------------------------------------------------------------------------------
 460       { # word loop
 461 $parse-mu:word-loop:
 462         (next-word-or-string %ecx %edx)
 463         # if slice-empty?(word-slice) break
 464         (slice-empty? %edx)
 465         3d/compare-eax-and 0/imm32
 466         0f 85/jump-if-not-equal break/disp32
 467         # if (*word-slice->start == "#") break
 468         # . eax = *word-slice->start
 469         8b/-> *edx 0/r32/eax
 470         8a/copy-byte *eax 0/r32/AL
 471         81 4/subop/and %eax 0xff/imm32
 472         # . if (eax == '#') break
 473         3d/compare-eax-and 0x23/imm32/hash
 474         0f 84/jump-if-equal break/disp32
 475         # if (slice-equal?(word-slice, "fn")) parse a function
 476         {
 477           (slice-equal? %edx "fn")
 478           3d/compare-eax-and 0/imm32
 479           0f 84/jump-if-equal break/disp32
 480           # var new-function/eax : (address function) = populate-mu-function()
 481           (allocate Heap *Function-size)  # => eax
 482           (populate-mu-function-header %ecx %eax)
 483           (populate-mu-function-body *(ebp+8) %eax)
 484           # *curr-function = new-function
 485           89/<- *edi 0/r32/eax
 486           # curr-function = &new-function->next
 487           8d/address-> *(eax+0x10) 7/r32/edi
 488           e9/jump $parse-mu:word-loop/disp32
 489         }
 490         # otherwise abort
 491         e9/jump $parse-mu:abort/disp32
 492       } # end word loop
 493       e9/jump loop/disp32
 494     } # end line loop
 495 $parse-mu:end:
 496     # . reclaim locals
 497     81 0/subop/add %esp 0x214/imm32
 498     # . restore registers
 499     5f/pop-to-edi
 500     5a/pop-to-edx
 501     59/pop-to-ecx
 502     58/pop-to-eax
 503     # . epilogue
 504     89/<- %esp 5/r32/ebp
 505     5d/pop-to-ebp
 506     c3/return
 507 
 508 $parse-mu:abort:
 509     # error("unexpected top-level command: " word-slice "\n")
 510     (write-buffered Stderr "unexpected top-level command: ")
 511     (write-buffered Stderr %edx)
 512     (write-buffered Stderr "\n")
 513     (flush Stderr)
 514     # . syscall(exit, 1)
 515     bb/copy-to-ebx  1/imm32
 516     b8/copy-to-eax  1/imm32/exit
 517     cd/syscall  0x80/imm8
 518     # never gets here
 519 
 520 # errors considered:
 521 #   fn foo { {
 522 #   fn foo { }
 523 #   fn foo { } {
 524 #   fn foo  # no block
 525 populate-mu-function-header:  # first-line : (address stream byte), out : (address function)
 526     # . prologue
 527     55/push-ebp
 528     89/<- %ebp 4/r32/esp
 529     # . save registers
 530     50/push-eax
 531     51/push-ecx
 532     57/push-edi
 533     # edi = out
 534     8b/-> *(ebp+0xc) 7/r32/edi
 535     # var word-slice/ecx : slice
 536     68/push 0/imm32/end
 537     68/push 0/imm32/start
 538     89/<- %ecx 4/r32/esp
 539     # save function name
 540     (next-word *(ebp+8) %ecx)
 541     (slice-to-string Heap %ecx)  # => eax
 542     89/<- *edi 0/r32/eax
 543     # assert that next token is '{'
 544     (next-word *(ebp+8) %ecx)
 545     (slice-equal? %ecx "{")
 546     3d/compare-eax-and 0/imm32
 547     74/jump-if-equal $populate-mu-function-header:abort/disp8
 548     # assert that there's no further token
 549     {
 550       # word-slice = next-word(line)
 551       (next-word *(ebp+8) %ecx)
 552       # if (word-slice == '') break
 553       (slice-empty? %ecx)
 554       3d/compare-eax-and 0/imm32
 555       75/jump-if-not-equal break/disp8
 556       # if (slice-starts-with?(word-slice, "#")) break
 557       # . eax = *word-slice->start
 558       8b/-> *edx 0/r32/eax
 559       8a/copy-byte *eax 0/r32/AL
 560       81 4/subop/and %eax 0xff/imm32
 561       # . if (eax == '#') break
 562       3d/compare-eax-and 0x23/imm32/hash
 563       74/jump-if-equal break/disp8
 564       # otherwise abort
 565       eb/jump $populate-mu-function-header:abort/disp8
 566     }
 567 $populate-mu-function-header:end:
 568     # . reclaim locals
 569     81 0/subop/add %esp 8/imm32
 570     # . restore registers
 571     5f/pop-to-edi
 572     59/pop-to-ecx
 573     58/pop-to-eax
 574     # . epilogue
 575     89/<- %esp 5/r32/ebp
 576     5d/pop-to-ebp
 577     c3/return
 578 
 579 $populate-mu-function-header:abort:
 580     # error("function header not in form 'fn <name> {'")
 581     (write-buffered Stderr "function header not in form 'fn <name> {' -- '")
 582     (rewind-stream *(ebp+8))
 583     (write-stream 2 *(ebp+8))
 584     (write-buffered Stderr "'\n")
 585     (flush Stderr)
 586     # . syscall(exit, 1)
 587     bb/copy-to-ebx  1/imm32
 588     b8/copy-to-eax  1/imm32/exit
 589     cd/syscall  0x80/imm8
 590     # never gets here
 591 
 592 # errors considered:
 593 #   { abc
 594 populate-mu-function-body:  # in : (address buffered-file), out : (address function)
 595     # . prologue
 596     55/push-ebp
 597     89/<- %ebp 4/r32/esp
 598     # . save registers
 599     50/push-eax
 600     51/push-ecx
 601     52/push-edx
 602     53/push-ebx
 603     # var line/ecx : (stream byte 512)
 604     81 5/subop/subtract %esp 0x200/imm32
 605     68/push 0x200/imm32/length
 606     68/push 0/imm32/read
 607     68/push 0/imm32/write
 608     89/<- %ecx 4/r32/esp
 609     # var word-slice/edx : slice
 610     68/push 0/imm32/end
 611     68/push 0/imm32/start
 612     89/<- %edx 4/r32/esp
 613     # var open-curly-count/ebx : int = 1
 614     bb/copy-to-ebx 1/imm32
 615     { # line loop
 616 $populate-mu-function-body:line-loop:
 617       # if (open-curly-count == 0) break
 618       81 7/subop/compare %ebx 0/imm32
 619       0f 84/jump-if-equal break/disp32
 620       # line = read-line-buffered(in)
 621       (clear-stream %ecx)
 622       (read-line-buffered *(ebp+8) %ecx)
 623       # if (line->write == 0) break
 624       81 7/subop/compare *ecx 0/imm32
 625       0f 84/jump-if-equal break/disp32
 626       # word-slice = next-word(line)
 627       (next-word %ecx %edx)
 628       # if slice-empty?(word-slice) continue
 629       (slice-empty? %ecx)
 630       3d/compare-eax-and 0/imm32
 631       75/jump-if-not-equal loop/disp8
 632       # if (slice-starts-with?(word-slice, '#') continue
 633       # . eax = *word-slice->start
 634       8b/-> *edx 0/r32/eax
 635       8a/copy-byte *eax 0/r32/AL
 636       81 4/subop/and %eax 0xff/imm32
 637       # . if (eax == '#') continue
 638       3d/compare-eax-and 0x23/imm32/hash
 639       74/jump-if-equal loop/disp8
 640       {
 641         # if slice-equal?(word-slice, "{") ++open-curly-count
 642         {
 643           (slice-equal? %ecx "{")
 644           3d/compare-eax-and 0/imm32
 645           74/jump-if-equal break/disp8
 646           43/increment-ebx
 647           eb/jump $curly-found:end/disp8
 648         }
 649         # else if slice-equal?(word-slice, "}") --open-curly-count
 650         {
 651           (slice-equal? %ecx "}")
 652           3d/compare-eax-and 0/imm32
 653           74/jump-if-equal break/disp8
 654           4b/decrement-ebx
 655           eb/jump $curly-found:end/disp8
 656         }
 657         # else break
 658         eb/jump $populate-mu-function-body:end/disp8
 659       }
 660       # - check for invalid tokens after curly
 661 $curly-found:end:
 662       # second-word-slice = next-word(line)
 663       (next-word %ecx %edx)
 664       # if slice-empty?(second-word-slice) continue
 665       (slice-empty? %ecx)
 666       3d/compare-eax-and 0/imm32
 667       0f 85/jump-if-not-equal loop/disp32
 668       # if (slice-starts-with?(second-word-slice, '#') continue
 669       # . eax = *second-word-slice->start
 670       8b/-> *edx 0/r32/eax
 671       8a/copy-byte *eax 0/r32/AL
 672       81 4/subop/and %eax 0xff/imm32
 673       # . if (eax == '#') continue
 674       3d/compare-eax-and 0x23/imm32/hash
 675       0f 84/jump-if-equal loop/disp32
 676       # abort
 677       eb/jump $populate-mu-function-body:abort/disp8
 678     } # end line loop
 679 $populate-mu-function-body:end:
 680     # . reclaim locals
 681     81 0/subop/add %esp 0x214/imm32
 682     # . restore registers
 683     5b/pop-to-ebx
 684     5a/pop-to-edx
 685     59/pop-to-ecx
 686     58/pop-to-eax
 687     # . epilogue
 688     89/<- %esp 5/r32/ebp
 689     5d/pop-to-ebp
 690     c3/return
 691 
 692 $populate-mu-function-body:abort:
 693     # error("'{' or '}' should be on its own line, but got '")
 694     (write-buffered Stderr "'{' or '}' should be on its own line, but got '")
 695     (rewind-stream %ecx)
 696     (write-stream 2 %ecx)
 697     (write-buffered Stderr "'\n")
 698     (flush Stderr)
 699     # . syscall(exit, 1)
 700     bb/copy-to-ebx  1/imm32
 701     b8/copy-to-eax  1/imm32/exit
 702     cd/syscall  0x80/imm8
 703     # never gets here
 704 
 705 check-mu-types:
 706     # . prologue
 707     55/push-ebp
 708     89/<- %ebp 4/r32/esp
 709     #
 710 $check-types:end:
 711     # . epilogue
 712     89/<- %esp 5/r32/ebp
 713     5d/pop-to-ebp
 714     c3/return
 715 
 716 emit-subx:  # out : (address buffered-file)
 717     # . prologue
 718     55/push-ebp
 719     89/<- %ebp 4/r32/esp
 720     # . save registers
 721     50/push-eax
 722     51/push-ecx
 723     57/push-edi
 724     # edi = out
 725     8b/-> *(ebp+8) 7/r32/edi
 726     # var curr/ecx : (address function) = Program
 727     8b/-> *Program 1/r32/ecx
 728     {
 729       # if (curr == NULL) break
 730       81 7/subop/compare %ecx 0/imm32
 731       0f 84/jump-if-equal break/disp32
 732       (emit-subx-function %edi %ecx)
 733       # curr = curr->next
 734       8b/-> *(ecx+0x10) 1/r32/ecx
 735       e9/jump loop/disp32
 736     }
 737 $emit-subx:end:
 738     # . restore registers
 739     5f/pop-to-edi
 740     59/pop-to-ecx
 741     58/pop-to-eax
 742     # . epilogue
 743     89/<- %esp 5/r32/ebp
 744     5d/pop-to-ebp
 745     c3/return
 746 
 747 # == Emitting a function
 748 # Emit function header
 749 # Emit function prologue
 750 # Translate function body
 751 # Emit function epilogue
 752 
 753 emit-subx-function:  # out : (address buffered-file), f : (address function)
 754     # . prologue
 755     55/push-ebp
 756     89/<- %ebp 4/r32/esp
 757     # . save registers
 758     50/push-eax
 759     51/push-ecx
 760     57/push-edi
 761     # edi = out
 762     8b/-> *(ebp+8) 7/r32/edi
 763     # ecx = f
 764     8b/-> *(ebp+0xc) 1/r32/ecx
 765     #
 766     (write-buffered %edi *ecx)
 767     (write-buffered %edi ":\n")
 768     (emit-subx-prologue %edi)
 769     (emit-subx-block %edi *(ecx+4))  # TODO: offset
 770     (emit-subx-epilogue %edi)
 771 $emit-subx-function:end:
 772     # . restore registers
 773     5f/pop-to-edi
 774     59/pop-to-ecx
 775     58/pop-to-eax
 776     # . epilogue
 777     89/<- %esp 5/r32/ebp
 778     5d/pop-to-ebp
 779     c3/return
 780 
 781 emit-subx-block:  # out : (address buffered-file), block : (address block)
 782     # . prologue
 783     55/push-ebp
 784     89/<- %ebp 4/r32/esp
 785     #
 786 $emit-subx-block:end:
 787     # . epilogue
 788     89/<- %esp 5/r32/ebp
 789     5d/pop-to-ebp
 790     c3/return
 791 
 792 emit-subx-statement:  # out : (address buffered-file), stmt : (address statement), vars : (address variable), regs : (address array (address variable)), primitives : (address opcode-info), functions : (address function)
 793     # . prologue
 794     55/push-ebp
 795     89/<- %ebp 4/r32/esp
 796     # . save registers
 797     50/push-eax
 798     51/push-ecx
 799     # var curr/ecx : (address primitive) = primitives
 800     8b/-> *(ebp+0x18) 1/r32/ecx
 801     {
 802       # if (curr != null) abort
 803       81 7/subop/compare *(ebp+0xc) 0/imm32
 804       0f 84/jump-if-equal $emit-subx-statement:abort/disp32
 805       # if (match(curr, stmt)) break
 806       (mu-stmt-matches-primitive? *(ebp+0xc) %ecx)  # => eax
 807       3d/compare-eax-and 0/imm32
 808       75/jump-if-not-equal break/disp8
 809       # emit code for stmt according to curr and vars
 810       # curr = curr->next
 811       8b/-> *(ecx+0x10) 1/r32/ecx
 812       e9/jump loop/disp32
 813     }
 814 $emit-subx-statement:end:
 815     # . restore registers
 816     59/pop-to-ecx
 817     58/pop-to-eax
 818     # . epilogue
 819     89/<- %esp 5/r32/ebp
 820     5d/pop-to-ebp
 821     c3/return
 822 
 823 $emit-subx-statement:abort:
 824     # error("couldn't translate '" stmt "'\n")
 825     (write-buffered Stderr "couldn't translate '")
 826 #?     (emit-string Stderr *(ebp+0xc))  # TODO
 827     (write-buffered Stderr "'\n")
 828     (flush Stderr)
 829     # . syscall(exit, 1)
 830     bb/copy-to-ebx  1/imm32
 831     b8/copy-to-eax  1/imm32/exit
 832     cd/syscall  0x80/imm8
 833     # never gets here
 834 
 835 mu-stmt-matches-primitive?:  # stmt : (address statement), primitive : (address opcode-info) => result/eax : boolean
 836     # . prologue
 837     55/push-ebp
 838     89/<- %ebp 4/r32/esp
 839     # . save registers
 840     51/push-ecx
 841     # return primitive->name == stmt->operation
 842     8b/-> *(ebp+8) 1/r32/ecx
 843     8b/-> *(ebp+0xc) 0/r32/eax
 844     (string-equal? *ecx *eax)  # => eax
 845 $mu-stmt-matches-primitive?:end:
 846     # . restore registers
 847     59/pop-to-ecx
 848     # . epilogue
 849     89/<- %esp 5/r32/ebp
 850     5d/pop-to-ebp
 851     c3/return
 852 
 853 test-emit-subx-statement-primitive:
 854     # Primitive operation on a variable on the stack.
 855     #   increment foo
 856     # =>
 857     #   ff 0/subop/increment *(ebp-8)
 858     #
 859     # There's a variable on the var stack as follows:
 860     #   name: 'foo'
 861     #   type: int
 862     #   location: -8  (negative numbers are on the stack;
 863     #                   0-7 are in registers;
 864     #                   higher positive numbers are invalid)
 865     #
 866     # There's nothing in registers.
 867     #
 868     # There's a primitive with this info:
 869     #   name: 'increment'
 870     #   inout: int/mem
 871     #   value: 'ff 0/subop/increment'
 872     #
 873     # There's nothing in functions.
 874     #
 875     # . prologue
 876     55/push-ebp
 877     89/<- %ebp 4/r32/esp
 878     # setup
 879     (clear-stream _test-output-stream)
 880     (clear-stream _test-output-buffered-file->buffer)
 881     # . ecx = vars
 882     68/push 0/imm32/next
 883     68/push -8/imm32/stack-offset
 884     68/push 0/imm32/int  # TODO
 885     68/push "foo"/imm32
 886     89/<- %ecx 4/r32/esp
 887     # . edx = operand
 888     68/push 0/imm32/next
 889     51/push-ecx/var-foo
 890     89/<- %edx 4/r32/esp
 891     # . edx = stmt
 892     68/push 0/imm32/next
 893     68/push 0/imm32/outputs
 894     52/push-edx/operand
 895     68/push "increment"/imm32/operation
 896     89/<- %edx 4/r32/esp
 897     # . ebx = primitives
 898     68/push 0/imm32/next
 899     68/push "ff 0/subop/increment"/imm32
 900     68/push 0/imm32/type-int
 901     68/push 0/imm32/storage-memory
 902     68/push "increment"/imm32/name
 903     89/<- %ebx 4/r32/esp
 904     # convert
 905     (emit-subx-statement _test-output-buffered-file %edx %ecx 0 %ebx 0)
 906     (flush _test-output-buffered-file)
 907 +--  6 lines: #?     # dump _test-output-stream --------------------------------------------------------------------------------------------------------------
 913     # check output
 914     (check-next-stream-line-equal _test-output-stream "ff 0/subop/increment *(ebp-8)" "F - test-emit-subx-statement-primitive/0")
 915     # . reclaim locals
 916     81 0/subop/add %esp 0x3c/imm32
 917     # . epilogue
 918     89/<- %esp 5/r32/ebp
 919     5d/pop-to-ebp
 920     c3/return
 921 
 922 test-emit-subx-statement-function-call:
 923     # Call a function on a variable on the stack.
 924     #   f var
 925     # =>
 926     #   (f2 *(ebp-8))
 927     # (Changing the function name just to help disambiguate things.)
 928     #
 929     # There's a variable on the var stack as follows:
 930     #   name: 'var'
 931     #   type: int
 932     #   location: -8  (negative numbers are on the stack;
 933     #                   0-7 are in registers;
 934     #                   higher positive numbers are invalid)
 935     #
 936     # There's nothing in registers.
 937     #
 938     # There's nothing in primitives.
 939     #
 940     # There's a function with this info:
 941     #   name: 'f'
 942     #   inout: int/mem
 943     #   value: 'f2'
 944     #
 945     # . prologue
 946     55/push-ebp
 947     89/<- %ebp 4/r32/esp
 948     # setup
 949     (clear-stream _test-output-stream)
 950     (clear-stream _test-output-buffered-file->buffer)
 951     # . ecx = vars
 952     68/push 0/imm32/next
 953     68/push -8/imm32/stack-offset
 954     68/push 0/imm32/int  # TODO
 955     68/push "var"/imm32
 956     89/<- %ecx 4/r32/esp
 957     # . edx = operand
 958     68/push 0/imm32/next
 959     51/push-ecx/var
 960     89/<- %edx 4/r32/esp
 961     # . edx = stmt
 962     68/push 0/imm32/next
 963     68/push 0/imm32/outputs
 964     52/push-edx/operand
 965     68/push "f"/imm32/operation
 966     89/<- %edx 4/r32/esp
 967     # . ebx = functions
 968     68/push 0/imm32/next
 969     68/push "f2"/imm32
 970     68/push 0/imm32/type-int
 971     68/push 0/imm32/storage-memory
 972     68/push "f"/imm32/name
 973     89/<- %ebx 4/r32/esp
 974     # convert
 975     (emit-subx-statement _test-output-buffered-file %edx %ecx 0 0 %ebx)
 976     (flush _test-output-buffered-file)
 977 +--  6 lines: #?     # dump _test-output-stream --------------------------------------------------------------------------------------------------------------
 983     # check output
 984     (check-next-stream-line-equal _test-output-stream "f2 *(ebp-8)" "F - test-emit-subx-statement-function-call/0")
 985     # . reclaim locals
 986     81 0/subop/add %esp 0x3c/imm32
 987     # . epilogue
 988     89/<- %esp 5/r32/ebp
 989     5d/pop-to-ebp
 990     c3/return
 991 
 992 emit-subx-prologue:  # out : (address buffered-file)
 993     # . prologue
 994     55/push-ebp
 995     89/<- %ebp 4/r32/esp
 996     #
 997     (write-buffered *(ebp+8) "# . prologue\n")
 998     (write-buffered *(ebp+8) "55/push-ebp\n")
 999     (write-buffered *(ebp+8) "89/<- %ebp 4/r32/esp\n")
1000 $emit-subx-prologue:end:
1001     # . epilogue
1002     89/<- %esp 5/r32/ebp
1003     5d/pop-to-ebp
1004     c3/return
1005 
1006 emit-subx-epilogue:  # out : (address buffered-file)
1007     # . prologue
1008     55/push-ebp
1009     89/<- %ebp 4/r32/esp
1010     #
1011     (write-buffered *(ebp+8) "# . epilogue\n")
1012     (write-buffered *(ebp+8) "89/<- %esp 5/r32/ebp\n")
1013     (write-buffered *(ebp+8) "5d/pop-to-ebp\n")
1014     (write-buffered *(ebp+8) "c3/return\n")
1015 $emit-subx-epilogue:end:
1016     # . epilogue
1017     89/<- %esp 5/r32/ebp
1018     5d/pop-to-ebp
1019     c3/return