X-Git-Url: http://git.joshuawise.com/snipe.git/blobdiff_plain/12aa4087bee3e70f170d7457794921de4e385227..6ade8b0a3251e44b34c6bdbbd9403e36d6fd6231:/README?ds=inline diff --git a/README b/README index 0e3bf3d..4c6899b 100644 --- a/README +++ b/README @@ -1,144 +1,69 @@ -(* README - * Author: Frank Pfenning - *) - ------------------------------------------------------------------------ -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 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.) - % 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. -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