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