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)
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/>. */
22 #include "coretypes.h"
29 #include "basic-block.h"
33 #include "diagnostic.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"
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
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
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. */
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))
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))
77 /* Do not copy between types for which we *do* need a conversion. */
78 if (!useless_type_conversion_p (type_d, type_o))
81 /* Propagating virtual operands is always ok. */
82 if (TREE_CODE (dest) == SSA_NAME && !is_gimple_reg (dest))
84 /* But only between virtual operands. */
85 gcc_assert (TREE_CODE (orig) == SSA_NAME && !is_gimple_reg (orig));
90 /* Anything else is OK. */
94 /* Like may_propagate_copy, but use as the destination expression
95 the principal expression (typically, the RHS) contained in
96 statement DEST. This is more efficient when working with the
97 gimple tuples representation. */
100 may_propagate_copy_into_stmt (gimple dest, tree orig)
105 /* If the statement is a switch or a single-rhs assignment,
106 then the expression to be replaced by the propagation may
107 be an SSA_NAME. Fortunately, there is an explicit tree
108 for the expression, so we delegate to may_propagate_copy. */
110 if (gimple_assign_single_p (dest))
111 return may_propagate_copy (gimple_assign_rhs1 (dest), orig);
112 else if (gimple_code (dest) == GIMPLE_SWITCH)
113 return may_propagate_copy (gimple_switch_index (dest), orig);
115 /* In other cases, the expression is not materialized, so there
116 is no destination to pass to may_propagate_copy. On the other
117 hand, the expression cannot be an SSA_NAME, so the analysis
120 if (TREE_CODE (orig) == SSA_NAME
121 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
124 if (is_gimple_assign (dest))
125 type_d = TREE_TYPE (gimple_assign_lhs (dest));
126 else if (gimple_code (dest) == GIMPLE_COND)
127 type_d = boolean_type_node;
128 else if (is_gimple_call (dest)
129 && gimple_call_lhs (dest) != NULL_TREE)
130 type_d = TREE_TYPE (gimple_call_lhs (dest));
134 type_o = TREE_TYPE (orig);
136 if (!useless_type_conversion_p (type_d, type_o))
142 /* Similarly, but we know that we're propagating into an ASM_EXPR. */
145 may_propagate_copy_into_asm (tree dest)
147 /* Hard register operands of asms are special. Do not bypass. */
148 return !(TREE_CODE (dest) == SSA_NAME
149 && TREE_CODE (SSA_NAME_VAR (dest)) == VAR_DECL
150 && DECL_HARD_REGISTER (SSA_NAME_VAR (dest)));
154 /* Common code for propagate_value and replace_exp.
156 Replace use operand OP_P with VAL. FOR_PROPAGATION indicates if the
157 replacement is done to propagate a value or not. */
160 replace_exp_1 (use_operand_p op_p, tree val,
161 bool for_propagation ATTRIBUTE_UNUSED)
163 tree op = USE_FROM_PTR (op_p);
165 #if defined ENABLE_CHECKING
166 gcc_assert (!(for_propagation
167 && TREE_CODE (op) == SSA_NAME
168 && TREE_CODE (val) == SSA_NAME
169 && !may_propagate_copy (op, val)));
172 if (TREE_CODE (val) == SSA_NAME)
175 SET_USE (op_p, unsave_expr_now (val));
179 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
180 into the operand pointed to by OP_P.
182 Use this version for const/copy propagation as it will perform additional
183 checks to ensure validity of the const/copy propagation. */
186 propagate_value (use_operand_p op_p, tree val)
188 replace_exp_1 (op_p, val, true);
191 /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
193 Use this version when not const/copy propagating values. For example,
194 PRE uses this version when building expressions as they would appear
195 in specific blocks taking into account actions of PHI nodes. */
198 replace_exp (use_operand_p op_p, tree val)
200 replace_exp_1 (op_p, val, false);
204 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
205 into the tree pointed to by OP_P.
207 Use this version for const/copy propagation when SSA operands are not
208 available. It will perform the additional checks to ensure validity of
209 the const/copy propagation, but will not update any operand information.
210 Be sure to mark the stmt as modified. */
213 propagate_tree_value (tree *op_p, tree val)
215 #if defined ENABLE_CHECKING
216 gcc_assert (!(TREE_CODE (val) == SSA_NAME
218 && TREE_CODE (*op_p) == SSA_NAME
219 && !may_propagate_copy (*op_p, val)));
222 if (TREE_CODE (val) == SSA_NAME)
225 *op_p = unsave_expr_now (val);
229 /* Like propagate_tree_value, but use as the operand to replace
230 the principal expression (typically, the RHS) contained in the
231 statement referenced by iterator GSI. Note that it is not
232 always possible to update the statement in-place, so a new
233 statement may be created to replace the original. */
236 propagate_tree_value_into_stmt (gimple_stmt_iterator *gsi, tree val)
238 gimple stmt = gsi_stmt (*gsi);
240 if (is_gimple_assign (stmt))
242 tree expr = NULL_TREE;
243 if (gimple_assign_single_p (stmt))
244 expr = gimple_assign_rhs1 (stmt);
245 propagate_tree_value (&expr, val);
246 gimple_assign_set_rhs_from_tree (gsi, expr);
247 stmt = gsi_stmt (*gsi);
249 else if (gimple_code (stmt) == GIMPLE_COND)
251 tree lhs = NULL_TREE;
252 tree rhs = fold_convert (TREE_TYPE (val), integer_zero_node);
253 propagate_tree_value (&lhs, val);
254 gimple_cond_set_code (stmt, NE_EXPR);
255 gimple_cond_set_lhs (stmt, lhs);
256 gimple_cond_set_rhs (stmt, rhs);
258 else if (is_gimple_call (stmt)
259 && gimple_call_lhs (stmt) != NULL_TREE)
263 tree expr = NULL_TREE;
264 propagate_tree_value (&expr, val);
265 new_stmt = gimple_build_assign (gimple_call_lhs (stmt), expr);
266 move_ssa_defining_stmt_for_defs (new_stmt, stmt);
267 gsi_replace (gsi, new_stmt, false);
269 else if (gimple_code (stmt) == GIMPLE_SWITCH)
270 propagate_tree_value (gimple_switch_index_ptr (stmt), val);
275 /*---------------------------------------------------------------------------
277 ---------------------------------------------------------------------------*/
278 /* During propagation, we keep chains of variables that are copies of
279 one another. If variable X_i is a copy of X_j and X_j is a copy of
280 X_k, COPY_OF will contain:
282 COPY_OF[i].VALUE = X_j
283 COPY_OF[j].VALUE = X_k
284 COPY_OF[k].VALUE = X_k
286 After propagation, the copy-of value for each variable X_i is
287 converted into the final value by walking the copy-of chains and
288 updating COPY_OF[i].VALUE to be the last element of the chain. */
289 static prop_value_t *copy_of;
291 /* Used in set_copy_of_val to determine if the last link of a copy-of
292 chain has changed. */
293 static tree *cached_last_copy_of;
296 /* Return true if this statement may generate a useful copy. */
299 stmt_may_generate_copy (gimple stmt)
301 if (gimple_code (stmt) == GIMPLE_PHI)
302 return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt));
304 if (gimple_code (stmt) != GIMPLE_ASSIGN)
307 /* If the statement has volatile operands, it won't generate a
309 if (gimple_has_volatile_ops (stmt))
312 /* Statements with loads and/or stores will never generate a useful copy. */
313 if (gimple_vuse (stmt))
316 /* Otherwise, the only statements that generate useful copies are
317 assignments whose RHS is just an SSA name that doesn't flow
318 through abnormal edges. */
319 return (gimple_assign_rhs_code (stmt) == SSA_NAME
320 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)));
324 /* Return the copy-of value for VAR. */
326 static inline prop_value_t *
327 get_copy_of_val (tree var)
329 prop_value_t *val = ©_of[SSA_NAME_VERSION (var)];
331 if (val->value == NULL_TREE
332 && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var)))
334 /* If the variable will never generate a useful copy relation,
335 make it its own copy. */
343 /* Return last link in the copy-of chain for VAR. */
346 get_last_copy_of (tree var)
351 /* Traverse COPY_OF starting at VAR until we get to the last
352 link in the chain. Since it is possible to have cycles in PHI
353 nodes, the copy-of chain may also contain cycles.
355 To avoid infinite loops and to avoid traversing lengthy copy-of
356 chains, we artificially limit the maximum number of chains we are
359 The value 5 was taken from a compiler and runtime library
360 bootstrap and a mixture of C and C++ code from various sources.
361 More than 82% of all copy-of chains were shorter than 5 links. */
365 for (i = 0; i < LIMIT; i++)
367 tree copy = copy_of[SSA_NAME_VERSION (last)].value;
368 if (copy == NULL_TREE || copy == last)
373 /* If we have reached the limit, then we are either in a copy-of
374 cycle or the copy-of chain is too long. In this case, just
375 return VAR so that it is not considered a copy of anything. */
376 return (i < LIMIT ? last : var);
380 /* Set FIRST to be the first variable in the copy-of chain for DEST.
381 If DEST's copy-of value or its copy-of chain has changed, return
384 MEM_REF is the memory reference where FIRST is stored. This is
385 used when DEST is a non-register and we are copy propagating loads
389 set_copy_of_val (tree dest, tree first)
391 unsigned int dest_ver = SSA_NAME_VERSION (dest);
392 tree old_first, old_last, new_last;
394 /* Set FIRST to be the first link in COPY_OF[DEST]. If that
395 changed, return true. */
396 old_first = copy_of[dest_ver].value;
397 copy_of[dest_ver].value = first;
399 if (old_first != first)
402 /* If FIRST and OLD_FIRST are the same, we need to check whether the
403 copy-of chain starting at FIRST ends in a different variable. If
404 the copy-of chain starting at FIRST ends up in a different
405 variable than the last cached value we had for DEST, then return
406 true because DEST is now a copy of a different variable.
408 This test is necessary because even though the first link in the
409 copy-of chain may not have changed, if any of the variables in
410 the copy-of chain changed its final value, DEST will now be the
411 copy of a different variable, so we have to do another round of
412 propagation for everything that depends on DEST. */
413 old_last = cached_last_copy_of[dest_ver];
414 new_last = get_last_copy_of (dest);
415 cached_last_copy_of[dest_ver] = new_last;
417 return (old_last != new_last);
421 /* Dump the copy-of value for variable VAR to FILE. */
424 dump_copy_of (FILE *file, tree var)
429 print_generic_expr (file, var, dump_flags);
431 if (TREE_CODE (var) != SSA_NAME)
434 visited = sbitmap_alloc (num_ssa_names);
435 sbitmap_zero (visited);
436 SET_BIT (visited, SSA_NAME_VERSION (var));
438 fprintf (file, " copy-of chain: ");
441 print_generic_expr (file, val, 0);
443 while (copy_of[SSA_NAME_VERSION (val)].value)
445 fprintf (file, "-> ");
446 val = copy_of[SSA_NAME_VERSION (val)].value;
447 print_generic_expr (file, val, 0);
449 if (TEST_BIT (visited, SSA_NAME_VERSION (val)))
451 SET_BIT (visited, SSA_NAME_VERSION (val));
454 val = get_copy_of_val (var)->value;
455 if (val == NULL_TREE)
456 fprintf (file, "[UNDEFINED]");
458 fprintf (file, "[COPY]");
460 fprintf (file, "[NOT A COPY]");
462 sbitmap_free (visited);
466 /* Evaluate the RHS of STMT. If it produces a valid copy, set the LHS
467 value and store the LHS into *RESULT_P. If STMT generates more
468 than one name (i.e., STMT is an aliased store), it is enough to
469 store the first name in the VDEF list into *RESULT_P. After
470 all, the names generated will be VUSEd in the same statements. */
472 static enum ssa_prop_result
473 copy_prop_visit_assignment (gimple stmt, tree *result_p)
476 prop_value_t *rhs_val;
478 lhs = gimple_assign_lhs (stmt);
479 rhs = gimple_assign_rhs1 (stmt);
482 gcc_assert (gimple_assign_rhs_code (stmt) == SSA_NAME);
484 rhs_val = get_copy_of_val (rhs);
486 if (TREE_CODE (lhs) == SSA_NAME)
488 /* Straight copy between two SSA names. First, make sure that
489 we can propagate the RHS into uses of LHS. */
490 if (!may_propagate_copy (lhs, rhs))
491 return SSA_PROP_VARYING;
493 /* Notice that in the case of assignments, we make the LHS be a
494 copy of RHS's value, not of RHS itself. This avoids keeping
495 unnecessary copy-of chains (assignments cannot be in a cycle
496 like PHI nodes), speeding up the propagation process.
497 This is different from what we do in copy_prop_visit_phi_node.
498 In those cases, we are interested in the copy-of chains. */
500 if (set_copy_of_val (*result_p, rhs_val->value))
501 return SSA_PROP_INTERESTING;
503 return SSA_PROP_NOT_INTERESTING;
506 return SSA_PROP_VARYING;
510 /* Visit the GIMPLE_COND STMT. Return SSA_PROP_INTERESTING
511 if it can determine which edge will be taken. Otherwise, return
514 static enum ssa_prop_result
515 copy_prop_visit_cond_stmt (gimple stmt, edge *taken_edge_p)
517 enum ssa_prop_result retval = SSA_PROP_VARYING;
519 tree op0 = gimple_cond_lhs (stmt);
520 tree op1 = gimple_cond_rhs (stmt);
522 /* The only conditionals that we may be able to compute statically
523 are predicates involving two SSA_NAMEs. */
524 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
526 op0 = get_last_copy_of (op0);
527 op1 = get_last_copy_of (op1);
529 /* See if we can determine the predicate's value. */
530 if (dump_file && (dump_flags & TDF_DETAILS))
532 fprintf (dump_file, "Trying to determine truth value of ");
533 fprintf (dump_file, "predicate ");
534 print_gimple_stmt (dump_file, stmt, 0, 0);
537 /* We can fold COND and get a useful result only when we have
538 the same SSA_NAME on both sides of a comparison operator. */
541 tree folded_cond = fold_binary (gimple_cond_code (stmt),
542 boolean_type_node, op0, op1);
545 basic_block bb = gimple_bb (stmt);
546 *taken_edge_p = find_taken_edge (bb, folded_cond);
548 retval = SSA_PROP_INTERESTING;
553 if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p)
554 fprintf (dump_file, "\nConditional will always take edge %d->%d\n",
555 (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index);
561 /* Evaluate statement STMT. If the statement produces a new output
562 value, return SSA_PROP_INTERESTING and store the SSA_NAME holding
563 the new value in *RESULT_P.
565 If STMT is a conditional branch and we can determine its truth
566 value, set *TAKEN_EDGE_P accordingly.
568 If the new value produced by STMT is varying, return
571 static enum ssa_prop_result
572 copy_prop_visit_stmt (gimple stmt, edge *taken_edge_p, tree *result_p)
574 enum ssa_prop_result retval;
576 if (dump_file && (dump_flags & TDF_DETAILS))
578 fprintf (dump_file, "\nVisiting statement:\n");
579 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
580 fprintf (dump_file, "\n");
583 if (gimple_assign_single_p (stmt)
584 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
585 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
587 /* If the statement is a copy assignment, evaluate its RHS to
588 see if the lattice value of its output has changed. */
589 retval = copy_prop_visit_assignment (stmt, result_p);
591 else if (gimple_code (stmt) == GIMPLE_COND)
593 /* See if we can determine which edge goes out of a conditional
595 retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p);
598 retval = SSA_PROP_VARYING;
600 if (retval == SSA_PROP_VARYING)
605 /* Any other kind of statement is not interesting for constant
606 propagation and, therefore, not worth simulating. */
607 if (dump_file && (dump_flags & TDF_DETAILS))
608 fprintf (dump_file, "No interesting values produced.\n");
610 /* The assignment is not a copy operation. Don't visit this
611 statement again and mark all the definitions in the statement
612 to be copies of nothing. */
613 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS)
614 set_copy_of_val (def, def);
621 /* Visit PHI node PHI. If all the arguments produce the same value,
622 set it to be the value of the LHS of PHI. */
624 static enum ssa_prop_result
625 copy_prop_visit_phi_node (gimple phi)
627 enum ssa_prop_result retval;
629 prop_value_t phi_val = { 0, NULL_TREE };
631 tree lhs = gimple_phi_result (phi);
633 if (dump_file && (dump_flags & TDF_DETAILS))
635 fprintf (dump_file, "\nVisiting PHI node: ");
636 print_gimple_stmt (dump_file, phi, 0, dump_flags);
637 fprintf (dump_file, "\n\n");
640 for (i = 0; i < gimple_phi_num_args (phi); i++)
642 prop_value_t *arg_val;
643 tree arg = gimple_phi_arg_def (phi, i);
644 edge e = gimple_phi_arg_edge (phi, i);
646 /* We don't care about values flowing through non-executable
648 if (!(e->flags & EDGE_EXECUTABLE))
651 /* Constants in the argument list never generate a useful copy.
652 Similarly, names that flow through abnormal edges cannot be
653 used to derive copies. */
654 if (TREE_CODE (arg) != SSA_NAME || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
660 /* Avoid copy propagation from an inner into an outer loop.
661 Otherwise, this may move loop variant variables outside of
662 their loops and prevent coalescing opportunities. If the
663 value was loop invariant, it will be hoisted by LICM and
664 exposed for copy propagation. Not a problem for virtual
666 if (is_gimple_reg (lhs)
667 && loop_depth_of_name (arg) > loop_depth_of_name (lhs))
673 /* If the LHS appears in the argument list, ignore it. It is
674 irrelevant as a copy. */
675 if (arg == lhs || get_last_copy_of (arg) == lhs)
678 if (dump_file && (dump_flags & TDF_DETAILS))
680 fprintf (dump_file, "\tArgument #%d: ", i);
681 dump_copy_of (dump_file, arg);
682 fprintf (dump_file, "\n");
685 arg_val = get_copy_of_val (arg);
687 /* If the LHS didn't have a value yet, make it a copy of the
688 first argument we find. Notice that while we make the LHS be
689 a copy of the argument itself, we take the memory reference
690 from the argument's value so that we can compare it to the
691 memory reference of all the other arguments. */
692 if (phi_val.value == NULL_TREE)
694 phi_val.value = arg_val->value ? arg_val->value : arg;
698 /* If PHI_VAL and ARG don't have a common copy-of chain, then
699 this PHI node cannot be a copy operation. Also, if we are
700 copy propagating stores and these two arguments came from
701 different memory references, they cannot be considered
703 if (get_last_copy_of (phi_val.value) != get_last_copy_of (arg))
710 if (phi_val.value && may_propagate_copy (lhs, phi_val.value)
711 && set_copy_of_val (lhs, phi_val.value))
712 retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
714 retval = SSA_PROP_NOT_INTERESTING;
716 if (dump_file && (dump_flags & TDF_DETAILS))
718 fprintf (dump_file, "\nPHI node ");
719 dump_copy_of (dump_file, lhs);
720 fprintf (dump_file, "\nTelling the propagator to ");
721 if (retval == SSA_PROP_INTERESTING)
722 fprintf (dump_file, "add SSA edges out of this PHI and continue.");
723 else if (retval == SSA_PROP_VARYING)
724 fprintf (dump_file, "add SSA edges out of this PHI and never visit again.");
726 fprintf (dump_file, "do nothing with SSA edges and keep iterating.");
727 fprintf (dump_file, "\n\n");
734 /* Initialize structures used for copy propagation. PHIS_ONLY is true
735 if we should only consider PHI nodes as generating copy propagation
739 init_copy_prop (void)
743 copy_of = XCNEWVEC (prop_value_t, num_ssa_names);
745 cached_last_copy_of = XCNEWVEC (tree, num_ssa_names);
749 gimple_stmt_iterator si;
750 int depth = bb->loop_depth;
752 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
754 gimple stmt = gsi_stmt (si);
758 /* The only statements that we care about are those that may
759 generate useful copies. We also need to mark conditional
760 jumps so that their outgoing edges are added to the work
761 lists of the propagator.
763 Avoid copy propagation from an inner into an outer loop.
764 Otherwise, this may move loop variant variables outside of
765 their loops and prevent coalescing opportunities. If the
766 value was loop invariant, it will be hoisted by LICM and
767 exposed for copy propagation. */
768 if (stmt_ends_bb_p (stmt))
769 prop_set_simulate_again (stmt, true);
770 else if (stmt_may_generate_copy (stmt)
771 /* Since we are iterating over the statements in
772 BB, not the phi nodes, STMT will always be an
774 && loop_depth_of_name (gimple_assign_rhs1 (stmt)) <= depth)
775 prop_set_simulate_again (stmt, true);
777 prop_set_simulate_again (stmt, false);
779 /* Mark all the outputs of this statement as not being
780 the copy of anything. */
781 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
782 if (!prop_simulate_again_p (stmt))
783 set_copy_of_val (def, def);
785 cached_last_copy_of[SSA_NAME_VERSION (def)] = def;
788 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
790 gimple phi = gsi_stmt (si);
793 def = gimple_phi_result (phi);
794 if (!is_gimple_reg (def)
795 /* In loop-closed SSA form do not copy-propagate through
796 PHI nodes. Technically this is only needed for loop
797 exit PHIs, but this is difficult to query. */
799 && gimple_phi_num_args (phi) == 1
800 && loops_state_satisfies_p (LOOP_CLOSED_SSA)))
801 prop_set_simulate_again (phi, false);
803 prop_set_simulate_again (phi, true);
805 if (!prop_simulate_again_p (phi))
806 set_copy_of_val (def, def);
808 cached_last_copy_of[SSA_NAME_VERSION (def)] = def;
814 /* Deallocate memory used in copy propagation and do final
818 fini_copy_prop (void)
823 /* Set the final copy-of value for each variable by traversing the
825 tmp = XCNEWVEC (prop_value_t, num_ssa_names);
826 for (i = 1; i < num_ssa_names; i++)
828 tree var = ssa_name (i);
831 || copy_of[i].value == var)
834 tmp[i].value = get_last_copy_of (var);
836 /* In theory the points-to solution of all members of the
837 copy chain is their intersection. For now we do not bother
838 to compute this but only make sure we do not lose points-to
839 information completely by setting the points-to solution
840 of the representative to the first solution we find if
841 it doesn't have one already. */
842 if (tmp[i].value != var
843 && POINTER_TYPE_P (TREE_TYPE (var))
844 && SSA_NAME_PTR_INFO (var)
845 && !SSA_NAME_PTR_INFO (tmp[i].value))
846 duplicate_ssa_name_ptr_info (tmp[i].value, SSA_NAME_PTR_INFO (var));
849 substitute_and_fold (tmp, false);
851 free (cached_last_copy_of);
857 /* Main entry point to the copy propagator.
859 PHIS_ONLY is true if we should only consider PHI nodes as generating
860 copy propagation opportunities.
862 The algorithm propagates the value COPY-OF using ssa_propagate. For
863 every variable X_i, COPY-OF(X_i) indicates which variable is X_i created
864 from. The following example shows how the algorithm proceeds at a
868 2 a_2 = PHI <a_24, x_1>
870 4 x_1 = PHI <x_298, a_5, a_2>
872 The end result should be that a_2, a_5, a_24 and x_1 are a copy of
873 x_298. Propagation proceeds as follows.
875 Visit #1: a_24 is copy-of x_1. Value changed.
876 Visit #2: a_2 is copy-of x_1. Value changed.
877 Visit #3: a_5 is copy-of x_1. Value changed.
878 Visit #4: x_1 is copy-of x_298. Value changed.
879 Visit #1: a_24 is copy-of x_298. Value changed.
880 Visit #2: a_2 is copy-of x_298. Value changed.
881 Visit #3: a_5 is copy-of x_298. Value changed.
882 Visit #4: x_1 is copy-of x_298. Stable state reached.
884 When visiting PHI nodes, we only consider arguments that flow
885 through edges marked executable by the propagation engine. So,
886 when visiting statement #2 for the first time, we will only look at
887 the first argument (a_24) and optimistically assume that its value
888 is the copy of a_24 (x_1).
890 The problem with this approach is that it may fail to discover copy
891 relations in PHI cycles. Instead of propagating copy-of
892 values, we actually propagate copy-of chains. For instance:
899 In this code fragment, COPY-OF (X_i) = { D_4, C_9, A_3, B_1 }.
900 Obviously, we are only really interested in the last value of the
901 chain, however the propagator needs to access the copy-of chain
902 when visiting PHI nodes.
904 To represent the copy-of chain, we use the array COPY_CHAINS, which
905 holds the first link in the copy-of chain for every variable.
906 If variable X_i is a copy of X_j, which in turn is a copy of X_k,
907 the array will contain:
913 Keeping copy-of chains instead of copy-of values directly becomes
914 important when visiting PHI nodes. Suppose that we had the
915 following PHI cycle, such that x_52 is already considered a copy of
918 1 x_54 = PHI <x_53, x_52>
919 2 x_53 = PHI <x_898, x_54>
921 Visit #1: x_54 is copy-of x_53 (because x_52 is copy-of x_53)
922 Visit #2: x_53 is copy-of x_898 (because x_54 is a copy of x_53,
923 so it is considered irrelevant
925 Visit #1: x_54 is copy-of nothing (x_53 is a copy-of x_898 and
926 x_52 is a copy of x_53, so
928 Visit #2: x_53 is copy-of nothing
930 This problem is avoided by keeping a chain of copies, instead of
931 the final copy-of value. Propagation will now only keep the first
932 element of a variable's copy-of chain. When visiting PHI nodes,
933 arguments are considered equal if their copy-of chains end in the
934 same variable. So, as long as their copy-of chains overlap, we
935 know that they will be a copy of the same variable, regardless of
936 which variable that may be).
938 Propagation would then proceed as follows (the notation a -> b
939 means that a is a copy-of b):
941 Visit #1: x_54 = PHI <x_53, x_52>
944 Result: x_54 -> x_53. Value changed. Add SSA edges.
946 Visit #1: x_53 = PHI <x_898, x_54>
949 Result: x_53 -> x_898. Value changed. Add SSA edges.
951 Visit #2: x_54 = PHI <x_53, x_52>
953 x_52 -> x_53 -> x_898
954 Result: x_54 -> x_898. Value changed. Add SSA edges.
956 Visit #2: x_53 = PHI <x_898, x_54>
959 Result: x_53 -> x_898. Value didn't change. Stable state
961 Once the propagator stabilizes, we end up with the desired result
962 x_53 and x_54 are both copies of x_898. */
965 execute_copy_prop (void)
968 ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node);
974 gate_copy_prop (void)
976 return flag_tree_copy_prop != 0;
979 struct gimple_opt_pass pass_copy_prop =
983 "copyprop", /* name */
984 gate_copy_prop, /* gate */
985 execute_copy_prop, /* execute */
988 0, /* static_pass_number */
989 TV_TREE_COPY_PROP, /* tv_id */
990 PROP_ssa | PROP_cfg, /* properties_required */
991 0, /* properties_provided */
992 0, /* properties_destroyed */
993 0, /* todo_flags_start */
998 | TODO_update_ssa /* todo_flags_finish */