* tree-vect-loop-manip.c (vect_do_peeling): Do not use
[official-gcc.git] / gcc / tree-ssa-phionlycprop.c
blobfe39aa71f98b5f846d7826ca0727303a330684ad
1 /* Const/Copy propagation originating from degenerate PHIs
2 Copyright (C) 2001-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "cfghooks.h"
25 #include "tree.h"
26 #include "gimple.h"
27 #include "ssa.h"
28 #include "fold-const.h"
29 #include "cfgloop.h"
30 #include "gimple-pretty-print.h"
31 #include "gimple-fold.h"
32 #include "tree-eh.h"
33 #include "gimple-iterator.h"
34 #include "tree-cfg.h"
35 #include "tree-pass.h"
36 #include "tree-ssa-propagate.h"
39 /* PHI-ONLY copy and constant propagation. This pass is meant to clean
40 up degenerate PHIs created by or exposed by jump threading. */
42 /* Given a statement STMT, which is either a PHI node or an assignment,
43 remove it from the IL. */
45 static void
46 remove_stmt_or_phi (gimple *stmt)
48 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
50 if (gimple_code (stmt) == GIMPLE_PHI)
51 remove_phi_node (&gsi, true);
52 else
54 gsi_remove (&gsi, true);
55 release_defs (stmt);
59 /* Given a statement STMT, which is either a PHI node or an assignment,
60 return the "rhs" of the node, in the case of a non-degenerate
61 phi, NULL is returned. */
63 static tree
64 get_rhs_or_phi_arg (gimple *stmt)
66 if (gimple_code (stmt) == GIMPLE_PHI)
67 return degenerate_phi_result (as_a <gphi *> (stmt));
68 else if (gimple_assign_single_p (stmt))
69 return gimple_assign_rhs1 (stmt);
70 else
71 gcc_unreachable ();
75 /* Given a statement STMT, which is either a PHI node or an assignment,
76 return the "lhs" of the node. */
78 static tree
79 get_lhs_or_phi_result (gimple *stmt)
81 if (gimple_code (stmt) == GIMPLE_PHI)
82 return gimple_phi_result (stmt);
83 else if (is_gimple_assign (stmt))
84 return gimple_assign_lhs (stmt);
85 else
86 gcc_unreachable ();
89 /* Propagate RHS into all uses of LHS (when possible).
91 RHS and LHS are derived from STMT, which is passed in solely so
92 that we can remove it if propagation is successful.
94 When propagating into a PHI node or into a statement which turns
95 into a trivial copy or constant initialization, set the
96 appropriate bit in INTERESTING_NAMEs so that we will visit those
97 nodes as well in an effort to pick up secondary optimization
98 opportunities.
100 NEED_EH_CLEANUP tracks blocks that need their EH information
101 cleaned up after changing EH information on a statement. */
103 static bool
104 propagate_rhs_into_lhs (gimple *stmt, tree lhs, tree rhs,
105 bitmap interesting_names, bitmap need_eh_cleanup)
107 bool cfg_altered = false;
109 /* First verify that propagation is valid. */
110 if (may_propagate_copy (lhs, rhs))
112 use_operand_p use_p;
113 imm_use_iterator iter;
114 gimple *use_stmt;
115 bool all = true;
117 /* Dump details. */
118 if (dump_file && (dump_flags & TDF_DETAILS))
120 fprintf (dump_file, " Replacing '");
121 print_generic_expr (dump_file, lhs, dump_flags);
122 fprintf (dump_file, "' with %s '",
123 (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable"));
124 print_generic_expr (dump_file, rhs, dump_flags);
125 fprintf (dump_file, "'\n");
128 /* Walk over every use of LHS and try to replace the use with RHS.
129 At this point the only reason why such a propagation would not
130 be successful would be if the use occurs in an ASM_EXPR. */
131 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
133 /* Leave debug stmts alone. If we succeed in propagating
134 all non-debug uses, we'll drop the DEF, and propagation
135 into debug stmts will occur then. */
136 if (gimple_debug_bind_p (use_stmt))
137 continue;
139 /* It's not always safe to propagate into an ASM_EXPR. */
140 if (gimple_code (use_stmt) == GIMPLE_ASM
141 && ! may_propagate_copy_into_asm (lhs))
143 all = false;
144 continue;
147 /* It's not ok to propagate into the definition stmt of RHS.
148 <bb 9>:
149 # prephitmp.12_36 = PHI <g_67.1_6(9)>
150 g_67.1_6 = prephitmp.12_36;
151 goto <bb 9>;
152 While this is strictly all dead code we do not want to
153 deal with this here. */
154 if (TREE_CODE (rhs) == SSA_NAME
155 && SSA_NAME_DEF_STMT (rhs) == use_stmt)
157 all = false;
158 continue;
161 /* Dump details. */
162 if (dump_file && (dump_flags & TDF_DETAILS))
164 fprintf (dump_file, " Original statement:");
165 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
168 /* Propagate the RHS into this use of the LHS. */
169 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
170 propagate_value (use_p, rhs);
172 /* Special cases to avoid useless calls into the folding
173 routines, operand scanning, etc.
175 Propagation into a PHI may cause the PHI to become
176 a degenerate, so mark the PHI as interesting. No other
177 actions are necessary. */
178 if (gimple_code (use_stmt) == GIMPLE_PHI)
180 tree result;
182 /* Dump details. */
183 if (dump_file && (dump_flags & TDF_DETAILS))
185 fprintf (dump_file, " Updated statement:");
186 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
189 result = get_lhs_or_phi_result (use_stmt);
190 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
191 continue;
194 /* From this point onward we are propagating into a
195 real statement. Folding may (or may not) be possible,
196 we may expose new operands, expose dead EH edges,
197 etc. */
198 /* NOTE tuples. In the tuples world, fold_stmt_inplace
199 cannot fold a call that simplifies to a constant,
200 because the GIMPLE_CALL must be replaced by a
201 GIMPLE_ASSIGN, and there is no way to effect such a
202 transformation in-place. We might want to consider
203 using the more general fold_stmt here. */
205 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
206 fold_stmt_inplace (&gsi);
209 /* Sometimes propagation can expose new operands to the
210 renamer. */
211 update_stmt (use_stmt);
213 /* Dump details. */
214 if (dump_file && (dump_flags & TDF_DETAILS))
216 fprintf (dump_file, " Updated statement:");
217 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
220 /* If we replaced a variable index with a constant, then
221 we would need to update the invariant flag for ADDR_EXPRs. */
222 if (gimple_assign_single_p (use_stmt)
223 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR)
224 recompute_tree_invariant_for_addr_expr
225 (gimple_assign_rhs1 (use_stmt));
227 /* If we cleaned up EH information from the statement,
228 mark its containing block as needing EH cleanups. */
229 if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt))
231 bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index);
232 if (dump_file && (dump_flags & TDF_DETAILS))
233 fprintf (dump_file, " Flagged to clear EH edges.\n");
236 /* Propagation may expose new trivial copy/constant propagation
237 opportunities. */
238 if (gimple_assign_single_p (use_stmt)
239 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
240 && (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
241 || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))))
243 tree result = get_lhs_or_phi_result (use_stmt);
244 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
247 /* Propagation into these nodes may make certain edges in
248 the CFG unexecutable. We want to identify them as PHI nodes
249 at the destination of those unexecutable edges may become
250 degenerates. */
251 else if (gimple_code (use_stmt) == GIMPLE_COND
252 || gimple_code (use_stmt) == GIMPLE_SWITCH
253 || gimple_code (use_stmt) == GIMPLE_GOTO)
255 tree val;
257 if (gimple_code (use_stmt) == GIMPLE_COND)
258 val = fold_binary_loc (gimple_location (use_stmt),
259 gimple_cond_code (use_stmt),
260 boolean_type_node,
261 gimple_cond_lhs (use_stmt),
262 gimple_cond_rhs (use_stmt));
263 else if (gimple_code (use_stmt) == GIMPLE_SWITCH)
264 val = gimple_switch_index (as_a <gswitch *> (use_stmt));
265 else
266 val = gimple_goto_dest (use_stmt);
268 if (val && is_gimple_min_invariant (val))
270 basic_block bb = gimple_bb (use_stmt);
271 edge te = find_taken_edge (bb, val);
272 if (!te)
273 continue;
275 edge_iterator ei;
276 edge e;
277 gimple_stmt_iterator gsi;
278 gphi_iterator psi;
280 /* Remove all outgoing edges except TE. */
281 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
283 if (e != te)
285 /* Mark all the PHI nodes at the destination of
286 the unexecutable edge as interesting. */
287 for (psi = gsi_start_phis (e->dest);
288 !gsi_end_p (psi);
289 gsi_next (&psi))
291 gphi *phi = psi.phi ();
293 tree result = gimple_phi_result (phi);
294 int version = SSA_NAME_VERSION (result);
296 bitmap_set_bit (interesting_names, version);
299 te->probability += e->probability;
301 remove_edge (e);
302 cfg_altered = true;
304 else
305 ei_next (&ei);
308 gsi = gsi_last_bb (gimple_bb (use_stmt));
309 gsi_remove (&gsi, true);
311 /* And fixup the flags on the single remaining edge. */
312 te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
313 te->flags &= ~EDGE_ABNORMAL;
314 te->flags |= EDGE_FALLTHRU;
319 /* Ensure there is nothing else to do. */
320 gcc_assert (!all || has_zero_uses (lhs));
322 /* If we were able to propagate away all uses of LHS, then
323 we can remove STMT. */
324 if (all)
325 remove_stmt_or_phi (stmt);
327 return cfg_altered;
330 /* STMT is either a PHI node (potentially a degenerate PHI node) or
331 a statement that is a trivial copy or constant initialization.
333 Attempt to eliminate STMT by propagating its RHS into all uses of
334 its LHS. This may in turn set new bits in INTERESTING_NAMES
335 for nodes we want to revisit later.
337 All exit paths should clear INTERESTING_NAMES for the result
338 of STMT.
340 NEED_EH_CLEANUP tracks blocks that need their EH information
341 cleaned up after changing EH information on a statement. It is
342 not set or queried here, but passed along to children. */
344 static bool
345 eliminate_const_or_copy (gimple *stmt, bitmap interesting_names,
346 bitmap need_eh_cleanup)
348 tree lhs = get_lhs_or_phi_result (stmt);
349 tree rhs;
350 int version = SSA_NAME_VERSION (lhs);
351 bool cfg_altered = false;
353 /* If the LHS of this statement or PHI has no uses, then we can
354 just eliminate it. This can occur if, for example, the PHI
355 was created by block duplication due to threading and its only
356 use was in the conditional at the end of the block which was
357 deleted. */
358 if (has_zero_uses (lhs))
360 bitmap_clear_bit (interesting_names, version);
361 remove_stmt_or_phi (stmt);
362 return cfg_altered;
365 /* Get the RHS of the assignment or PHI node if the PHI is a
366 degenerate. */
367 rhs = get_rhs_or_phi_arg (stmt);
368 if (!rhs)
370 bitmap_clear_bit (interesting_names, version);
371 return cfg_altered;
374 if (!virtual_operand_p (lhs))
375 cfg_altered = propagate_rhs_into_lhs (stmt, lhs, rhs,
376 interesting_names, need_eh_cleanup);
377 else
379 gimple *use_stmt;
380 imm_use_iterator iter;
381 use_operand_p use_p;
382 /* For virtual operands we have to propagate into all uses as
383 otherwise we will create overlapping life-ranges. */
384 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
385 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
386 SET_USE (use_p, rhs);
387 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
388 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs) = 1;
389 remove_stmt_or_phi (stmt);
392 /* Note that STMT may well have been deleted by now, so do
393 not access it, instead use the saved version # to clear
394 T's entry in the worklist. */
395 bitmap_clear_bit (interesting_names, version);
396 return cfg_altered;
399 /* The first phase in degenerate PHI elimination.
401 Eliminate the degenerate PHIs in BB, then recurse on the
402 dominator children of BB.
404 INTERESTING_NAMES tracks SSA_NAMEs that we may want to revisit
405 in the future. It is not set or queried here, but passed along
406 to children.
408 NEED_EH_CLEANUP tracks blocks that need their EH information
409 cleaned up after changing EH information on a statement. It is
410 not set or queried here, but passed along to children. */
412 static bool
413 eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names,
414 bitmap need_eh_cleanup)
416 gphi_iterator gsi;
417 basic_block son;
418 bool cfg_altered = false;
420 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);)
422 gphi *phi = gsi.phi ();
423 /* We might end up removing PHI so advance the iterator now. */
424 gsi_next (&gsi);
425 cfg_altered |= eliminate_const_or_copy (phi, interesting_names,
426 need_eh_cleanup);
429 /* Recurse into the dominator children of BB. */
430 for (son = first_dom_son (CDI_DOMINATORS, bb);
431 son;
432 son = next_dom_son (CDI_DOMINATORS, son))
433 cfg_altered |= eliminate_degenerate_phis_1 (son, interesting_names,
434 need_eh_cleanup);
436 return cfg_altered;
440 /* A very simple pass to eliminate degenerate PHI nodes from the
441 IL. This is meant to be fast enough to be able to be run several
442 times in the optimization pipeline.
444 Certain optimizations, particularly those which duplicate blocks
445 or remove edges from the CFG can create or expose PHIs which are
446 trivial copies or constant initializations.
448 While we could pick up these optimizations in DOM or with the
449 combination of copy-prop and CCP, those solutions are far too
450 heavy-weight for our needs.
452 This implementation has two phases so that we can efficiently
453 eliminate the first order degenerate PHIs and second order
454 degenerate PHIs.
456 The first phase performs a dominator walk to identify and eliminate
457 the vast majority of the degenerate PHIs. When a degenerate PHI
458 is identified and eliminated any affected statements or PHIs
459 are put on a worklist.
461 The second phase eliminates degenerate PHIs and trivial copies
462 or constant initializations using the worklist. This is how we
463 pick up the secondary optimization opportunities with minimal
464 cost. */
466 namespace {
468 const pass_data pass_data_phi_only_cprop =
470 GIMPLE_PASS, /* type */
471 "phicprop", /* name */
472 OPTGROUP_NONE, /* optinfo_flags */
473 TV_TREE_PHI_CPROP, /* tv_id */
474 ( PROP_cfg | PROP_ssa ), /* properties_required */
475 0, /* properties_provided */
476 0, /* properties_destroyed */
477 0, /* todo_flags_start */
478 ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */
481 class pass_phi_only_cprop : public gimple_opt_pass
483 public:
484 pass_phi_only_cprop (gcc::context *ctxt)
485 : gimple_opt_pass (pass_data_phi_only_cprop, ctxt)
488 /* opt_pass methods: */
489 opt_pass * clone () { return new pass_phi_only_cprop (m_ctxt); }
490 virtual bool gate (function *) { return flag_tree_dom != 0; }
491 virtual unsigned int execute (function *);
493 }; // class pass_phi_only_cprop
495 unsigned int
496 pass_phi_only_cprop::execute (function *fun)
498 bool cfg_altered = false;
500 /* Bitmap of blocks which need EH information updated. We can not
501 update it on-the-fly as doing so invalidates the dominator tree. */
502 auto_bitmap need_eh_cleanup;
504 /* INTERESTING_NAMES is effectively our worklist, indexed by
505 SSA_NAME_VERSION.
507 A set bit indicates that the statement or PHI node which
508 defines the SSA_NAME should be (re)examined to determine if
509 it has become a degenerate PHI or trivial const/copy propagation
510 opportunity.
512 Experiments have show we generally get better compilation
513 time behavior with bitmaps rather than sbitmaps. */
514 auto_bitmap interesting_names;
515 auto_bitmap interesting_names1;
517 calculate_dominance_info (CDI_DOMINATORS);
518 cfg_altered = false;
520 /* First phase. Eliminate degenerate PHIs via a dominator
521 walk of the CFG.
523 Experiments have indicated that we generally get better
524 compile-time behavior by visiting blocks in the first
525 phase in dominator order. Presumably this is because walking
526 in dominator order leaves fewer PHIs for later examination
527 by the worklist phase. */
528 cfg_altered = eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR_FOR_FN (fun),
529 interesting_names,
530 need_eh_cleanup);
532 /* Second phase. Eliminate second order degenerate PHIs as well
533 as trivial copies or constant initializations identified by
534 the first phase or this phase. Basically we keep iterating
535 until our set of INTERESTING_NAMEs is empty. */
536 while (!bitmap_empty_p (interesting_names))
538 unsigned int i;
539 bitmap_iterator bi;
541 /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
542 changed during the loop. Copy it to another bitmap and
543 use that. */
544 bitmap_copy (interesting_names1, interesting_names);
546 EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi)
548 tree name = ssa_name (i);
550 /* Ignore SSA_NAMEs that have been released because
551 their defining statement was deleted (unreachable). */
552 if (name)
553 cfg_altered
554 |= eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)),
555 interesting_names, need_eh_cleanup);
559 if (cfg_altered)
561 free_dominance_info (CDI_DOMINATORS);
562 /* If we changed the CFG schedule loops for fixup by cfgcleanup. */
563 loops_state_set (LOOPS_NEED_FIXUP);
566 /* Propagation of const and copies may make some EH edges dead. Purge
567 such edges from the CFG as needed. */
568 if (!bitmap_empty_p (need_eh_cleanup))
569 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
571 return 0;
574 } // anon namespace
576 gimple_opt_pass *
577 make_pass_phi_only_cprop (gcc::context *ctxt)
579 return new pass_phi_only_cprop (ctxt);