Homework 7

The assignment is to extend your calc->LLVM compiler from assignment 6:

https://utah.instructure.com/courses/377698/assignments/3420338

There are five parts.

First, recall that supporting extra parens was optional in homework 6. For this assignment it is mandatory that you do not support extra parens. Thus, this program is now an error: ((1))

Second, if you implemented the "if" construct using select instead of using control flow, you'll need to implement control flow instead. This is because we'll be introducing side effects, making it erroneous to speculatively execute both branches of a conditional.

Third, since our language is no longer purely functional, order of evaluation matters. For every syntactic form such as (if B E E), terms must be evaluated in left-to-right order. This is probably what you did in the first place, but now you need to make sure.

Fourth, support these new expression forms:

• m0..m9 are mutable 64-bit variables with initial value zero.
• (set E M) computes E and stores the resulting value in M, a mutable variable. The value of a set-expression is E.
• (seq E E) performs sequential composition of two expressions. The value of a seq-expression is the value of its second subexpression. The first subexpression has no effect on the ongoing computation except through side effects. 
• (while B E) repeatedly evaluates Boolean expression B, then expression E, as long as B is true. The value of the expression is the final value of E, or zero if B is false the first time. Loops may be nested arbitrarily. The code will be a bit tricky, you probably want to draw out the basic blocks and control flow edges between them on paper before starting to write code.

You have two options for implementing mutable variables:

1. Place them in memory using alloca instructions, and then access their values using loads and stores. This is easy since memory lives outside of the SSA world. Don't forget to initialize each memory location.
2. Place them in registers. Reading the value of a register is trivial (just use the Value as an operand) but SSA registers can only be assigned a value at one place in the program. To give a new value to a mutable variable, you create a new Value and subsequently, reads from the mutable variable should refer to the new value. When there is nontrivial control flow, you will need to insert Phi nodes to merge the old and new values. In this case you are implementing your own on-the-fly conversion into SSA form.

Fifth, before class on Thursday Oct 27, submit one or more new test cases to the calc-compiler repository. Place them in the directory auto-tests-hw7 and submit a pull request. At least one instance of each new expression form should be contained in your new test(s). Your test should run quickly, preferably in less than a tenth of a second.