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 successor. 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 /* cleanup_cfg maintains following flags for each basic block. */
50 /* Set if life info needs to be recomputed for given BB. */
52 /* Set if BB is the forwarder block to avoid too many
53 forwarder_block_p calls. */
54 BB_FORWARDER_BLOCK = 2
57 #define BB_FLAGS(bb) (enum bb_flags)(bb)->aux
58 #define BB_SET_FLAG(bb,flag) \
59 (bb)->aux = (void *) (long) ((enum bb_flags)(bb)->aux | (flag))
60 #define BB_CLEAR_FLAG(bb,flag) \
61 (bb)->aux = (void *) (long) ((enum bb_flags)(bb)->aux & ~(flag))
63 #define FORWARDER_BLOCK_P(bb) (BB_FLAGS(bb) & BB_FORWARDER_BLOCK)
65 static bool try_crossjump_to_edge PARAMS ((int, edge, edge));
66 static bool try_crossjump_bb PARAMS ((int, basic_block));
67 static bool outgoing_edges_match PARAMS ((basic_block, basic_block));
68 static int flow_find_cross_jump PARAMS ((int, basic_block, basic_block,
71 static bool delete_unreachable_blocks PARAMS ((void));
72 static bool label_is_jump_target_p PARAMS ((rtx, rtx));
73 static bool tail_recursion_label_p PARAMS ((rtx));
74 static void merge_blocks_move_predecessor_nojumps PARAMS ((basic_block,
76 static void merge_blocks_move_successor_nojumps PARAMS ((basic_block,
78 static bool merge_blocks PARAMS ((edge,basic_block,basic_block,
80 static bool try_optimize_cfg PARAMS ((int));
81 static bool try_simplify_condjump PARAMS ((basic_block));
82 static bool try_forward_edges PARAMS ((int, basic_block));
83 static void notice_new_block PARAMS ((basic_block));
84 static void update_forwarder_flag PARAMS ((basic_block));
86 /* Set flags for newly created block. */
94 BB_SET_FLAG (bb, BB_UPDATE_LIFE);
95 if (forwarder_block_p (bb))
96 BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
99 /* Recompute forwarder flag after block has been modified. */
102 update_forwarder_flag (bb)
105 if (forwarder_block_p (bb))
106 BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
108 BB_CLEAR_FLAG (bb, BB_FORWARDER_BLOCK);
111 /* Simplify a conditional jump around an unconditional jump.
112 Return true if something changed. */
115 try_simplify_condjump (cbranch_block)
116 basic_block cbranch_block;
118 basic_block jump_block, jump_dest_block, cbranch_dest_block;
119 edge cbranch_jump_edge, cbranch_fallthru_edge;
122 /* Verify that there are exactly two successors. */
123 if (!cbranch_block->succ
124 || !cbranch_block->succ->succ_next
125 || cbranch_block->succ->succ_next->succ_next)
128 /* Verify that we've got a normal conditional branch at the end
130 cbranch_insn = cbranch_block->end;
131 if (!any_condjump_p (cbranch_insn))
134 cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
135 cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
137 /* The next block must not have multiple predecessors, must not
138 be the last block in the function, and must contain just the
139 unconditional jump. */
140 jump_block = cbranch_fallthru_edge->dest;
141 if (jump_block->pred->pred_next
142 || jump_block->index == n_basic_blocks - 1
143 || !FORWARDER_BLOCK_P (jump_block))
145 jump_dest_block = jump_block->succ->dest;
147 /* The conditional branch must target the block after the
148 unconditional branch. */
149 cbranch_dest_block = cbranch_jump_edge->dest;
151 if (!can_fallthru (jump_block, cbranch_dest_block))
154 /* Invert the conditional branch. */
155 if (!invert_jump (cbranch_insn, block_label (jump_dest_block), 0))
159 fprintf (rtl_dump_file, "Simplifying condjump %i around jump %i\n",
160 INSN_UID (cbranch_insn), INSN_UID (jump_block->end));
162 /* Success. Update the CFG to match. Note that after this point
163 the edge variable names appear backwards; the redirection is done
164 this way to preserve edge profile data. */
165 cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
167 cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
169 cbranch_jump_edge->flags |= EDGE_FALLTHRU;
170 cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
172 /* Delete the block with the unconditional jump, and clean up the mess. */
173 flow_delete_block (jump_block);
174 tidy_fallthru_edge (cbranch_jump_edge, cbranch_block, cbranch_dest_block);
179 /* Attempt to forward edges leaving basic block B.
180 Return true if successful. */
183 try_forward_edges (mode, b)
187 bool changed = false;
190 for (e = b->succ; e ; e = next)
192 basic_block target, first;
197 /* Skip complex edges because we don't know how to update them.
199 Still handle fallthru edges, as we can succeed to forward fallthru
200 edge to the same place as the branch edge of conditional branch
201 and turn conditional branch to an unconditional branch. */
202 if (e->flags & EDGE_COMPLEX)
205 target = first = e->dest;
208 /* Look for the real destination of the jump.
209 Avoid infinite loop in the infinite empty loop by counting
210 up to n_basic_blocks. */
211 while (FORWARDER_BLOCK_P (target)
212 && target->succ->dest != EXIT_BLOCK_PTR
213 && counter < n_basic_blocks)
215 /* Bypass trivial infinite loops. */
216 if (target == target->succ->dest)
217 counter = n_basic_blocks;
219 /* Avoid killing of loop pre-headers, as it is the place loop
220 optimizer wants to hoist code to.
222 For fallthru forwarders, the LOOP_BEG note must appear between
223 the header of block and CODE_LABEL of the loop, for non forwarders
224 it must appear before the JUMP_INSN. */
225 if (mode & CLEANUP_PRE_LOOP)
227 rtx insn = (target->succ->flags & EDGE_FALLTHRU
228 ? target->head : prev_nonnote_insn (target->end));
230 if (GET_CODE (insn) != NOTE)
231 insn = NEXT_INSN (insn);
233 for (;insn && GET_CODE (insn) != CODE_LABEL && !INSN_P (insn);
234 insn = NEXT_INSN (insn))
235 if (GET_CODE (insn) == NOTE
236 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
239 if (GET_CODE (insn) == NOTE)
242 target = target->succ->dest, counter++;
245 if (counter >= n_basic_blocks)
248 fprintf (rtl_dump_file, "Infinite loop in BB %i.\n",
251 else if (target == first)
252 ; /* We didn't do anything. */
255 /* Save the values now, as the edge may get removed. */
256 gcov_type edge_count = e->count;
257 int edge_probability = e->probability;
259 if (redirect_edge_and_branch (e, target))
261 /* We successfully forwarded the edge. Now update profile
262 data: for each edge we traversed in the chain, remove
263 the original edge's execution count. */
264 int edge_frequency = ((edge_probability * b->frequency
265 + REG_BR_PROB_BASE / 2)
268 if (!FORWARDER_BLOCK_P (b) && forwarder_block_p (b))
269 BB_SET_FLAG (b, BB_FORWARDER_BLOCK);
270 BB_SET_FLAG (b, BB_UPDATE_LIFE);
274 first->count -= edge_count;
275 first->succ->count -= edge_count;
276 first->frequency -= edge_frequency;
277 first = first->succ->dest;
279 while (first != target);
286 fprintf (rtl_dump_file, "Forwarding edge %i->%i to %i failed.\n",
287 b->index, e->dest->index, target->index);
295 /* Return true if LABEL is a target of JUMP_INSN. This applies only
296 to non-complex jumps. That is, direct unconditional, conditional,
297 and tablejumps, but not computed jumps or returns. It also does
298 not apply to the fallthru case of a conditional jump. */
301 label_is_jump_target_p (label, jump_insn)
302 rtx label, jump_insn;
304 rtx tmp = JUMP_LABEL (jump_insn);
310 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
311 && GET_CODE (tmp) == JUMP_INSN
312 && (tmp = PATTERN (tmp),
313 GET_CODE (tmp) == ADDR_VEC
314 || GET_CODE (tmp) == ADDR_DIFF_VEC))
316 rtvec vec = XVEC (tmp, GET_CODE (tmp) == ADDR_DIFF_VEC);
317 int i, veclen = GET_NUM_ELEM (vec);
319 for (i = 0; i < veclen; ++i)
320 if (XEXP (RTVEC_ELT (vec, i), 0) == label)
327 /* Return true if LABEL is used for tail recursion. */
330 tail_recursion_label_p (label)
335 for (x = tail_recursion_label_list; x; x = XEXP (x, 1))
336 if (label == XEXP (x, 0))
342 /* Blocks A and B are to be merged into a single block. A has no incoming
343 fallthru edge, so it can be moved before B without adding or modifying
344 any jumps (aside from the jump from A to B). */
347 merge_blocks_move_predecessor_nojumps (a, b)
353 barrier = next_nonnote_insn (a->end);
354 if (GET_CODE (barrier) != BARRIER)
356 delete_insn (barrier);
358 /* Move block and loop notes out of the chain so that we do not
361 ??? A better solution would be to squeeze out all the non-nested notes
362 and adjust the block trees appropriately. Even better would be to have
363 a tighter connection between block trees and rtl so that this is not
365 if (squeeze_notes (&a->head, &a->end))
368 /* Scramble the insn chain. */
369 if (a->end != PREV_INSN (b->head))
370 reorder_insns_nobb (a->head, a->end, PREV_INSN (b->head));
371 BB_SET_FLAG (a, BB_UPDATE_LIFE);
375 fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
379 /* Swap the records for the two blocks around. Although we are deleting B,
380 A is now where B was and we want to compact the BB array from where
382 BASIC_BLOCK (a->index) = b;
383 BASIC_BLOCK (b->index) = a;
388 /* Now blocks A and B are contiguous. Merge them. */
389 merge_blocks_nomove (a, b);
392 /* Blocks A and B are to be merged into a single block. B has no outgoing
393 fallthru edge, so it can be moved after A without adding or modifying
394 any jumps (aside from the jump from A to B). */
397 merge_blocks_move_successor_nojumps (a, b)
400 rtx barrier, real_b_end;
403 barrier = NEXT_INSN (b->end);
405 /* Recognize a jump table following block B. */
407 && GET_CODE (barrier) == CODE_LABEL
408 && NEXT_INSN (barrier)
409 && GET_CODE (NEXT_INSN (barrier)) == JUMP_INSN
410 && (GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_VEC
411 || GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_DIFF_VEC))
413 /* Temporarily add the table jump insn to b, so that it will also
414 be moved to the correct location. */
415 b->end = NEXT_INSN (barrier);
416 barrier = NEXT_INSN (b->end);
419 /* There had better have been a barrier there. Delete it. */
420 if (barrier && GET_CODE (barrier) == BARRIER)
421 delete_insn (barrier);
423 /* Move block and loop notes out of the chain so that we do not
426 ??? A better solution would be to squeeze out all the non-nested notes
427 and adjust the block trees appropriately. Even better would be to have
428 a tighter connection between block trees and rtl so that this is not
430 if (squeeze_notes (&b->head, &b->end))
433 /* Scramble the insn chain. */
434 reorder_insns_nobb (b->head, b->end, a->end);
436 /* Restore the real end of b. */
439 /* Now blocks A and B are contiguous. Merge them. */
440 merge_blocks_nomove (a, b);
441 BB_SET_FLAG (a, BB_UPDATE_LIFE);
445 fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
450 /* Attempt to merge basic blocks that are potentially non-adjacent.
451 Return true iff the attempt succeeded. */
454 merge_blocks (e, b, c, mode)
459 /* If C has a tail recursion label, do not merge. There is no
460 edge recorded from the call_placeholder back to this label, as
461 that would make optimize_sibling_and_tail_recursive_calls more
462 complex for no gain. */
463 if ((mode & CLEANUP_PRE_SIBCALL)
464 && GET_CODE (c->head) == CODE_LABEL
465 && tail_recursion_label_p (c->head))
468 /* If B has a fallthru edge to C, no need to move anything. */
469 if (e->flags & EDGE_FALLTHRU)
471 /* We need to update liveness in case C already has broken liveness
472 or B ends by conditional jump to next instructions that will be
474 if ((BB_FLAGS (c) & BB_UPDATE_LIFE)
475 || GET_CODE (b->end) == JUMP_INSN)
476 BB_SET_FLAG (b, BB_UPDATE_LIFE);
477 merge_blocks_nomove (b, c);
478 update_forwarder_flag (b);
482 fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
488 /* Otherwise we will need to move code around. Do that only if expensive
489 transformations are allowed. */
490 else if (mode & CLEANUP_EXPENSIVE)
492 edge tmp_edge, b_fallthru_edge;
493 bool c_has_outgoing_fallthru;
494 bool b_has_incoming_fallthru;
496 /* Avoid overactive code motion, as the forwarder blocks should be
497 eliminated by edge redirection instead. One exception might have
498 been if B is a forwarder block and C has no fallthru edge, but
499 that should be cleaned up by bb-reorder instead. */
500 if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
503 /* We must make sure to not munge nesting of lexical blocks,
504 and loop notes. This is done by squeezing out all the notes
505 and leaving them there to lie. Not ideal, but functional. */
507 for (tmp_edge = c->succ; tmp_edge; tmp_edge = tmp_edge->succ_next)
508 if (tmp_edge->flags & EDGE_FALLTHRU)
510 c_has_outgoing_fallthru = (tmp_edge != NULL);
512 for (tmp_edge = b->pred; tmp_edge; tmp_edge = tmp_edge->pred_next)
513 if (tmp_edge->flags & EDGE_FALLTHRU)
515 b_has_incoming_fallthru = (tmp_edge != NULL);
516 b_fallthru_edge = tmp_edge;
518 /* Otherwise, we're going to try to move C after B. If C does
519 not have an outgoing fallthru, then it can be moved
520 immediately after B without introducing or modifying jumps. */
521 if (! c_has_outgoing_fallthru)
523 merge_blocks_move_successor_nojumps (b, c);
527 /* If B does not have an incoming fallthru, then it can be moved
528 immediately before C without introducing or modifying jumps.
529 C cannot be the first block, so we do not have to worry about
530 accessing a non-existent block. */
532 if (b_has_incoming_fallthru)
535 if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
537 bb = force_nonfallthru (b_fallthru_edge);
539 notice_new_block (bb);
541 BB_SET_FLAG (b_fallthru_edge->src, BB_UPDATE_LIFE);
543 merge_blocks_move_predecessor_nojumps (b, c);
549 /* Look through the insns at the end of BB1 and BB2 and find the longest
550 sequence that are equivalent. Store the first insns for that sequence
551 in *F1 and *F2 and return the sequence length.
553 To simplify callers of this function, if the blocks match exactly,
554 store the head of the blocks in *F1 and *F2. */
557 flow_find_cross_jump (mode, bb1, bb2, f1, f2)
558 int mode ATTRIBUTE_UNUSED;
559 basic_block bb1, bb2;
562 rtx i1, i2, p1, p2, last1, last2, afterlast1, afterlast2;
565 /* Skip simple jumps at the end of the blocks. Complex jumps still
566 need to be compared for equivalence, which we'll do below. */
570 || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
574 || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
577 last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
581 while ((GET_CODE (i1) == NOTE && i1 != bb1->head))
583 while ((GET_CODE (i2) == NOTE && i2 != bb2->head))
586 if (i1 == bb1->head || i2 == bb2->head)
589 /* Verify that I1 and I2 are equivalent. */
591 if (GET_CODE (i1) != GET_CODE (i2))
597 /* If this is a CALL_INSN, compare register usage information.
598 If we don't check this on stack register machines, the two
599 CALL_INSNs might be merged leaving reg-stack.c with mismatching
600 numbers of stack registers in the same basic block.
601 If we don't check this on machines with delay slots, a delay slot may
602 be filled that clobbers a parameter expected by the subroutine.
604 ??? We take the simple route for now and assume that if they're
605 equal, they were constructed identically. */
607 if (GET_CODE (i1) == CALL_INSN
608 && ! rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
609 CALL_INSN_FUNCTION_USAGE (i2)))
613 /* If cross_jump_death_matters is not 0, the insn's mode
614 indicates whether or not the insn contains any stack-like
617 if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
619 /* If register stack conversion has already been done, then
620 death notes must also be compared before it is certain that
621 the two instruction streams match. */
624 HARD_REG_SET i1_regset, i2_regset;
626 CLEAR_HARD_REG_SET (i1_regset);
627 CLEAR_HARD_REG_SET (i2_regset);
629 for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
630 if (REG_NOTE_KIND (note) == REG_DEAD
631 && STACK_REG_P (XEXP (note, 0)))
632 SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
634 for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
635 if (REG_NOTE_KIND (note) == REG_DEAD
636 && STACK_REG_P (XEXP (note, 0)))
637 SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
639 GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
648 if (GET_CODE (p1) != GET_CODE (p2))
651 if (! rtx_renumbered_equal_p (p1, p2))
653 /* The following code helps take care of G++ cleanups. */
654 rtx equiv1 = find_reg_equal_equiv_note (i1);
655 rtx equiv2 = find_reg_equal_equiv_note (i2);
658 /* If the equivalences are not to a constant, they may
659 reference pseudos that no longer exist, so we can't
661 && CONSTANT_P (XEXP (equiv1, 0))
662 && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
664 rtx s1 = single_set (i1);
665 rtx s2 = single_set (i2);
666 if (s1 != 0 && s2 != 0
667 && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
669 validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
670 validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
671 if (! rtx_renumbered_equal_p (p1, p2))
673 else if (apply_change_group ())
681 /* Don't begin a cross-jump with a USE or CLOBBER insn. */
682 if (GET_CODE (p1) != USE && GET_CODE (p1) != CLOBBER)
684 /* If the merged insns have different REG_EQUAL notes, then
686 rtx equiv1 = find_reg_equal_equiv_note (i1);
687 rtx equiv2 = find_reg_equal_equiv_note (i2);
689 if (equiv1 && !equiv2)
690 remove_note (i1, equiv1);
691 else if (!equiv1 && equiv2)
692 remove_note (i2, equiv2);
693 else if (equiv1 && equiv2
694 && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
696 remove_note (i1, equiv1);
697 remove_note (i2, equiv2);
700 afterlast1 = last1, afterlast2 = last2;
701 last1 = i1, last2 = i2;
711 /* Don't allow the insn after a compare to be shared by
712 cross-jumping unless the compare is also shared. */
713 if (reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
714 last1 = afterlast1, last2 = afterlast2, ninsns--;
718 /* Include preceding notes and labels in the cross-jump. One,
719 this may bring us to the head of the blocks as requested above.
720 Two, it keeps line number notes as matched as may be. */
723 while (last1 != bb1->head && GET_CODE (PREV_INSN (last1)) == NOTE)
724 last1 = PREV_INSN (last1);
725 if (last1 != bb1->head && GET_CODE (PREV_INSN (last1)) == CODE_LABEL)
726 last1 = PREV_INSN (last1);
727 while (last2 != bb2->head && GET_CODE (PREV_INSN (last2)) == NOTE)
728 last2 = PREV_INSN (last2);
729 if (last2 != bb2->head && GET_CODE (PREV_INSN (last2)) == CODE_LABEL)
730 last2 = PREV_INSN (last2);
739 /* Return true iff outgoing edges of BB1 and BB2 match, together with
740 the branch instruction. This means that if we commonize the control
741 flow before end of the basic block, the semantic remains unchanged.
743 We may assume that there exists one edge with a common destination. */
746 outgoing_edges_match (bb1, bb2)
750 /* If BB1 has only one successor, we must be looking at an unconditional
751 jump. Which, by the assumption above, means that we only need to check
752 that BB2 has one successor. */
753 if (bb1->succ && !bb1->succ->succ_next)
754 return (bb2->succ && !bb2->succ->succ_next);
756 /* Match conditional jumps - this may get tricky when fallthru and branch
757 edges are crossed. */
759 && bb1->succ->succ_next
760 && !bb1->succ->succ_next->succ_next
761 && any_condjump_p (bb1->end))
765 rtx set1, set2, cond1, cond2;
766 enum rtx_code code1, code2;
769 || !bb2->succ->succ_next
770 || bb1->succ->succ_next->succ_next
771 || !any_condjump_p (bb2->end))
774 b1 = BRANCH_EDGE (bb1);
775 b2 = BRANCH_EDGE (bb2);
776 f1 = FALLTHRU_EDGE (bb1);
777 f2 = FALLTHRU_EDGE (bb2);
779 /* Get around possible forwarders on fallthru edges. Other cases
780 should be optimized out already. */
781 if (FORWARDER_BLOCK_P (f1->dest))
783 if (FORWARDER_BLOCK_P (f2->dest))
786 /* To simplify use of this function, return false if there are
787 unneeded forwarder blocks. These will get eliminated later
788 during cleanup_cfg. */
789 if (FORWARDER_BLOCK_P (f1->dest)
790 || FORWARDER_BLOCK_P (f2->dest)
791 || FORWARDER_BLOCK_P (b1->dest)
792 || FORWARDER_BLOCK_P (b2->dest))
795 if (f1->dest == f2->dest && b1->dest == b2->dest)
797 else if (f1->dest == b2->dest && b1->dest == f2->dest)
802 set1 = pc_set (bb1->end);
803 set2 = pc_set (bb2->end);
804 if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
805 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
808 cond1 = XEXP (SET_SRC (set1), 0);
809 cond2 = XEXP (SET_SRC (set2), 0);
810 code1 = GET_CODE (cond1);
812 code2 = reversed_comparison_code (cond2, bb2->end);
814 code2 = GET_CODE (cond2);
815 if (code2 == UNKNOWN)
818 /* Verify codes and operands match. */
819 match = ((code1 == code2
820 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
821 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
822 || (code1 == swap_condition (code2)
823 && rtx_renumbered_equal_p (XEXP (cond1, 1),
825 && rtx_renumbered_equal_p (XEXP (cond1, 0),
828 /* If we return true, we will join the blocks. Which means that
829 we will only have one branch prediction bit to work with. Thus
830 we require the existing branches to have probabilities that are
832 /* ??? We should use bb->frequency to allow merging in infrequently
833 executed blocks, but at the moment it is not available when
834 cleanup_cfg is run. */
835 if (match && !optimize_size)
839 note1 = find_reg_note (bb1->end, REG_BR_PROB, 0);
840 note2 = find_reg_note (bb2->end, REG_BR_PROB, 0);
844 prob1 = INTVAL (XEXP (note1, 0));
845 prob2 = INTVAL (XEXP (note2, 0));
847 prob2 = REG_BR_PROB_BASE - prob2;
849 /* Fail if the difference in probabilities is
851 if (abs (prob1 - prob2) > REG_BR_PROB_BASE / 20)
854 else if (note1 || note2)
858 if (rtl_dump_file && match)
859 fprintf (rtl_dump_file, "Conditionals in bb %i and %i match.\n",
860 bb1->index, bb2->index);
865 /* ??? We can handle computed jumps too. This may be important for
866 inlined functions containing switch statements. Also jumps w/o
867 fallthru edges can be handled by simply matching whole insn. */
871 /* E1 and E2 are edges with the same destination block. Search their
872 predecessors for common code. If found, redirect control flow from
873 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
876 try_crossjump_to_edge (mode, e1, e2)
881 basic_block src1 = e1->src, src2 = e2->src;
882 basic_block redirect_to;
883 rtx newpos1, newpos2;
889 /* Search backward through forwarder blocks. We don't need to worry
890 about multiple entry or chained forwarders, as they will be optimized
891 away. We do this to look past the unconditional jump following a
892 conditional jump that is required due to the current CFG shape. */
894 && !src1->pred->pred_next
895 && FORWARDER_BLOCK_P (src1))
901 && !src2->pred->pred_next
902 && FORWARDER_BLOCK_P (src2))
908 /* Nothing to do if we reach ENTRY, or a common source block. */
909 if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
914 /* Seeing more than 1 forwarder blocks would confuse us later... */
915 if (FORWARDER_BLOCK_P (e1->dest)
916 && FORWARDER_BLOCK_P (e1->dest->succ->dest))
918 if (FORWARDER_BLOCK_P (e2->dest)
919 && FORWARDER_BLOCK_P (e2->dest->succ->dest))
922 /* Likewise with dead code (possibly newly created by the other optimizations
924 if (!src1->pred || !src2->pred)
927 /* Likewise with complex edges.
928 ??? We should be able to handle most complex edges later with some
930 if (e1->flags & EDGE_COMPLEX)
933 /* Look for the common insn sequence, part the first ... */
934 if (!outgoing_edges_match (src1, src2))
937 /* ... and part the second. */
938 nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
942 /* Avoid splitting if possible. */
943 if (newpos2 == src2->head)
948 fprintf (rtl_dump_file, "Splitting bb %i before %i insns\n",
949 src2->index, nmatch);
950 redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
954 fprintf (rtl_dump_file,
955 "Cross jumping from bb %i to bb %i; %i common insns\n",
956 src1->index, src2->index, nmatch);
958 redirect_to->count += src1->count;
959 redirect_to->frequency += src1->frequency;
961 /* Recompute the frequencies and counts of outgoing edges. */
962 for (s = redirect_to->succ; s; s = s->succ_next)
965 basic_block d = s->dest;
967 if (FORWARDER_BLOCK_P (d))
969 for (s2 = src1->succ; ; s2 = s2->succ_next)
971 basic_block d2 = s2->dest;
972 if (FORWARDER_BLOCK_P (d2))
977 s->count += s2->count;
979 /* Take care to update possible forwarder blocks. We verified
980 that there is no more than one in the chain, so we can't run
981 into infinite loop. */
982 if (FORWARDER_BLOCK_P (s->dest))
984 s->dest->succ->count += s2->count;
985 s->dest->count += s2->count;
986 s->dest->frequency += EDGE_FREQUENCY (s);
988 if (FORWARDER_BLOCK_P (s2->dest))
990 s2->dest->succ->count -= s2->count;
991 s2->dest->count -= s2->count;
992 s2->dest->frequency -= EDGE_FREQUENCY (s);
994 if (!redirect_to->frequency && !src1->frequency)
995 s->probability = (s->probability + s2->probability) / 2;
998 ((s->probability * redirect_to->frequency +
999 s2->probability * src1->frequency)
1000 / (redirect_to->frequency + src1->frequency));
1003 note = find_reg_note (redirect_to->end, REG_BR_PROB, 0);
1005 XEXP (note, 0) = GEN_INT (BRANCH_EDGE (redirect_to)->probability);
1007 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1009 /* Skip possible basic block header. */
1010 if (GET_CODE (newpos1) == CODE_LABEL)
1011 newpos1 = NEXT_INSN (newpos1);
1012 if (GET_CODE (newpos1) == NOTE)
1013 newpos1 = NEXT_INSN (newpos1);
1016 /* Emit the jump insn. */
1017 label = block_label (redirect_to);
1018 emit_jump_insn_after (gen_jump (label), src1->end);
1019 JUMP_LABEL (src1->end) = label;
1020 LABEL_NUSES (label)++;
1022 /* Delete the now unreachable instructions. */
1023 delete_insn_chain (newpos1, last);
1025 /* Make sure there is a barrier after the new jump. */
1026 last = next_nonnote_insn (src1->end);
1027 if (!last || GET_CODE (last) != BARRIER)
1028 emit_barrier_after (src1->end);
1032 remove_edge (src1->succ);
1033 make_single_succ_edge (src1, redirect_to, 0);
1035 BB_SET_FLAG (src1, BB_UPDATE_LIFE);
1036 update_forwarder_flag (src1);
1041 /* Search the predecessors of BB for common insn sequences. When found,
1042 share code between them by redirecting control flow. Return true if
1043 any changes made. */
1046 try_crossjump_bb (mode, bb)
1050 edge e, e2, nexte2, nexte, fallthru;
1053 /* Nothing to do if there is not at least two incoming edges. */
1054 if (!bb->pred || !bb->pred->pred_next)
1057 /* It is always cheapest to redirect a block that ends in a branch to
1058 a block that falls through into BB, as that adds no branches to the
1059 program. We'll try that combination first. */
1060 for (fallthru = bb->pred; fallthru; fallthru = fallthru->pred_next)
1061 if (fallthru->flags & EDGE_FALLTHRU)
1065 for (e = bb->pred; e; e = nexte)
1067 nexte = e->pred_next;
1069 /* Elide complex edges now, as neither try_crossjump_to_edge
1070 nor outgoing_edges_match can handle them. */
1071 if (e->flags & EDGE_COMPLEX)
1074 /* As noted above, first try with the fallthru predecessor. */
1077 /* Don't combine the fallthru edge into anything else.
1078 If there is a match, we'll do it the other way around. */
1082 if (try_crossjump_to_edge (mode, e, fallthru))
1090 /* Non-obvious work limiting check: Recognize that we're going
1091 to call try_crossjump_bb on every basic block. So if we have
1092 two blocks with lots of outgoing edges (a switch) and they
1093 share lots of common destinations, then we would do the
1094 cross-jump check once for each common destination.
1096 Now, if the blocks actually are cross-jump candidates, then
1097 all of their destinations will be shared. Which means that
1098 we only need check them for cross-jump candidacy once. We
1099 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1100 choosing to do the check from the block for which the edge
1101 in question is the first successor of A. */
1102 if (e->src->succ != e)
1105 for (e2 = bb->pred; e2; e2 = nexte2)
1107 nexte2 = e2->pred_next;
1112 /* We've already checked the fallthru edge above. */
1116 /* Again, neither try_crossjump_to_edge nor outgoing_edges_match
1117 can handle complex edges. */
1118 if (e2->flags & EDGE_COMPLEX)
1121 /* The "first successor" check above only prevents multiple
1122 checks of crossjump(A,B). In order to prevent redundant
1123 checks of crossjump(B,A), require that A be the block
1124 with the lowest index. */
1125 if (e->src->index > e2->src->index)
1128 if (try_crossjump_to_edge (mode, e, e2))
1140 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1141 instructions etc. Return nonzero if changes were made. */
1144 try_optimize_cfg (mode)
1148 bool changed_overall = false;
1153 if (mode & CLEANUP_CROSSJUMP)
1154 add_noreturn_fake_exit_edges ();
1156 for (i = 0; i < n_basic_blocks; i++)
1157 update_forwarder_flag (BASIC_BLOCK (i));
1159 /* Attempt to merge blocks as made possible by edge removal. If a block
1160 has only one successor, and the successor has only one predecessor,
1161 they may be combined. */
1169 fprintf (rtl_dump_file, "\n\ntry_optimize_cfg iteration %i\n\n",
1172 for (i = 0; i < n_basic_blocks;)
1174 basic_block c, b = BASIC_BLOCK (i);
1176 bool changed_here = false;
1178 /* Delete trivially dead basic blocks. */
1179 while (b->pred == NULL)
1181 c = BASIC_BLOCK (b->index - 1);
1183 fprintf (rtl_dump_file, "Deleting block %i.\n", b->index);
1184 flow_delete_block (b);
1189 /* Remove code labels no longer used. Don't do this before
1190 CALL_PLACEHOLDER is removed, as some branches may be hidden
1192 if (b->pred->pred_next == NULL
1193 && (b->pred->flags & EDGE_FALLTHRU)
1194 && !(b->pred->flags & EDGE_COMPLEX)
1195 && GET_CODE (b->head) == CODE_LABEL
1196 && (!(mode & CLEANUP_PRE_SIBCALL)
1197 || !tail_recursion_label_p (b->head))
1198 /* If the previous block ends with a branch to this block,
1199 we can't delete the label. Normally this is a condjump
1200 that is yet to be simplified, but if CASE_DROPS_THRU,
1201 this can be a tablejump with some element going to the
1202 same place as the default (fallthru). */
1203 && (b->pred->src == ENTRY_BLOCK_PTR
1204 || GET_CODE (b->pred->src->end) != JUMP_INSN
1205 || ! label_is_jump_target_p (b->head, b->pred->src->end)))
1207 rtx label = b->head;
1208 b->head = NEXT_INSN (b->head);
1209 delete_insn_chain (label, label);
1211 fprintf (rtl_dump_file, "Deleted label in block %i.\n",
1215 /* If we fall through an empty block, we can remove it. */
1216 if (b->pred->pred_next == NULL
1217 && (b->pred->flags & EDGE_FALLTHRU)
1218 && GET_CODE (b->head) != CODE_LABEL
1219 && FORWARDER_BLOCK_P (b)
1220 /* Note that forwarder_block_p true ensures that there
1221 is a successor for this block. */
1222 && (b->succ->flags & EDGE_FALLTHRU)
1223 && n_basic_blocks > 1)
1226 fprintf (rtl_dump_file, "Deleting fallthru block %i.\n",
1228 c = BASIC_BLOCK (b->index ? b->index - 1 : 1);
1229 redirect_edge_succ_nodup (b->pred, b->succ->dest);
1230 flow_delete_block (b);
1235 /* Merge blocks. Loop because chains of blocks might be
1237 while ((s = b->succ) != NULL
1238 && s->succ_next == NULL
1239 && !(s->flags & EDGE_COMPLEX)
1240 && (c = s->dest) != EXIT_BLOCK_PTR
1241 && c->pred->pred_next == NULL
1242 /* If the jump insn has side effects,
1243 we can't kill the edge. */
1244 && (GET_CODE (b->end) != JUMP_INSN
1245 || onlyjump_p (b->end))
1246 && merge_blocks (s, b, c, mode))
1247 changed_here = true;
1249 /* Simplify branch over branch. */
1250 if ((mode & CLEANUP_EXPENSIVE) && try_simplify_condjump (b))
1252 BB_SET_FLAG (b, BB_UPDATE_LIFE);
1253 changed_here = true;
1256 /* If B has a single outgoing edge, but uses a non-trivial jump
1257 instruction without side-effects, we can either delete the
1258 jump entirely, or replace it with a simple unconditional jump.
1259 Use redirect_edge_and_branch to do the dirty work. */
1261 && ! b->succ->succ_next
1262 && b->succ->dest != EXIT_BLOCK_PTR
1263 && onlyjump_p (b->end)
1264 && redirect_edge_and_branch (b->succ, b->succ->dest))
1266 BB_SET_FLAG (b, BB_UPDATE_LIFE);
1267 update_forwarder_flag (b);
1268 changed_here = true;
1271 /* Simplify branch to branch. */
1272 if (try_forward_edges (mode, b))
1273 changed_here = true;
1275 /* Look for shared code between blocks. */
1276 if ((mode & CLEANUP_CROSSJUMP)
1277 && try_crossjump_bb (mode, b))
1278 changed_here = true;
1280 /* Don't get confused by the index shift caused by deleting
1288 if ((mode & CLEANUP_CROSSJUMP)
1289 && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
1292 #ifdef ENABLE_CHECKING
1294 verify_flow_info ();
1297 changed_overall |= changed;
1301 if (mode & CLEANUP_CROSSJUMP)
1302 remove_fake_edges ();
1304 if ((mode & CLEANUP_UPDATE_LIFE) && changed_overall)
1307 blocks = sbitmap_alloc (n_basic_blocks);
1308 sbitmap_zero (blocks);
1309 for (i = 0; i < n_basic_blocks; i++)
1310 if (BB_FLAGS (BASIC_BLOCK (i)) & BB_UPDATE_LIFE)
1313 SET_BIT (blocks, i);
1316 update_life_info (blocks, UPDATE_LIFE_GLOBAL,
1317 PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
1318 | PROP_KILL_DEAD_CODE);
1319 sbitmap_free (blocks);
1321 for (i = 0; i < n_basic_blocks; i++)
1322 BASIC_BLOCK (i)->aux = NULL;
1324 return changed_overall;
1327 /* Delete all unreachable basic blocks. */
1330 delete_unreachable_blocks ()
1333 bool changed = false;
1335 find_unreachable_blocks ();
1337 /* Delete all unreachable basic blocks. Count down so that we
1338 don't interfere with the block renumbering that happens in
1339 flow_delete_block. */
1341 for (i = n_basic_blocks - 1; i >= 0; --i)
1343 basic_block b = BASIC_BLOCK (i);
1345 if (!(b->flags & BB_REACHABLE))
1346 flow_delete_block (b), changed = true;
1350 tidy_fallthru_edges ();
1354 /* Tidy the CFG by deleting unreachable code and whatnot. */
1360 bool changed = false;
1362 timevar_push (TV_CLEANUP_CFG);
1363 changed = delete_unreachable_blocks ();
1364 if (try_optimize_cfg (mode))
1365 delete_unreachable_blocks (), changed = true;
1367 /* Kill the data we won't maintain. */
1368 free_EXPR_LIST_list (&label_value_list);
1369 free_EXPR_LIST_list (&tail_recursion_label_list);
1370 timevar_pop (TV_CLEANUP_CFG);