Single assignment analysis

Single assignment analysis combines first order closure analysis with an inverse of the Scheme-specific Pass 1 transformation that eliminated all internal definitions.

Single assignment analysis identifies any formal parameters that are assigned exactly once, at the head of the lambda body, to the result of a lambda expression, and are called as often as they are referenced. Such parameters are actually the names of local procedures whose call points are all visible to the compiler. There is no need to create a closure for such procedures, since the environment in which they are declared will be accessible from the environment in effect at each place where they are called. This fact is recorded by transforming

  (lambda (... I ...)
    (begin D ...)
    (begin (set! I L) E1 ...))


   (lambda (... IGNORED ...)
     (begin (define I L) D ...)
     (begin E1 ...))

in which the single assignment has become an internal definition. For example, the assignment to .loop|2 in the output of Pass 1 becomes an internal definition during Pass 2:

   (set! reverse-map
     (lambda (.f|1 .l|1)
       (define .loop|2
         (lambda (.l|3 .x|3)
           (if (pair? .l|3)
                 (let ((.x|6|9 .l|3))
                     (.check! (pair? .x|6|9) 1 .x|6|9)
                     (.cdr:pair .x|6|9)))
                 (cons (.f|1 (let ((.x|15|18 .l|3))
                                 (.check! (pair? .x|15|18) 0 .x|15|18)
                                 (.car:pair .x|15|18))))
       (.loop|2 .l|1 '())))

It may seem that nothing has been accomplished by converting the original internal definition into an assignment, only to convert it back into an internal definition.

The point is that an internal definition in the output of Pass 2 records a known local procedure, whereas an internal definition in the original code may define a variable whose value is not even a procedure, or whose value is changed by assignments, or whose value is a procedure that must be represented as a closure because it is passed as an argument. In other words, Twobit uses the internal definition syntax as a handy notation for known local procedures, whereas Scheme programmers use that syntax for allocation and initialization of arbitrary variables.

Twobit's single assignment analysis also checks to make sure every call to a known local procedure passes the correct number of arguments. If the known local procedure has a rest parameter, the rest parameter is replaced by an ordinary parameter and the excess arguments in each call to that known procedure are replaced by an open-coded call to LIST.

Single assignment analysis is followed by single assignment elimination.