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