Initial import of l3c

[snipe.git] / README

README
------

This compiler is a big long chain of modules that transform l3 code into
x86_64 assembly.

Here is a breakdown of the modules and changes from l2:

  * The parser.  The parser was mainly brought in from lab 2, and mainly
    just a straight-forward extension of the l2 parser.  We added the
    ability to parse functions, function calls, and variable declarations.

  * The typechecker.  This module is mostly the same as that from l2. It
    performs function-related typechecking as well now, such as ensuring
    that the correct number of arguments is supplied in a function call,
    that there are no multiple definitions of functions, and that there is a
    main function that takes only one argument.

  * The translator was extended with a CALL.

  * The munch module was also extended with the ability to munch CALL; a
    major improvement was made when we realized we could determine what
    expressions had effects and what had fixed registers. Any expressions
    that use no fixed registers and have no effects can be reordered during
    evaluation of a function call's arguments. This enabled us to save a
    bunch of register-register moves. Saving the caller save registers is
    left to the liveness analyzer, which we believe results in substantially
    better code than saving and restoring all caller saves.

  * The liveness analyzer remains in more or less the same form, but with
    substantial performance and cleanliness improvements by replacing lists
    with maps (via BinaryMapFn) and sets (via ListSetFn). Also, a bug of
    incredible type A was discovered through much pain and suffering, and
    promptly fixed; it involved not realizing that a def on one line led to
    an interference on any succeeding lines. Somehow we got away with this
    for lab 2. Otherwise, we just explicitly state rules to generate
    def/use/succ predicates which we then iterate over to find a fixed point
    for livenesses using the standard rules.

  * The grapher was changed to use the binary map and list set for
    performance boosts (needed to pass certain large tests, like
    pine-tree_print.l3). It generates an interference graph from a list of
    livenesses at each source line.

  * The color orderer had no changes.

  * The coloring module was slightly updated to recognize more fixed-color
    registers. It implements a greedy coloring algorithm.

  * The solidifier was modified to change the callee save system. Now we
    only save the registers we need to. This improvement was pushed by
    excessively slow execution time on one of the tests.

  * The peepholer is upgraded somewhat; it now eliminates more redundant
    instructions (such as adding/subtracting 0).

  * The stringifier is of no interest to you, for it does real things that
    interact with the real world, and that is not of interest to people who
    write in ML.

  * Our internal representation of x86 assembly was changed. In particular,
    conditional sets and jumps are now SETcc of cc * oper and Jcc of cc *
    oper, instead of a separate SET or J for each condition code. This
    simplifies other parts of the code as well.

We believe that it is fully functional. We generate correct code whenever we
are supposed to, and we pass every test that we can lay our hands on
(including all of l2, and one of ours that killed the reference compiler).
Of course, our last bug was caught by only one failing test, so...