1/* CFG cleanup for trees.
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 "rtl.h"
25#include "tree.h"
26#include "gimple.h"
27#include "cfghooks.h"
28#include "tree-pass.h"
29#include "ssa.h"
30#include "diagnostic-core.h"
31#include "fold-const.h"
32#include "cfganal.h"
33#include "cfgcleanup.h"
34#include "tree-eh.h"
35#include "gimplify.h"
36#include "gimple-iterator.h"
37#include "tree-cfg.h"
38#include "tree-ssa-loop-manip.h"
39#include "tree-dfa.h"
40#include "tree-ssa.h"
41#include "cfgloop.h"
42#include "tree-scalar-evolution.h"
43#include "gimple-match.h"
44#include "gimple-fold.h"
45#include "tree-ssa-loop-niter.h"
46
47
48/* The set of blocks in that at least one of the following changes happened:
49 -- the statement at the end of the block was changed
50 -- the block was newly created
51 -- the set of the predecessors of the block changed
52 -- the set of the successors of the block changed
53 ??? Maybe we could track these changes separately, since they determine
54 what cleanups it makes sense to try on the block. */
55bitmap cfgcleanup_altered_bbs;
56
57/* Remove any fallthru edge from EV. Return true if an edge was removed. */
58
59static bool
60remove_fallthru_edge (vec<edge, va_gc> *ev)
61{
62 edge_iterator ei;
63 edge e;
64
65 FOR_EACH_EDGE (e, ei, ev)
66 if ((e->flags & EDGE_FALLTHRU) != 0)
67 {
68 if (e->flags & EDGE_COMPLEX)
69 e->flags &= ~EDGE_FALLTHRU;
70 else
71 remove_edge_and_dominated_blocks (e);
72 return true;
73 }
74 return false;
75}
76
77/* Convert a SWTCH with single non-default case to gcond and replace it
78 at GSI. */
79
80static bool
81convert_single_case_switch (gswitch *swtch, gimple_stmt_iterator &gsi)
82{
83 if (gimple_switch_num_labels (swtch) != 2)
84 return false;
85
86 tree index = gimple_switch_index (swtch);
87 tree default_label = CASE_LABEL (gimple_switch_default_label (swtch));
88 tree label = gimple_switch_label (swtch, 1);
89 tree low = CASE_LOW (label);
90 tree high = CASE_HIGH (label);
91
92 basic_block default_bb = label_to_block_fn (cfun, default_label);
93 basic_block case_bb = label_to_block_fn (cfun, CASE_LABEL (label));
94
95 basic_block bb = gimple_bb (swtch);
96 gcond *cond;
97
98 /* Replace switch statement with condition statement. */
99 if (high)
100 {
101 tree lhs, rhs;
102 generate_range_test (bb, index, low, high, &lhs, &rhs);
103 cond = gimple_build_cond (LE_EXPR, lhs, rhs, NULL_TREE, NULL_TREE);
104 }
105 else
106 cond = gimple_build_cond (EQ_EXPR, index,
107 fold_convert (TREE_TYPE (index), low),
108 NULL_TREE, NULL_TREE);
109
110 gsi_replace (&gsi, cond, true);
111
112 /* Update edges. */
113 edge case_edge = find_edge (bb, case_bb);
114 edge default_edge = find_edge (bb, default_bb);
115
116 case_edge->flags |= EDGE_TRUE_VALUE;
117 default_edge->flags |= EDGE_FALSE_VALUE;
118 return true;
119}
120
121/* Disconnect an unreachable block in the control expression starting
122 at block BB. */
123
124static bool
125cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi)
126{
127 edge taken_edge;
128 bool retval = false;
129 gimple *stmt = gsi_stmt (gsi);
130
131 if (!single_succ_p (bb))
132 {
133 edge e;
134 edge_iterator ei;
135 bool warned;
136 tree val = NULL_TREE;
137
138 /* Try to convert a switch with just a single non-default case to
139 GIMPLE condition. */
140 if (gimple_code (stmt) == GIMPLE_SWITCH
141 && convert_single_case_switch (as_a<gswitch *> (stmt), gsi))
142 stmt = gsi_stmt (gsi);
143
144 fold_defer_overflow_warnings ();
145 switch (gimple_code (stmt))
146 {
147 case GIMPLE_COND:
148 {
149 code_helper rcode;
150 tree ops[3] = {};
151 if (gimple_simplify (stmt, &rcode, ops, NULL, no_follow_ssa_edges,
152 no_follow_ssa_edges)
153 && rcode == INTEGER_CST)
154 val = ops[0];
155 }
156 break;
157
158 case GIMPLE_SWITCH:
159 val = gimple_switch_index (as_a <gswitch *> (stmt));
160 break;
161
162 default:
163 ;
164 }
165 taken_edge = find_taken_edge (bb, val);
166 if (!taken_edge)
167 {
168 fold_undefer_and_ignore_overflow_warnings ();
169 return false;
170 }
171
172 /* Remove all the edges except the one that is always executed. */
173 warned = false;
174 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
175 {
176 if (e != taken_edge)
177 {
178 if (!warned)
179 {
180 fold_undefer_overflow_warnings
181 (true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
182 warned = true;
183 }
184
185 taken_edge->probability += e->probability;
186 remove_edge_and_dominated_blocks (e);
187 retval = true;
188 }
189 else
190 ei_next (&ei);
191 }
192 if (!warned)
193 fold_undefer_and_ignore_overflow_warnings ();
194 }
195 else
196 taken_edge = single_succ_edge (bb);
197
198 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
199 gsi_remove (&gsi, true);
200 taken_edge->flags = EDGE_FALLTHRU;
201
202 return retval;
203}
204
205/* Cleanup the GF_CALL_CTRL_ALTERING flag according to
206 to updated gimple_call_flags. */
207
208static void
209cleanup_call_ctrl_altering_flag (gimple *bb_end)
210{
211 if (!is_gimple_call (bb_end)
212 || !gimple_call_ctrl_altering_p (bb_end))
213 return;
214
215 int flags = gimple_call_flags (bb_end);
216 if (((flags & (ECF_CONST | ECF_PURE))
217 && !(flags & ECF_LOOPING_CONST_OR_PURE))
218 || (flags & ECF_LEAF))
219 gimple_call_set_ctrl_altering (bb_end, false);
220}
221
222/* Try to remove superfluous control structures in basic block BB. Returns
223 true if anything changes. */
224
225static bool
226cleanup_control_flow_bb (basic_block bb)
227{
228 gimple_stmt_iterator gsi;
229 bool retval = false;
230 gimple *stmt;
231
232 /* If the last statement of the block could throw and now cannot,
233 we need to prune cfg. */
234 retval |= gimple_purge_dead_eh_edges (bb);
235
236 gsi = gsi_last_nondebug_bb (bb);
237 if (gsi_end_p (gsi))
238 return retval;
239
240 stmt = gsi_stmt (gsi);
241
242 /* Try to cleanup ctrl altering flag for call which ends bb. */
243 cleanup_call_ctrl_altering_flag (stmt);
244
245 if (gimple_code (stmt) == GIMPLE_COND
246 || gimple_code (stmt) == GIMPLE_SWITCH)
247 {
248 gcc_checking_assert (gsi_stmt (gsi_last_bb (bb)) == stmt);
249 retval |= cleanup_control_expr_graph (bb, gsi);
250 }
251 else if (gimple_code (stmt) == GIMPLE_GOTO
252 && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
253 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0))
254 == LABEL_DECL))
255 {
256 /* If we had a computed goto which has a compile-time determinable
257 destination, then we can eliminate the goto. */
258 edge e;
259 tree label;
260 edge_iterator ei;
261 basic_block target_block;
262
263 gcc_checking_assert (gsi_stmt (gsi_last_bb (bb)) == stmt);
264 /* First look at all the outgoing edges. Delete any outgoing
265 edges which do not go to the right block. For the one
266 edge which goes to the right block, fix up its flags. */
267 label = TREE_OPERAND (gimple_goto_dest (stmt), 0);
268 if (DECL_CONTEXT (label) != cfun->decl)
269 return retval;
270 target_block = label_to_block (label);
271 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
272 {
273 if (e->dest != target_block)
274 remove_edge_and_dominated_blocks (e);
275 else
276 {
277 /* Turn off the EDGE_ABNORMAL flag. */
278 e->flags &= ~EDGE_ABNORMAL;
279
280 /* And set EDGE_FALLTHRU. */
281 e->flags |= EDGE_FALLTHRU;
282 ei_next (&ei);
283 }
284 }
285
286 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
287 bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
288
289 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
290 relevant information we need. */
291 gsi_remove (&gsi, true);
292 retval = true;
293 }
294
295 /* Check for indirect calls that have been turned into
296 noreturn calls. */
297 else if (is_gimple_call (stmt)
298 && gimple_call_noreturn_p (stmt))
299 {
300 /* If there are debug stmts after the noreturn call, remove them
301 now, they should be all unreachable anyway. */
302 for (gsi_next (&gsi); !gsi_end_p (gsi); )
303 gsi_remove (&gsi, true);
304 if (remove_fallthru_edge (bb->succs))
305 retval = true;
306 }
307
308 return retval;
309}
310
311/* Return true if basic block BB does nothing except pass control
312 flow to another block and that we can safely insert a label at
313 the start of the successor block.
314
315 As a precondition, we require that BB be not equal to
316 the entry block. */
317
318static bool
319tree_forwarder_block_p (basic_block bb, bool phi_wanted)
320{
321 gimple_stmt_iterator gsi;
322 location_t locus;
323
324 /* BB must have a single outgoing edge. */
325 if (single_succ_p (bb) != 1
326 /* If PHI_WANTED is false, BB must not have any PHI nodes.
327 Otherwise, BB must have PHI nodes. */
328 || gimple_seq_empty_p (phi_nodes (bb)) == phi_wanted
329 /* BB may not be a predecessor of the exit block. */
330 || single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
331 /* Nor should this be an infinite loop. */
332 || single_succ (bb) == bb
333 /* BB may not have an abnormal outgoing edge. */
334 || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
335 return false;
336
337 gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
338
339 locus = single_succ_edge (bb)->goto_locus;
340
341 /* There should not be an edge coming from entry, or an EH edge. */
342 {
343 edge_iterator ei;
344 edge e;
345
346 FOR_EACH_EDGE (e, ei, bb->preds)
347 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || (e->flags & EDGE_EH))
348 return false;
349 /* If goto_locus of any of the edges differs, prevent removing
350 the forwarder block for -O0. */
351 else if (optimize == 0 && e->goto_locus != locus)
352 return false;
353 }
354
355 /* Now walk through the statements backward. We can ignore labels,
356 anything else means this is not a forwarder block. */
357 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
358 {
359 gimple *stmt = gsi_stmt (gsi);
360
361 switch (gimple_code (stmt))
362 {
363 case GIMPLE_LABEL:
364 if (DECL_NONLOCAL (gimple_label_label (as_a <glabel *> (stmt))))
365 return false;
366 if (optimize == 0 && gimple_location (stmt) != locus)
367 return false;
368 break;
369
370 /* ??? For now, hope there's a corresponding debug
371 assignment at the destination. */
372 case GIMPLE_DEBUG:
373 break;
374
375 default:
376 return false;
377 }
378 }
379
380 if (current_loops)
381 {
382 basic_block dest;
383 /* Protect loop headers. */
384 if (bb_loop_header_p (bb))
385 return false;
386
387 dest = EDGE_SUCC (bb, 0)->dest;
388 /* Protect loop preheaders and latches if requested. */
389 if (dest->loop_father->header == dest)
390 {
391 if (bb->loop_father == dest->loop_father)
392 {
393 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
394 return false;
395 /* If bb doesn't have a single predecessor we'd make this
396 loop have multiple latches. Don't do that if that
397 would in turn require disambiguating them. */
398 return (single_pred_p (bb)
399 || loops_state_satisfies_p
400 (LOOPS_MAY_HAVE_MULTIPLE_LATCHES));
401 }
402 else if (bb->loop_father == loop_outer (dest->loop_father))
403 return !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS);
404 /* Always preserve other edges into loop headers that are
405 not simple latches or preheaders. */
406 return false;
407 }
408 }
409
410 return true;
411}
412
413/* If all the PHI nodes in DEST have alternatives for E1 and E2 and
414 those alternatives are equal in each of the PHI nodes, then return
415 true, else return false. */
416
417static bool
418phi_alternatives_equal (basic_block dest, edge e1, edge e2)
419{
420 int n1 = e1->dest_idx;
421 int n2 = e2->dest_idx;
422 gphi_iterator gsi;
423
424 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
425 {
426 gphi *phi = gsi.phi ();
427 tree val1 = gimple_phi_arg_def (phi, n1);
428 tree val2 = gimple_phi_arg_def (phi, n2);
429
430 gcc_assert (val1 != NULL_TREE);
431 gcc_assert (val2 != NULL_TREE);
432
433 if (!operand_equal_for_phi_arg_p (val1, val2))
434 return false;
435 }
436
437 return true;
438}
439
440/* Removes forwarder block BB. Returns false if this failed. */
441
442static bool
443remove_forwarder_block (basic_block bb)
444{
445 edge succ = single_succ_edge (bb), e, s;
446 basic_block dest = succ->dest;
447 gimple *label;
448 edge_iterator ei;
449 gimple_stmt_iterator gsi, gsi_to;
450 bool can_move_debug_stmts;
451
452 /* We check for infinite loops already in tree_forwarder_block_p.
453 However it may happen that the infinite loop is created
454 afterwards due to removal of forwarders. */
455 if (dest == bb)
456 return false;
457
458 /* If the destination block consists of a nonlocal label or is a
459 EH landing pad, do not merge it. */
460 label = first_stmt (dest);
461 if (label)
462 if (glabel *label_stmt = dyn_cast <glabel *> (label))
463 if (DECL_NONLOCAL (gimple_label_label (label_stmt))
464 || EH_LANDING_PAD_NR (gimple_label_label (label_stmt)) != 0)
465 return false;
466
467 /* If there is an abnormal edge to basic block BB, but not into
468 dest, problems might occur during removal of the phi node at out
469 of ssa due to overlapping live ranges of registers.
470
471 If there is an abnormal edge in DEST, the problems would occur
472 anyway since cleanup_dead_labels would then merge the labels for
473 two different eh regions, and rest of exception handling code
474 does not like it.
475
476 So if there is an abnormal edge to BB, proceed only if there is
477 no abnormal edge to DEST and there are no phi nodes in DEST. */
478 if (bb_has_abnormal_pred (bb)
479 && (bb_has_abnormal_pred (dest)
480 || !gimple_seq_empty_p (phi_nodes (dest))))
481 return false;
482
483 /* If there are phi nodes in DEST, and some of the blocks that are
484 predecessors of BB are also predecessors of DEST, check that the
485 phi node arguments match. */
486 if (!gimple_seq_empty_p (phi_nodes (dest)))
487 {
488 FOR_EACH_EDGE (e, ei, bb->preds)
489 {
490 s = find_edge (e->src, dest);
491 if (!s)
492 continue;
493
494 if (!phi_alternatives_equal (dest, succ, s))
495 return false;
496 }
497 }
498
499 can_move_debug_stmts = MAY_HAVE_DEBUG_STMTS && single_pred_p (dest);
500
501 basic_block pred = NULL;
502 if (single_pred_p (bb))
503 pred = single_pred (bb);
504
505 /* Redirect the edges. */
506 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
507 {
508 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
509
510 if (e->flags & EDGE_ABNORMAL)
511 {
512 /* If there is an abnormal edge, redirect it anyway, and
513 move the labels to the new block to make it legal. */
514 s = redirect_edge_succ_nodup (e, dest);
515 }
516 else
517 s = redirect_edge_and_branch (e, dest);
518
519 if (s == e)
520 {
521 /* Create arguments for the phi nodes, since the edge was not
522 here before. */
523 for (gphi_iterator psi = gsi_start_phis (dest);
524 !gsi_end_p (psi);
525 gsi_next (&psi))
526 {
527 gphi *phi = psi.phi ();
528 source_location l = gimple_phi_arg_location_from_edge (phi, succ);
529 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
530 add_phi_arg (phi, unshare_expr (def), s, l);
531 }
532 }
533 }
534
535 /* Move nonlocal labels and computed goto targets as well as user
536 defined labels and labels with an EH landing pad number to the
537 new block, so that the redirection of the abnormal edges works,
538 jump targets end up in a sane place and debug information for
539 labels is retained. */
540 gsi_to = gsi_start_bb (dest);
541 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
542 {
543 tree decl;
544 label = gsi_stmt (gsi);
545 if (is_gimple_debug (label)
546 ? can_move_debug_stmts
547 : ((decl = gimple_label_label (as_a <glabel *> (label))),
548 EH_LANDING_PAD_NR (decl) != 0
549 || DECL_NONLOCAL (decl)
550 || FORCED_LABEL (decl)
551 || !DECL_ARTIFICIAL (decl)))
552 {
553 gsi_remove (&gsi, false);
554 gsi_insert_before (&gsi_to, label, GSI_SAME_STMT);
555 }
556 else
557 gsi_next (&gsi);
558 }
559
560 bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
561
562 /* Update the dominators. */
563 if (dom_info_available_p (CDI_DOMINATORS))
564 {
565 basic_block dom, dombb, domdest;
566
567 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
568 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
569 if (domdest == bb)
570 {
571 /* Shortcut to avoid calling (relatively expensive)
572 nearest_common_dominator unless necessary. */
573 dom = dombb;
574 }
575 else
576 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
577
578 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
579 }
580
581 /* Adjust latch infomation of BB's parent loop as otherwise
582 the cfg hook has a hard time not to kill the loop. */
583 if (current_loops && bb->loop_father->latch == bb)
584 bb->loop_father->latch = pred;
585
586 /* And kill the forwarder block. */
587 delete_basic_block (bb);
588
589 return true;
590}
591
592/* STMT is a call that has been discovered noreturn. Split the
593 block to prepare fixing up the CFG and remove LHS.
594 Return true if cleanup-cfg needs to run. */
595
596bool
597fixup_noreturn_call (gimple *stmt)
598{
599 basic_block bb = gimple_bb (stmt);
600 bool changed = false;
601
602 if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
603 return false;
604
605 /* First split basic block if stmt is not last. */
606 if (stmt != gsi_stmt (gsi_last_bb (bb)))
607 {
608 if (stmt == gsi_stmt (gsi_last_nondebug_bb (bb)))
609 {
610 /* Don't split if there are only debug stmts
611 after stmt, that can result in -fcompare-debug
612 failures. Remove the debug stmts instead,
613 they should be all unreachable anyway. */
614 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
615 for (gsi_next (&gsi); !gsi_end_p (gsi); )
616 gsi_remove (&gsi, true);
617 }
618 else
619 {
620 split_block (bb, stmt);
621 changed = true;
622 }
623 }
624
625 /* If there is an LHS, remove it, but only if its type has fixed size.
626 The LHS will need to be recreated during RTL expansion and creating
627 temporaries of variable-sized types is not supported. Also don't
628 do this with TREE_ADDRESSABLE types, as assign_temp will abort.
629 Drop LHS regardless of TREE_ADDRESSABLE, if the function call
630 has been changed into a call that does not return a value, like
631 __builtin_unreachable or __cxa_pure_virtual. */
632 tree lhs = gimple_call_lhs (stmt);
633 if (lhs
634 && (should_remove_lhs_p (lhs)
635 || VOID_TYPE_P (TREE_TYPE (gimple_call_fntype (stmt)))))
636 {
637 gimple_call_set_lhs (stmt, NULL_TREE);
638
639 /* We need to fix up the SSA name to avoid checking errors. */
640 if (TREE_CODE (lhs) == SSA_NAME)
641 {
642 tree new_var = create_tmp_reg (TREE_TYPE (lhs));
643 SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs, new_var);
644 SSA_NAME_DEF_STMT (lhs) = gimple_build_nop ();
645 set_ssa_default_def (cfun, new_var, lhs);
646 }
647
648 update_stmt (stmt);
649 }
650
651 /* Mark the call as altering control flow. */
652 if (!gimple_call_ctrl_altering_p (stmt))
653 {
654 gimple_call_set_ctrl_altering (stmt, true);
655 changed = true;
656 }
657
658 return changed;
659}
660
661/* Return true if we want to merge BB1 and BB2 into a single block. */
662
663static bool
664want_merge_blocks_p (basic_block bb1, basic_block bb2)
665{
666 if (!can_merge_blocks_p (bb1, bb2))
667 return false;
668 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb1);
669 if (gsi_end_p (gsi) || !stmt_can_terminate_bb_p (gsi_stmt (gsi)))
670 return true;
671 return bb1->count.ok_for_merging (bb2->count);
672}
673
674
675/* Tries to cleanup cfg in basic block BB. Returns true if anything
676 changes. */
677
678static bool
679cleanup_tree_cfg_bb (basic_block bb)
680{
681 if (tree_forwarder_block_p (bb, false)
682 && remove_forwarder_block (bb))
683 return true;
684
685 /* If there is a merge opportunity with the predecessor
686 do nothing now but wait until we process the predecessor.
687 This happens when we visit BBs in a non-optimal order and
688 avoids quadratic behavior with adjusting stmts BB pointer. */
689 if (single_pred_p (bb)
690 && want_merge_blocks_p (single_pred (bb), bb))
691 /* But make sure we _do_ visit it. When we remove unreachable paths
692 ending in a backedge we fail to mark the destinations predecessors
693 as changed. */
694 bitmap_set_bit (cfgcleanup_altered_bbs, single_pred (bb)->index);
695
696 /* Merging the blocks may create new opportunities for folding
697 conditional branches (due to the elimination of single-valued PHI
698 nodes). */
699 else if (single_succ_p (bb)
700 && want_merge_blocks_p (bb, single_succ (bb)))
701 {
702 merge_blocks (bb, single_succ (bb));
703 return true;
704 }
705
706 return false;
707}
708
709/* Do cleanup_control_flow_bb in PRE order. */
710
711static bool
712cleanup_control_flow_pre ()
713{
714 bool retval = false;
715
716 auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
717 auto_sbitmap visited (last_basic_block_for_fn (cfun));
718 bitmap_clear (visited);
719
720 stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
721
722 while (! stack.is_empty ())
723 {
724 /* Look at the edge on the top of the stack. */
725 edge_iterator ei = stack.last ();
726 basic_block dest = ei_edge (ei)->dest;
727
728 if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
729 && ! bitmap_bit_p (visited, dest->index))
730 {
731 bitmap_set_bit (visited, dest->index);
732 retval |= cleanup_control_flow_bb (dest);
733 if (EDGE_COUNT (dest->succs) > 0)
734 stack.quick_push (ei_start (dest->succs));
735 }
736 else
737 {
738 if (!ei_one_before_end_p (ei))
739 ei_next (&stack.last ());
740 else
741 stack.pop ();
742 }
743 }
744
745 return retval;
746}
747
748/* Iterate the cfg cleanups, while anything changes. */
749
750static bool
751cleanup_tree_cfg_1 (void)
752{
753 bool retval = false;
754 basic_block bb;
755 unsigned i, n;
756
757 /* Prepare the worklists of altered blocks. */
758 cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
759
760 /* During forwarder block cleanup, we may redirect edges out of
761 SWITCH_EXPRs, which can get expensive. So we want to enable
762 recording of edge to CASE_LABEL_EXPR. */
763 start_recording_case_labels ();
764
765 /* We cannot use FOR_EACH_BB_FN for the BB iterations below
766 since the basic blocks may get removed. */
767
768 /* Start by iterating over all basic blocks in PRE order looking for
769 edge removal opportunities. Do this first because incoming SSA form
770 may be invalid and we want to avoid performing SSA related tasks such
771 as propgating out a PHI node during BB merging in that state. */
772 retval |= cleanup_control_flow_pre ();
773
774 /* After doing the above SSA form should be valid (or an update SSA
775 should be required). */
776
777 /* Continue by iterating over all basic blocks looking for BB merging
778 opportunities. */
779 n = last_basic_block_for_fn (cfun);
780 for (i = NUM_FIXED_BLOCKS; i < n; i++)
781 {
782 bb = BASIC_BLOCK_FOR_FN (cfun, i);
783 if (bb)
784 retval |= cleanup_tree_cfg_bb (bb);
785 }
786
787 /* Now process the altered blocks, as long as any are available. */
788 while (!bitmap_empty_p (cfgcleanup_altered_bbs))
789 {
790 i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
791 bitmap_clear_bit (cfgcleanup_altered_bbs, i);
792 if (i < NUM_FIXED_BLOCKS)
793 continue;
794
795 bb = BASIC_BLOCK_FOR_FN (cfun, i);
796 if (!bb)
797 continue;
798
799 retval |= cleanup_control_flow_bb (bb);
800 retval |= cleanup_tree_cfg_bb (bb);
801 }
802
803 end_recording_case_labels ();
804 BITMAP_FREE (cfgcleanup_altered_bbs);
805 return retval;
806}
807
808static bool
809mfb_keep_latches (edge e)
810{
811 return ! dominated_by_p (CDI_DOMINATORS, e->src, e->dest);
812}
813
814/* Remove unreachable blocks and other miscellaneous clean up work.
815 Return true if the flowgraph was modified, false otherwise. */
816
817static bool
818cleanup_tree_cfg_noloop (void)
819{
820 bool changed;
821
822 timevar_push (TV_TREE_CLEANUP_CFG);
823
824 /* Iterate until there are no more cleanups left to do. If any
825 iteration changed the flowgraph, set CHANGED to true.
826
827 If dominance information is available, there cannot be any unreachable
828 blocks. */
829 if (!dom_info_available_p (CDI_DOMINATORS))
830 {
831 changed = delete_unreachable_blocks ();
832 calculate_dominance_info (CDI_DOMINATORS);
833 }
834 else
835 {
836 checking_verify_dominators (CDI_DOMINATORS);
837 changed = false;
838 }
839
840 /* Ensure that we have single entries into loop headers. Otherwise
841 if one of the entries is becoming a latch due to CFG cleanup
842 (from formerly being part of an irreducible region) then we mess
843 up loop fixup and associate the old loop with a different region
844 which makes niter upper bounds invalid. See for example PR80549.
845 This needs to be done before we remove trivially dead edges as
846 we need to capture the dominance state before the pending transform. */
847 if (current_loops)
848 {
849 loop_p loop;
850 unsigned i;
851 FOR_EACH_VEC_ELT (*get_loops (cfun), i, loop)
852 if (loop && loop->header)
853 {
854 basic_block bb = loop->header;
855 edge_iterator ei;
856 edge e;
857 bool found_latch = false;
858 bool any_abnormal = false;
859 unsigned n = 0;
860 /* We are only interested in preserving existing loops, but
861 we need to check whether they are still real and of course
862 if we need to add a preheader at all. */
863 FOR_EACH_EDGE (e, ei, bb->preds)
864 {
865 if (e->flags & EDGE_ABNORMAL)
866 {
867 any_abnormal = true;
868 break;
869 }
870 if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
871 {
872 found_latch = true;
873 continue;
874 }
875 n++;
876 }
877 /* If we have more than one entry to the loop header
878 create a forwarder. */
879 if (found_latch && ! any_abnormal && n > 1)
880 {
881 edge fallthru = make_forwarder_block (bb, mfb_keep_latches,
882 NULL);
883 loop->header = fallthru->dest;
884 if (! loops_state_satisfies_p (LOOPS_NEED_FIXUP))
885 {
886 /* The loop updating from the CFG hook is incomplete
887 when we have multiple latches, fixup manually. */
888 remove_bb_from_loops (fallthru->src);
889 loop_p cloop = loop;
890 FOR_EACH_EDGE (e, ei, fallthru->src->preds)
891 cloop = find_common_loop (cloop, e->src->loop_father);
892 add_bb_to_loop (fallthru->src, cloop);
893 }
894 }
895 }
896 }
897
898 changed |= cleanup_tree_cfg_1 ();
899
900 gcc_assert (dom_info_available_p (CDI_DOMINATORS));
901
902 /* Do not renumber blocks if the SCEV cache is active, it is indexed by
903 basic-block numbers. */
904 if (! scev_initialized_p ())
905 compact_blocks ();
906
907 checking_verify_flow_info ();
908
909 timevar_pop (TV_TREE_CLEANUP_CFG);
910
911 if (changed && current_loops)
912 {
913 /* Removing edges and/or blocks may make recorded bounds refer
914 to stale GIMPLE stmts now, so clear them. */
915 free_numbers_of_iterations_estimates (cfun);
916 loops_state_set (LOOPS_NEED_FIXUP);
917 }
918
919 return changed;
920}
921
922/* Repairs loop structures. */
923
924static void
925repair_loop_structures (void)
926{
927 bitmap changed_bbs;
928 unsigned n_new_loops;
929
930 calculate_dominance_info (CDI_DOMINATORS);
931
932 timevar_push (TV_REPAIR_LOOPS);
933 changed_bbs = BITMAP_ALLOC (NULL);
934 n_new_loops = fix_loop_structure (changed_bbs);
935
936 /* This usually does nothing. But sometimes parts of cfg that originally
937 were inside a loop get out of it due to edge removal (since they
938 become unreachable by back edges from latch). Also a former
939 irreducible loop can become reducible - in this case force a full
940 rewrite into loop-closed SSA form. */
941 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
942 rewrite_into_loop_closed_ssa (n_new_loops ? NULL : changed_bbs,
943 TODO_update_ssa);
944
945 BITMAP_FREE (changed_bbs);
946
947 checking_verify_loop_structure ();
948 scev_reset ();
949
950 timevar_pop (TV_REPAIR_LOOPS);
951}
952
953/* Cleanup cfg and repair loop structures. */
954
955bool
956cleanup_tree_cfg (void)
957{
958 bool changed = cleanup_tree_cfg_noloop ();
959
960 if (current_loops != NULL
961 && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
962 repair_loop_structures ();
963
964 return changed;
965}
966
967/* Tries to merge the PHI nodes at BB into those at BB's sole successor.
968 Returns true if successful. */
969
970static bool
971remove_forwarder_block_with_phi (basic_block bb)
972{
973 edge succ = single_succ_edge (bb);
974 basic_block dest = succ->dest;
975 gimple *label;
976 basic_block dombb, domdest, dom;
977
978 /* We check for infinite loops already in tree_forwarder_block_p.
979 However it may happen that the infinite loop is created
980 afterwards due to removal of forwarders. */
981 if (dest == bb)
982 return false;
983
984 /* Removal of forwarders may expose new natural loops and thus
985 a block may turn into a loop header. */
986 if (current_loops && bb_loop_header_p (bb))
987 return false;
988
989 /* If the destination block consists of a nonlocal label, do not
990 merge it. */
991 label = first_stmt (dest);
992 if (label)
993 if (glabel *label_stmt = dyn_cast <glabel *> (label))
994 if (DECL_NONLOCAL (gimple_label_label (label_stmt)))
995 return false;
996
997 /* Record BB's single pred in case we need to update the father
998 loop's latch information later. */
999 basic_block pred = NULL;
1000 if (single_pred_p (bb))
1001 pred = single_pred (bb);
1002
1003 /* Redirect each incoming edge to BB to DEST. */
1004 while (EDGE_COUNT (bb->preds) > 0)
1005 {
1006 edge e = EDGE_PRED (bb, 0), s;
1007 gphi_iterator gsi;
1008
1009 s = find_edge (e->src, dest);
1010 if (s)
1011 {
1012 /* We already have an edge S from E->src to DEST. If S and
1013 E->dest's sole successor edge have the same PHI arguments
1014 at DEST, redirect S to DEST. */
1015 if (phi_alternatives_equal (dest, s, succ))
1016 {
1017 e = redirect_edge_and_branch (e, dest);
1018 redirect_edge_var_map_clear (e);
1019 continue;
1020 }
1021
1022 /* PHI arguments are different. Create a forwarder block by
1023 splitting E so that we can merge PHI arguments on E to
1024 DEST. */
1025 e = single_succ_edge (split_edge (e));
1026 }
1027 else
1028 {
1029 /* If we merge the forwarder into a loop header verify if we
1030 are creating another loop latch edge. If so, reset
1031 number of iteration information of the loop. */
1032 if (dest->loop_father->header == dest
1033 && dominated_by_p (CDI_DOMINATORS, e->src, dest))
1034 {
1035 dest->loop_father->any_upper_bound = false;
1036 dest->loop_father->any_likely_upper_bound = false;
1037 free_numbers_of_iterations_estimates (dest->loop_father);
1038 }
1039 }
1040
1041 s = redirect_edge_and_branch (e, dest);
1042
1043 /* redirect_edge_and_branch must not create a new edge. */
1044 gcc_assert (s == e);
1045
1046 /* Add to the PHI nodes at DEST each PHI argument removed at the
1047 destination of E. */
1048 for (gsi = gsi_start_phis (dest);
1049 !gsi_end_p (gsi);
1050 gsi_next (&gsi))
1051 {
1052 gphi *phi = gsi.phi ();
1053 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
1054 source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
1055
1056 if (TREE_CODE (def) == SSA_NAME)
1057 {
1058 /* If DEF is one of the results of PHI nodes removed during
1059 redirection, replace it with the PHI argument that used
1060 to be on E. */
1061 vec<edge_var_map> *head = redirect_edge_var_map_vector (e);
1062 size_t length = head ? head->length () : 0;
1063 for (size_t i = 0; i < length; i++)
1064 {
1065 edge_var_map *vm = &(*head)[i];
1066 tree old_arg = redirect_edge_var_map_result (vm);
1067 tree new_arg = redirect_edge_var_map_def (vm);
1068
1069 if (def == old_arg)
1070 {
1071 def = new_arg;
1072 locus = redirect_edge_var_map_location (vm);
1073 break;
1074 }
1075 }
1076 }
1077
1078 add_phi_arg (phi, def, s, locus);
1079 }
1080
1081 redirect_edge_var_map_clear (e);
1082 }
1083
1084 /* Update the dominators. */
1085 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
1086 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
1087 if (domdest == bb)
1088 {
1089 /* Shortcut to avoid calling (relatively expensive)
1090 nearest_common_dominator unless necessary. */
1091 dom = dombb;
1092 }
1093 else
1094 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
1095
1096 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
1097
1098 /* Adjust latch infomation of BB's parent loop as otherwise
1099 the cfg hook has a hard time not to kill the loop. */
1100 if (current_loops && bb->loop_father->latch == bb)
1101 bb->loop_father->latch = pred;
1102
1103 /* Remove BB since all of BB's incoming edges have been redirected
1104 to DEST. */
1105 delete_basic_block (bb);
1106
1107 return true;
1108}
1109
1110/* This pass merges PHI nodes if one feeds into another. For example,
1111 suppose we have the following:
1112
1113 goto <bb 9> (<L9>);
1114
1115<L8>:;
1116 tem_17 = foo ();
1117
1118 # tem_6 = PHI <tem_17(8), tem_23(7)>;
1119<L9>:;
1120
1121 # tem_3 = PHI <tem_6(9), tem_2(5)>;
1122<L10>:;
1123
1124 Then we merge the first PHI node into the second one like so:
1125
1126 goto <bb 9> (<L10>);
1127
1128<L8>:;
1129 tem_17 = foo ();
1130
1131 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
1132<L10>:;
1133*/
1134
1135namespace {
1136
1137const pass_data pass_data_merge_phi =
1138{
1139 GIMPLE_PASS, /* type */
1140 "mergephi", /* name */
1141 OPTGROUP_NONE, /* optinfo_flags */
1142 TV_TREE_MERGE_PHI, /* tv_id */
1143 ( PROP_cfg | PROP_ssa ), /* properties_required */
1144 0, /* properties_provided */
1145 0, /* properties_destroyed */
1146 0, /* todo_flags_start */
1147 0, /* todo_flags_finish */
1148};
1149
1150class pass_merge_phi : public gimple_opt_pass
1151{
1152public:
1153 pass_merge_phi (gcc::context *ctxt)
1154 : gimple_opt_pass (pass_data_merge_phi, ctxt)
1155 {}
1156
1157 /* opt_pass methods: */
1158 opt_pass * clone () { return new pass_merge_phi (m_ctxt); }
1159 virtual unsigned int execute (function *);
1160
1161}; // class pass_merge_phi
1162
1163unsigned int
1164pass_merge_phi::execute (function *fun)
1165{
1166 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
1167 basic_block *current = worklist;
1168 basic_block bb;
1169
1170 calculate_dominance_info (CDI_DOMINATORS);
1171
1172 /* Find all PHI nodes that we may be able to merge. */
1173 FOR_EACH_BB_FN (bb, fun)
1174 {
1175 basic_block dest;
1176
1177 /* Look for a forwarder block with PHI nodes. */
1178 if (!tree_forwarder_block_p (bb, true))
1179 continue;
1180
1181 dest = single_succ (bb);
1182
1183 /* We have to feed into another basic block with PHI
1184 nodes. */
1185 if (gimple_seq_empty_p (phi_nodes (dest))
1186 /* We don't want to deal with a basic block with
1187 abnormal edges. */
1188 || bb_has_abnormal_pred (bb))
1189 continue;
1190
1191 if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
1192 {
1193 /* If BB does not dominate DEST, then the PHI nodes at
1194 DEST must be the only users of the results of the PHI
1195 nodes at BB. */
1196 *current++ = bb;
1197 }
1198 else
1199 {
1200 gphi_iterator gsi;
1201 unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
1202
1203 /* BB dominates DEST. There may be many users of the PHI
1204 nodes in BB. However, there is still a trivial case we
1205 can handle. If the result of every PHI in BB is used
1206 only by a PHI in DEST, then we can trivially merge the
1207 PHI nodes from BB into DEST. */
1208 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1209 gsi_next (&gsi))
1210 {
1211 gphi *phi = gsi.phi ();
1212 tree result = gimple_phi_result (phi);
1213 use_operand_p imm_use;
1214 gimple *use_stmt;
1215
1216 /* If the PHI's result is never used, then we can just
1217 ignore it. */
1218 if (has_zero_uses (result))
1219 continue;
1220
1221 /* Get the single use of the result of this PHI node. */
1222 if (!single_imm_use (result, &imm_use, &use_stmt)
1223 || gimple_code (use_stmt) != GIMPLE_PHI
1224 || gimple_bb (use_stmt) != dest
1225 || gimple_phi_arg_def (use_stmt, dest_idx) != result)
1226 break;
1227 }
1228
1229 /* If the loop above iterated through all the PHI nodes
1230 in BB, then we can merge the PHIs from BB into DEST. */
1231 if (gsi_end_p (gsi))
1232 *current++ = bb;
1233 }
1234 }
1235
1236 /* Now let's drain WORKLIST. */
1237 bool changed = false;
1238 while (current != worklist)
1239 {
1240 bb = *--current;
1241 changed |= remove_forwarder_block_with_phi (bb);
1242 }
1243 free (worklist);
1244
1245 /* Removing forwarder blocks can cause formerly irreducible loops
1246 to become reducible if we merged two entry blocks. */
1247 if (changed
1248 && current_loops)
1249 loops_state_set (LOOPS_NEED_FIXUP);
1250
1251 return 0;
1252}
1253
1254} // anon namespace
1255
1256gimple_opt_pass *
1257make_pass_merge_phi (gcc::context *ctxt)
1258{
1259 return new pass_merge_phi (ctxt);
1260}
1261
1262/* Pass: cleanup the CFG just before expanding trees to RTL.
1263 This is just a round of label cleanups and case node grouping
1264 because after the tree optimizers have run such cleanups may
1265 be necessary. */
1266
1267static unsigned int
1268execute_cleanup_cfg_post_optimizing (void)
1269{
1270 unsigned int todo = execute_fixup_cfg ();
1271 if (cleanup_tree_cfg ())
1272 {
1273 todo &= ~TODO_cleanup_cfg;
1274 todo |= TODO_update_ssa;
1275 }
1276 maybe_remove_unreachable_handlers ();
1277 cleanup_dead_labels ();
1278 if (group_case_labels ())
1279 todo |= TODO_cleanup_cfg;
1280 if ((flag_compare_debug_opt || flag_compare_debug)
1281 && flag_dump_final_insns)
1282 {
1283 FILE *final_output = fopen (flag_dump_final_insns, "a");
1284
1285 if (!final_output)
1286 {
1287 error ("could not open final insn dump file %qs: %m",
1288 flag_dump_final_insns);
1289 flag_dump_final_insns = NULL;
1290 }
1291 else
1292 {
1293 int save_unnumbered = flag_dump_unnumbered;
1294 int save_noaddr = flag_dump_noaddr;
1295
1296 flag_dump_noaddr = flag_dump_unnumbered = 1;
1297 fprintf (final_output, "\n");
1298 dump_enumerated_decls (final_output,
1299 dump_flags | TDF_SLIM | TDF_NOUID);
1300 flag_dump_noaddr = save_noaddr;
1301 flag_dump_unnumbered = save_unnumbered;
1302 if (fclose (final_output))
1303 {
1304 error ("could not close final insn dump file %qs: %m",
1305 flag_dump_final_insns);
1306 flag_dump_final_insns = NULL;
1307 }
1308 }
1309 }
1310 return todo;
1311}
1312
1313namespace {
1314
1315const pass_data pass_data_cleanup_cfg_post_optimizing =
1316{
1317 GIMPLE_PASS, /* type */
1318 "optimized", /* name */
1319 OPTGROUP_NONE, /* optinfo_flags */
1320 TV_TREE_CLEANUP_CFG, /* tv_id */
1321 PROP_cfg, /* properties_required */
1322 0, /* properties_provided */
1323 0, /* properties_destroyed */
1324 0, /* todo_flags_start */
1325 TODO_remove_unused_locals, /* todo_flags_finish */
1326};
1327
1328class pass_cleanup_cfg_post_optimizing : public gimple_opt_pass
1329{
1330public:
1331 pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1332 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing, ctxt)
1333 {}
1334
1335 /* opt_pass methods: */
1336 virtual unsigned int execute (function *)
1337 {
1338 return execute_cleanup_cfg_post_optimizing ();
1339 }
1340
1341}; // class pass_cleanup_cfg_post_optimizing
1342
1343} // anon namespace
1344
1345gimple_opt_pass *
1346make_pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1347{
1348 return new pass_cleanup_cfg_post_optimizing (ctxt);
1349}
1350
1351
1352