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