Mercurial > hg > CbC > CbC_gcc
comparison gcc/tree-ssa-copy.c @ 0:a06113de4d67
first commit
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 17 Jul 2009 14:47:48 +0900 |
parents | |
children | 77e2b8dfacca |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:a06113de4d67 |
---|---|
1 /* Copy propagation and SSA_NAME replacement support routines. | |
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc. | |
3 | |
4 This file is part of GCC. | |
5 | |
6 GCC is free software; you can redistribute it and/or modify | |
7 it under the terms of the GNU General Public License as published by | |
8 the Free Software Foundation; either version 3, or (at your option) | |
9 any later version. | |
10 | |
11 GCC is distributed in the hope that it will be useful, | |
12 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 GNU General Public License for more details. | |
15 | |
16 You should have received a copy of the GNU General Public License | |
17 along with GCC; see the file COPYING3. If not see | |
18 <http://www.gnu.org/licenses/>. */ | |
19 | |
20 #include "config.h" | |
21 #include "system.h" | |
22 #include "coretypes.h" | |
23 #include "tm.h" | |
24 #include "tree.h" | |
25 #include "flags.h" | |
26 #include "rtl.h" | |
27 #include "tm_p.h" | |
28 #include "ggc.h" | |
29 #include "basic-block.h" | |
30 #include "output.h" | |
31 #include "expr.h" | |
32 #include "function.h" | |
33 #include "diagnostic.h" | |
34 #include "timevar.h" | |
35 #include "tree-dump.h" | |
36 #include "tree-flow.h" | |
37 #include "tree-pass.h" | |
38 #include "tree-ssa-propagate.h" | |
39 #include "langhooks.h" | |
40 | |
41 /* This file implements the copy propagation pass and provides a | |
42 handful of interfaces for performing const/copy propagation and | |
43 simple expression replacement which keep variable annotations | |
44 up-to-date. | |
45 | |
46 We require that for any copy operation where the RHS and LHS have | |
47 a non-null memory tag the memory tag be the same. It is OK | |
48 for one or both of the memory tags to be NULL. | |
49 | |
50 We also require tracking if a variable is dereferenced in a load or | |
51 store operation. | |
52 | |
53 We enforce these requirements by having all copy propagation and | |
54 replacements of one SSA_NAME with a different SSA_NAME to use the | |
55 APIs defined in this file. */ | |
56 | |
57 /* Return true if we may propagate ORIG into DEST, false otherwise. */ | |
58 | |
59 bool | |
60 may_propagate_copy (tree dest, tree orig) | |
61 { | |
62 tree type_d = TREE_TYPE (dest); | |
63 tree type_o = TREE_TYPE (orig); | |
64 | |
65 /* If ORIG flows in from an abnormal edge, it cannot be propagated. */ | |
66 if (TREE_CODE (orig) == SSA_NAME | |
67 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig)) | |
68 return false; | |
69 | |
70 /* If DEST is an SSA_NAME that flows from an abnormal edge, then it | |
71 cannot be replaced. */ | |
72 if (TREE_CODE (dest) == SSA_NAME | |
73 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest)) | |
74 return false; | |
75 | |
76 /* For memory partitions, copies are OK as long as the memory symbol | |
77 belongs to the partition. */ | |
78 if (TREE_CODE (dest) == SSA_NAME | |
79 && TREE_CODE (SSA_NAME_VAR (dest)) == MEMORY_PARTITION_TAG) | |
80 return (TREE_CODE (orig) == SSA_NAME | |
81 && !is_gimple_reg (orig) | |
82 && (SSA_NAME_VAR (dest) == SSA_NAME_VAR (orig) | |
83 || bitmap_bit_p (MPT_SYMBOLS (SSA_NAME_VAR (dest)), | |
84 DECL_UID (SSA_NAME_VAR (orig))))); | |
85 | |
86 if (TREE_CODE (orig) == SSA_NAME | |
87 && TREE_CODE (SSA_NAME_VAR (orig)) == MEMORY_PARTITION_TAG) | |
88 return (TREE_CODE (dest) == SSA_NAME | |
89 && !is_gimple_reg (dest) | |
90 && (SSA_NAME_VAR (dest) == SSA_NAME_VAR (orig) | |
91 || bitmap_bit_p (MPT_SYMBOLS (SSA_NAME_VAR (orig)), | |
92 DECL_UID (SSA_NAME_VAR (dest))))); | |
93 | |
94 /* Do not copy between types for which we *do* need a conversion. */ | |
95 if (!useless_type_conversion_p (type_d, type_o)) | |
96 return false; | |
97 | |
98 /* FIXME. GIMPLE is allowing pointer assignments and comparisons of | |
99 pointers that have different alias sets. This means that these | |
100 pointers will have different memory tags associated to them. | |
101 | |
102 If we allow copy propagation in these cases, statements de-referencing | |
103 the new pointer will now have a reference to a different memory tag | |
104 with potentially incorrect SSA information. | |
105 | |
106 This was showing up in libjava/java/util/zip/ZipFile.java with code | |
107 like: | |
108 | |
109 struct java.io.BufferedInputStream *T.660; | |
110 struct java.io.BufferedInputStream *T.647; | |
111 struct java.io.InputStream *is; | |
112 struct java.io.InputStream *is.662; | |
113 [ ... ] | |
114 T.660 = T.647; | |
115 is = T.660; <-- This ought to be type-casted | |
116 is.662 = is; | |
117 | |
118 Also, f/name.c exposed a similar problem with a COND_EXPR predicate | |
119 that was causing DOM to generate and equivalence with two pointers of | |
120 alias-incompatible types: | |
121 | |
122 struct _ffename_space *n; | |
123 struct _ffename *ns; | |
124 [ ... ] | |
125 if (n == ns) | |
126 goto lab; | |
127 ... | |
128 lab: | |
129 return n; | |
130 | |
131 I think that GIMPLE should emit the appropriate type-casts. For the | |
132 time being, blocking copy-propagation in these cases is the safe thing | |
133 to do. */ | |
134 if (TREE_CODE (dest) == SSA_NAME | |
135 && TREE_CODE (orig) == SSA_NAME | |
136 && POINTER_TYPE_P (type_d) | |
137 && POINTER_TYPE_P (type_o)) | |
138 { | |
139 tree mt_dest = symbol_mem_tag (SSA_NAME_VAR (dest)); | |
140 tree mt_orig = symbol_mem_tag (SSA_NAME_VAR (orig)); | |
141 if (mt_dest && mt_orig && mt_dest != mt_orig) | |
142 return false; | |
143 else if (get_alias_set (TREE_TYPE (type_d)) != | |
144 get_alias_set (TREE_TYPE (type_o))) | |
145 return false; | |
146 else if (!MTAG_P (SSA_NAME_VAR (dest)) | |
147 && !MTAG_P (SSA_NAME_VAR (orig)) | |
148 && (DECL_NO_TBAA_P (SSA_NAME_VAR (dest)) | |
149 != DECL_NO_TBAA_P (SSA_NAME_VAR (orig)))) | |
150 return false; | |
151 | |
152 /* Also verify flow-sensitive information is compatible. */ | |
153 if (SSA_NAME_PTR_INFO (orig) && SSA_NAME_PTR_INFO (dest)) | |
154 { | |
155 struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig); | |
156 struct ptr_info_def *dest_ptr_info = SSA_NAME_PTR_INFO (dest); | |
157 | |
158 if (orig_ptr_info->name_mem_tag | |
159 && dest_ptr_info->name_mem_tag | |
160 && orig_ptr_info->pt_vars | |
161 && dest_ptr_info->pt_vars | |
162 && !bitmap_intersect_p (dest_ptr_info->pt_vars, | |
163 orig_ptr_info->pt_vars)) | |
164 return false; | |
165 } | |
166 } | |
167 | |
168 /* If the destination is a SSA_NAME for a virtual operand, then we have | |
169 some special cases to handle. */ | |
170 if (TREE_CODE (dest) == SSA_NAME && !is_gimple_reg (dest)) | |
171 { | |
172 /* If both operands are SSA_NAMEs referring to virtual operands, then | |
173 we can always propagate. */ | |
174 if (TREE_CODE (orig) == SSA_NAME | |
175 && !is_gimple_reg (orig)) | |
176 return true; | |
177 | |
178 /* We have a "copy" from something like a constant into a virtual | |
179 operand. Reject these. */ | |
180 return false; | |
181 } | |
182 | |
183 /* Anything else is OK. */ | |
184 return true; | |
185 } | |
186 | |
187 /* Like may_propagate_copy, but use as the destination expression | |
188 the principal expression (typically, the RHS) contained in | |
189 statement DEST. This is more efficient when working with the | |
190 gimple tuples representation. */ | |
191 | |
192 bool | |
193 may_propagate_copy_into_stmt (gimple dest, tree orig) | |
194 { | |
195 tree type_d; | |
196 tree type_o; | |
197 | |
198 /* If the statement is a switch or a single-rhs assignment, | |
199 then the expression to be replaced by the propagation may | |
200 be an SSA_NAME. Fortunately, there is an explicit tree | |
201 for the expression, so we delegate to may_propagate_copy. */ | |
202 | |
203 if (gimple_assign_single_p (dest)) | |
204 return may_propagate_copy (gimple_assign_rhs1 (dest), orig); | |
205 else if (gimple_code (dest) == GIMPLE_SWITCH) | |
206 return may_propagate_copy (gimple_switch_index (dest), orig); | |
207 | |
208 /* In other cases, the expression is not materialized, so there | |
209 is no destination to pass to may_propagate_copy. On the other | |
210 hand, the expression cannot be an SSA_NAME, so the analysis | |
211 is much simpler. */ | |
212 | |
213 if (TREE_CODE (orig) == SSA_NAME | |
214 && (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig) | |
215 || TREE_CODE (SSA_NAME_VAR (orig)) == MEMORY_PARTITION_TAG)) | |
216 return false; | |
217 | |
218 if (is_gimple_assign (dest)) | |
219 type_d = TREE_TYPE (gimple_assign_lhs (dest)); | |
220 else if (gimple_code (dest) == GIMPLE_COND) | |
221 type_d = boolean_type_node; | |
222 else if (is_gimple_call (dest) | |
223 && gimple_call_lhs (dest) != NULL_TREE) | |
224 type_d = TREE_TYPE (gimple_call_lhs (dest)); | |
225 else | |
226 gcc_unreachable (); | |
227 | |
228 type_o = TREE_TYPE (orig); | |
229 | |
230 if (!useless_type_conversion_p (type_d, type_o)) | |
231 return false; | |
232 | |
233 return true; | |
234 } | |
235 | |
236 /* Similarly, but we know that we're propagating into an ASM_EXPR. */ | |
237 | |
238 bool | |
239 may_propagate_copy_into_asm (tree dest) | |
240 { | |
241 /* Hard register operands of asms are special. Do not bypass. */ | |
242 return !(TREE_CODE (dest) == SSA_NAME | |
243 && TREE_CODE (SSA_NAME_VAR (dest)) == VAR_DECL | |
244 && DECL_HARD_REGISTER (SSA_NAME_VAR (dest))); | |
245 } | |
246 | |
247 | |
248 /* Given two SSA_NAMEs pointers ORIG and NEW such that we are copy | |
249 propagating NEW into ORIG, consolidate aliasing information so that | |
250 they both share the same memory tags. */ | |
251 | |
252 void | |
253 merge_alias_info (tree orig_name, tree new_name) | |
254 { | |
255 tree new_sym = SSA_NAME_VAR (new_name); | |
256 tree orig_sym = SSA_NAME_VAR (orig_name); | |
257 var_ann_t new_ann = var_ann (new_sym); | |
258 var_ann_t orig_ann = var_ann (orig_sym); | |
259 | |
260 /* No merging necessary when memory partitions are involved. */ | |
261 if (factoring_name_p (new_name)) | |
262 { | |
263 gcc_assert (!is_gimple_reg (orig_sym)); | |
264 return; | |
265 } | |
266 else if (factoring_name_p (orig_name)) | |
267 { | |
268 gcc_assert (!is_gimple_reg (new_sym)); | |
269 return; | |
270 } | |
271 | |
272 gcc_assert (POINTER_TYPE_P (TREE_TYPE (orig_name)) | |
273 && POINTER_TYPE_P (TREE_TYPE (new_name))); | |
274 | |
275 #if defined ENABLE_CHECKING | |
276 gcc_assert (useless_type_conversion_p (TREE_TYPE (orig_name), | |
277 TREE_TYPE (new_name))); | |
278 | |
279 /* Check that flow-sensitive information is compatible. Notice that | |
280 we may not merge flow-sensitive information here. This function | |
281 is called when propagating equivalences dictated by the IL, like | |
282 a copy operation P_i = Q_j, and from equivalences dictated by | |
283 control-flow, like if (P_i == Q_j). | |
284 | |
285 In the former case, P_i and Q_j are equivalent in every block | |
286 dominated by the assignment, so their flow-sensitive information | |
287 is always the same. However, in the latter case, the pointers | |
288 P_i and Q_j are only equivalent in one of the sub-graphs out of | |
289 the predicate, so their flow-sensitive information is not the | |
290 same in every block dominated by the predicate. | |
291 | |
292 Since we cannot distinguish one case from another in this | |
293 function, we can only make sure that if P_i and Q_j have | |
294 flow-sensitive information, they should be compatible. | |
295 | |
296 As callers of merge_alias_info are supposed to call may_propagate_copy | |
297 first, the following check is redundant. Thus, only do it if checking | |
298 is enabled. */ | |
299 if (SSA_NAME_PTR_INFO (orig_name) && SSA_NAME_PTR_INFO (new_name)) | |
300 { | |
301 struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig_name); | |
302 struct ptr_info_def *new_ptr_info = SSA_NAME_PTR_INFO (new_name); | |
303 | |
304 /* Note that pointer NEW and ORIG may actually have different | |
305 pointed-to variables (e.g., PR 18291 represented in | |
306 testsuite/gcc.c-torture/compile/pr18291.c). However, since | |
307 NEW is being copy-propagated into ORIG, it must always be | |
308 true that the pointed-to set for pointer NEW is the same, or | |
309 a subset, of the pointed-to set for pointer ORIG. If this | |
310 isn't the case, we shouldn't have been able to do the | |
311 propagation of NEW into ORIG. */ | |
312 if (orig_ptr_info->name_mem_tag | |
313 && new_ptr_info->name_mem_tag | |
314 && orig_ptr_info->pt_vars | |
315 && new_ptr_info->pt_vars) | |
316 gcc_assert (bitmap_intersect_p (new_ptr_info->pt_vars, | |
317 orig_ptr_info->pt_vars)); | |
318 } | |
319 #endif | |
320 | |
321 /* Synchronize the symbol tags. If both pointers had a tag and they | |
322 are different, then something has gone wrong. Symbol tags can | |
323 always be merged because they are flow insensitive, all the SSA | |
324 names of the same base DECL share the same symbol tag. */ | |
325 if (new_ann->symbol_mem_tag == NULL_TREE) | |
326 new_ann->symbol_mem_tag = orig_ann->symbol_mem_tag; | |
327 else if (orig_ann->symbol_mem_tag == NULL_TREE) | |
328 orig_ann->symbol_mem_tag = new_ann->symbol_mem_tag; | |
329 else | |
330 gcc_assert (new_ann->symbol_mem_tag == orig_ann->symbol_mem_tag); | |
331 | |
332 /* Copy flow-sensitive alias information in case that NEW_NAME | |
333 didn't get a NMT but was set to pt_anything for optimization | |
334 purposes. In case ORIG_NAME has a NMT we can safely use its | |
335 flow-sensitive alias information as a conservative estimate. */ | |
336 if (SSA_NAME_PTR_INFO (orig_name) | |
337 && SSA_NAME_PTR_INFO (orig_name)->name_mem_tag | |
338 && (!SSA_NAME_PTR_INFO (new_name) | |
339 || !SSA_NAME_PTR_INFO (new_name)->name_mem_tag)) | |
340 { | |
341 struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig_name); | |
342 struct ptr_info_def *new_ptr_info = get_ptr_info (new_name); | |
343 memcpy (new_ptr_info, orig_ptr_info, sizeof (struct ptr_info_def)); | |
344 } | |
345 } | |
346 | |
347 | |
348 /* Common code for propagate_value and replace_exp. | |
349 | |
350 Replace use operand OP_P with VAL. FOR_PROPAGATION indicates if the | |
351 replacement is done to propagate a value or not. */ | |
352 | |
353 static void | |
354 replace_exp_1 (use_operand_p op_p, tree val, | |
355 bool for_propagation ATTRIBUTE_UNUSED) | |
356 { | |
357 tree op = USE_FROM_PTR (op_p); | |
358 | |
359 #if defined ENABLE_CHECKING | |
360 gcc_assert (!(for_propagation | |
361 && TREE_CODE (op) == SSA_NAME | |
362 && TREE_CODE (val) == SSA_NAME | |
363 && !may_propagate_copy (op, val))); | |
364 #endif | |
365 | |
366 if (TREE_CODE (val) == SSA_NAME) | |
367 { | |
368 if (TREE_CODE (op) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (op))) | |
369 merge_alias_info (op, val); | |
370 SET_USE (op_p, val); | |
371 } | |
372 else | |
373 SET_USE (op_p, unsave_expr_now (val)); | |
374 } | |
375 | |
376 | |
377 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME) | |
378 into the operand pointed to by OP_P. | |
379 | |
380 Use this version for const/copy propagation as it will perform additional | |
381 checks to ensure validity of the const/copy propagation. */ | |
382 | |
383 void | |
384 propagate_value (use_operand_p op_p, tree val) | |
385 { | |
386 replace_exp_1 (op_p, val, true); | |
387 } | |
388 | |
389 /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME). | |
390 | |
391 Use this version when not const/copy propagating values. For example, | |
392 PRE uses this version when building expressions as they would appear | |
393 in specific blocks taking into account actions of PHI nodes. */ | |
394 | |
395 void | |
396 replace_exp (use_operand_p op_p, tree val) | |
397 { | |
398 replace_exp_1 (op_p, val, false); | |
399 } | |
400 | |
401 | |
402 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME) | |
403 into the tree pointed to by OP_P. | |
404 | |
405 Use this version for const/copy propagation when SSA operands are not | |
406 available. It will perform the additional checks to ensure validity of | |
407 the const/copy propagation, but will not update any operand information. | |
408 Be sure to mark the stmt as modified. */ | |
409 | |
410 void | |
411 propagate_tree_value (tree *op_p, tree val) | |
412 { | |
413 #if defined ENABLE_CHECKING | |
414 gcc_assert (!(TREE_CODE (val) == SSA_NAME | |
415 && *op_p | |
416 && TREE_CODE (*op_p) == SSA_NAME | |
417 && !may_propagate_copy (*op_p, val))); | |
418 #endif | |
419 | |
420 if (TREE_CODE (val) == SSA_NAME) | |
421 { | |
422 if (*op_p && TREE_CODE (*op_p) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (*op_p))) | |
423 merge_alias_info (*op_p, val); | |
424 *op_p = val; | |
425 } | |
426 else | |
427 *op_p = unsave_expr_now (val); | |
428 } | |
429 | |
430 | |
431 /* Like propagate_tree_value, but use as the operand to replace | |
432 the principal expression (typically, the RHS) contained in the | |
433 statement referenced by iterator GSI. Note that it is not | |
434 always possible to update the statement in-place, so a new | |
435 statement may be created to replace the original. */ | |
436 | |
437 void | |
438 propagate_tree_value_into_stmt (gimple_stmt_iterator *gsi, tree val) | |
439 { | |
440 gimple stmt = gsi_stmt (*gsi); | |
441 | |
442 if (is_gimple_assign (stmt)) | |
443 { | |
444 tree expr = NULL_TREE; | |
445 if (gimple_assign_single_p (stmt)) | |
446 expr = gimple_assign_rhs1 (stmt); | |
447 propagate_tree_value (&expr, val); | |
448 gimple_assign_set_rhs_from_tree (gsi, expr); | |
449 stmt = gsi_stmt (*gsi); | |
450 } | |
451 else if (gimple_code (stmt) == GIMPLE_COND) | |
452 { | |
453 tree lhs = NULL_TREE; | |
454 tree rhs = fold_convert (TREE_TYPE (val), integer_zero_node); | |
455 propagate_tree_value (&lhs, val); | |
456 gimple_cond_set_code (stmt, NE_EXPR); | |
457 gimple_cond_set_lhs (stmt, lhs); | |
458 gimple_cond_set_rhs (stmt, rhs); | |
459 } | |
460 else if (is_gimple_call (stmt) | |
461 && gimple_call_lhs (stmt) != NULL_TREE) | |
462 { | |
463 gimple new_stmt; | |
464 | |
465 tree expr = NULL_TREE; | |
466 propagate_tree_value (&expr, val); | |
467 new_stmt = gimple_build_assign (gimple_call_lhs (stmt), expr); | |
468 copy_virtual_operands (new_stmt, stmt); | |
469 move_ssa_defining_stmt_for_defs (new_stmt, stmt); | |
470 gsi_replace (gsi, new_stmt, false); | |
471 } | |
472 else if (gimple_code (stmt) == GIMPLE_SWITCH) | |
473 propagate_tree_value (gimple_switch_index_ptr (stmt), val); | |
474 else | |
475 gcc_unreachable (); | |
476 } | |
477 | |
478 /*--------------------------------------------------------------------------- | |
479 Copy propagation | |
480 ---------------------------------------------------------------------------*/ | |
481 /* During propagation, we keep chains of variables that are copies of | |
482 one another. If variable X_i is a copy of X_j and X_j is a copy of | |
483 X_k, COPY_OF will contain: | |
484 | |
485 COPY_OF[i].VALUE = X_j | |
486 COPY_OF[j].VALUE = X_k | |
487 COPY_OF[k].VALUE = X_k | |
488 | |
489 After propagation, the copy-of value for each variable X_i is | |
490 converted into the final value by walking the copy-of chains and | |
491 updating COPY_OF[i].VALUE to be the last element of the chain. */ | |
492 static prop_value_t *copy_of; | |
493 | |
494 /* Used in set_copy_of_val to determine if the last link of a copy-of | |
495 chain has changed. */ | |
496 static tree *cached_last_copy_of; | |
497 | |
498 | |
499 /* Return true if this statement may generate a useful copy. */ | |
500 | |
501 static bool | |
502 stmt_may_generate_copy (gimple stmt) | |
503 { | |
504 if (gimple_code (stmt) == GIMPLE_PHI) | |
505 return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt)); | |
506 | |
507 if (gimple_code (stmt) != GIMPLE_ASSIGN) | |
508 return false; | |
509 | |
510 /* If the statement has volatile operands, it won't generate a | |
511 useful copy. */ | |
512 if (gimple_has_volatile_ops (stmt)) | |
513 return false; | |
514 | |
515 /* Statements with loads and/or stores will never generate a useful copy. */ | |
516 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) | |
517 return false; | |
518 | |
519 /* Otherwise, the only statements that generate useful copies are | |
520 assignments whose RHS is just an SSA name that doesn't flow | |
521 through abnormal edges. */ | |
522 return (gimple_assign_rhs_code (stmt) == SSA_NAME | |
523 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt))); | |
524 } | |
525 | |
526 | |
527 /* Return the copy-of value for VAR. */ | |
528 | |
529 static inline prop_value_t * | |
530 get_copy_of_val (tree var) | |
531 { | |
532 prop_value_t *val = ©_of[SSA_NAME_VERSION (var)]; | |
533 | |
534 if (val->value == NULL_TREE | |
535 && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var))) | |
536 { | |
537 /* If the variable will never generate a useful copy relation, | |
538 make it its own copy. */ | |
539 val->value = var; | |
540 } | |
541 | |
542 return val; | |
543 } | |
544 | |
545 | |
546 /* Return last link in the copy-of chain for VAR. */ | |
547 | |
548 static tree | |
549 get_last_copy_of (tree var) | |
550 { | |
551 tree last; | |
552 int i; | |
553 | |
554 /* Traverse COPY_OF starting at VAR until we get to the last | |
555 link in the chain. Since it is possible to have cycles in PHI | |
556 nodes, the copy-of chain may also contain cycles. | |
557 | |
558 To avoid infinite loops and to avoid traversing lengthy copy-of | |
559 chains, we artificially limit the maximum number of chains we are | |
560 willing to traverse. | |
561 | |
562 The value 5 was taken from a compiler and runtime library | |
563 bootstrap and a mixture of C and C++ code from various sources. | |
564 More than 82% of all copy-of chains were shorter than 5 links. */ | |
565 #define LIMIT 5 | |
566 | |
567 last = var; | |
568 for (i = 0; i < LIMIT; i++) | |
569 { | |
570 tree copy = copy_of[SSA_NAME_VERSION (last)].value; | |
571 if (copy == NULL_TREE || copy == last) | |
572 break; | |
573 last = copy; | |
574 } | |
575 | |
576 /* If we have reached the limit, then we are either in a copy-of | |
577 cycle or the copy-of chain is too long. In this case, just | |
578 return VAR so that it is not considered a copy of anything. */ | |
579 return (i < LIMIT ? last : var); | |
580 } | |
581 | |
582 | |
583 /* Set FIRST to be the first variable in the copy-of chain for DEST. | |
584 If DEST's copy-of value or its copy-of chain has changed, return | |
585 true. | |
586 | |
587 MEM_REF is the memory reference where FIRST is stored. This is | |
588 used when DEST is a non-register and we are copy propagating loads | |
589 and stores. */ | |
590 | |
591 static inline bool | |
592 set_copy_of_val (tree dest, tree first) | |
593 { | |
594 unsigned int dest_ver = SSA_NAME_VERSION (dest); | |
595 tree old_first, old_last, new_last; | |
596 | |
597 /* Set FIRST to be the first link in COPY_OF[DEST]. If that | |
598 changed, return true. */ | |
599 old_first = copy_of[dest_ver].value; | |
600 copy_of[dest_ver].value = first; | |
601 | |
602 if (old_first != first) | |
603 return true; | |
604 | |
605 /* If FIRST and OLD_FIRST are the same, we need to check whether the | |
606 copy-of chain starting at FIRST ends in a different variable. If | |
607 the copy-of chain starting at FIRST ends up in a different | |
608 variable than the last cached value we had for DEST, then return | |
609 true because DEST is now a copy of a different variable. | |
610 | |
611 This test is necessary because even though the first link in the | |
612 copy-of chain may not have changed, if any of the variables in | |
613 the copy-of chain changed its final value, DEST will now be the | |
614 copy of a different variable, so we have to do another round of | |
615 propagation for everything that depends on DEST. */ | |
616 old_last = cached_last_copy_of[dest_ver]; | |
617 new_last = get_last_copy_of (dest); | |
618 cached_last_copy_of[dest_ver] = new_last; | |
619 | |
620 return (old_last != new_last); | |
621 } | |
622 | |
623 | |
624 /* Dump the copy-of value for variable VAR to FILE. */ | |
625 | |
626 static void | |
627 dump_copy_of (FILE *file, tree var) | |
628 { | |
629 tree val; | |
630 sbitmap visited; | |
631 | |
632 print_generic_expr (file, var, dump_flags); | |
633 | |
634 if (TREE_CODE (var) != SSA_NAME) | |
635 return; | |
636 | |
637 visited = sbitmap_alloc (num_ssa_names); | |
638 sbitmap_zero (visited); | |
639 SET_BIT (visited, SSA_NAME_VERSION (var)); | |
640 | |
641 fprintf (file, " copy-of chain: "); | |
642 | |
643 val = var; | |
644 print_generic_expr (file, val, 0); | |
645 fprintf (file, " "); | |
646 while (copy_of[SSA_NAME_VERSION (val)].value) | |
647 { | |
648 fprintf (file, "-> "); | |
649 val = copy_of[SSA_NAME_VERSION (val)].value; | |
650 print_generic_expr (file, val, 0); | |
651 fprintf (file, " "); | |
652 if (TEST_BIT (visited, SSA_NAME_VERSION (val))) | |
653 break; | |
654 SET_BIT (visited, SSA_NAME_VERSION (val)); | |
655 } | |
656 | |
657 val = get_copy_of_val (var)->value; | |
658 if (val == NULL_TREE) | |
659 fprintf (file, "[UNDEFINED]"); | |
660 else if (val != var) | |
661 fprintf (file, "[COPY]"); | |
662 else | |
663 fprintf (file, "[NOT A COPY]"); | |
664 | |
665 sbitmap_free (visited); | |
666 } | |
667 | |
668 | |
669 /* Evaluate the RHS of STMT. If it produces a valid copy, set the LHS | |
670 value and store the LHS into *RESULT_P. If STMT generates more | |
671 than one name (i.e., STMT is an aliased store), it is enough to | |
672 store the first name in the VDEF list into *RESULT_P. After | |
673 all, the names generated will be VUSEd in the same statements. */ | |
674 | |
675 static enum ssa_prop_result | |
676 copy_prop_visit_assignment (gimple stmt, tree *result_p) | |
677 { | |
678 tree lhs, rhs; | |
679 prop_value_t *rhs_val; | |
680 | |
681 lhs = gimple_assign_lhs (stmt); | |
682 rhs = gimple_assign_rhs1 (stmt); | |
683 | |
684 | |
685 gcc_assert (gimple_assign_rhs_code (stmt) == SSA_NAME); | |
686 | |
687 rhs_val = get_copy_of_val (rhs); | |
688 | |
689 if (TREE_CODE (lhs) == SSA_NAME) | |
690 { | |
691 /* Straight copy between two SSA names. First, make sure that | |
692 we can propagate the RHS into uses of LHS. */ | |
693 if (!may_propagate_copy (lhs, rhs)) | |
694 return SSA_PROP_VARYING; | |
695 | |
696 /* Notice that in the case of assignments, we make the LHS be a | |
697 copy of RHS's value, not of RHS itself. This avoids keeping | |
698 unnecessary copy-of chains (assignments cannot be in a cycle | |
699 like PHI nodes), speeding up the propagation process. | |
700 This is different from what we do in copy_prop_visit_phi_node. | |
701 In those cases, we are interested in the copy-of chains. */ | |
702 *result_p = lhs; | |
703 if (set_copy_of_val (*result_p, rhs_val->value)) | |
704 return SSA_PROP_INTERESTING; | |
705 else | |
706 return SSA_PROP_NOT_INTERESTING; | |
707 } | |
708 | |
709 return SSA_PROP_VARYING; | |
710 } | |
711 | |
712 | |
713 /* Visit the GIMPLE_COND STMT. Return SSA_PROP_INTERESTING | |
714 if it can determine which edge will be taken. Otherwise, return | |
715 SSA_PROP_VARYING. */ | |
716 | |
717 static enum ssa_prop_result | |
718 copy_prop_visit_cond_stmt (gimple stmt, edge *taken_edge_p) | |
719 { | |
720 enum ssa_prop_result retval = SSA_PROP_VARYING; | |
721 | |
722 tree op0 = gimple_cond_lhs (stmt); | |
723 tree op1 = gimple_cond_rhs (stmt); | |
724 | |
725 /* The only conditionals that we may be able to compute statically | |
726 are predicates involving two SSA_NAMEs. */ | |
727 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME) | |
728 { | |
729 op0 = get_last_copy_of (op0); | |
730 op1 = get_last_copy_of (op1); | |
731 | |
732 /* See if we can determine the predicate's value. */ | |
733 if (dump_file && (dump_flags & TDF_DETAILS)) | |
734 { | |
735 fprintf (dump_file, "Trying to determine truth value of "); | |
736 fprintf (dump_file, "predicate "); | |
737 print_gimple_stmt (dump_file, stmt, 0, 0); | |
738 } | |
739 | |
740 /* We can fold COND and get a useful result only when we have | |
741 the same SSA_NAME on both sides of a comparison operator. */ | |
742 if (op0 == op1) | |
743 { | |
744 tree folded_cond = fold_binary (gimple_cond_code (stmt), | |
745 boolean_type_node, op0, op1); | |
746 if (folded_cond) | |
747 { | |
748 basic_block bb = gimple_bb (stmt); | |
749 *taken_edge_p = find_taken_edge (bb, folded_cond); | |
750 if (*taken_edge_p) | |
751 retval = SSA_PROP_INTERESTING; | |
752 } | |
753 } | |
754 } | |
755 | |
756 if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p) | |
757 fprintf (dump_file, "\nConditional will always take edge %d->%d\n", | |
758 (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index); | |
759 | |
760 return retval; | |
761 } | |
762 | |
763 | |
764 /* Evaluate statement STMT. If the statement produces a new output | |
765 value, return SSA_PROP_INTERESTING and store the SSA_NAME holding | |
766 the new value in *RESULT_P. | |
767 | |
768 If STMT is a conditional branch and we can determine its truth | |
769 value, set *TAKEN_EDGE_P accordingly. | |
770 | |
771 If the new value produced by STMT is varying, return | |
772 SSA_PROP_VARYING. */ | |
773 | |
774 static enum ssa_prop_result | |
775 copy_prop_visit_stmt (gimple stmt, edge *taken_edge_p, tree *result_p) | |
776 { | |
777 enum ssa_prop_result retval; | |
778 | |
779 if (dump_file && (dump_flags & TDF_DETAILS)) | |
780 { | |
781 fprintf (dump_file, "\nVisiting statement:\n"); | |
782 print_gimple_stmt (dump_file, stmt, 0, dump_flags); | |
783 fprintf (dump_file, "\n"); | |
784 } | |
785 | |
786 if (gimple_assign_single_p (stmt) | |
787 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME | |
788 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME) | |
789 { | |
790 /* If the statement is a copy assignment, evaluate its RHS to | |
791 see if the lattice value of its output has changed. */ | |
792 retval = copy_prop_visit_assignment (stmt, result_p); | |
793 } | |
794 else if (gimple_code (stmt) == GIMPLE_COND) | |
795 { | |
796 /* See if we can determine which edge goes out of a conditional | |
797 jump. */ | |
798 retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p); | |
799 } | |
800 else | |
801 retval = SSA_PROP_VARYING; | |
802 | |
803 if (retval == SSA_PROP_VARYING) | |
804 { | |
805 tree def; | |
806 ssa_op_iter i; | |
807 | |
808 /* Any other kind of statement is not interesting for constant | |
809 propagation and, therefore, not worth simulating. */ | |
810 if (dump_file && (dump_flags & TDF_DETAILS)) | |
811 fprintf (dump_file, "No interesting values produced.\n"); | |
812 | |
813 /* The assignment is not a copy operation. Don't visit this | |
814 statement again and mark all the definitions in the statement | |
815 to be copies of nothing. */ | |
816 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS) | |
817 set_copy_of_val (def, def); | |
818 } | |
819 | |
820 return retval; | |
821 } | |
822 | |
823 | |
824 /* Visit PHI node PHI. If all the arguments produce the same value, | |
825 set it to be the value of the LHS of PHI. */ | |
826 | |
827 static enum ssa_prop_result | |
828 copy_prop_visit_phi_node (gimple phi) | |
829 { | |
830 enum ssa_prop_result retval; | |
831 unsigned i; | |
832 prop_value_t phi_val = { 0, NULL_TREE }; | |
833 | |
834 tree lhs = gimple_phi_result (phi); | |
835 | |
836 if (dump_file && (dump_flags & TDF_DETAILS)) | |
837 { | |
838 fprintf (dump_file, "\nVisiting PHI node: "); | |
839 print_gimple_stmt (dump_file, phi, 0, dump_flags); | |
840 fprintf (dump_file, "\n\n"); | |
841 } | |
842 | |
843 for (i = 0; i < gimple_phi_num_args (phi); i++) | |
844 { | |
845 prop_value_t *arg_val; | |
846 tree arg = gimple_phi_arg_def (phi, i); | |
847 edge e = gimple_phi_arg_edge (phi, i); | |
848 | |
849 /* We don't care about values flowing through non-executable | |
850 edges. */ | |
851 if (!(e->flags & EDGE_EXECUTABLE)) | |
852 continue; | |
853 | |
854 /* Constants in the argument list never generate a useful copy. | |
855 Similarly, names that flow through abnormal edges cannot be | |
856 used to derive copies. */ | |
857 if (TREE_CODE (arg) != SSA_NAME || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg)) | |
858 { | |
859 phi_val.value = lhs; | |
860 break; | |
861 } | |
862 | |
863 /* Avoid copy propagation from an inner into an outer loop. | |
864 Otherwise, this may move loop variant variables outside of | |
865 their loops and prevent coalescing opportunities. If the | |
866 value was loop invariant, it will be hoisted by LICM and | |
867 exposed for copy propagation. */ | |
868 if (loop_depth_of_name (arg) > loop_depth_of_name (lhs)) | |
869 { | |
870 phi_val.value = lhs; | |
871 break; | |
872 } | |
873 | |
874 /* If the LHS appears in the argument list, ignore it. It is | |
875 irrelevant as a copy. */ | |
876 if (arg == lhs || get_last_copy_of (arg) == lhs) | |
877 continue; | |
878 | |
879 if (dump_file && (dump_flags & TDF_DETAILS)) | |
880 { | |
881 fprintf (dump_file, "\tArgument #%d: ", i); | |
882 dump_copy_of (dump_file, arg); | |
883 fprintf (dump_file, "\n"); | |
884 } | |
885 | |
886 arg_val = get_copy_of_val (arg); | |
887 | |
888 /* If the LHS didn't have a value yet, make it a copy of the | |
889 first argument we find. Notice that while we make the LHS be | |
890 a copy of the argument itself, we take the memory reference | |
891 from the argument's value so that we can compare it to the | |
892 memory reference of all the other arguments. */ | |
893 if (phi_val.value == NULL_TREE) | |
894 { | |
895 phi_val.value = arg; | |
896 continue; | |
897 } | |
898 | |
899 /* If PHI_VAL and ARG don't have a common copy-of chain, then | |
900 this PHI node cannot be a copy operation. Also, if we are | |
901 copy propagating stores and these two arguments came from | |
902 different memory references, they cannot be considered | |
903 copies. */ | |
904 if (get_last_copy_of (phi_val.value) != get_last_copy_of (arg)) | |
905 { | |
906 phi_val.value = lhs; | |
907 break; | |
908 } | |
909 } | |
910 | |
911 if (phi_val.value && may_propagate_copy (lhs, phi_val.value) | |
912 && set_copy_of_val (lhs, phi_val.value)) | |
913 retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING; | |
914 else | |
915 retval = SSA_PROP_NOT_INTERESTING; | |
916 | |
917 if (dump_file && (dump_flags & TDF_DETAILS)) | |
918 { | |
919 fprintf (dump_file, "\nPHI node "); | |
920 dump_copy_of (dump_file, lhs); | |
921 fprintf (dump_file, "\nTelling the propagator to "); | |
922 if (retval == SSA_PROP_INTERESTING) | |
923 fprintf (dump_file, "add SSA edges out of this PHI and continue."); | |
924 else if (retval == SSA_PROP_VARYING) | |
925 fprintf (dump_file, "add SSA edges out of this PHI and never visit again."); | |
926 else | |
927 fprintf (dump_file, "do nothing with SSA edges and keep iterating."); | |
928 fprintf (dump_file, "\n\n"); | |
929 } | |
930 | |
931 return retval; | |
932 } | |
933 | |
934 | |
935 /* Initialize structures used for copy propagation. PHIS_ONLY is true | |
936 if we should only consider PHI nodes as generating copy propagation | |
937 opportunities. */ | |
938 | |
939 static void | |
940 init_copy_prop (void) | |
941 { | |
942 basic_block bb; | |
943 | |
944 copy_of = XCNEWVEC (prop_value_t, num_ssa_names); | |
945 | |
946 cached_last_copy_of = XCNEWVEC (tree, num_ssa_names); | |
947 | |
948 FOR_EACH_BB (bb) | |
949 { | |
950 gimple_stmt_iterator si; | |
951 int depth = bb->loop_depth; | |
952 | |
953 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) | |
954 { | |
955 gimple stmt = gsi_stmt (si); | |
956 ssa_op_iter iter; | |
957 tree def; | |
958 | |
959 /* The only statements that we care about are those that may | |
960 generate useful copies. We also need to mark conditional | |
961 jumps so that their outgoing edges are added to the work | |
962 lists of the propagator. | |
963 | |
964 Avoid copy propagation from an inner into an outer loop. | |
965 Otherwise, this may move loop variant variables outside of | |
966 their loops and prevent coalescing opportunities. If the | |
967 value was loop invariant, it will be hoisted by LICM and | |
968 exposed for copy propagation. */ | |
969 if (stmt_ends_bb_p (stmt)) | |
970 prop_set_simulate_again (stmt, true); | |
971 else if (stmt_may_generate_copy (stmt) | |
972 /* Since we are iterating over the statements in | |
973 BB, not the phi nodes, STMT will always be an | |
974 assignment. */ | |
975 && loop_depth_of_name (gimple_assign_rhs1 (stmt)) <= depth) | |
976 prop_set_simulate_again (stmt, true); | |
977 else | |
978 prop_set_simulate_again (stmt, false); | |
979 | |
980 /* Mark all the outputs of this statement as not being | |
981 the copy of anything. */ | |
982 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) | |
983 if (!prop_simulate_again_p (stmt)) | |
984 set_copy_of_val (def, def); | |
985 else | |
986 cached_last_copy_of[SSA_NAME_VERSION (def)] = def; | |
987 } | |
988 | |
989 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) | |
990 { | |
991 gimple phi = gsi_stmt (si); | |
992 tree def; | |
993 | |
994 def = gimple_phi_result (phi); | |
995 if (!is_gimple_reg (def)) | |
996 prop_set_simulate_again (phi, false); | |
997 else | |
998 prop_set_simulate_again (phi, true); | |
999 | |
1000 if (!prop_simulate_again_p (phi)) | |
1001 set_copy_of_val (def, def); | |
1002 else | |
1003 cached_last_copy_of[SSA_NAME_VERSION (def)] = def; | |
1004 } | |
1005 } | |
1006 } | |
1007 | |
1008 | |
1009 /* Deallocate memory used in copy propagation and do final | |
1010 substitution. */ | |
1011 | |
1012 static void | |
1013 fini_copy_prop (void) | |
1014 { | |
1015 size_t i; | |
1016 prop_value_t *tmp; | |
1017 | |
1018 /* Set the final copy-of value for each variable by traversing the | |
1019 copy-of chains. */ | |
1020 tmp = XCNEWVEC (prop_value_t, num_ssa_names); | |
1021 for (i = 1; i < num_ssa_names; i++) | |
1022 { | |
1023 tree var = ssa_name (i); | |
1024 if (var && copy_of[i].value && copy_of[i].value != var) | |
1025 tmp[i].value = get_last_copy_of (var); | |
1026 } | |
1027 | |
1028 substitute_and_fold (tmp, false); | |
1029 | |
1030 free (cached_last_copy_of); | |
1031 free (copy_of); | |
1032 free (tmp); | |
1033 } | |
1034 | |
1035 | |
1036 /* Main entry point to the copy propagator. | |
1037 | |
1038 PHIS_ONLY is true if we should only consider PHI nodes as generating | |
1039 copy propagation opportunities. | |
1040 | |
1041 The algorithm propagates the value COPY-OF using ssa_propagate. For | |
1042 every variable X_i, COPY-OF(X_i) indicates which variable is X_i created | |
1043 from. The following example shows how the algorithm proceeds at a | |
1044 high level: | |
1045 | |
1046 1 a_24 = x_1 | |
1047 2 a_2 = PHI <a_24, x_1> | |
1048 3 a_5 = PHI <a_2> | |
1049 4 x_1 = PHI <x_298, a_5, a_2> | |
1050 | |
1051 The end result should be that a_2, a_5, a_24 and x_1 are a copy of | |
1052 x_298. Propagation proceeds as follows. | |
1053 | |
1054 Visit #1: a_24 is copy-of x_1. Value changed. | |
1055 Visit #2: a_2 is copy-of x_1. Value changed. | |
1056 Visit #3: a_5 is copy-of x_1. Value changed. | |
1057 Visit #4: x_1 is copy-of x_298. Value changed. | |
1058 Visit #1: a_24 is copy-of x_298. Value changed. | |
1059 Visit #2: a_2 is copy-of x_298. Value changed. | |
1060 Visit #3: a_5 is copy-of x_298. Value changed. | |
1061 Visit #4: x_1 is copy-of x_298. Stable state reached. | |
1062 | |
1063 When visiting PHI nodes, we only consider arguments that flow | |
1064 through edges marked executable by the propagation engine. So, | |
1065 when visiting statement #2 for the first time, we will only look at | |
1066 the first argument (a_24) and optimistically assume that its value | |
1067 is the copy of a_24 (x_1). | |
1068 | |
1069 The problem with this approach is that it may fail to discover copy | |
1070 relations in PHI cycles. Instead of propagating copy-of | |
1071 values, we actually propagate copy-of chains. For instance: | |
1072 | |
1073 A_3 = B_1; | |
1074 C_9 = A_3; | |
1075 D_4 = C_9; | |
1076 X_i = D_4; | |
1077 | |
1078 In this code fragment, COPY-OF (X_i) = { D_4, C_9, A_3, B_1 }. | |
1079 Obviously, we are only really interested in the last value of the | |
1080 chain, however the propagator needs to access the copy-of chain | |
1081 when visiting PHI nodes. | |
1082 | |
1083 To represent the copy-of chain, we use the array COPY_CHAINS, which | |
1084 holds the first link in the copy-of chain for every variable. | |
1085 If variable X_i is a copy of X_j, which in turn is a copy of X_k, | |
1086 the array will contain: | |
1087 | |
1088 COPY_CHAINS[i] = X_j | |
1089 COPY_CHAINS[j] = X_k | |
1090 COPY_CHAINS[k] = X_k | |
1091 | |
1092 Keeping copy-of chains instead of copy-of values directly becomes | |
1093 important when visiting PHI nodes. Suppose that we had the | |
1094 following PHI cycle, such that x_52 is already considered a copy of | |
1095 x_53: | |
1096 | |
1097 1 x_54 = PHI <x_53, x_52> | |
1098 2 x_53 = PHI <x_898, x_54> | |
1099 | |
1100 Visit #1: x_54 is copy-of x_53 (because x_52 is copy-of x_53) | |
1101 Visit #2: x_53 is copy-of x_898 (because x_54 is a copy of x_53, | |
1102 so it is considered irrelevant | |
1103 as a copy). | |
1104 Visit #1: x_54 is copy-of nothing (x_53 is a copy-of x_898 and | |
1105 x_52 is a copy of x_53, so | |
1106 they don't match) | |
1107 Visit #2: x_53 is copy-of nothing | |
1108 | |
1109 This problem is avoided by keeping a chain of copies, instead of | |
1110 the final copy-of value. Propagation will now only keep the first | |
1111 element of a variable's copy-of chain. When visiting PHI nodes, | |
1112 arguments are considered equal if their copy-of chains end in the | |
1113 same variable. So, as long as their copy-of chains overlap, we | |
1114 know that they will be a copy of the same variable, regardless of | |
1115 which variable that may be). | |
1116 | |
1117 Propagation would then proceed as follows (the notation a -> b | |
1118 means that a is a copy-of b): | |
1119 | |
1120 Visit #1: x_54 = PHI <x_53, x_52> | |
1121 x_53 -> x_53 | |
1122 x_52 -> x_53 | |
1123 Result: x_54 -> x_53. Value changed. Add SSA edges. | |
1124 | |
1125 Visit #1: x_53 = PHI <x_898, x_54> | |
1126 x_898 -> x_898 | |
1127 x_54 -> x_53 | |
1128 Result: x_53 -> x_898. Value changed. Add SSA edges. | |
1129 | |
1130 Visit #2: x_54 = PHI <x_53, x_52> | |
1131 x_53 -> x_898 | |
1132 x_52 -> x_53 -> x_898 | |
1133 Result: x_54 -> x_898. Value changed. Add SSA edges. | |
1134 | |
1135 Visit #2: x_53 = PHI <x_898, x_54> | |
1136 x_898 -> x_898 | |
1137 x_54 -> x_898 | |
1138 Result: x_53 -> x_898. Value didn't change. Stable state | |
1139 | |
1140 Once the propagator stabilizes, we end up with the desired result | |
1141 x_53 and x_54 are both copies of x_898. */ | |
1142 | |
1143 static unsigned int | |
1144 execute_copy_prop (void) | |
1145 { | |
1146 init_copy_prop (); | |
1147 ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node); | |
1148 fini_copy_prop (); | |
1149 return 0; | |
1150 } | |
1151 | |
1152 static bool | |
1153 gate_copy_prop (void) | |
1154 { | |
1155 return flag_tree_copy_prop != 0; | |
1156 } | |
1157 | |
1158 struct gimple_opt_pass pass_copy_prop = | |
1159 { | |
1160 { | |
1161 GIMPLE_PASS, | |
1162 "copyprop", /* name */ | |
1163 gate_copy_prop, /* gate */ | |
1164 execute_copy_prop, /* execute */ | |
1165 NULL, /* sub */ | |
1166 NULL, /* next */ | |
1167 0, /* static_pass_number */ | |
1168 TV_TREE_COPY_PROP, /* tv_id */ | |
1169 PROP_ssa | PROP_cfg, /* properties_required */ | |
1170 0, /* properties_provided */ | |
1171 0, /* properties_destroyed */ | |
1172 0, /* todo_flags_start */ | |
1173 TODO_cleanup_cfg | |
1174 | TODO_dump_func | |
1175 | TODO_ggc_collect | |
1176 | TODO_verify_ssa | |
1177 | TODO_update_ssa /* todo_flags_finish */ | |
1178 } | |
1179 }; |