Single assignment

Single assignment is an optimization technique that breaks the connection between variable names in a high level programming language and their location in the assembler code.

The basic principle of single assigment is that each location is written only once. After that the location can only be read from.

Demonstration:

a:=x+y;<BR> b:=a-1;<BR> a:=y+b;<BR> b:=x*4;<BR> a:=a+b;<BR>

...becomes...

loc1:=x+y;<BR> loc2:=loc1-1;<BR> loc3:=y+loc2;<BR> loc4:=x*4;<BR> loc5:=loc3+loc4;<BR>

The register allocator or temp allocator will try to coalesce the locations and remove moves between them.

Advantages of single assignment

Basically single assignment allows advanced optimizations. A few examples.

Very short live ranges

The live ranges of single assignment will be very short. For example for the example above:

loc1:=x+y; Live: x,y loc2:=loc1-1; Live: x,y,loc1 loc3:=y+loc2; Live: x,loc2 loc4:=x*4; Live: loc3,loc4 loc5:=loc3+loc4; Live: loc5

The short live ranges ensure that the computation can be performed with a very low amount of registers. The untransformed code used 4 variables, which were all live at the same time. So therefore we would need 4 registers for the variables alone. For temporary value we would propably need one more register, so we would need 5 registers in total.

For the single assignment form of the code, the register pressure is greatly reduced because of the short live ranges. We need to temporary registers, because the temporary register becomes the new location. Because only 3 locations are live at the same time, the computation can be peformed with only 3 registers.