# Homework 8: Optimizations
In this homework, you’ll implement some optimizations in your compiler. You’ll
also come up with benchmark programs and see how well your optimizations do on a
Copyright By PowCoder代写 加微信 powcoder
collaboratively-developed benchmark suite.
You’ll implement at least _two_ of the following optimizations (all of which we
discussed in class):
– Constant propagation
– Inlining
– Common subexpression elimination
In order to make inlining and common subexpression elimination easier to
implement, you’ll also write an AST pass (i.e., a function of type `program ->
program`) to make sure all variable names are globally unique.
_Note:_ Task 1 (as defined below) will be due **1 WEEK BEFORE** the rest of the
tasks. It has a separate assignment on Gradescope, `hw8-benchmarks`.
_Note:_ There are no “subtasks” in this assignment. Each numbered section has
exactly one task to go with it: Task 1, Task 2, Task 3a, Task 3b, and Task 3c.
### Grading
You have some options as far as how much time and effort to put into this final
homework. For example:
– If you’re short on time and want to be done with the semester—perfectly
understandable!—we recommend implementing **constant propagation and
inlining**, skipping the optional extension to constant propagation.
– If you feel like diving in a little deeper, implement constant propagation and
common subexpression elimination, including the optional extension to constant
propagation.
It’s up to you!
– You will receive full credit for correctly completing Task 1, Task 2, and
_just two_ of Task 3a, Task 3b, and Task 3c. In other words, for full credit,
you will only need to implement _two_ optimizations total.
– You will receive an additional 10% (extra credit) if you correctly implement
the remaining third optimization (i.e., _all three_ of Task 3a, Task 3b, and
But again, no pressure! **You can receive full credit by doing _just two_ of
Task 3a, Task 3b, and Task 3c!**
No matter which of the optimizations you chose to implement, Task 1 and Task 2
are both required.
### Starter code
The starter code is the same as for Homework 7, but without support for MLB
syntax. In particular, lambda expressions and function pointers are not
supported.
You will write all your optimizations in the file `lib/optimize.ml`. **You will
not need to modify any other files.**
### Testing
**There is no reference solution for this homework.** This is because everyone’s
optimizations will be slightly different!
That being said, we still encourage you to write tests using the `OUnit2`
framework we used for Homework 1. For a refresher on how that works, check out
[Section 2](https://classroom.github.com/a/AyX1r280). In any case, we will *not*
be grading any tests you write for this assignment _except for_ the benchmarks
that you explicitly submit in Task 1.
### Running the optimizer and compiler
You can run the compiler with specific optimization passes enabled using the
`bin/compile.exe` executable, by passing the `-p` argument one or more
times. For instance:
dune exec bin/compile.exe — examples/ex1.lisp output -r -p propagate-constants -p uniquify-variables -p inline
will execute the compiler with constant propagation, globally unique names, and
inlining enabled. You can also use this to execute an optimization more than
once—for instance, doing constant propagation, then inlining, then constant
propagation again.
You can also pass `-o` instead to enable all optimizations.
## 1. Benchmarks (due 1 week early)
_**Note:** For full credit, you **must** complete this task._
We’ve set up a
[repository for benchmarks](https://github.com/berkeley-cs164-2021/hw8-benchmarks)
for this homework assignment, as well as a script that you can use to see how
much your optimizations improve performance on the various benchmarks.
_Note:_ We will **not** be grading your optimizations based on a competition of
any kind with the benchmarks submitted. Instead, we will just be grading your
optimizations on the basis of whether or not they behave as prescribed.
**Task 1 (DUE 1 WEEK EARLY):** In the Gradescope assignment `hw8-benchmarks`,
upload _at least three_ interesting benchmark programs.
We will periodically take these submissions from Gradescope and upload them to
the *public* benchmarking repository, so please **DO NOT INCLUDE ANY IDENTIFYING
INFORMATION IN YOUR BENCHMARKS** (e.g. name, email, date of birth, social
security number, password…).
This also means that you should periodically do a `git pull` on the
`hw8-benchmarks` repo to get the latest benchmarks to run your optimizations on,
if you’d like!
## 2. Globablly unique names
_**Note:** For full credit, you **must** implement this pass._
Many optimizations can benefit from a pass that ensures all names are globally
**Task 2:** Implement this pass using `gensym`.
This pass should be run before inlining and common subexpression elimination,
and both of those optimizations can then assume globally-unique names (this is
an exception to the usual principle that the order of optimizations shouldn’t
matter for correctness). The `validate_passes` function in `optimize.ml` ensures
that this optimization is executed before inlining and common subexpression
elimination.
_Hint:_ You should implement this optimization before implementing
inlining or common subexpression elimination!
## 3a. Constant propagation
_**Note:** You can choose not to implement this optimization and still get full
credit; in that case, you must implement both inlining and common subexpression
elimination._
Constant propagation is a crucial optimization in which as much computation as
possible is done at _compile time_ instead of at _run time_.
We implemented a sketch of a simple version of constant propagation in class.
**Task 3a:** Implement constant propagation, which should support:
– Replacing the primitive operations `add1`, `sub1`, `plus`, `minus`, `eq`, and
`lt` with their statically-determined result when possible;
– Replacing `let`-bound names with constant boolean or number values when
– Eliminating `if` expressions where the test expression’s value can be
statically determined.
**Optional extension (for no additional credit):** You can also implement
re-associating binary operations (possibly in a separate pass) to find
opportunities for constant propagation. For instance, consider the expression
(+ 5 (+ 2 (read-num))
This expression won’t be modified by the constant propagation algorithm
described above, but with re-association it could be optimized to
(+ 7 (read-num))
## 3b. Inlining
_**Note:** You can choose not to implement this optimization and still get full
credit; in that case, you must implement both constant propagation and common
subexpression elimination._
In this task, you will implement function inlining for function definitions.
In general, inlining functions can be tricky because of variable names; consider
the following code:
(define (f x y) (+ x y))
(let ((x 2))
(let ((y 3))
A naive inlining implementation might result in code like this:
(let ((x 2))
(let ((y 3))
(let ((x y))
(let ((y x))
(+ x y)))))
This expression, however, is not equivalent!
This problem can be solved by adding a simultaneous binding form like the one
you implemented in Homework 3. _It can also be solved by just ensuring that all
variable and parameter names are globally unique._
You should implement a heuristic for when to inline a given function. This
heuristic should involve both (1) the number of static call sites and (2) the
size of the function body. For example, you could multiply some measure of the
size of the function body by the number of call sites and see if this exceeds
some target threshold. We recommend implementing your inliner as follows:
1. Find a function to inline. This function should satisfy your heuristics and
be a *leaf* function, i.e., one that doesn’t contain any function calls.
2. Inline static calls to the function and remove the function’s definition.
3. Go back to Step 1. Now that you’ve inlined a function, more functions may now
be leaf functions.
This process will never inline recursive functions, including mutually-recursive
functions.
**Task 3b:** Implement function inlining for function definitions. Please
describe your heuristic in a comment at the **VERY TOP** of the
`optimizations.ml` file.
## 3c. Common subexpression elimination
_**Note:** You can choose not to implement this optimization and still get full
credit; in that case, you must implement both constant propagation and
inlining._
In this task, you will implement common subexpression elimination.
This optimization pass should find common subexpressions, add names for those
subexpressions, and replace the subexpressions with variable references.
This optimization is more challenging to implement than inlining is. Our
suggested approach is to:
– Optimize each definition (including the top-level program body) independently.
For each definition:
– Make a list of *all* of the subexpressions in the program that don’t include
calls to `(read-num)` or `(print)`
– Find any such subexpressions that occur more than once
– Pick a new variable name for each expression that occurs more than once
– Replace each subexpression with this variable name
– Add a let-binding for each common subexpression
The most difficult part of this process is determining where to put the new
let-binding. Consider replacing the (identical) subexpressions `e1`, `e2`, and
`e3` with the variable `x`. You’ll need to find the lowest common ancestor `e`
of `e1`, `e2`, and `e3`, then replace it with
(let ((x e1)) e)
In order to find this lowest common ancestor, it will likely be useful to track
the “path” to a given expression: how to get to that subexpressson from the top
level of the given definition. How exactly you do this is up to you.
**Task 3c:** Implement common subexpression elimination.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com