### Due date: 19th of May, 2016, 13:00

*(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 `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`

. The specific implementation of CPSOptimizerLow is given.

More specifically, you **are expected to implement**:

- Dead code elimination
- Common-subexpression elimination
- Constant folding
- Neutral/absorbing elements optimization
- Shrinking inlining
- General inlining, according to a predetermined heuristics (see below)

For **bonus grade**, you may implement:

- Block primitive optimizations

**Do** **not** implement:

- η-reduction
- Contification

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! = 479001600 Instruction Stats ================= 1032 LetP 538 LetC ... ...12

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.

### Notes on Implementation

The implementation sketch that is given to you is not a trivial mapping of the theory into code, so here are some notes to guide you through it.

The optimizations are split in shrinking (in method `shrink`

) and non-shrinking (or general inlining, in method `inline`

) optimizations. Remember that shrinking optimizations are safe to apply as often as desired, while inlining may lead to arbitrarily large code, or even diverge the optimizer.

The general idea of the optimizer (see method `apply`

) is the following: After an initial step of iteratively applying `shrink`

until a fixed point, we iteratively apply a step of `inline`

and a step of `shrink`

until one of the following happens:

- The tree does not change,
- We reach a specified number of iterations, or
- The resulting tree’s size exceeds
`maxSize`

, given as a function of the initial size.

The two first conditions are checked by the `fixedPoint`

function itself, while the third is checked within `inline`

.

The `inline`

function is actually a small series of inlining steps. During each inlining step, we choose to inline functions/continuations of increasing size. For continuations, this size is linear to the number of steps, but for functions it is exponential (according to the Fibonacci sequence). We stop inlining after a specified number of steps, or if the tree grows to more than `maxSize`

.

The internal traversals of both the `shrink`

and `inline`

functions accept an implicit argument of the `State`

type, which, as you may have guessed, tracks the local state of the optimization. You are supposed to update it as you traverse the subtrees using the designated methods. The descriptions in the source file will hopefully make each field’s role to the optimization clear.

### Testing

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

**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`

)**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)**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 `CL3ToCPSTranslator`

, `CPSValueRepresenter`

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!**

### 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] 202 LetP
[stats] 134 LetC
[stats] 125 LetL
[stats] 50 If
[stats] 45 AppF
[stats] 33 AppC
[stats] 1 LetF
[stats] 1 Halt
[stats]
[stats] Value Primitives Stats
[stats] ======================
[stats] 47 CPSArithShiftR$
[stats] 21 CPSBlockSet$
[stats] 20 CPSOr$
[stats] 20 CPSArithShiftL$
[stats] 18 CPSSub$
[stats] 18 CPSAdd$
[stats] 16 CPSByteWrite$
[stats] 16 CPSBlockLength$
[stats] 12 CPSBlockGet$
[stats] 8 CPSBlockAlloc
[stats] 2 CPSBlockTag$
[stats] 2 CPSByteRead$
[stats] 1 CPSMul$
[stats] 1 CPSAnd$
[stats]
[stats] Logic Primitives Stats
[stats] ======================
[stats] 19 CPSLt$
[stats] 18 CPSLe$
[stats] 7 CPSEq$
[stats] 4 CPSGt$
[stats] 2 CPSNe$
[stats]
[stats] Functions defined: 33
[stats] Continuations defined: 134

` `