1 /* CFG cleanup for trees.
2 Copyright (C) 2001-2018 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 "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. */
55 bitmap cfgcleanup_altered_bbs;
56
57 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
58
59 static bool
remove_fallthru_edge(vec<edge,va_gc> * ev)60 remove_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
80 static bool
convert_single_case_switch(gswitch * swtch,gimple_stmt_iterator & gsi)81 convert_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
124 static bool
cleanup_control_expr_graph(basic_block bb,gimple_stmt_iterator gsi)125 cleanup_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
208 static void
cleanup_call_ctrl_altering_flag(gimple * bb_end)209 cleanup_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
225 static bool
cleanup_control_flow_bb(basic_block bb)226 cleanup_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
318 static bool
tree_forwarder_block_p(basic_block bb,bool phi_wanted)319 tree_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
417 static bool
phi_alternatives_equal(basic_block dest,edge e1,edge e2)418 phi_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
442 static bool
remove_forwarder_block(basic_block bb)443 remove_forwarder_block (basic_block bb)
444 {
445 edge succ = single_succ_edge (bb), e, s;
446 basic_block dest = succ->dest;
447 gimple *stmt;
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 stmt = first_stmt (dest);
461 if (stmt)
462 if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
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 stmt = gsi_stmt (gsi);
544 if (is_gimple_debug (stmt))
545 break;
546
547 /* Forwarder blocks can only contain labels and debug stmts, and
548 labels must come first, so if we get to this point, we know
549 we're looking at a label. */
550 tree decl = gimple_label_label (as_a <glabel *> (stmt));
551 if (EH_LANDING_PAD_NR (decl) != 0
552 || DECL_NONLOCAL (decl)
553 || FORCED_LABEL (decl)
554 || !DECL_ARTIFICIAL (decl))
555 gsi_move_before (&gsi, &gsi_to);
556 else
557 gsi_next (&gsi);
558 }
559
560 /* Move debug statements if the destination has a single predecessor. */
561 if (can_move_debug_stmts && !gsi_end_p (gsi))
562 {
563 gsi_to = gsi_after_labels (dest);
564 do
565 {
566 gimple *debug = gsi_stmt (gsi);
567 gcc_assert (is_gimple_debug (debug));
568 gsi_move_before (&gsi, &gsi_to);
569 }
570 while (!gsi_end_p (gsi));
571 }
572
573 bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
574
575 /* Update the dominators. */
576 if (dom_info_available_p (CDI_DOMINATORS))
577 {
578 basic_block dom, dombb, domdest;
579
580 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
581 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
582 if (domdest == bb)
583 {
584 /* Shortcut to avoid calling (relatively expensive)
585 nearest_common_dominator unless necessary. */
586 dom = dombb;
587 }
588 else
589 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
590
591 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
592 }
593
594 /* Adjust latch infomation of BB's parent loop as otherwise
595 the cfg hook has a hard time not to kill the loop. */
596 if (current_loops && bb->loop_father->latch == bb)
597 bb->loop_father->latch = pred;
598
599 /* And kill the forwarder block. */
600 delete_basic_block (bb);
601
602 return true;
603 }
604
605 /* STMT is a call that has been discovered noreturn. Split the
606 block to prepare fixing up the CFG and remove LHS.
607 Return true if cleanup-cfg needs to run. */
608
609 bool
fixup_noreturn_call(gimple * stmt)610 fixup_noreturn_call (gimple *stmt)
611 {
612 basic_block bb = gimple_bb (stmt);
613 bool changed = false;
614
615 if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
616 return false;
617
618 /* First split basic block if stmt is not last. */
619 if (stmt != gsi_stmt (gsi_last_bb (bb)))
620 {
621 if (stmt == gsi_stmt (gsi_last_nondebug_bb (bb)))
622 {
623 /* Don't split if there are only debug stmts
624 after stmt, that can result in -fcompare-debug
625 failures. Remove the debug stmts instead,
626 they should be all unreachable anyway. */
627 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
628 for (gsi_next (&gsi); !gsi_end_p (gsi); )
629 gsi_remove (&gsi, true);
630 }
631 else
632 {
633 split_block (bb, stmt);
634 changed = true;
635 }
636 }
637
638 /* If there is an LHS, remove it, but only if its type has fixed size.
639 The LHS will need to be recreated during RTL expansion and creating
640 temporaries of variable-sized types is not supported. Also don't
641 do this with TREE_ADDRESSABLE types, as assign_temp will abort.
642 Drop LHS regardless of TREE_ADDRESSABLE, if the function call
643 has been changed into a call that does not return a value, like
644 __builtin_unreachable or __cxa_pure_virtual. */
645 tree lhs = gimple_call_lhs (stmt);
646 if (lhs
647 && (should_remove_lhs_p (lhs)
648 || VOID_TYPE_P (TREE_TYPE (gimple_call_fntype (stmt)))))
649 {
650 gimple_call_set_lhs (stmt, NULL_TREE);
651
652 /* We need to fix up the SSA name to avoid checking errors. */
653 if (TREE_CODE (lhs) == SSA_NAME)
654 {
655 tree new_var = create_tmp_reg (TREE_TYPE (lhs));
656 SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs, new_var);
657 SSA_NAME_DEF_STMT (lhs) = gimple_build_nop ();
658 set_ssa_default_def (cfun, new_var, lhs);
659 }
660
661 update_stmt (stmt);
662 }
663
664 /* Mark the call as altering control flow. */
665 if (!gimple_call_ctrl_altering_p (stmt))
666 {
667 gimple_call_set_ctrl_altering (stmt, true);
668 changed = true;
669 }
670
671 return changed;
672 }
673
674 /* Return true if we want to merge BB1 and BB2 into a single block. */
675
676 static bool
want_merge_blocks_p(basic_block bb1,basic_block bb2)677 want_merge_blocks_p (basic_block bb1, basic_block bb2)
678 {
679 if (!can_merge_blocks_p (bb1, bb2))
680 return false;
681 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb1);
682 if (gsi_end_p (gsi) || !stmt_can_terminate_bb_p (gsi_stmt (gsi)))
683 return true;
684 return bb1->count.ok_for_merging (bb2->count);
685 }
686
687
688 /* Tries to cleanup cfg in basic block BB. Returns true if anything
689 changes. */
690
691 static bool
cleanup_tree_cfg_bb(basic_block bb)692 cleanup_tree_cfg_bb (basic_block bb)
693 {
694 if (tree_forwarder_block_p (bb, false)
695 && remove_forwarder_block (bb))
696 return true;
697
698 /* If there is a merge opportunity with the predecessor
699 do nothing now but wait until we process the predecessor.
700 This happens when we visit BBs in a non-optimal order and
701 avoids quadratic behavior with adjusting stmts BB pointer. */
702 if (single_pred_p (bb)
703 && want_merge_blocks_p (single_pred (bb), bb))
704 /* But make sure we _do_ visit it. When we remove unreachable paths
705 ending in a backedge we fail to mark the destinations predecessors
706 as changed. */
707 bitmap_set_bit (cfgcleanup_altered_bbs, single_pred (bb)->index);
708
709 /* Merging the blocks may create new opportunities for folding
710 conditional branches (due to the elimination of single-valued PHI
711 nodes). */
712 else if (single_succ_p (bb)
713 && want_merge_blocks_p (bb, single_succ (bb)))
714 {
715 merge_blocks (bb, single_succ (bb));
716 return true;
717 }
718
719 return false;
720 }
721
722 /* Do cleanup_control_flow_bb in PRE order. */
723
724 static bool
cleanup_control_flow_pre()725 cleanup_control_flow_pre ()
726 {
727 bool retval = false;
728
729 auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
730 auto_sbitmap visited (last_basic_block_for_fn (cfun));
731 bitmap_clear (visited);
732
733 stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
734
735 while (! stack.is_empty ())
736 {
737 /* Look at the edge on the top of the stack. */
738 edge_iterator ei = stack.last ();
739 basic_block dest = ei_edge (ei)->dest;
740
741 if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
742 && ! bitmap_bit_p (visited, dest->index))
743 {
744 bitmap_set_bit (visited, dest->index);
745 retval |= cleanup_control_flow_bb (dest);
746 if (EDGE_COUNT (dest->succs) > 0)
747 stack.quick_push (ei_start (dest->succs));
748 }
749 else
750 {
751 if (!ei_one_before_end_p (ei))
752 ei_next (&stack.last ());
753 else
754 stack.pop ();
755 }
756 }
757
758 return retval;
759 }
760
761 /* Iterate the cfg cleanups, while anything changes. */
762
763 static bool
cleanup_tree_cfg_1(void)764 cleanup_tree_cfg_1 (void)
765 {
766 bool retval = false;
767 basic_block bb;
768 unsigned i, n;
769
770 /* Prepare the worklists of altered blocks. */
771 cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
772
773 /* During forwarder block cleanup, we may redirect edges out of
774 SWITCH_EXPRs, which can get expensive. So we want to enable
775 recording of edge to CASE_LABEL_EXPR. */
776 start_recording_case_labels ();
777
778 /* We cannot use FOR_EACH_BB_FN for the BB iterations below
779 since the basic blocks may get removed. */
780
781 /* Start by iterating over all basic blocks in PRE order looking for
782 edge removal opportunities. Do this first because incoming SSA form
783 may be invalid and we want to avoid performing SSA related tasks such
784 as propgating out a PHI node during BB merging in that state. */
785 retval |= cleanup_control_flow_pre ();
786
787 /* After doing the above SSA form should be valid (or an update SSA
788 should be required). */
789
790 /* Continue by iterating over all basic blocks looking for BB merging
791 opportunities. */
792 n = last_basic_block_for_fn (cfun);
793 for (i = NUM_FIXED_BLOCKS; i < n; i++)
794 {
795 bb = BASIC_BLOCK_FOR_FN (cfun, i);
796 if (bb)
797 retval |= cleanup_tree_cfg_bb (bb);
798 }
799
800 /* Now process the altered blocks, as long as any are available. */
801 while (!bitmap_empty_p (cfgcleanup_altered_bbs))
802 {
803 i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
804 bitmap_clear_bit (cfgcleanup_altered_bbs, i);
805 if (i < NUM_FIXED_BLOCKS)
806 continue;
807
808 bb = BASIC_BLOCK_FOR_FN (cfun, i);
809 if (!bb)
810 continue;
811
812 retval |= cleanup_control_flow_bb (bb);
813 retval |= cleanup_tree_cfg_bb (bb);
814 }
815
816 end_recording_case_labels ();
817 BITMAP_FREE (cfgcleanup_altered_bbs);
818 return retval;
819 }
820
821 static bool
mfb_keep_latches(edge e)822 mfb_keep_latches (edge e)
823 {
824 return ! dominated_by_p (CDI_DOMINATORS, e->src, e->dest);
825 }
826
827 /* Remove unreachable blocks and other miscellaneous clean up work.
828 Return true if the flowgraph was modified, false otherwise. */
829
830 static bool
cleanup_tree_cfg_noloop(void)831 cleanup_tree_cfg_noloop (void)
832 {
833 bool changed;
834
835 timevar_push (TV_TREE_CLEANUP_CFG);
836
837 /* Iterate until there are no more cleanups left to do. If any
838 iteration changed the flowgraph, set CHANGED to true.
839
840 If dominance information is available, there cannot be any unreachable
841 blocks. */
842 if (!dom_info_available_p (CDI_DOMINATORS))
843 {
844 changed = delete_unreachable_blocks ();
845 calculate_dominance_info (CDI_DOMINATORS);
846 }
847 else
848 {
849 checking_verify_dominators (CDI_DOMINATORS);
850 changed = false;
851 }
852
853 /* Ensure that we have single entries into loop headers. Otherwise
854 if one of the entries is becoming a latch due to CFG cleanup
855 (from formerly being part of an irreducible region) then we mess
856 up loop fixup and associate the old loop with a different region
857 which makes niter upper bounds invalid. See for example PR80549.
858 This needs to be done before we remove trivially dead edges as
859 we need to capture the dominance state before the pending transform. */
860 if (current_loops)
861 {
862 loop_p loop;
863 unsigned i;
864 FOR_EACH_VEC_ELT (*get_loops (cfun), i, loop)
865 if (loop && loop->header)
866 {
867 basic_block bb = loop->header;
868 edge_iterator ei;
869 edge e;
870 bool found_latch = false;
871 bool any_abnormal = false;
872 unsigned n = 0;
873 /* We are only interested in preserving existing loops, but
874 we need to check whether they are still real and of course
875 if we need to add a preheader at all. */
876 FOR_EACH_EDGE (e, ei, bb->preds)
877 {
878 if (e->flags & EDGE_ABNORMAL)
879 {
880 any_abnormal = true;
881 break;
882 }
883 if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
884 {
885 found_latch = true;
886 continue;
887 }
888 n++;
889 }
890 /* If we have more than one entry to the loop header
891 create a forwarder. */
892 if (found_latch && ! any_abnormal && n > 1)
893 {
894 edge fallthru = make_forwarder_block (bb, mfb_keep_latches,
895 NULL);
896 loop->header = fallthru->dest;
897 if (! loops_state_satisfies_p (LOOPS_NEED_FIXUP))
898 {
899 /* The loop updating from the CFG hook is incomplete
900 when we have multiple latches, fixup manually. */
901 remove_bb_from_loops (fallthru->src);
902 loop_p cloop = loop;
903 FOR_EACH_EDGE (e, ei, fallthru->src->preds)
904 cloop = find_common_loop (cloop, e->src->loop_father);
905 add_bb_to_loop (fallthru->src, cloop);
906 }
907 }
908 }
909 }
910
911 changed |= cleanup_tree_cfg_1 ();
912
913 gcc_assert (dom_info_available_p (CDI_DOMINATORS));
914
915 /* Do not renumber blocks if the SCEV cache is active, it is indexed by
916 basic-block numbers. */
917 if (! scev_initialized_p ())
918 compact_blocks ();
919
920 checking_verify_flow_info ();
921
922 timevar_pop (TV_TREE_CLEANUP_CFG);
923
924 if (changed && current_loops)
925 {
926 /* Removing edges and/or blocks may make recorded bounds refer
927 to stale GIMPLE stmts now, so clear them. */
928 free_numbers_of_iterations_estimates (cfun);
929 loops_state_set (LOOPS_NEED_FIXUP);
930 }
931
932 return changed;
933 }
934
935 /* Repairs loop structures. */
936
937 static void
repair_loop_structures(void)938 repair_loop_structures (void)
939 {
940 bitmap changed_bbs;
941 unsigned n_new_loops;
942
943 calculate_dominance_info (CDI_DOMINATORS);
944
945 timevar_push (TV_REPAIR_LOOPS);
946 changed_bbs = BITMAP_ALLOC (NULL);
947 n_new_loops = fix_loop_structure (changed_bbs);
948
949 /* This usually does nothing. But sometimes parts of cfg that originally
950 were inside a loop get out of it due to edge removal (since they
951 become unreachable by back edges from latch). Also a former
952 irreducible loop can become reducible - in this case force a full
953 rewrite into loop-closed SSA form. */
954 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
955 rewrite_into_loop_closed_ssa (n_new_loops ? NULL : changed_bbs,
956 TODO_update_ssa);
957
958 BITMAP_FREE (changed_bbs);
959
960 checking_verify_loop_structure ();
961 scev_reset ();
962
963 timevar_pop (TV_REPAIR_LOOPS);
964 }
965
966 /* Cleanup cfg and repair loop structures. */
967
968 bool
cleanup_tree_cfg(void)969 cleanup_tree_cfg (void)
970 {
971 bool changed = cleanup_tree_cfg_noloop ();
972
973 if (current_loops != NULL
974 && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
975 repair_loop_structures ();
976
977 return changed;
978 }
979
980 /* Tries to merge the PHI nodes at BB into those at BB's sole successor.
981 Returns true if successful. */
982
983 static bool
remove_forwarder_block_with_phi(basic_block bb)984 remove_forwarder_block_with_phi (basic_block bb)
985 {
986 edge succ = single_succ_edge (bb);
987 basic_block dest = succ->dest;
988 gimple *label;
989 basic_block dombb, domdest, dom;
990
991 /* We check for infinite loops already in tree_forwarder_block_p.
992 However it may happen that the infinite loop is created
993 afterwards due to removal of forwarders. */
994 if (dest == bb)
995 return false;
996
997 /* Removal of forwarders may expose new natural loops and thus
998 a block may turn into a loop header. */
999 if (current_loops && bb_loop_header_p (bb))
1000 return false;
1001
1002 /* If the destination block consists of a nonlocal label, do not
1003 merge it. */
1004 label = first_stmt (dest);
1005 if (label)
1006 if (glabel *label_stmt = dyn_cast <glabel *> (label))
1007 if (DECL_NONLOCAL (gimple_label_label (label_stmt)))
1008 return false;
1009
1010 /* Record BB's single pred in case we need to update the father
1011 loop's latch information later. */
1012 basic_block pred = NULL;
1013 if (single_pred_p (bb))
1014 pred = single_pred (bb);
1015
1016 /* Redirect each incoming edge to BB to DEST. */
1017 while (EDGE_COUNT (bb->preds) > 0)
1018 {
1019 edge e = EDGE_PRED (bb, 0), s;
1020 gphi_iterator gsi;
1021
1022 s = find_edge (e->src, dest);
1023 if (s)
1024 {
1025 /* We already have an edge S from E->src to DEST. If S and
1026 E->dest's sole successor edge have the same PHI arguments
1027 at DEST, redirect S to DEST. */
1028 if (phi_alternatives_equal (dest, s, succ))
1029 {
1030 e = redirect_edge_and_branch (e, dest);
1031 redirect_edge_var_map_clear (e);
1032 continue;
1033 }
1034
1035 /* PHI arguments are different. Create a forwarder block by
1036 splitting E so that we can merge PHI arguments on E to
1037 DEST. */
1038 e = single_succ_edge (split_edge (e));
1039 }
1040 else
1041 {
1042 /* If we merge the forwarder into a loop header verify if we
1043 are creating another loop latch edge. If so, reset
1044 number of iteration information of the loop. */
1045 if (dest->loop_father->header == dest
1046 && dominated_by_p (CDI_DOMINATORS, e->src, dest))
1047 {
1048 dest->loop_father->any_upper_bound = false;
1049 dest->loop_father->any_likely_upper_bound = false;
1050 free_numbers_of_iterations_estimates (dest->loop_father);
1051 }
1052 }
1053
1054 s = redirect_edge_and_branch (e, dest);
1055
1056 /* redirect_edge_and_branch must not create a new edge. */
1057 gcc_assert (s == e);
1058
1059 /* Add to the PHI nodes at DEST each PHI argument removed at the
1060 destination of E. */
1061 for (gsi = gsi_start_phis (dest);
1062 !gsi_end_p (gsi);
1063 gsi_next (&gsi))
1064 {
1065 gphi *phi = gsi.phi ();
1066 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
1067 source_location locus = gimple_phi_arg_location_from_edge (phi, succ);
1068
1069 if (TREE_CODE (def) == SSA_NAME)
1070 {
1071 /* If DEF is one of the results of PHI nodes removed during
1072 redirection, replace it with the PHI argument that used
1073 to be on E. */
1074 vec<edge_var_map> *head = redirect_edge_var_map_vector (e);
1075 size_t length = head ? head->length () : 0;
1076 for (size_t i = 0; i < length; i++)
1077 {
1078 edge_var_map *vm = &(*head)[i];
1079 tree old_arg = redirect_edge_var_map_result (vm);
1080 tree new_arg = redirect_edge_var_map_def (vm);
1081
1082 if (def == old_arg)
1083 {
1084 def = new_arg;
1085 locus = redirect_edge_var_map_location (vm);
1086 break;
1087 }
1088 }
1089 }
1090
1091 add_phi_arg (phi, def, s, locus);
1092 }
1093
1094 redirect_edge_var_map_clear (e);
1095 }
1096
1097 /* Update the dominators. */
1098 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
1099 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
1100 if (domdest == bb)
1101 {
1102 /* Shortcut to avoid calling (relatively expensive)
1103 nearest_common_dominator unless necessary. */
1104 dom = dombb;
1105 }
1106 else
1107 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
1108
1109 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
1110
1111 /* Adjust latch infomation of BB's parent loop as otherwise
1112 the cfg hook has a hard time not to kill the loop. */
1113 if (current_loops && bb->loop_father->latch == bb)
1114 bb->loop_father->latch = pred;
1115
1116 /* Remove BB since all of BB's incoming edges have been redirected
1117 to DEST. */
1118 delete_basic_block (bb);
1119
1120 return true;
1121 }
1122
1123 /* This pass merges PHI nodes if one feeds into another. For example,
1124 suppose we have the following:
1125
1126 goto <bb 9> (<L9>);
1127
1128 <L8>:;
1129 tem_17 = foo ();
1130
1131 # tem_6 = PHI <tem_17(8), tem_23(7)>;
1132 <L9>:;
1133
1134 # tem_3 = PHI <tem_6(9), tem_2(5)>;
1135 <L10>:;
1136
1137 Then we merge the first PHI node into the second one like so:
1138
1139 goto <bb 9> (<L10>);
1140
1141 <L8>:;
1142 tem_17 = foo ();
1143
1144 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
1145 <L10>:;
1146 */
1147
1148 namespace {
1149
1150 const pass_data pass_data_merge_phi =
1151 {
1152 GIMPLE_PASS, /* type */
1153 "mergephi", /* name */
1154 OPTGROUP_NONE, /* optinfo_flags */
1155 TV_TREE_MERGE_PHI, /* tv_id */
1156 ( PROP_cfg | PROP_ssa ), /* properties_required */
1157 0, /* properties_provided */
1158 0, /* properties_destroyed */
1159 0, /* todo_flags_start */
1160 0, /* todo_flags_finish */
1161 };
1162
1163 class pass_merge_phi : public gimple_opt_pass
1164 {
1165 public:
pass_merge_phi(gcc::context * ctxt)1166 pass_merge_phi (gcc::context *ctxt)
1167 : gimple_opt_pass (pass_data_merge_phi, ctxt)
1168 {}
1169
1170 /* opt_pass methods: */
clone()1171 opt_pass * clone () { return new pass_merge_phi (m_ctxt); }
1172 virtual unsigned int execute (function *);
1173
1174 }; // class pass_merge_phi
1175
1176 unsigned int
execute(function * fun)1177 pass_merge_phi::execute (function *fun)
1178 {
1179 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
1180 basic_block *current = worklist;
1181 basic_block bb;
1182
1183 calculate_dominance_info (CDI_DOMINATORS);
1184
1185 /* Find all PHI nodes that we may be able to merge. */
1186 FOR_EACH_BB_FN (bb, fun)
1187 {
1188 basic_block dest;
1189
1190 /* Look for a forwarder block with PHI nodes. */
1191 if (!tree_forwarder_block_p (bb, true))
1192 continue;
1193
1194 dest = single_succ (bb);
1195
1196 /* We have to feed into another basic block with PHI
1197 nodes. */
1198 if (gimple_seq_empty_p (phi_nodes (dest))
1199 /* We don't want to deal with a basic block with
1200 abnormal edges. */
1201 || bb_has_abnormal_pred (bb))
1202 continue;
1203
1204 if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
1205 {
1206 /* If BB does not dominate DEST, then the PHI nodes at
1207 DEST must be the only users of the results of the PHI
1208 nodes at BB. */
1209 *current++ = bb;
1210 }
1211 else
1212 {
1213 gphi_iterator gsi;
1214 unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
1215
1216 /* BB dominates DEST. There may be many users of the PHI
1217 nodes in BB. However, there is still a trivial case we
1218 can handle. If the result of every PHI in BB is used
1219 only by a PHI in DEST, then we can trivially merge the
1220 PHI nodes from BB into DEST. */
1221 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1222 gsi_next (&gsi))
1223 {
1224 gphi *phi = gsi.phi ();
1225 tree result = gimple_phi_result (phi);
1226 use_operand_p imm_use;
1227 gimple *use_stmt;
1228
1229 /* If the PHI's result is never used, then we can just
1230 ignore it. */
1231 if (has_zero_uses (result))
1232 continue;
1233
1234 /* Get the single use of the result of this PHI node. */
1235 if (!single_imm_use (result, &imm_use, &use_stmt)
1236 || gimple_code (use_stmt) != GIMPLE_PHI
1237 || gimple_bb (use_stmt) != dest
1238 || gimple_phi_arg_def (use_stmt, dest_idx) != result)
1239 break;
1240 }
1241
1242 /* If the loop above iterated through all the PHI nodes
1243 in BB, then we can merge the PHIs from BB into DEST. */
1244 if (gsi_end_p (gsi))
1245 *current++ = bb;
1246 }
1247 }
1248
1249 /* Now let's drain WORKLIST. */
1250 bool changed = false;
1251 while (current != worklist)
1252 {
1253 bb = *--current;
1254 changed |= remove_forwarder_block_with_phi (bb);
1255 }
1256 free (worklist);
1257
1258 /* Removing forwarder blocks can cause formerly irreducible loops
1259 to become reducible if we merged two entry blocks. */
1260 if (changed
1261 && current_loops)
1262 loops_state_set (LOOPS_NEED_FIXUP);
1263
1264 return 0;
1265 }
1266
1267 } // anon namespace
1268
1269 gimple_opt_pass *
make_pass_merge_phi(gcc::context * ctxt)1270 make_pass_merge_phi (gcc::context *ctxt)
1271 {
1272 return new pass_merge_phi (ctxt);
1273 }
1274
1275 /* Pass: cleanup the CFG just before expanding trees to RTL.
1276 This is just a round of label cleanups and case node grouping
1277 because after the tree optimizers have run such cleanups may
1278 be necessary. */
1279
1280 static unsigned int
execute_cleanup_cfg_post_optimizing(void)1281 execute_cleanup_cfg_post_optimizing (void)
1282 {
1283 unsigned int todo = execute_fixup_cfg ();
1284 if (cleanup_tree_cfg ())
1285 {
1286 todo &= ~TODO_cleanup_cfg;
1287 todo |= TODO_update_ssa;
1288 }
1289 maybe_remove_unreachable_handlers ();
1290 cleanup_dead_labels ();
1291 if (group_case_labels ())
1292 todo |= TODO_cleanup_cfg;
1293 if ((flag_compare_debug_opt || flag_compare_debug)
1294 && flag_dump_final_insns)
1295 {
1296 FILE *final_output = fopen (flag_dump_final_insns, "a");
1297
1298 if (!final_output)
1299 {
1300 error ("could not open final insn dump file %qs: %m",
1301 flag_dump_final_insns);
1302 flag_dump_final_insns = NULL;
1303 }
1304 else
1305 {
1306 int save_unnumbered = flag_dump_unnumbered;
1307 int save_noaddr = flag_dump_noaddr;
1308
1309 flag_dump_noaddr = flag_dump_unnumbered = 1;
1310 fprintf (final_output, "\n");
1311 dump_enumerated_decls (final_output,
1312 dump_flags | TDF_SLIM | TDF_NOUID);
1313 flag_dump_noaddr = save_noaddr;
1314 flag_dump_unnumbered = save_unnumbered;
1315 if (fclose (final_output))
1316 {
1317 error ("could not close final insn dump file %qs: %m",
1318 flag_dump_final_insns);
1319 flag_dump_final_insns = NULL;
1320 }
1321 }
1322 }
1323 return todo;
1324 }
1325
1326 namespace {
1327
1328 const pass_data pass_data_cleanup_cfg_post_optimizing =
1329 {
1330 GIMPLE_PASS, /* type */
1331 "optimized", /* name */
1332 OPTGROUP_NONE, /* optinfo_flags */
1333 TV_TREE_CLEANUP_CFG, /* tv_id */
1334 PROP_cfg, /* properties_required */
1335 0, /* properties_provided */
1336 0, /* properties_destroyed */
1337 0, /* todo_flags_start */
1338 TODO_remove_unused_locals, /* todo_flags_finish */
1339 };
1340
1341 class pass_cleanup_cfg_post_optimizing : public gimple_opt_pass
1342 {
1343 public:
pass_cleanup_cfg_post_optimizing(gcc::context * ctxt)1344 pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1345 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing, ctxt)
1346 {}
1347
1348 /* opt_pass methods: */
execute(function *)1349 virtual unsigned int execute (function *)
1350 {
1351 return execute_cleanup_cfg_post_optimizing ();
1352 }
1353
1354 }; // class pass_cleanup_cfg_post_optimizing
1355
1356 } // anon namespace
1357
1358 gimple_opt_pass *
make_pass_cleanup_cfg_post_optimizing(gcc::context * ctxt)1359 make_pass_cleanup_cfg_post_optimizing (gcc::context *ctxt)
1360 {
1361 return new pass_cleanup_cfg_post_optimizing (ctxt);
1362 }
1363
1364
1365