Merge branch 'vendor/GCC44'
[dragonfly.git] / contrib / gcc-4.4 / gcc / tree-cfgcleanup.c
CommitLineData
c251ad9e 1/* CFG cleanup for trees.
4b1e227d 2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
c251ad9e
SS
3 Free Software Foundation, Inc.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "tm.h"
25#include "tree.h"
26#include "rtl.h"
27#include "tm_p.h"
28#include "hard-reg-set.h"
29#include "basic-block.h"
30#include "output.h"
31#include "toplev.h"
32#include "flags.h"
33#include "function.h"
34#include "expr.h"
35#include "ggc.h"
36#include "langhooks.h"
37#include "diagnostic.h"
38#include "tree-flow.h"
39#include "timevar.h"
40#include "tree-dump.h"
41#include "tree-pass.h"
42#include "toplev.h"
43#include "except.h"
44#include "cfgloop.h"
45#include "cfglayout.h"
46#include "hashtab.h"
47#include "tree-ssa-propagate.h"
48#include "tree-scalar-evolution.h"
49
50/* The set of blocks in that at least one of the following changes happened:
51 -- the statement at the end of the block was changed
52 -- the block was newly created
53 -- the set of the predecessors of the block changed
54 -- the set of the successors of the block changed
55 ??? Maybe we could track these changes separately, since they determine
56 what cleanups it makes sense to try on the block. */
57bitmap cfgcleanup_altered_bbs;
58
59/* Remove any fallthru edge from EV. Return true if an edge was removed. */
60
61static bool
62remove_fallthru_edge (VEC(edge,gc) *ev)
63{
64 edge_iterator ei;
65 edge e;
66
67 FOR_EACH_EDGE (e, ei, ev)
68 if ((e->flags & EDGE_FALLTHRU) != 0)
69 {
70 remove_edge_and_dominated_blocks (e);
71 return true;
72 }
73 return false;
74}
75
76
77/* Disconnect an unreachable block in the control expression starting
78 at block BB. */
79
80static bool
81cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi)
82{
83 edge taken_edge;
84 bool retval = false;
85 gimple stmt = gsi_stmt (gsi);
86 tree val;
87
88 if (!single_succ_p (bb))
89 {
90 edge e;
91 edge_iterator ei;
92 bool warned;
93
94 fold_defer_overflow_warnings ();
95 val = gimple_fold (stmt);
96 taken_edge = find_taken_edge (bb, val);
97 if (!taken_edge)
98 {
99 fold_undefer_and_ignore_overflow_warnings ();
100 return false;
101 }
102
103 /* Remove all the edges except the one that is always executed. */
104 warned = false;
105 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
106 {
107 if (e != taken_edge)
108 {
109 if (!warned)
110 {
111 fold_undefer_overflow_warnings
112 (true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
113 warned = true;
114 }
115
116 taken_edge->probability += e->probability;
117 taken_edge->count += e->count;
118 remove_edge_and_dominated_blocks (e);
119 retval = true;
120 }
121 else
122 ei_next (&ei);
123 }
124 if (!warned)
125 fold_undefer_and_ignore_overflow_warnings ();
126 if (taken_edge->probability > REG_BR_PROB_BASE)
127 taken_edge->probability = REG_BR_PROB_BASE;
128 }
129 else
130 taken_edge = single_succ_edge (bb);
131
132 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
133 gsi_remove (&gsi, true);
134 taken_edge->flags = EDGE_FALLTHRU;
135
136 return retval;
137}
138
139/* Try to remove superfluous control structures in basic block BB. Returns
140 true if anything changes. */
141
142static bool
143cleanup_control_flow_bb (basic_block bb)
144{
145 gimple_stmt_iterator gsi;
146 bool retval = false;
147 gimple stmt;
148
149 /* If the last statement of the block could throw and now cannot,
150 we need to prune cfg. */
151 retval |= gimple_purge_dead_eh_edges (bb);
152
153 gsi = gsi_last_bb (bb);
154 if (gsi_end_p (gsi))
155 return retval;
156
157 stmt = gsi_stmt (gsi);
158
159 if (gimple_code (stmt) == GIMPLE_COND
160 || gimple_code (stmt) == GIMPLE_SWITCH)
161 retval |= cleanup_control_expr_graph (bb, gsi);
162 else if (gimple_code (stmt) == GIMPLE_GOTO
163 && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR
164 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0))
165 == LABEL_DECL))
166 {
167 /* If we had a computed goto which has a compile-time determinable
168 destination, then we can eliminate the goto. */
169 edge e;
170 tree label;
171 edge_iterator ei;
172 basic_block target_block;
173
174 /* First look at all the outgoing edges. Delete any outgoing
175 edges which do not go to the right block. For the one
176 edge which goes to the right block, fix up its flags. */
177 label = TREE_OPERAND (gimple_goto_dest (stmt), 0);
178 target_block = label_to_block (label);
179 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
180 {
181 if (e->dest != target_block)
182 remove_edge_and_dominated_blocks (e);
183 else
184 {
185 /* Turn off the EDGE_ABNORMAL flag. */
186 e->flags &= ~EDGE_ABNORMAL;
187
188 /* And set EDGE_FALLTHRU. */
189 e->flags |= EDGE_FALLTHRU;
190 ei_next (&ei);
191 }
192 }
193
194 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index);
195 bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index);
196
197 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the
198 relevant information we need. */
199 gsi_remove (&gsi, true);
200 retval = true;
201 }
202
203 /* Check for indirect calls that have been turned into
204 noreturn calls. */
205 else if (is_gimple_call (stmt)
206 && gimple_call_noreturn_p (stmt)
207 && remove_fallthru_edge (bb->succs))
208 retval = true;
209
210 return retval;
211}
212
213/* Return true if basic block BB does nothing except pass control
214 flow to another block and that we can safely insert a label at
215 the start of the successor block.
216
217 As a precondition, we require that BB be not equal to
218 ENTRY_BLOCK_PTR. */
219
220static bool
221tree_forwarder_block_p (basic_block bb, bool phi_wanted)
222{
223 gimple_stmt_iterator gsi;
224 edge_iterator ei;
225 edge e, succ;
226 basic_block dest;
4b1e227d 227 location_t locus;
c251ad9e
SS
228
229 /* BB must have a single outgoing edge. */
230 if (single_succ_p (bb) != 1
231 /* If PHI_WANTED is false, BB must not have any PHI nodes.
232 Otherwise, BB must have PHI nodes. */
233 || gimple_seq_empty_p (phi_nodes (bb)) == phi_wanted
234 /* BB may not be a predecessor of EXIT_BLOCK_PTR. */
235 || single_succ (bb) == EXIT_BLOCK_PTR
236 /* Nor should this be an infinite loop. */
237 || single_succ (bb) == bb
238 /* BB may not have an abnormal outgoing edge. */
239 || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
240 return false;
241
242#if ENABLE_CHECKING
243 gcc_assert (bb != ENTRY_BLOCK_PTR);
244#endif
245
4b1e227d
SW
246 locus = single_succ_edge (bb)->goto_locus;
247
c251ad9e
SS
248 /* Now walk through the statements backward. We can ignore labels,
249 anything else means this is not a forwarder block. */
250 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
251 {
252 gimple stmt = gsi_stmt (gsi);
253
254 switch (gimple_code (stmt))
255 {
256 case GIMPLE_LABEL:
257 if (DECL_NONLOCAL (gimple_label_label (stmt)))
258 return false;
4b1e227d
SW
259 if (optimize == 0 && gimple_location (stmt) != locus)
260 return false;
c251ad9e
SS
261 break;
262
263 default:
264 return false;
265 }
266 }
267
268 if (find_edge (ENTRY_BLOCK_PTR, bb))
269 return false;
270
271 if (current_loops)
272 {
273 basic_block dest;
274 /* Protect loop latches, headers and preheaders. */
275 if (bb->loop_father->header == bb)
276 return false;
277 dest = EDGE_SUCC (bb, 0)->dest;
278
279 if (dest->loop_father->header == dest)
280 return false;
281 }
282
283 /* If we have an EH edge leaving this block, make sure that the
284 destination of this block has only one predecessor. This ensures
285 that we don't get into the situation where we try to remove two
286 forwarders that go to the same basic block but are handlers for
287 different EH regions. */
288 succ = single_succ_edge (bb);
289 dest = succ->dest;
290 FOR_EACH_EDGE (e, ei, bb->preds)
291 {
292 if (e->flags & EDGE_EH)
293 {
294 if (!single_pred_p (dest))
295 return false;
296 }
4b1e227d
SW
297 /* If goto_locus of any of the edges differs, prevent removing
298 the forwarder block for -O0. */
299 if (optimize == 0 && e->goto_locus != locus)
300 return false;
c251ad9e
SS
301 }
302
303 return true;
304}
305
306/* Return true if BB has at least one abnormal incoming edge. */
307
308static inline bool
309has_abnormal_incoming_edge_p (basic_block bb)
310{
311 edge e;
312 edge_iterator ei;
313
314 FOR_EACH_EDGE (e, ei, bb->preds)
315 if (e->flags & EDGE_ABNORMAL)
316 return true;
317
318 return false;
319}
320
321/* If all the PHI nodes in DEST have alternatives for E1 and E2 and
322 those alternatives are equal in each of the PHI nodes, then return
323 true, else return false. */
324
325static bool
326phi_alternatives_equal (basic_block dest, edge e1, edge e2)
327{
328 int n1 = e1->dest_idx;
329 int n2 = e2->dest_idx;
330 gimple_stmt_iterator gsi;
331
332 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
333 {
334 gimple phi = gsi_stmt (gsi);
335 tree val1 = gimple_phi_arg_def (phi, n1);
336 tree val2 = gimple_phi_arg_def (phi, n2);
337
338 gcc_assert (val1 != NULL_TREE);
339 gcc_assert (val2 != NULL_TREE);
340
341 if (!operand_equal_for_phi_arg_p (val1, val2))
342 return false;
343 }
344
345 return true;
346}
347
348/* Removes forwarder block BB. Returns false if this failed. */
349
350static bool
351remove_forwarder_block (basic_block bb)
352{
353 edge succ = single_succ_edge (bb), e, s;
354 basic_block dest = succ->dest;
355 gimple label;
356 edge_iterator ei;
357 gimple_stmt_iterator gsi, gsi_to;
358 bool seen_abnormal_edge = false;
359
360 /* We check for infinite loops already in tree_forwarder_block_p.
361 However it may happen that the infinite loop is created
362 afterwards due to removal of forwarders. */
363 if (dest == bb)
364 return false;
365
366 /* If the destination block consists of a nonlocal label, do not merge
367 it. */
368 label = first_stmt (dest);
369 if (label
370 && gimple_code (label) == GIMPLE_LABEL
371 && DECL_NONLOCAL (gimple_label_label (label)))
372 return false;
373
374 /* If there is an abnormal edge to basic block BB, but not into
375 dest, problems might occur during removal of the phi node at out
376 of ssa due to overlapping live ranges of registers.
377
378 If there is an abnormal edge in DEST, the problems would occur
379 anyway since cleanup_dead_labels would then merge the labels for
380 two different eh regions, and rest of exception handling code
381 does not like it.
382
383 So if there is an abnormal edge to BB, proceed only if there is
384 no abnormal edge to DEST and there are no phi nodes in DEST. */
385 if (has_abnormal_incoming_edge_p (bb))
386 {
387 seen_abnormal_edge = true;
388
389 if (has_abnormal_incoming_edge_p (dest)
390 || !gimple_seq_empty_p (phi_nodes (dest)))
391 return false;
392 }
393
394 /* If there are phi nodes in DEST, and some of the blocks that are
395 predecessors of BB are also predecessors of DEST, check that the
396 phi node arguments match. */
397 if (!gimple_seq_empty_p (phi_nodes (dest)))
398 {
399 FOR_EACH_EDGE (e, ei, bb->preds)
400 {
401 s = find_edge (e->src, dest);
402 if (!s)
403 continue;
404
405 if (!phi_alternatives_equal (dest, succ, s))
406 return false;
407 }
408 }
409
410 /* Redirect the edges. */
411 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
412 {
413 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
414
415 if (e->flags & EDGE_ABNORMAL)
416 {
417 /* If there is an abnormal edge, redirect it anyway, and
418 move the labels to the new block to make it legal. */
419 s = redirect_edge_succ_nodup (e, dest);
420 }
421 else
422 s = redirect_edge_and_branch (e, dest);
423
424 if (s == e)
425 {
426 /* Create arguments for the phi nodes, since the edge was not
427 here before. */
428 for (gsi = gsi_start_phis (dest);
429 !gsi_end_p (gsi);
430 gsi_next (&gsi))
431 {
432 gimple phi = gsi_stmt (gsi);
433 add_phi_arg (phi, gimple_phi_arg_def (phi, succ->dest_idx), s);
434 }
435 }
436 }
437
438 if (seen_abnormal_edge)
439 {
440 /* Move the labels to the new block, so that the redirection of
441 the abnormal edges works. */
442 gsi_to = gsi_start_bb (dest);
443 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
444 {
445 label = gsi_stmt (gsi);
446 gcc_assert (gimple_code (label) == GIMPLE_LABEL);
447 gsi_remove (&gsi, false);
448 gsi_insert_before (&gsi_to, label, GSI_CONTINUE_LINKING);
449 }
450 }
451
452 bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
453
454 /* Update the dominators. */
455 if (dom_info_available_p (CDI_DOMINATORS))
456 {
457 basic_block dom, dombb, domdest;
458
459 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
460 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
461 if (domdest == bb)
462 {
463 /* Shortcut to avoid calling (relatively expensive)
464 nearest_common_dominator unless necessary. */
465 dom = dombb;
466 }
467 else
468 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
469
470 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
471 }
472
473 /* And kill the forwarder block. */
474 delete_basic_block (bb);
475
476 return true;
477}
478
479/* Split basic blocks on calls in the middle of a basic block that are now
480 known not to return, and remove the unreachable code. */
481
482static bool
483split_bbs_on_noreturn_calls (void)
484{
485 bool changed = false;
486 gimple stmt;
487 basic_block bb;
488
489 /* Detect cases where a mid-block call is now known not to return. */
490 if (cfun->gimple_df)
491 while (VEC_length (gimple, MODIFIED_NORETURN_CALLS (cfun)))
492 {
493 stmt = VEC_pop (gimple, MODIFIED_NORETURN_CALLS (cfun));
494 bb = gimple_bb (stmt);
495 /* BB might be deleted at this point, so verify first
496 BB is present in the cfg. */
497 if (bb == NULL
498 || bb->index < NUM_FIXED_BLOCKS
499 || bb->index >= n_basic_blocks
500 || BASIC_BLOCK (bb->index) != bb
501 || last_stmt (bb) == stmt
502 || !gimple_call_noreturn_p (stmt))
503 continue;
504
505 changed = true;
506 split_block (bb, stmt);
507 remove_fallthru_edge (bb->succs);
508 }
509
510 return changed;
511}
512
513/* If GIMPLE_OMP_RETURN in basic block BB is unreachable, remove it. */
514
515static bool
516cleanup_omp_return (basic_block bb)
517{
518 gimple stmt = last_stmt (bb);
519 basic_block control_bb;
520
521 if (stmt == NULL
522 || gimple_code (stmt) != GIMPLE_OMP_RETURN
523 || !single_pred_p (bb))
524 return false;
525
526 control_bb = single_pred (bb);
527 stmt = last_stmt (control_bb);
528
4b1e227d 529 if (stmt == NULL || gimple_code (stmt) != GIMPLE_OMP_SECTIONS_SWITCH)
c251ad9e
SS
530 return false;
531
532 /* The block with the control statement normally has two entry edges -- one
533 from entry, one from continue. If continue is removed, return is
534 unreachable, so we remove it here as well. */
535 if (EDGE_COUNT (control_bb->preds) == 2)
536 return false;
537
538 gcc_assert (EDGE_COUNT (control_bb->preds) == 1);
539 remove_edge_and_dominated_blocks (single_pred_edge (bb));
540 return true;
541}
542
543/* Tries to cleanup cfg in basic block BB. Returns true if anything
544 changes. */
545
546static bool
547cleanup_tree_cfg_bb (basic_block bb)
548{
549 bool retval = false;
550
551 if (cleanup_omp_return (bb))
552 return true;
553
554 retval = cleanup_control_flow_bb (bb);
4b1e227d
SW
555
556 if (tree_forwarder_block_p (bb, false)
c251ad9e
SS
557 && remove_forwarder_block (bb))
558 return true;
559
560 /* Merging the blocks may create new opportunities for folding
561 conditional branches (due to the elimination of single-valued PHI
562 nodes). */
563 if (single_succ_p (bb)
564 && can_merge_blocks_p (bb, single_succ (bb)))
565 {
566 merge_blocks (bb, single_succ (bb));
567 return true;
568 }
569
570 return retval;
571}
572
573/* Iterate the cfg cleanups, while anything changes. */
574
575static bool
576cleanup_tree_cfg_1 (void)
577{
578 bool retval = false;
579 basic_block bb;
580 unsigned i, n;
581
582 retval |= split_bbs_on_noreturn_calls ();
583
584 /* Prepare the worklists of altered blocks. */
585 cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL);
586
587 /* During forwarder block cleanup, we may redirect edges out of
588 SWITCH_EXPRs, which can get expensive. So we want to enable
589 recording of edge to CASE_LABEL_EXPR. */
590 start_recording_case_labels ();
591
592 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB,
593 since the basic blocks may get removed. */
594 n = last_basic_block;
595 for (i = NUM_FIXED_BLOCKS; i < n; i++)
596 {
597 bb = BASIC_BLOCK (i);
598 if (bb)
599 retval |= cleanup_tree_cfg_bb (bb);
600 }
601
602 /* Now process the altered blocks, as long as any are available. */
603 while (!bitmap_empty_p (cfgcleanup_altered_bbs))
604 {
605 i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
606 bitmap_clear_bit (cfgcleanup_altered_bbs, i);
607 if (i < NUM_FIXED_BLOCKS)
608 continue;
609
610 bb = BASIC_BLOCK (i);
611 if (!bb)
612 continue;
613
614 retval |= cleanup_tree_cfg_bb (bb);
615
616 /* Rerun split_bbs_on_noreturn_calls, in case we have altered any noreturn
617 calls. */
618 retval |= split_bbs_on_noreturn_calls ();
619 }
620
621 end_recording_case_labels ();
622 BITMAP_FREE (cfgcleanup_altered_bbs);
623 return retval;
624}
625
626
627/* Remove unreachable blocks and other miscellaneous clean up work.
628 Return true if the flowgraph was modified, false otherwise. */
629
630static bool
631cleanup_tree_cfg_noloop (void)
632{
633 bool changed;
634
635 timevar_push (TV_TREE_CLEANUP_CFG);
636
637 /* Iterate until there are no more cleanups left to do. If any
638 iteration changed the flowgraph, set CHANGED to true.
639
640 If dominance information is available, there cannot be any unreachable
641 blocks. */
642 if (!dom_info_available_p (CDI_DOMINATORS))
643 {
644 changed = delete_unreachable_blocks ();
645 calculate_dominance_info (CDI_DOMINATORS);
646 }
647 else
648 {
649#ifdef ENABLE_CHECKING
650 verify_dominators (CDI_DOMINATORS);
651#endif
652 changed = false;
653 }
654
655 changed |= cleanup_tree_cfg_1 ();
656
657 gcc_assert (dom_info_available_p (CDI_DOMINATORS));
658 compact_blocks ();
659
660#ifdef ENABLE_CHECKING
661 verify_flow_info ();
662#endif
663
664 timevar_pop (TV_TREE_CLEANUP_CFG);
665
666 if (changed && current_loops)
667 loops_state_set (LOOPS_NEED_FIXUP);
668
669 return changed;
670}
671
672/* Repairs loop structures. */
673
674static void
675repair_loop_structures (void)
676{
677 bitmap changed_bbs = BITMAP_ALLOC (NULL);
678 fix_loop_structure (changed_bbs);
679
680 /* This usually does nothing. But sometimes parts of cfg that originally
681 were inside a loop get out of it due to edge removal (since they
682 become unreachable by back edges from latch). */
683 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
684 rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
685
686 BITMAP_FREE (changed_bbs);
687
688#ifdef ENABLE_CHECKING
689 verify_loop_structure ();
690#endif
691 scev_reset ();
692
693 loops_state_clear (LOOPS_NEED_FIXUP);
694}
695
696/* Cleanup cfg and repair loop structures. */
697
698bool
699cleanup_tree_cfg (void)
700{
701 bool changed = cleanup_tree_cfg_noloop ();
702
703 if (current_loops != NULL
704 && loops_state_satisfies_p (LOOPS_NEED_FIXUP))
705 repair_loop_structures ();
706
707 return changed;
708}
709
710/* Merge the PHI nodes at BB into those at BB's sole successor. */
711
712static void
713remove_forwarder_block_with_phi (basic_block bb)
714{
715 edge succ = single_succ_edge (bb);
716 basic_block dest = succ->dest;
717 gimple label;
718 basic_block dombb, domdest, dom;
719
720 /* We check for infinite loops already in tree_forwarder_block_p.
721 However it may happen that the infinite loop is created
722 afterwards due to removal of forwarders. */
723 if (dest == bb)
724 return;
725
726 /* If the destination block consists of a nonlocal label, do not
727 merge it. */
728 label = first_stmt (dest);
729 if (label
730 && gimple_code (label) == GIMPLE_LABEL
731 && DECL_NONLOCAL (gimple_label_label (label)))
732 return;
733
734 /* Redirect each incoming edge to BB to DEST. */
735 while (EDGE_COUNT (bb->preds) > 0)
736 {
737 edge e = EDGE_PRED (bb, 0), s;
738 gimple_stmt_iterator gsi;
739
740 s = find_edge (e->src, dest);
741 if (s)
742 {
743 /* We already have an edge S from E->src to DEST. If S and
744 E->dest's sole successor edge have the same PHI arguments
745 at DEST, redirect S to DEST. */
746 if (phi_alternatives_equal (dest, s, succ))
747 {
748 e = redirect_edge_and_branch (e, dest);
749 redirect_edge_var_map_clear (e);
750 continue;
751 }
752
753 /* PHI arguments are different. Create a forwarder block by
754 splitting E so that we can merge PHI arguments on E to
755 DEST. */
756 e = single_succ_edge (split_edge (e));
757 }
758
759 s = redirect_edge_and_branch (e, dest);
760
761 /* redirect_edge_and_branch must not create a new edge. */
762 gcc_assert (s == e);
763
764 /* Add to the PHI nodes at DEST each PHI argument removed at the
765 destination of E. */
766 for (gsi = gsi_start_phis (dest);
767 !gsi_end_p (gsi);
768 gsi_next (&gsi))
769 {
770 gimple phi = gsi_stmt (gsi);
771 tree def = gimple_phi_arg_def (phi, succ->dest_idx);
772
773 if (TREE_CODE (def) == SSA_NAME)
774 {
775 edge_var_map_vector head;
776 edge_var_map *vm;
777 size_t i;
778
779 /* If DEF is one of the results of PHI nodes removed during
780 redirection, replace it with the PHI argument that used
781 to be on E. */
782 head = redirect_edge_var_map_vector (e);
783 for (i = 0; VEC_iterate (edge_var_map, head, i, vm); ++i)
784 {
785 tree old_arg = redirect_edge_var_map_result (vm);
786 tree new_arg = redirect_edge_var_map_def (vm);
787
788 if (def == old_arg)
789 {
790 def = new_arg;
791 break;
792 }
793 }
794 }
795
796 add_phi_arg (phi, def, s);
797 }
798
799 redirect_edge_var_map_clear (e);
800 }
801
802 /* Update the dominators. */
803 dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
804 domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
805 if (domdest == bb)
806 {
807 /* Shortcut to avoid calling (relatively expensive)
808 nearest_common_dominator unless necessary. */
809 dom = dombb;
810 }
811 else
812 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
813
814 set_immediate_dominator (CDI_DOMINATORS, dest, dom);
815
816 /* Remove BB since all of BB's incoming edges have been redirected
817 to DEST. */
818 delete_basic_block (bb);
819}
820
821/* This pass merges PHI nodes if one feeds into another. For example,
822 suppose we have the following:
823
824 goto <bb 9> (<L9>);
825
826<L8>:;
827 tem_17 = foo ();
828
829 # tem_6 = PHI <tem_17(8), tem_23(7)>;
830<L9>:;
831
832 # tem_3 = PHI <tem_6(9), tem_2(5)>;
833<L10>:;
834
835 Then we merge the first PHI node into the second one like so:
836
837 goto <bb 9> (<L10>);
838
839<L8>:;
840 tem_17 = foo ();
841
842 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
843<L10>:;
844*/
845
846static unsigned int
847merge_phi_nodes (void)
848{
849 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks);
850 basic_block *current = worklist;
851 basic_block bb;
852
853 calculate_dominance_info (CDI_DOMINATORS);
854
855 /* Find all PHI nodes that we may be able to merge. */
856 FOR_EACH_BB (bb)
857 {
858 basic_block dest;
859
860 /* Look for a forwarder block with PHI nodes. */
861 if (!tree_forwarder_block_p (bb, true))
862 continue;
863
864 dest = single_succ (bb);
865
866 /* We have to feed into another basic block with PHI
867 nodes. */
868 if (!phi_nodes (dest)
869 /* We don't want to deal with a basic block with
870 abnormal edges. */
871 || has_abnormal_incoming_edge_p (bb))
872 continue;
873
874 if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
875 {
876 /* If BB does not dominate DEST, then the PHI nodes at
877 DEST must be the only users of the results of the PHI
878 nodes at BB. */
879 *current++ = bb;
880 }
881 else
882 {
883 gimple_stmt_iterator gsi;
884 unsigned int dest_idx = single_succ_edge (bb)->dest_idx;
885
886 /* BB dominates DEST. There may be many users of the PHI
887 nodes in BB. However, there is still a trivial case we
888 can handle. If the result of every PHI in BB is used
889 only by a PHI in DEST, then we can trivially merge the
890 PHI nodes from BB into DEST. */
891 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
892 gsi_next (&gsi))
893 {
894 gimple phi = gsi_stmt (gsi);
895 tree result = gimple_phi_result (phi);
896 use_operand_p imm_use;
897 gimple use_stmt;
898
899 /* If the PHI's result is never used, then we can just
900 ignore it. */
901 if (has_zero_uses (result))
902 continue;
903
904 /* Get the single use of the result of this PHI node. */
905 if (!single_imm_use (result, &imm_use, &use_stmt)
906 || gimple_code (use_stmt) != GIMPLE_PHI
907 || gimple_bb (use_stmt) != dest
908 || gimple_phi_arg_def (use_stmt, dest_idx) != result)
909 break;
910 }
911
912 /* If the loop above iterated through all the PHI nodes
913 in BB, then we can merge the PHIs from BB into DEST. */
914 if (gsi_end_p (gsi))
915 *current++ = bb;
916 }
917 }
918
919 /* Now let's drain WORKLIST. */
920 while (current != worklist)
921 {
922 bb = *--current;
923 remove_forwarder_block_with_phi (bb);
924 }
925
926 free (worklist);
927 return 0;
928}
929
930static bool
931gate_merge_phi (void)
932{
933 return 1;
934}
935
936struct gimple_opt_pass pass_merge_phi =
937{
938 {
939 GIMPLE_PASS,
940 "mergephi", /* name */
941 gate_merge_phi, /* gate */
942 merge_phi_nodes, /* execute */
943 NULL, /* sub */
944 NULL, /* next */
945 0, /* static_pass_number */
946 TV_TREE_MERGE_PHI, /* tv_id */
947 PROP_cfg | PROP_ssa, /* properties_required */
948 0, /* properties_provided */
949 0, /* properties_destroyed */
950 0, /* todo_flags_start */
951 TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */
952 | TODO_verify_ssa
953 }
954};