CS502

View the Project on GitHub TiarkRompf/cs502

Project 4: Optimization

Due: Nov 20, 11:59PM

Download the skeleton code for the project here.

This project will be done individually, as with the previous two projects.

Your task in this assignment is to implement a series of optimizations for the CPS compiler. In the skeleton code 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:

For bonus grade, you may implement:

Do not implement:

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. :D
Now, to start hacking on the optimizer:

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
=================
    1032  LetP
     538  LetC
     ...  ...

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 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:

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. These will be included in the skeleton code.

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 we perform during grading will be executed using the reference compiler phases for assignments 2-4, only taking the optimizer from your code!

Turning In

The project is due by November 20, 11:59PM. To turn in your project, go to the same directory that your proj4 directory lives in (you do not have to name it proj4, but it must contain all of the project files) and type:

turnin -c cs502 -p project4 proj4 

You can verify the status of your turned in project by running:

turnin -c cs502 -p project4 -v

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: maze.l3 with 12 for both inputs.

Instruction Stats
=================
 1447846  LetC
 1223903  LetP
 1126157  LetL
  598163  If
  262985  AppC
  260868  AppF
       1  Halt
       1  LetF

Value Primitives Stats
======================
  446426  CPSBlockGet$
  236774  CPSOr$
  231107  CPSArithShiftL$
  228711  CPSBlockTag$
   29386  CPSBlockSet$
   13652  CPSBlockAlloc
   10632  CPSSub$
   10369  CPSAdd$
    9672  CPSArithShiftR$
    3570  CPSAnd$
    1607  CPSMul$
    1052  CPSXOr$
     662  CPSByteWrite$
     263  CPSMod$
      14  CPSBlockLength$
       6  CPSByteRead$

Logic Primitives Stats
======================
  380730  CPSEq$
  214652  CPSNe$
    2057  CPSLt$
     672  CPSLe$
      52  CPSGt$

Functions defined: 25
Continuations defined: 1447846