]>
Commit | Line | Data |
---|---|---|
c63539ff ML |
1 | .. |
2 | Copyright 1988-2022 Free Software Foundation, Inc. | |
3 | This is part of the GCC manual. | |
4 | For copying conditions, see the copyright.rst file. | |
5 | ||
6 | .. index:: SSA, static single assignment | |
7 | ||
8 | .. _ssa: | |
9 | ||
10 | Static Single Assignment | |
11 | ************************ | |
12 | ||
13 | Most of the tree optimizers rely on the data flow information provided | |
14 | by the Static Single Assignment (SSA) form. We implement the SSA form | |
15 | as described in R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and | |
16 | K. Zadeck. Efficiently Computing Static Single Assignment Form and the | |
17 | Control Dependence Graph. ACM Transactions on Programming Languages | |
18 | and Systems, 13(4):451-490, October 1991. | |
19 | ||
20 | The SSA form is based on the premise that program variables are | |
21 | assigned in exactly one location in the program. Multiple assignments | |
22 | to the same variable create new versions of that variable. Naturally, | |
23 | actual programs are seldom in SSA form initially because variables | |
24 | tend to be assigned multiple times. The compiler modifies the program | |
25 | representation so that every time a variable is assigned in the code, | |
26 | a new version of the variable is created. Different versions of the | |
27 | same variable are distinguished by subscripting the variable name with | |
28 | its version number. Variables used in the right-hand side of | |
29 | expressions are renamed so that their version number matches that of | |
30 | the most recent assignment. | |
31 | ||
32 | We represent variable versions using ``SSA_NAME`` nodes. The | |
33 | renaming process in :samp:`tree-ssa.cc` wraps every real and | |
34 | virtual operand with an ``SSA_NAME`` node which contains | |
35 | the version number and the statement that created the | |
36 | ``SSA_NAME``. Only definitions and virtual definitions may | |
37 | create new ``SSA_NAME`` nodes. | |
38 | ||
39 | .. index:: PHI nodes | |
40 | ||
41 | Sometimes, flow of control makes it impossible to determine the | |
42 | most recent version of a variable. In these cases, the compiler | |
43 | inserts an artificial definition for that variable called | |
44 | :dfn:`PHI function` or :dfn:`PHI node`. This new definition merges | |
45 | all the incoming versions of the variable to create a new name | |
46 | for it. For instance, | |
47 | ||
48 | .. code-block:: c++ | |
49 | ||
50 | if (...) | |
51 | a_1 = 5; | |
52 | else if (...) | |
53 | a_2 = 2; | |
54 | else | |
55 | a_3 = 13; | |
56 | ||
57 | # a_4 = PHI <a_1, a_2, a_3> | |
58 | return a_4; | |
59 | ||
60 | Since it is not possible to determine which of the three branches | |
61 | will be taken at runtime, we don't know which of ``a_1``, | |
62 | ``a_2`` or ``a_3`` to use at the return statement. So, the | |
63 | SSA renamer creates a new version ``a_4`` which is assigned | |
64 | the result of 'merging' ``a_1``, ``a_2`` and ``a_3``. | |
65 | Hence, PHI nodes mean 'one of these operands. I don't know | |
66 | which'. | |
67 | ||
68 | The following functions can be used to examine PHI nodes | |
69 | ||
70 | .. function:: gimple_phi_result (phi) | |
71 | ||
72 | Returns the ``SSA_NAME`` created by PHI node :samp:`{phi}` (i.e., :samp:`{phi}` 's LHS). | |
73 | ||
74 | .. function:: gimple_phi_num_args (phi) | |
75 | ||
76 | Returns the number of arguments in :samp:`{phi}`. This number is exactly | |
77 | the number of incoming edges to the basic block holding :samp:`{phi}`. | |
78 | ||
79 | .. function:: gimple_phi_arg (phi, i) | |
80 | ||
81 | Returns :samp:`{i}` th argument of :samp:`{phi}`. | |
82 | ||
83 | .. function:: gimple_phi_arg_edge (phi, i) | |
84 | ||
85 | Returns the incoming edge for the :samp:`{i}` th argument of :samp:`{phi}`. | |
86 | ||
87 | .. function:: gimple_phi_arg_def (phi, i) | |
88 | ||
89 | Returns the ``SSA_NAME`` for the :samp:`{i}` th argument of :samp:`{phi}`. | |
90 | ||
91 | .. index:: update_ssa, preserving SSA form | |
92 | ||
93 | Preserving the SSA form | |
94 | ^^^^^^^^^^^^^^^^^^^^^^^ | |
95 | ||
96 | Some optimization passes make changes to the function that | |
97 | invalidate the SSA property. This can happen when a pass has | |
98 | added new symbols or changed the program so that variables that | |
99 | were previously aliased aren't anymore. Whenever something like this | |
100 | happens, the affected symbols must be renamed into SSA form again. | |
101 | Transformations that emit new code or replicate existing statements | |
102 | will also need to update the SSA form. | |
103 | ||
104 | Since GCC implements two different SSA forms for register and virtual | |
105 | variables, keeping the SSA form up to date depends on whether you are | |
106 | updating register or virtual names. In both cases, the general idea | |
107 | behind incremental SSA updates is similar: when new SSA names are | |
108 | created, they typically are meant to replace other existing names in | |
109 | the program. | |
110 | ||
111 | For instance, given the following code: | |
112 | ||
113 | .. code-block:: c++ | |
114 | ||
115 | 1 L0: | |
116 | 2 x_1 = PHI (0, x_5) | |
117 | 3 if (x_1 < 10) | |
118 | 4 if (x_1 > 7) | |
119 | 5 y_2 = 0 | |
120 | 6 else | |
121 | 7 y_3 = x_1 + x_7 | |
122 | 8 endif | |
123 | 9 x_5 = x_1 + 1 | |
124 | 10 goto L0; | |
125 | 11 endif | |
126 | ||
127 | Suppose that we insert new names ``x_10`` and ``x_11`` (lines | |
128 | ``4`` and ``8``). | |
129 | ||
130 | .. code-block:: c++ | |
131 | ||
132 | 1 L0: | |
133 | 2 x_1 = PHI (0, x_5) | |
134 | 3 if (x_1 < 10) | |
135 | 4 x_10 = ... | |
136 | 5 if (x_1 > 7) | |
137 | 6 y_2 = 0 | |
138 | 7 else | |
139 | 8 x_11 = ... | |
140 | 9 y_3 = x_1 + x_7 | |
141 | 10 endif | |
142 | 11 x_5 = x_1 + 1 | |
143 | 12 goto L0; | |
144 | 13 endif | |
145 | ||
146 | We want to replace all the uses of ``x_1`` with the new definitions | |
147 | of ``x_10`` and ``x_11``. Note that the only uses that should | |
148 | be replaced are those at lines ``5``, ``9`` and ``11``. | |
149 | Also, the use of ``x_7`` at line ``9`` should *not* be | |
150 | replaced (this is why we cannot just mark symbol ``x`` for | |
151 | renaming). | |
152 | ||
153 | Additionally, we may need to insert a PHI node at line ``11`` | |
154 | because that is a merge point for ``x_10`` and ``x_11``. So the | |
155 | use of ``x_1`` at line ``11`` will be replaced with the new PHI | |
156 | node. The insertion of PHI nodes is optional. They are not strictly | |
157 | necessary to preserve the SSA form, and depending on what the caller | |
158 | inserted, they may not even be useful for the optimizers. | |
159 | ||
160 | Updating the SSA form is a two step process. First, the pass has to | |
161 | identify which names need to be updated and/or which symbols need to | |
162 | be renamed into SSA form for the first time. When new names are | |
163 | introduced to replace existing names in the program, the mapping | |
164 | between the old and the new names are registered by calling | |
165 | ``register_new_name_mapping`` (note that if your pass creates new | |
166 | code by duplicating basic blocks, the call to ``tree_duplicate_bb`` | |
167 | will set up the necessary mappings automatically). | |
168 | ||
169 | After the replacement mappings have been registered and new symbols | |
170 | marked for renaming, a call to ``update_ssa`` makes the registered | |
171 | changes. This can be done with an explicit call or by creating | |
172 | ``TODO`` flags in the ``tree_opt_pass`` structure for your pass. | |
173 | There are several ``TODO`` flags that control the behavior of | |
174 | ``update_ssa`` : | |
175 | ||
176 | * ``TODO_update_ssa``. Update the SSA form inserting PHI nodes | |
177 | for newly exposed symbols and virtual names marked for updating. | |
178 | When updating real names, only insert PHI nodes for a real name | |
179 | ``O_j`` in blocks reached by all the new and old definitions for | |
180 | ``O_j``. If the iterated dominance frontier for ``O_j`` | |
181 | is not pruned, we may end up inserting PHI nodes in blocks that | |
182 | have one or more edges with no incoming definition for | |
183 | ``O_j``. This would lead to uninitialized warnings for | |
184 | ``O_j`` 's symbol. | |
185 | ||
186 | * ``TODO_update_ssa_no_phi``. Update the SSA form without | |
187 | inserting any new PHI nodes at all. This is used by passes that | |
188 | have either inserted all the PHI nodes themselves or passes that | |
189 | need only to patch use-def and def-def chains for virtuals | |
190 | (e.g., DCE). | |
191 | ||
192 | * ``TODO_update_ssa_full_phi``. Insert PHI nodes everywhere | |
193 | they are needed. No pruning of the IDF is done. This is used | |
194 | by passes that need the PHI nodes for ``O_j`` even if it | |
195 | means that some arguments will come from the default definition | |
196 | of ``O_j`` 's symbol (e.g., ``pass_linear_transform``). | |
197 | ||
198 | WARNING: If you need to use this flag, chances are that your | |
199 | pass may be doing something wrong. Inserting PHI nodes for an | |
200 | old name where not all edges carry a new replacement may lead to | |
201 | silent codegen errors or spurious uninitialized warnings. | |
202 | ||
203 | * ``TODO_update_ssa_only_virtuals``. Passes that update the | |
204 | SSA form on their own may want to delegate the updating of | |
205 | virtual names to the generic updater. Since FUD chains are | |
206 | easier to maintain, this simplifies the work they need to do. | |
207 | NOTE: If this flag is used, any OLD->NEW mappings for real names | |
208 | are explicitly destroyed and only the symbols marked for | |
209 | renaming are processed. | |
210 | ||
211 | .. index:: examining SSA_NAMEs | |
212 | ||
213 | Examining SSA_NAME nodes | |
214 | ^^^^^^^^^^^^^^^^^^^^^^^^ | |
215 | ||
216 | The following macros can be used to examine ``SSA_NAME`` nodes | |
217 | ||
218 | .. c:macro:: SSA_NAME_DEF_STMT (var) | |
219 | ||
220 | Returns the statement :samp:`{s}` that creates the ``SSA_NAME`` | |
221 | :samp:`{var}`. If :samp:`{s}` is an empty statement (i.e., ``IS_EMPTY_STMT | |
222 | (s)`` returns ``true``), it means that the first reference to | |
223 | this variable is a USE or a VUSE. | |
224 | ||
225 | .. c:macro:: SSA_NAME_VERSION (var) | |
226 | ||
227 | Returns the version number of the ``SSA_NAME`` object :samp:`{var}`. | |
228 | ||
229 | Walking the dominator tree | |
230 | ^^^^^^^^^^^^^^^^^^^^^^^^^^ | |
231 | ||
232 | .. function:: void walk_dominator_tree (walk_data, bb) | |
233 | ||
234 | This function walks the dominator tree for the current CFG calling a | |
235 | set of callback functions defined in :samp:`{struct dom_walk_data}` in | |
236 | :samp:`domwalk.h`. The call back functions you need to define give you | |
237 | hooks to execute custom code at various points during traversal: | |
238 | ||
239 | * Once to initialize any local data needed while processing | |
240 | :samp:`{bb}` and its children. This local data is pushed into an | |
241 | internal stack which is automatically pushed and popped as the | |
242 | walker traverses the dominator tree. | |
243 | ||
244 | * Once before traversing all the statements in the :samp:`{bb}`. | |
245 | ||
246 | * Once for every statement inside :samp:`{bb}`. | |
247 | ||
248 | * Once after traversing all the statements and before recursing | |
249 | into :samp:`{bb}` 's dominator children. | |
250 | ||
251 | * It then recurses into all the dominator children of :samp:`{bb}`. | |
252 | ||
253 | * After recursing into all the dominator children of :samp:`{bb}` it | |
254 | can, optionally, traverse every statement in :samp:`{bb}` again | |
255 | (i.e., repeating steps 2 and 3). | |
256 | ||
257 | * Once after walking the statements in :samp:`{bb}` and :samp:`{bb}` 's | |
258 | dominator children. At this stage, the block local data stack | |
3ed1b4ce | 259 | is popped. |