Sign in Join
Wiki copytemporary

Single assignment: what changed

Revision 1 to 2. Removed lines have a minus sign; added lines have a plus sign.

OldNewLine
11------------------------------------------------------------------------
22
33**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.
44
55The basic principle of single assigment is that each location is written only once. After that the location can only be read from.
66
77Demonstration:
88
9-<TABLE>
10-
11-<TR>
12-
13-<TD>
14-
15-<TABLE border=1 cellpadding=20>
16-
17-<TR>
18-
19-<TD>
20-
219 a:=x+y;
2210 b:=a-1;
2311 a:=y+b;
2412 b:=x*4;
2513 a:=a+b;
2614
27-</TD>
28-
29-</TR>
30-
31-</TABLE>
32-
33-</TD>
34-
35-<TD>
36-
3715...becomes...
3816
39-</TD>
40-
41-<TD>
42-
43-<TABLE border=1 cellpadding=20>
44-
45-<TR>
46-
47-<TD>
48-
4917 loc1:=x+y;
5018 loc2:=loc1-1;
5119 loc3:=y+loc2;
5220 loc4:=x*4;
5321 loc5:=loc3+loc4;
5422
55-</TD>
56-
57-</TR>
58-
59-</TABLE>
60-
61-</TD>
62-
63-</TR>
64-
65-</TABLE>
66-
6723The register allocator or temp allocator will try to coalesce the locations and remove moves between them.
6824
6925## Advantages of single assignment
7026
7127Basically single assignment allows advanced optimizations. A few examples.
7228
7329### Very short live ranges
7430
7531The live ranges of single assignment will be very short. For example for the example above:
7632
77-<TABLE border=1 cellpadding=20>
78-
79-<TR>
80-
81-<TD>
82-
8333 loc1:=x+y; Live: x,y
8434 loc2:=loc1-1; Live: x,y,loc1
8535 loc3:=y+loc2; Live: x,loc2
8636 loc4:=x*4; Live: loc3,loc4
8737 loc5:=loc3+loc4; Live: loc5
8838
89-</TD>
90-
91-</TR>
92-
93-</TABLE>
94-
9539The 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.
9640
9741For the single assignment form of the code, the register pressure is greatly reduced because of the short live ranges. We need no 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.
9842
9943### Better use of special registers
10044
10145For some code, the variables need to be stored in special registers, for example for:
10246
10347
10448c:=a shl b;
10549
10650...
10751
10852e:=c shl d;
10953
11054... 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.
11155
11256### Optimizing variables away
11357
114-<TABLE>
115-
116-<TR>
117-
118-<TD>
119-
120-<TABLE border=1 cellpadding=20>
121-
122-<TR>
123-
124-<TD>
125-
12658 a:=1;
12759 b:=a+1;
12860 c:=b*2;
12961
130-</TD>
131-
132-</TR>
133-
134-</TABLE>
135-
136-</TD>
137-
138-<TD>
139-
14062...becomes...
14163
142-</TD>
143-
144-<TD>
145-
146-<TABLE border=1 cellpadding=20>
147-
148-<TR>
149-
150-<TD>
151-
15264 loc1:=1; Live: []
15365 loc2:=loc1+1; Live: Loc1
15466 loc3:=loc2*2; Live: Loc2
15567 Live: Loc3
15668
157-</TD>
158-
159-</TR>
160-
161-</TABLE>
162-
163-</TD>
164-
165-</TR>
166-
167-</TABLE>
168-
16969Location 1..3 do not conflict and can therefore be stored in the same register. The code might become:
17070
17171
17272mov eax,1
17373
17474inc eax
17575
17676shl eax,1
17777
17878It 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. Because loc1 is constant, loc2 also can become LOC_CONSTANT. The code generator could therefore simply generate:
17979
18080
18181mov eax,4
18282
18383## Using single assignment for temps instead of registers
18484
18585The single assignment technique can also very well be used for local variables instead of registers and be used to reduce the amount copying between those variables. For example shortstrings are often copied around unnecessary. By applying single assignment to the code, temporary strings can be coalesced with actual string variables and the copies to them can therefore be optimizes away by the temp allocator.
18686
18787An example is the code "c:=c+'abcdefg';". The expression c+'abcdefg" is currently calculated in a temporary string which is later copied into the location of c again. Single assignment would result in different two locations for c, which can be coalesced into a single location, removing the need for an unnecessary string copy, and decrease the size of the stack frame.
18888
18989## Technical obstacles implementing single assigment
19090
19191Program control instructions are an obstacle to the single assignment principle. For example:
19292
193-<TABLE border=1 cellpadding=20>
194-
195-<TR>
196-
197-<TD>
198-
19993 1: a:=0;
20094 2: b:=0;
20195 3: c:=0;
20296 4: label1:
20397 5: b:=a+1;
20498 6: c:=c+b;
20599 7: a:=b*2
206100 8: if a<10 then
207101 9: goto label1;
208102 10: result:=c;
209103
210-</TD>
211-
212-</TR>
213-
214-</TABLE>
215-
216104Tranforming this program to single assignment form is problematic because the second assignment to "a" would move a in a different register than it is expected at label 1.
217105
218106To overcome this problem, "merge" functions are added to the label. Also called "phi" functions. Using a [[flow graph]] a compiler can determine line 3 is reachable from both line 1 as line 9.
219107
220108It therefore known a will be assigned to a different location when coming from line 9 than when we are coming from line 1. Therefore a merge function is inserted for variable a for both locations. For easy understanding the locations are named after the variable they originate from in the following single assigment form of the code:
221109
222-<TABLE border=1 cellpadding=20>
223-
224-<TR>
225-
226-<TD>
227-
228110 1: a1:=0;
229111 2: b1:=0;
230112 3: c1:=0;
231113 4: label1:
232114 5: a3:=merge(from_line_1:a1,from_line_11:a2);
233115 6: b2:=merge(from_line_1:b1,from_line_11:b3);
234116 7: c3:=merge(from_line_1:c1,from_line_11:c2);
235117 8: b3:=a3+1;
236118 9: c2:=c3+b3;
237119 10: a2:=b3*2
238120 12: if a2<10 then
239121 13: goto label1;
240122 14: result:=c2;
241123
242-</TD>
243-
244-</TR>
245-
246-</TABLE>
247-
248124The merge function can be explained as follows: For example, when arriving from line 1, the merge function assigns a1 to a3, when arriving from line 11, it assigns a2 to a3. After this process, the code is further transformed during which the merge functions are removed:
249125
250-<TABLE border=1 cellpadding=20>
251-
252-<TR>
253-
254-<TD>
255-
256126 1: a1:=0;
257127 2: b1:=0;
258128 3: c1:=0;
259129 4: a3:=a1;
260130 5: b2:=b1;
261131 6: c3:=c1;
262132 7: label1:
263133 8: b3:=a3+1;
264134 9: c2:=c3+b3;
265135 10: a2:=b3*2
266136 11: if a2<10 then
267137 12: begin
268138 13: a3:=a2;
269139 14: b2:=b3;
270140 15: c3:=c2;
271141 16: goto label1;
272142 17: end;
273143 18: result:=c2;
274144
275-</TD>
276-
277-</TR>
278-
279-</TABLE>
280-
281145This is a correct single assignment form of the code. Note that the merge function for b2 is unnecessary in the above code. If we would add merge functions recklessly, for complex code, our (internal) code would blow up a lot and therefore our register allocator would get a lot of work. Using a [[flow graph]] we can determine exactly when a merge function is necessary.
282146
283147There should be a merge function for a variable "a" at a certain node "z" of the flow graph of the code, when all of the following critria are true:
284148
285149- There exists a code block x containing a definition (a write to) a.
286150- There exists a code block y, y\<\>x, containing a definition (a write to) a.
287151- In the flow graph, there exists a non-empty path Pa from x to z.
288152- In the flow graph, there exists a non-empty path Pb from y to z.
289153- Pa and Pb do not have any node in the flow graph in common other than z
290154- Node z does not appear within both Pa and Pb, prior to the end though it may appear in one or the other.
291155
292156Using the above criteria, we can get a more efficient correct single assignment form:
293157
294-<TABLE border=1 cellpadding=20>
295-
296-<TR>
297-
298-<TD>
299-
300158 1: a1:=0;
301159 2: b1:=0;
302160 3: c1:=0;
303161 4: a3:=a1;
304162 5: c3:=c1;
305163 6: label1:
306164 7: b2:=a3+1;
307165 8: c2:=c3+b2;
308166 9: a2:=b2*2
309167 10: if a2<10 then
310168 11: begin
311169 12: a3:=a2;
312170 13: c3:=c2;
313171 14: goto label1;
314172 15: end;
315173 16: result:=c2;
316-
317-</TD>
318-
319-</TR>
320-
321-</TABLE>
322174
323175## Specific challenges for Free Pascal to implement single assignment
324176
325177- Free Pascal does not generate a flow graph. Generating a flow graph is not trivial with the current node tree design, because generating it needs traversing a code tree bottom up. This could be solved by turning the blockn into an array or double linked list instead of a binary tree.
326178- Free Pascal gives control statements their own nodes instead of converting control statements to goto. This problem is minor and while it will make generating the flow graph more complex, the current approach can be kept.
327179
328180## High level or low level
329181
330182Single assignment can be done at high level, converting a node tree to single assignment form, as at low level, generating assembler code in single assignment form. While the examples above have been written in a high level form, it makes more sense for Free Pascal do generate code in single assignment form right away.
331183
332184---
333185*From the Free Pascal wiki, page "Single assignment", as it stood on 2013-03-22 after a change by BigChimp, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's [[Licensing]] page. If you have concerns about this material, [message the admin](/wiki-contact).*
334186Category: Compiler design
335187Category: FPC

Back to history