Drill 9 Solutions

Suppose that we run a constant folding optimization on the following program.
```
(let ((x (+ 3 2)) (+ (let ((y (+ 1 5))) (* y x) (read-num)))
```
What will the optimized program look like? (You can write it as a Lisp expression, not an AST.)

Which optimizations should we expect to improve the performance of this program?
```
(define (map f l)
(if (empty? l) ())
    (pair (f (left l)) (map f (right l))))
(define (f x) (+ x 2))
(let ((l (map f (pair (+ 100 3) (pair (+ 100 3) ()))))) (print (pair (read-num) l)))
```
- constant folding
- inlining
- common subexpression elimination
Because map is recursive, we cannot eliminate the function call by inlining. But (+ 100 3) is a subexpression that appears twice, and is constant, so can be evaluated at compile time.
Consider the following basic block, and suppose that after the last line, only t6 is live.
```
L1:
t0 <- 3 
t1 <- read_num()
t2 <- t0 * t1 
t3 <- 2
t4 <- t3 + t1
t5 <- f(t4, t2)
t6 <- print(t5)
```
a. After the line t3 <- 2, which temporaries are live?
- t0
- t1
- t2
- t3
- t4
- t5
- t6
b. What's the minimum number of registers we need to allocate to execute this program without using the stack?
- 3
Describe as precisely as you can, in a short sentence or two, the "correctness theorem" for our class compiler: what does it mean when I say that "the compiler doesn't have any bugs"?

Suppose that p is an input program that successfully parses to an AST, and executing the interpreter on p produces a value v. If we compile and run p, the output (treated as a value) should also be v.