# 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?

- Non-recursive functions
- Recursive functions with statically known arguments
- Statically-known functions
- No free variables

When *should* we inline?

- Short functions
- Functions with few static call sites

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 an expression has multiple identical side-effect-free (i.e. constant) subexpressions

When *should* it be applied?

- Very common subexpressions
- Very big/slow subexpressions