1 /* CFG cleanup for trees.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to
18 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
19 Boston, MA 02110-1301, USA. */
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
36 #include "langhooks.h"
37 #include "diagnostic.h"
38 #include "tree-flow.h"
40 #include "tree-dump.h"
41 #include "tree-pass.h"
45 #include "cfglayout.h"
47 #include "tree-ssa-propagate.h"
49 /* Remove any fallthru edge from EV. Return true if an edge was removed. */
52 remove_fallthru_edge (VEC(edge
,gc
) *ev
)
57 FOR_EACH_EDGE (e
, ei
, ev
)
58 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
66 /* Disconnect an unreachable block in the control expression starting
70 cleanup_control_expr_graph (basic_block bb
, block_stmt_iterator bsi
)
74 tree expr
= bsi_stmt (bsi
), val
;
76 if (!single_succ_p (bb
))
81 switch (TREE_CODE (expr
))
84 val
= COND_EXPR_COND (expr
);
88 val
= SWITCH_COND (expr
);
89 if (TREE_CODE (val
) != INTEGER_CST
)
97 taken_edge
= find_taken_edge (bb
, val
);
101 /* Remove all the edges except the one that is always executed. */
102 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
106 taken_edge
->probability
+= e
->probability
;
107 taken_edge
->count
+= e
->count
;
114 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
115 taken_edge
->probability
= REG_BR_PROB_BASE
;
118 taken_edge
= single_succ_edge (bb
);
121 taken_edge
->flags
= EDGE_FALLTHRU
;
123 /* We removed some paths from the cfg. */
124 free_dominance_info (CDI_DOMINATORS
);
129 /* A list of all the noreturn calls passed to modify_stmt.
130 cleanup_control_flow uses it to detect cases where a mid-block
131 indirect call has been turned into a noreturn call. When this
132 happens, all the instructions after the call are no longer
133 reachable and must be deleted as dead. */
135 VEC(tree
,gc
) *modified_noreturn_calls
;
137 /* Try to remove superfluous control structures. */
140 cleanup_control_flow (void)
143 block_stmt_iterator bsi
;
147 /* Detect cases where a mid-block call is now known not to return. */
148 while (VEC_length (tree
, modified_noreturn_calls
))
150 stmt
= VEC_pop (tree
, modified_noreturn_calls
);
151 bb
= bb_for_stmt (stmt
);
152 if (bb
!= NULL
&& last_stmt (bb
) != stmt
&& noreturn_call_p (stmt
))
153 split_block (bb
, stmt
);
163 stmt
= bsi_stmt (bsi
);
164 if (TREE_CODE (stmt
) == COND_EXPR
165 || TREE_CODE (stmt
) == SWITCH_EXPR
)
166 retval
|= cleanup_control_expr_graph (bb
, bsi
);
168 /* If we had a computed goto which has a compile-time determinable
169 destination, then we can eliminate the goto. */
170 if (TREE_CODE (stmt
) == GOTO_EXPR
171 && TREE_CODE (GOTO_DESTINATION (stmt
)) == ADDR_EXPR
172 && TREE_CODE (TREE_OPERAND (GOTO_DESTINATION (stmt
), 0)) == LABEL_DECL
)
177 basic_block target_block
;
178 bool removed_edge
= false;
180 /* First look at all the outgoing edges. Delete any outgoing
181 edges which do not go to the right block. For the one
182 edge which goes to the right block, fix up its flags. */
183 label
= TREE_OPERAND (GOTO_DESTINATION (stmt
), 0);
184 target_block
= label_to_block (label
);
185 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
187 if (e
->dest
!= target_block
)
194 /* Turn off the EDGE_ABNORMAL flag. */
195 e
->flags
&= ~EDGE_ABNORMAL
;
197 /* And set EDGE_FALLTHRU. */
198 e
->flags
|= EDGE_FALLTHRU
;
203 /* If we removed one or more edges, then we will need to fix the
204 dominators. It may be possible to incrementally update them. */
206 free_dominance_info (CDI_DOMINATORS
);
208 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
209 relevant information we need. */
214 /* Check for indirect calls that have been turned into
216 if (noreturn_call_p (stmt
) && remove_fallthru_edge (bb
->succs
))
218 free_dominance_info (CDI_DOMINATORS
);
225 /* Return true if basic block BB does nothing except pass control
226 flow to another block and that we can safely insert a label at
227 the start of the successor block.
229 As a precondition, we require that BB be not equal to
233 tree_forwarder_block_p (basic_block bb
, bool phi_wanted
)
235 block_stmt_iterator bsi
;
237 /* BB must have a single outgoing edge. */
238 if (single_succ_p (bb
) != 1
239 /* If PHI_WANTED is false, BB must not have any PHI nodes.
240 Otherwise, BB must have PHI nodes. */
241 || (phi_nodes (bb
) != NULL_TREE
) != phi_wanted
242 /* BB may not be a predecessor of EXIT_BLOCK_PTR. */
243 || single_succ (bb
) == EXIT_BLOCK_PTR
244 /* Nor should this be an infinite loop. */
245 || single_succ (bb
) == bb
246 /* BB may not have an abnormal outgoing edge. */
247 || (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
251 gcc_assert (bb
!= ENTRY_BLOCK_PTR
);
254 /* Now walk through the statements backward. We can ignore labels,
255 anything else means this is not a forwarder block. */
256 for (bsi
= bsi_last (bb
); !bsi_end_p (bsi
); bsi_prev (&bsi
))
258 tree stmt
= bsi_stmt (bsi
);
260 switch (TREE_CODE (stmt
))
263 if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt
)))
272 if (find_edge (ENTRY_BLOCK_PTR
, bb
))
278 /* Protect loop latches, headers and preheaders. */
279 if (bb
->loop_father
->header
== bb
)
281 dest
= EDGE_SUCC (bb
, 0)->dest
;
283 if (dest
->loop_father
->header
== dest
)
290 /* Return true if BB has at least one abnormal incoming edge. */
293 has_abnormal_incoming_edge_p (basic_block bb
)
298 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
299 if (e
->flags
& EDGE_ABNORMAL
)
305 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
306 those alternatives are equal in each of the PHI nodes, then return
307 true, else return false. */
310 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
312 int n1
= e1
->dest_idx
;
313 int n2
= e2
->dest_idx
;
316 for (phi
= phi_nodes (dest
); phi
; phi
= PHI_CHAIN (phi
))
318 tree val1
= PHI_ARG_DEF (phi
, n1
);
319 tree val2
= PHI_ARG_DEF (phi
, n2
);
321 gcc_assert (val1
!= NULL_TREE
);
322 gcc_assert (val2
!= NULL_TREE
);
324 if (!operand_equal_for_phi_arg_p (val1
, val2
))
331 /* Removes forwarder block BB. Returns false if this failed. If a new
332 forwarder block is created due to redirection of edges, it is
333 stored to worklist. */
336 remove_forwarder_block (basic_block bb
, basic_block
**worklist
)
338 edge succ
= single_succ_edge (bb
), e
, s
;
339 basic_block dest
= succ
->dest
;
343 block_stmt_iterator bsi
, bsi_to
;
344 bool seen_abnormal_edge
= false;
346 /* We check for infinite loops already in tree_forwarder_block_p.
347 However it may happen that the infinite loop is created
348 afterwards due to removal of forwarders. */
352 /* If the destination block consists of a nonlocal label, do not merge
354 label
= first_stmt (dest
);
356 && TREE_CODE (label
) == LABEL_EXPR
357 && DECL_NONLOCAL (LABEL_EXPR_LABEL (label
)))
360 /* If there is an abnormal edge to basic block BB, but not into
361 dest, problems might occur during removal of the phi node at out
362 of ssa due to overlapping live ranges of registers.
364 If there is an abnormal edge in DEST, the problems would occur
365 anyway since cleanup_dead_labels would then merge the labels for
366 two different eh regions, and rest of exception handling code
369 So if there is an abnormal edge to BB, proceed only if there is
370 no abnormal edge to DEST and there are no phi nodes in DEST. */
371 if (has_abnormal_incoming_edge_p (bb
))
373 seen_abnormal_edge
= true;
375 if (has_abnormal_incoming_edge_p (dest
)
376 || phi_nodes (dest
) != NULL_TREE
)
380 /* If there are phi nodes in DEST, and some of the blocks that are
381 predecessors of BB are also predecessors of DEST, check that the
382 phi node arguments match. */
383 if (phi_nodes (dest
))
385 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
387 s
= find_edge (e
->src
, dest
);
391 if (!phi_alternatives_equal (dest
, succ
, s
))
396 /* Redirect the edges. */
397 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
399 if (e
->flags
& EDGE_ABNORMAL
)
401 /* If there is an abnormal edge, redirect it anyway, and
402 move the labels to the new block to make it legal. */
403 s
= redirect_edge_succ_nodup (e
, dest
);
406 s
= redirect_edge_and_branch (e
, dest
);
410 /* Create arguments for the phi nodes, since the edge was not
412 for (phi
= phi_nodes (dest
); phi
; phi
= PHI_CHAIN (phi
))
413 add_phi_arg (phi
, PHI_ARG_DEF (phi
, succ
->dest_idx
), s
);
417 /* The source basic block might become a forwarder. We know
418 that it was not a forwarder before, since it used to have
419 at least two outgoing edges, so we may just add it to
421 if (tree_forwarder_block_p (s
->src
, false))
422 *(*worklist
)++ = s
->src
;
426 if (seen_abnormal_edge
)
428 /* Move the labels to the new block, so that the redirection of
429 the abnormal edges works. */
431 bsi_to
= bsi_start (dest
);
432 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); )
434 label
= bsi_stmt (bsi
);
435 gcc_assert (TREE_CODE (label
) == LABEL_EXPR
);
437 bsi_insert_before (&bsi_to
, label
, BSI_CONTINUE_LINKING
);
441 /* Update the dominators. */
442 if (dom_info_available_p (CDI_DOMINATORS
))
444 basic_block dom
, dombb
, domdest
;
446 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
447 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
450 /* Shortcut to avoid calling (relatively expensive)
451 nearest_common_dominator unless necessary. */
455 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
457 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
460 /* And kill the forwarder block. */
461 delete_basic_block (bb
);
466 /* Removes forwarder blocks. */
469 cleanup_forwarder_blocks (void)
472 bool changed
= false;
473 basic_block
*worklist
= xmalloc (sizeof (basic_block
) * n_basic_blocks
);
474 basic_block
*current
= worklist
;
478 if (tree_forwarder_block_p (bb
, false))
482 while (current
!= worklist
)
485 changed
|= remove_forwarder_block (bb
, ¤t
);
492 /* Remove unreachable blocks and other miscellaneous clean up work. */
495 cleanup_tree_cfg (void)
499 timevar_push (TV_TREE_CLEANUP_CFG
);
501 retval
= cleanup_control_flow ();
502 retval
|= delete_unreachable_blocks ();
504 /* Forwarder blocks can carry line number information which is
505 useful when debugging, so we only clean them up when
510 /* cleanup_forwarder_blocks can redirect edges out of
511 SWITCH_EXPRs, which can get expensive. So we want to enable
512 recording of edge to CASE_LABEL_EXPR mappings around the call
513 to cleanup_forwarder_blocks. */
514 start_recording_case_labels ();
515 retval
|= cleanup_forwarder_blocks ();
516 end_recording_case_labels ();
519 #ifdef ENABLE_CHECKING
522 gcc_assert (!cleanup_control_flow ());
523 gcc_assert (!delete_unreachable_blocks ());
525 gcc_assert (!cleanup_forwarder_blocks ());
529 /* Merging the blocks creates no new opportunities for the other
530 optimizations, so do it here. */
531 retval
|= merge_seq_blocks ();
535 #ifdef ENABLE_CHECKING
538 timevar_pop (TV_TREE_CLEANUP_CFG
);
542 /* Cleanup cfg and repair loop structures. */
545 cleanup_tree_cfg_loop (void)
547 bitmap changed_bbs
= BITMAP_ALLOC (NULL
);
551 fix_loop_structure (current_loops
, changed_bbs
);
552 calculate_dominance_info (CDI_DOMINATORS
);
554 /* This usually does nothing. But sometimes parts of cfg that originally
555 were inside a loop get out of it due to edge removal (since they
556 become unreachable by back edges from latch). */
557 rewrite_into_loop_closed_ssa (changed_bbs
, TODO_update_ssa
);
559 BITMAP_FREE (changed_bbs
);
561 #ifdef ENABLE_CHECKING
562 verify_loop_structure (current_loops
);
566 /* Merge the PHI nodes at BB into those at BB's sole successor. */
569 remove_forwarder_block_with_phi (basic_block bb
)
571 edge succ
= single_succ_edge (bb
);
572 basic_block dest
= succ
->dest
;
574 basic_block dombb
, domdest
, dom
;
576 /* We check for infinite loops already in tree_forwarder_block_p.
577 However it may happen that the infinite loop is created
578 afterwards due to removal of forwarders. */
582 /* If the destination block consists of a nonlocal label, do not
584 label
= first_stmt (dest
);
586 && TREE_CODE (label
) == LABEL_EXPR
587 && DECL_NONLOCAL (LABEL_EXPR_LABEL (label
)))
590 /* Redirect each incoming edge to BB to DEST. */
591 while (EDGE_COUNT (bb
->preds
) > 0)
593 edge e
= EDGE_PRED (bb
, 0), s
;
596 s
= find_edge (e
->src
, dest
);
599 /* We already have an edge S from E->src to DEST. If S and
600 E->dest's sole successor edge have the same PHI arguments
601 at DEST, redirect S to DEST. */
602 if (phi_alternatives_equal (dest
, s
, succ
))
604 e
= redirect_edge_and_branch (e
, dest
);
605 PENDING_STMT (e
) = NULL_TREE
;
609 /* PHI arguments are different. Create a forwarder block by
610 splitting E so that we can merge PHI arguments on E to
612 e
= single_succ_edge (split_edge (e
));
615 s
= redirect_edge_and_branch (e
, dest
);
617 /* redirect_edge_and_branch must not create a new edge. */
620 /* Add to the PHI nodes at DEST each PHI argument removed at the
622 for (phi
= phi_nodes (dest
); phi
; phi
= PHI_CHAIN (phi
))
624 tree def
= PHI_ARG_DEF (phi
, succ
->dest_idx
);
626 if (TREE_CODE (def
) == SSA_NAME
)
630 /* If DEF is one of the results of PHI nodes removed during
631 redirection, replace it with the PHI argument that used
633 for (var
= PENDING_STMT (e
); var
; var
= TREE_CHAIN (var
))
635 tree old_arg
= TREE_PURPOSE (var
);
636 tree new_arg
= TREE_VALUE (var
);
646 add_phi_arg (phi
, def
, s
);
649 PENDING_STMT (e
) = NULL
;
652 /* Update the dominators. */
653 dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
654 domdest
= get_immediate_dominator (CDI_DOMINATORS
, dest
);
657 /* Shortcut to avoid calling (relatively expensive)
658 nearest_common_dominator unless necessary. */
662 dom
= nearest_common_dominator (CDI_DOMINATORS
, domdest
, dombb
);
664 set_immediate_dominator (CDI_DOMINATORS
, dest
, dom
);
666 /* Remove BB since all of BB's incoming edges have been redirected
668 delete_basic_block (bb
);
671 /* This pass merges PHI nodes if one feeds into another. For example,
672 suppose we have the following:
679 # tem_6 = PHI <tem_17(8), tem_23(7)>;
682 # tem_3 = PHI <tem_6(9), tem_2(5)>;
685 Then we merge the first PHI node into the second one like so:
692 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
697 merge_phi_nodes (void)
699 basic_block
*worklist
= xmalloc (sizeof (basic_block
) * n_basic_blocks
);
700 basic_block
*current
= worklist
;
703 calculate_dominance_info (CDI_DOMINATORS
);
705 /* Find all PHI nodes that we may be able to merge. */
710 /* Look for a forwarder block with PHI nodes. */
711 if (!tree_forwarder_block_p (bb
, true))
714 dest
= single_succ (bb
);
716 /* We have to feed into another basic block with PHI
718 if (!phi_nodes (dest
)
719 /* We don't want to deal with a basic block with
721 || has_abnormal_incoming_edge_p (bb
))
724 if (!dominated_by_p (CDI_DOMINATORS
, dest
, bb
))
726 /* If BB does not dominate DEST, then the PHI nodes at
727 DEST must be the only users of the results of the PHI
733 /* Now let's drain WORKLIST. */
734 while (current
!= worklist
)
737 remove_forwarder_block_with_phi (bb
);
744 gate_merge_phi (void)
749 struct tree_opt_pass pass_merge_phi
= {
750 "mergephi", /* name */
751 gate_merge_phi
, /* gate */
752 merge_phi_nodes
, /* execute */
755 0, /* static_pass_number */
756 TV_TREE_MERGE_PHI
, /* tv_id */
757 PROP_cfg
| PROP_ssa
, /* properties_required */
758 0, /* properties_provided */
759 0, /* properties_destroyed */
760 0, /* todo_flags_start */
761 TODO_dump_func
| TODO_ggc_collect
/* todo_flags_finish */