re PR target/65697 (__atomic memory barriers not strong enough for __sync builtins)
[gcc.git] / gcc / tree-ssa-copy.c
1 /* Copy propagation and SSA_NAME replacement support routines.
2 Copyright (C) 2004-2015 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 "alias.h"
25 #include "symtab.h"
26 #include "tree.h"
27 #include "fold-const.h"
28 #include "flags.h"
29 #include "tm_p.h"
30 #include "predict.h"
31 #include "hard-reg-set.h"
32 #include "function.h"
33 #include "dominance.h"
34 #include "cfg.h"
35 #include "basic-block.h"
36 #include "gimple-pretty-print.h"
37 #include "tree-ssa-alias.h"
38 #include "internal-fn.h"
39 #include "gimple-expr.h"
40 #include "gimple.h"
41 #include "gimple-iterator.h"
42 #include "gimple-ssa.h"
43 #include "tree-cfg.h"
44 #include "tree-phinodes.h"
45 #include "ssa-iterators.h"
46 #include "stringpool.h"
47 #include "tree-ssanames.h"
48 #include "tree-pass.h"
49 #include "tree-ssa-propagate.h"
50 #include "langhooks.h"
51 #include "cfgloop.h"
52 #include "tree-scalar-evolution.h"
53 #include "tree-ssa-dom.h"
54 #include "tree-ssa-loop-niter.h"
55
56
57 /* This file implements the copy propagation pass and provides a
58 handful of interfaces for performing const/copy propagation and
59 simple expression replacement which keep variable annotations
60 up-to-date.
61
62 We require that for any copy operation where the RHS and LHS have
63 a non-null memory tag the memory tag be the same. It is OK
64 for one or both of the memory tags to be NULL.
65
66 We also require tracking if a variable is dereferenced in a load or
67 store operation.
68
69 We enforce these requirements by having all copy propagation and
70 replacements of one SSA_NAME with a different SSA_NAME to use the
71 APIs defined in this file. */
72
73 /*---------------------------------------------------------------------------
74 Copy propagation
75 ---------------------------------------------------------------------------*/
76 /* Lattice for copy-propagation. The lattice is initialized to
77 UNDEFINED (value == NULL) for SSA names that can become a copy
78 of something or VARYING (value == self) if not (see get_copy_of_val
79 and stmt_may_generate_copy). Other values make the name a COPY
80 of that value.
81
82 When visiting a statement or PHI node the lattice value for an
83 SSA name can transition from UNDEFINED to COPY to VARYING. */
84
85 struct prop_value_t {
86 /* Copy-of value. */
87 tree value;
88 };
89
90 static prop_value_t *copy_of;
91 static unsigned n_copy_of;
92
93
94 /* Return true if this statement may generate a useful copy. */
95
96 static bool
97 stmt_may_generate_copy (gimple stmt)
98 {
99 if (gimple_code (stmt) == GIMPLE_PHI)
100 return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt));
101
102 if (gimple_code (stmt) != GIMPLE_ASSIGN)
103 return false;
104
105 /* If the statement has volatile operands, it won't generate a
106 useful copy. */
107 if (gimple_has_volatile_ops (stmt))
108 return false;
109
110 /* Statements with loads and/or stores will never generate a useful copy. */
111 if (gimple_vuse (stmt))
112 return false;
113
114 /* Otherwise, the only statements that generate useful copies are
115 assignments whose RHS is just an SSA name that doesn't flow
116 through abnormal edges. */
117 return ((gimple_assign_rhs_code (stmt) == SSA_NAME
118 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
119 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)));
120 }
121
122
123 /* Return the copy-of value for VAR. */
124
125 static inline prop_value_t *
126 get_copy_of_val (tree var)
127 {
128 prop_value_t *val = &copy_of[SSA_NAME_VERSION (var)];
129
130 if (val->value == NULL_TREE
131 && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var)))
132 {
133 /* If the variable will never generate a useful copy relation,
134 make it its own copy. */
135 val->value = var;
136 }
137
138 return val;
139 }
140
141 /* Return the variable VAR is a copy of or VAR if VAR isn't the result
142 of a copy. */
143
144 static inline tree
145 valueize_val (tree var)
146 {
147 if (TREE_CODE (var) == SSA_NAME)
148 {
149 tree val = get_copy_of_val (var)->value;
150 if (val)
151 return val;
152 }
153 return var;
154 }
155
156 /* Set VAL to be the copy of VAR. If that changed return true. */
157
158 static inline bool
159 set_copy_of_val (tree var, tree val)
160 {
161 unsigned int ver = SSA_NAME_VERSION (var);
162 tree old;
163
164 /* Set FIRST to be the first link in COPY_OF[DEST]. If that
165 changed, return true. */
166 old = copy_of[ver].value;
167 copy_of[ver].value = val;
168
169 if (old != val
170 || (val && !operand_equal_p (old, val, 0)))
171 return true;
172
173 return false;
174 }
175
176
177 /* Dump the copy-of value for variable VAR to FILE. */
178
179 static void
180 dump_copy_of (FILE *file, tree var)
181 {
182 tree val;
183
184 print_generic_expr (file, var, dump_flags);
185 if (TREE_CODE (var) != SSA_NAME)
186 return;
187
188 val = copy_of[SSA_NAME_VERSION (var)].value;
189 fprintf (file, " copy-of chain: ");
190 print_generic_expr (file, var, 0);
191 fprintf (file, " ");
192 if (!val)
193 fprintf (file, "[UNDEFINED]");
194 else if (val == var)
195 fprintf (file, "[NOT A COPY]");
196 else
197 {
198 fprintf (file, "-> ");
199 print_generic_expr (file, val, 0);
200 fprintf (file, " ");
201 fprintf (file, "[COPY]");
202 }
203 }
204
205
206 /* Evaluate the RHS of STMT. If it produces a valid copy, set the LHS
207 value and store the LHS into *RESULT_P. */
208
209 static enum ssa_prop_result
210 copy_prop_visit_assignment (gimple stmt, tree *result_p)
211 {
212 tree lhs, rhs;
213
214 lhs = gimple_assign_lhs (stmt);
215 rhs = valueize_val (gimple_assign_rhs1 (stmt));
216
217 if (TREE_CODE (lhs) == SSA_NAME)
218 {
219 /* Straight copy between two SSA names. First, make sure that
220 we can propagate the RHS into uses of LHS. */
221 if (!may_propagate_copy (lhs, rhs))
222 return SSA_PROP_VARYING;
223
224 *result_p = lhs;
225 if (set_copy_of_val (*result_p, rhs))
226 return SSA_PROP_INTERESTING;
227 else
228 return SSA_PROP_NOT_INTERESTING;
229 }
230
231 return SSA_PROP_VARYING;
232 }
233
234
235 /* Visit the GIMPLE_COND STMT. Return SSA_PROP_INTERESTING
236 if it can determine which edge will be taken. Otherwise, return
237 SSA_PROP_VARYING. */
238
239 static enum ssa_prop_result
240 copy_prop_visit_cond_stmt (gimple stmt, edge *taken_edge_p)
241 {
242 enum ssa_prop_result retval = SSA_PROP_VARYING;
243 location_t loc = gimple_location (stmt);
244
245 tree op0 = valueize_val (gimple_cond_lhs (stmt));
246 tree op1 = valueize_val (gimple_cond_rhs (stmt));
247
248 /* See if we can determine the predicate's value. */
249 if (dump_file && (dump_flags & TDF_DETAILS))
250 {
251 fprintf (dump_file, "Trying to determine truth value of ");
252 fprintf (dump_file, "predicate ");
253 print_gimple_stmt (dump_file, stmt, 0, 0);
254 }
255
256 /* Fold COND and see whether we get a useful result. */
257 tree folded_cond = fold_binary_loc (loc, gimple_cond_code (stmt),
258 boolean_type_node, op0, op1);
259 if (folded_cond)
260 {
261 basic_block bb = gimple_bb (stmt);
262 *taken_edge_p = find_taken_edge (bb, folded_cond);
263 if (*taken_edge_p)
264 retval = SSA_PROP_INTERESTING;
265 }
266
267 if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p)
268 fprintf (dump_file, "\nConditional will always take edge %d->%d\n",
269 (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index);
270
271 return retval;
272 }
273
274
275 /* Evaluate statement STMT. If the statement produces a new output
276 value, return SSA_PROP_INTERESTING and store the SSA_NAME holding
277 the new value in *RESULT_P.
278
279 If STMT is a conditional branch and we can determine its truth
280 value, set *TAKEN_EDGE_P accordingly.
281
282 If the new value produced by STMT is varying, return
283 SSA_PROP_VARYING. */
284
285 static enum ssa_prop_result
286 copy_prop_visit_stmt (gimple stmt, edge *taken_edge_p, tree *result_p)
287 {
288 enum ssa_prop_result retval;
289
290 if (dump_file && (dump_flags & TDF_DETAILS))
291 {
292 fprintf (dump_file, "\nVisiting statement:\n");
293 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
294 fprintf (dump_file, "\n");
295 }
296
297 if (gimple_assign_single_p (stmt)
298 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
299 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
300 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
301 {
302 /* If the statement is a copy assignment, evaluate its RHS to
303 see if the lattice value of its output has changed. */
304 retval = copy_prop_visit_assignment (stmt, result_p);
305 }
306 else if (gimple_code (stmt) == GIMPLE_COND)
307 {
308 /* See if we can determine which edge goes out of a conditional
309 jump. */
310 retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p);
311 }
312 else
313 retval = SSA_PROP_VARYING;
314
315 if (retval == SSA_PROP_VARYING)
316 {
317 tree def;
318 ssa_op_iter i;
319
320 /* Any other kind of statement is not interesting for constant
321 propagation and, therefore, not worth simulating. */
322 if (dump_file && (dump_flags & TDF_DETAILS))
323 fprintf (dump_file, "No interesting values produced.\n");
324
325 /* The assignment is not a copy operation. Don't visit this
326 statement again and mark all the definitions in the statement
327 to be copies of nothing. */
328 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS)
329 set_copy_of_val (def, def);
330 }
331
332 return retval;
333 }
334
335
336 /* Visit PHI node PHI. If all the arguments produce the same value,
337 set it to be the value of the LHS of PHI. */
338
339 static enum ssa_prop_result
340 copy_prop_visit_phi_node (gphi *phi)
341 {
342 enum ssa_prop_result retval;
343 unsigned i;
344 prop_value_t phi_val = { NULL_TREE };
345
346 tree lhs = gimple_phi_result (phi);
347
348 if (dump_file && (dump_flags & TDF_DETAILS))
349 {
350 fprintf (dump_file, "\nVisiting PHI node: ");
351 print_gimple_stmt (dump_file, phi, 0, dump_flags);
352 }
353
354 for (i = 0; i < gimple_phi_num_args (phi); i++)
355 {
356 prop_value_t *arg_val;
357 tree arg_value;
358 tree arg = gimple_phi_arg_def (phi, i);
359 edge e = gimple_phi_arg_edge (phi, i);
360
361 /* We don't care about values flowing through non-executable
362 edges. */
363 if (!(e->flags & EDGE_EXECUTABLE))
364 continue;
365
366 /* Names that flow through abnormal edges cannot be used to
367 derive copies. */
368 if (TREE_CODE (arg) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
369 {
370 phi_val.value = lhs;
371 break;
372 }
373
374 if (dump_file && (dump_flags & TDF_DETAILS))
375 {
376 fprintf (dump_file, "\tArgument #%d: ", i);
377 dump_copy_of (dump_file, arg);
378 fprintf (dump_file, "\n");
379 }
380
381 if (TREE_CODE (arg) == SSA_NAME)
382 {
383 arg_val = get_copy_of_val (arg);
384
385 /* If we didn't visit the definition of arg yet treat it as
386 UNDEFINED. This also handles PHI arguments that are the
387 same as lhs. We'll come here again. */
388 if (!arg_val->value)
389 continue;
390
391 arg_value = arg_val->value;
392 }
393 else
394 arg_value = valueize_val (arg);
395
396 /* In loop-closed SSA form do not copy-propagate SSA-names across
397 loop exit edges. */
398 if (loops_state_satisfies_p (LOOP_CLOSED_SSA)
399 && TREE_CODE (arg_value) == SSA_NAME
400 && loop_exit_edge_p (e->src->loop_father, e))
401 {
402 phi_val.value = lhs;
403 break;
404 }
405
406 /* If the LHS didn't have a value yet, make it a copy of the
407 first argument we find. */
408 if (phi_val.value == NULL_TREE)
409 {
410 phi_val.value = arg_value;
411 continue;
412 }
413
414 /* If PHI_VAL and ARG don't have a common copy-of chain, then
415 this PHI node cannot be a copy operation. */
416 if (phi_val.value != arg_value
417 && !operand_equal_p (phi_val.value, arg_value, 0))
418 {
419 phi_val.value = lhs;
420 break;
421 }
422 }
423
424 if (phi_val.value
425 && may_propagate_copy (lhs, phi_val.value)
426 && set_copy_of_val (lhs, phi_val.value))
427 retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
428 else
429 retval = SSA_PROP_NOT_INTERESTING;
430
431 if (dump_file && (dump_flags & TDF_DETAILS))
432 {
433 fprintf (dump_file, "PHI node ");
434 dump_copy_of (dump_file, lhs);
435 fprintf (dump_file, "\nTelling the propagator to ");
436 if (retval == SSA_PROP_INTERESTING)
437 fprintf (dump_file, "add SSA edges out of this PHI and continue.");
438 else if (retval == SSA_PROP_VARYING)
439 fprintf (dump_file, "add SSA edges out of this PHI and never visit again.");
440 else
441 fprintf (dump_file, "do nothing with SSA edges and keep iterating.");
442 fprintf (dump_file, "\n\n");
443 }
444
445 return retval;
446 }
447
448
449 /* Initialize structures used for copy propagation. */
450
451 static void
452 init_copy_prop (void)
453 {
454 basic_block bb;
455
456 n_copy_of = num_ssa_names;
457 copy_of = XCNEWVEC (prop_value_t, n_copy_of);
458
459 FOR_EACH_BB_FN (bb, cfun)
460 {
461 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
462 gsi_next (&si))
463 {
464 gimple stmt = gsi_stmt (si);
465 ssa_op_iter iter;
466 tree def;
467
468 /* The only statements that we care about are those that may
469 generate useful copies. We also need to mark conditional
470 jumps so that their outgoing edges are added to the work
471 lists of the propagator. */
472 if (stmt_ends_bb_p (stmt))
473 prop_set_simulate_again (stmt, true);
474 else if (stmt_may_generate_copy (stmt))
475 prop_set_simulate_again (stmt, true);
476 else
477 prop_set_simulate_again (stmt, false);
478
479 /* Mark all the outputs of this statement as not being
480 the copy of anything. */
481 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
482 if (!prop_simulate_again_p (stmt))
483 set_copy_of_val (def, def);
484 }
485
486 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
487 gsi_next (&si))
488 {
489 gphi *phi = si.phi ();
490 tree def;
491
492 def = gimple_phi_result (phi);
493 if (virtual_operand_p (def))
494 prop_set_simulate_again (phi, false);
495 else
496 prop_set_simulate_again (phi, true);
497
498 if (!prop_simulate_again_p (phi))
499 set_copy_of_val (def, def);
500 }
501 }
502 }
503
504 /* Callback for substitute_and_fold to get at the final copy-of values. */
505
506 static tree
507 get_value (tree name)
508 {
509 tree val;
510 if (SSA_NAME_VERSION (name) >= n_copy_of)
511 return NULL_TREE;
512 val = copy_of[SSA_NAME_VERSION (name)].value;
513 if (val && val != name)
514 return val;
515 return NULL_TREE;
516 }
517
518 /* Deallocate memory used in copy propagation and do final
519 substitution. */
520
521 static bool
522 fini_copy_prop (void)
523 {
524 unsigned i;
525
526 /* Set the final copy-of value for each variable by traversing the
527 copy-of chains. */
528 for (i = 1; i < num_ssa_names; i++)
529 {
530 tree var = ssa_name (i);
531 if (!var
532 || !copy_of[i].value
533 || copy_of[i].value == var)
534 continue;
535
536 /* In theory the points-to solution of all members of the
537 copy chain is their intersection. For now we do not bother
538 to compute this but only make sure we do not lose points-to
539 information completely by setting the points-to solution
540 of the representative to the first solution we find if
541 it doesn't have one already. */
542 if (copy_of[i].value != var
543 && TREE_CODE (copy_of[i].value) == SSA_NAME)
544 {
545 basic_block copy_of_bb
546 = gimple_bb (SSA_NAME_DEF_STMT (copy_of[i].value));
547 basic_block var_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
548 if (POINTER_TYPE_P (TREE_TYPE (var))
549 && SSA_NAME_PTR_INFO (var)
550 && !SSA_NAME_PTR_INFO (copy_of[i].value))
551 {
552 duplicate_ssa_name_ptr_info (copy_of[i].value,
553 SSA_NAME_PTR_INFO (var));
554 /* Points-to information is cfg insensitive,
555 but alignment info might be cfg sensitive, if it
556 e.g. is derived from VRP derived non-zero bits.
557 So, do not copy alignment info if the two SSA_NAMEs
558 aren't defined in the same basic block. */
559 if (var_bb != copy_of_bb)
560 mark_ptr_info_alignment_unknown
561 (SSA_NAME_PTR_INFO (copy_of[i].value));
562 }
563 else if (!POINTER_TYPE_P (TREE_TYPE (var))
564 && SSA_NAME_RANGE_INFO (var)
565 && !SSA_NAME_RANGE_INFO (copy_of[i].value)
566 && var_bb == copy_of_bb)
567 duplicate_ssa_name_range_info (copy_of[i].value,
568 SSA_NAME_RANGE_TYPE (var),
569 SSA_NAME_RANGE_INFO (var));
570 }
571 }
572
573 bool changed = substitute_and_fold (get_value, NULL, true);
574 if (changed)
575 {
576 free_numbers_of_iterations_estimates ();
577 if (scev_initialized_p ())
578 scev_reset ();
579 }
580
581 free (copy_of);
582
583 return changed;
584 }
585
586
587 /* Main entry point to the copy propagator.
588
589 PHIS_ONLY is true if we should only consider PHI nodes as generating
590 copy propagation opportunities.
591
592 The algorithm propagates the value COPY-OF using ssa_propagate. For
593 every variable X_i, COPY-OF(X_i) indicates which variable is X_i created
594 from. The following example shows how the algorithm proceeds at a
595 high level:
596
597 1 a_24 = x_1
598 2 a_2 = PHI <a_24, x_1>
599 3 a_5 = PHI <a_2>
600 4 x_1 = PHI <x_298, a_5, a_2>
601
602 The end result should be that a_2, a_5, a_24 and x_1 are a copy of
603 x_298. Propagation proceeds as follows.
604
605 Visit #1: a_24 is copy-of x_1. Value changed.
606 Visit #2: a_2 is copy-of x_1. Value changed.
607 Visit #3: a_5 is copy-of x_1. Value changed.
608 Visit #4: x_1 is copy-of x_298. Value changed.
609 Visit #1: a_24 is copy-of x_298. Value changed.
610 Visit #2: a_2 is copy-of x_298. Value changed.
611 Visit #3: a_5 is copy-of x_298. Value changed.
612 Visit #4: x_1 is copy-of x_298. Stable state reached.
613
614 When visiting PHI nodes, we only consider arguments that flow
615 through edges marked executable by the propagation engine. So,
616 when visiting statement #2 for the first time, we will only look at
617 the first argument (a_24) and optimistically assume that its value
618 is the copy of a_24 (x_1). */
619
620 static unsigned int
621 execute_copy_prop (void)
622 {
623 init_copy_prop ();
624 ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node);
625 if (fini_copy_prop ())
626 return TODO_cleanup_cfg;
627 return 0;
628 }
629
630 namespace {
631
632 const pass_data pass_data_copy_prop =
633 {
634 GIMPLE_PASS, /* type */
635 "copyprop", /* name */
636 OPTGROUP_NONE, /* optinfo_flags */
637 TV_TREE_COPY_PROP, /* tv_id */
638 ( PROP_ssa | PROP_cfg ), /* properties_required */
639 0, /* properties_provided */
640 0, /* properties_destroyed */
641 0, /* todo_flags_start */
642 0, /* todo_flags_finish */
643 };
644
645 class pass_copy_prop : public gimple_opt_pass
646 {
647 public:
648 pass_copy_prop (gcc::context *ctxt)
649 : gimple_opt_pass (pass_data_copy_prop, ctxt)
650 {}
651
652 /* opt_pass methods: */
653 opt_pass * clone () { return new pass_copy_prop (m_ctxt); }
654 virtual bool gate (function *) { return flag_tree_copy_prop != 0; }
655 virtual unsigned int execute (function *) { return execute_copy_prop (); }
656
657 }; // class pass_copy_prop
658
659 } // anon namespace
660
661 gimple_opt_pass *
662 make_pass_copy_prop (gcc::context *ctxt)
663 {
664 return new pass_copy_prop (ctxt);
665 }