Assignment elimination

Following single assignment analysis and single assignment elimination, assignment elimination finds all remaining local variables that appear on the left hand side of an assignment. If any such variables I1 ... are found, then the body of the lambda expression being optimized is replaced by a LET of the form 

  ((lambda (V1 ...) ...)
   (MAKE-CELL I1) ...)
in which all references to such variables are replaced by calls to CELL-REF, and all assignments by calls to CELL-SET!. The MAKE-CELL procedure allocates heap storage for the variable, which is essentially replaced by a pointer to that storage. Assignment elimination makes all local variables immutable as in Standard ML, so they can be copied freely, which greatly simplifies lambda lifting.

The storage for an assigned variable must be allocated on the heap if that variable is accessible from any procedure whose lifetime cannot be bounded. Programmers should realize that assignments are more expensive in higher order languages than in most imperative languages.

After assignment elimination has eliminated all assignments to the local variables of a lambda expression, the known local procedures of that lambda expression can be lifted to the next outer lambda expression.