Inlining and CSE

Recall two questions to ask ourselves about any particular optimization: when can the optimization be applied, and when should it be applied? For constant folding, both answers were basically "always." But that's not the case for every optimization.

Inlining

Consider the following program:

(define (f x) (+ x 2))
(print (* (f (read-num)) (f (read-num))))

The define feels almost unnecessary -- and function calls aren't cheap! We could imagine rewriting this, pretty syntactically, to

(print (* 
  (let ((x (read-num))) (+ x 2)) 
  (let ((x (read-num))) (+ x 2))))

In this case, this change seems like an improvement. But as before, we should carefully analyze when we can and should do this kind of inlining. Think about this program:

(define (g x) (* x 3))
(define (f x) (+ (g x) 2))
(print (* (f (read-num)) (f (read-num))))

Some compilers will only inline g. Others will be willing to do both. Let's start by inlining f.

(define (g x) (* x 3))
(print (* (let ((x (read-num))) (+ (g x) 2)) (let ((x (read-num))) (+ (g x) 2))))

And then g:

(print (* (let ((x (read-num))) (+ (let ((x x)) (* x 3)) 2)) (let ((x (read-num))) (+ (let ((x x)) (* x 3)) 2))))

This works, but the order was important! We had to inline these functions in the order they called each other.

What about this program:

(define (map f l)
  (if (empty? l) ())
    (pair (f (left l)) (map f (right l))))
(define (f x) (+ x 2))
(print (map f (pair 1 (pair 2 ()))))

Since map is recursive, though, we can't fully inline it. (We can't really inline f either!)

When can we inline? When is inlining safe?

When should we inline?

You're going to have a chance to implement inlining on the final homework. You'll have to consider these tradeoffs for yourself!

Common subexpression sharing

Consider the following program:

(let ((x (read-num)))
    (+ (* (+ x 2) (+ x 2)) (+ x 2)))

There's some repeated work; it would be more efficient for us to evaluate the following equivalent program.

(let ((x (read-num)))
    (let ((y (+ x 2)))
      (+ (* y y) y)))

This optimization is called common subexpression elimination (CSE).

Let's consider doing this in some other cases:

(define (sum-to x)
  (if (= x 0) 0
    (+ x (sum-to (sub1 x)))))
(let ((x (read-num)))
  (+ (* (sum-to x) (sum-to x)) (sum-to x)))

The program sum-to is a constant (or pure) function here, so we should be able to eliminate the three calls to sum-to x down to one. But contrast that to this program:

(define (read-plus x)
  (+ (read-num) x))
(let ((x (read-num)))
  (+ (* (read-plus x) (read-plus x)) (read-plus x)))

It does not seem safe to eliminate read-plus x here!

So, when can we eliminate common subexpressions?

When should it be applied?