Difference between revisions of "Single assignment"
Daniel-fpc (talk | contribs) (more) |
Daniel-fpc (talk | contribs) (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 11: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:
|
...becomes... |
|
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
|
...becomes... |
|
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