1/* Const/Copy propagation originating from degenerate PHIs
2 Copyright (C) 2001-2017 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 "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"
37
38
39/* PHI-ONLY copy and constant propagation. This pass is meant to clean
40 up degenerate PHIs created by or exposed by jump threading. */
41
42/* Given a statement STMT, which is either a PHI node or an assignment,
43 remove it from the IL. */
44
45static void
46remove_stmt_or_phi (gimple *stmt)
47{
48 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
49
50 if (gimple_code (stmt) == GIMPLE_PHI)
51 remove_phi_node (&gsi, true);
52 else
53 {
54 gsi_remove (&gsi, true);
55 release_defs (stmt);
56 }
57}
58
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. */
62
63static tree
64get_rhs_or_phi_arg (gimple *stmt)
65{
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 ();
72}
73
74
75/* Given a statement STMT, which is either a PHI node or an assignment,
76 return the "lhs" of the node. */
77
78static tree
79get_lhs_or_phi_result (gimple *stmt)
80{
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 ();
87}
88
89/* Propagate RHS into all uses of LHS (when possible).
90
91 RHS and LHS are derived from STMT, which is passed in solely so
92 that we can remove it if propagation is successful.
93
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.
99
100 NEED_EH_CLEANUP tracks blocks that need their EH information
101 cleaned up after changing EH information on a statement. */
102
103static bool
104propagate_rhs_into_lhs (gimple *stmt, tree lhs, tree rhs,
105 bitmap interesting_names, bitmap need_eh_cleanup)
106{
107 bool cfg_altered = false;
108
109 /* First verify that propagation is valid. */
110 if (may_propagate_copy (lhs, rhs))
111 {
112 use_operand_p use_p;
113 imm_use_iterator iter;
114 gimple *use_stmt;
115 bool all = true;
116
117 /* Dump details. */
118 if (dump_file && (dump_flags & TDF_DETAILS))
119 {
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");
126 }
127
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)
132 {
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;
138
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))
142 {
143 all = false;
144 continue;
145 }
146
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)
156 {
157 all = false;
158 continue;
159 }
160
161 /* Dump details. */
162 if (dump_file && (dump_flags & TDF_DETAILS))
163 {
164 fprintf (dump_file, " Original statement:");
165 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
166 }
167
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);
171
172 /* Special cases to avoid useless calls into the folding
173 routines, operand scanning, etc.
174
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)
179 {
180 tree result;
181
182 /* Dump details. */
183 if (dump_file && (dump_flags & TDF_DETAILS))
184 {
185 fprintf (dump_file, " Updated statement:");
186 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
187 }
188
189 result = get_lhs_or_phi_result (use_stmt);
190 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
191 continue;
192 }
193
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. */
204 {
205 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
206 fold_stmt_inplace (&gsi);
207 }
208
209 /* Sometimes propagation can expose new operands to the
210 renamer. */
211 update_stmt (use_stmt);
212
213 /* Dump details. */
214 if (dump_file && (dump_flags & TDF_DETAILS))
215 {
216 fprintf (dump_file, " Updated statement:");
217 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
218 }
219
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));
226
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))
230 {
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");
234 }
235
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))))
242 {
243 tree result = get_lhs_or_phi_result (use_stmt);
244 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
245 }
246
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)
254 {
255 tree val;
256
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);
267
268 if (val && is_gimple_min_invariant (val))
269 {
270 basic_block bb = gimple_bb (use_stmt);
271 edge te = find_taken_edge (bb, val);
272 if (!te)
273 continue;
274
275 edge_iterator ei;
276 edge e;
277 gimple_stmt_iterator gsi;
278 gphi_iterator psi;
279
280 /* Remove all outgoing edges except TE. */
281 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
282 {
283 if (e != te)
284 {
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))
290 {
291 gphi *phi = psi.phi ();
292
293 tree result = gimple_phi_result (phi);
294 int version = SSA_NAME_VERSION (result);
295
296 bitmap_set_bit (interesting_names, version);
297 }
298
299 te->probability += e->probability;
300
301 remove_edge (e);
302 cfg_altered = true;
303 }
304 else
305 ei_next (&ei);
306 }
307
308 gsi = gsi_last_bb (gimple_bb (use_stmt));
309 gsi_remove (&gsi, true);
310
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;
315 }
316 }
317 }
318
319 /* Ensure there is nothing else to do. */
320 gcc_assert (!all || has_zero_uses (lhs));
321
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);
326 }
327 return cfg_altered;
328}
329
330/* STMT is either a PHI node (potentially a degenerate PHI node) or
331 a statement that is a trivial copy or constant initialization.
332
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.
336
337 All exit paths should clear INTERESTING_NAMES for the result
338 of STMT.
339
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. */
343
344static bool
345eliminate_const_or_copy (gimple *stmt, bitmap interesting_names,
346 bitmap need_eh_cleanup)
347{
348 tree lhs = get_lhs_or_phi_result (stmt);
349 tree rhs;
350 int version = SSA_NAME_VERSION (lhs);
351 bool cfg_altered = false;
352
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))
359 {
360 bitmap_clear_bit (interesting_names, version);
361 remove_stmt_or_phi (stmt);
362 return cfg_altered;
363 }
364
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)
369 {
370 bitmap_clear_bit (interesting_names, version);
371 return cfg_altered;
372 }
373
374 if (!virtual_operand_p (lhs))
375 cfg_altered = propagate_rhs_into_lhs (stmt, lhs, rhs,
376 interesting_names, need_eh_cleanup);
377 else
378 {
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);
390 }
391
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;
397}
398
399/* The first phase in degenerate PHI elimination.
400
401 Eliminate the degenerate PHIs in BB, then recurse on the
402 dominator children of BB.
403
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.
407
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. */
411
412static bool
413eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names,
414 bitmap need_eh_cleanup)
415{
416 gphi_iterator gsi;
417 basic_block son;
418 bool cfg_altered = false;
419
420 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);)
421 {
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);
427 }
428
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);
435
436 return cfg_altered;
437}
438
439
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.
443
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.
447
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.
451
452 This implementation has two phases so that we can efficiently
453 eliminate the first order degenerate PHIs and second order
454 degenerate PHIs.
455
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.
460
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. */
465
466namespace {
467
468const pass_data pass_data_phi_only_cprop =
469{
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 */
479};
480
481class pass_phi_only_cprop : public gimple_opt_pass
482{
483public:
484 pass_phi_only_cprop (gcc::context *ctxt)
485 : gimple_opt_pass (pass_data_phi_only_cprop, ctxt)
486 {}
487
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 *);
492
493}; // class pass_phi_only_cprop
494
495unsigned int
496pass_phi_only_cprop::execute (function *fun)
497{
498 bool cfg_altered = false;
499
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;
503
504 /* INTERESTING_NAMES is effectively our worklist, indexed by
505 SSA_NAME_VERSION.
506
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.
511
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;
516
517 calculate_dominance_info (CDI_DOMINATORS);
518 cfg_altered = false;
519
520 /* First phase. Eliminate degenerate PHIs via a dominator
521 walk of the CFG.
522
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);
531
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))
537 {
538 unsigned int i;
539 bitmap_iterator bi;
540
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);
545
546 EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi)
547 {
548 tree name = ssa_name (i);
549
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);
556 }
557 }
558
559 if (cfg_altered)
560 {
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);
564 }
565
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);
570
571 return 0;
572}
573
574} // anon namespace
575
576gimple_opt_pass *
577make_pass_phi_only_cprop (gcc::context *ctxt)
578{
579 return new pass_phi_only_cprop (ctxt);
580}
581