Difference between revisions of "Single assignment"

From Lazarus wiki
Jump to navigationJump to search
(more)
(More)
Line 51: Line 51:
  
 
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.
 
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.
 +
 +
=== Better use of special registers ===
 +
 +
For some code, the variables need to be stored in special registers, for example for:
 +
 +
:c:=a shl b;
 +
:...
 +
:e:=c shl d;
 +
 +
... variable b should be placed into ecx, but this is true for variable d as well. Normally, this would cause a conflict, and therefore a spill. This can happen with single assignment as well, but, single assignment allows for allocation of b into another register later on in the, and therefore allows possibilities for both b and d to be allocated into ecx during the shift.
 +
 +
=== Optimizing variables away ===
 +
 +
<TABLE>
 +
<TR><TD>
 +
<TABLE border=1 cellpadding=20>
 +
<TR><TD><pre>
 +
a:=1;
 +
b:=a+1;
 +
c:=b*2;
 +
</pre></TD></TR>
 +
</TABLE>
 +
</TD><TD>
 +
...becomes...
 +
</TD><TD>
 +
<TABLE border=1 cellpadding=20>
 +
<TR><TD><pre>
 +
loc1:=1;              Live: []
 +
loc2:=loc1+1;        Live: Loc1
 +
loc3:=loc2*2;        Live: Loc2
 +
                      Live: Loc3
 +
</pre></TD></TR>
 +
</TABLE>
 +
</TD></TR></TABLE>
 +
 +
Location 1..3 do not conflict and can therefore be stored in the same register. The code might become:
 +
 +
:mov eax,1
 +
:inc eax
 +
:shl eax,1
 +
 +
It can get even better, because nothing with single assignment prevents you from assigning a variable LOC_CONSTANT. I.e. the because loc1 is only written to once with a constant, you can simply "store" loc1 in LOC_CONSTANT. The code generator could therefore simply generate:
 +
 +
:mov eax,4

Revision as of 10:13, 20 May 2006

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.

Better use of special registers

For some code, the variables need to be stored in special registers, for example for:

c:=a shl b;
...
e:=c shl d;

... variable b should be placed into ecx, but this is true for variable d as well. Normally, this would cause a conflict, and therefore a spill. This can happen with single assignment as well, but, single assignment allows for allocation of b into another register later on in the, and therefore allows possibilities for both b and d to be allocated into ecx during the shift.

Optimizing variables away

a:=1;
b:=a+1;
c:=b*2;

...becomes...

loc1:=1;              Live: []
loc2:=loc1+1;         Live: Loc1
loc3:=loc2*2;         Live: Loc2
                      Live: Loc3

Location 1..3 do not conflict and can therefore be stored in the same register. The code might become:

mov eax,1
inc eax
shl eax,1

It can get even better, because nothing with single assignment prevents you from assigning a variable LOC_CONSTANT. I.e. the because loc1 is only written to once with a constant, you can simply "store" loc1 in LOC_CONSTANT. The code generator could therefore simply generate:

mov eax,4