Assignment 4: Optimization

(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.CPSEarlyOptimizer and 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!

Reference Implementation (for assignments 2 and 3)

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 l3.reference package, which contains CL3ToCPSTransformer, CPSDataRepresentation and CPSHoister. To make your project compile in Eclipse, you will have to regenerate the project files with sbt eclipse.