X-Git-Url: http://git.joshuawise.com/snipe.git/blobdiff_plain/12aa4087bee3e70f170d7457794921de4e385227..fe2f67179a5ea776444fdc8b30a27245867220ca:/README?ds=sidebyside diff --git a/README b/README index 0e3bf3d..3c068e3 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 L5 code into +x86_64 assembly. + +Here is a breakdown of the modules and changes from L5: + + * The parser. The parser was mainly brought in from lab 4, and mainly + just a straight-forward extension of the L4 parser to have increments, + decrements, conditionals, and hex constants. + + * AST utilities were updated to use the new temp typing system. + + * Temporaries now are the only source of sizing information until we hit + the stage at which point instructions are generated. At that point, + instructions get sizing info, too, but really, that's about it. + + * The typechecker was mostly unchanged. + + * The translator was changed to use the new sizing system. Of interest, + the 'safe' alloc routine and the 'safe' dereference routines have been + moved into the IR stage, as opposed to having custom instructions + generated for them at the munch stage. This was done with the addition + of the 'stmvar' IR function, which is equivalent to the GCC C extension: + ({ stm; stm; ... expr }) + in that it evaluates the statements first, then returns the evaluation + of the expression. + + * The munch modules were updated to remove a lot of their suck and make + them correct again. Specifically, they were updated to use the new + typing system and perform type inference of sorts (i.e. adding a + quadword base pointer and a long offset yields a quad, etc.). This is + far superior to the previous sizing method, in which we gave some loose + (and disgusting) annotations of size and left the final sizing decisions + to the stringifier (O.o). + + * The liveness analyzer was mainly unchanged. + + * The grapher was fully unchanged. Nice. + + * The color orderer was optimized a bit. + + * The coloring module was fully unchanged. Nice. + + * The solidifier was similarly ripped out and hit by the diqing beam, sent + on a flight to Diqing airport, which is in Diqing which is in + the Diqing province in China, and subsequently it was diqed. It is now + much happier. + + * The peepholer has been moved into the optimization framework. + + * An optimization framework was added, allowing optimizers to be + individually turned off from the command line with approximately no work + on our part. I'm particularly proud of the simplicity with which it + allows one to write optimizations; see optimize/feckful.sml. They need + only be hooked in one place (in particular, in a list at the top of + top.sml). Individual optimizations will be discussed in the paper to be + handed in tomorrow. + + * 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. + +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 the regression suite). There are a number of optimizations +that we wish to do, especially various interprocedural ones, but we ran out +of time.