(graded, group assignment)
Your task in this assignment is to implement a series of optimizations for the CPS compiler. In the new
assignment4 branch you will find the optimization phases,
l3.CPSLateOptimizer which are executed before and after data representation and hoisting. Each of these optimization phases consist of several microphases, such as inlining, dead code elimination and partial evaluation. These microphases are executed in sequence until a fixpoint is reached. So make sure there is a fixpoint that your microphases will reach!
Compiler phases are located in
src/l3/CPSOptimizer.scala and microphases are located in
src/l3/CPSOptimizerMicrophases.scala. You will also have to implement the the transformations such that the final test case in
test/l3/CPSOptimizer-Greybox.scala is optimized. When you’ll have all optimizations ready, this is how compiled code will look like:
input: (def char-print (fun (c) (@char-print c))) (def function-compose (fun (f g) (fun (x) (f (g x))))) (def + (fun (x y) (@+ x y))) (def succ (fun (x) (+ x 1))) (def twice (fun (x) (+ x x))) (char-print (@int->char ((function-compose succ twice) 39))) (char-print (@int->char ((function-compose succ succ) 73))) (char-print (@int->char ((function-compose twice succ) 4))) output: (let* ((v$1 79) (v$2 (char-print v$1)) (v$3 75) (v$4 (char-print v$3)) (v$5 10) (v$6 (char-print v$5))) (halt))
Closures? Blocks? What are those? Our optimizer obliterated all abstractions and gave us the simplest inline code possible. 😀 Oh, and did we mention tests are back? Greybox, meaning we don’t care about the trees, but put conditions on the number of instructions the interpreter executes for your code.
To get started:
git fetch origin git checkout origin/assignment4 git merge origin/assignment3 # fix any merge errors you may get sbt clean update test # and have a look at the following files # src/l3/CPSOptimizer.scala -- the two compiler phases for optimization # src/l3/CPSOptimizerMicrophases.scala -- the microphases themselves # src/l3/CPSOptimizerMicrophase.scala -- support code for microphases # src/l3/CPSOptimizerPartialEval.scala -- partial evaluators for CL3 and CPS primitives
or, just for the optimizer tests:
sbt 'test-only l3.test.CPSOptimizer_Greybox
As always, questions are welcome, cool ideas are welcome even more!
Jonas pointed out several problems in the testing infrastructure. To merge patches for those:
git fetch origin git merge origin/assignment4-patch1 git merge origin/assignment4-patch2
Sorry for the inconvenience!
To allow you to easily work on this assignment, we decided to give you the reference binaries for assignments 2 and 3. To merge them in, do:
git fetch origin git merge origin/assignment4-reference
The included jar file will give access to the