README

   1 README
   2 ------
   3
   4 This compiler is a big long chain of modules that transform l3 code into
   5 x86_64 assembly.
   6
   7 Here is a breakdown of the modules and changes from l2:
   8
   9   * The parser.  The parser was mainly brought in from lab 2, and mainly
  10     just a straight-forward extension of the l2 parser.  We added the
  11     ability to parse functions, function calls, and variable declarations.
  12
  13   * The typechecker.  This module is mostly the same as that from l2. It
  14     performs function-related typechecking as well now, such as ensuring
  15     that the correct number of arguments is supplied in a function call,
  16     that there are no multiple definitions of functions, and that there is a
  17     main function that takes only one argument.
  18
  19   * The translator was extended with a CALL.
  20
  21   * The munch module was also extended with the ability to munch CALL; a
  22     major improvement was made when we realized we could determine what
  23     expressions had effects and what had fixed registers. Any expressions
  24     that use no fixed registers and have no effects can be reordered during
  25     evaluation of a function call's arguments. This enabled us to save a
  26     bunch of register-register moves. Saving the caller save registers is
  27     left to the liveness analyzer, which we believe results in substantially
  28     better code than saving and restoring all caller saves.
  29
  30   * The liveness analyzer remains in more or less the same form, but with
  31     substantial performance and cleanliness improvements by replacing lists
  32     with maps (via BinaryMapFn) and sets (via ListSetFn). Also, a bug of
  33     incredible type A was discovered through much pain and suffering, and
  34     promptly fixed; it involved not realizing that a def on one line led to
  35     an interference on any succeeding lines. Somehow we got away with this
  36     for lab 2. Otherwise, we just explicitly state rules to generate
  37     def/use/succ predicates which we then iterate over to find a fixed point
  38     for livenesses using the standard rules.
  39
  40   * The grapher was changed to use the binary map and list set for
  41     performance boosts (needed to pass certain large tests, like
  42     pine-tree_print.l3). It generates an interference graph from a list of
  43     livenesses at each source line.
  44
  45   * The color orderer had no changes.
  46
  47   * The coloring module was slightly updated to recognize more fixed-color
  48     registers. It implements a greedy coloring algorithm.
  49
  50   * The solidifier was modified to change the callee save system. Now we
  51     only save the registers we need to. This improvement was pushed by
  52     excessively slow execution time on one of the tests.
  53
  54   * The peepholer is upgraded somewhat; it now eliminates more redundant
  55     instructions (such as adding/subtracting 0).
  56
  57   * The stringifier is of no interest to you, for it does real things that
  58     interact with the real world, and that is not of interest to people who
  59     write in ML.
  60
  61   * Our internal representation of x86 assembly was changed. In particular,
  62     conditional sets and jumps are now SETcc of cc * oper and Jcc of cc *
  63     oper, instead of a separate SET or J for each condition code. This
  64     simplifies other parts of the code as well.
  65
  66 We believe that it is fully functional. We generate correct code whenever we
  67 are supposed to, and we pass every test that we can lay our hands on
  68 (including all of l2, and one of ours that killed the reference compiler).
  69 Of course, our last bug was caught by only one failing test, so...