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. Prevent jump.c from deleting
110 "unreachable" instructions. */
111 LABEL_NUSES (JUMP_LABEL (cbranch_insn
))++;
112 if (!invert_jump (cbranch_insn
, block_label (jump_dest_block
), 1))
114 LABEL_NUSES (JUMP_LABEL (cbranch_insn
))--;
119 fprintf (rtl_dump_file
, "Simplifying condjump %i around jump %i\n",
120 INSN_UID (cbranch_insn
), INSN_UID (jump_block
->end
));
122 /* Success. Update the CFG to match. Note that after this point
123 the edge variable names appear backwards; the redirection is done
124 this way to preserve edge profile data. */
125 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
127 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
129 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
130 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
132 /* Delete the block with the unconditional jump, and clean up the mess. */
133 flow_delete_block (jump_block
);
134 tidy_fallthru_edge (cbranch_jump_edge
, cbranch_block
, cbranch_dest_block
);
139 /* Attempt to forward edges leaving basic block B.
140 Return true if sucessful. */
143 try_forward_edges (mode
, b
)
147 bool changed
= false;
150 for (e
= b
->succ
; e
; e
= next
)
152 basic_block target
, first
;
157 /* Skip complex edges because we don't know how to update them.
159 Still handle fallthru edges, as we can suceed to forward fallthru
160 edge to the same place as the branch edge of conditional branch
161 and turn conditional branch to an unconditonal branch. */
162 if (e
->flags
& EDGE_COMPLEX
)
165 target
= first
= e
->dest
;
168 /* Look for the real destination of the jump.
169 Avoid inifinite loop in the infinite empty loop by counting
170 up to n_basic_blocks. */
171 while (forwarder_block_p (target
)
172 && target
->succ
->dest
!= EXIT_BLOCK_PTR
173 && counter
< n_basic_blocks
)
175 /* Bypass trivial infinite loops. */
176 if (target
== target
->succ
->dest
)
177 counter
= n_basic_blocks
;
179 /* Avoid killing of loop pre-headers, as it is the place loop
180 optimizer wants to hoist code to.
182 For fallthru forwarders, the LOOP_BEG note must appear between
183 the header of block and CODE_LABEL of the loop, for non forwarders
184 it must appear before the JUMP_INSN. */
185 if (mode
& CLEANUP_PRE_LOOP
)
187 rtx insn
= (target
->succ
->flags
& EDGE_FALLTHRU
188 ? target
->head
: prev_nonnote_insn (target
->end
));
190 if (GET_CODE (insn
) != NOTE
)
191 insn
= NEXT_INSN (insn
);
193 for (;insn
&& GET_CODE (insn
) != CODE_LABEL
&& !INSN_P (insn
);
194 insn
= NEXT_INSN (insn
))
195 if (GET_CODE (insn
) == NOTE
196 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
199 if (GET_CODE (insn
) == NOTE
)
202 target
= target
->succ
->dest
, counter
++;
205 if (counter
>= n_basic_blocks
)
208 fprintf (rtl_dump_file
, "Infinite loop in BB %i.\n",
211 else if (target
== first
)
212 ; /* We didn't do anything. */
215 /* Save the values now, as the edge may get removed. */
216 gcov_type edge_count
= e
->count
;
217 int edge_probability
= e
->probability
;
219 if (redirect_edge_and_branch (e
, target
))
221 /* We successfully forwarded the edge. Now update profile
222 data: for each edge we traversed in the chain, remove
223 the original edge's execution count. */
224 int edge_frequency
= ((edge_probability
* b
->frequency
225 + REG_BR_PROB_BASE
/ 2)
230 first
->count
-= edge_count
;
231 first
->succ
->count
-= edge_count
;
232 first
->frequency
-= edge_frequency
;
233 first
= first
->succ
->dest
;
235 while (first
!= target
);
242 fprintf (rtl_dump_file
, "Forwarding edge %i->%i to %i failed.\n",
243 b
->index
, e
->dest
->index
, target
->index
);
251 /* Return true if LABEL is used for tail recursion. */
254 tail_recursion_label_p (label
)
259 for (x
= tail_recursion_label_list
; x
; x
= XEXP (x
, 1))
260 if (label
== XEXP (x
, 0))
266 /* Blocks A and B are to be merged into a single block. A has no incoming
267 fallthru edge, so it can be moved before B without adding or modifying
268 any jumps (aside from the jump from A to B). */
271 merge_blocks_move_predecessor_nojumps (a
, b
)
277 barrier
= next_nonnote_insn (a
->end
);
278 if (GET_CODE (barrier
) != BARRIER
)
280 flow_delete_insn (barrier
);
282 /* Move block and loop notes out of the chain so that we do not
285 ??? A better solution would be to squeeze out all the non-nested notes
286 and adjust the block trees appropriately. Even better would be to have
287 a tighter connection between block trees and rtl so that this is not
289 squeeze_notes (&a
->head
, &a
->end
);
291 /* Scramble the insn chain. */
292 if (a
->end
!= PREV_INSN (b
->head
))
293 reorder_insns (a
->head
, a
->end
, PREV_INSN (b
->head
));
297 fprintf (rtl_dump_file
, "Moved block %d before %d and merged.\n",
301 /* Swap the records for the two blocks around. Although we are deleting B,
302 A is now where B was and we want to compact the BB array from where
304 BASIC_BLOCK (a
->index
) = b
;
305 BASIC_BLOCK (b
->index
) = a
;
310 /* Now blocks A and B are contiguous. Merge them. */
311 merge_blocks_nomove (a
, b
);
314 /* Blocks A and B are to be merged into a single block. B has no outgoing
315 fallthru edge, so it can be moved after A without adding or modifying
316 any jumps (aside from the jump from A to B). */
319 merge_blocks_move_successor_nojumps (a
, b
)
324 barrier
= NEXT_INSN (b
->end
);
326 /* Recognize a jump table following block B. */
328 && GET_CODE (barrier
) == CODE_LABEL
329 && NEXT_INSN (barrier
)
330 && GET_CODE (NEXT_INSN (barrier
)) == JUMP_INSN
331 && (GET_CODE (PATTERN (NEXT_INSN (barrier
))) == ADDR_VEC
332 || GET_CODE (PATTERN (NEXT_INSN (barrier
))) == ADDR_DIFF_VEC
))
334 b
->end
= NEXT_INSN (barrier
);
335 barrier
= NEXT_INSN (b
->end
);
338 /* There had better have been a barrier there. Delete it. */
339 if (barrier
&& GET_CODE (barrier
) == BARRIER
)
340 flow_delete_insn (barrier
);
342 /* Move block and loop notes out of the chain so that we do not
345 ??? A better solution would be to squeeze out all the non-nested notes
346 and adjust the block trees appropriately. Even better would be to have
347 a tighter connection between block trees and rtl so that this is not
349 squeeze_notes (&b
->head
, &b
->end
);
351 /* Scramble the insn chain. */
352 reorder_insns (b
->head
, b
->end
, a
->end
);
354 /* Now blocks A and B are contiguous. Merge them. */
355 merge_blocks_nomove (a
, b
);
359 fprintf (rtl_dump_file
, "Moved block %d after %d and merged.\n",
364 /* Attempt to merge basic blocks that are potentially non-adjacent.
365 Return true iff the attempt succeeded. */
368 merge_blocks (e
, b
, c
, mode
)
373 /* If C has a tail recursion label, do not merge. There is no
374 edge recorded from the call_placeholder back to this label, as
375 that would make optimize_sibling_and_tail_recursive_calls more
376 complex for no gain. */
377 if ((mode
& CLEANUP_PRE_SIBCALL
)
378 && GET_CODE (c
->head
) == CODE_LABEL
379 && tail_recursion_label_p (c
->head
))
382 /* If B has a fallthru edge to C, no need to move anything. */
383 if (e
->flags
& EDGE_FALLTHRU
)
385 merge_blocks_nomove (b
, c
);
389 fprintf (rtl_dump_file
, "Merged %d and %d without moving.\n",
395 /* Otherwise we will need to move code around. Do that only if expensive
396 transformations are allowed. */
397 else if (mode
& CLEANUP_EXPENSIVE
)
399 edge tmp_edge
, b_fallthru_edge
;
400 bool c_has_outgoing_fallthru
;
401 bool b_has_incoming_fallthru
;
403 /* Avoid overactive code motion, as the forwarder blocks should be
404 eliminated by edge redirection instead. One exception might have
405 been if B is a forwarder block and C has no fallthru edge, but
406 that should be cleaned up by bb-reorder instead. */
407 if (forwarder_block_p (b
) || forwarder_block_p (c
))
410 /* We must make sure to not munge nesting of lexical blocks,
411 and loop notes. This is done by squeezing out all the notes
412 and leaving them there to lie. Not ideal, but functional. */
414 for (tmp_edge
= c
->succ
; tmp_edge
; tmp_edge
= tmp_edge
->succ_next
)
415 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
417 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
419 for (tmp_edge
= b
->pred
; tmp_edge
; tmp_edge
= tmp_edge
->pred_next
)
420 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
422 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
423 b_fallthru_edge
= tmp_edge
;
425 /* Otherwise, we're going to try to move C after B. If C does
426 not have an outgoing fallthru, then it can be moved
427 immediately after B without introducing or modifying jumps. */
428 if (! c_has_outgoing_fallthru
)
430 merge_blocks_move_successor_nojumps (b
, c
);
434 /* If B does not have an incoming fallthru, then it can be moved
435 immediately before C without introducing or modifying jumps.
436 C cannot be the first block, so we do not have to worry about
437 accessing a non-existent block. */
439 if (b_has_incoming_fallthru
)
441 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
443 force_nonfallthru (b_fallthru_edge
);
445 merge_blocks_move_predecessor_nojumps (b
, c
);
451 /* Look through the insns at the end of BB1 and BB2 and find the longest
452 sequence that are equivalent. Store the first insns for that sequence
453 in *F1 and *F2 and return the sequence length.
455 To simplify callers of this function, if the blocks match exactly,
456 store the head of the blocks in *F1 and *F2. */
459 flow_find_cross_jump (mode
, bb1
, bb2
, f1
, f2
)
460 int mode ATTRIBUTE_UNUSED
;
461 basic_block bb1
, bb2
;
464 rtx i1
, i2
, p1
, p2
, last1
, last2
, afterlast1
, afterlast2
;
467 /* Skip simple jumps at the end of the blocks. Complex jumps still
468 need to be compared for equivalence, which we'll do below. */
472 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
476 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
479 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
483 while ((GET_CODE (i1
) == NOTE
&& i1
!= bb1
->head
))
485 while ((GET_CODE (i2
) == NOTE
&& i2
!= bb2
->head
))
488 if (i1
== bb1
->head
|| i2
== bb2
->head
)
491 /* Verify that I1 and I2 are equivalent. */
493 if (GET_CODE (i1
) != GET_CODE (i2
))
499 /* If this is a CALL_INSN, compare register usage information.
500 If we don't check this on stack register machines, the two
501 CALL_INSNs might be merged leaving reg-stack.c with mismatching
502 numbers of stack registers in the same basic block.
503 If we don't check this on machines with delay slots, a delay slot may
504 be filled that clobbers a parameter expected by the subroutine.
506 ??? We take the simple route for now and assume that if they're
507 equal, they were constructed identically. */
509 if (GET_CODE (i1
) == CALL_INSN
510 && ! rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
511 CALL_INSN_FUNCTION_USAGE (i2
)))
515 /* If cross_jump_death_matters is not 0, the insn's mode
516 indicates whether or not the insn contains any stack-like
519 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
521 /* If register stack conversion has already been done, then
522 death notes must also be compared before it is certain that
523 the two instruction streams match. */
526 HARD_REG_SET i1_regset
, i2_regset
;
528 CLEAR_HARD_REG_SET (i1_regset
);
529 CLEAR_HARD_REG_SET (i2_regset
);
531 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
532 if (REG_NOTE_KIND (note
) == REG_DEAD
533 && STACK_REG_P (XEXP (note
, 0)))
534 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
536 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
537 if (REG_NOTE_KIND (note
) == REG_DEAD
538 && STACK_REG_P (XEXP (note
, 0)))
539 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
541 GO_IF_HARD_REG_EQUAL (i1_regset
, i2_regset
, done
);
550 if (GET_CODE (p1
) != GET_CODE (p2
))
553 if (! rtx_renumbered_equal_p (p1
, p2
))
555 /* The following code helps take care of G++ cleanups. */
556 rtx equiv1
= find_reg_equal_equiv_note (i1
);
557 rtx equiv2
= find_reg_equal_equiv_note (i2
);
560 /* If the equivalences are not to a constant, they may
561 reference pseudos that no longer exist, so we can't
563 && CONSTANT_P (XEXP (equiv1
, 0))
564 && rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
566 rtx s1
= single_set (i1
);
567 rtx s2
= single_set (i2
);
568 if (s1
!= 0 && s2
!= 0
569 && rtx_renumbered_equal_p (SET_DEST (s1
), SET_DEST (s2
)))
571 validate_change (i1
, &SET_SRC (s1
), XEXP (equiv1
, 0), 1);
572 validate_change (i2
, &SET_SRC (s2
), XEXP (equiv2
, 0), 1);
573 if (! rtx_renumbered_equal_p (p1
, p2
))
575 else if (apply_change_group ())
583 /* Don't begin a cross-jump with a USE or CLOBBER insn. */
584 if (GET_CODE (p1
) != USE
&& GET_CODE (p1
) != CLOBBER
)
586 afterlast1
= last1
, afterlast2
= last2
;
587 last1
= i1
, last2
= i2
;
597 /* Don't allow the insn after a compare to be shared by
598 cross-jumping unless the compare is also shared. */
599 if (reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
600 last1
= afterlast1
, last2
= afterlast2
, ninsns
--;
604 /* Include preceeding notes and labels in the cross-jump. One,
605 this may bring us to the head of the blocks as requested above.
606 Two, it keeps line number notes as matched as may be. */
609 while (last1
!= bb1
->head
&& GET_CODE (PREV_INSN (last1
)) == NOTE
)
610 last1
= PREV_INSN (last1
);
611 if (last1
!= bb1
->head
&& GET_CODE (PREV_INSN (last1
)) == CODE_LABEL
)
612 last1
= PREV_INSN (last1
);
613 while (last2
!= bb2
->head
&& GET_CODE (PREV_INSN (last2
)) == NOTE
)
614 last2
= PREV_INSN (last2
);
615 if (last2
!= bb2
->head
&& GET_CODE (PREV_INSN (last2
)) == CODE_LABEL
)
616 last2
= PREV_INSN (last2
);
625 /* Return true iff outgoing edges of BB1 and BB2 match, together with
626 the branch instruction. This means that if we commonize the control
627 flow before end of the basic block, the semantic remains unchanged.
629 We may assume that there exists one edge with a common destination. */
632 outgoing_edges_match (bb1
, bb2
)
636 /* If BB1 has only one successor, we must be looking at an unconditional
637 jump. Which, by the assumption above, means that we only need to check
638 that BB2 has one successor. */
639 if (bb1
->succ
&& !bb1
->succ
->succ_next
)
640 return (bb2
->succ
&& !bb2
->succ
->succ_next
);
642 /* Match conditional jumps - this may get tricky when fallthru and branch
643 edges are crossed. */
645 && bb1
->succ
->succ_next
646 && !bb1
->succ
->succ_next
->succ_next
647 && any_condjump_p (bb1
->end
))
651 rtx set1
, set2
, cond1
, cond2
;
652 enum rtx_code code1
, code2
;
655 || !bb2
->succ
->succ_next
656 || bb1
->succ
->succ_next
->succ_next
657 || !any_condjump_p (bb2
->end
))
660 b1
= BRANCH_EDGE (bb1
);
661 b2
= BRANCH_EDGE (bb2
);
662 f1
= FALLTHRU_EDGE (bb1
);
663 f2
= FALLTHRU_EDGE (bb2
);
665 /* Get around possible forwarders on fallthru edges. Other cases
666 should be optimized out already. */
667 if (forwarder_block_p (f1
->dest
))
669 if (forwarder_block_p (f2
->dest
))
672 /* To simplify use of this function, return false if there are
673 unneeded forwarder blocks. These will get eliminated later
674 during cleanup_cfg. */
675 if (forwarder_block_p (f1
->dest
)
676 || forwarder_block_p (f2
->dest
)
677 || forwarder_block_p (b1
->dest
)
678 || forwarder_block_p (b2
->dest
))
681 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
683 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
688 set1
= pc_set (bb1
->end
);
689 set2
= pc_set (bb2
->end
);
690 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
691 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
694 cond1
= XEXP (SET_SRC (set1
), 0);
695 cond2
= XEXP (SET_SRC (set2
), 0);
696 code1
= GET_CODE (cond1
);
698 code2
= reversed_comparison_code (cond2
, bb2
->end
);
700 code2
= GET_CODE (cond2
);
701 if (code2
== UNKNOWN
)
704 /* Verify codes and operands match. */
705 match
= ((code1
== code2
706 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
707 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
708 || (code1
== swap_condition (code2
)
709 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
711 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
714 /* If we return true, we will join the blocks. Which means that
715 we will only have one branch prediction bit to work with. Thus
716 we require the existing branches to have probabilities that are
718 /* ??? We should use bb->frequency to allow merging in infrequently
719 executed blocks, but at the moment it is not available when
720 cleanup_cfg is run. */
721 if (match
&& !optimize_size
)
725 note1
= find_reg_note (bb1
->end
, REG_BR_PROB
, 0);
726 note2
= find_reg_note (bb2
->end
, REG_BR_PROB
, 0);
730 prob1
= INTVAL (XEXP (note1
, 0));
731 prob2
= INTVAL (XEXP (note2
, 0));
733 prob2
= REG_BR_PROB_BASE
- prob2
;
735 /* Fail if the difference in probabilities is
737 if (abs (prob1
- prob2
) > REG_BR_PROB_BASE
/ 20)
740 else if (note1
|| note2
)
744 if (rtl_dump_file
&& match
)
745 fprintf (rtl_dump_file
, "Conditionals in bb %i and %i match.\n",
746 bb1
->index
, bb2
->index
);
751 /* ??? We can handle computed jumps too. This may be important for
752 inlined functions containing switch statements. Also jumps w/o
753 fallthru edges can be handled by simply matching whole insn. */
757 /* E1 and E2 are edges with the same destination block. Search their
758 predecessors for common code. If found, redirect control flow from
759 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
762 try_crossjump_to_edge (mode
, e1
, e2
)
767 basic_block src1
= e1
->src
, src2
= e2
->src
;
768 basic_block redirect_to
;
769 rtx newpos1
, newpos2
;
775 /* Search backward through forwarder blocks. We don't need to worry
776 about multiple entry or chained forwarders, as they will be optimized
777 away. We do this to look past the unconditional jump following a
778 conditional jump that is required due to the current CFG shape. */
780 && !src1
->pred
->pred_next
781 && forwarder_block_p (src1
))
787 && !src2
->pred
->pred_next
788 && forwarder_block_p (src2
))
794 /* Nothing to do if we reach ENTRY, or a common source block. */
795 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
800 /* Seeing more than 1 forwarder blocks would confuse us later... */
801 if (forwarder_block_p (e1
->dest
)
802 && forwarder_block_p (e1
->dest
->succ
->dest
))
804 if (forwarder_block_p (e2
->dest
)
805 && forwarder_block_p (e2
->dest
->succ
->dest
))
808 /* Likewise with dead code (possibly newly created by the other optimizations
810 if (!src1
->pred
|| !src2
->pred
)
813 /* Likewise with complex edges.
814 ??? We should be able to handle most complex edges later with some
816 if (e1
->flags
& EDGE_COMPLEX
)
819 /* Look for the common insn sequence, part the first ... */
820 if (!outgoing_edges_match (src1
, src2
))
823 /* ... and part the second. */
824 nmatch
= flow_find_cross_jump (mode
, src1
, src2
, &newpos1
, &newpos2
);
828 /* Avoid splitting if possible. */
829 if (newpos2
== src2
->head
)
834 fprintf (rtl_dump_file
, "Splitting bb %i before %i insns\n",
835 src2
->index
, nmatch
);
836 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
840 fprintf (rtl_dump_file
,
841 "Cross jumping from bb %i to bb %i; %i common insns\n",
842 src1
->index
, src2
->index
, nmatch
);
844 redirect_to
->count
+= src1
->count
;
845 redirect_to
->frequency
+= src1
->frequency
;
847 /* Recompute the frequencies and counts of outgoing edges. */
848 for (s
= redirect_to
->succ
; s
; s
= s
->succ_next
)
851 basic_block d
= s
->dest
;
853 if (forwarder_block_p (d
))
855 for (s2
= src1
->succ
; ; s2
= s2
->succ_next
)
857 basic_block d2
= s2
->dest
;
858 if (forwarder_block_p (d2
))
863 s
->count
+= s2
->count
;
865 /* Take care to update possible forwarder blocks. We verified
866 that there is no more than one in the chain, so we can't run
867 into infinite loop. */
868 if (forwarder_block_p (s
->dest
))
870 s
->dest
->succ
->count
+= s2
->count
;
871 s
->dest
->count
+= s2
->count
;
872 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
874 if (forwarder_block_p (s2
->dest
))
876 s2
->dest
->succ
->count
-= s2
->count
;
877 s2
->dest
->count
-= s2
->count
;
878 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
880 if (!redirect_to
->frequency
&& !src1
->frequency
)
881 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
884 ((s
->probability
* redirect_to
->frequency
+
885 s2
->probability
* src1
->frequency
)
886 / (redirect_to
->frequency
+ src1
->frequency
));
889 note
= find_reg_note (redirect_to
->end
, REG_BR_PROB
, 0);
891 XEXP (note
, 0) = GEN_INT (BRANCH_EDGE (redirect_to
)->probability
);
893 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
895 /* Skip possible basic block header. */
896 if (GET_CODE (newpos1
) == CODE_LABEL
)
897 newpos1
= NEXT_INSN (newpos1
);
898 if (GET_CODE (newpos1
) == NOTE
)
899 newpos1
= NEXT_INSN (newpos1
);
902 /* Emit the jump insn. */
903 label
= block_label (redirect_to
);
904 src1
->end
= emit_jump_insn_before (gen_jump (label
), newpos1
);
905 JUMP_LABEL (src1
->end
) = label
;
906 LABEL_NUSES (label
)++;
907 if (basic_block_for_insn
)
908 set_block_for_new_insns (src1
->end
, src1
);
910 /* Delete the now unreachable instructions. */
911 flow_delete_insn_chain (newpos1
, last
);
913 /* Make sure there is a barrier after the new jump. */
914 last
= next_nonnote_insn (src1
->end
);
915 if (!last
|| GET_CODE (last
) != BARRIER
)
916 emit_barrier_after (src1
->end
);
920 remove_edge (src1
->succ
);
921 make_single_succ_edge (src1
, redirect_to
, 0);
926 /* Search the predecessors of BB for common insn sequences. When found,
927 share code between them by redirecting control flow. Return true if
931 try_crossjump_bb (mode
, bb
)
935 edge e
, e2
, nexte2
, nexte
, fallthru
;
938 /* Nothing to do if there is not at least two incomming edges. */
939 if (!bb
->pred
|| !bb
->pred
->pred_next
)
942 /* It is always cheapest to redirect a block that ends in a branch to
943 a block that falls through into BB, as that adds no branches to the
944 program. We'll try that combination first. */
945 for (fallthru
= bb
->pred
; fallthru
; fallthru
= fallthru
->pred_next
)
946 if (fallthru
->flags
& EDGE_FALLTHRU
)
950 for (e
= bb
->pred
; e
; e
= nexte
)
952 nexte
= e
->pred_next
;
954 /* Elide complex edges now, as neither try_crossjump_to_edge
955 nor outgoing_edges_match can handle them. */
956 if (e
->flags
& EDGE_COMPLEX
)
959 /* As noted above, first try with the fallthru predecessor. */
962 /* Don't combine the fallthru edge into anything else.
963 If there is a match, we'll do it the other way around. */
967 if (try_crossjump_to_edge (mode
, e
, fallthru
))
975 /* Non-obvious work limiting check: Recognize that we're going
976 to call try_crossjump_bb on every basic block. So if we have
977 two blocks with lots of outgoing edges (a switch) and they
978 share lots of common destinations, then we would do the
979 cross-jump check once for each common destination.
981 Now, if the blocks actually are cross-jump candidates, then
982 all of their destinations will be shared. Which means that
983 we only need check them for cross-jump candidacy once. We
984 can eliminate redundant checks of crossjump(A,B) by arbitrarily
985 choosing to do the check from the block for which the edge
986 in question is the first successor of A. */
987 if (e
->src
->succ
!= e
)
990 for (e2
= bb
->pred
; e2
; e2
= nexte2
)
992 nexte2
= e2
->pred_next
;
997 /* We've already checked the fallthru edge above. */
1001 /* Again, neither try_crossjump_to_edge nor outgoing_edges_match
1002 can handle complex edges. */
1003 if (e2
->flags
& EDGE_COMPLEX
)
1006 /* The "first successor" check above only prevents multiple
1007 checks of crossjump(A,B). In order to prevent redundant
1008 checks of crossjump(B,A), require that A be the block
1009 with the lowest index. */
1010 if (e
->src
->index
> e2
->src
->index
)
1013 if (try_crossjump_to_edge (mode
, e
, e2
))
1025 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1026 instructions etc. Return nonzero if changes were made. */
1029 try_optimize_cfg (mode
)
1033 bool changed_overall
= false;
1037 /* Attempt to merge blocks as made possible by edge removal. If a block
1038 has only one successor, and the successor has only one predecessor,
1039 they may be combined. */
1047 fprintf (rtl_dump_file
, "\n\ntry_optimize_cfg iteration %i\n\n",
1050 for (i
= 0; i
< n_basic_blocks
;)
1052 basic_block c
, b
= BASIC_BLOCK (i
);
1054 bool changed_here
= false;
1056 /* Delete trivially dead basic blocks. */
1057 while (b
->pred
== NULL
)
1059 c
= BASIC_BLOCK (b
->index
- 1);
1061 fprintf (rtl_dump_file
, "Deleting block %i.\n", b
->index
);
1062 flow_delete_block (b
);
1067 /* Remove code labels no longer used. Don't do this before
1068 CALL_PLACEHOLDER is removed, as some branches may be hidden
1070 if (b
->pred
->pred_next
== NULL
1071 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1072 && !(b
->pred
->flags
& EDGE_COMPLEX
)
1073 && GET_CODE (b
->head
) == CODE_LABEL
1074 && (!(mode
& CLEANUP_PRE_SIBCALL
)
1075 || !tail_recursion_label_p (b
->head
))
1076 /* If previous block ends with condjump jumping to next BB,
1077 we can't delete the label. */
1078 && (b
->pred
->src
== ENTRY_BLOCK_PTR
1079 || !reg_mentioned_p (b
->head
, b
->pred
->src
->end
)))
1081 rtx label
= b
->head
;
1082 b
->head
= NEXT_INSN (b
->head
);
1083 flow_delete_insn_chain (label
, label
);
1085 fprintf (rtl_dump_file
, "Deleted label in block %i.\n",
1089 /* If we fall through an empty block, we can remove it. */
1090 if (b
->pred
->pred_next
== NULL
1091 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1092 && GET_CODE (b
->head
) != CODE_LABEL
1093 && forwarder_block_p (b
)
1094 /* Note that forwarder_block_p true ensures that there
1095 is a successor for this block. */
1096 && (b
->succ
->flags
& EDGE_FALLTHRU
)
1097 && n_basic_blocks
> 1)
1100 fprintf (rtl_dump_file
, "Deleting fallthru block %i.\n",
1102 c
= BASIC_BLOCK (b
->index
? b
->index
- 1 : 1);
1103 redirect_edge_succ_nodup (b
->pred
, b
->succ
->dest
);
1104 flow_delete_block (b
);
1109 /* Merge blocks. Loop because chains of blocks might be
1111 while ((s
= b
->succ
) != NULL
1112 && s
->succ_next
== NULL
1113 && !(s
->flags
& EDGE_COMPLEX
)
1114 && (c
= s
->dest
) != EXIT_BLOCK_PTR
1115 && c
->pred
->pred_next
== NULL
1116 /* If the jump insn has side effects,
1117 we can't kill the edge. */
1118 && (GET_CODE (b
->end
) != JUMP_INSN
1119 || onlyjump_p (b
->end
))
1120 && merge_blocks (s
, b
, c
, mode
))
1121 changed_here
= true;
1123 /* Simplify branch over branch. */
1124 if ((mode
& CLEANUP_EXPENSIVE
) && try_simplify_condjump (b
))
1125 changed_here
= true;
1127 /* If B has a single outgoing edge, but uses a non-trivial jump
1128 instruction without side-effects, we can either delete the
1129 jump entirely, or replace it with a simple unconditional jump.
1130 Use redirect_edge_and_branch to do the dirty work. */
1132 && ! b
->succ
->succ_next
1133 && b
->succ
->dest
!= EXIT_BLOCK_PTR
1134 && onlyjump_p (b
->end
)
1135 && redirect_edge_and_branch (b
->succ
, b
->succ
->dest
))
1136 changed_here
= true;
1138 /* Simplify branch to branch. */
1139 if (try_forward_edges (mode
, b
))
1140 changed_here
= true;
1142 /* Look for shared code between blocks. */
1143 if ((mode
& CLEANUP_CROSSJUMP
)
1144 && try_crossjump_bb (mode
, b
))
1145 changed_here
= true;
1147 /* Don't get confused by the index shift caused by deleting
1155 if ((mode
& CLEANUP_CROSSJUMP
)
1156 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
1159 #ifdef ENABLE_CHECKING
1161 verify_flow_info ();
1164 changed_overall
|= changed
;
1167 return changed_overall
;
1170 /* Delete all unreachable basic blocks. */
1173 delete_unreachable_blocks ()
1176 bool changed
= false;
1178 find_unreachable_blocks ();
1180 /* Delete all unreachable basic blocks. Count down so that we
1181 don't interfere with the block renumbering that happens in
1182 flow_delete_block. */
1184 for (i
= n_basic_blocks
- 1; i
>= 0; --i
)
1186 basic_block b
= BASIC_BLOCK (i
);
1188 if (!(b
->flags
& BB_REACHABLE
))
1189 flow_delete_block (b
), changed
= true;
1193 tidy_fallthru_edges ();
1197 /* Tidy the CFG by deleting unreachable code and whatnot. */
1204 bool changed
= false;
1206 timevar_push (TV_CLEANUP_CFG
);
1207 changed
= delete_unreachable_blocks ();
1208 if (try_optimize_cfg (mode
))
1209 delete_unreachable_blocks (), changed
= true;
1211 /* Kill the data we won't maintain. */
1212 free_EXPR_LIST_list (&label_value_list
);
1213 free_EXPR_LIST_list (&tail_recursion_label_list
);
1214 timevar_pop (TV_CLEANUP_CFG
);
1216 /* Clear bb->aux on all basic blocks. */
1217 for (i
= 0; i
< n_basic_blocks
; ++i
)
1218 BASIC_BLOCK (i
)->aux
= NULL
;