* config.gcc (cygwin tm_file): Add cygwin-stdint.h.
[official-gcc.git] / gcc / tree-ssa-copy.c
blobf582ed0f99659c4f7fd34521684b7a767194c710
1 /* Copy propagation and SSA_NAME replacement support routines.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
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.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "tree.h"
25 #include "flags.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "ggc.h"
29 #include "basic-block.h"
30 #include "output.h"
31 #include "expr.h"
32 #include "function.h"
33 #include "diagnostic.h"
34 #include "timevar.h"
35 #include "tree-dump.h"
36 #include "tree-flow.h"
37 #include "tree-pass.h"
38 #include "tree-ssa-propagate.h"
39 #include "langhooks.h"
40 #include "cfgloop.h"
42 /* This file implements the copy propagation pass and provides a
43 handful of interfaces for performing const/copy propagation and
44 simple expression replacement which keep variable annotations
45 up-to-date.
47 We require that for any copy operation where the RHS and LHS have
48 a non-null memory tag the memory tag be the same. It is OK
49 for one or both of the memory tags to be NULL.
51 We also require tracking if a variable is dereferenced in a load or
52 store operation.
54 We enforce these requirements by having all copy propagation and
55 replacements of one SSA_NAME with a different SSA_NAME to use the
56 APIs defined in this file. */
58 /* Return true if we may propagate ORIG into DEST, false otherwise. */
60 bool
61 may_propagate_copy (tree dest, tree orig)
63 tree type_d = TREE_TYPE (dest);
64 tree type_o = TREE_TYPE (orig);
66 /* If ORIG flows in from an abnormal edge, it cannot be propagated. */
67 if (TREE_CODE (orig) == SSA_NAME
68 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
69 return false;
71 /* If DEST is an SSA_NAME that flows from an abnormal edge, then it
72 cannot be replaced. */
73 if (TREE_CODE (dest) == SSA_NAME
74 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest))
75 return false;
77 /* Do not copy between types for which we *do* need a conversion. */
78 if (!useless_type_conversion_p (type_d, type_o))
79 return false;
81 /* FIXME. GIMPLE is allowing pointer assignments and comparisons of
82 pointers that have different alias sets. This means that these
83 pointers will have different memory tags associated to them.
85 If we allow copy propagation in these cases, statements de-referencing
86 the new pointer will now have a reference to a different memory tag
87 with potentially incorrect SSA information.
89 This was showing up in libjava/java/util/zip/ZipFile.java with code
90 like:
92 struct java.io.BufferedInputStream *T.660;
93 struct java.io.BufferedInputStream *T.647;
94 struct java.io.InputStream *is;
95 struct java.io.InputStream *is.662;
96 [ ... ]
97 T.660 = T.647;
98 is = T.660; <-- This ought to be type-casted
99 is.662 = is;
101 Also, f/name.c exposed a similar problem with a COND_EXPR predicate
102 that was causing DOM to generate and equivalence with two pointers of
103 alias-incompatible types:
105 struct _ffename_space *n;
106 struct _ffename *ns;
107 [ ... ]
108 if (n == ns)
109 goto lab;
111 lab:
112 return n;
114 I think that GIMPLE should emit the appropriate type-casts. For the
115 time being, blocking copy-propagation in these cases is the safe thing
116 to do. */
117 if (TREE_CODE (dest) == SSA_NAME
118 && TREE_CODE (orig) == SSA_NAME
119 && POINTER_TYPE_P (type_d)
120 && POINTER_TYPE_P (type_o))
122 if (get_alias_set (TREE_TYPE (type_d))
123 != get_alias_set (TREE_TYPE (type_o)))
124 return false;
125 else if (DECL_NO_TBAA_P (SSA_NAME_VAR (dest))
126 != DECL_NO_TBAA_P (SSA_NAME_VAR (orig)))
127 return false;
130 /* Propagating virtual operands is always ok. */
131 if (TREE_CODE (dest) == SSA_NAME && !is_gimple_reg (dest))
133 /* But only between virtual operands. */
134 gcc_assert (TREE_CODE (orig) == SSA_NAME && !is_gimple_reg (orig));
136 return true;
139 /* Anything else is OK. */
140 return true;
143 /* Like may_propagate_copy, but use as the destination expression
144 the principal expression (typically, the RHS) contained in
145 statement DEST. This is more efficient when working with the
146 gimple tuples representation. */
148 bool
149 may_propagate_copy_into_stmt (gimple dest, tree orig)
151 tree type_d;
152 tree type_o;
154 /* If the statement is a switch or a single-rhs assignment,
155 then the expression to be replaced by the propagation may
156 be an SSA_NAME. Fortunately, there is an explicit tree
157 for the expression, so we delegate to may_propagate_copy. */
159 if (gimple_assign_single_p (dest))
160 return may_propagate_copy (gimple_assign_rhs1 (dest), orig);
161 else if (gimple_code (dest) == GIMPLE_SWITCH)
162 return may_propagate_copy (gimple_switch_index (dest), orig);
164 /* In other cases, the expression is not materialized, so there
165 is no destination to pass to may_propagate_copy. On the other
166 hand, the expression cannot be an SSA_NAME, so the analysis
167 is much simpler. */
169 if (TREE_CODE (orig) == SSA_NAME
170 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
171 return false;
173 if (is_gimple_assign (dest))
174 type_d = TREE_TYPE (gimple_assign_lhs (dest));
175 else if (gimple_code (dest) == GIMPLE_COND)
176 type_d = boolean_type_node;
177 else if (is_gimple_call (dest)
178 && gimple_call_lhs (dest) != NULL_TREE)
179 type_d = TREE_TYPE (gimple_call_lhs (dest));
180 else
181 gcc_unreachable ();
183 type_o = TREE_TYPE (orig);
185 if (!useless_type_conversion_p (type_d, type_o))
186 return false;
188 return true;
191 /* Similarly, but we know that we're propagating into an ASM_EXPR. */
193 bool
194 may_propagate_copy_into_asm (tree dest)
196 /* Hard register operands of asms are special. Do not bypass. */
197 return !(TREE_CODE (dest) == SSA_NAME
198 && TREE_CODE (SSA_NAME_VAR (dest)) == VAR_DECL
199 && DECL_HARD_REGISTER (SSA_NAME_VAR (dest)));
203 /* Given two SSA_NAMEs pointers ORIG and NEW such that we are copy
204 propagating NEW into ORIG, consolidate aliasing information so that
205 they both share the same memory tags. */
207 void
208 merge_alias_info (tree orig_name, tree new_name)
210 gcc_assert (POINTER_TYPE_P (TREE_TYPE (orig_name))
211 && POINTER_TYPE_P (TREE_TYPE (new_name)));
213 #if defined ENABLE_CHECKING
214 gcc_assert (useless_type_conversion_p (TREE_TYPE (orig_name),
215 TREE_TYPE (new_name)));
216 #endif
218 /* Check that flow-sensitive information is compatible. Notice that
219 we may not merge flow-sensitive information here. This function
220 is called when propagating equivalences dictated by the IL, like
221 a copy operation P_i = Q_j, and from equivalences dictated by
222 control-flow, like if (P_i == Q_j).
224 In the former case, P_i and Q_j are equivalent in every block
225 dominated by the assignment, so their flow-sensitive information
226 is always the same. However, in the latter case, the pointers
227 P_i and Q_j are only equivalent in one of the sub-graphs out of
228 the predicate, so their flow-sensitive information is not the
229 same in every block dominated by the predicate.
231 Since we cannot distinguish one case from another in this
232 function, we cannot merge flow-sensitive information by
233 intersecting. Instead the only thing we can do is to _not_
234 merge flow-sensitive information.
236 ??? At some point we should enhance this machinery to distinguish
237 both cases in the caller. */
241 /* Common code for propagate_value and replace_exp.
243 Replace use operand OP_P with VAL. FOR_PROPAGATION indicates if the
244 replacement is done to propagate a value or not. */
246 static void
247 replace_exp_1 (use_operand_p op_p, tree val,
248 bool for_propagation ATTRIBUTE_UNUSED)
250 tree op = USE_FROM_PTR (op_p);
252 #if defined ENABLE_CHECKING
253 gcc_assert (!(for_propagation
254 && TREE_CODE (op) == SSA_NAME
255 && TREE_CODE (val) == SSA_NAME
256 && !may_propagate_copy (op, val)));
257 #endif
259 if (TREE_CODE (val) == SSA_NAME)
261 if (TREE_CODE (op) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (op)))
262 merge_alias_info (op, val);
263 SET_USE (op_p, val);
265 else
266 SET_USE (op_p, unsave_expr_now (val));
270 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
271 into the operand pointed to by OP_P.
273 Use this version for const/copy propagation as it will perform additional
274 checks to ensure validity of the const/copy propagation. */
276 void
277 propagate_value (use_operand_p op_p, tree val)
279 replace_exp_1 (op_p, val, true);
282 /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
284 Use this version when not const/copy propagating values. For example,
285 PRE uses this version when building expressions as they would appear
286 in specific blocks taking into account actions of PHI nodes. */
288 void
289 replace_exp (use_operand_p op_p, tree val)
291 replace_exp_1 (op_p, val, false);
295 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
296 into the tree pointed to by OP_P.
298 Use this version for const/copy propagation when SSA operands are not
299 available. It will perform the additional checks to ensure validity of
300 the const/copy propagation, but will not update any operand information.
301 Be sure to mark the stmt as modified. */
303 void
304 propagate_tree_value (tree *op_p, tree val)
306 #if defined ENABLE_CHECKING
307 gcc_assert (!(TREE_CODE (val) == SSA_NAME
308 && *op_p
309 && TREE_CODE (*op_p) == SSA_NAME
310 && !may_propagate_copy (*op_p, val)));
311 #endif
313 if (TREE_CODE (val) == SSA_NAME)
315 if (*op_p && TREE_CODE (*op_p) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (*op_p)))
316 merge_alias_info (*op_p, val);
317 *op_p = val;
319 else
320 *op_p = unsave_expr_now (val);
324 /* Like propagate_tree_value, but use as the operand to replace
325 the principal expression (typically, the RHS) contained in the
326 statement referenced by iterator GSI. Note that it is not
327 always possible to update the statement in-place, so a new
328 statement may be created to replace the original. */
330 void
331 propagate_tree_value_into_stmt (gimple_stmt_iterator *gsi, tree val)
333 gimple stmt = gsi_stmt (*gsi);
335 if (is_gimple_assign (stmt))
337 tree expr = NULL_TREE;
338 if (gimple_assign_single_p (stmt))
339 expr = gimple_assign_rhs1 (stmt);
340 propagate_tree_value (&expr, val);
341 gimple_assign_set_rhs_from_tree (gsi, expr);
342 stmt = gsi_stmt (*gsi);
344 else if (gimple_code (stmt) == GIMPLE_COND)
346 tree lhs = NULL_TREE;
347 tree rhs = fold_convert (TREE_TYPE (val), integer_zero_node);
348 propagate_tree_value (&lhs, val);
349 gimple_cond_set_code (stmt, NE_EXPR);
350 gimple_cond_set_lhs (stmt, lhs);
351 gimple_cond_set_rhs (stmt, rhs);
353 else if (is_gimple_call (stmt)
354 && gimple_call_lhs (stmt) != NULL_TREE)
356 gimple new_stmt;
358 tree expr = NULL_TREE;
359 propagate_tree_value (&expr, val);
360 new_stmt = gimple_build_assign (gimple_call_lhs (stmt), expr);
361 move_ssa_defining_stmt_for_defs (new_stmt, stmt);
362 gsi_replace (gsi, new_stmt, false);
364 else if (gimple_code (stmt) == GIMPLE_SWITCH)
365 propagate_tree_value (gimple_switch_index_ptr (stmt), val);
366 else
367 gcc_unreachable ();
370 /*---------------------------------------------------------------------------
371 Copy propagation
372 ---------------------------------------------------------------------------*/
373 /* During propagation, we keep chains of variables that are copies of
374 one another. If variable X_i is a copy of X_j and X_j is a copy of
375 X_k, COPY_OF will contain:
377 COPY_OF[i].VALUE = X_j
378 COPY_OF[j].VALUE = X_k
379 COPY_OF[k].VALUE = X_k
381 After propagation, the copy-of value for each variable X_i is
382 converted into the final value by walking the copy-of chains and
383 updating COPY_OF[i].VALUE to be the last element of the chain. */
384 static prop_value_t *copy_of;
386 /* Used in set_copy_of_val to determine if the last link of a copy-of
387 chain has changed. */
388 static tree *cached_last_copy_of;
391 /* Return true if this statement may generate a useful copy. */
393 static bool
394 stmt_may_generate_copy (gimple stmt)
396 if (gimple_code (stmt) == GIMPLE_PHI)
397 return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt));
399 if (gimple_code (stmt) != GIMPLE_ASSIGN)
400 return false;
402 /* If the statement has volatile operands, it won't generate a
403 useful copy. */
404 if (gimple_has_volatile_ops (stmt))
405 return false;
407 /* Statements with loads and/or stores will never generate a useful copy. */
408 if (gimple_vuse (stmt))
409 return false;
411 /* Otherwise, the only statements that generate useful copies are
412 assignments whose RHS is just an SSA name that doesn't flow
413 through abnormal edges. */
414 return (gimple_assign_rhs_code (stmt) == SSA_NAME
415 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)));
419 /* Return the copy-of value for VAR. */
421 static inline prop_value_t *
422 get_copy_of_val (tree var)
424 prop_value_t *val = &copy_of[SSA_NAME_VERSION (var)];
426 if (val->value == NULL_TREE
427 && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var)))
429 /* If the variable will never generate a useful copy relation,
430 make it its own copy. */
431 val->value = var;
434 return val;
438 /* Return last link in the copy-of chain for VAR. */
440 static tree
441 get_last_copy_of (tree var)
443 tree last;
444 int i;
446 /* Traverse COPY_OF starting at VAR until we get to the last
447 link in the chain. Since it is possible to have cycles in PHI
448 nodes, the copy-of chain may also contain cycles.
450 To avoid infinite loops and to avoid traversing lengthy copy-of
451 chains, we artificially limit the maximum number of chains we are
452 willing to traverse.
454 The value 5 was taken from a compiler and runtime library
455 bootstrap and a mixture of C and C++ code from various sources.
456 More than 82% of all copy-of chains were shorter than 5 links. */
457 #define LIMIT 5
459 last = var;
460 for (i = 0; i < LIMIT; i++)
462 tree copy = copy_of[SSA_NAME_VERSION (last)].value;
463 if (copy == NULL_TREE || copy == last)
464 break;
465 last = copy;
468 /* If we have reached the limit, then we are either in a copy-of
469 cycle or the copy-of chain is too long. In this case, just
470 return VAR so that it is not considered a copy of anything. */
471 return (i < LIMIT ? last : var);
475 /* Set FIRST to be the first variable in the copy-of chain for DEST.
476 If DEST's copy-of value or its copy-of chain has changed, return
477 true.
479 MEM_REF is the memory reference where FIRST is stored. This is
480 used when DEST is a non-register and we are copy propagating loads
481 and stores. */
483 static inline bool
484 set_copy_of_val (tree dest, tree first)
486 unsigned int dest_ver = SSA_NAME_VERSION (dest);
487 tree old_first, old_last, new_last;
489 /* Set FIRST to be the first link in COPY_OF[DEST]. If that
490 changed, return true. */
491 old_first = copy_of[dest_ver].value;
492 copy_of[dest_ver].value = first;
494 if (old_first != first)
495 return true;
497 /* If FIRST and OLD_FIRST are the same, we need to check whether the
498 copy-of chain starting at FIRST ends in a different variable. If
499 the copy-of chain starting at FIRST ends up in a different
500 variable than the last cached value we had for DEST, then return
501 true because DEST is now a copy of a different variable.
503 This test is necessary because even though the first link in the
504 copy-of chain may not have changed, if any of the variables in
505 the copy-of chain changed its final value, DEST will now be the
506 copy of a different variable, so we have to do another round of
507 propagation for everything that depends on DEST. */
508 old_last = cached_last_copy_of[dest_ver];
509 new_last = get_last_copy_of (dest);
510 cached_last_copy_of[dest_ver] = new_last;
512 return (old_last != new_last);
516 /* Dump the copy-of value for variable VAR to FILE. */
518 static void
519 dump_copy_of (FILE *file, tree var)
521 tree val;
522 sbitmap visited;
524 print_generic_expr (file, var, dump_flags);
526 if (TREE_CODE (var) != SSA_NAME)
527 return;
529 visited = sbitmap_alloc (num_ssa_names);
530 sbitmap_zero (visited);
531 SET_BIT (visited, SSA_NAME_VERSION (var));
533 fprintf (file, " copy-of chain: ");
535 val = var;
536 print_generic_expr (file, val, 0);
537 fprintf (file, " ");
538 while (copy_of[SSA_NAME_VERSION (val)].value)
540 fprintf (file, "-> ");
541 val = copy_of[SSA_NAME_VERSION (val)].value;
542 print_generic_expr (file, val, 0);
543 fprintf (file, " ");
544 if (TEST_BIT (visited, SSA_NAME_VERSION (val)))
545 break;
546 SET_BIT (visited, SSA_NAME_VERSION (val));
549 val = get_copy_of_val (var)->value;
550 if (val == NULL_TREE)
551 fprintf (file, "[UNDEFINED]");
552 else if (val != var)
553 fprintf (file, "[COPY]");
554 else
555 fprintf (file, "[NOT A COPY]");
557 sbitmap_free (visited);
561 /* Evaluate the RHS of STMT. If it produces a valid copy, set the LHS
562 value and store the LHS into *RESULT_P. If STMT generates more
563 than one name (i.e., STMT is an aliased store), it is enough to
564 store the first name in the VDEF list into *RESULT_P. After
565 all, the names generated will be VUSEd in the same statements. */
567 static enum ssa_prop_result
568 copy_prop_visit_assignment (gimple stmt, tree *result_p)
570 tree lhs, rhs;
571 prop_value_t *rhs_val;
573 lhs = gimple_assign_lhs (stmt);
574 rhs = gimple_assign_rhs1 (stmt);
577 gcc_assert (gimple_assign_rhs_code (stmt) == SSA_NAME);
579 rhs_val = get_copy_of_val (rhs);
581 if (TREE_CODE (lhs) == SSA_NAME)
583 /* Straight copy between two SSA names. First, make sure that
584 we can propagate the RHS into uses of LHS. */
585 if (!may_propagate_copy (lhs, rhs))
586 return SSA_PROP_VARYING;
588 /* Notice that in the case of assignments, we make the LHS be a
589 copy of RHS's value, not of RHS itself. This avoids keeping
590 unnecessary copy-of chains (assignments cannot be in a cycle
591 like PHI nodes), speeding up the propagation process.
592 This is different from what we do in copy_prop_visit_phi_node.
593 In those cases, we are interested in the copy-of chains. */
594 *result_p = lhs;
595 if (set_copy_of_val (*result_p, rhs_val->value))
596 return SSA_PROP_INTERESTING;
597 else
598 return SSA_PROP_NOT_INTERESTING;
601 return SSA_PROP_VARYING;
605 /* Visit the GIMPLE_COND STMT. Return SSA_PROP_INTERESTING
606 if it can determine which edge will be taken. Otherwise, return
607 SSA_PROP_VARYING. */
609 static enum ssa_prop_result
610 copy_prop_visit_cond_stmt (gimple stmt, edge *taken_edge_p)
612 enum ssa_prop_result retval = SSA_PROP_VARYING;
614 tree op0 = gimple_cond_lhs (stmt);
615 tree op1 = gimple_cond_rhs (stmt);
617 /* The only conditionals that we may be able to compute statically
618 are predicates involving two SSA_NAMEs. */
619 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
621 op0 = get_last_copy_of (op0);
622 op1 = get_last_copy_of (op1);
624 /* See if we can determine the predicate's value. */
625 if (dump_file && (dump_flags & TDF_DETAILS))
627 fprintf (dump_file, "Trying to determine truth value of ");
628 fprintf (dump_file, "predicate ");
629 print_gimple_stmt (dump_file, stmt, 0, 0);
632 /* We can fold COND and get a useful result only when we have
633 the same SSA_NAME on both sides of a comparison operator. */
634 if (op0 == op1)
636 tree folded_cond = fold_binary (gimple_cond_code (stmt),
637 boolean_type_node, op0, op1);
638 if (folded_cond)
640 basic_block bb = gimple_bb (stmt);
641 *taken_edge_p = find_taken_edge (bb, folded_cond);
642 if (*taken_edge_p)
643 retval = SSA_PROP_INTERESTING;
648 if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p)
649 fprintf (dump_file, "\nConditional will always take edge %d->%d\n",
650 (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index);
652 return retval;
656 /* Evaluate statement STMT. If the statement produces a new output
657 value, return SSA_PROP_INTERESTING and store the SSA_NAME holding
658 the new value in *RESULT_P.
660 If STMT is a conditional branch and we can determine its truth
661 value, set *TAKEN_EDGE_P accordingly.
663 If the new value produced by STMT is varying, return
664 SSA_PROP_VARYING. */
666 static enum ssa_prop_result
667 copy_prop_visit_stmt (gimple stmt, edge *taken_edge_p, tree *result_p)
669 enum ssa_prop_result retval;
671 if (dump_file && (dump_flags & TDF_DETAILS))
673 fprintf (dump_file, "\nVisiting statement:\n");
674 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
675 fprintf (dump_file, "\n");
678 if (gimple_assign_single_p (stmt)
679 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
680 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
682 /* If the statement is a copy assignment, evaluate its RHS to
683 see if the lattice value of its output has changed. */
684 retval = copy_prop_visit_assignment (stmt, result_p);
686 else if (gimple_code (stmt) == GIMPLE_COND)
688 /* See if we can determine which edge goes out of a conditional
689 jump. */
690 retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p);
692 else
693 retval = SSA_PROP_VARYING;
695 if (retval == SSA_PROP_VARYING)
697 tree def;
698 ssa_op_iter i;
700 /* Any other kind of statement is not interesting for constant
701 propagation and, therefore, not worth simulating. */
702 if (dump_file && (dump_flags & TDF_DETAILS))
703 fprintf (dump_file, "No interesting values produced.\n");
705 /* The assignment is not a copy operation. Don't visit this
706 statement again and mark all the definitions in the statement
707 to be copies of nothing. */
708 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS)
709 set_copy_of_val (def, def);
712 return retval;
716 /* Visit PHI node PHI. If all the arguments produce the same value,
717 set it to be the value of the LHS of PHI. */
719 static enum ssa_prop_result
720 copy_prop_visit_phi_node (gimple phi)
722 enum ssa_prop_result retval;
723 unsigned i;
724 prop_value_t phi_val = { 0, NULL_TREE };
726 tree lhs = gimple_phi_result (phi);
728 if (dump_file && (dump_flags & TDF_DETAILS))
730 fprintf (dump_file, "\nVisiting PHI node: ");
731 print_gimple_stmt (dump_file, phi, 0, dump_flags);
732 fprintf (dump_file, "\n\n");
735 for (i = 0; i < gimple_phi_num_args (phi); i++)
737 prop_value_t *arg_val;
738 tree arg = gimple_phi_arg_def (phi, i);
739 edge e = gimple_phi_arg_edge (phi, i);
741 /* We don't care about values flowing through non-executable
742 edges. */
743 if (!(e->flags & EDGE_EXECUTABLE))
744 continue;
746 /* Constants in the argument list never generate a useful copy.
747 Similarly, names that flow through abnormal edges cannot be
748 used to derive copies. */
749 if (TREE_CODE (arg) != SSA_NAME || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
751 phi_val.value = lhs;
752 break;
755 /* Avoid copy propagation from an inner into an outer loop.
756 Otherwise, this may move loop variant variables outside of
757 their loops and prevent coalescing opportunities. If the
758 value was loop invariant, it will be hoisted by LICM and
759 exposed for copy propagation. Not a problem for virtual
760 operands though. */
761 if (is_gimple_reg (lhs)
762 && loop_depth_of_name (arg) > loop_depth_of_name (lhs))
764 phi_val.value = lhs;
765 break;
768 /* If the LHS appears in the argument list, ignore it. It is
769 irrelevant as a copy. */
770 if (arg == lhs || get_last_copy_of (arg) == lhs)
771 continue;
773 if (dump_file && (dump_flags & TDF_DETAILS))
775 fprintf (dump_file, "\tArgument #%d: ", i);
776 dump_copy_of (dump_file, arg);
777 fprintf (dump_file, "\n");
780 arg_val = get_copy_of_val (arg);
782 /* If the LHS didn't have a value yet, make it a copy of the
783 first argument we find. Notice that while we make the LHS be
784 a copy of the argument itself, we take the memory reference
785 from the argument's value so that we can compare it to the
786 memory reference of all the other arguments. */
787 if (phi_val.value == NULL_TREE)
789 phi_val.value = arg_val->value ? arg_val->value : arg;
790 continue;
793 /* If PHI_VAL and ARG don't have a common copy-of chain, then
794 this PHI node cannot be a copy operation. Also, if we are
795 copy propagating stores and these two arguments came from
796 different memory references, they cannot be considered
797 copies. */
798 if (get_last_copy_of (phi_val.value) != get_last_copy_of (arg))
800 phi_val.value = lhs;
801 break;
805 if (phi_val.value && may_propagate_copy (lhs, phi_val.value)
806 && set_copy_of_val (lhs, phi_val.value))
807 retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
808 else
809 retval = SSA_PROP_NOT_INTERESTING;
811 if (dump_file && (dump_flags & TDF_DETAILS))
813 fprintf (dump_file, "\nPHI node ");
814 dump_copy_of (dump_file, lhs);
815 fprintf (dump_file, "\nTelling the propagator to ");
816 if (retval == SSA_PROP_INTERESTING)
817 fprintf (dump_file, "add SSA edges out of this PHI and continue.");
818 else if (retval == SSA_PROP_VARYING)
819 fprintf (dump_file, "add SSA edges out of this PHI and never visit again.");
820 else
821 fprintf (dump_file, "do nothing with SSA edges and keep iterating.");
822 fprintf (dump_file, "\n\n");
825 return retval;
829 /* Initialize structures used for copy propagation. PHIS_ONLY is true
830 if we should only consider PHI nodes as generating copy propagation
831 opportunities. */
833 static void
834 init_copy_prop (void)
836 basic_block bb;
838 copy_of = XCNEWVEC (prop_value_t, num_ssa_names);
840 cached_last_copy_of = XCNEWVEC (tree, num_ssa_names);
842 FOR_EACH_BB (bb)
844 gimple_stmt_iterator si;
845 int depth = bb->loop_depth;
847 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
849 gimple stmt = gsi_stmt (si);
850 ssa_op_iter iter;
851 tree def;
853 /* The only statements that we care about are those that may
854 generate useful copies. We also need to mark conditional
855 jumps so that their outgoing edges are added to the work
856 lists of the propagator.
858 Avoid copy propagation from an inner into an outer loop.
859 Otherwise, this may move loop variant variables outside of
860 their loops and prevent coalescing opportunities. If the
861 value was loop invariant, it will be hoisted by LICM and
862 exposed for copy propagation. */
863 if (stmt_ends_bb_p (stmt))
864 prop_set_simulate_again (stmt, true);
865 else if (stmt_may_generate_copy (stmt)
866 /* Since we are iterating over the statements in
867 BB, not the phi nodes, STMT will always be an
868 assignment. */
869 && loop_depth_of_name (gimple_assign_rhs1 (stmt)) <= depth)
870 prop_set_simulate_again (stmt, true);
871 else
872 prop_set_simulate_again (stmt, false);
874 /* Mark all the outputs of this statement as not being
875 the copy of anything. */
876 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
877 if (!prop_simulate_again_p (stmt))
878 set_copy_of_val (def, def);
879 else
880 cached_last_copy_of[SSA_NAME_VERSION (def)] = def;
883 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
885 gimple phi = gsi_stmt (si);
886 tree def;
888 def = gimple_phi_result (phi);
889 if (!is_gimple_reg (def)
890 /* In loop-closed SSA form do not copy-propagate through
891 PHI nodes. Technically this is only needed for loop
892 exit PHIs, but this is difficult to query. */
893 || (current_loops
894 && gimple_phi_num_args (phi) == 1
895 && loops_state_satisfies_p (LOOP_CLOSED_SSA)))
896 prop_set_simulate_again (phi, false);
897 else
898 prop_set_simulate_again (phi, true);
900 if (!prop_simulate_again_p (phi))
901 set_copy_of_val (def, def);
902 else
903 cached_last_copy_of[SSA_NAME_VERSION (def)] = def;
909 /* Deallocate memory used in copy propagation and do final
910 substitution. */
912 static void
913 fini_copy_prop (void)
915 size_t i;
916 prop_value_t *tmp;
918 /* Set the final copy-of value for each variable by traversing the
919 copy-of chains. */
920 tmp = XCNEWVEC (prop_value_t, num_ssa_names);
921 for (i = 1; i < num_ssa_names; i++)
923 tree var = ssa_name (i);
924 if (var && copy_of[i].value && copy_of[i].value != var)
925 tmp[i].value = get_last_copy_of (var);
928 substitute_and_fold (tmp, false);
930 free (cached_last_copy_of);
931 free (copy_of);
932 free (tmp);
936 /* Main entry point to the copy propagator.
938 PHIS_ONLY is true if we should only consider PHI nodes as generating
939 copy propagation opportunities.
941 The algorithm propagates the value COPY-OF using ssa_propagate. For
942 every variable X_i, COPY-OF(X_i) indicates which variable is X_i created
943 from. The following example shows how the algorithm proceeds at a
944 high level:
946 1 a_24 = x_1
947 2 a_2 = PHI <a_24, x_1>
948 3 a_5 = PHI <a_2>
949 4 x_1 = PHI <x_298, a_5, a_2>
951 The end result should be that a_2, a_5, a_24 and x_1 are a copy of
952 x_298. Propagation proceeds as follows.
954 Visit #1: a_24 is copy-of x_1. Value changed.
955 Visit #2: a_2 is copy-of x_1. Value changed.
956 Visit #3: a_5 is copy-of x_1. Value changed.
957 Visit #4: x_1 is copy-of x_298. Value changed.
958 Visit #1: a_24 is copy-of x_298. Value changed.
959 Visit #2: a_2 is copy-of x_298. Value changed.
960 Visit #3: a_5 is copy-of x_298. Value changed.
961 Visit #4: x_1 is copy-of x_298. Stable state reached.
963 When visiting PHI nodes, we only consider arguments that flow
964 through edges marked executable by the propagation engine. So,
965 when visiting statement #2 for the first time, we will only look at
966 the first argument (a_24) and optimistically assume that its value
967 is the copy of a_24 (x_1).
969 The problem with this approach is that it may fail to discover copy
970 relations in PHI cycles. Instead of propagating copy-of
971 values, we actually propagate copy-of chains. For instance:
973 A_3 = B_1;
974 C_9 = A_3;
975 D_4 = C_9;
976 X_i = D_4;
978 In this code fragment, COPY-OF (X_i) = { D_4, C_9, A_3, B_1 }.
979 Obviously, we are only really interested in the last value of the
980 chain, however the propagator needs to access the copy-of chain
981 when visiting PHI nodes.
983 To represent the copy-of chain, we use the array COPY_CHAINS, which
984 holds the first link in the copy-of chain for every variable.
985 If variable X_i is a copy of X_j, which in turn is a copy of X_k,
986 the array will contain:
988 COPY_CHAINS[i] = X_j
989 COPY_CHAINS[j] = X_k
990 COPY_CHAINS[k] = X_k
992 Keeping copy-of chains instead of copy-of values directly becomes
993 important when visiting PHI nodes. Suppose that we had the
994 following PHI cycle, such that x_52 is already considered a copy of
995 x_53:
997 1 x_54 = PHI <x_53, x_52>
998 2 x_53 = PHI <x_898, x_54>
1000 Visit #1: x_54 is copy-of x_53 (because x_52 is copy-of x_53)
1001 Visit #2: x_53 is copy-of x_898 (because x_54 is a copy of x_53,
1002 so it is considered irrelevant
1003 as a copy).
1004 Visit #1: x_54 is copy-of nothing (x_53 is a copy-of x_898 and
1005 x_52 is a copy of x_53, so
1006 they don't match)
1007 Visit #2: x_53 is copy-of nothing
1009 This problem is avoided by keeping a chain of copies, instead of
1010 the final copy-of value. Propagation will now only keep the first
1011 element of a variable's copy-of chain. When visiting PHI nodes,
1012 arguments are considered equal if their copy-of chains end in the
1013 same variable. So, as long as their copy-of chains overlap, we
1014 know that they will be a copy of the same variable, regardless of
1015 which variable that may be).
1017 Propagation would then proceed as follows (the notation a -> b
1018 means that a is a copy-of b):
1020 Visit #1: x_54 = PHI <x_53, x_52>
1021 x_53 -> x_53
1022 x_52 -> x_53
1023 Result: x_54 -> x_53. Value changed. Add SSA edges.
1025 Visit #1: x_53 = PHI <x_898, x_54>
1026 x_898 -> x_898
1027 x_54 -> x_53
1028 Result: x_53 -> x_898. Value changed. Add SSA edges.
1030 Visit #2: x_54 = PHI <x_53, x_52>
1031 x_53 -> x_898
1032 x_52 -> x_53 -> x_898
1033 Result: x_54 -> x_898. Value changed. Add SSA edges.
1035 Visit #2: x_53 = PHI <x_898, x_54>
1036 x_898 -> x_898
1037 x_54 -> x_898
1038 Result: x_53 -> x_898. Value didn't change. Stable state
1040 Once the propagator stabilizes, we end up with the desired result
1041 x_53 and x_54 are both copies of x_898. */
1043 static unsigned int
1044 execute_copy_prop (void)
1046 init_copy_prop ();
1047 ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node);
1048 fini_copy_prop ();
1049 return 0;
1052 static bool
1053 gate_copy_prop (void)
1055 return flag_tree_copy_prop != 0;
1058 struct gimple_opt_pass pass_copy_prop =
1061 GIMPLE_PASS,
1062 "copyprop", /* name */
1063 gate_copy_prop, /* gate */
1064 execute_copy_prop, /* execute */
1065 NULL, /* sub */
1066 NULL, /* next */
1067 0, /* static_pass_number */
1068 TV_TREE_COPY_PROP, /* tv_id */
1069 PROP_ssa | PROP_cfg, /* properties_required */
1070 0, /* properties_provided */
1071 0, /* properties_destroyed */
1072 0, /* todo_flags_start */
1073 TODO_cleanup_cfg
1074 | TODO_dump_func
1075 | TODO_ggc_collect
1076 | TODO_verify_ssa
1077 | TODO_update_ssa /* todo_flags_finish */