-(* README
- * Author: Frank Pfenning <fp@cs.cmu.edu>
- *)
-
------------------------------------------------------------------------
-Welcome to 15-411 F08!
------------------------------------------------------------------------
-
-This is some starter code for the L1 compiler you have to build for
-the Lab1. It contains a lexer, parser, translator, and even a code
-generator, except that the code generator creates pseudo assembly
-language with fictitious instructions and an unlimited number of
-registers. We took some care to use good style (according to the
-instructor); you may consider this a model for your own coding. Feel
-free to modify any and all of this code as you see fit.
-
-Bug reports to the instructor Frank Pfenning <fp@cs.cmu.edu> are
-particularly welcome and will be noted in the extra credit category.
-
------------------------------------------------------------------------
-SML Notes
------------------------------------------------------------------------
-There are many different compilers for SML, perhaps the most
-popular ones are
-
- SML/NJ -- http://www.smlnj.org/
- MLton -- http://www.mlton.org/
- Poly/ML -- http://www.polyml.org/
-
-In this class we will be using SML/NJ v110.59. Please make sure your
-code compiles under specifically this version on the lab machines
-where it is the default and can be invoked simply with "sml" in a
-shell.
-
-If you develop your implementation on other machines, similar versions
-of SML/NJ are likely to be compatible, but you should certainly check
-your code on the lab machines.
-
-For (almost universal) Standard Basis Libraries, see
-http://www.standardml.org/Basis/index.html. Further resources, such
-as documentation for ML-Lex and ML-Yacc, and documentation for the SML/NJ
-specific libraries which are used in the starter code, can be found at
-
- http://www.cs.cmu.edu/~fp/courses/15411-f08/resources.html
-
-------------------------------------------------------------------------
-Source Files
-------------------------------------------------------------------------
-The following are the source files for the L1 compiler
-
-README -- this file
-
-Makefile -- makefile for the compiler
- For a quick test
-
- % make l1c (generates file bin/l1c.heap.<os-tag>)
- % bin/l1c --verbose ../tests/test1.c
-
- should generate ../tests/test1.s in pseudo assembly
-
- % make clean (removes generated files)
- % make TAGS (creates file TAGS, for Emacs tags commands)
-
-compile-l1c.sml -- SML commands that will create bin/l1c.heap.<os-tag>
-bin/l1c -- the script that will run the exported SML heap
-
-sources.cm -- lists all source files, including libraries,
- and lexer and grammar specifications
- For a quick test
-
- % sml
- - CM.make "sources.cm";
- - Top.test "--verbose ../tests/test1.c";
-
- should generate ../tests/test1.s in pseudo assembly
-
-parse/ast.sml -- definition and printer for abstract syntax trees (AST's)
-parse/l1.lex -- L1 lexer
-parse/l1.grm -- L1 grammar
-parse/parse.sml -- L1 parser
-parse/parsestate.sml -- L1 parser support for error messages
-
-type/typechecker.sml -- (trivial) type-checker for AST
-
-trans/temp.sml -- functions to generate and track temp's
-trans/tree.sml -- definition and pretty printer for IR trees
-trans/trans.sml -- translation from AST to IR trees
-
-codegen/assem.sml -- pseudo assembly format for this starter code
-codegen/codegen.sml -- pseudo code generator
-
-util/errormsg.sml -- error message utilities
-util/flag.sml -- library for defining flags
-util/mark.sml -- library for tracking source file positions
-util/safe-io.sml -- I/O utilities
-util/symbol.sml -- symbol table library
-util/word32.sml -- machine word utilities for two's complement interpretation
-
-top/top.sml -- top level function for export to binary and testing
-
-------------------------------------------------------------------------
-Debugging Hints
-------------------------------------------------------------------------
-You can use
-
- - Top.test "--verbose --dump-ast --dump-ir --dump-assem file.l1";
-
-to print information from all the phases of the current compiler.
-
-If you want to see the internal representations, you can call directly
-on SML's top level:
-
- - val ast = Parse.parse "file.l1";
- - val ir = Trans.translate ast;
- - val assem = Codegen.codgen ir;
-
-This will use SML's internal printing function to print the data
-structures. However, not everything will show.
-
-"-" means that the type is opaque. Sometimes you can replace an opaque
- signature ascription ":>" with a transparent one ":" to see the info.
- For reasons of general hygiene, however, you should change it back
- before handing in.
-
-"#" means that the printing depth is exceeded. Use
-
- - Control.Print.printDepth := 100;
-
- to increase the depth if you need to see more.
-
-"..." means that the printing length is exceeded. Use
-
- - Control.Print.printLength := 1000;
-
- to increase the length if you need to see more.
-
-------------------------------------------------------------------------
-Library Hints
-------------------------------------------------------------------------
-See util/symbol.sml for some uses of libraries provided with SML/NJ
-(and some other SML implementations). BinaryMapFn and
-BinarySetFn are likely of general use. To see their interface,
-you can check http://www.smlnj.org/doc/smlnj-lib/Manual/toc.html.
-I found binary maps and binary sets to be occasionally helpful.
+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...
\ No newline at end of file
git.joshuawise.com / snipe.git / blobdiff