imin

A compiler for (a subset of) Racket -> x86-64, written in Racket

TODO

• Add tests that have nested ifs in then/else positions
• Add tests that have ifs in assignments

Resources

• Harvard assembly tutorial
• x86-64 for the compiler writer
• x86-64 cheatsheet
• Indiana University compiler course
• Original ICFP pearl on nanopass compilers
• Andy Keep dissertation on nanopass compilers
• An Incremental Approach to Compiler Construction, Nada Amin's implementation (which can compile itself!)
• Partial computation, Yoshihiko Futamura
• Interference graphs of programs in SSA-form
• Racket nanopass library
• Intel x86 Manual

Adding compiler tests

1. Add a .rkt test file in /tests, e.g.

; /tests/var_test_12.rkt
(let ([x (read)])
  (+ x 2))

2. Add a .in file containing inputs to all the read calls, e.g.

; /tests/var_test_12.in
3

3. Add a .res file containingt the expected output, e.g.

; /test/var_test_12.res
5

4. Run tests

racket run-tests.rkt

Debugging assembly with gdb

1. Compile the .s file with -g to generate debugging symbols, e.g.

  gcc -g var_test_11.s

2. Load the .out file into gdb

  gdb var_test_11.out

3. Set break points by passing addresses via <label> + <offset>, e.g.

  (gdb) info break
  No breakpoints or watchpoints.
  (gdb) break *main+2
  Breakpoint 1 at 0x1124: file var_test_11.s, line 8.

Use del <number> to delete breakpoint (number comes from info break). 4. Use run to step through the program, stopping at each break point and cont to continue till the next breakpoint. Use info registers to inspect register contents, print/<bxd> <reg> to print contents of register <reg> in binary/hex/decimal, e.g.

  (gdb) print/d $rax

prints the contents of register rax in decimal 5. Use info frame to show stack frame info and x/<offset><bxd><bhwg> <addr> to examine contents at that address. E.g.

  (gdb) x/4xw $sp

prints "four words (w) of memory above the stack pointer (here, $sp) in hexadecimal (x)".

Editing run-tests.rkt

• The passes variable ins run-tests.rkt runs the passes in the very order.

Using the runtime for IO

The runtime.c file needs to be compiled and linked with the assembly code that the compiler produces. To compile runtime.c, do the following

   gcc -c -g -std=c99 runtime.c

This will produce a file named runtime.o. The -g flag is to tell the compiler to produce debug information.

Next, suppose the compiler has translated the Racket program in file foo.rkt into the x86 assembly program in file foo.s (The .s filename extension is the standard one for assembly programs.) To produce an executable program, do

  gcc -g runtime.o foo.s

which will produce the executable program named a.out.

Interesting bugs so far

• In the shrink pass, I had implemented <= as

  (match e
    ...
    [(Prim '<= `(,e1 ,e2))
     (let ([e1 (shrink-exp e1)]
           [e2 (shrink-exp e2)])
       (If (Prim '< `(,e1 ,e2)) (Bool #t) (Prim 'eq? `(,e1 ,e2))))]
    ...)
  

  how ever, this duplicates e1 and e2! A compiler must never duplicate code -- in this case, this duplication can introduce issues if either of them are a (read) call, since the compiled program may potentially have to read the file twice instead of once!
• Before a tail call, the callee-saved registers must be popped-off from the stack. However, observe that if a callee-saved register is being used as the argument to TailJmp, we have an absurdity! The function address first gets leaqed into a callee-saved register, but then all callee-saved registers get poped, so this leaq is overwritten and jmp's target is not what we want it to be.

Notes

• rsp must always be of the form 8 + 16 * n, for some natural n. If pushqs/popqs break this alignment, it must be realigned via subq. For instance, if rsp (which always gets pushqed in all functions) and rbx (say function uses it locally) get pushqed, then the stack is currently aligned to 8 + 8 = 16 bytes, which isn't 8+16n. So subq $8, %rsp must be generated to realign to 8+16n. If only rbp were being pushed, then this extra subq would not have been necessary.
• Stuff that lazy explicate control achieves
  1. Avoids duplicate block generation
  2. Avoids dead block generation