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