Drill 8

1. 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.)

   * `(+ 30 (read-num))`

2. 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.

3. 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

4. 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"?

Check Solutions