Single assignment elimination

This optimization is not terribly important, but it illustrates the subtlety of interprocedural optimizations for imperative languages.

Single assignment elimination attempts to convert local variables that are assigned once at the head of their scope into LET variables:

  (lambda (... I1 ... In ...)
    (begin D ...)
    (begin (set! I1 E1)
           ...
           (set! In En)
           E ...))

becomes

  (lambda (... IGNORED ... IGNORED ...)
    (let* ((I1 E1) ... (In En))
      (begin D ...)
      (begin E ...)))

provided for each k:

1. Ik does not occur in E1, ..., Ek.
2. Either E1 through Ek contain no procedure calls or Ik is not accessible from an escaping lambda expression.
3. Ik is assigned only once.

The third condition is probably not necessary.

The second condition is necessary because, for example,

  (define f
    (lambda (x)
      (set! x (g))
      (lambda () x)))

is not equivalent to

  (define f
    (lambda (IGNORED)
      ((lambda (x)
         (lambda () x))
       (g))))

in all Scheme contexts. In particular, if g is defined by

  (define g
    (let ((n 0)
          (get-x (lambda () 0))
          (set-x (lambda (y) -1)))
      (lambda ()
        (case n
          ((0) (set! n 1)
               (let ((h (f 0)))
                 (if (= n 2)
                     (set! get-x h))
                 (write (get-x))
                 (newline)
                 (set! n 3)
                 (g)))
          ((1) (set! n 2)
               (call-with-current-continuation
                (lambda (k)
                  (set! set-x k)
                  3)))
          ((3) (set-x (+ 1 (get-x))))))))

then the first definition of f causes (g) to print all the integers beginning with 3, but the second definition of f causes (g) to print 3 over and over again.

Single assignment elimination is followed by assignment elimination.