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