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


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


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.

(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)))))
(+ (* (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)

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