1 /* Control flow optimization code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* This file contains optimizer of the control flow. The main entrypoint is
23 cleanup_cfg. Following optimizations are performed:
25 - Unreachable blocks removal
26 - Edge forwarding (edge to the forwarder block is forwarded to it's
27 succesor. Simplification of the branch instruction is performed by
28 underlying infrastructure so branch can be converted to simplejump or
30 - Cross jumping (tail merging)
31 - Conditional jump-around-simplejump simplification
32 - Basic block merging. */
37 #include "hard-reg-set.h"
38 #include "basic-block.h"
41 #include "insn-config.h"
48 static bool try_crossjump_to_edge PARAMS ((int, edge, edge));
49 static bool try_crossjump_bb PARAMS ((int, basic_block));
50 static bool outgoing_edges_match PARAMS ((basic_block, basic_block));
51 static int flow_find_cross_jump PARAMS ((int, basic_block, basic_block,
54 static bool delete_unreachable_blocks PARAMS ((void));
55 static bool tail_recursion_label_p PARAMS ((rtx));
56 static void merge_blocks_move_predecessor_nojumps PARAMS ((basic_block,
58 static void merge_blocks_move_successor_nojumps PARAMS ((basic_block,
60 static bool merge_blocks PARAMS ((edge,basic_block,basic_block,
62 static bool try_optimize_cfg PARAMS ((int));
63 static bool try_simplify_condjump PARAMS ((basic_block));
64 static bool try_forward_edges PARAMS ((int, basic_block));
66 /* Simplify a conditional jump around an unconditional jump.
67 Return true if something changed. */
70 try_simplify_condjump (cbranch_block)
71 basic_block cbranch_block;
73 basic_block jump_block, jump_dest_block, cbranch_dest_block;
74 edge cbranch_jump_edge, cbranch_fallthru_edge;
77 /* Verify that there are exactly two successors. */
78 if (!cbranch_block->succ
79 || !cbranch_block->succ->succ_next
80 || cbranch_block->succ->succ_next->succ_next)
83 /* Verify that we've got a normal conditional branch at the end
85 cbranch_insn = cbranch_block->end;
86 if (!any_condjump_p (cbranch_insn))
89 cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
90 cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
92 /* The next block must not have multiple predecessors, must not
93 be the last block in the function, and must contain just the
94 unconditional jump. */
95 jump_block = cbranch_fallthru_edge->dest;
96 if (jump_block->pred->pred_next
97 || jump_block->index == n_basic_blocks - 1
98 || !forwarder_block_p (jump_block))
100 jump_dest_block = jump_block->succ->dest;
102 /* The conditional branch must target the block after the
103 unconditional branch. */
104 cbranch_dest_block = cbranch_jump_edge->dest;
106 if (!can_fallthru (jump_block, cbranch_dest_block))
109 /* Invert the conditional branch. */
110 if (!invert_jump (cbranch_insn, block_label (jump_dest_block), 0))
114 fprintf (rtl_dump_file, "Simplifying condjump %i around jump %i\n",
115 INSN_UID (cbranch_insn), INSN_UID (jump_block->end));
117 /* Success. Update the CFG to match. Note that after this point
118 the edge variable names appear backwards; the redirection is done
119 this way to preserve edge profile data. */
120 cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
122 cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
124 cbranch_jump_edge->flags |= EDGE_FALLTHRU;
125 cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
127 /* Delete the block with the unconditional jump, and clean up the mess. */
128 flow_delete_block (jump_block);
129 tidy_fallthru_edge (cbranch_jump_edge, cbranch_block, cbranch_dest_block);
134 /* Attempt to forward edges leaving basic block B.
135 Return true if sucessful. */
138 try_forward_edges (mode, b)
142 bool changed = false;
145 for (e = b->succ; e ; e = next)
147 basic_block target, first;
152 /* Skip complex edges because we don't know how to update them.
154 Still handle fallthru edges, as we can suceed to forward fallthru
155 edge to the same place as the branch edge of conditional branch
156 and turn conditional branch to an unconditonal branch. */
157 if (e->flags & EDGE_COMPLEX)
160 target = first = e->dest;
163 /* Look for the real destination of the jump.
164 Avoid inifinite loop in the infinite empty loop by counting
165 up to n_basic_blocks. */
166 while (forwarder_block_p (target)
167 && target->succ->dest != EXIT_BLOCK_PTR
168 && counter < n_basic_blocks)
170 /* Bypass trivial infinite loops. */
171 if (target == target->succ->dest)
172 counter = n_basic_blocks;
174 /* Avoid killing of loop pre-headers, as it is the place loop
175 optimizer wants to hoist code to.
177 For fallthru forwarders, the LOOP_BEG note must appear between
178 the header of block and CODE_LABEL of the loop, for non forwarders
179 it must appear before the JUMP_INSN. */
180 if (mode & CLEANUP_PRE_LOOP)
182 rtx insn = (target->succ->flags & EDGE_FALLTHRU
183 ? target->head : prev_nonnote_insn (target->end));
185 if (GET_CODE (insn) != NOTE)
186 insn = NEXT_INSN (insn);
188 for (;insn && GET_CODE (insn) != CODE_LABEL && !INSN_P (insn);
189 insn = NEXT_INSN (insn))
190 if (GET_CODE (insn) == NOTE
191 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
194 if (GET_CODE (insn) == NOTE)
197 target = target->succ->dest, counter++;
200 if (counter >= n_basic_blocks)
203 fprintf (rtl_dump_file, "Infinite loop in BB %i.\n",
206 else if (target == first)
207 ; /* We didn't do anything. */
210 /* Save the values now, as the edge may get removed. */
211 gcov_type edge_count = e->count;
212 int edge_probability = e->probability;
214 if (redirect_edge_and_branch (e, target))
216 /* We successfully forwarded the edge. Now update profile
217 data: for each edge we traversed in the chain, remove
218 the original edge's execution count. */
219 int edge_frequency = ((edge_probability * b->frequency
220 + REG_BR_PROB_BASE / 2)
225 first->count -= edge_count;
226 first->succ->count -= edge_count;
227 first->frequency -= edge_frequency;
228 first = first->succ->dest;
230 while (first != target);
237 fprintf (rtl_dump_file, "Forwarding edge %i->%i to %i failed.\n",
238 b->index, e->dest->index, target->index);
246 /* Return true if LABEL is used for tail recursion. */
249 tail_recursion_label_p (label)
254 for (x = tail_recursion_label_list; x; x = XEXP (x, 1))
255 if (label == XEXP (x, 0))
261 /* Blocks A and B are to be merged into a single block. A has no incoming
262 fallthru edge, so it can be moved before B without adding or modifying
263 any jumps (aside from the jump from A to B). */
266 merge_blocks_move_predecessor_nojumps (a, b)
272 barrier = next_nonnote_insn (a->end);
273 if (GET_CODE (barrier) != BARRIER)
275 delete_insn (barrier);
277 /* Move block and loop notes out of the chain so that we do not
280 ??? A better solution would be to squeeze out all the non-nested notes
281 and adjust the block trees appropriately. Even better would be to have
282 a tighter connection between block trees and rtl so that this is not
284 squeeze_notes (&a->head, &a->end);
286 /* Scramble the insn chain. */
287 if (a->end != PREV_INSN (b->head))
288 reorder_insns_nobb (a->head, a->end, PREV_INSN (b->head));
292 fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
296 /* Swap the records for the two blocks around. Although we are deleting B,
297 A is now where B was and we want to compact the BB array from where
299 BASIC_BLOCK (a->index) = b;
300 BASIC_BLOCK (b->index) = a;
305 /* Now blocks A and B are contiguous. Merge them. */
306 merge_blocks_nomove (a, b);
309 /* Blocks A and B are to be merged into a single block. B has no outgoing
310 fallthru edge, so it can be moved after A without adding or modifying
311 any jumps (aside from the jump from A to B). */
314 merge_blocks_move_successor_nojumps (a, b)
317 rtx barrier, real_b_end;
320 barrier = NEXT_INSN (b->end);
322 /* Recognize a jump table following block B. */
324 && GET_CODE (barrier) == CODE_LABEL
325 && NEXT_INSN (barrier)
326 && GET_CODE (NEXT_INSN (barrier)) == JUMP_INSN
327 && (GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_VEC
328 || GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_DIFF_VEC))
330 /* Temporarily add the table jump insn to b, so that it will also
331 be moved to the correct location. */
332 b->end = NEXT_INSN (barrier);
333 barrier = NEXT_INSN (b->end);
336 /* There had better have been a barrier there. Delete it. */
337 if (barrier && GET_CODE (barrier) == BARRIER)
338 delete_insn (barrier);
340 /* Move block and loop notes out of the chain so that we do not
343 ??? A better solution would be to squeeze out all the non-nested notes
344 and adjust the block trees appropriately. Even better would be to have
345 a tighter connection between block trees and rtl so that this is not
347 squeeze_notes (&b->head, &b->end);
349 /* Scramble the insn chain. */
350 reorder_insns_nobb (b->head, b->end, a->end);
352 /* Restore the real end of b. */
355 /* Now blocks A and B are contiguous. Merge them. */
356 merge_blocks_nomove (a, b);
360 fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
365 /* Attempt to merge basic blocks that are potentially non-adjacent.
366 Return true iff the attempt succeeded. */
369 merge_blocks (e, b, c, mode)
374 /* If C has a tail recursion label, do not merge. There is no
375 edge recorded from the call_placeholder back to this label, as
376 that would make optimize_sibling_and_tail_recursive_calls more
377 complex for no gain. */
378 if ((mode & CLEANUP_PRE_SIBCALL)
379 && GET_CODE (c->head) == CODE_LABEL
380 && tail_recursion_label_p (c->head))
383 /* If B has a fallthru edge to C, no need to move anything. */
384 if (e->flags & EDGE_FALLTHRU)
386 merge_blocks_nomove (b, c);
390 fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
396 /* Otherwise we will need to move code around. Do that only if expensive
397 transformations are allowed. */
398 else if (mode & CLEANUP_EXPENSIVE)
400 edge tmp_edge, b_fallthru_edge;
401 bool c_has_outgoing_fallthru;
402 bool b_has_incoming_fallthru;
404 /* Avoid overactive code motion, as the forwarder blocks should be
405 eliminated by edge redirection instead. One exception might have
406 been if B is a forwarder block and C has no fallthru edge, but
407 that should be cleaned up by bb-reorder instead. */
408 if (forwarder_block_p (b) || forwarder_block_p (c))
411 /* We must make sure to not munge nesting of lexical blocks,
412 and loop notes. This is done by squeezing out all the notes
413 and leaving them there to lie. Not ideal, but functional. */
415 for (tmp_edge = c->succ; tmp_edge; tmp_edge = tmp_edge->succ_next)
416 if (tmp_edge->flags & EDGE_FALLTHRU)
418 c_has_outgoing_fallthru = (tmp_edge != NULL);
420 for (tmp_edge = b->pred; tmp_edge; tmp_edge = tmp_edge->pred_next)
421 if (tmp_edge->flags & EDGE_FALLTHRU)
423 b_has_incoming_fallthru = (tmp_edge != NULL);
424 b_fallthru_edge = tmp_edge;
426 /* Otherwise, we're going to try to move C after B. If C does
427 not have an outgoing fallthru, then it can be moved
428 immediately after B without introducing or modifying jumps. */
429 if (! c_has_outgoing_fallthru)
431 merge_blocks_move_successor_nojumps (b, c);
435 /* If B does not have an incoming fallthru, then it can be moved
436 immediately before C without introducing or modifying jumps.
437 C cannot be the first block, so we do not have to worry about
438 accessing a non-existent block. */
440 if (b_has_incoming_fallthru)
442 if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
444 force_nonfallthru (b_fallthru_edge);
446 merge_blocks_move_predecessor_nojumps (b, c);
452 /* Look through the insns at the end of BB1 and BB2 and find the longest
453 sequence that are equivalent. Store the first insns for that sequence
454 in *F1 and *F2 and return the sequence length.
456 To simplify callers of this function, if the blocks match exactly,
457 store the head of the blocks in *F1 and *F2. */
460 flow_find_cross_jump (mode, bb1, bb2, f1, f2)
461 int mode ATTRIBUTE_UNUSED;
462 basic_block bb1, bb2;
465 rtx i1, i2, p1, p2, last1, last2, afterlast1, afterlast2;
468 /* Skip simple jumps at the end of the blocks. Complex jumps still
469 need to be compared for equivalence, which we'll do below. */
473 || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
477 || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
480 last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
484 while ((GET_CODE (i1) == NOTE && i1 != bb1->head))
486 while ((GET_CODE (i2) == NOTE && i2 != bb2->head))
489 if (i1 == bb1->head || i2 == bb2->head)
492 /* Verify that I1 and I2 are equivalent. */
494 if (GET_CODE (i1) != GET_CODE (i2))
500 /* If this is a CALL_INSN, compare register usage information.
501 If we don't check this on stack register machines, the two
502 CALL_INSNs might be merged leaving reg-stack.c with mismatching
503 numbers of stack registers in the same basic block.
504 If we don't check this on machines with delay slots, a delay slot may
505 be filled that clobbers a parameter expected by the subroutine.
507 ??? We take the simple route for now and assume that if they're
508 equal, they were constructed identically. */
510 if (GET_CODE (i1) == CALL_INSN
511 && ! rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
512 CALL_INSN_FUNCTION_USAGE (i2)))
516 /* If cross_jump_death_matters is not 0, the insn's mode
517 indicates whether or not the insn contains any stack-like
520 if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
522 /* If register stack conversion has already been done, then
523 death notes must also be compared before it is certain that
524 the two instruction streams match. */
527 HARD_REG_SET i1_regset, i2_regset;
529 CLEAR_HARD_REG_SET (i1_regset);
530 CLEAR_HARD_REG_SET (i2_regset);
532 for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
533 if (REG_NOTE_KIND (note) == REG_DEAD
534 && STACK_REG_P (XEXP (note, 0)))
535 SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
537 for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
538 if (REG_NOTE_KIND (note) == REG_DEAD
539 && STACK_REG_P (XEXP (note, 0)))
540 SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
542 GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
551 if (GET_CODE (p1) != GET_CODE (p2))
554 if (! rtx_renumbered_equal_p (p1, p2))
556 /* The following code helps take care of G++ cleanups. */
557 rtx equiv1 = find_reg_equal_equiv_note (i1);
558 rtx equiv2 = find_reg_equal_equiv_note (i2);
561 /* If the equivalences are not to a constant, they may
562 reference pseudos that no longer exist, so we can't
564 && CONSTANT_P (XEXP (equiv1, 0))
565 && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
567 rtx s1 = single_set (i1);
568 rtx s2 = single_set (i2);
569 if (s1 != 0 && s2 != 0
570 && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
572 validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
573 validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
574 if (! rtx_renumbered_equal_p (p1, p2))
576 else if (apply_change_group ())
584 /* Don't begin a cross-jump with a USE or CLOBBER insn. */
585 if (GET_CODE (p1) != USE && GET_CODE (p1) != CLOBBER)
587 /* If the merged insns have different REG_EQUAL notes, then
589 rtx equiv1 = find_reg_equal_equiv_note (i1);
590 rtx equiv2 = find_reg_equal_equiv_note (i2);
592 if (equiv1 && !equiv2)
593 remove_note (i1, equiv1);
594 else if (!equiv1 && equiv2)
595 remove_note (i2, equiv2);
596 else if (equiv1 && equiv2
597 && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
599 remove_note (i1, equiv1);
600 remove_note (i2, equiv2);
603 afterlast1 = last1, afterlast2 = last2;
604 last1 = i1, last2 = i2;
614 /* Don't allow the insn after a compare to be shared by
615 cross-jumping unless the compare is also shared. */
616 if (reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
617 last1 = afterlast1, last2 = afterlast2, ninsns--;
621 /* Include preceeding notes and labels in the cross-jump. One,
622 this may bring us to the head of the blocks as requested above.
623 Two, it keeps line number notes as matched as may be. */
626 while (last1 != bb1->head && GET_CODE (PREV_INSN (last1)) == NOTE)
627 last1 = PREV_INSN (last1);
628 if (last1 != bb1->head && GET_CODE (PREV_INSN (last1)) == CODE_LABEL)
629 last1 = PREV_INSN (last1);
630 while (last2 != bb2->head && GET_CODE (PREV_INSN (last2)) == NOTE)
631 last2 = PREV_INSN (last2);
632 if (last2 != bb2->head && GET_CODE (PREV_INSN (last2)) == CODE_LABEL)
633 last2 = PREV_INSN (last2);
642 /* Return true iff outgoing edges of BB1 and BB2 match, together with
643 the branch instruction. This means that if we commonize the control
644 flow before end of the basic block, the semantic remains unchanged.
646 We may assume that there exists one edge with a common destination. */
649 outgoing_edges_match (bb1, bb2)
653 /* If BB1 has only one successor, we must be looking at an unconditional
654 jump. Which, by the assumption above, means that we only need to check
655 that BB2 has one successor. */
656 if (bb1->succ && !bb1->succ->succ_next)
657 return (bb2->succ && !bb2->succ->succ_next);
659 /* Match conditional jumps - this may get tricky when fallthru and branch
660 edges are crossed. */
662 && bb1->succ->succ_next
663 && !bb1->succ->succ_next->succ_next
664 && any_condjump_p (bb1->end))
668 rtx set1, set2, cond1, cond2;
669 enum rtx_code code1, code2;
672 || !bb2->succ->succ_next
673 || bb1->succ->succ_next->succ_next
674 || !any_condjump_p (bb2->end))
677 b1 = BRANCH_EDGE (bb1);
678 b2 = BRANCH_EDGE (bb2);
679 f1 = FALLTHRU_EDGE (bb1);
680 f2 = FALLTHRU_EDGE (bb2);
682 /* Get around possible forwarders on fallthru edges. Other cases
683 should be optimized out already. */
684 if (forwarder_block_p (f1->dest))
686 if (forwarder_block_p (f2->dest))
689 /* To simplify use of this function, return false if there are
690 unneeded forwarder blocks. These will get eliminated later
691 during cleanup_cfg. */
692 if (forwarder_block_p (f1->dest)
693 || forwarder_block_p (f2->dest)
694 || forwarder_block_p (b1->dest)
695 || forwarder_block_p (b2->dest))
698 if (f1->dest == f2->dest && b1->dest == b2->dest)
700 else if (f1->dest == b2->dest && b1->dest == f2->dest)
705 set1 = pc_set (bb1->end);
706 set2 = pc_set (bb2->end);
707 if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
708 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
711 cond1 = XEXP (SET_SRC (set1), 0);
712 cond2 = XEXP (SET_SRC (set2), 0);
713 code1 = GET_CODE (cond1);
715 code2 = reversed_comparison_code (cond2, bb2->end);
717 code2 = GET_CODE (cond2);
718 if (code2 == UNKNOWN)
721 /* Verify codes and operands match. */
722 match = ((code1 == code2
723 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
724 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
725 || (code1 == swap_condition (code2)
726 && rtx_renumbered_equal_p (XEXP (cond1, 1),
728 && rtx_renumbered_equal_p (XEXP (cond1, 0),
731 /* If we return true, we will join the blocks. Which means that
732 we will only have one branch prediction bit to work with. Thus
733 we require the existing branches to have probabilities that are
735 /* ??? We should use bb->frequency to allow merging in infrequently
736 executed blocks, but at the moment it is not available when
737 cleanup_cfg is run. */
738 if (match && !optimize_size)
742 note1 = find_reg_note (bb1->end, REG_BR_PROB, 0);
743 note2 = find_reg_note (bb2->end, REG_BR_PROB, 0);
747 prob1 = INTVAL (XEXP (note1, 0));
748 prob2 = INTVAL (XEXP (note2, 0));
750 prob2 = REG_BR_PROB_BASE - prob2;
752 /* Fail if the difference in probabilities is
754 if (abs (prob1 - prob2) > REG_BR_PROB_BASE / 20)
757 else if (note1 || note2)
761 if (rtl_dump_file && match)
762 fprintf (rtl_dump_file, "Conditionals in bb %i and %i match.\n",
763 bb1->index, bb2->index);
768 /* ??? We can handle computed jumps too. This may be important for
769 inlined functions containing switch statements. Also jumps w/o
770 fallthru edges can be handled by simply matching whole insn. */
774 /* E1 and E2 are edges with the same destination block. Search their
775 predecessors for common code. If found, redirect control flow from
776 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
779 try_crossjump_to_edge (mode, e1, e2)
784 basic_block src1 = e1->src, src2 = e2->src;
785 basic_block redirect_to;
786 rtx newpos1, newpos2;
792 /* Search backward through forwarder blocks. We don't need to worry
793 about multiple entry or chained forwarders, as they will be optimized
794 away. We do this to look past the unconditional jump following a
795 conditional jump that is required due to the current CFG shape. */
797 && !src1->pred->pred_next
798 && forwarder_block_p (src1))
804 && !src2->pred->pred_next
805 && forwarder_block_p (src2))
811 /* Nothing to do if we reach ENTRY, or a common source block. */
812 if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
817 /* Seeing more than 1 forwarder blocks would confuse us later... */
818 if (forwarder_block_p (e1->dest)
819 && forwarder_block_p (e1->dest->succ->dest))
821 if (forwarder_block_p (e2->dest)
822 && forwarder_block_p (e2->dest->succ->dest))
825 /* Likewise with dead code (possibly newly created by the other optimizations
827 if (!src1->pred || !src2->pred)
830 /* Likewise with complex edges.
831 ??? We should be able to handle most complex edges later with some
833 if (e1->flags & EDGE_COMPLEX)
836 /* Look for the common insn sequence, part the first ... */
837 if (!outgoing_edges_match (src1, src2))
840 /* ... and part the second. */
841 nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
845 /* Avoid splitting if possible. */
846 if (newpos2 == src2->head)
851 fprintf (rtl_dump_file, "Splitting bb %i before %i insns\n",
852 src2->index, nmatch);
853 redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
857 fprintf (rtl_dump_file,
858 "Cross jumping from bb %i to bb %i; %i common insns\n",
859 src1->index, src2->index, nmatch);
861 redirect_to->count += src1->count;
862 redirect_to->frequency += src1->frequency;
864 /* Recompute the frequencies and counts of outgoing edges. */
865 for (s = redirect_to->succ; s; s = s->succ_next)
868 basic_block d = s->dest;
870 if (forwarder_block_p (d))
872 for (s2 = src1->succ; ; s2 = s2->succ_next)
874 basic_block d2 = s2->dest;
875 if (forwarder_block_p (d2))
880 s->count += s2->count;
882 /* Take care to update possible forwarder blocks. We verified
883 that there is no more than one in the chain, so we can't run
884 into infinite loop. */
885 if (forwarder_block_p (s->dest))
887 s->dest->succ->count += s2->count;
888 s->dest->count += s2->count;
889 s->dest->frequency += EDGE_FREQUENCY (s);
891 if (forwarder_block_p (s2->dest))
893 s2->dest->succ->count -= s2->count;
894 s2->dest->count -= s2->count;
895 s2->dest->frequency -= EDGE_FREQUENCY (s);
897 if (!redirect_to->frequency && !src1->frequency)
898 s->probability = (s->probability + s2->probability) / 2;
901 ((s->probability * redirect_to->frequency +
902 s2->probability * src1->frequency)
903 / (redirect_to->frequency + src1->frequency));
906 note = find_reg_note (redirect_to->end, REG_BR_PROB, 0);
908 XEXP (note, 0) = GEN_INT (BRANCH_EDGE (redirect_to)->probability);
910 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
912 /* Skip possible basic block header. */
913 if (GET_CODE (newpos1) == CODE_LABEL)
914 newpos1 = NEXT_INSN (newpos1);
915 if (GET_CODE (newpos1) == NOTE)
916 newpos1 = NEXT_INSN (newpos1);
919 /* Emit the jump insn. */
920 label = block_label (redirect_to);
921 emit_jump_insn_after (gen_jump (label), src1->end);
922 JUMP_LABEL (src1->end) = label;
923 LABEL_NUSES (label)++;
925 /* Delete the now unreachable instructions. */
926 delete_insn_chain (newpos1, last);
928 /* Make sure there is a barrier after the new jump. */
929 last = next_nonnote_insn (src1->end);
930 if (!last || GET_CODE (last) != BARRIER)
931 emit_barrier_after (src1->end);
935 remove_edge (src1->succ);
936 make_single_succ_edge (src1, redirect_to, 0);
941 /* Search the predecessors of BB for common insn sequences. When found,
942 share code between them by redirecting control flow. Return true if
946 try_crossjump_bb (mode, bb)
950 edge e, e2, nexte2, nexte, fallthru;
953 /* Nothing to do if there is not at least two incomming edges. */
954 if (!bb->pred || !bb->pred->pred_next)
957 /* It is always cheapest to redirect a block that ends in a branch to
958 a block that falls through into BB, as that adds no branches to the
959 program. We'll try that combination first. */
960 for (fallthru = bb->pred; fallthru; fallthru = fallthru->pred_next)
961 if (fallthru->flags & EDGE_FALLTHRU)
965 for (e = bb->pred; e; e = nexte)
967 nexte = e->pred_next;
969 /* Elide complex edges now, as neither try_crossjump_to_edge
970 nor outgoing_edges_match can handle them. */
971 if (e->flags & EDGE_COMPLEX)
974 /* As noted above, first try with the fallthru predecessor. */
977 /* Don't combine the fallthru edge into anything else.
978 If there is a match, we'll do it the other way around. */
982 if (try_crossjump_to_edge (mode, e, fallthru))
990 /* Non-obvious work limiting check: Recognize that we're going
991 to call try_crossjump_bb on every basic block. So if we have
992 two blocks with lots of outgoing edges (a switch) and they
993 share lots of common destinations, then we would do the
994 cross-jump check once for each common destination.
996 Now, if the blocks actually are cross-jump candidates, then
997 all of their destinations will be shared. Which means that
998 we only need check them for cross-jump candidacy once. We
999 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1000 choosing to do the check from the block for which the edge
1001 in question is the first successor of A. */
1002 if (e->src->succ != e)
1005 for (e2 = bb->pred; e2; e2 = nexte2)
1007 nexte2 = e2->pred_next;
1012 /* We've already checked the fallthru edge above. */
1016 /* Again, neither try_crossjump_to_edge nor outgoing_edges_match
1017 can handle complex edges. */
1018 if (e2->flags & EDGE_COMPLEX)
1021 /* The "first successor" check above only prevents multiple
1022 checks of crossjump(A,B). In order to prevent redundant
1023 checks of crossjump(B,A), require that A be the block
1024 with the lowest index. */
1025 if (e->src->index > e2->src->index)
1028 if (try_crossjump_to_edge (mode, e, e2))
1040 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1041 instructions etc. Return nonzero if changes were made. */
1044 try_optimize_cfg (mode)
1048 bool changed_overall = false;
1052 if (mode & CLEANUP_CROSSJUMP)
1053 add_noreturn_fake_exit_edges ();
1055 /* Attempt to merge blocks as made possible by edge removal. If a block
1056 has only one successor, and the successor has only one predecessor,
1057 they may be combined. */
1065 fprintf (rtl_dump_file, "\n\ntry_optimize_cfg iteration %i\n\n",
1068 for (i = 0; i < n_basic_blocks;)
1070 basic_block c, b = BASIC_BLOCK (i);
1072 bool changed_here = false;
1074 /* Delete trivially dead basic blocks. */
1075 while (b->pred == NULL)
1077 c = BASIC_BLOCK (b->index - 1);
1079 fprintf (rtl_dump_file, "Deleting block %i.\n", b->index);
1080 flow_delete_block (b);
1085 /* Remove code labels no longer used. Don't do this before
1086 CALL_PLACEHOLDER is removed, as some branches may be hidden
1088 if (b->pred->pred_next == NULL
1089 && (b->pred->flags & EDGE_FALLTHRU)
1090 && !(b->pred->flags & EDGE_COMPLEX)
1091 && GET_CODE (b->head) == CODE_LABEL
1092 && (!(mode & CLEANUP_PRE_SIBCALL)
1093 || !tail_recursion_label_p (b->head))
1094 /* If previous block ends with condjump jumping to next BB,
1095 we can't delete the label. */
1096 && (b->pred->src == ENTRY_BLOCK_PTR
1097 || !reg_mentioned_p (b->head, b->pred->src->end)))
1099 rtx label = b->head;
1100 b->head = NEXT_INSN (b->head);
1101 delete_insn_chain (label, label);
1103 fprintf (rtl_dump_file, "Deleted label in block %i.\n",
1107 /* If we fall through an empty block, we can remove it. */
1108 if (b->pred->pred_next == NULL
1109 && (b->pred->flags & EDGE_FALLTHRU)
1110 && GET_CODE (b->head) != CODE_LABEL
1111 && forwarder_block_p (b)
1112 /* Note that forwarder_block_p true ensures that there
1113 is a successor for this block. */
1114 && (b->succ->flags & EDGE_FALLTHRU)
1115 && n_basic_blocks > 1)
1118 fprintf (rtl_dump_file, "Deleting fallthru block %i.\n",
1120 c = BASIC_BLOCK (b->index ? b->index - 1 : 1);
1121 redirect_edge_succ_nodup (b->pred, b->succ->dest);
1122 flow_delete_block (b);
1127 /* Merge blocks. Loop because chains of blocks might be
1129 while ((s = b->succ) != NULL
1130 && s->succ_next == NULL
1131 && !(s->flags & EDGE_COMPLEX)
1132 && (c = s->dest) != EXIT_BLOCK_PTR
1133 && c->pred->pred_next == NULL
1134 /* If the jump insn has side effects,
1135 we can't kill the edge. */
1136 && (GET_CODE (b->end) != JUMP_INSN
1137 || onlyjump_p (b->end))
1138 && merge_blocks (s, b, c, mode))
1139 changed_here = true;
1141 /* Simplify branch over branch. */
1142 if ((mode & CLEANUP_EXPENSIVE) && try_simplify_condjump (b))
1143 changed_here = true;
1145 /* If B has a single outgoing edge, but uses a non-trivial jump
1146 instruction without side-effects, we can either delete the
1147 jump entirely, or replace it with a simple unconditional jump.
1148 Use redirect_edge_and_branch to do the dirty work. */
1150 && ! b->succ->succ_next
1151 && b->succ->dest != EXIT_BLOCK_PTR
1152 && onlyjump_p (b->end)
1153 && redirect_edge_and_branch (b->succ, b->succ->dest))
1154 changed_here = true;
1156 /* Simplify branch to branch. */
1157 if (try_forward_edges (mode, b))
1158 changed_here = true;
1160 /* Look for shared code between blocks. */
1161 if ((mode & CLEANUP_CROSSJUMP)
1162 && try_crossjump_bb (mode, b))
1163 changed_here = true;
1165 /* Don't get confused by the index shift caused by deleting
1173 if ((mode & CLEANUP_CROSSJUMP)
1174 && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
1177 #ifdef ENABLE_CHECKING
1179 verify_flow_info ();
1182 changed_overall |= changed;
1186 if (mode & CLEANUP_CROSSJUMP)
1187 remove_fake_edges ();
1189 return changed_overall;
1192 /* Delete all unreachable basic blocks. */
1195 delete_unreachable_blocks ()
1198 bool changed = false;
1200 find_unreachable_blocks ();
1202 /* Delete all unreachable basic blocks. Count down so that we
1203 don't interfere with the block renumbering that happens in
1204 flow_delete_block. */
1206 for (i = n_basic_blocks - 1; i >= 0; --i)
1208 basic_block b = BASIC_BLOCK (i);
1210 if (!(b->flags & BB_REACHABLE))
1211 flow_delete_block (b), changed = true;
1215 tidy_fallthru_edges ();
1219 /* Tidy the CFG by deleting unreachable code and whatnot. */
1226 bool changed = false;
1228 timevar_push (TV_CLEANUP_CFG);
1229 changed = delete_unreachable_blocks ();
1230 if (try_optimize_cfg (mode))
1231 delete_unreachable_blocks (), changed = true;
1233 /* Kill the data we won't maintain. */
1234 free_EXPR_LIST_list (&label_value_list);
1235 free_EXPR_LIST_list (&tail_recursion_label_list);
1236 timevar_pop (TV_CLEANUP_CFG);
1238 /* Clear bb->aux on all basic blocks. */
1239 for (i = 0; i < n_basic_blocks; ++i)
1240 BASIC_BLOCK (i)->aux = NULL;