1 /* Copy propagation and SSA_NAME replacement support routines.
2 Copyright (C) 2004-2014 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
10
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "tree.h"
25 #include "flags.h"
26 #include "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"
48
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.
53
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.
57
58 We also require tracking if a variable is dereferenced in a load or
59 store operation.
60
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. */
64
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.
73
74 When visiting a statement or PHI node the lattice value for an
75 SSA name can transition from UNDEFINED to COPY to VARYING. */
76
77 struct prop_value_d {
78 /* Copy-of value. */
79 tree value;
80 };
81 typedef struct prop_value_d prop_value_t;
82
83 static prop_value_t *copy_of;
84 static unsigned n_copy_of;
85
86
87 /* Return true if this statement may generate a useful copy. */
88
89 static bool
stmt_may_generate_copy(gimple stmt)90 stmt_may_generate_copy (gimple stmt)
91 {
92 if (gimple_code (stmt) == GIMPLE_PHI)
93 return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt));
94
95 if (gimple_code (stmt) != GIMPLE_ASSIGN)
96 return false;
97
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;
102
103 /* Statements with loads and/or stores will never generate a useful copy. */
104 if (gimple_vuse (stmt))
105 return false;
106
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)));
113 }
114
115
116 /* Return the copy-of value for VAR. */
117
118 static inline prop_value_t *
get_copy_of_val(tree var)119 get_copy_of_val (tree var)
120 {
121 prop_value_t *val = ©_of[SSA_NAME_VERSION (var)];
122
123 if (val->value == NULL_TREE
124 && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var)))
125 {
126 /* If the variable will never generate a useful copy relation,
127 make it its own copy. */
128 val->value = var;
129 }
130
131 return val;
132 }
133
134 /* Return the variable VAR is a copy of or VAR if VAR isn't the result
135 of a copy. */
136
137 static inline tree
valueize_val(tree var)138 valueize_val (tree var)
139 {
140 if (TREE_CODE (var) == SSA_NAME)
141 {
142 tree val = get_copy_of_val (var)->value;
143 if (val)
144 return val;
145 }
146 return var;
147 }
148
149 /* Set VAL to be the copy of VAR. If that changed return true. */
150
151 static inline bool
set_copy_of_val(tree var,tree val)152 set_copy_of_val (tree var, tree val)
153 {
154 unsigned int ver = SSA_NAME_VERSION (var);
155 tree old;
156
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;
161
162 if (old != val
163 || (val && !operand_equal_p (old, val, 0)))
164 return true;
165
166 return false;
167 }
168
169
170 /* Dump the copy-of value for variable VAR to FILE. */
171
172 static void
dump_copy_of(FILE * file,tree var)173 dump_copy_of (FILE *file, tree var)
174 {
175 tree val;
176
177 print_generic_expr (file, var, dump_flags);
178 if (TREE_CODE (var) != SSA_NAME)
179 return;
180
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
190 {
191 fprintf (file, "-> ");
192 print_generic_expr (file, val, 0);
193 fprintf (file, " ");
194 fprintf (file, "[COPY]");
195 }
196 }
197
198
199 /* Evaluate the RHS of STMT. If it produces a valid copy, set the LHS
200 value and store the LHS into *RESULT_P. */
201
202 static enum ssa_prop_result
copy_prop_visit_assignment(gimple stmt,tree * result_p)203 copy_prop_visit_assignment (gimple stmt, tree *result_p)
204 {
205 tree lhs, rhs;
206
207 lhs = gimple_assign_lhs (stmt);
208 rhs = valueize_val (gimple_assign_rhs1 (stmt));
209
210 if (TREE_CODE (lhs) == SSA_NAME)
211 {
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;
216
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;
222 }
223
224 return SSA_PROP_VARYING;
225 }
226
227
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. */
231
232 static enum ssa_prop_result
copy_prop_visit_cond_stmt(gimple stmt,edge * taken_edge_p)233 copy_prop_visit_cond_stmt (gimple stmt, edge *taken_edge_p)
234 {
235 enum ssa_prop_result retval = SSA_PROP_VARYING;
236 location_t loc = gimple_location (stmt);
237
238 tree op0 = valueize_val (gimple_cond_lhs (stmt));
239 tree op1 = valueize_val (gimple_cond_rhs (stmt));
240
241 /* See if we can determine the predicate's value. */
242 if (dump_file && (dump_flags & TDF_DETAILS))
243 {
244 fprintf (dump_file, "Trying to determine truth value of ");
245 fprintf (dump_file, "predicate ");
246 print_gimple_stmt (dump_file, stmt, 0, 0);
247 }
248
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);
252 if (folded_cond)
253 {
254 basic_block bb = gimple_bb (stmt);
255 *taken_edge_p = find_taken_edge (bb, folded_cond);
256 if (*taken_edge_p)
257 retval = SSA_PROP_INTERESTING;
258 }
259
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);
263
264 return retval;
265 }
266
267
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.
271
272 If STMT is a conditional branch and we can determine its truth
273 value, set *TAKEN_EDGE_P accordingly.
274
275 If the new value produced by STMT is varying, return
276 SSA_PROP_VARYING. */
277
278 static enum ssa_prop_result
copy_prop_visit_stmt(gimple stmt,edge * taken_edge_p,tree * result_p)279 copy_prop_visit_stmt (gimple stmt, edge *taken_edge_p, tree *result_p)
280 {
281 enum ssa_prop_result retval;
282
283 if (dump_file && (dump_flags & TDF_DETAILS))
284 {
285 fprintf (dump_file, "\nVisiting statement:\n");
286 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
287 fprintf (dump_file, "\n");
288 }
289
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))))
294 {
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);
298 }
299 else if (gimple_code (stmt) == GIMPLE_COND)
300 {
301 /* See if we can determine which edge goes out of a conditional
302 jump. */
303 retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p);
304 }
305 else
306 retval = SSA_PROP_VARYING;
307
308 if (retval == SSA_PROP_VARYING)
309 {
310 tree def;
311 ssa_op_iter i;
312
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");
317
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);
323 }
324
325 return retval;
326 }
327
328
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. */
331
332 static enum ssa_prop_result
copy_prop_visit_phi_node(gimple phi)333 copy_prop_visit_phi_node (gimple phi)
334 {
335 enum ssa_prop_result retval;
336 unsigned i;
337 prop_value_t phi_val = { NULL_TREE };
338
339 tree lhs = gimple_phi_result (phi);
340
341 if (dump_file && (dump_flags & TDF_DETAILS))
342 {
343 fprintf (dump_file, "\nVisiting PHI node: ");
344 print_gimple_stmt (dump_file, phi, 0, dump_flags);
345 }
346
347 for (i = 0; i < gimple_phi_num_args (phi); i++)
348 {
349 prop_value_t *arg_val;
350 tree arg_value;
351 tree arg = gimple_phi_arg_def (phi, i);
352 edge e = gimple_phi_arg_edge (phi, i);
353
354 /* We don't care about values flowing through non-executable
355 edges. */
356 if (!(e->flags & EDGE_EXECUTABLE))
357 continue;
358
359 /* Names that flow through abnormal edges cannot be used to
360 derive copies. */
361 if (TREE_CODE (arg) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
362 {
363 phi_val.value = lhs;
364 break;
365 }
366
367 if (dump_file && (dump_flags & TDF_DETAILS))
368 {
369 fprintf (dump_file, "\tArgument #%d: ", i);
370 dump_copy_of (dump_file, arg);
371 fprintf (dump_file, "\n");
372 }
373
374 if (TREE_CODE (arg) == SSA_NAME)
375 {
376 arg_val = get_copy_of_val (arg);
377
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. */
381 if (!arg_val->value)
382 continue;
383
384 arg_value = arg_val->value;
385 }
386 else
387 arg_value = valueize_val (arg);
388
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. */
397 if (current_loops
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))))
402 {
403 phi_val.value = lhs;
404 break;
405 }
406
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)
410 {
411 phi_val.value = arg_value;
412 continue;
413 }
414
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))
419 {
420 phi_val.value = lhs;
421 break;
422 }
423 }
424
425 if (phi_val.value
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;
429 else
430 retval = SSA_PROP_NOT_INTERESTING;
431
432 if (dump_file && (dump_flags & TDF_DETAILS))
433 {
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.");
441 else
442 fprintf (dump_file, "do nothing with SSA edges and keep iterating.");
443 fprintf (dump_file, "\n\n");
444 }
445
446 return retval;
447 }
448
449
450 /* Initialize structures used for copy propagation. */
451
452 static void
init_copy_prop(void)453 init_copy_prop (void)
454 {
455 basic_block bb;
456
457 n_copy_of = num_ssa_names;
458 copy_of = XCNEWVEC (prop_value_t, n_copy_of);
459
460 FOR_EACH_BB_FN (bb, cfun)
461 {
462 gimple_stmt_iterator si;
463 int depth = bb_loop_depth (bb);
464
465 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
466 {
467 gimple stmt = gsi_stmt (si);
468 ssa_op_iter iter;
469 tree def;
470
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.
475
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
487 assignment. */
488 && loop_depth_of_name (gimple_assign_rhs1 (stmt)) <= depth)
489 prop_set_simulate_again (stmt, true);
490 else
491 prop_set_simulate_again (stmt, false);
492
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);
498 }
499
500 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
501 {
502 gimple phi = gsi_stmt (si);
503 tree def;
504
505 def = gimple_phi_result (phi);
506 if (virtual_operand_p (def))
507 prop_set_simulate_again (phi, false);
508 else
509 prop_set_simulate_again (phi, true);
510
511 if (!prop_simulate_again_p (phi))
512 set_copy_of_val (def, def);
513 }
514 }
515 }
516
517 /* Callback for substitute_and_fold to get at the final copy-of values. */
518
519 static tree
get_value(tree name)520 get_value (tree name)
521 {
522 tree val;
523 if (SSA_NAME_VERSION (name) >= n_copy_of)
524 return NULL_TREE;
525 val = copy_of[SSA_NAME_VERSION (name)].value;
526 if (val && val != name)
527 return val;
528 return NULL_TREE;
529 }
530
531 /* Deallocate memory used in copy propagation and do final
532 substitution. */
533
534 static void
fini_copy_prop(void)535 fini_copy_prop (void)
536 {
537 unsigned i;
538
539 /* Set the final copy-of value for each variable by traversing the
540 copy-of chains. */
541 for (i = 1; i < num_ssa_names; i++)
542 {
543 tree var = ssa_name (i);
544 if (!var
545 || !copy_of[i].value
546 || copy_of[i].value == var)
547 continue;
548
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)
557 {
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))
564 {
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));
575 }
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));
583 }
584 }
585
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 ());
588
589 free (copy_of);
590 }
591
592
593 /* Main entry point to the copy propagator.
594
595 PHIS_ONLY is true if we should only consider PHI nodes as generating
596 copy propagation opportunities.
597
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
601 high level:
602
603 1 a_24 = x_1
604 2 a_2 = PHI <a_24, x_1>
605 3 a_5 = PHI <a_2>
606 4 x_1 = PHI <x_298, a_5, a_2>
607
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.
610
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.
619
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). */
625
626 static unsigned int
execute_copy_prop(void)627 execute_copy_prop (void)
628 {
629 init_copy_prop ();
630 ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node);
631 fini_copy_prop ();
632 return 0;
633 }
634
635 static bool
gate_copy_prop(void)636 gate_copy_prop (void)
637 {
638 return flag_tree_copy_prop != 0;
639 }
640
641 namespace {
642
643 const pass_data pass_data_copy_prop =
644 {
645 GIMPLE_PASS, /* type */
646 "copyprop", /* name */
647 OPTGROUP_NONE, /* optinfo_flags */
648 true, /* has_gate */
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 */
657 };
658
659 class pass_copy_prop : public gimple_opt_pass
660 {
661 public:
pass_copy_prop(gcc::context * ctxt)662 pass_copy_prop (gcc::context *ctxt)
663 : gimple_opt_pass (pass_data_copy_prop, ctxt)
664 {}
665
666 /* opt_pass methods: */
clone()667 opt_pass * clone () { return new pass_copy_prop (m_ctxt); }
gate()668 bool gate () { return gate_copy_prop (); }
execute()669 unsigned int execute () { return execute_copy_prop (); }
670
671 }; // class pass_copy_prop
672
673 } // anon namespace
674
675 gimple_opt_pass *
make_pass_copy_prop(gcc::context * ctxt)676 make_pass_copy_prop (gcc::context *ctxt)
677 {
678 return new pass_copy_prop (ctxt);
679 }
680