Mercurial > hg > CbC > CbC_gcc
annotate gcc/doc/tree-ssa.texi @ 120:f93fa5091070
fix conv1.c
author | mir3636 |
---|---|
date | Thu, 08 Mar 2018 14:53:42 +0900 |
parents | 04ced10e8804 |
children | 84e7813d76e9 |
rev | line source |
---|---|
111 | 1 @c Copyright (C) 2004-2017 Free Software Foundation, Inc. |
0 | 2 @c This is part of the GCC manual. |
3 @c For copying conditions, see the file gcc.texi. | |
4 | |
5 @c --------------------------------------------------------------------- | |
6 @c Tree SSA | |
7 @c --------------------------------------------------------------------- | |
8 | |
9 @node Tree SSA | |
10 @chapter Analysis and Optimization of GIMPLE tuples | |
11 @cindex Tree SSA | |
12 @cindex Optimization infrastructure for GIMPLE | |
13 | |
14 GCC uses three main intermediate languages to represent the program | |
15 during compilation: GENERIC, GIMPLE and RTL@. GENERIC is a | |
16 language-independent representation generated by each front end. It | |
17 is used to serve as an interface between the parser and optimizer. | |
18 GENERIC is a common representation that is able to represent programs | |
19 written in all the languages supported by GCC@. | |
20 | |
21 GIMPLE and RTL are used to optimize the program. GIMPLE is used for | |
22 target and language independent optimizations (e.g., inlining, | |
23 constant propagation, tail call elimination, redundancy elimination, | |
24 etc). Much like GENERIC, GIMPLE is a language independent, tree based | |
25 representation. However, it differs from GENERIC in that the GIMPLE | |
26 grammar is more restrictive: expressions contain no more than 3 | |
27 operands (except function calls), it has no control flow structures | |
28 and expressions with side-effects are only allowed on the right hand | |
29 side of assignments. See the chapter describing GENERIC and GIMPLE | |
30 for more details. | |
31 | |
32 This chapter describes the data structures and functions used in the | |
33 GIMPLE optimizers (also known as ``tree optimizers'' or ``middle | |
34 end''). In particular, it focuses on all the macros, data structures, | |
35 functions and programming constructs needed to implement optimization | |
36 passes for GIMPLE@. | |
37 | |
38 @menu | |
39 * Annotations:: Attributes for variables. | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
40 * SSA Operands:: SSA names referenced by GIMPLE statements. |
0 | 41 * SSA:: Static Single Assignment representation. |
42 * Alias analysis:: Representing aliased loads and stores. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
43 * Memory model:: Memory model used by the middle-end. |
0 | 44 @end menu |
45 | |
46 @node Annotations | |
47 @section Annotations | |
48 @cindex annotations | |
49 | |
50 The optimizers need to associate attributes with variables during the | |
51 optimization process. For instance, we need to know whether a | |
52 variable has aliases. All these attributes are stored in data | |
53 structures called annotations which are then linked to the field | |
54 @code{ann} in @code{struct tree_common}. | |
55 | |
56 | |
57 @node SSA Operands | |
58 @section SSA Operands | |
59 @cindex operands | |
60 @cindex virtual operands | |
61 @cindex real operands | |
62 @findex update_stmt | |
63 | |
64 Almost every GIMPLE statement will contain a reference to a variable | |
65 or memory location. Since statements come in different shapes and | |
66 sizes, their operands are going to be located at various spots inside | |
67 the statement's tree. To facilitate access to the statement's | |
68 operands, they are organized into lists associated inside each | |
69 statement's annotation. Each element in an operand list is a pointer | |
70 to a @code{VAR_DECL}, @code{PARM_DECL} or @code{SSA_NAME} tree node. | |
71 This provides a very convenient way of examining and replacing | |
72 operands. | |
73 | |
74 Data flow analysis and optimization is done on all tree nodes | |
75 representing variables. Any node for which @code{SSA_VAR_P} returns | |
76 nonzero is considered when scanning statement operands. However, not | |
77 all @code{SSA_VAR_P} variables are processed in the same way. For the | |
78 purposes of optimization, we need to distinguish between references to | |
79 local scalar variables and references to globals, statics, structures, | |
80 arrays, aliased variables, etc. The reason is simple, the compiler | |
81 can gather complete data flow information for a local scalar. On the | |
82 other hand, a global variable may be modified by a function call, it | |
83 may not be possible to keep track of all the elements of an array or | |
84 the fields of a structure, etc. | |
85 | |
86 The operand scanner gathers two kinds of operands: @dfn{real} and | |
87 @dfn{virtual}. An operand for which @code{is_gimple_reg} returns true | |
88 is considered real, otherwise it is a virtual operand. We also | |
89 distinguish between uses and definitions. An operand is used if its | |
90 value is loaded by the statement (e.g., the operand at the RHS of an | |
91 assignment). If the statement assigns a new value to the operand, the | |
92 operand is considered a definition (e.g., the operand at the LHS of | |
93 an assignment). | |
94 | |
95 Virtual and real operands also have very different data flow | |
96 properties. Real operands are unambiguous references to the | |
97 full object that they represent. For instance, given | |
98 | |
99 @smallexample | |
100 @{ | |
101 int a, b; | |
102 a = b | |
103 @} | |
104 @end smallexample | |
105 | |
106 Since @code{a} and @code{b} are non-aliased locals, the statement | |
107 @code{a = b} will have one real definition and one real use because | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
108 variable @code{a} is completely modified with the contents of |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
109 variable @code{b}. Real definition are also known as @dfn{killing |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
110 definitions}. Similarly, the use of @code{b} reads all its bits. |
0 | 111 |
112 In contrast, virtual operands are used with variables that can have | |
113 a partial or ambiguous reference. This includes structures, arrays, | |
114 globals, and aliased variables. In these cases, we have two types of | |
115 definitions. For globals, structures, and arrays, we can determine from | |
116 a statement whether a variable of these types has a killing definition. | |
117 If the variable does, then the statement is marked as having a | |
118 @dfn{must definition} of that variable. However, if a statement is only | |
119 defining a part of the variable (i.e.@: a field in a structure), or if we | |
120 know that a statement might define the variable but we cannot say for sure, | |
121 then we mark that statement as having a @dfn{may definition}. For | |
122 instance, given | |
123 | |
124 @smallexample | |
125 @{ | |
126 int a, b, *p; | |
127 | |
128 if (@dots{}) | |
129 p = &a; | |
130 else | |
131 p = &b; | |
132 *p = 5; | |
133 return *p; | |
134 @} | |
135 @end smallexample | |
136 | |
137 The assignment @code{*p = 5} may be a definition of @code{a} or | |
138 @code{b}. If we cannot determine statically where @code{p} is | |
139 pointing to at the time of the store operation, we create virtual | |
140 definitions to mark that statement as a potential definition site for | |
141 @code{a} and @code{b}. Memory loads are similarly marked with virtual | |
142 use operands. Virtual operands are shown in tree dumps right before | |
143 the statement that contains them. To request a tree dump with virtual | |
144 operands, use the @option{-vops} option to @option{-fdump-tree}: | |
145 | |
146 @smallexample | |
147 @{ | |
148 int a, b, *p; | |
149 | |
150 if (@dots{}) | |
151 p = &a; | |
152 else | |
153 p = &b; | |
154 # a = VDEF <a> | |
155 # b = VDEF <b> | |
156 *p = 5; | |
157 | |
158 # VUSE <a> | |
159 # VUSE <b> | |
160 return *p; | |
161 @} | |
162 @end smallexample | |
163 | |
164 Notice that @code{VDEF} operands have two copies of the referenced | |
165 variable. This indicates that this is not a killing definition of | |
166 that variable. In this case we refer to it as a @dfn{may definition} | |
167 or @dfn{aliased store}. The presence of the second copy of the | |
168 variable in the @code{VDEF} operand will become important when the | |
169 function is converted into SSA form. This will be used to link all | |
170 the non-killing definitions to prevent optimizations from making | |
171 incorrect assumptions about them. | |
172 | |
173 Operands are updated as soon as the statement is finished via a call | |
174 to @code{update_stmt}. If statement elements are changed via | |
175 @code{SET_USE} or @code{SET_DEF}, then no further action is required | |
176 (i.e., those macros take care of updating the statement). If changes | |
177 are made by manipulating the statement's tree directly, then a call | |
178 must be made to @code{update_stmt} when complete. Calling one of the | |
179 @code{bsi_insert} routines or @code{bsi_replace} performs an implicit | |
180 call to @code{update_stmt}. | |
181 | |
182 @subsection Operand Iterators And Access Routines | |
111 | 183 @cindex Operand Iterators |
0 | 184 @cindex Operand Access Routines |
185 | |
186 Operands are collected by @file{tree-ssa-operands.c}. They are stored | |
187 inside each statement's annotation and can be accessed through either the | |
188 operand iterators or an access routine. | |
189 | |
190 The following access routines are available for examining operands: | |
191 | |
192 @enumerate | |
111 | 193 @item @code{SINGLE_SSA_@{USE,DEF,TREE@}_OPERAND}: These accessors will return |
194 NULL unless there is exactly one operand matching the specified flags. If | |
195 there is exactly one operand, the operand is returned as either a @code{tree}, | |
0 | 196 @code{def_operand_p}, or @code{use_operand_p}. |
197 | |
198 @smallexample | |
199 tree t = SINGLE_SSA_TREE_OPERAND (stmt, flags); | |
200 use_operand_p u = SINGLE_SSA_USE_OPERAND (stmt, SSA_ALL_VIRTUAL_USES); | |
201 def_operand_p d = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_ALL_DEFS); | |
202 @end smallexample | |
203 | |
111 | 204 @item @code{ZERO_SSA_OPERANDS}: This macro returns true if there are no |
0 | 205 operands matching the specified flags. |
206 | |
207 @smallexample | |
208 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) | |
209 return; | |
210 @end smallexample | |
211 | |
111 | 212 @item @code{NUM_SSA_OPERANDS}: This macro Returns the number of operands |
213 matching 'flags'. This actually executes a loop to perform the count, so | |
0 | 214 only use this if it is really needed. |
215 | |
216 @smallexample | |
217 int count = NUM_SSA_OPERANDS (stmt, flags) | |
218 @end smallexample | |
219 @end enumerate | |
220 | |
221 | |
222 If you wish to iterate over some or all operands, use the | |
223 @code{FOR_EACH_SSA_@{USE,DEF,TREE@}_OPERAND} iterator. For example, to print | |
224 all the operands for a statement: | |
225 | |
226 @smallexample | |
227 void | |
228 print_ops (tree stmt) | |
229 @{ | |
230 ssa_op_iter; | |
231 tree var; | |
232 | |
233 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_OPERANDS) | |
234 print_generic_expr (stderr, var, TDF_SLIM); | |
235 @} | |
236 @end smallexample | |
237 | |
238 | |
239 How to choose the appropriate iterator: | |
240 | |
241 @enumerate | |
242 @item Determine whether you are need to see the operand pointers, or just the | |
243 trees, and choose the appropriate macro: | |
244 | |
245 @smallexample | |
246 Need Macro: | |
247 ---- ------- | |
248 use_operand_p FOR_EACH_SSA_USE_OPERAND | |
249 def_operand_p FOR_EACH_SSA_DEF_OPERAND | |
250 tree FOR_EACH_SSA_TREE_OPERAND | |
251 @end smallexample | |
252 | |
253 @item You need to declare a variable of the type you are interested | |
254 in, and an ssa_op_iter structure which serves as the loop controlling | |
255 variable. | |
256 | |
257 @item Determine which operands you wish to use, and specify the flags of | |
258 those you are interested in. They are documented in | |
259 @file{tree-ssa-operands.h}: | |
260 | |
261 @smallexample | |
262 #define SSA_OP_USE 0x01 /* @r{Real USE operands.} */ | |
263 #define SSA_OP_DEF 0x02 /* @r{Real DEF operands.} */ | |
264 #define SSA_OP_VUSE 0x04 /* @r{VUSE operands.} */ | |
111 | 265 #define SSA_OP_VDEF 0x08 /* @r{VDEF operands.} */ |
0 | 266 |
267 /* @r{These are commonly grouped operand flags.} */ | |
111 | 268 #define SSA_OP_VIRTUAL_USES (SSA_OP_VUSE) |
269 #define SSA_OP_VIRTUAL_DEFS (SSA_OP_VDEF) | |
270 #define SSA_OP_ALL_VIRTUALS (SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_DEFS) | |
271 #define SSA_OP_ALL_USES (SSA_OP_VIRTUAL_USES | SSA_OP_USE) | |
272 #define SSA_OP_ALL_DEFS (SSA_OP_VIRTUAL_DEFS | SSA_OP_DEF) | |
273 #define SSA_OP_ALL_OPERANDS (SSA_OP_ALL_USES | SSA_OP_ALL_DEFS) | |
0 | 274 @end smallexample |
275 @end enumerate | |
276 | |
277 So if you want to look at the use pointers for all the @code{USE} and | |
278 @code{VUSE} operands, you would do something like: | |
279 | |
280 @smallexample | |
281 use_operand_p use_p; | |
282 ssa_op_iter iter; | |
283 | |
284 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, (SSA_OP_USE | SSA_OP_VUSE)) | |
285 @{ | |
286 process_use_ptr (use_p); | |
287 @} | |
288 @end smallexample | |
289 | |
290 The @code{TREE} macro is basically the same as the @code{USE} and | |
291 @code{DEF} macros, only with the use or def dereferenced via | |
292 @code{USE_FROM_PTR (use_p)} and @code{DEF_FROM_PTR (def_p)}. Since we | |
293 aren't using operand pointers, use and defs flags can be mixed. | |
294 | |
295 @smallexample | |
296 tree var; | |
297 ssa_op_iter iter; | |
298 | |
299 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_VUSE) | |
300 @{ | |
301 print_generic_expr (stderr, var, TDF_SLIM); | |
302 @} | |
303 @end smallexample | |
304 | |
305 @code{VDEF}s are broken into two flags, one for the | |
306 @code{DEF} portion (@code{SSA_OP_VDEF}) and one for the USE portion | |
111 | 307 (@code{SSA_OP_VUSE}). |
0 | 308 |
111 | 309 There are many examples in the code, in addition to the documentation |
310 in @file{tree-ssa-operands.h} and @file{ssa-iterators.h}. | |
0 | 311 |
312 There are also a couple of variants on the stmt iterators regarding PHI | |
313 nodes. | |
314 | |
111 | 315 @code{FOR_EACH_PHI_ARG} Works exactly like |
316 @code{FOR_EACH_SSA_USE_OPERAND}, except it works over @code{PHI} arguments | |
0 | 317 instead of statement operands. |
318 | |
319 @smallexample | |
320 /* Look at every virtual PHI use. */ | |
321 FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_VIRTUAL_USES) | |
322 @{ | |
323 my_code; | |
324 @} | |
325 | |
326 /* Look at every real PHI use. */ | |
327 FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_USES) | |
328 my_code; | |
329 | |
330 /* Look at every PHI use. */ | |
331 FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_ALL_USES) | |
332 my_code; | |
333 @end smallexample | |
334 | |
111 | 335 @code{FOR_EACH_PHI_OR_STMT_@{USE,DEF@}} works exactly like |
0 | 336 @code{FOR_EACH_SSA_@{USE,DEF@}_OPERAND}, except it will function on |
337 either a statement or a @code{PHI} node. These should be used when it is | |
111 | 338 appropriate but they are not quite as efficient as the individual |
0 | 339 @code{FOR_EACH_PHI} and @code{FOR_EACH_SSA} routines. |
340 | |
341 @smallexample | |
342 FOR_EACH_PHI_OR_STMT_USE (use_operand_p, stmt, iter, flags) | |
343 @{ | |
344 my_code; | |
345 @} | |
346 | |
347 FOR_EACH_PHI_OR_STMT_DEF (def_operand_p, phi, iter, flags) | |
348 @{ | |
349 my_code; | |
350 @} | |
351 @end smallexample | |
352 | |
353 @subsection Immediate Uses | |
354 @cindex Immediate Uses | |
355 | |
111 | 356 Immediate use information is now always available. Using the immediate use |
0 | 357 iterators, you may examine every use of any @code{SSA_NAME}. For instance, |
358 to change each use of @code{ssa_var} to @code{ssa_var2} and call fold_stmt on | |
359 each stmt after that is done: | |
360 | |
361 @smallexample | |
362 use_operand_p imm_use_p; | |
363 imm_use_iterator iterator; | |
364 tree ssa_var, stmt; | |
365 | |
366 | |
367 FOR_EACH_IMM_USE_STMT (stmt, iterator, ssa_var) | |
368 @{ | |
369 FOR_EACH_IMM_USE_ON_STMT (imm_use_p, iterator) | |
370 SET_USE (imm_use_p, ssa_var_2); | |
371 fold_stmt (stmt); | |
372 @} | |
373 @end smallexample | |
374 | |
375 There are 2 iterators which can be used. @code{FOR_EACH_IMM_USE_FAST} is | |
376 used when the immediate uses are not changed, i.e., you are looking at the | |
111 | 377 uses, but not setting them. |
0 | 378 |
111 | 379 If they do get changed, then care must be taken that things are not changed |
380 under the iterators, so use the @code{FOR_EACH_IMM_USE_STMT} and | |
381 @code{FOR_EACH_IMM_USE_ON_STMT} iterators. They attempt to preserve the | |
382 sanity of the use list by moving all the uses for a statement into | |
383 a controlled position, and then iterating over those uses. Then the | |
0 | 384 optimization can manipulate the stmt when all the uses have been |
111 | 385 processed. This is a little slower than the FAST version since it adds a |
386 placeholder element and must sort through the list a bit for each statement. | |
387 This placeholder element must be also be removed if the loop is | |
388 terminated early. The macro @code{BREAK_FROM_IMM_USE_SAFE} is provided | |
0 | 389 to do this : |
390 | |
391 @smallexample | |
392 FOR_EACH_IMM_USE_STMT (stmt, iterator, ssa_var) | |
393 @{ | |
394 if (stmt == last_stmt) | |
395 BREAK_FROM_SAFE_IMM_USE (iter); | |
396 | |
397 FOR_EACH_IMM_USE_ON_STMT (imm_use_p, iterator) | |
398 SET_USE (imm_use_p, ssa_var_2); | |
399 fold_stmt (stmt); | |
400 @} | |
401 @end smallexample | |
402 | |
403 There are checks in @code{verify_ssa} which verify that the immediate use list | |
111 | 404 is up to date, as well as checking that an optimization didn't break from the |
405 loop without using this macro. It is safe to simply 'break'; from a | |
0 | 406 @code{FOR_EACH_IMM_USE_FAST} traverse. |
407 | |
408 Some useful functions and macros: | |
409 @enumerate | |
410 @item @code{has_zero_uses (ssa_var)} : Returns true if there are no uses of | |
411 @code{ssa_var}. | |
111 | 412 @item @code{has_single_use (ssa_var)} : Returns true if there is only a |
0 | 413 single use of @code{ssa_var}. |
414 @item @code{single_imm_use (ssa_var, use_operand_p *ptr, tree *stmt)} : | |
415 Returns true if there is only a single use of @code{ssa_var}, and also returns | |
416 the use pointer and statement it occurs in, in the second and third parameters. | |
417 @item @code{num_imm_uses (ssa_var)} : Returns the number of immediate uses of | |
418 @code{ssa_var}. It is better not to use this if possible since it simply | |
419 utilizes a loop to count the uses. | |
420 @item @code{PHI_ARG_INDEX_FROM_USE (use_p)} : Given a use within a @code{PHI} | |
421 node, return the index number for the use. An assert is triggered if the use | |
422 isn't located in a @code{PHI} node. | |
423 @item @code{USE_STMT (use_p)} : Return the statement a use occurs in. | |
424 @end enumerate | |
425 | |
426 Note that uses are not put into an immediate use list until their statement is | |
111 | 427 actually inserted into the instruction stream via a @code{bsi_*} routine. |
0 | 428 |
111 | 429 It is also still possible to utilize lazy updating of statements, but this |
430 should be used only when absolutely required. Both alias analysis and the | |
431 dominator optimizations currently do this. | |
0 | 432 |
111 | 433 When lazy updating is being used, the immediate use information is out of date |
0 | 434 and cannot be used reliably. Lazy updating is achieved by simply marking |
111 | 435 statements modified via calls to @code{gimple_set_modified} instead of |
436 @code{update_stmt}. When lazy updating is no longer required, all the | |
437 modified statements must have @code{update_stmt} called in order to bring them | |
438 up to date. This must be done before the optimization is finished, or | |
0 | 439 @code{verify_ssa} will trigger an abort. |
440 | |
441 This is done with a simple loop over the instruction stream: | |
442 @smallexample | |
443 block_stmt_iterator bsi; | |
444 basic_block bb; | |
445 FOR_EACH_BB (bb) | |
446 @{ | |
447 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
448 update_stmt_if_modified (bsi_stmt (bsi)); | |
449 @} | |
450 @end smallexample | |
451 | |
452 @node SSA | |
453 @section Static Single Assignment | |
454 @cindex SSA | |
455 @cindex static single assignment | |
456 | |
457 Most of the tree optimizers rely on the data flow information provided | |
458 by the Static Single Assignment (SSA) form. We implement the SSA form | |
459 as described in @cite{R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and | |
460 K. Zadeck. Efficiently Computing Static Single Assignment Form and the | |
461 Control Dependence Graph. ACM Transactions on Programming Languages | |
462 and Systems, 13(4):451-490, October 1991}. | |
463 | |
464 The SSA form is based on the premise that program variables are | |
465 assigned in exactly one location in the program. Multiple assignments | |
466 to the same variable create new versions of that variable. Naturally, | |
467 actual programs are seldom in SSA form initially because variables | |
468 tend to be assigned multiple times. The compiler modifies the program | |
469 representation so that every time a variable is assigned in the code, | |
470 a new version of the variable is created. Different versions of the | |
471 same variable are distinguished by subscripting the variable name with | |
472 its version number. Variables used in the right-hand side of | |
473 expressions are renamed so that their version number matches that of | |
474 the most recent assignment. | |
475 | |
476 We represent variable versions using @code{SSA_NAME} nodes. The | |
477 renaming process in @file{tree-ssa.c} wraps every real and | |
478 virtual operand with an @code{SSA_NAME} node which contains | |
479 the version number and the statement that created the | |
480 @code{SSA_NAME}. Only definitions and virtual definitions may | |
481 create new @code{SSA_NAME} nodes. | |
482 | |
483 @cindex PHI nodes | |
484 Sometimes, flow of control makes it impossible to determine the | |
485 most recent version of a variable. In these cases, the compiler | |
486 inserts an artificial definition for that variable called | |
487 @dfn{PHI function} or @dfn{PHI node}. This new definition merges | |
488 all the incoming versions of the variable to create a new name | |
489 for it. For instance, | |
490 | |
491 @smallexample | |
492 if (@dots{}) | |
493 a_1 = 5; | |
494 else if (@dots{}) | |
495 a_2 = 2; | |
496 else | |
497 a_3 = 13; | |
498 | |
499 # a_4 = PHI <a_1, a_2, a_3> | |
500 return a_4; | |
501 @end smallexample | |
502 | |
503 Since it is not possible to determine which of the three branches | |
504 will be taken at runtime, we don't know which of @code{a_1}, | |
505 @code{a_2} or @code{a_3} to use at the return statement. So, the | |
506 SSA renamer creates a new version @code{a_4} which is assigned | |
507 the result of ``merging'' @code{a_1}, @code{a_2} and @code{a_3}. | |
508 Hence, PHI nodes mean ``one of these operands. I don't know | |
509 which''. | |
510 | |
111 | 511 The following functions can be used to examine PHI nodes |
0 | 512 |
111 | 513 @defun gimple_phi_result (@var{phi}) |
0 | 514 Returns the @code{SSA_NAME} created by PHI node @var{phi} (i.e., |
515 @var{phi}'s LHS)@. | |
111 | 516 @end defun |
0 | 517 |
111 | 518 @defun gimple_phi_num_args (@var{phi}) |
0 | 519 Returns the number of arguments in @var{phi}. This number is exactly |
520 the number of incoming edges to the basic block holding @var{phi}@. | |
111 | 521 @end defun |
0 | 522 |
111 | 523 @defun gimple_phi_arg (@var{phi}, @var{i}) |
524 Returns @var{i}th argument of @var{phi}@. | |
525 @end defun | |
0 | 526 |
111 | 527 @defun gimple_phi_arg_edge (@var{phi}, @var{i}) |
0 | 528 Returns the incoming edge for the @var{i}th argument of @var{phi}. |
111 | 529 @end defun |
0 | 530 |
111 | 531 @defun gimple_phi_arg_def (@var{phi}, @var{i}) |
0 | 532 Returns the @code{SSA_NAME} for the @var{i}th argument of @var{phi}. |
111 | 533 @end defun |
0 | 534 |
535 | |
536 @subsection Preserving the SSA form | |
537 @findex update_ssa | |
538 @cindex preserving SSA form | |
539 Some optimization passes make changes to the function that | |
540 invalidate the SSA property. This can happen when a pass has | |
541 added new symbols or changed the program so that variables that | |
542 were previously aliased aren't anymore. Whenever something like this | |
111 | 543 happens, the affected symbols must be renamed into SSA form again. |
0 | 544 Transformations that emit new code or replicate existing statements |
545 will also need to update the SSA form@. | |
546 | |
547 Since GCC implements two different SSA forms for register and virtual | |
548 variables, keeping the SSA form up to date depends on whether you are | |
549 updating register or virtual names. In both cases, the general idea | |
550 behind incremental SSA updates is similar: when new SSA names are | |
551 created, they typically are meant to replace other existing names in | |
552 the program@. | |
553 | |
554 For instance, given the following code: | |
555 | |
556 @smallexample | |
557 1 L0: | |
558 2 x_1 = PHI (0, x_5) | |
559 3 if (x_1 < 10) | |
560 4 if (x_1 > 7) | |
561 5 y_2 = 0 | |
562 6 else | |
563 7 y_3 = x_1 + x_7 | |
564 8 endif | |
565 9 x_5 = x_1 + 1 | |
566 10 goto L0; | |
567 11 endif | |
568 @end smallexample | |
569 | |
570 Suppose that we insert new names @code{x_10} and @code{x_11} (lines | |
571 @code{4} and @code{8})@. | |
572 | |
573 @smallexample | |
574 1 L0: | |
575 2 x_1 = PHI (0, x_5) | |
576 3 if (x_1 < 10) | |
577 4 x_10 = @dots{} | |
578 5 if (x_1 > 7) | |
579 6 y_2 = 0 | |
580 7 else | |
581 8 x_11 = @dots{} | |
582 9 y_3 = x_1 + x_7 | |
583 10 endif | |
584 11 x_5 = x_1 + 1 | |
585 12 goto L0; | |
586 13 endif | |
587 @end smallexample | |
588 | |
589 We want to replace all the uses of @code{x_1} with the new definitions | |
590 of @code{x_10} and @code{x_11}. Note that the only uses that should | |
591 be replaced are those at lines @code{5}, @code{9} and @code{11}. | |
592 Also, the use of @code{x_7} at line @code{9} should @emph{not} be | |
593 replaced (this is why we cannot just mark symbol @code{x} for | |
594 renaming)@. | |
595 | |
596 Additionally, we may need to insert a PHI node at line @code{11} | |
597 because that is a merge point for @code{x_10} and @code{x_11}. So the | |
598 use of @code{x_1} at line @code{11} will be replaced with the new PHI | |
599 node. The insertion of PHI nodes is optional. They are not strictly | |
600 necessary to preserve the SSA form, and depending on what the caller | |
601 inserted, they may not even be useful for the optimizers@. | |
602 | |
603 Updating the SSA form is a two step process. First, the pass has to | |
604 identify which names need to be updated and/or which symbols need to | |
605 be renamed into SSA form for the first time. When new names are | |
606 introduced to replace existing names in the program, the mapping | |
607 between the old and the new names are registered by calling | |
608 @code{register_new_name_mapping} (note that if your pass creates new | |
609 code by duplicating basic blocks, the call to @code{tree_duplicate_bb} | |
111 | 610 will set up the necessary mappings automatically). |
0 | 611 |
612 After the replacement mappings have been registered and new symbols | |
613 marked for renaming, a call to @code{update_ssa} makes the registered | |
614 changes. This can be done with an explicit call or by creating | |
615 @code{TODO} flags in the @code{tree_opt_pass} structure for your pass. | |
616 There are several @code{TODO} flags that control the behavior of | |
617 @code{update_ssa}: | |
618 | |
619 @itemize @bullet | |
620 @item @code{TODO_update_ssa}. Update the SSA form inserting PHI nodes | |
621 for newly exposed symbols and virtual names marked for updating. | |
622 When updating real names, only insert PHI nodes for a real name | |
623 @code{O_j} in blocks reached by all the new and old definitions for | |
624 @code{O_j}. If the iterated dominance frontier for @code{O_j} | |
625 is not pruned, we may end up inserting PHI nodes in blocks that | |
626 have one or more edges with no incoming definition for | |
627 @code{O_j}. This would lead to uninitialized warnings for | |
628 @code{O_j}'s symbol@. | |
629 | |
630 @item @code{TODO_update_ssa_no_phi}. Update the SSA form without | |
631 inserting any new PHI nodes at all. This is used by passes that | |
632 have either inserted all the PHI nodes themselves or passes that | |
633 need only to patch use-def and def-def chains for virtuals | |
634 (e.g., DCE)@. | |
635 | |
636 | |
637 @item @code{TODO_update_ssa_full_phi}. Insert PHI nodes everywhere | |
638 they are needed. No pruning of the IDF is done. This is used | |
639 by passes that need the PHI nodes for @code{O_j} even if it | |
640 means that some arguments will come from the default definition | |
641 of @code{O_j}'s symbol (e.g., @code{pass_linear_transform})@. | |
642 | |
643 WARNING: If you need to use this flag, chances are that your | |
644 pass may be doing something wrong. Inserting PHI nodes for an | |
645 old name where not all edges carry a new replacement may lead to | |
646 silent codegen errors or spurious uninitialized warnings@. | |
647 | |
648 @item @code{TODO_update_ssa_only_virtuals}. Passes that update the | |
649 SSA form on their own may want to delegate the updating of | |
650 virtual names to the generic updater. Since FUD chains are | |
651 easier to maintain, this simplifies the work they need to do. | |
652 NOTE: If this flag is used, any OLD->NEW mappings for real names | |
653 are explicitly destroyed and only the symbols marked for | |
654 renaming are processed@. | |
655 @end itemize | |
656 | |
657 @subsection Examining @code{SSA_NAME} nodes | |
658 @cindex examining SSA_NAMEs | |
659 | |
660 The following macros can be used to examine @code{SSA_NAME} nodes | |
661 | |
662 @defmac SSA_NAME_DEF_STMT (@var{var}) | |
663 Returns the statement @var{s} that creates the @code{SSA_NAME} | |
664 @var{var}. If @var{s} is an empty statement (i.e., @code{IS_EMPTY_STMT | |
665 (@var{s})} returns @code{true}), it means that the first reference to | |
666 this variable is a USE or a VUSE@. | |
667 @end defmac | |
668 | |
669 @defmac SSA_NAME_VERSION (@var{var}) | |
670 Returns the version number of the @code{SSA_NAME} object @var{var}. | |
671 @end defmac | |
672 | |
673 | |
674 @subsection Walking the dominator tree | |
675 | |
676 @deftypefn {Tree SSA function} void walk_dominator_tree (@var{walk_data}, @var{bb}) | |
677 | |
678 This function walks the dominator tree for the current CFG calling a | |
679 set of callback functions defined in @var{struct dom_walk_data} in | |
680 @file{domwalk.h}. The call back functions you need to define give you | |
681 hooks to execute custom code at various points during traversal: | |
682 | |
683 @enumerate | |
684 @item Once to initialize any local data needed while processing | |
685 @var{bb} and its children. This local data is pushed into an | |
686 internal stack which is automatically pushed and popped as the | |
687 walker traverses the dominator tree. | |
688 | |
689 @item Once before traversing all the statements in the @var{bb}. | |
690 | |
691 @item Once for every statement inside @var{bb}. | |
692 | |
693 @item Once after traversing all the statements and before recursing | |
694 into @var{bb}'s dominator children. | |
695 | |
696 @item It then recurses into all the dominator children of @var{bb}. | |
697 | |
698 @item After recursing into all the dominator children of @var{bb} it | |
699 can, optionally, traverse every statement in @var{bb} again | |
700 (i.e., repeating steps 2 and 3). | |
701 | |
702 @item Once after walking the statements in @var{bb} and @var{bb}'s | |
703 dominator children. At this stage, the block local data stack | |
704 is popped. | |
705 @end enumerate | |
706 @end deftypefn | |
707 | |
708 @node Alias analysis | |
709 @section Alias analysis | |
710 @cindex alias | |
711 @cindex flow-sensitive alias analysis | |
712 @cindex flow-insensitive alias analysis | |
713 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
714 Alias analysis in GIMPLE SSA form consists of two pieces. First |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
715 the virtual SSA web ties conflicting memory accesses and provides |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
716 a SSA use-def chain and SSA immediate-use chains for walking |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
717 possibly dependent memory accesses. Second an alias-oracle can |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
718 be queried to disambiguate explicit and implicit memory references. |
0 | 719 |
720 @enumerate | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
721 @item Memory SSA form. |
0 | 722 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
723 All statements that may use memory have exactly one accompanied use of |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
724 a virtual SSA name that represents the state of memory at the |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
725 given point in the IL. |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
726 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
727 All statements that may define memory have exactly one accompanied |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
728 definition of a virtual SSA name using the previous state of memory |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
729 and defining the new state of memory after the given point in the IL. |
0 | 730 |
731 @smallexample | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
732 int i; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
733 int foo (void) |
0 | 734 @{ |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
735 # .MEM_3 = VDEF <.MEM_2(D)> |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
736 i = 1; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
737 # VUSE <.MEM_3> |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
738 return i; |
0 | 739 @} |
740 @end smallexample | |
741 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
742 The virtual SSA names in this case are @code{.MEM_2(D)} and |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
743 @code{.MEM_3}. The store to the global variable @code{i} |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
744 defines @code{.MEM_3} invalidating @code{.MEM_2(D)}. The |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
745 load from @code{i} uses that new state @code{.MEM_3}. |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
746 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
747 The virtual SSA web serves as constraints to SSA optimizers |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
748 preventing illegitimate code-motion and optimization. It |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
749 also provides a way to walk related memory statements. |
0 | 750 |
751 @item Points-to and escape analysis. | |
752 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
753 Points-to analysis builds a set of constraints from the GIMPLE |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
754 SSA IL representing all pointer operations and facts we do |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
755 or do not know about pointers. Solving this set of constraints |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
756 yields a conservatively correct solution for each pointer |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
757 variable in the program (though we are only interested in |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
758 SSA name pointers) as to what it may possibly point to. |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
759 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
760 This points-to solution for a given SSA name pointer is stored |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
761 in the @code{pt_solution} sub-structure of the |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
762 @code{SSA_NAME_PTR_INFO} record. The following accessor |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
763 functions are available: |
0 | 764 |
765 @itemize @bullet | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
766 @item @code{pt_solution_includes} |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
767 @item @code{pt_solutions_intersect} |
0 | 768 @end itemize |
769 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
770 Points-to analysis also computes the solution for two special |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
771 set of pointers, @code{ESCAPED} and @code{CALLUSED}. Those |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
772 represent all memory that has escaped the scope of analysis |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
773 or that is used by pure or nested const calls. |
0 | 774 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
775 @item Type-based alias analysis |
0 | 776 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
777 Type-based alias analysis is frontend dependent though generic |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
778 support is provided by the middle-end in @code{alias.c}. TBAA |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
779 code is used by both tree optimizers and RTL optimizers. |
0 | 780 |
781 Every language that wishes to perform language-specific alias analysis | |
782 should define a function that computes, given a @code{tree} | |
783 node, an alias set for the node. Nodes in different alias sets are not | |
784 allowed to alias. For an example, see the C front-end function | |
785 @code{c_get_alias_set}. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
786 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
787 @item Tree alias-oracle |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
788 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
789 The tree alias-oracle provides means to disambiguate two memory |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
790 references and memory references against statements. The following |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
791 queries are available: |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
792 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
793 @itemize @bullet |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
794 @item @code{refs_may_alias_p} |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
795 @item @code{ref_maybe_used_by_stmt_p} |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
796 @item @code{stmt_may_clobber_ref_p} |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
797 @end itemize |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
798 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
799 In addition to those two kind of statement walkers are available |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
800 walking statements related to a reference ref. |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
801 @code{walk_non_aliased_vuses} walks over dominating memory defining |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
802 statements and calls back if the statement does not clobber ref |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
803 providing the non-aliased VUSE. The walk stops at |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
804 the first clobbering statement or if asked to. |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
805 @code{walk_aliased_vdefs} walks over dominating memory defining |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
806 statements and calls back on each statement clobbering ref |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
807 providing its aliasing VDEF. The walk stops if asked to. |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
808 |
0 | 809 @end enumerate |
810 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
811 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
812 @node Memory model |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
813 @section Memory model |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
814 @cindex memory model |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
815 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
816 The memory model used by the middle-end models that of the C/C++ |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
817 languages. The middle-end has the notion of an effective type |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
818 of a memory region which is used for type-based alias analysis. |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
819 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
820 The following is a refinement of ISO C99 6.5/6, clarifying the block copy case |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
821 to follow common sense and extending the concept of a dynamic effective |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
822 type to objects with a declared type as required for C++. |
0 | 823 |
824 @smallexample | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
825 The effective type of an object for an access to its stored value is |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
826 the declared type of the object or the effective type determined by |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
827 a previous store to it. If a value is stored into an object through |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
828 an lvalue having a type that is not a character type, then the |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
829 type of the lvalue becomes the effective type of the object for that |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
830 access and for subsequent accesses that do not modify the stored value. |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
831 If a value is copied into an object using @code{memcpy} or @code{memmove}, |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
832 or is copied as an array of character type, then the effective type |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
833 of the modified object for that access and for subsequent accesses that |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
834 do not modify the value is undetermined. For all other accesses to an |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
835 object, the effective type of the object is simply the type of the |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
836 lvalue used for the access. |
0 | 837 @end smallexample |
838 |