Project

The final assesment for this course consists of an individually completed project.

Final deliverables are due by the end of the time schedule for the class’s final exam as set by the registrar.

Submissions should be made on Gradescope.

There are several projects to choose from, described below.

In addition the source code for your project, you must write a 2-page document which gives a summary of your work and describes how your project is implemented.

1 a86 optimizer

Our compiler is designed to be simple and easy to maintain. That comes at the cost of emitting code that often does needless work. Write an a86 optimizer, i.e., a program that takes in a list of a86 instructions and produces an alternative list of instructions that have the same behavior, but will execute more efficiently.

This is a fairly open-ended project, which means you can take a simple approach, or you can do a deep-dive on assembly code optimization and try to do something very sophisticated.

For a maximum of 95% of the possible points, your optimizer should work on any a86 instructions produced by the Iniquity compiler. For 100%, your optimizer should work on any a86 instructions produced by the Loot compiler.

The most important aspect of the optimizer is it must preserve the meaning of the original source program. If running a program with or without optimization can produce different results, you will lose significant points.

The second important aspect of the optimizer is that it produces more efficient code (but this should never come at the expense of correctness—otherwise it’s trivial to optimize every program!). You should design some experiments demonstrating the impact of your optimizations and measure the performance improvement of your optimizer.

Here are some ideas for what you can optimize:

• Avoid stack references where possible.

  For example, you might push something and immediately reference it: (seq (Push r1) (Mov r2 (Offset rsp 0))), which is equivalent to (seq (Push r1) (Mov r2 r1)). The register-to-register move will be faster than accessing the memory on the stack.

• Avoid stack pushes where possible.

  In the previous example, it may be tempting to delete the Push, but that is only valid if that stack element is not referenced later before being popped. And even if the element is not referenced, we have to be careful about how the element is popped.

  But if you know where the pop occurs and there’s no intervening references in to the stack or other stack changes, then you can improve the code further, e.g. (seq (Push r1) (Mov r2 (Offset rsp 0)) (Add rsp 8)) can become (seq (Mov r2 r1)).

• Statically compute.

  Sometimes the compiler emits code for computing something at run-time which can instead be computed at compile time. For example, the compiler might emit (seq (Mov r 42) (Add r 12)), but this can be simplified to (seq (Mov r 54)).

There are many, many other kinds of optimizations you might consider. To get a sense of the opportunities for optimization, try compiling small examples and looking at the assembly code produces. Try hand-optimizing the code, then try to abstract what you did by hand and do it programmatically.

2 Source optimizer

Another complimentary approach to making programs compute more efficiently is to optimize them at the level of source code. Write a source code optimizer, i.e. a program that takes in a program AST and produces an alternative AST that has the same behavior, but will execute more efficiently.

This is another fairly open-ended project, which means you can take a simple approach, or you can do a deep-dive on source code optimization and try to do something very sophisticated.

For a maximum of 95% of the possible points, your optimizer should work for the Iniquity language. For 100%, your optimizer should work for the Loot language (or later).

The most important aspect of the optimizer is it must preserve the meaning of the original source program. If running a program with or without optimization can produce different results, you will lose significant points.

The second important aspect of the optimizer is that it produces more efficient code (but this should never come at the expense of correctness—otherwise it’s trivial to optimize every program!). You should design some experiments demonstrating the impact of your optimizations and measure the performance improvement of your optimizer.

Here are some ideas for where you can optimize:

• Avoid variable bindings where possible.

  Sometimes a program may bind a variable to a value, but then use the variable only once, e.g. (let ((x (add1 7))) (add1 x)). We can instead replace the variable occurrence with it’s definition to get: (add1 (add1 7)). Note that can must be taken to not do this optimization if it changes the order in which effects may happen. For example, consider

  (let ((x (read-byte)))

  (begin (read-byte)

  (add1 x)))

  This is not the same as:

  (begin (read-byte)

  (add1 (read-byte)))

  because the latter adds one to the second byte of the input stream rather than the first.

• Statically compute.

  Sometimes parts of a program can be computed at compile-time rather than run-time. For example, (add1 41) can be replaced with 42. Likewise, expressions like (if #f e1 e2) can be replaced by e2.

• Inline function calls.

  Suppose you have:

  (define (f x) (add1 x))

  (if (zero? (f 5)) e1 e2)

  Since the expression (f 5) is calling a known function, you should be able to transform this call into (let ((x 5)) (add1 x)). Using the previously described optimization, you can further optimize this to (add1 5), which in turn can be simiplified to 6. You can keep going and notice that (zero? 6) is just #f, so the whole program can be simplified to:

  (define (f x) (add1 x))

  e2

Note that the last example can get considerably more complicated in a language with first-class functions since it may not be possible to know statically which function is being called.

There are many other optimziations you might consider. Think about the kinds of expressions you might write and how they can be simplified, then figure out how to do it programmatically.

3 Multiple return values

Racket, Scheme, and even x86 support returning more than one value from a function call. Implement Racket’s let-values and values forms to add multiple return values.

You may choose to implement this feature for any language that is Iniquity or later for a maximum 95% of the possible points. For 100% you’ll need to implement the feature for Loot or later.

Here are the key features that need to be added:

• (values e1 ... en) will evaluate e1 through en and then “return” all of their values.

• (let-values ([(x1 ... xn) e]) e0) will evaluate e, which is expected to be an expression that produces n values, which are bound to x1 through xn in the body expression e0.

Here are some examples to help illustrate:

Examples

> (let-values ([(x y) (values 1 2)]) (+ x y))

3

> (let-values ([(x) (values 1)]) (add1 x))

2

> (let-values ([() (values)]) 7)

7

> (define (f x)     (values x (+ x 1) (+ x 2)))

> (let-values ([(x y z) (f 5)])     (cons x (cons y (cons z '()))))

'(5 6 7)

> (add1 (values 5))

6

> (let ((x (values 5)))     (add1 x))

6

Any time an expression produces a number of values that doesn’t match what the surrounding context expects, an error should be signalled.

Examples

> (add1 (values 1 2))

result arity mismatch;

expected number of values not received

expected: 1

received: 2

> (let-values ([(x y) 2]) x)

result arity mismatch;

expected number of values not received

expected: 2

received: 1

in: local-binding form

arguments...:

2

The top-level expression may produce any number of values and the run-time system should print each of them out, followed by a newline:

Examples

> (values 1 2 3)

1 2 3

Note there is some symmetry here between function arity checking where we make sure the number of arguments matches the number of parameters of the function being called and the “result arity” checking that is required to implement this feature. This suggests a similiar approach to implementing this feature, namely designating a register to communicate the arity of the result, which should be checked by the surrounding context.

You will also need to design an alternative mechanism for communicating return values. Using a single register ('rax) works when every expression produces a single result, but now expressions may produce an arbitrary number of results and using registers will no longer suffice. (Although you may want to continue to use 'rax for the common case of a single result.) The solution for this problem with function parameters was to use the stack and a similar approach can work for results too.

4 Exceptions and Exception Handling

Exceptions and exception handling mechanisms are widely used in modern programming languages. Implement Racket’s raise and with-handlers forms to add exception handling.

You may choose to implement this feature for any language that is Iniquity or later for a maximum 95% of the possible points. For 100% you’ll need to implement the feature for Loot or later.

Here are the key features that need to be added:

• (raise e) will evaluate e and then “raise” the value, side-stepping the usual flow of control and instead jump to the most recently installed exception handler.

• (with-handlers ([p1 f1] ...) e) will install a new exception handler during the evaluation of e. If e raises an exception that is not caught, the predicates should be applied to the raised value until finding the first pi that returns true, at which point the corresponding function fi is called with the raised value and the result of that application is the result of the entire with-handlers expression. If e does not raise an error, its value is the value of the with-handler expression.

Here are some examples to help illustrate:

Examples

> (with-handlers ([string? (λ (s) (cons "got" s))])     (raise "a string!"))

'("got" . "a string!")

> (with-handlers ([string? (λ (s) (cons "got" s))]                   [number? (λ (n) (+ n n))])     (raise 10))

20

> (with-handlers ([string? (λ (s) (cons "got" s))]                   [number? (λ (n) (+ n n))])     (+ (raise 10) 30))

20

> (let ((f (λ (x) (raise 10))))     (with-handlers ([string? (λ (s) (cons "got" s))]                     [number? (λ (n) (+ n n))])       (+ (f 10) 30)))

20

> (with-handlers ([string? (λ (s) (cons "got" s))]                   [number? (λ (n) (+ n n))])     'nothing-bad-happens)

'nothing-bad-happens

> (with-handlers ([symbol? (λ (s) (cons 'reraised s))])     (with-handlers ([string? (λ (s) (cons "got" s))]                     [number? (λ (n) (+ n n))])       (raise 'not-handled-by-inner-handler)))

'(reraised . not-handled-by-inner-handler)

Notice that when a value is raised, the enclosing context is discard. In the third example, the surrounding (+ [] 30) part is ignored and instead the raised value 10 is given the exception handler predicates, selecting the appropriate handler.

Thinking about the implementation, what this means is that a portion of the stack needs to be discarded, namely the area between the current top of the stack and the stack that was in place when the with-handlers expression was evaluated.

This suggestions that a with-handlers expression should stash away the current value of 'rsp. When a raise happens, it grabs the stashed away value and installs it as the current value of 'rsp, effectively rolling back the stack to its state at the point the exception handler was installed. It should then jump to code that will carry out the applying of the predicates and right-hand-side functions.

Since with-handlers can be nested, you will need to maintain an arbitrarily large collection of exception handlers, each of which has a pointer into the stack and a label for the code to handle the exception. This collection should operate like a stack: each with-handlers expression adds a new handler to the handler stack. If the body expression returns normally, the top-most handler should be removed. When a raise happens, the top-most handler is popped and used.

5 Design your own

You may also design your own project, however, you will need to submit a one-page write-up that documents what you plan to do and how you will evaluate whether it is successful. You must submit this document and have it approved by the instructor by Dec 7.