1 Introduction🔗

Your task in this assignment is to implement a series of optimizations for the CPS compiler. In the skeleton code you will find src/main/scala/project6/CPSOptimizer.scala. This file contains the optimizer mechanism, followed by two specific instantiations: CPSOptimizerHigh and CPSOptimizerLow. Your task is to implement 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.

For bonus grade, you may implement:

• Block primitive optimizations

For fun and fame, you may implement any optimizations you can think about and show off your results in the challenge (see below).

Do not implement:

• eta-reduction

• Contification. It is already implemented and can be turned on by uncommenting line 49 in Main.scala. Careful the tests do not use it.

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

def printChar(c: Int) = putchar(c);
def functionCompose(f: Int => Int, g: Int => Int) = (x: Int) => f(g(x));
def plus(x: Int, y: Int) = x + y;
def succ(x: Int) = x + 1;
def twice(x: Int) = x + x;
printChar(functionCompose(succ,twice)(39));
printChar(functionCompose(succ,succ)(73));
printChar(functionCompose(twice,succ)(4));
0

vall t_2 = 79;
valp t_3 = byte-write(t_2);
vall t_5 = 75;
valp t_6 = byte-write(t_5);
vall t_8 = 10;
valp t_9 = byte-write(t_8);
vall t_11 = 0;
halt(t_11)

Closures? Blocks? The optimizer eliminated all abstractions and gave us the simplest inline code possible. Now, to start hacking on the optimizer. For example, running the pascal.scala example with the library give you the following (optimized) output:

> run ../library/miniscala.lib ../examples/pascal.scala
...
[info] Running miniscala.Main ../library/miniscala.lib ../examples/pascal.scala
// CPS IR omitted ...
enter size (0 to exit)> 12
(1 11 55 165 330 462 462 330 165 55 11 1 )
(1 10 45 120 210 252 210 120 45 10 1 )
(1 9 36 84 126 126 84 36 9 1 )
(1 8 28 56 70 56 28 8 1 )
(1 7 21 35 35 21 7 1 )
(1 6 15 20 15 6 1 )
(1 5 10 10 5 1 )
(1 4 6 4 1 )
(1 3 3 1 )
(1 2 1 )
(1 1 )
(1 )
enter size (0 to exit)> 0
Instruction Stats
=================
    6101  LetP
    3194  LetL
    2312  LetC
     826  If
     759  AppC
     608  AppF
       1  Halt
       1  LetF

When type 0 to exit, you will see the instruction stats. The Instruction stats indicate how many instructions were executed while computing the pascal triangle. This is in contrast to the total instructions in the output program, which is constant regardless of the input.

2 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 inlineF) 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 inlineF 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 inlineF.

The inlineF 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 inlineF 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.

3 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 preserve the semantics of the program (see 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 CPSOptimizer_Greybox.scala and the additions to CPSInterpreter.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 CPSInterpreter.scala). You can compete with your fellows and with our reference implementation to get the best results possible. Feel free to post your results on Piazza and brag about them, and yes, extra credits will be given for top performers in the challenge!

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!

4 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.

NOTE: Turn on contification in order to improve your numbers.

Challenge: maze.scala with 12 for both inputs.

sbt:Project6> run ../library/miniscala.lib ../examples/maze.scala
...
Size: 12
Seed: 12
...
Instruction Stats
=================
 1319925  LetP
 1074383  LetL
 1003771  LetC
  446034  If
  292910  AppF
  113205  AppC
       1  LetF
       1  Halt

Value Primitives Stats
======================
  510158  CPSBlockGet$
  247412  CPSOr$
  241868  CPSArithShiftL$
  239466  CPSBlockTag$
   30504  CPSBlockSet$
   14660  CPSBlockAlloc
   10245  CPSSub$
    9983  CPSAdd$
    8583  CPSArithShiftR$
    3433  CPSAnd$
    1611  CPSMul$
    1056  CPSXOr$
     662  CPSByteWrite$
     264  CPSMod$
      14  CPSBlockLength$
       6  CPSByteRead$

Logic Primitives Stats
======================
  380718  CPSEq$
   63196  CPSNe$
    2058  CPSLt$
      52  CPSGt$
      10  CPSLe$

Functions defined: 26
Continuations defined: 1003771

5 Submission🔗

You should turn in the proj6 directory. Please run an sbt clean before packaging and submitting.

To submit your project, create a ZIP file named proj6.zip of the proj6 directory and upload it to the corresponding assignment on Canvas.

Verify your submission by downloading the ZIP file you uploaded on Canvas and extracting its content. The uncompressed content should be the proj6 folder containing the code. Your submission ZIP file should have the exact same structure as the skeleton ZIP file.

Your submitted code must compile, i.e. running sbt compile gives no errors. If your code does not compile, your submission will not be graded and you will receive 0 points for the whole project.

Late Submission Policy: Projects are due at 11:59pm on the due date. Succeeding projects build upon previous ones and will reveal solutions of preceding projects, so late submissions will not be accepted. Submitted after the deadline will receive 0 points.