Daily bump.
[official-gcc.git] / gcc / tree-ssa-copy.c
blob02f474355b75a9e425fe23cf4b5491355a3faadb
1 /* Copy propagation and SSA_NAME replacement support routines.
2 Copyright (C) 2004-2014 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 "tm_p.h"
27 #include "basic-block.h"
28 #include "function.h"
29 #include "gimple-pretty-print.h"
30 #include "tree-ssa-alias.h"
31 #include "internal-fn.h"
32 #include "gimple-expr.h"
33 #include "is-a.h"
34 #include "gimple.h"
35 #include "gimple-iterator.h"
36 #include "gimple-ssa.h"
37 #include "tree-cfg.h"
38 #include "tree-phinodes.h"
39 #include "ssa-iterators.h"
40 #include "stringpool.h"
41 #include "tree-ssanames.h"
42 #include "tree-pass.h"
43 #include "tree-ssa-propagate.h"
44 #include "langhooks.h"
45 #include "cfgloop.h"
46 #include "tree-scalar-evolution.h"
47 #include "tree-ssa-dom.h"
49 /* This file implements the copy propagation pass and provides a
50 handful of interfaces for performing const/copy propagation and
51 simple expression replacement which keep variable annotations
52 up-to-date.
54 We require that for any copy operation where the RHS and LHS have
55 a non-null memory tag the memory tag be the same. It is OK
56 for one or both of the memory tags to be NULL.
58 We also require tracking if a variable is dereferenced in a load or
59 store operation.
61 We enforce these requirements by having all copy propagation and
62 replacements of one SSA_NAME with a different SSA_NAME to use the
63 APIs defined in this file. */
65 /*---------------------------------------------------------------------------
66 Copy propagation
67 ---------------------------------------------------------------------------*/
68 /* Lattice for copy-propagation. The lattice is initialized to
69 UNDEFINED (value == NULL) for SSA names that can become a copy
70 of something or VARYING (value == self) if not (see get_copy_of_val
71 and stmt_may_generate_copy). Other values make the name a COPY
72 of that value.
74 When visiting a statement or PHI node the lattice value for an
75 SSA name can transition from UNDEFINED to COPY to VARYING. */
77 struct prop_value_d {
78 /* Copy-of value. */
79 tree value;
81 typedef struct prop_value_d prop_value_t;
83 static prop_value_t *copy_of;
84 static unsigned n_copy_of;
87 /* Return true if this statement may generate a useful copy. */
89 static bool
90 stmt_may_generate_copy (gimple stmt)
92 if (gimple_code (stmt) == GIMPLE_PHI)
93 return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt));
95 if (gimple_code (stmt) != GIMPLE_ASSIGN)
96 return false;
98 /* If the statement has volatile operands, it won't generate a
99 useful copy. */
100 if (gimple_has_volatile_ops (stmt))
101 return false;
103 /* Statements with loads and/or stores will never generate a useful copy. */
104 if (gimple_vuse (stmt))
105 return false;
107 /* Otherwise, the only statements that generate useful copies are
108 assignments whose RHS is just an SSA name that doesn't flow
109 through abnormal edges. */
110 return ((gimple_assign_rhs_code (stmt) == SSA_NAME
111 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
112 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)));
116 /* Return the copy-of value for VAR. */
118 static inline prop_value_t *
119 get_copy_of_val (tree var)
121 prop_value_t *val = &copy_of[SSA_NAME_VERSION (var)];
123 if (val->value == NULL_TREE
124 && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var)))
126 /* If the variable will never generate a useful copy relation,
127 make it its own copy. */
128 val->value = var;
131 return val;
134 /* Return the variable VAR is a copy of or VAR if VAR isn't the result
135 of a copy. */
137 static inline tree
138 valueize_val (tree var)
140 if (TREE_CODE (var) == SSA_NAME)
142 tree val = get_copy_of_val (var)->value;
143 if (val)
144 return val;
146 return var;
149 /* Set VAL to be the copy of VAR. If that changed return true. */
151 static inline bool
152 set_copy_of_val (tree var, tree val)
154 unsigned int ver = SSA_NAME_VERSION (var);
155 tree old;
157 /* Set FIRST to be the first link in COPY_OF[DEST]. If that
158 changed, return true. */
159 old = copy_of[ver].value;
160 copy_of[ver].value = val;
162 if (old != val
163 || (val && !operand_equal_p (old, val, 0)))
164 return true;
166 return false;
170 /* Dump the copy-of value for variable VAR to FILE. */
172 static void
173 dump_copy_of (FILE *file, tree var)
175 tree val;
177 print_generic_expr (file, var, dump_flags);
178 if (TREE_CODE (var) != SSA_NAME)
179 return;
181 val = copy_of[SSA_NAME_VERSION (var)].value;
182 fprintf (file, " copy-of chain: ");
183 print_generic_expr (file, var, 0);
184 fprintf (file, " ");
185 if (!val)
186 fprintf (file, "[UNDEFINED]");
187 else if (val == var)
188 fprintf (file, "[NOT A COPY]");
189 else
191 fprintf (file, "-> ");
192 print_generic_expr (file, val, 0);
193 fprintf (file, " ");
194 fprintf (file, "[COPY]");
199 /* Evaluate the RHS of STMT. If it produces a valid copy, set the LHS
200 value and store the LHS into *RESULT_P. */
202 static enum ssa_prop_result
203 copy_prop_visit_assignment (gimple stmt, tree *result_p)
205 tree lhs, rhs;
207 lhs = gimple_assign_lhs (stmt);
208 rhs = valueize_val (gimple_assign_rhs1 (stmt));
210 if (TREE_CODE (lhs) == SSA_NAME)
212 /* Straight copy between two SSA names. First, make sure that
213 we can propagate the RHS into uses of LHS. */
214 if (!may_propagate_copy (lhs, rhs))
215 return SSA_PROP_VARYING;
217 *result_p = lhs;
218 if (set_copy_of_val (*result_p, rhs))
219 return SSA_PROP_INTERESTING;
220 else
221 return SSA_PROP_NOT_INTERESTING;
224 return SSA_PROP_VARYING;
228 /* Visit the GIMPLE_COND STMT. Return SSA_PROP_INTERESTING
229 if it can determine which edge will be taken. Otherwise, return
230 SSA_PROP_VARYING. */
232 static enum ssa_prop_result
233 copy_prop_visit_cond_stmt (gimple stmt, edge *taken_edge_p)
235 enum ssa_prop_result retval = SSA_PROP_VARYING;
236 location_t loc = gimple_location (stmt);
238 tree op0 = gimple_cond_lhs (stmt);
239 tree op1 = gimple_cond_rhs (stmt);
241 /* The only conditionals that we may be able to compute statically
242 are predicates involving two SSA_NAMEs. */
243 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
245 op0 = valueize_val (op0);
246 op1 = valueize_val (op1);
248 /* See if we can determine the predicate's value. */
249 if (dump_file && (dump_flags & TDF_DETAILS))
251 fprintf (dump_file, "Trying to determine truth value of ");
252 fprintf (dump_file, "predicate ");
253 print_gimple_stmt (dump_file, stmt, 0, 0);
256 /* We can fold COND and get a useful result only when we have
257 the same SSA_NAME on both sides of a comparison operator. */
258 if (op0 == op1)
260 tree folded_cond = fold_binary_loc (loc, gimple_cond_code (stmt),
261 boolean_type_node, op0, op1);
262 if (folded_cond)
264 basic_block bb = gimple_bb (stmt);
265 *taken_edge_p = find_taken_edge (bb, folded_cond);
266 if (*taken_edge_p)
267 retval = SSA_PROP_INTERESTING;
272 if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p)
273 fprintf (dump_file, "\nConditional will always take edge %d->%d\n",
274 (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index);
276 return retval;
280 /* Evaluate statement STMT. If the statement produces a new output
281 value, return SSA_PROP_INTERESTING and store the SSA_NAME holding
282 the new value in *RESULT_P.
284 If STMT is a conditional branch and we can determine its truth
285 value, set *TAKEN_EDGE_P accordingly.
287 If the new value produced by STMT is varying, return
288 SSA_PROP_VARYING. */
290 static enum ssa_prop_result
291 copy_prop_visit_stmt (gimple stmt, edge *taken_edge_p, tree *result_p)
293 enum ssa_prop_result retval;
295 if (dump_file && (dump_flags & TDF_DETAILS))
297 fprintf (dump_file, "\nVisiting statement:\n");
298 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
299 fprintf (dump_file, "\n");
302 if (gimple_assign_single_p (stmt)
303 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
304 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
305 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
307 /* If the statement is a copy assignment, evaluate its RHS to
308 see if the lattice value of its output has changed. */
309 retval = copy_prop_visit_assignment (stmt, result_p);
311 else if (gimple_code (stmt) == GIMPLE_COND)
313 /* See if we can determine which edge goes out of a conditional
314 jump. */
315 retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p);
317 else
318 retval = SSA_PROP_VARYING;
320 if (retval == SSA_PROP_VARYING)
322 tree def;
323 ssa_op_iter i;
325 /* Any other kind of statement is not interesting for constant
326 propagation and, therefore, not worth simulating. */
327 if (dump_file && (dump_flags & TDF_DETAILS))
328 fprintf (dump_file, "No interesting values produced.\n");
330 /* The assignment is not a copy operation. Don't visit this
331 statement again and mark all the definitions in the statement
332 to be copies of nothing. */
333 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS)
334 set_copy_of_val (def, def);
337 return retval;
341 /* Visit PHI node PHI. If all the arguments produce the same value,
342 set it to be the value of the LHS of PHI. */
344 static enum ssa_prop_result
345 copy_prop_visit_phi_node (gimple phi)
347 enum ssa_prop_result retval;
348 unsigned i;
349 prop_value_t phi_val = { NULL_TREE };
351 tree lhs = gimple_phi_result (phi);
353 if (dump_file && (dump_flags & TDF_DETAILS))
355 fprintf (dump_file, "\nVisiting PHI node: ");
356 print_gimple_stmt (dump_file, phi, 0, dump_flags);
359 for (i = 0; i < gimple_phi_num_args (phi); i++)
361 prop_value_t *arg_val;
362 tree arg_value;
363 tree arg = gimple_phi_arg_def (phi, i);
364 edge e = gimple_phi_arg_edge (phi, i);
366 /* We don't care about values flowing through non-executable
367 edges. */
368 if (!(e->flags & EDGE_EXECUTABLE))
369 continue;
371 /* Names that flow through abnormal edges cannot be used to
372 derive copies. */
373 if (TREE_CODE (arg) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
375 phi_val.value = lhs;
376 break;
379 if (dump_file && (dump_flags & TDF_DETAILS))
381 fprintf (dump_file, "\tArgument #%d: ", i);
382 dump_copy_of (dump_file, arg);
383 fprintf (dump_file, "\n");
386 if (TREE_CODE (arg) == SSA_NAME)
388 arg_val = get_copy_of_val (arg);
390 /* If we didn't visit the definition of arg yet treat it as
391 UNDEFINED. This also handles PHI arguments that are the
392 same as lhs. We'll come here again. */
393 if (!arg_val->value)
394 continue;
396 arg_value = arg_val->value;
398 else
399 arg_value = valueize_val (arg);
401 /* Avoid copy propagation from an inner into an outer loop.
402 Otherwise, this may move loop variant variables outside of
403 their loops and prevent coalescing opportunities. If the
404 value was loop invariant, it will be hoisted by LICM and
405 exposed for copy propagation.
406 ??? The value will be always loop invariant.
407 In loop-closed SSA form do not copy-propagate through
408 PHI nodes in blocks with a loop exit edge predecessor. */
409 if (current_loops
410 && TREE_CODE (arg_value) == SSA_NAME
411 && (loop_depth_of_name (arg_value) > loop_depth_of_name (lhs)
412 || (loops_state_satisfies_p (LOOP_CLOSED_SSA)
413 && loop_exit_edge_p (e->src->loop_father, e))))
415 phi_val.value = lhs;
416 break;
419 /* If the LHS didn't have a value yet, make it a copy of the
420 first argument we find. */
421 if (phi_val.value == NULL_TREE)
423 phi_val.value = arg_value;
424 continue;
427 /* If PHI_VAL and ARG don't have a common copy-of chain, then
428 this PHI node cannot be a copy operation. */
429 if (phi_val.value != arg_value
430 && !operand_equal_p (phi_val.value, arg_value, 0))
432 phi_val.value = lhs;
433 break;
437 if (phi_val.value
438 && may_propagate_copy (lhs, phi_val.value)
439 && set_copy_of_val (lhs, phi_val.value))
440 retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
441 else
442 retval = SSA_PROP_NOT_INTERESTING;
444 if (dump_file && (dump_flags & TDF_DETAILS))
446 fprintf (dump_file, "PHI node ");
447 dump_copy_of (dump_file, lhs);
448 fprintf (dump_file, "\nTelling the propagator to ");
449 if (retval == SSA_PROP_INTERESTING)
450 fprintf (dump_file, "add SSA edges out of this PHI and continue.");
451 else if (retval == SSA_PROP_VARYING)
452 fprintf (dump_file, "add SSA edges out of this PHI and never visit again.");
453 else
454 fprintf (dump_file, "do nothing with SSA edges and keep iterating.");
455 fprintf (dump_file, "\n\n");
458 return retval;
462 /* Initialize structures used for copy propagation. */
464 static void
465 init_copy_prop (void)
467 basic_block bb;
469 n_copy_of = num_ssa_names;
470 copy_of = XCNEWVEC (prop_value_t, n_copy_of);
472 FOR_EACH_BB_FN (bb, cfun)
474 gimple_stmt_iterator si;
475 int depth = bb_loop_depth (bb);
477 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
479 gimple stmt = gsi_stmt (si);
480 ssa_op_iter iter;
481 tree def;
483 /* The only statements that we care about are those that may
484 generate useful copies. We also need to mark conditional
485 jumps so that their outgoing edges are added to the work
486 lists of the propagator.
488 Avoid copy propagation from an inner into an outer loop.
489 Otherwise, this may move loop variant variables outside of
490 their loops and prevent coalescing opportunities. If the
491 value was loop invariant, it will be hoisted by LICM and
492 exposed for copy propagation.
493 ??? This doesn't make sense. */
494 if (stmt_ends_bb_p (stmt))
495 prop_set_simulate_again (stmt, true);
496 else if (stmt_may_generate_copy (stmt)
497 /* Since we are iterating over the statements in
498 BB, not the phi nodes, STMT will always be an
499 assignment. */
500 && loop_depth_of_name (gimple_assign_rhs1 (stmt)) <= depth)
501 prop_set_simulate_again (stmt, true);
502 else
503 prop_set_simulate_again (stmt, false);
505 /* Mark all the outputs of this statement as not being
506 the copy of anything. */
507 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
508 if (!prop_simulate_again_p (stmt))
509 set_copy_of_val (def, def);
512 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
514 gimple phi = gsi_stmt (si);
515 tree def;
517 def = gimple_phi_result (phi);
518 if (virtual_operand_p (def))
519 prop_set_simulate_again (phi, false);
520 else
521 prop_set_simulate_again (phi, true);
523 if (!prop_simulate_again_p (phi))
524 set_copy_of_val (def, def);
529 /* Callback for substitute_and_fold to get at the final copy-of values. */
531 static tree
532 get_value (tree name)
534 tree val;
535 if (SSA_NAME_VERSION (name) >= n_copy_of)
536 return NULL_TREE;
537 val = copy_of[SSA_NAME_VERSION (name)].value;
538 if (val && val != name)
539 return val;
540 return NULL_TREE;
543 /* Deallocate memory used in copy propagation and do final
544 substitution. */
546 static void
547 fini_copy_prop (void)
549 unsigned i;
551 /* Set the final copy-of value for each variable by traversing the
552 copy-of chains. */
553 for (i = 1; i < num_ssa_names; i++)
555 tree var = ssa_name (i);
556 if (!var
557 || !copy_of[i].value
558 || copy_of[i].value == var)
559 continue;
561 /* In theory the points-to solution of all members of the
562 copy chain is their intersection. For now we do not bother
563 to compute this but only make sure we do not lose points-to
564 information completely by setting the points-to solution
565 of the representative to the first solution we find if
566 it doesn't have one already. */
567 if (copy_of[i].value != var
568 && TREE_CODE (copy_of[i].value) == SSA_NAME)
570 basic_block copy_of_bb
571 = gimple_bb (SSA_NAME_DEF_STMT (copy_of[i].value));
572 basic_block var_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
573 if (POINTER_TYPE_P (TREE_TYPE (var))
574 && SSA_NAME_PTR_INFO (var)
575 && !SSA_NAME_PTR_INFO (copy_of[i].value))
577 duplicate_ssa_name_ptr_info (copy_of[i].value,
578 SSA_NAME_PTR_INFO (var));
579 /* Points-to information is cfg insensitive,
580 but alignment info might be cfg sensitive, if it
581 e.g. is derived from VRP derived non-zero bits.
582 So, do not copy alignment info if the two SSA_NAMEs
583 aren't defined in the same basic block. */
584 if (var_bb != copy_of_bb)
585 mark_ptr_info_alignment_unknown
586 (SSA_NAME_PTR_INFO (copy_of[i].value));
588 else if (!POINTER_TYPE_P (TREE_TYPE (var))
589 && SSA_NAME_RANGE_INFO (var)
590 && !SSA_NAME_RANGE_INFO (copy_of[i].value)
591 && var_bb == copy_of_bb)
592 duplicate_ssa_name_range_info (copy_of[i].value,
593 SSA_NAME_RANGE_TYPE (var),
594 SSA_NAME_RANGE_INFO (var));
598 /* Don't do DCE if SCEV is initialized. It would destroy the scev cache. */
599 substitute_and_fold (get_value, NULL, !scev_initialized_p ());
601 free (copy_of);
605 /* Main entry point to the copy propagator.
607 PHIS_ONLY is true if we should only consider PHI nodes as generating
608 copy propagation opportunities.
610 The algorithm propagates the value COPY-OF using ssa_propagate. For
611 every variable X_i, COPY-OF(X_i) indicates which variable is X_i created
612 from. The following example shows how the algorithm proceeds at a
613 high level:
615 1 a_24 = x_1
616 2 a_2 = PHI <a_24, x_1>
617 3 a_5 = PHI <a_2>
618 4 x_1 = PHI <x_298, a_5, a_2>
620 The end result should be that a_2, a_5, a_24 and x_1 are a copy of
621 x_298. Propagation proceeds as follows.
623 Visit #1: a_24 is copy-of x_1. Value changed.
624 Visit #2: a_2 is copy-of x_1. Value changed.
625 Visit #3: a_5 is copy-of x_1. Value changed.
626 Visit #4: x_1 is copy-of x_298. Value changed.
627 Visit #1: a_24 is copy-of x_298. Value changed.
628 Visit #2: a_2 is copy-of x_298. Value changed.
629 Visit #3: a_5 is copy-of x_298. Value changed.
630 Visit #4: x_1 is copy-of x_298. Stable state reached.
632 When visiting PHI nodes, we only consider arguments that flow
633 through edges marked executable by the propagation engine. So,
634 when visiting statement #2 for the first time, we will only look at
635 the first argument (a_24) and optimistically assume that its value
636 is the copy of a_24 (x_1). */
638 static unsigned int
639 execute_copy_prop (void)
641 init_copy_prop ();
642 ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node);
643 fini_copy_prop ();
644 return 0;
647 static bool
648 gate_copy_prop (void)
650 return flag_tree_copy_prop != 0;
653 namespace {
655 const pass_data pass_data_copy_prop =
657 GIMPLE_PASS, /* type */
658 "copyprop", /* name */
659 OPTGROUP_NONE, /* optinfo_flags */
660 true, /* has_gate */
661 true, /* has_execute */
662 TV_TREE_COPY_PROP, /* tv_id */
663 ( PROP_ssa | PROP_cfg ), /* properties_required */
664 0, /* properties_provided */
665 0, /* properties_destroyed */
666 0, /* todo_flags_start */
667 ( TODO_cleanup_cfg | TODO_verify_ssa
668 | TODO_update_ssa ), /* todo_flags_finish */
671 class pass_copy_prop : public gimple_opt_pass
673 public:
674 pass_copy_prop (gcc::context *ctxt)
675 : gimple_opt_pass (pass_data_copy_prop, ctxt)
678 /* opt_pass methods: */
679 opt_pass * clone () { return new pass_copy_prop (m_ctxt); }
680 bool gate () { return gate_copy_prop (); }
681 unsigned int execute () { return execute_copy_prop (); }
683 }; // class pass_copy_prop
685 } // anon namespace
687 gimple_opt_pass *
688 make_pass_copy_prop (gcc::context *ctxt)
690 return new pass_copy_prop (ctxt);