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)
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"
27 #include "basic-block.h"
29 #include "gimple-pretty-print.h"
30 #include "tree-ssa-alias.h"
31 #include "internal-fn.h"
32 #include "gimple-expr.h"
35 #include "gimple-iterator.h"
36 #include "gimple-ssa.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"
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
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
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 /*---------------------------------------------------------------------------
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
74 When visiting a statement or PHI node the lattice value for an
75 SSA name can transition from UNDEFINED to COPY to VARYING. */
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. */
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
)
98 /* If the statement has volatile operands, it won't generate a
100 if (gimple_has_volatile_ops (stmt
))
103 /* Statements with loads and/or stores will never generate a useful copy. */
104 if (gimple_vuse (stmt
))
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
= ©_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. */
134 /* Return the variable VAR is a copy of or VAR if VAR isn't the result
138 valueize_val (tree var
)
140 if (TREE_CODE (var
) == SSA_NAME
)
142 tree val
= get_copy_of_val (var
)->value
;
149 /* Set VAL to be the copy of VAR. If that changed return true. */
152 set_copy_of_val (tree var
, tree val
)
154 unsigned int ver
= SSA_NAME_VERSION (var
);
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
;
163 || (val
&& !operand_equal_p (old
, val
, 0)))
170 /* Dump the copy-of value for variable VAR to FILE. */
173 dump_copy_of (FILE *file
, tree var
)
177 print_generic_expr (file
, var
, dump_flags
);
178 if (TREE_CODE (var
) != SSA_NAME
)
181 val
= copy_of
[SSA_NAME_VERSION (var
)].value
;
182 fprintf (file
, " copy-of chain: ");
183 print_generic_expr (file
, var
, 0);
186 fprintf (file
, "[UNDEFINED]");
188 fprintf (file
, "[NOT A COPY]");
191 fprintf (file
, "-> ");
192 print_generic_expr (file
, val
, 0);
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
)
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
;
218 if (set_copy_of_val (*result_p
, rhs
))
219 return SSA_PROP_INTERESTING
;
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
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
= valueize_val (gimple_cond_lhs (stmt
));
239 tree op1
= valueize_val (gimple_cond_rhs (stmt
));
241 /* See if we can determine the predicate's value. */
242 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
244 fprintf (dump_file
, "Trying to determine truth value of ");
245 fprintf (dump_file
, "predicate ");
246 print_gimple_stmt (dump_file
, stmt
, 0, 0);
249 /* Fold COND and see whether we get a useful result. */
250 tree folded_cond
= fold_binary_loc (loc
, gimple_cond_code (stmt
),
251 boolean_type_node
, op0
, op1
);
254 basic_block bb
= gimple_bb (stmt
);
255 *taken_edge_p
= find_taken_edge (bb
, folded_cond
);
257 retval
= SSA_PROP_INTERESTING
;
260 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && *taken_edge_p
)
261 fprintf (dump_file
, "\nConditional will always take edge %d->%d\n",
262 (*taken_edge_p
)->src
->index
, (*taken_edge_p
)->dest
->index
);
268 /* Evaluate statement STMT. If the statement produces a new output
269 value, return SSA_PROP_INTERESTING and store the SSA_NAME holding
270 the new value in *RESULT_P.
272 If STMT is a conditional branch and we can determine its truth
273 value, set *TAKEN_EDGE_P accordingly.
275 If the new value produced by STMT is varying, return
278 static enum ssa_prop_result
279 copy_prop_visit_stmt (gimple stmt
, edge
*taken_edge_p
, tree
*result_p
)
281 enum ssa_prop_result retval
;
283 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
285 fprintf (dump_file
, "\nVisiting statement:\n");
286 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
287 fprintf (dump_file
, "\n");
290 if (gimple_assign_single_p (stmt
)
291 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
292 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
293 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
295 /* If the statement is a copy assignment, evaluate its RHS to
296 see if the lattice value of its output has changed. */
297 retval
= copy_prop_visit_assignment (stmt
, result_p
);
299 else if (gimple_code (stmt
) == GIMPLE_COND
)
301 /* See if we can determine which edge goes out of a conditional
303 retval
= copy_prop_visit_cond_stmt (stmt
, taken_edge_p
);
306 retval
= SSA_PROP_VARYING
;
308 if (retval
== SSA_PROP_VARYING
)
313 /* Any other kind of statement is not interesting for constant
314 propagation and, therefore, not worth simulating. */
315 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
316 fprintf (dump_file
, "No interesting values produced.\n");
318 /* The assignment is not a copy operation. Don't visit this
319 statement again and mark all the definitions in the statement
320 to be copies of nothing. */
321 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, i
, SSA_OP_ALL_DEFS
)
322 set_copy_of_val (def
, def
);
329 /* Visit PHI node PHI. If all the arguments produce the same value,
330 set it to be the value of the LHS of PHI. */
332 static enum ssa_prop_result
333 copy_prop_visit_phi_node (gimple phi
)
335 enum ssa_prop_result retval
;
337 prop_value_t phi_val
= { NULL_TREE
};
339 tree lhs
= gimple_phi_result (phi
);
341 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
343 fprintf (dump_file
, "\nVisiting PHI node: ");
344 print_gimple_stmt (dump_file
, phi
, 0, dump_flags
);
347 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
349 prop_value_t
*arg_val
;
351 tree arg
= gimple_phi_arg_def (phi
, i
);
352 edge e
= gimple_phi_arg_edge (phi
, i
);
354 /* We don't care about values flowing through non-executable
356 if (!(e
->flags
& EDGE_EXECUTABLE
))
359 /* Names that flow through abnormal edges cannot be used to
361 if (TREE_CODE (arg
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg
))
367 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
369 fprintf (dump_file
, "\tArgument #%d: ", i
);
370 dump_copy_of (dump_file
, arg
);
371 fprintf (dump_file
, "\n");
374 if (TREE_CODE (arg
) == SSA_NAME
)
376 arg_val
= get_copy_of_val (arg
);
378 /* If we didn't visit the definition of arg yet treat it as
379 UNDEFINED. This also handles PHI arguments that are the
380 same as lhs. We'll come here again. */
384 arg_value
= arg_val
->value
;
387 arg_value
= valueize_val (arg
);
389 /* Avoid copy propagation from an inner into an outer loop.
390 Otherwise, this may move loop variant variables outside of
391 their loops and prevent coalescing opportunities. If the
392 value was loop invariant, it will be hoisted by LICM and
393 exposed for copy propagation.
394 ??? The value will be always loop invariant.
395 In loop-closed SSA form do not copy-propagate through
396 PHI nodes in blocks with a loop exit edge predecessor. */
398 && TREE_CODE (arg_value
) == SSA_NAME
399 && (loop_depth_of_name (arg_value
) > loop_depth_of_name (lhs
)
400 || (loops_state_satisfies_p (LOOP_CLOSED_SSA
)
401 && loop_exit_edge_p (e
->src
->loop_father
, e
))))
407 /* If the LHS didn't have a value yet, make it a copy of the
408 first argument we find. */
409 if (phi_val
.value
== NULL_TREE
)
411 phi_val
.value
= arg_value
;
415 /* If PHI_VAL and ARG don't have a common copy-of chain, then
416 this PHI node cannot be a copy operation. */
417 if (phi_val
.value
!= arg_value
418 && !operand_equal_p (phi_val
.value
, arg_value
, 0))
426 && may_propagate_copy (lhs
, phi_val
.value
)
427 && set_copy_of_val (lhs
, phi_val
.value
))
428 retval
= (phi_val
.value
!= lhs
) ? SSA_PROP_INTERESTING
: SSA_PROP_VARYING
;
430 retval
= SSA_PROP_NOT_INTERESTING
;
432 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
434 fprintf (dump_file
, "PHI node ");
435 dump_copy_of (dump_file
, lhs
);
436 fprintf (dump_file
, "\nTelling the propagator to ");
437 if (retval
== SSA_PROP_INTERESTING
)
438 fprintf (dump_file
, "add SSA edges out of this PHI and continue.");
439 else if (retval
== SSA_PROP_VARYING
)
440 fprintf (dump_file
, "add SSA edges out of this PHI and never visit again.");
442 fprintf (dump_file
, "do nothing with SSA edges and keep iterating.");
443 fprintf (dump_file
, "\n\n");
450 /* Initialize structures used for copy propagation. */
453 init_copy_prop (void)
457 n_copy_of
= num_ssa_names
;
458 copy_of
= XCNEWVEC (prop_value_t
, n_copy_of
);
460 FOR_EACH_BB_FN (bb
, cfun
)
462 gimple_stmt_iterator si
;
463 int depth
= bb_loop_depth (bb
);
465 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
467 gimple stmt
= gsi_stmt (si
);
471 /* The only statements that we care about are those that may
472 generate useful copies. We also need to mark conditional
473 jumps so that their outgoing edges are added to the work
474 lists of the propagator.
476 Avoid copy propagation from an inner into an outer loop.
477 Otherwise, this may move loop variant variables outside of
478 their loops and prevent coalescing opportunities. If the
479 value was loop invariant, it will be hoisted by LICM and
480 exposed for copy propagation.
481 ??? This doesn't make sense. */
482 if (stmt_ends_bb_p (stmt
))
483 prop_set_simulate_again (stmt
, true);
484 else if (stmt_may_generate_copy (stmt
)
485 /* Since we are iterating over the statements in
486 BB, not the phi nodes, STMT will always be an
488 && loop_depth_of_name (gimple_assign_rhs1 (stmt
)) <= depth
)
489 prop_set_simulate_again (stmt
, true);
491 prop_set_simulate_again (stmt
, false);
493 /* Mark all the outputs of this statement as not being
494 the copy of anything. */
495 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
496 if (!prop_simulate_again_p (stmt
))
497 set_copy_of_val (def
, def
);
500 for (si
= gsi_start_phis (bb
); !gsi_end_p (si
); gsi_next (&si
))
502 gimple phi
= gsi_stmt (si
);
505 def
= gimple_phi_result (phi
);
506 if (virtual_operand_p (def
))
507 prop_set_simulate_again (phi
, false);
509 prop_set_simulate_again (phi
, true);
511 if (!prop_simulate_again_p (phi
))
512 set_copy_of_val (def
, def
);
517 /* Callback for substitute_and_fold to get at the final copy-of values. */
520 get_value (tree name
)
523 if (SSA_NAME_VERSION (name
) >= n_copy_of
)
525 val
= copy_of
[SSA_NAME_VERSION (name
)].value
;
526 if (val
&& val
!= name
)
531 /* Deallocate memory used in copy propagation and do final
535 fini_copy_prop (void)
539 /* Set the final copy-of value for each variable by traversing the
541 for (i
= 1; i
< num_ssa_names
; i
++)
543 tree var
= ssa_name (i
);
546 || copy_of
[i
].value
== var
)
549 /* In theory the points-to solution of all members of the
550 copy chain is their intersection. For now we do not bother
551 to compute this but only make sure we do not lose points-to
552 information completely by setting the points-to solution
553 of the representative to the first solution we find if
554 it doesn't have one already. */
555 if (copy_of
[i
].value
!= var
556 && TREE_CODE (copy_of
[i
].value
) == SSA_NAME
)
558 basic_block copy_of_bb
559 = gimple_bb (SSA_NAME_DEF_STMT (copy_of
[i
].value
));
560 basic_block var_bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
561 if (POINTER_TYPE_P (TREE_TYPE (var
))
562 && SSA_NAME_PTR_INFO (var
)
563 && !SSA_NAME_PTR_INFO (copy_of
[i
].value
))
565 duplicate_ssa_name_ptr_info (copy_of
[i
].value
,
566 SSA_NAME_PTR_INFO (var
));
567 /* Points-to information is cfg insensitive,
568 but alignment info might be cfg sensitive, if it
569 e.g. is derived from VRP derived non-zero bits.
570 So, do not copy alignment info if the two SSA_NAMEs
571 aren't defined in the same basic block. */
572 if (var_bb
!= copy_of_bb
)
573 mark_ptr_info_alignment_unknown
574 (SSA_NAME_PTR_INFO (copy_of
[i
].value
));
576 else if (!POINTER_TYPE_P (TREE_TYPE (var
))
577 && SSA_NAME_RANGE_INFO (var
)
578 && !SSA_NAME_RANGE_INFO (copy_of
[i
].value
)
579 && var_bb
== copy_of_bb
)
580 duplicate_ssa_name_range_info (copy_of
[i
].value
,
581 SSA_NAME_RANGE_TYPE (var
),
582 SSA_NAME_RANGE_INFO (var
));
586 /* Don't do DCE if SCEV is initialized. It would destroy the scev cache. */
587 substitute_and_fold (get_value
, NULL
, !scev_initialized_p ());
593 /* Main entry point to the copy propagator.
595 PHIS_ONLY is true if we should only consider PHI nodes as generating
596 copy propagation opportunities.
598 The algorithm propagates the value COPY-OF using ssa_propagate. For
599 every variable X_i, COPY-OF(X_i) indicates which variable is X_i created
600 from. The following example shows how the algorithm proceeds at a
604 2 a_2 = PHI <a_24, x_1>
606 4 x_1 = PHI <x_298, a_5, a_2>
608 The end result should be that a_2, a_5, a_24 and x_1 are a copy of
609 x_298. Propagation proceeds as follows.
611 Visit #1: a_24 is copy-of x_1. Value changed.
612 Visit #2: a_2 is copy-of x_1. Value changed.
613 Visit #3: a_5 is copy-of x_1. Value changed.
614 Visit #4: x_1 is copy-of x_298. Value changed.
615 Visit #1: a_24 is copy-of x_298. Value changed.
616 Visit #2: a_2 is copy-of x_298. Value changed.
617 Visit #3: a_5 is copy-of x_298. Value changed.
618 Visit #4: x_1 is copy-of x_298. Stable state reached.
620 When visiting PHI nodes, we only consider arguments that flow
621 through edges marked executable by the propagation engine. So,
622 when visiting statement #2 for the first time, we will only look at
623 the first argument (a_24) and optimistically assume that its value
624 is the copy of a_24 (x_1). */
627 execute_copy_prop (void)
630 ssa_propagate (copy_prop_visit_stmt
, copy_prop_visit_phi_node
);
636 gate_copy_prop (void)
638 return flag_tree_copy_prop
!= 0;
643 const pass_data pass_data_copy_prop
=
645 GIMPLE_PASS
, /* type */
646 "copyprop", /* name */
647 OPTGROUP_NONE
, /* optinfo_flags */
649 true, /* has_execute */
650 TV_TREE_COPY_PROP
, /* tv_id */
651 ( PROP_ssa
| PROP_cfg
), /* properties_required */
652 0, /* properties_provided */
653 0, /* properties_destroyed */
654 0, /* todo_flags_start */
655 ( TODO_cleanup_cfg
| TODO_verify_ssa
656 | TODO_update_ssa
), /* todo_flags_finish */
659 class pass_copy_prop
: public gimple_opt_pass
662 pass_copy_prop (gcc::context
*ctxt
)
663 : gimple_opt_pass (pass_data_copy_prop
, ctxt
)
666 /* opt_pass methods: */
667 opt_pass
* clone () { return new pass_copy_prop (m_ctxt
); }
668 bool gate () { return gate_copy_prop (); }
669 unsigned int execute () { return execute_copy_prop (); }
671 }; // class pass_copy_prop
676 make_pass_copy_prop (gcc::context
*ctxt
)
678 return new pass_copy_prop (ctxt
);