X-Git-Url: http://git.joshuawise.com/snipe.git/blobdiff_plain/0a24e44d4e9f82f8d3d83de8e58c83c8cf2868b6..f285fa8903ee50118b6d92150c18cb3a32f52ed2:/README diff --git a/README b/README index 66a2e23..3c068e3 100644 --- a/README +++ b/README @@ -1,69 +1,69 @@ README ------ -This compiler is a big long chain of modules that transform l2 code into +This compiler is a big long chain of modules that transform L5 code into x86_64 assembly. -These modules include: - - * The parser. The parser was mainly brought in from lab 1, and mainly - just a straight-forward extension of the l1 parser. We continued to - mark expressions, and pass marking through as needed so that we could - produce reasonable error messages up through translation stage. We - introduced all needed grammar with no shift/reduce conflicts, but for - one in the IF/ELSE stage, with a construct such as: - if (x) - if (z) - a - else - b - (indentation intentionally omitted; there are at least two legitimate - ways to parse that!) - * The typechecker. This module was completely rewritten since lab1. Three - checks are instituted: a check to see if the program has misplaced break - or continue statements, a check to see that the program returns in all - control paths, and a check that all variables are initialized in all - control paths before usage. +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. - The return and break check is essentially implemented per the rules; the - only thing of interest for the variable initialization routine is that - there is a helper that computes all assigns to extend contexts from - block contents. It was determined that returning 2 accumulators from - varcheck would lead to returning 17 accumulators, which would lead to - 1984193248148132 accumulators; and 238547854478 accumulators leads to - the foldl, and foldl leads to anger, anger leads to hate, and hate leads - to the Dark Side. - * The translator is mainly intact; it was determined that the IR will have - basic control flow instructions of labels, jumps, and jump if not - conditional, which we deemed sufficient to implement all forms of l2 - control. - * The munch module was fully rewritten; we now munch directly to - pseudo-x86_64, in that it has temporaries allowed in it as well. We - believe that this allows us to generate much more optimal code than - munching into three op, converting from three to two, then converting - two to x86_64; in particular, we can run liveness on the x86_64 - directions directly, which makes translation significantly easier (we do - not have to worry about mashing necessary registers). - * The liveness analyzer was also fully rewritten; it is now fully - def-use-succ, giving us very pretty rules, and a lot of very ugly code - to mash them together. Luckily, the ugly code need not be touched ever - again. - * The grapher had about 4 characters of inconsequential change that had - the useful property of speeding it up by two orders of magnitude. You - need not worry about it. - * The orderer and colorer had no changes. - * A new module was introduced -- in particular, the solidifier. The - solidifier takes pseudo-x86_64 that is annotated with register locations - and emits needed spill and unspill operations to get everything into - real registers that the x86_64 chips can access. - * The peepholer remains pretty simple; redundant moves are optimized out, - and hence the code size drops by a factor of 1.5 or so. + * 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's fully functional; we have not had a case in quite some -time that caused us to generate incorrect code (at least, when we should -generate code). The internal debug mechanisms are very useful; often a -line-by-line examination of dumps after each translation phase can narrow -bugs down into single lines of ML code. +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.