Branch data Line data Source code
1 : : /* Copy propagation and SSA_NAME replacement support routines.
2 : : Copyright (C) 2004-2024 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 : : #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 : :
67 : : struct prop_value_t {
68 : : /* Copy-of value. */
69 : : tree value;
70 : : };
71 : :
72 : 2193106 : class 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 : :
79 : : static prop_value_t *copy_of;
80 : : static unsigned n_copy_of;
81 : :
82 : :
83 : : /* Return true if this statement may generate a useful copy. */
84 : :
85 : : static bool
86 : 166239595 : stmt_may_generate_copy (gimple *stmt)
87 : : {
88 : 166239595 : if (gimple_code (stmt) == GIMPLE_PHI)
89 : 250 : return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt));
90 : :
91 : 166239345 : if (gimple_code (stmt) != GIMPLE_ASSIGN)
92 : : return false;
93 : :
94 : : /* If the statement has volatile operands, it won't generate a
95 : : useful copy. */
96 : 55026596 : if (gimple_has_volatile_ops (stmt))
97 : : return false;
98 : :
99 : : /* Statements with loads and/or stores will never generate a useful copy. */
100 : 50445474 : if (gimple_vuse (stmt))
101 : : return false;
102 : :
103 : : /* If the assignment is from a constant it generates a useful copy. */
104 : 21394709 : if (gimple_assign_single_p (stmt)
105 : 21394709 : && is_gimple_min_invariant (gimple_assign_rhs1 (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 : 21055323 : tree rhs = single_ssa_tree_operand (stmt, SSA_OP_USE);
112 : 36411203 : return (rhs && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs));
113 : : }
114 : :
115 : :
116 : : /* Return the copy-of value for VAR. */
117 : :
118 : : static inline prop_value_t *
119 : 46911741 : get_copy_of_val (tree var)
120 : : {
121 : 46911741 : prop_value_t *val = ©_of[SSA_NAME_VERSION (var)];
122 : :
123 : 46911741 : if (val->value == NULL_TREE
124 : 46911741 : && !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 : 1063925 : val->value = var;
129 : : }
130 : :
131 : 46911741 : 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
138 : 51841715 : valueize_val (tree var)
139 : : {
140 : 51841715 : if (TREE_CODE (var) == SSA_NAME)
141 : : {
142 : 36430955 : tree val = get_copy_of_val (var)->value;
143 : 36430955 : 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
152 : 91180167 : set_copy_of_val (tree var, tree val)
153 : : {
154 : 91180167 : unsigned int ver = SSA_NAME_VERSION (var);
155 : 91180167 : tree old;
156 : :
157 : : /* Set FIRST to be the first link in COPY_OF[DEST]. If that
158 : : changed, return true. */
159 : 91180167 : old = copy_of[ver].value;
160 : 91180167 : copy_of[ver].value = val;
161 : :
162 : 91180167 : if (old != val
163 : 91180167 : && (!old || !operand_equal_p (old, val, 0)))
164 : 88930545 : return true;
165 : :
166 : : return false;
167 : : }
168 : :
169 : :
170 : : /* Dump the copy-of value for variable VAR to FILE. */
171 : :
172 : : static void
173 : 0 : dump_copy_of (FILE *file, tree var)
174 : : {
175 : 0 : tree val;
176 : :
177 : 0 : print_generic_expr (file, var, dump_flags);
178 : 0 : if (TREE_CODE (var) != SSA_NAME)
179 : : return;
180 : :
181 : 0 : val = copy_of[SSA_NAME_VERSION (var)].value;
182 : 0 : fprintf (file, " copy-of chain: ");
183 : 0 : print_generic_expr (file, var);
184 : 0 : fprintf (file, " ");
185 : 0 : if (!val)
186 : 0 : fprintf (file, "[UNDEFINED]");
187 : 0 : else if (val == var)
188 : 0 : fprintf (file, "[NOT A COPY]");
189 : : else
190 : : {
191 : 0 : fprintf (file, "-> ");
192 : 0 : print_generic_expr (file, val);
193 : 0 : fprintf (file, " ");
194 : 0 : 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
203 : 20581429 : copy_prop_visit_assignment (gimple *stmt, tree *result_p)
204 : : {
205 : 20581429 : tree lhs = gimple_assign_lhs (stmt);
206 : 20581429 : tree rhs = gimple_fold_stmt_to_constant_1 (stmt, valueize_val);
207 : 20581429 : if (rhs
208 : 20581429 : && (TREE_CODE (rhs) == SSA_NAME
209 : 4714591 : || 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 : 5153729 : if (!may_propagate_copy (lhs, rhs))
214 : 15428438 : rhs = lhs;
215 : : }
216 : : else
217 : : rhs = lhs;
218 : :
219 : 20581429 : *result_p = lhs;
220 : 20581429 : if (set_copy_of_val (*result_p, rhs))
221 : : return SSA_PROP_INTERESTING;
222 : 1104204 : 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 : :
230 : : static enum ssa_prop_result
231 : 11057048 : copy_prop_visit_cond_stmt (gimple *stmt, edge *taken_edge_p)
232 : : {
233 : 11057048 : enum ssa_prop_result retval = SSA_PROP_VARYING;
234 : 11057048 : location_t loc = gimple_location (stmt);
235 : :
236 : 11057048 : tree op0 = valueize_val (gimple_cond_lhs (stmt));
237 : 11057048 : tree op1 = valueize_val (gimple_cond_rhs (stmt));
238 : :
239 : : /* See if we can determine the predicate's value. */
240 : 11057048 : if (dump_file && (dump_flags & TDF_DETAILS))
241 : : {
242 : 0 : fprintf (dump_file, "Trying to determine truth value of ");
243 : 0 : fprintf (dump_file, "predicate ");
244 : 0 : print_gimple_stmt (dump_file, stmt, 0);
245 : : }
246 : :
247 : : /* Fold COND and see whether we get a useful result. */
248 : 11057048 : tree folded_cond = fold_binary_loc (loc, gimple_cond_code (stmt),
249 : : boolean_type_node, op0, op1);
250 : 11057048 : if (folded_cond)
251 : : {
252 : 2081835 : basic_block bb = gimple_bb (stmt);
253 : 2081835 : *taken_edge_p = find_taken_edge (bb, folded_cond);
254 : 2081835 : if (*taken_edge_p)
255 : 11057048 : retval = SSA_PROP_INTERESTING;
256 : : }
257 : :
258 : 11057048 : if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p)
259 : 0 : fprintf (dump_file, "\nConditional will always take edge %d->%d\n",
260 : 0 : (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index);
261 : :
262 : 11057048 : 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 : :
276 : : enum ssa_prop_result
277 : 37650180 : copy_prop::visit_stmt (gimple *stmt, edge *taken_edge_p, tree *result_p)
278 : : {
279 : 37650180 : enum ssa_prop_result retval;
280 : :
281 : 37650180 : if (dump_file && (dump_flags & TDF_DETAILS))
282 : : {
283 : 0 : fprintf (dump_file, "\nVisiting statement:\n");
284 : 0 : print_gimple_stmt (dump_file, stmt, 0, dump_flags);
285 : 0 : fprintf (dump_file, "\n");
286 : : }
287 : :
288 : 37650180 : if (is_gimple_assign (stmt)
289 : 37650180 : && 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 : 20581429 : retval = copy_prop_visit_assignment (stmt, result_p);
294 : : }
295 : 17068751 : else if (gimple_code (stmt) == GIMPLE_COND)
296 : : {
297 : : /* See if we can determine which edge goes out of a conditional
298 : : jump. */
299 : 11057048 : retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p);
300 : : }
301 : : else
302 : : retval = SSA_PROP_VARYING;
303 : :
304 : 31638477 : if (retval == SSA_PROP_VARYING)
305 : : {
306 : 17206579 : tree def;
307 : 17206579 : ssa_op_iter i;
308 : :
309 : : /* Any other kind of statement is not interesting for constant
310 : : propagation and, therefore, not worth simulating. */
311 : 17206579 : if (dump_file && (dump_flags & TDF_DETAILS))
312 : 0 : fprintf (dump_file, "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 : 21876440 : FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS)
318 : 4669861 : set_copy_of_val (def, def);
319 : : }
320 : :
321 : 37650180 : 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 : :
328 : : enum ssa_prop_result
329 : 9945244 : copy_prop::visit_phi (gphi *phi)
330 : : {
331 : 9945244 : enum ssa_prop_result retval;
332 : 9945244 : unsigned i;
333 : 9945244 : prop_value_t phi_val = { NULL_TREE };
334 : :
335 : 9945244 : tree lhs = gimple_phi_result (phi);
336 : :
337 : 9945244 : if (dump_file && (dump_flags & TDF_DETAILS))
338 : : {
339 : 0 : fprintf (dump_file, "\nVisiting PHI node: ");
340 : 0 : print_gimple_stmt (dump_file, phi, 0, dump_flags);
341 : : }
342 : :
343 : 23051468 : for (i = 0; i < gimple_phi_num_args (phi); i++)
344 : : {
345 : 18996231 : prop_value_t *arg_val;
346 : 18996231 : tree arg_value;
347 : 18996231 : tree arg = gimple_phi_arg_def (phi, i);
348 : 18996231 : edge e = gimple_phi_arg_edge (phi, i);
349 : :
350 : : /* We don't care about values flowing through non-executable
351 : : edges. */
352 : 18996231 : if (!(e->flags & EDGE_EXECUTABLE))
353 : 3097037 : continue;
354 : :
355 : : /* Names that flow through abnormal edges cannot be used to
356 : : derive copies. */
357 : 15899194 : if (TREE_CODE (arg) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
358 : : {
359 : : phi_val.value = lhs;
360 : : break;
361 : : }
362 : :
363 : 15893827 : if (dump_file && (dump_flags & TDF_DETAILS))
364 : : {
365 : 0 : fprintf (dump_file, "\tArgument #%d: ", i);
366 : 0 : dump_copy_of (dump_file, arg);
367 : 0 : fprintf (dump_file, "\n");
368 : : }
369 : :
370 : 15893827 : if (TREE_CODE (arg) == SSA_NAME)
371 : : {
372 : 10480786 : arg_val = get_copy_of_val (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 : 10480786 : if (!arg_val->value)
378 : 0 : continue;
379 : :
380 : : arg_value = arg_val->value;
381 : : }
382 : : else
383 : 5413041 : arg_value = valueize_val (arg);
384 : :
385 : : /* In loop-closed SSA form do not copy-propagate SSA-names across
386 : : loop exit edges. */
387 : 15893827 : if (loops_state_satisfies_p (LOOP_CLOSED_SSA)
388 : 5970712 : && TREE_CODE (arg_value) == SSA_NAME
389 : 18946312 : && 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 : 15366695 : if (phi_val.value == NULL_TREE)
398 : : {
399 : 9421364 : phi_val.value = arg_value;
400 : 9421364 : 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 : 5945331 : if (phi_val.value != arg_value
406 : 5945331 : && !operand_equal_p (phi_val.value, arg_value, 0))
407 : : {
408 : : phi_val.value = lhs;
409 : : break;
410 : : }
411 : : }
412 : :
413 : 9945244 : if (phi_val.value
414 : 9945244 : && may_propagate_copy (lhs, phi_val.value)
415 : 19883392 : && set_copy_of_val (lhs, phi_val.value))
416 : 9881001 : retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
417 : : else
418 : : retval = SSA_PROP_NOT_INTERESTING;
419 : :
420 : 9945244 : if (dump_file && (dump_flags & TDF_DETAILS))
421 : : {
422 : 0 : fprintf (dump_file, "PHI node ");
423 : 0 : dump_copy_of (dump_file, lhs);
424 : 0 : fprintf (dump_file, "\nTelling the propagator to ");
425 : 0 : if (retval == SSA_PROP_INTERESTING)
426 : 0 : fprintf (dump_file, "add SSA edges out of this PHI and continue.");
427 : 0 : else if (retval == SSA_PROP_VARYING)
428 : 0 : fprintf (dump_file, "add SSA edges out of this PHI and never visit again.");
429 : : else
430 : 0 : fprintf (dump_file, "do nothing with SSA edges and keep iterating.");
431 : 0 : fprintf (dump_file, "\n\n");
432 : : }
433 : :
434 : 9945244 : return retval;
435 : : }
436 : :
437 : :
438 : : /* Initialize structures used for copy propagation. */
439 : :
440 : : static void
441 : 2193106 : init_copy_prop (void)
442 : : {
443 : 2193106 : basic_block bb;
444 : :
445 : 2193106 : n_copy_of = num_ssa_names;
446 : 2193106 : copy_of = XCNEWVEC (prop_value_t, n_copy_of);
447 : :
448 : 27240069 : FOR_EACH_BB_FN (bb, cfun)
449 : : {
450 : 231586137 : for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
451 : 181492211 : gsi_next (&si))
452 : : {
453 : 181492211 : gimple *stmt = gsi_stmt (si);
454 : 181492211 : ssa_op_iter iter;
455 : 181492211 : 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 : 181492211 : if (stmt_ends_bb_p (stmt))
462 : 16316541 : prop_set_simulate_again (stmt, true);
463 : 165175670 : else if (stmt_may_generate_copy (stmt))
464 : 15693029 : prop_set_simulate_again (stmt, true);
465 : : else
466 : 149482641 : prop_set_simulate_again (stmt, false);
467 : :
468 : : /* Mark all the outputs of this statement as not being
469 : : the copy of anything. */
470 : 251907736 : FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
471 : 70415525 : if (!prop_simulate_again_p (stmt))
472 : 50947558 : set_copy_of_val (def, def);
473 : : }
474 : :
475 : 36749826 : for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
476 : 11702863 : gsi_next (&si))
477 : : {
478 : 11702863 : gphi *phi = si.phi ();
479 : 11702863 : tree def;
480 : :
481 : 11702863 : def = gimple_phi_result (phi);
482 : 23405726 : if (virtual_operand_p (def))
483 : 5043171 : prop_set_simulate_again (phi, false);
484 : : else
485 : 6659692 : prop_set_simulate_again (phi, true);
486 : :
487 : 11702863 : if (!prop_simulate_again_p (phi))
488 : 5043171 : set_copy_of_val (def, def);
489 : : }
490 : : }
491 : 2193106 : }
492 : :
493 : 8772424 : class 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 : :
501 : : tree
502 : 152280236 : copy_folder::value_of_expr (tree name, gimple *)
503 : : {
504 : 152280236 : tree val;
505 : 152280236 : if (SSA_NAME_VERSION (name) >= n_copy_of)
506 : : return NULL_TREE;
507 : 152280236 : val = copy_of[SSA_NAME_VERSION (name)].value;
508 : 152280236 : if (val && val != name)
509 : 3466365 : return val;
510 : : return NULL_TREE;
511 : : }
512 : :
513 : : /* Deallocate memory used in copy propagation and do final
514 : : substitution. */
515 : :
516 : : static bool
517 : 2193106 : fini_copy_prop (void)
518 : : {
519 : 2193106 : unsigned i;
520 : 2193106 : tree var;
521 : :
522 : : /* Set the final copy-of value for each variable by traversing the
523 : : copy-of chains. */
524 : 115345674 : FOR_EACH_SSA_NAME (i, var, cfun)
525 : : {
526 : 88702980 : if (!copy_of[i].value
527 : 83176206 : || copy_of[i].value == var)
528 : 86387975 : 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 : 2315005 : if (copy_of[i].value != var
537 : 2315005 : && TREE_CODE (copy_of[i].value) == SSA_NAME)
538 : : {
539 : 1809502 : basic_block copy_of_bb
540 : 1809502 : = gimple_bb (SSA_NAME_DEF_STMT (copy_of[i].value));
541 : 1809502 : basic_block var_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
542 : 2785095 : if (POINTER_TYPE_P (TREE_TYPE (var))
543 : 836596 : && SSA_NAME_PTR_INFO (var)
544 : 2390385 : && !SSA_NAME_PTR_INFO (copy_of[i].value))
545 : : {
546 : 319561 : duplicate_ssa_name_ptr_info (copy_of[i].value,
547 : 319561 : 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 : 319561 : if (var_bb != copy_of_bb)
554 : 39543 : reset_flow_sensitive_info (copy_of[i].value);
555 : : }
556 : 2464525 : else if (!POINTER_TYPE_P (TREE_TYPE (var))
557 : 972906 : && SSA_NAME_RANGE_INFO (var)
558 : 210019 : && !SSA_NAME_RANGE_INFO (copy_of[i].value)
559 : 1539725 : && var_bb == copy_of_bb)
560 : 634 : duplicate_ssa_name_range_info (copy_of[i].value, var);
561 : : }
562 : : }
563 : :
564 : 2193106 : class copy_folder copy_folder;
565 : 2193106 : bool changed = copy_folder.substitute_and_fold ();
566 : 2193106 : if (changed)
567 : : {
568 : 129060 : free_numbers_of_iterations_estimates (cfun);
569 : 129060 : if (scev_initialized_p ())
570 : 7325 : scev_reset ();
571 : : }
572 : :
573 : 2193106 : free (copy_of);
574 : :
575 : 2193106 : return changed;
576 : 2193106 : }
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 : :
612 : : static unsigned int
613 : 2193106 : execute_copy_prop (void)
614 : : {
615 : 2193106 : init_copy_prop ();
616 : 2193106 : class copy_prop copy_prop;
617 : 2193106 : copy_prop.ssa_propagate ();
618 : 2193106 : if (fini_copy_prop ())
619 : 129060 : return TODO_cleanup_cfg;
620 : : return 0;
621 : 2193106 : }
622 : :
623 : : namespace {
624 : :
625 : : const pass_data pass_data_copy_prop =
626 : : {
627 : : GIMPLE_PASS, /* type */
628 : : "copyprop", /* name */
629 : : OPTGROUP_NONE, /* optinfo_flags */
630 : : TV_TREE_COPY_PROP, /* tv_id */
631 : : ( PROP_ssa | PROP_cfg ), /* properties_required */
632 : : 0, /* properties_provided */
633 : : 0, /* properties_destroyed */
634 : : 0, /* todo_flags_start */
635 : : 0, /* todo_flags_finish */
636 : : };
637 : :
638 : : class pass_copy_prop : public gimple_opt_pass
639 : : {
640 : : public:
641 : 1409570 : pass_copy_prop (gcc::context *ctxt)
642 : 2819140 : : gimple_opt_pass (pass_data_copy_prop, ctxt)
643 : : {}
644 : :
645 : : /* opt_pass methods: */
646 : 1127656 : opt_pass * clone () final override { return new pass_copy_prop (m_ctxt); }
647 : 2193584 : bool gate (function *) final override { return flag_tree_copy_prop != 0; }
648 : 2193106 : unsigned int execute (function *) final override
649 : : {
650 : 2193106 : return execute_copy_prop ();
651 : : }
652 : :
653 : : }; // class pass_copy_prop
654 : :
655 : : } // anon namespace
656 : :
657 : : gimple_opt_pass *
658 : 281914 : make_pass_copy_prop (gcc::context *ctxt)
659 : : {
660 : 281914 : return new pass_copy_prop (ctxt);
661 : : }
|
