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 tail_recursion_label_p
PARAMS ((rtx
));
73 static void merge_blocks_move_predecessor_nojumps
PARAMS ((basic_block
,
75 static void merge_blocks_move_successor_nojumps
PARAMS ((basic_block
,
77 static bool merge_blocks
PARAMS ((edge
,basic_block
,basic_block
,
79 static bool try_optimize_cfg
PARAMS ((int));
80 static bool try_simplify_condjump
PARAMS ((basic_block
));
81 static bool try_forward_edges
PARAMS ((int, basic_block
));
82 static void notice_new_block
PARAMS ((basic_block
));
83 static void update_forwarder_flag
PARAMS ((basic_block
));
85 /* Set flags for newly created block. */
93 BB_SET_FLAG (bb
, BB_UPDATE_LIFE
);
94 if (forwarder_block_p (bb
))
95 BB_SET_FLAG (bb
, BB_FORWARDER_BLOCK
);
98 /* Recompute forwarder flag after block has been modified. */
101 update_forwarder_flag (bb
)
104 if (forwarder_block_p (bb
))
105 BB_SET_FLAG (bb
, BB_FORWARDER_BLOCK
);
107 BB_CLEAR_FLAG (bb
, BB_FORWARDER_BLOCK
);
110 /* Simplify a conditional jump around an unconditional jump.
111 Return true if something changed. */
114 try_simplify_condjump (cbranch_block
)
115 basic_block cbranch_block
;
117 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
118 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
121 /* Verify that there are exactly two successors. */
122 if (!cbranch_block
->succ
123 || !cbranch_block
->succ
->succ_next
124 || cbranch_block
->succ
->succ_next
->succ_next
)
127 /* Verify that we've got a normal conditional branch at the end
129 cbranch_insn
= cbranch_block
->end
;
130 if (!any_condjump_p (cbranch_insn
))
133 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
134 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
136 /* The next block must not have multiple predecessors, must not
137 be the last block in the function, and must contain just the
138 unconditional jump. */
139 jump_block
= cbranch_fallthru_edge
->dest
;
140 if (jump_block
->pred
->pred_next
141 || jump_block
->index
== n_basic_blocks
- 1
142 || !FORWARDER_BLOCK_P (jump_block
))
144 jump_dest_block
= jump_block
->succ
->dest
;
146 /* The conditional branch must target the block after the
147 unconditional branch. */
148 cbranch_dest_block
= cbranch_jump_edge
->dest
;
150 if (!can_fallthru (jump_block
, cbranch_dest_block
))
153 /* Invert the conditional branch. */
154 if (!invert_jump (cbranch_insn
, block_label (jump_dest_block
), 0))
158 fprintf (rtl_dump_file
, "Simplifying condjump %i around jump %i\n",
159 INSN_UID (cbranch_insn
), INSN_UID (jump_block
->end
));
161 /* Success. Update the CFG to match. Note that after this point
162 the edge variable names appear backwards; the redirection is done
163 this way to preserve edge profile data. */
164 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
166 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
168 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
169 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
171 /* Delete the block with the unconditional jump, and clean up the mess. */
172 flow_delete_block (jump_block
);
173 tidy_fallthru_edge (cbranch_jump_edge
, cbranch_block
, cbranch_dest_block
);
178 /* Attempt to forward edges leaving basic block B.
179 Return true if successful. */
182 try_forward_edges (mode
, b
)
186 bool changed
= false;
189 for (e
= b
->succ
; e
; e
= next
)
191 basic_block target
, first
;
196 /* Skip complex edges because we don't know how to update them.
198 Still handle fallthru edges, as we can succeed to forward fallthru
199 edge to the same place as the branch edge of conditional branch
200 and turn conditional branch to an unconditional branch. */
201 if (e
->flags
& EDGE_COMPLEX
)
204 target
= first
= e
->dest
;
207 /* Look for the real destination of the jump.
208 Avoid infinite loop in the infinite empty loop by counting
209 up to n_basic_blocks. */
210 while (FORWARDER_BLOCK_P (target
)
211 && target
->succ
->dest
!= EXIT_BLOCK_PTR
212 && counter
< n_basic_blocks
)
214 /* Bypass trivial infinite loops. */
215 if (target
== target
->succ
->dest
)
216 counter
= n_basic_blocks
;
218 /* Avoid killing of loop pre-headers, as it is the place loop
219 optimizer wants to hoist code to.
221 For fallthru forwarders, the LOOP_BEG note must appear between
222 the header of block and CODE_LABEL of the loop, for non forwarders
223 it must appear before the JUMP_INSN. */
224 if (mode
& CLEANUP_PRE_LOOP
)
226 rtx insn
= (target
->succ
->flags
& EDGE_FALLTHRU
227 ? target
->head
: prev_nonnote_insn (target
->end
));
229 if (GET_CODE (insn
) != NOTE
)
230 insn
= NEXT_INSN (insn
);
232 for (;insn
&& GET_CODE (insn
) != CODE_LABEL
&& !INSN_P (insn
);
233 insn
= NEXT_INSN (insn
))
234 if (GET_CODE (insn
) == NOTE
235 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
238 if (GET_CODE (insn
) == NOTE
)
241 target
= target
->succ
->dest
, counter
++;
244 if (counter
>= n_basic_blocks
)
247 fprintf (rtl_dump_file
, "Infinite loop in BB %i.\n",
250 else if (target
== first
)
251 ; /* We didn't do anything. */
254 /* Save the values now, as the edge may get removed. */
255 gcov_type edge_count
= e
->count
;
256 int edge_probability
= e
->probability
;
258 if (redirect_edge_and_branch (e
, target
))
260 /* We successfully forwarded the edge. Now update profile
261 data: for each edge we traversed in the chain, remove
262 the original edge's execution count. */
263 int edge_frequency
= ((edge_probability
* b
->frequency
264 + REG_BR_PROB_BASE
/ 2)
267 if (!FORWARDER_BLOCK_P (b
) && forwarder_block_p (b
))
268 BB_SET_FLAG (b
, BB_FORWARDER_BLOCK
);
269 BB_SET_FLAG (b
, BB_UPDATE_LIFE
);
273 first
->count
-= edge_count
;
274 first
->succ
->count
-= edge_count
;
275 first
->frequency
-= edge_frequency
;
276 first
= first
->succ
->dest
;
278 while (first
!= target
);
285 fprintf (rtl_dump_file
, "Forwarding edge %i->%i to %i failed.\n",
286 b
->index
, e
->dest
->index
, target
->index
);
294 /* Return true if LABEL is used for tail recursion. */
297 tail_recursion_label_p (label
)
302 for (x
= tail_recursion_label_list
; x
; x
= XEXP (x
, 1))
303 if (label
== XEXP (x
, 0))
309 /* Blocks A and B are to be merged into a single block. A has no incoming
310 fallthru edge, so it can be moved before B without adding or modifying
311 any jumps (aside from the jump from A to B). */
314 merge_blocks_move_predecessor_nojumps (a
, b
)
320 barrier
= next_nonnote_insn (a
->end
);
321 if (GET_CODE (barrier
) != BARRIER
)
323 delete_insn (barrier
);
325 /* Move block and loop notes out of the chain so that we do not
328 ??? A better solution would be to squeeze out all the non-nested notes
329 and adjust the block trees appropriately. Even better would be to have
330 a tighter connection between block trees and rtl so that this is not
332 if (squeeze_notes (&a
->head
, &a
->end
))
335 /* Scramble the insn chain. */
336 if (a
->end
!= PREV_INSN (b
->head
))
337 reorder_insns_nobb (a
->head
, a
->end
, PREV_INSN (b
->head
));
338 BB_SET_FLAG (a
, BB_UPDATE_LIFE
);
342 fprintf (rtl_dump_file
, "Moved block %d before %d and merged.\n",
346 /* Swap the records for the two blocks around. Although we are deleting B,
347 A is now where B was and we want to compact the BB array from where
349 BASIC_BLOCK (a
->index
) = b
;
350 BASIC_BLOCK (b
->index
) = a
;
355 /* Now blocks A and B are contiguous. Merge them. */
356 merge_blocks_nomove (a
, b
);
359 /* Blocks A and B are to be merged into a single block. B has no outgoing
360 fallthru edge, so it can be moved after A without adding or modifying
361 any jumps (aside from the jump from A to B). */
364 merge_blocks_move_successor_nojumps (a
, b
)
367 rtx barrier
, real_b_end
;
370 barrier
= NEXT_INSN (b
->end
);
372 /* Recognize a jump table following block B. */
374 && GET_CODE (barrier
) == CODE_LABEL
375 && NEXT_INSN (barrier
)
376 && GET_CODE (NEXT_INSN (barrier
)) == JUMP_INSN
377 && (GET_CODE (PATTERN (NEXT_INSN (barrier
))) == ADDR_VEC
378 || GET_CODE (PATTERN (NEXT_INSN (barrier
))) == ADDR_DIFF_VEC
))
380 /* Temporarily add the table jump insn to b, so that it will also
381 be moved to the correct location. */
382 b
->end
= NEXT_INSN (barrier
);
383 barrier
= NEXT_INSN (b
->end
);
386 /* There had better have been a barrier there. Delete it. */
387 if (barrier
&& GET_CODE (barrier
) == BARRIER
)
388 delete_insn (barrier
);
390 /* Move block and loop notes out of the chain so that we do not
393 ??? A better solution would be to squeeze out all the non-nested notes
394 and adjust the block trees appropriately. Even better would be to have
395 a tighter connection between block trees and rtl so that this is not
397 if (squeeze_notes (&b
->head
, &b
->end
))
400 /* Scramble the insn chain. */
401 reorder_insns_nobb (b
->head
, b
->end
, a
->end
);
403 /* Restore the real end of b. */
406 /* Now blocks A and B are contiguous. Merge them. */
407 merge_blocks_nomove (a
, b
);
408 BB_SET_FLAG (a
, BB_UPDATE_LIFE
);
412 fprintf (rtl_dump_file
, "Moved block %d after %d and merged.\n",
417 /* Attempt to merge basic blocks that are potentially non-adjacent.
418 Return true iff the attempt succeeded. */
421 merge_blocks (e
, b
, c
, mode
)
426 /* If C has a tail recursion label, do not merge. There is no
427 edge recorded from the call_placeholder back to this label, as
428 that would make optimize_sibling_and_tail_recursive_calls more
429 complex for no gain. */
430 if ((mode
& CLEANUP_PRE_SIBCALL
)
431 && GET_CODE (c
->head
) == CODE_LABEL
432 && tail_recursion_label_p (c
->head
))
435 /* If B has a fallthru edge to C, no need to move anything. */
436 if (e
->flags
& EDGE_FALLTHRU
)
438 /* We need to update liveness in case C already has broken liveness
439 or B ends by conditional jump to next instructions that will be
441 if ((BB_FLAGS (c
) & BB_UPDATE_LIFE
)
442 || GET_CODE (b
->end
) == JUMP_INSN
)
443 BB_SET_FLAG (b
, BB_UPDATE_LIFE
);
444 merge_blocks_nomove (b
, c
);
445 update_forwarder_flag (b
);
449 fprintf (rtl_dump_file
, "Merged %d and %d without moving.\n",
455 /* Otherwise we will need to move code around. Do that only if expensive
456 transformations are allowed. */
457 else if (mode
& CLEANUP_EXPENSIVE
)
459 edge tmp_edge
, b_fallthru_edge
;
460 bool c_has_outgoing_fallthru
;
461 bool b_has_incoming_fallthru
;
463 /* Avoid overactive code motion, as the forwarder blocks should be
464 eliminated by edge redirection instead. One exception might have
465 been if B is a forwarder block and C has no fallthru edge, but
466 that should be cleaned up by bb-reorder instead. */
467 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
470 /* We must make sure to not munge nesting of lexical blocks,
471 and loop notes. This is done by squeezing out all the notes
472 and leaving them there to lie. Not ideal, but functional. */
474 for (tmp_edge
= c
->succ
; tmp_edge
; tmp_edge
= tmp_edge
->succ_next
)
475 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
477 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
479 for (tmp_edge
= b
->pred
; tmp_edge
; tmp_edge
= tmp_edge
->pred_next
)
480 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
482 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
483 b_fallthru_edge
= tmp_edge
;
485 /* Otherwise, we're going to try to move C after B. If C does
486 not have an outgoing fallthru, then it can be moved
487 immediately after B without introducing or modifying jumps. */
488 if (! c_has_outgoing_fallthru
)
490 merge_blocks_move_successor_nojumps (b
, c
);
494 /* If B does not have an incoming fallthru, then it can be moved
495 immediately before C without introducing or modifying jumps.
496 C cannot be the first block, so we do not have to worry about
497 accessing a non-existent block. */
499 if (b_has_incoming_fallthru
)
502 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
504 bb
= force_nonfallthru (b_fallthru_edge
);
506 notice_new_block (bb
);
508 BB_SET_FLAG (b_fallthru_edge
->src
, BB_UPDATE_LIFE
);
510 merge_blocks_move_predecessor_nojumps (b
, c
);
516 /* Look through the insns at the end of BB1 and BB2 and find the longest
517 sequence that are equivalent. Store the first insns for that sequence
518 in *F1 and *F2 and return the sequence length.
520 To simplify callers of this function, if the blocks match exactly,
521 store the head of the blocks in *F1 and *F2. */
524 flow_find_cross_jump (mode
, bb1
, bb2
, f1
, f2
)
525 int mode ATTRIBUTE_UNUSED
;
526 basic_block bb1
, bb2
;
529 rtx i1
, i2
, p1
, p2
, last1
, last2
, afterlast1
, afterlast2
;
532 /* Skip simple jumps at the end of the blocks. Complex jumps still
533 need to be compared for equivalence, which we'll do below. */
537 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
541 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
544 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
548 while ((GET_CODE (i1
) == NOTE
&& i1
!= bb1
->head
))
550 while ((GET_CODE (i2
) == NOTE
&& i2
!= bb2
->head
))
553 if (i1
== bb1
->head
|| i2
== bb2
->head
)
556 /* Verify that I1 and I2 are equivalent. */
558 if (GET_CODE (i1
) != GET_CODE (i2
))
564 /* If this is a CALL_INSN, compare register usage information.
565 If we don't check this on stack register machines, the two
566 CALL_INSNs might be merged leaving reg-stack.c with mismatching
567 numbers of stack registers in the same basic block.
568 If we don't check this on machines with delay slots, a delay slot may
569 be filled that clobbers a parameter expected by the subroutine.
571 ??? We take the simple route for now and assume that if they're
572 equal, they were constructed identically. */
574 if (GET_CODE (i1
) == CALL_INSN
575 && ! rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
576 CALL_INSN_FUNCTION_USAGE (i2
)))
580 /* If cross_jump_death_matters is not 0, the insn's mode
581 indicates whether or not the insn contains any stack-like
584 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
586 /* If register stack conversion has already been done, then
587 death notes must also be compared before it is certain that
588 the two instruction streams match. */
591 HARD_REG_SET i1_regset
, i2_regset
;
593 CLEAR_HARD_REG_SET (i1_regset
);
594 CLEAR_HARD_REG_SET (i2_regset
);
596 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
597 if (REG_NOTE_KIND (note
) == REG_DEAD
598 && STACK_REG_P (XEXP (note
, 0)))
599 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
601 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
602 if (REG_NOTE_KIND (note
) == REG_DEAD
603 && STACK_REG_P (XEXP (note
, 0)))
604 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
606 GO_IF_HARD_REG_EQUAL (i1_regset
, i2_regset
, done
);
615 if (GET_CODE (p1
) != GET_CODE (p2
))
618 if (! rtx_renumbered_equal_p (p1
, p2
))
620 /* The following code helps take care of G++ cleanups. */
621 rtx equiv1
= find_reg_equal_equiv_note (i1
);
622 rtx equiv2
= find_reg_equal_equiv_note (i2
);
625 /* If the equivalences are not to a constant, they may
626 reference pseudos that no longer exist, so we can't
628 && CONSTANT_P (XEXP (equiv1
, 0))
629 && rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
631 rtx s1
= single_set (i1
);
632 rtx s2
= single_set (i2
);
633 if (s1
!= 0 && s2
!= 0
634 && rtx_renumbered_equal_p (SET_DEST (s1
), SET_DEST (s2
)))
636 validate_change (i1
, &SET_SRC (s1
), XEXP (equiv1
, 0), 1);
637 validate_change (i2
, &SET_SRC (s2
), XEXP (equiv2
, 0), 1);
638 if (! rtx_renumbered_equal_p (p1
, p2
))
640 else if (apply_change_group ())
648 /* Don't begin a cross-jump with a USE or CLOBBER insn. */
649 if (GET_CODE (p1
) != USE
&& GET_CODE (p1
) != CLOBBER
)
651 /* If the merged insns have different REG_EQUAL notes, then
653 rtx equiv1
= find_reg_equal_equiv_note (i1
);
654 rtx equiv2
= find_reg_equal_equiv_note (i2
);
656 if (equiv1
&& !equiv2
)
657 remove_note (i1
, equiv1
);
658 else if (!equiv1
&& equiv2
)
659 remove_note (i2
, equiv2
);
660 else if (equiv1
&& equiv2
661 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
663 remove_note (i1
, equiv1
);
664 remove_note (i2
, equiv2
);
667 afterlast1
= last1
, afterlast2
= last2
;
668 last1
= i1
, last2
= i2
;
678 /* Don't allow the insn after a compare to be shared by
679 cross-jumping unless the compare is also shared. */
680 if (reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
681 last1
= afterlast1
, last2
= afterlast2
, ninsns
--;
685 /* Include preceding notes and labels in the cross-jump. One,
686 this may bring us to the head of the blocks as requested above.
687 Two, it keeps line number notes as matched as may be. */
690 while (last1
!= bb1
->head
&& GET_CODE (PREV_INSN (last1
)) == NOTE
)
691 last1
= PREV_INSN (last1
);
692 if (last1
!= bb1
->head
&& GET_CODE (PREV_INSN (last1
)) == CODE_LABEL
)
693 last1
= PREV_INSN (last1
);
694 while (last2
!= bb2
->head
&& GET_CODE (PREV_INSN (last2
)) == NOTE
)
695 last2
= PREV_INSN (last2
);
696 if (last2
!= bb2
->head
&& GET_CODE (PREV_INSN (last2
)) == CODE_LABEL
)
697 last2
= PREV_INSN (last2
);
706 /* Return true iff outgoing edges of BB1 and BB2 match, together with
707 the branch instruction. This means that if we commonize the control
708 flow before end of the basic block, the semantic remains unchanged.
710 We may assume that there exists one edge with a common destination. */
713 outgoing_edges_match (bb1
, bb2
)
717 /* If BB1 has only one successor, we must be looking at an unconditional
718 jump. Which, by the assumption above, means that we only need to check
719 that BB2 has one successor. */
720 if (bb1
->succ
&& !bb1
->succ
->succ_next
)
721 return (bb2
->succ
&& !bb2
->succ
->succ_next
);
723 /* Match conditional jumps - this may get tricky when fallthru and branch
724 edges are crossed. */
726 && bb1
->succ
->succ_next
727 && !bb1
->succ
->succ_next
->succ_next
728 && any_condjump_p (bb1
->end
))
732 rtx set1
, set2
, cond1
, cond2
;
733 enum rtx_code code1
, code2
;
736 || !bb2
->succ
->succ_next
737 || bb1
->succ
->succ_next
->succ_next
738 || !any_condjump_p (bb2
->end
))
741 b1
= BRANCH_EDGE (bb1
);
742 b2
= BRANCH_EDGE (bb2
);
743 f1
= FALLTHRU_EDGE (bb1
);
744 f2
= FALLTHRU_EDGE (bb2
);
746 /* Get around possible forwarders on fallthru edges. Other cases
747 should be optimized out already. */
748 if (FORWARDER_BLOCK_P (f1
->dest
))
750 if (FORWARDER_BLOCK_P (f2
->dest
))
753 /* To simplify use of this function, return false if there are
754 unneeded forwarder blocks. These will get eliminated later
755 during cleanup_cfg. */
756 if (FORWARDER_BLOCK_P (f1
->dest
)
757 || FORWARDER_BLOCK_P (f2
->dest
)
758 || FORWARDER_BLOCK_P (b1
->dest
)
759 || FORWARDER_BLOCK_P (b2
->dest
))
762 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
764 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
769 set1
= pc_set (bb1
->end
);
770 set2
= pc_set (bb2
->end
);
771 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
772 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
775 cond1
= XEXP (SET_SRC (set1
), 0);
776 cond2
= XEXP (SET_SRC (set2
), 0);
777 code1
= GET_CODE (cond1
);
779 code2
= reversed_comparison_code (cond2
, bb2
->end
);
781 code2
= GET_CODE (cond2
);
782 if (code2
== UNKNOWN
)
785 /* Verify codes and operands match. */
786 match
= ((code1
== code2
787 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
788 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
789 || (code1
== swap_condition (code2
)
790 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
792 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
795 /* If we return true, we will join the blocks. Which means that
796 we will only have one branch prediction bit to work with. Thus
797 we require the existing branches to have probabilities that are
799 /* ??? We should use bb->frequency to allow merging in infrequently
800 executed blocks, but at the moment it is not available when
801 cleanup_cfg is run. */
802 if (match
&& !optimize_size
)
806 note1
= find_reg_note (bb1
->end
, REG_BR_PROB
, 0);
807 note2
= find_reg_note (bb2
->end
, REG_BR_PROB
, 0);
811 prob1
= INTVAL (XEXP (note1
, 0));
812 prob2
= INTVAL (XEXP (note2
, 0));
814 prob2
= REG_BR_PROB_BASE
- prob2
;
816 /* Fail if the difference in probabilities is
818 if (abs (prob1
- prob2
) > REG_BR_PROB_BASE
/ 20)
821 else if (note1
|| note2
)
825 if (rtl_dump_file
&& match
)
826 fprintf (rtl_dump_file
, "Conditionals in bb %i and %i match.\n",
827 bb1
->index
, bb2
->index
);
832 /* ??? We can handle computed jumps too. This may be important for
833 inlined functions containing switch statements. Also jumps w/o
834 fallthru edges can be handled by simply matching whole insn. */
838 /* E1 and E2 are edges with the same destination block. Search their
839 predecessors for common code. If found, redirect control flow from
840 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
843 try_crossjump_to_edge (mode
, e1
, e2
)
848 basic_block src1
= e1
->src
, src2
= e2
->src
;
849 basic_block redirect_to
;
850 rtx newpos1
, newpos2
;
856 /* Search backward through forwarder blocks. We don't need to worry
857 about multiple entry or chained forwarders, as they will be optimized
858 away. We do this to look past the unconditional jump following a
859 conditional jump that is required due to the current CFG shape. */
861 && !src1
->pred
->pred_next
862 && FORWARDER_BLOCK_P (src1
))
868 && !src2
->pred
->pred_next
869 && FORWARDER_BLOCK_P (src2
))
875 /* Nothing to do if we reach ENTRY, or a common source block. */
876 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
881 /* Seeing more than 1 forwarder blocks would confuse us later... */
882 if (FORWARDER_BLOCK_P (e1
->dest
)
883 && FORWARDER_BLOCK_P (e1
->dest
->succ
->dest
))
885 if (FORWARDER_BLOCK_P (e2
->dest
)
886 && FORWARDER_BLOCK_P (e2
->dest
->succ
->dest
))
889 /* Likewise with dead code (possibly newly created by the other optimizations
891 if (!src1
->pred
|| !src2
->pred
)
894 /* Likewise with complex edges.
895 ??? We should be able to handle most complex edges later with some
897 if (e1
->flags
& EDGE_COMPLEX
)
900 /* Look for the common insn sequence, part the first ... */
901 if (!outgoing_edges_match (src1
, src2
))
904 /* ... and part the second. */
905 nmatch
= flow_find_cross_jump (mode
, src1
, src2
, &newpos1
, &newpos2
);
909 /* Avoid splitting if possible. */
910 if (newpos2
== src2
->head
)
915 fprintf (rtl_dump_file
, "Splitting bb %i before %i insns\n",
916 src2
->index
, nmatch
);
917 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
921 fprintf (rtl_dump_file
,
922 "Cross jumping from bb %i to bb %i; %i common insns\n",
923 src1
->index
, src2
->index
, nmatch
);
925 redirect_to
->count
+= src1
->count
;
926 redirect_to
->frequency
+= src1
->frequency
;
928 /* Recompute the frequencies and counts of outgoing edges. */
929 for (s
= redirect_to
->succ
; s
; s
= s
->succ_next
)
932 basic_block d
= s
->dest
;
934 if (FORWARDER_BLOCK_P (d
))
936 for (s2
= src1
->succ
; ; s2
= s2
->succ_next
)
938 basic_block d2
= s2
->dest
;
939 if (FORWARDER_BLOCK_P (d2
))
944 s
->count
+= s2
->count
;
946 /* Take care to update possible forwarder blocks. We verified
947 that there is no more than one in the chain, so we can't run
948 into infinite loop. */
949 if (FORWARDER_BLOCK_P (s
->dest
))
951 s
->dest
->succ
->count
+= s2
->count
;
952 s
->dest
->count
+= s2
->count
;
953 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
955 if (FORWARDER_BLOCK_P (s2
->dest
))
957 s2
->dest
->succ
->count
-= s2
->count
;
958 s2
->dest
->count
-= s2
->count
;
959 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
961 if (!redirect_to
->frequency
&& !src1
->frequency
)
962 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
965 ((s
->probability
* redirect_to
->frequency
+
966 s2
->probability
* src1
->frequency
)
967 / (redirect_to
->frequency
+ src1
->frequency
));
970 note
= find_reg_note (redirect_to
->end
, REG_BR_PROB
, 0);
972 XEXP (note
, 0) = GEN_INT (BRANCH_EDGE (redirect_to
)->probability
);
974 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
976 /* Skip possible basic block header. */
977 if (GET_CODE (newpos1
) == CODE_LABEL
)
978 newpos1
= NEXT_INSN (newpos1
);
979 if (GET_CODE (newpos1
) == NOTE
)
980 newpos1
= NEXT_INSN (newpos1
);
983 /* Emit the jump insn. */
984 label
= block_label (redirect_to
);
985 emit_jump_insn_after (gen_jump (label
), src1
->end
);
986 JUMP_LABEL (src1
->end
) = label
;
987 LABEL_NUSES (label
)++;
989 /* Delete the now unreachable instructions. */
990 delete_insn_chain (newpos1
, last
);
992 /* Make sure there is a barrier after the new jump. */
993 last
= next_nonnote_insn (src1
->end
);
994 if (!last
|| GET_CODE (last
) != BARRIER
)
995 emit_barrier_after (src1
->end
);
999 remove_edge (src1
->succ
);
1000 make_single_succ_edge (src1
, redirect_to
, 0);
1002 BB_SET_FLAG (src1
, BB_UPDATE_LIFE
);
1003 update_forwarder_flag (src1
);
1008 /* Search the predecessors of BB for common insn sequences. When found,
1009 share code between them by redirecting control flow. Return true if
1010 any changes made. */
1013 try_crossjump_bb (mode
, bb
)
1017 edge e
, e2
, nexte2
, nexte
, fallthru
;
1020 /* Nothing to do if there is not at least two incoming edges. */
1021 if (!bb
->pred
|| !bb
->pred
->pred_next
)
1024 /* It is always cheapest to redirect a block that ends in a branch to
1025 a block that falls through into BB, as that adds no branches to the
1026 program. We'll try that combination first. */
1027 for (fallthru
= bb
->pred
; fallthru
; fallthru
= fallthru
->pred_next
)
1028 if (fallthru
->flags
& EDGE_FALLTHRU
)
1032 for (e
= bb
->pred
; e
; e
= nexte
)
1034 nexte
= e
->pred_next
;
1036 /* Elide complex edges now, as neither try_crossjump_to_edge
1037 nor outgoing_edges_match can handle them. */
1038 if (e
->flags
& EDGE_COMPLEX
)
1041 /* As noted above, first try with the fallthru predecessor. */
1044 /* Don't combine the fallthru edge into anything else.
1045 If there is a match, we'll do it the other way around. */
1049 if (try_crossjump_to_edge (mode
, e
, fallthru
))
1057 /* Non-obvious work limiting check: Recognize that we're going
1058 to call try_crossjump_bb on every basic block. So if we have
1059 two blocks with lots of outgoing edges (a switch) and they
1060 share lots of common destinations, then we would do the
1061 cross-jump check once for each common destination.
1063 Now, if the blocks actually are cross-jump candidates, then
1064 all of their destinations will be shared. Which means that
1065 we only need check them for cross-jump candidacy once. We
1066 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1067 choosing to do the check from the block for which the edge
1068 in question is the first successor of A. */
1069 if (e
->src
->succ
!= e
)
1072 for (e2
= bb
->pred
; e2
; e2
= nexte2
)
1074 nexte2
= e2
->pred_next
;
1079 /* We've already checked the fallthru edge above. */
1083 /* Again, neither try_crossjump_to_edge nor outgoing_edges_match
1084 can handle complex edges. */
1085 if (e2
->flags
& EDGE_COMPLEX
)
1088 /* The "first successor" check above only prevents multiple
1089 checks of crossjump(A,B). In order to prevent redundant
1090 checks of crossjump(B,A), require that A be the block
1091 with the lowest index. */
1092 if (e
->src
->index
> e2
->src
->index
)
1095 if (try_crossjump_to_edge (mode
, e
, e2
))
1107 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1108 instructions etc. Return nonzero if changes were made. */
1111 try_optimize_cfg (mode
)
1115 bool changed_overall
= false;
1120 if (mode
& CLEANUP_CROSSJUMP
)
1121 add_noreturn_fake_exit_edges ();
1123 for (i
= 0; i
< n_basic_blocks
; i
++)
1124 update_forwarder_flag (BASIC_BLOCK (i
));
1126 /* Attempt to merge blocks as made possible by edge removal. If a block
1127 has only one successor, and the successor has only one predecessor,
1128 they may be combined. */
1136 fprintf (rtl_dump_file
, "\n\ntry_optimize_cfg iteration %i\n\n",
1139 for (i
= 0; i
< n_basic_blocks
;)
1141 basic_block c
, b
= BASIC_BLOCK (i
);
1143 bool changed_here
= false;
1145 /* Delete trivially dead basic blocks. */
1146 while (b
->pred
== NULL
)
1148 c
= BASIC_BLOCK (b
->index
- 1);
1150 fprintf (rtl_dump_file
, "Deleting block %i.\n", b
->index
);
1151 flow_delete_block (b
);
1156 /* Remove code labels no longer used. Don't do this before
1157 CALL_PLACEHOLDER is removed, as some branches may be hidden
1159 if (b
->pred
->pred_next
== NULL
1160 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1161 && !(b
->pred
->flags
& EDGE_COMPLEX
)
1162 && GET_CODE (b
->head
) == CODE_LABEL
1163 && (!(mode
& CLEANUP_PRE_SIBCALL
)
1164 || !tail_recursion_label_p (b
->head
))
1165 /* If previous block ends with condjump jumping to next BB,
1166 we can't delete the label. */
1167 && (b
->pred
->src
== ENTRY_BLOCK_PTR
1168 || !reg_mentioned_p (b
->head
, b
->pred
->src
->end
)))
1170 rtx label
= b
->head
;
1171 b
->head
= NEXT_INSN (b
->head
);
1172 delete_insn_chain (label
, label
);
1174 fprintf (rtl_dump_file
, "Deleted label in block %i.\n",
1178 /* If we fall through an empty block, we can remove it. */
1179 if (b
->pred
->pred_next
== NULL
1180 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1181 && GET_CODE (b
->head
) != CODE_LABEL
1182 && FORWARDER_BLOCK_P (b
)
1183 /* Note that forwarder_block_p true ensures that there
1184 is a successor for this block. */
1185 && (b
->succ
->flags
& EDGE_FALLTHRU
)
1186 && n_basic_blocks
> 1)
1189 fprintf (rtl_dump_file
, "Deleting fallthru block %i.\n",
1191 c
= BASIC_BLOCK (b
->index
? b
->index
- 1 : 1);
1192 redirect_edge_succ_nodup (b
->pred
, b
->succ
->dest
);
1193 flow_delete_block (b
);
1198 /* Merge blocks. Loop because chains of blocks might be
1200 while ((s
= b
->succ
) != NULL
1201 && s
->succ_next
== NULL
1202 && !(s
->flags
& EDGE_COMPLEX
)
1203 && (c
= s
->dest
) != EXIT_BLOCK_PTR
1204 && c
->pred
->pred_next
== NULL
1205 /* If the jump insn has side effects,
1206 we can't kill the edge. */
1207 && (GET_CODE (b
->end
) != JUMP_INSN
1208 || onlyjump_p (b
->end
))
1209 && merge_blocks (s
, b
, c
, mode
))
1210 changed_here
= true;
1212 /* Simplify branch over branch. */
1213 if ((mode
& CLEANUP_EXPENSIVE
) && try_simplify_condjump (b
))
1215 BB_SET_FLAG (b
, BB_UPDATE_LIFE
);
1216 changed_here
= true;
1219 /* If B has a single outgoing edge, but uses a non-trivial jump
1220 instruction without side-effects, we can either delete the
1221 jump entirely, or replace it with a simple unconditional jump.
1222 Use redirect_edge_and_branch to do the dirty work. */
1224 && ! b
->succ
->succ_next
1225 && b
->succ
->dest
!= EXIT_BLOCK_PTR
1226 && onlyjump_p (b
->end
)
1227 && redirect_edge_and_branch (b
->succ
, b
->succ
->dest
))
1229 BB_SET_FLAG (b
, BB_UPDATE_LIFE
);
1230 update_forwarder_flag (b
);
1231 changed_here
= true;
1234 /* Simplify branch to branch. */
1235 if (try_forward_edges (mode
, b
))
1236 changed_here
= true;
1238 /* Look for shared code between blocks. */
1239 if ((mode
& CLEANUP_CROSSJUMP
)
1240 && try_crossjump_bb (mode
, b
))
1241 changed_here
= true;
1243 /* Don't get confused by the index shift caused by deleting
1251 if ((mode
& CLEANUP_CROSSJUMP
)
1252 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
1255 #ifdef ENABLE_CHECKING
1257 verify_flow_info ();
1260 changed_overall
|= changed
;
1264 if (mode
& CLEANUP_CROSSJUMP
)
1265 remove_fake_edges ();
1267 if ((mode
& CLEANUP_UPDATE_LIFE
) && changed_overall
)
1270 blocks
= sbitmap_alloc (n_basic_blocks
);
1271 sbitmap_zero (blocks
);
1272 for (i
= 0; i
< n_basic_blocks
; i
++)
1273 if (BB_FLAGS (BASIC_BLOCK (i
)) & BB_UPDATE_LIFE
)
1276 SET_BIT (blocks
, i
);
1279 update_life_info (blocks
, UPDATE_LIFE_GLOBAL
,
1280 PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
1281 | PROP_KILL_DEAD_CODE
);
1282 sbitmap_free (blocks
);
1284 for (i
= 0; i
< n_basic_blocks
; i
++)
1285 BASIC_BLOCK (i
)->aux
= NULL
;
1287 return changed_overall
;
1290 /* Delete all unreachable basic blocks. */
1293 delete_unreachable_blocks ()
1296 bool changed
= false;
1298 find_unreachable_blocks ();
1300 /* Delete all unreachable basic blocks. Count down so that we
1301 don't interfere with the block renumbering that happens in
1302 flow_delete_block. */
1304 for (i
= n_basic_blocks
- 1; i
>= 0; --i
)
1306 basic_block b
= BASIC_BLOCK (i
);
1308 if (!(b
->flags
& BB_REACHABLE
))
1309 flow_delete_block (b
), changed
= true;
1313 tidy_fallthru_edges ();
1317 /* Tidy the CFG by deleting unreachable code and whatnot. */
1323 bool changed
= false;
1325 timevar_push (TV_CLEANUP_CFG
);
1326 changed
= delete_unreachable_blocks ();
1327 if (try_optimize_cfg (mode
))
1328 delete_unreachable_blocks (), changed
= true;
1330 /* Kill the data we won't maintain. */
1331 free_EXPR_LIST_list (&label_value_list
);
1332 free_EXPR_LIST_list (&tail_recursion_label_list
);
1333 timevar_pop (TV_CLEANUP_CFG
);