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

source code of gcc/tree-ssa-copy.cc