Assignment 5: Optimization

Due date: 1st of May, 2014

(graded, group assignment)

Your task in this assignment is to implement a series of optimizations for the CPS compiler. In the new assignment5 branch you will find src/l3/CPSOptimizer.scala. This file contains the optimizer mechanism, followed by two specific instantiations: CPSOptimizerHigh and l3.CPSOptimizerLow. Your task is to fill in the optimizer mechanism, which consists of shrinking and non-shrinking optimizations (as described in the lectures) and the specific implementation of CPSOptimizerHigh.

Once the optimizer is fully functional, it should optimize the following example correctly:

 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? The optimizer eliminated all abstractions and gave us the simplest inline code possible. đŸ˜€

Now, to start hacking on the optimizer:

 git commit -a git fetch  git merge origin/assignment5 cd l3/compiler sbt clean update compile 'run ../library/lib.ml3 ../examples/bignums.l3' ... [info] Running l3.Main ../library/lib.ml3 ../examples/bignums.l3 Factorial of? 12 12! = 479001600  Instruction Stats =================     3060  LetL     2929  LetP      ...  ... 

The “Instruction stats” indicate how many instructions were executed while computing the factorial of 12. This is in contrast to the total instructions in the output program, which is constant regardless of the input.


Testing will be slightly different this time. We have 3 sets of tests:

  1. Blackbox tests check the program you output runs correctly, therefore the optimizations keep the semantics of the language (see test/l3/test/CPSOptimizer_Blackbox.scala)
  2. Greybox tests execute the program while recording the execution trace and then require certain properties of the trace, such as, for example that at most 2 functions were defined (see test/l3/test/CPSOptimizer_Greybox.scala and the additions to src/l3/Interpreter.scala for more details)
  3. Optimization challenge allows showing off how good your optimizer is on larger applications: we will run an example application and output the execution statistics (see src/l3/Interpreter.scala) — you can compete with your colleagues and with our reference implementation to get the best results possible. And yes, you should brag about your results on the Forum!

Some Blackbox and Greybox tests have already been given in the source code, but the Repository application contains the full test suite. Likewise, the Optimization challenge is only available in the Repository application.

This assignment gives you a lot of liberty into how and what you optimize, so go ahead and write the best optimizer in the entire class!


Reference Implementation

To allow you to easily work on this assignment, we decided to give you the reference binaries for assignments 2, 3 and 4. To merge them in, do:

 git fetch origin git merge origin/assignment5-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.

Also keep in mind that tests on the server will be executed using the reference compiler phases for assignments 2-4, only taking the optimizer from your code!


A mistake found its way into the reference skeleton for this assignment, and was pointed out by Adrien on piazza. We’ve fixed it and you can patch the reference implementation using the following commands:

 git checkout master git fetch origin git merge origin/assignment5-patch1

Challenge Results

For the reference compiler we have developed, the challenge results are given below. Different results form these statistics are encouraged, especially if they reduce the numbers in one category or the other.

Challenge: [stats]   [stats]  Instruction Stats [stats]  ================= [stats]    716775  LetC [stats]    657986  LetP [stats]    603371  LetL [stats]    295965  If [stats]    150310  AppF [stats]    124845  AppC [stats]         1  LetF [stats]         1  Halt$ [stats]   [stats]  Value Primitives Stats [stats]  ====================== [stats]    252902  CPSBlockGet$ [stats]    122406  CPSAdd$ [stats]    119908  CPSArithShiftL$ [stats]    118273  CPSBlockTag$ [stats]     23617  CPSBlockSet$ [stats]     11360  CPSBlockAlloc [stats]      3220  CPSSub$ [stats]      3069  CPSArithShiftR$ [stats]      1359  CPSOr$ [stats]       537  CPSXOr$ [stats]       474  CPSCharPrint$ [stats]       383  CPSMul$ [stats]       279  CPSAnd$ [stats]       179  CPSMod$ [stats]        16  CPSBlockSize$ [stats]         4  CPSCharRead$ [stats]   [stats]  Logic Primitives Stats [stats]  ====================== [stats]    191106  CPSEq$ [stats]    103191  CPSNe$ [stats]      1616  CPSLt$ [stats]        44  CPSGt$ [stats]         8  CPSLe$ [stats]   [stats]  Functions defined: 31 [stats]  Continuations defined: 716775