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"
51 /* cleanup_cfg maintains following flags for each basic block. */
55 /* Set if BB is the forwarder block to avoid too many
56 forwarder_block_p calls. */
57 BB_FORWARDER_BLOCK
= 1
60 #define BB_FLAGS(BB) (enum bb_flags) (BB)->aux
61 #define BB_SET_FLAG(BB, FLAG) \
62 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux | (FLAG))
63 #define BB_CLEAR_FLAG(BB, FLAG) \
64 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux & ~(FLAG))
66 #define FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK)
68 static bool try_crossjump_to_edge
PARAMS ((int, edge
, edge
));
69 static bool try_crossjump_bb
PARAMS ((int, basic_block
));
70 static bool outgoing_edges_match
PARAMS ((int,
71 basic_block
, basic_block
));
72 static int flow_find_cross_jump
PARAMS ((int, basic_block
, basic_block
,
74 static bool insns_match_p
PARAMS ((int, rtx
, rtx
));
76 static bool delete_unreachable_blocks
PARAMS ((void));
77 static bool label_is_jump_target_p
PARAMS ((rtx
, rtx
));
78 static bool tail_recursion_label_p
PARAMS ((rtx
));
79 static void merge_blocks_move_predecessor_nojumps
PARAMS ((basic_block
,
81 static void merge_blocks_move_successor_nojumps
PARAMS ((basic_block
,
83 static bool merge_blocks
PARAMS ((edge
,basic_block
,basic_block
,
85 static bool try_optimize_cfg
PARAMS ((int));
86 static bool try_simplify_condjump
PARAMS ((basic_block
));
87 static bool try_forward_edges
PARAMS ((int, basic_block
));
88 static edge thread_jump
PARAMS ((int, edge
, basic_block
));
89 static bool mark_effect
PARAMS ((rtx
, bitmap
));
90 static void notice_new_block
PARAMS ((basic_block
));
91 static void update_forwarder_flag
PARAMS ((basic_block
));
92 static int mentions_nonequal_regs
PARAMS ((rtx
*, void *));
94 /* Set flags for newly created block. */
103 if (forwarder_block_p (bb
))
104 BB_SET_FLAG (bb
, BB_FORWARDER_BLOCK
);
107 /* Recompute forwarder flag after block has been modified. */
110 update_forwarder_flag (bb
)
113 if (forwarder_block_p (bb
))
114 BB_SET_FLAG (bb
, BB_FORWARDER_BLOCK
);
116 BB_CLEAR_FLAG (bb
, BB_FORWARDER_BLOCK
);
119 /* Simplify a conditional jump around an unconditional jump.
120 Return true if something changed. */
123 try_simplify_condjump (cbranch_block
)
124 basic_block cbranch_block
;
126 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
127 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
130 /* Verify that there are exactly two successors. */
131 if (!cbranch_block
->succ
132 || !cbranch_block
->succ
->succ_next
133 || cbranch_block
->succ
->succ_next
->succ_next
)
136 /* Verify that we've got a normal conditional branch at the end
138 cbranch_insn
= cbranch_block
->end
;
139 if (!any_condjump_p (cbranch_insn
))
142 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
143 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
145 /* The next block must not have multiple predecessors, must not
146 be the last block in the function, and must contain just the
147 unconditional jump. */
148 jump_block
= cbranch_fallthru_edge
->dest
;
149 if (jump_block
->pred
->pred_next
150 || jump_block
->index
== n_basic_blocks
- 1
151 || !FORWARDER_BLOCK_P (jump_block
))
153 jump_dest_block
= jump_block
->succ
->dest
;
155 /* The conditional branch must target the block after the
156 unconditional branch. */
157 cbranch_dest_block
= cbranch_jump_edge
->dest
;
159 if (!can_fallthru (jump_block
, cbranch_dest_block
))
162 /* Invert the conditional branch. */
163 if (!invert_jump (cbranch_insn
, block_label (jump_dest_block
), 0))
167 fprintf (rtl_dump_file
, "Simplifying condjump %i around jump %i\n",
168 INSN_UID (cbranch_insn
), INSN_UID (jump_block
->end
));
170 /* Success. Update the CFG to match. Note that after this point
171 the edge variable names appear backwards; the redirection is done
172 this way to preserve edge profile data. */
173 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
175 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
177 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
178 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
179 update_br_prob_note (cbranch_block
);
181 /* Delete the block with the unconditional jump, and clean up the mess. */
182 flow_delete_block (jump_block
);
183 tidy_fallthru_edge (cbranch_jump_edge
, cbranch_block
, cbranch_dest_block
);
188 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
189 on register. Used by jump threading. */
192 mark_effect (exp
, nonequal
)
198 switch (GET_CODE (exp
))
200 /* In case we do clobber the register, mark it as equal, as we know the
201 value is dead so it don't have to match. */
203 if (REG_P (XEXP (exp
, 0)))
205 dest
= XEXP (exp
, 0);
206 regno
= REGNO (dest
);
207 CLEAR_REGNO_REG_SET (nonequal
, regno
);
208 if (regno
< FIRST_PSEUDO_REGISTER
)
210 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
212 CLEAR_REGNO_REG_SET (nonequal
, regno
+ n
);
218 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
220 dest
= SET_DEST (exp
);
225 regno
= REGNO (dest
);
226 SET_REGNO_REG_SET (nonequal
, regno
);
227 if (regno
< FIRST_PSEUDO_REGISTER
)
229 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
231 SET_REGNO_REG_SET (nonequal
, regno
+ n
);
240 /* Return nonzero if X is an register set in regset DATA.
241 Called via for_each_rtx. */
243 mentions_nonequal_regs (x
, data
)
247 regset nonequal
= (regset
) data
;
253 if (REGNO_REG_SET_P (nonequal
, regno
))
255 if (regno
< FIRST_PSEUDO_REGISTER
)
257 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (*x
));
259 if (REGNO_REG_SET_P (nonequal
, regno
+ n
))
265 /* Attempt to prove that the basic block B will have no side effects and
266 allways continues in the same edge if reached via E. Return the edge
267 if exist, NULL otherwise. */
270 thread_jump (mode
, e
, b
)
275 rtx set1
, set2
, cond1
, cond2
, insn
;
276 enum rtx_code code1
, code2
, reversed_code2
;
277 bool reverse1
= false;
282 /* At the moment, we do handle only conditional jumps, but later we may
283 want to extend this code to tablejumps and others. */
284 if (!e
->src
->succ
->succ_next
|| e
->src
->succ
->succ_next
->succ_next
)
286 if (!b
->succ
|| !b
->succ
->succ_next
|| b
->succ
->succ_next
->succ_next
)
289 /* Second branch must end with onlyjump, as we will eliminate the jump. */
290 if (!any_condjump_p (e
->src
->end
) || !any_condjump_p (b
->end
)
291 || !onlyjump_p (b
->end
))
294 set1
= pc_set (e
->src
->end
);
295 set2
= pc_set (b
->end
);
296 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
297 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
300 cond1
= XEXP (SET_SRC (set1
), 0);
301 cond2
= XEXP (SET_SRC (set2
), 0);
303 code1
= reversed_comparison_code (cond1
, e
->src
->end
);
305 code1
= GET_CODE (cond1
);
307 code2
= GET_CODE (cond2
);
308 reversed_code2
= reversed_comparison_code (cond2
, b
->end
);
310 if (!comparison_dominates_p (code1
, code2
)
311 && !comparison_dominates_p (code1
, reversed_code2
))
314 /* Ensure that the comparison operators are equivalent.
315 ??? This is far too pesimistic. We should allow swapped operands,
316 different CCmodes, or for example comparisons for interval, that
317 dominate even when operands are not equivalent. */
318 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
319 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
322 /* Short circuit cases where block B contains some side effects, as we can't
324 for (insn
= NEXT_INSN (b
->head
); insn
!= NEXT_INSN (b
->end
);
325 insn
= NEXT_INSN (insn
))
326 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
331 /* First process all values computed in the source basic block. */
332 for (insn
= NEXT_INSN (e
->src
->head
); insn
!= NEXT_INSN (e
->src
->end
);
333 insn
= NEXT_INSN (insn
))
335 cselib_process_insn (insn
);
337 nonequal
= BITMAP_XMALLOC();
338 CLEAR_REG_SET (nonequal
);
340 /* Now assume that we've continued by the edge E to B and continue
341 processing as if it were same basic block.
342 Our goal is to prove that whole block is an NOOP. */
344 for (insn
= NEXT_INSN (b
->head
); insn
!= NEXT_INSN (b
->end
) && !failed
;
345 insn
= NEXT_INSN (insn
))
349 rtx pat
= PATTERN (insn
);
351 if (GET_CODE (pat
) == PARALLEL
)
353 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
354 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
357 failed
|= mark_effect (pat
, nonequal
);
360 cselib_process_insn (insn
);
363 /* Later we should clear nonequal of dead registers. So far we don't
364 have life information in cfg_cleanup. */
368 /* cond2 must not mention any register that is not equal to the
370 if (for_each_rtx (&cond2
, mentions_nonequal_regs
, nonequal
))
373 /* In case liveness information is available, we need to prove equivalence
374 only of the live values. */
375 if (mode
& CLEANUP_UPDATE_LIFE
)
376 AND_REG_SET (nonequal
, b
->global_live_at_end
);
378 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, goto failed_exit
;);
380 BITMAP_XFREE (nonequal
);
382 if ((comparison_dominates_p (code1
, code2
) != 0)
383 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
384 return BRANCH_EDGE (b
);
386 return FALLTHRU_EDGE (b
);
389 BITMAP_XFREE (nonequal
);
394 /* Attempt to forward edges leaving basic block B.
395 Return true if successful. */
398 try_forward_edges (mode
, b
)
402 bool changed
= false;
403 edge e
, next
, *threaded_edges
= NULL
;
405 for (e
= b
->succ
; e
; e
= next
)
407 basic_block target
, first
;
409 bool threaded
= false;
410 int nthreaded_edges
= 0;
414 /* Skip complex edges because we don't know how to update them.
416 Still handle fallthru edges, as we can succeed to forward fallthru
417 edge to the same place as the branch edge of conditional branch
418 and turn conditional branch to an unconditional branch. */
419 if (e
->flags
& EDGE_COMPLEX
)
422 target
= first
= e
->dest
;
425 while (counter
< n_basic_blocks
)
427 basic_block new_target
= NULL
;
428 bool new_target_threaded
= false;
430 if (FORWARDER_BLOCK_P (target
)
431 && target
->succ
->dest
!= EXIT_BLOCK_PTR
)
433 /* Bypass trivial infinite loops. */
434 if (target
== target
->succ
->dest
)
435 counter
= n_basic_blocks
;
436 new_target
= target
->succ
->dest
;
439 /* Allow to thread only over one edge at time to simplify updating
441 else if (mode
& CLEANUP_THREADING
)
443 edge t
= thread_jump (mode
, e
, target
);
447 threaded_edges
= xmalloc (sizeof (*threaded_edges
)
453 /* Detect an infinite loop across blocks not
454 including the start block. */
455 for (i
= 0; i
< nthreaded_edges
; ++i
)
456 if (threaded_edges
[i
] == t
)
458 if (i
< nthreaded_edges
)
460 counter
= n_basic_blocks
;
465 /* Detect an infinite loop across the start block. */
469 if (nthreaded_edges
>= n_basic_blocks
)
471 threaded_edges
[nthreaded_edges
++] = t
;
473 new_target
= t
->dest
;
474 new_target_threaded
= true;
481 /* Avoid killing of loop pre-headers, as it is the place loop
482 optimizer wants to hoist code to.
484 For fallthru forwarders, the LOOP_BEG note must appear between
485 the header of block and CODE_LABEL of the loop, for non forwarders
486 it must appear before the JUMP_INSN. */
487 if (mode
& CLEANUP_PRE_LOOP
)
489 rtx insn
= (target
->succ
->flags
& EDGE_FALLTHRU
490 ? target
->head
: prev_nonnote_insn (target
->end
));
492 if (GET_CODE (insn
) != NOTE
)
493 insn
= NEXT_INSN (insn
);
495 for (; insn
&& GET_CODE (insn
) != CODE_LABEL
&& !INSN_P (insn
);
496 insn
= NEXT_INSN (insn
))
497 if (GET_CODE (insn
) == NOTE
498 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
501 if (GET_CODE (insn
) == NOTE
)
507 threaded
|= new_target_threaded
;
510 if (counter
>= n_basic_blocks
)
513 fprintf (rtl_dump_file
, "Infinite loop in BB %i.\n",
516 else if (target
== first
)
517 ; /* We didn't do anything. */
520 /* Save the values now, as the edge may get removed. */
521 gcov_type edge_count
= e
->count
;
522 int edge_probability
= e
->probability
;
526 /* Don't force if target is exit block. */
527 if (threaded
&& target
!= EXIT_BLOCK_PTR
)
529 notice_new_block (redirect_edge_and_branch_force (e
, target
));
531 fprintf (rtl_dump_file
, "Conditionals threaded.\n");
533 else if (!redirect_edge_and_branch (e
, target
))
536 fprintf (rtl_dump_file
,
537 "Forwarding edge %i->%i to %i failed.\n",
538 b
->index
, e
->dest
->index
, target
->index
);
542 /* We successfully forwarded the edge. Now update profile
543 data: for each edge we traversed in the chain, remove
544 the original edge's execution count. */
545 edge_frequency
= ((edge_probability
* b
->frequency
546 + REG_BR_PROB_BASE
/ 2)
549 if (!FORWARDER_BLOCK_P (b
) && forwarder_block_p (b
))
550 BB_SET_FLAG (b
, BB_FORWARDER_BLOCK
);
556 first
->count
-= edge_count
;
557 if (first
->count
< 0)
559 first
->frequency
-= edge_frequency
;
560 if (first
->frequency
< 0)
561 first
->frequency
= 0;
562 if (first
->succ
->succ_next
)
566 if (n
>= nthreaded_edges
)
568 t
= threaded_edges
[n
++];
571 if (first
->frequency
)
572 prob
= edge_frequency
* REG_BR_PROB_BASE
/ first
->frequency
;
575 if (prob
> t
->probability
)
576 prob
= t
->probability
;
577 t
->probability
-= prob
;
578 prob
= REG_BR_PROB_BASE
- prob
;
581 first
->succ
->probability
= REG_BR_PROB_BASE
;
582 first
->succ
->succ_next
->probability
= 0;
585 for (e
= first
->succ
; e
; e
= e
->succ_next
)
586 e
->probability
= ((e
->probability
* REG_BR_PROB_BASE
)
588 update_br_prob_note (first
);
592 /* It is possible that as the result of
593 threading we've removed edge as it is
594 threaded to the fallthru edge. Avoid
595 getting out of sync. */
596 if (n
< nthreaded_edges
597 && first
== threaded_edges
[n
]->src
)
602 t
->count
-= edge_count
;
607 while (first
!= target
);
614 free (threaded_edges
);
618 /* Return true if LABEL is a target of JUMP_INSN. This applies only
619 to non-complex jumps. That is, direct unconditional, conditional,
620 and tablejumps, but not computed jumps or returns. It also does
621 not apply to the fallthru case of a conditional jump. */
624 label_is_jump_target_p (label
, jump_insn
)
625 rtx label
, jump_insn
;
627 rtx tmp
= JUMP_LABEL (jump_insn
);
633 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
634 && GET_CODE (tmp
) == JUMP_INSN
635 && (tmp
= PATTERN (tmp
),
636 GET_CODE (tmp
) == ADDR_VEC
637 || GET_CODE (tmp
) == ADDR_DIFF_VEC
))
639 rtvec vec
= XVEC (tmp
, GET_CODE (tmp
) == ADDR_DIFF_VEC
);
640 int i
, veclen
= GET_NUM_ELEM (vec
);
642 for (i
= 0; i
< veclen
; ++i
)
643 if (XEXP (RTVEC_ELT (vec
, i
), 0) == label
)
650 /* Return true if LABEL is used for tail recursion. */
653 tail_recursion_label_p (label
)
658 for (x
= tail_recursion_label_list
; x
; x
= XEXP (x
, 1))
659 if (label
== XEXP (x
, 0))
665 /* Blocks A and B are to be merged into a single block. A has no incoming
666 fallthru edge, so it can be moved before B without adding or modifying
667 any jumps (aside from the jump from A to B). */
670 merge_blocks_move_predecessor_nojumps (a
, b
)
676 barrier
= next_nonnote_insn (a
->end
);
677 if (GET_CODE (barrier
) != BARRIER
)
679 delete_insn (barrier
);
681 /* Move block and loop notes out of the chain so that we do not
684 ??? A better solution would be to squeeze out all the non-nested notes
685 and adjust the block trees appropriately. Even better would be to have
686 a tighter connection between block trees and rtl so that this is not
688 if (squeeze_notes (&a
->head
, &a
->end
))
691 /* Scramble the insn chain. */
692 if (a
->end
!= PREV_INSN (b
->head
))
693 reorder_insns_nobb (a
->head
, a
->end
, PREV_INSN (b
->head
));
694 a
->flags
|= BB_DIRTY
;
697 fprintf (rtl_dump_file
, "Moved block %d before %d and merged.\n",
700 /* Swap the records for the two blocks around. Although we are deleting B,
701 A is now where B was and we want to compact the BB array from where
703 BASIC_BLOCK (a
->index
) = b
;
704 BASIC_BLOCK (b
->index
) = a
;
709 /* Now blocks A and B are contiguous. Merge them. */
710 merge_blocks_nomove (a
, b
);
713 /* Blocks A and B are to be merged into a single block. B has no outgoing
714 fallthru edge, so it can be moved after A without adding or modifying
715 any jumps (aside from the jump from A to B). */
718 merge_blocks_move_successor_nojumps (a
, b
)
721 rtx barrier
, real_b_end
;
724 barrier
= NEXT_INSN (b
->end
);
726 /* Recognize a jump table following block B. */
728 && GET_CODE (barrier
) == CODE_LABEL
729 && NEXT_INSN (barrier
)
730 && GET_CODE (NEXT_INSN (barrier
)) == JUMP_INSN
731 && (GET_CODE (PATTERN (NEXT_INSN (barrier
))) == ADDR_VEC
732 || GET_CODE (PATTERN (NEXT_INSN (barrier
))) == ADDR_DIFF_VEC
))
734 /* Temporarily add the table jump insn to b, so that it will also
735 be moved to the correct location. */
736 b
->end
= NEXT_INSN (barrier
);
737 barrier
= NEXT_INSN (b
->end
);
740 /* There had better have been a barrier there. Delete it. */
741 if (barrier
&& GET_CODE (barrier
) == BARRIER
)
742 delete_insn (barrier
);
744 /* Move block and loop notes out of the chain so that we do not
747 ??? A better solution would be to squeeze out all the non-nested notes
748 and adjust the block trees appropriately. Even better would be to have
749 a tighter connection between block trees and rtl so that this is not
751 if (squeeze_notes (&b
->head
, &b
->end
))
754 /* Scramble the insn chain. */
755 reorder_insns_nobb (b
->head
, b
->end
, a
->end
);
757 /* Restore the real end of b. */
760 /* Now blocks A and B are contiguous. Merge them. */
761 merge_blocks_nomove (a
, b
);
764 fprintf (rtl_dump_file
, "Moved block %d after %d and merged.\n",
768 /* Attempt to merge basic blocks that are potentially non-adjacent.
769 Return true iff the attempt succeeded. */
772 merge_blocks (e
, b
, c
, mode
)
777 /* If C has a tail recursion label, do not merge. There is no
778 edge recorded from the call_placeholder back to this label, as
779 that would make optimize_sibling_and_tail_recursive_calls more
780 complex for no gain. */
781 if ((mode
& CLEANUP_PRE_SIBCALL
)
782 && GET_CODE (c
->head
) == CODE_LABEL
783 && tail_recursion_label_p (c
->head
))
786 /* If B has a fallthru edge to C, no need to move anything. */
787 if (e
->flags
& EDGE_FALLTHRU
)
789 int b_index
= b
->index
, c_index
= c
->index
;
790 merge_blocks_nomove (b
, c
);
791 update_forwarder_flag (b
);
794 fprintf (rtl_dump_file
, "Merged %d and %d without moving.\n",
800 /* Otherwise we will need to move code around. Do that only if expensive
801 transformations are allowed. */
802 else if (mode
& CLEANUP_EXPENSIVE
)
804 edge tmp_edge
, b_fallthru_edge
;
805 bool c_has_outgoing_fallthru
;
806 bool b_has_incoming_fallthru
;
808 /* Avoid overactive code motion, as the forwarder blocks should be
809 eliminated by edge redirection instead. One exception might have
810 been if B is a forwarder block and C has no fallthru edge, but
811 that should be cleaned up by bb-reorder instead. */
812 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
815 /* We must make sure to not munge nesting of lexical blocks,
816 and loop notes. This is done by squeezing out all the notes
817 and leaving them there to lie. Not ideal, but functional. */
819 for (tmp_edge
= c
->succ
; tmp_edge
; tmp_edge
= tmp_edge
->succ_next
)
820 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
823 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
825 for (tmp_edge
= b
->pred
; tmp_edge
; tmp_edge
= tmp_edge
->pred_next
)
826 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
829 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
830 b_fallthru_edge
= tmp_edge
;
832 /* Otherwise, we're going to try to move C after B. If C does
833 not have an outgoing fallthru, then it can be moved
834 immediately after B without introducing or modifying jumps. */
835 if (! c_has_outgoing_fallthru
)
837 merge_blocks_move_successor_nojumps (b
, c
);
841 /* If B does not have an incoming fallthru, then it can be moved
842 immediately before C without introducing or modifying jumps.
843 C cannot be the first block, so we do not have to worry about
844 accessing a non-existent block. */
846 if (b_has_incoming_fallthru
)
850 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
852 bb
= force_nonfallthru (b_fallthru_edge
);
854 notice_new_block (bb
);
857 merge_blocks_move_predecessor_nojumps (b
, c
);
865 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
868 insns_match_p (mode
, i1
, i2
)
869 int mode ATTRIBUTE_UNUSED
;
874 /* Verify that I1 and I2 are equivalent. */
875 if (GET_CODE (i1
) != GET_CODE (i2
))
881 if (GET_CODE (p1
) != GET_CODE (p2
))
884 /* If this is a CALL_INSN, compare register usage information.
885 If we don't check this on stack register machines, the two
886 CALL_INSNs might be merged leaving reg-stack.c with mismatching
887 numbers of stack registers in the same basic block.
888 If we don't check this on machines with delay slots, a delay slot may
889 be filled that clobbers a parameter expected by the subroutine.
891 ??? We take the simple route for now and assume that if they're
892 equal, they were constructed identically. */
894 if (GET_CODE (i1
) == CALL_INSN
895 && !rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
896 CALL_INSN_FUNCTION_USAGE (i2
)))
900 /* If cross_jump_death_matters is not 0, the insn's mode
901 indicates whether or not the insn contains any stack-like
904 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
906 /* If register stack conversion has already been done, then
907 death notes must also be compared before it is certain that
908 the two instruction streams match. */
911 HARD_REG_SET i1_regset
, i2_regset
;
913 CLEAR_HARD_REG_SET (i1_regset
);
914 CLEAR_HARD_REG_SET (i2_regset
);
916 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
917 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
918 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
920 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
921 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
922 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
924 GO_IF_HARD_REG_EQUAL (i1_regset
, i2_regset
, done
);
934 ? ! rtx_renumbered_equal_p (p1
, p2
) : ! rtx_equal_p (p1
, p2
))
936 /* The following code helps take care of G++ cleanups. */
937 rtx equiv1
= find_reg_equal_equiv_note (i1
);
938 rtx equiv2
= find_reg_equal_equiv_note (i2
);
941 /* If the equivalences are not to a constant, they may
942 reference pseudos that no longer exist, so we can't
944 && (! reload_completed
945 || (CONSTANT_P (XEXP (equiv1
, 0))
946 && rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))))
948 rtx s1
= single_set (i1
);
949 rtx s2
= single_set (i2
);
950 if (s1
!= 0 && s2
!= 0
951 && rtx_renumbered_equal_p (SET_DEST (s1
), SET_DEST (s2
)))
953 validate_change (i1
, &SET_SRC (s1
), XEXP (equiv1
, 0), 1);
954 validate_change (i2
, &SET_SRC (s2
), XEXP (equiv2
, 0), 1);
955 if (! rtx_renumbered_equal_p (p1
, p2
))
957 else if (apply_change_group ())
968 /* Look through the insns at the end of BB1 and BB2 and find the longest
969 sequence that are equivalent. Store the first insns for that sequence
970 in *F1 and *F2 and return the sequence length.
972 To simplify callers of this function, if the blocks match exactly,
973 store the head of the blocks in *F1 and *F2. */
976 flow_find_cross_jump (mode
, bb1
, bb2
, f1
, f2
)
977 int mode ATTRIBUTE_UNUSED
;
978 basic_block bb1
, bb2
;
981 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
984 /* Skip simple jumps at the end of the blocks. Complex jumps still
985 need to be compared for equivalence, which we'll do below. */
988 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
990 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
998 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1001 /* Count everything except for unconditional jump as insn. */
1002 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1004 i2
= PREV_INSN (i2
);
1010 while (!active_insn_p (i1
) && i1
!= bb1
->head
)
1011 i1
= PREV_INSN (i1
);
1013 while (!active_insn_p (i2
) && i2
!= bb2
->head
)
1014 i2
= PREV_INSN (i2
);
1016 if (i1
== bb1
->head
|| i2
== bb2
->head
)
1019 if (!insns_match_p (mode
, i1
, i2
))
1022 /* Don't begin a cross-jump with a USE or CLOBBER insn. */
1023 if (active_insn_p (i1
))
1025 /* If the merged insns have different REG_EQUAL notes, then
1027 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1028 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1030 if (equiv1
&& !equiv2
)
1031 remove_note (i1
, equiv1
);
1032 else if (!equiv1
&& equiv2
)
1033 remove_note (i2
, equiv2
);
1034 else if (equiv1
&& equiv2
1035 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1037 remove_note (i1
, equiv1
);
1038 remove_note (i2
, equiv2
);
1041 afterlast1
= last1
, afterlast2
= last2
;
1042 last1
= i1
, last2
= i2
;
1046 i1
= PREV_INSN (i1
);
1047 i2
= PREV_INSN (i2
);
1051 /* Don't allow the insn after a compare to be shared by
1052 cross-jumping unless the compare is also shared. */
1053 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1054 last1
= afterlast1
, last2
= afterlast2
, ninsns
--;
1057 /* Include preceding notes and labels in the cross-jump. One,
1058 this may bring us to the head of the blocks as requested above.
1059 Two, it keeps line number notes as matched as may be. */
1062 while (last1
!= bb1
->head
&& !active_insn_p (PREV_INSN (last1
)))
1063 last1
= PREV_INSN (last1
);
1065 if (last1
!= bb1
->head
&& GET_CODE (PREV_INSN (last1
)) == CODE_LABEL
)
1066 last1
= PREV_INSN (last1
);
1068 while (last2
!= bb2
->head
&& !active_insn_p (PREV_INSN (last2
)))
1069 last2
= PREV_INSN (last2
);
1071 if (last2
!= bb2
->head
&& GET_CODE (PREV_INSN (last2
)) == CODE_LABEL
)
1072 last2
= PREV_INSN (last2
);
1081 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1082 the branch instruction. This means that if we commonize the control
1083 flow before end of the basic block, the semantic remains unchanged.
1085 We may assume that there exists one edge with a common destination. */
1088 outgoing_edges_match (mode
, bb1
, bb2
)
1093 int nehedges1
= 0, nehedges2
= 0;
1094 edge fallthru1
= 0, fallthru2
= 0;
1097 /* If BB1 has only one successor, we may be looking at either an
1098 unconditional jump, or a fake edge to exit. */
1099 if (bb1
->succ
&& !bb1
->succ
->succ_next
1100 && !(bb1
->succ
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
1101 return (bb2
->succ
&& !bb2
->succ
->succ_next
1102 && (bb2
->succ
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0);
1104 /* Match conditional jumps - this may get tricky when fallthru and branch
1105 edges are crossed. */
1107 && bb1
->succ
->succ_next
1108 && !bb1
->succ
->succ_next
->succ_next
1109 && any_condjump_p (bb1
->end
)
1110 && onlyjump_p (bb1
->end
))
1112 edge b1
, f1
, b2
, f2
;
1113 bool reverse
, match
;
1114 rtx set1
, set2
, cond1
, cond2
;
1115 enum rtx_code code1
, code2
;
1118 || !bb2
->succ
->succ_next
1119 || bb1
->succ
->succ_next
->succ_next
1120 || !any_condjump_p (bb2
->end
)
1121 || !onlyjump_p (bb1
->end
))
1124 b1
= BRANCH_EDGE (bb1
);
1125 b2
= BRANCH_EDGE (bb2
);
1126 f1
= FALLTHRU_EDGE (bb1
);
1127 f2
= FALLTHRU_EDGE (bb2
);
1129 /* Get around possible forwarders on fallthru edges. Other cases
1130 should be optimized out already. */
1131 if (FORWARDER_BLOCK_P (f1
->dest
))
1132 f1
= f1
->dest
->succ
;
1134 if (FORWARDER_BLOCK_P (f2
->dest
))
1135 f2
= f2
->dest
->succ
;
1137 /* To simplify use of this function, return false if there are
1138 unneeded forwarder blocks. These will get eliminated later
1139 during cleanup_cfg. */
1140 if (FORWARDER_BLOCK_P (f1
->dest
)
1141 || FORWARDER_BLOCK_P (f2
->dest
)
1142 || FORWARDER_BLOCK_P (b1
->dest
)
1143 || FORWARDER_BLOCK_P (b2
->dest
))
1146 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1148 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1153 set1
= pc_set (bb1
->end
);
1154 set2
= pc_set (bb2
->end
);
1155 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1156 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1159 cond1
= XEXP (SET_SRC (set1
), 0);
1160 cond2
= XEXP (SET_SRC (set2
), 0);
1161 code1
= GET_CODE (cond1
);
1163 code2
= reversed_comparison_code (cond2
, bb2
->end
);
1165 code2
= GET_CODE (cond2
);
1167 if (code2
== UNKNOWN
)
1170 /* Verify codes and operands match. */
1171 match
= ((code1
== code2
1172 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1173 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1174 || (code1
== swap_condition (code2
)
1175 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1177 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1180 /* If we return true, we will join the blocks. Which means that
1181 we will only have one branch prediction bit to work with. Thus
1182 we require the existing branches to have probabilities that are
1186 && bb1
->frequency
> BB_FREQ_MAX
/ 1000
1187 && bb2
->frequency
> BB_FREQ_MAX
/ 1000)
1191 if (b1
->dest
== b2
->dest
)
1192 prob2
= b2
->probability
;
1194 /* Do not use f2 probability as f2 may be forwarded. */
1195 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1197 /* Fail if the difference in probabilities is
1199 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 20)
1202 fprintf (rtl_dump_file
,
1203 "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
1204 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1210 if (rtl_dump_file
&& match
)
1211 fprintf (rtl_dump_file
, "Conditionals in bb %i and %i match.\n",
1212 bb1
->index
, bb2
->index
);
1217 /* Generic case - we are seeing an computed jump, table jump or trapping
1220 /* First ensure that the instructions match. There may be many outgoing
1221 edges so this test is generally cheaper.
1222 ??? Currently the tablejumps will never match, as they do have
1223 different tables. */
1224 if (!insns_match_p (mode
, bb1
->end
, bb2
->end
))
1227 /* Search the outgoing edges, ensure that the counts do match, find possible
1228 fallthru and exception handling edges since these needs more
1230 for (e1
= bb1
->succ
, e2
= bb2
->succ
; e1
&& e2
;
1231 e1
= e1
->succ_next
, e2
= e2
->succ_next
)
1233 if (e1
->flags
& EDGE_EH
)
1236 if (e2
->flags
& EDGE_EH
)
1239 if (e1
->flags
& EDGE_FALLTHRU
)
1241 if (e2
->flags
& EDGE_FALLTHRU
)
1245 /* If number of edges of various types does not match, fail. */
1247 || nehedges1
!= nehedges2
1248 || (fallthru1
!= 0) != (fallthru2
!= 0))
1251 /* fallthru edges must be forwarded to the same destination. */
1254 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1255 ? fallthru1
->dest
->succ
->dest
: fallthru1
->dest
);
1256 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1257 ? fallthru2
->dest
->succ
->dest
: fallthru2
->dest
);
1263 /* In case we do have EH edges, ensure we are in the same region. */
1266 rtx n1
= find_reg_note (bb1
->end
, REG_EH_REGION
, 0);
1267 rtx n2
= find_reg_note (bb2
->end
, REG_EH_REGION
, 0);
1269 if (XEXP (n1
, 0) != XEXP (n2
, 0))
1273 /* We don't need to match the rest of edges as above checks should be enought
1274 to ensure that they are equivalent. */
1278 /* E1 and E2 are edges with the same destination block. Search their
1279 predecessors for common code. If found, redirect control flow from
1280 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1283 try_crossjump_to_edge (mode
, e1
, e2
)
1288 basic_block src1
= e1
->src
, src2
= e2
->src
;
1289 basic_block redirect_to
;
1290 rtx newpos1
, newpos2
;
1295 /* Search backward through forwarder blocks. We don't need to worry
1296 about multiple entry or chained forwarders, as they will be optimized
1297 away. We do this to look past the unconditional jump following a
1298 conditional jump that is required due to the current CFG shape. */
1300 && !src1
->pred
->pred_next
1301 && FORWARDER_BLOCK_P (src1
))
1302 e1
= src1
->pred
, src1
= e1
->src
;
1305 && !src2
->pred
->pred_next
1306 && FORWARDER_BLOCK_P (src2
))
1307 e2
= src2
->pred
, src2
= e2
->src
;
1309 /* Nothing to do if we reach ENTRY, or a common source block. */
1310 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1315 /* Seeing more than 1 forwarder blocks would confuse us later... */
1316 if (FORWARDER_BLOCK_P (e1
->dest
)
1317 && FORWARDER_BLOCK_P (e1
->dest
->succ
->dest
))
1320 if (FORWARDER_BLOCK_P (e2
->dest
)
1321 && FORWARDER_BLOCK_P (e2
->dest
->succ
->dest
))
1324 /* Likewise with dead code (possibly newly created by the other optimizations
1326 if (!src1
->pred
|| !src2
->pred
)
1329 /* Look for the common insn sequence, part the first ... */
1330 if (!outgoing_edges_match (mode
, src1
, src2
))
1333 /* ... and part the second. */
1334 nmatch
= flow_find_cross_jump (mode
, src1
, src2
, &newpos1
, &newpos2
);
1338 /* Avoid splitting if possible. */
1339 if (newpos2
== src2
->head
)
1344 fprintf (rtl_dump_file
, "Splitting bb %i before %i insns\n",
1345 src2
->index
, nmatch
);
1346 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
1350 fprintf (rtl_dump_file
,
1351 "Cross jumping from bb %i to bb %i; %i common insns\n",
1352 src1
->index
, src2
->index
, nmatch
);
1354 redirect_to
->count
+= src1
->count
;
1355 redirect_to
->frequency
+= src1
->frequency
;
1356 /* We may have some registers visible trought the block. */
1357 redirect_to
->flags
|= BB_DIRTY
;
1359 /* Recompute the frequencies and counts of outgoing edges. */
1360 for (s
= redirect_to
->succ
; s
; s
= s
->succ_next
)
1363 basic_block d
= s
->dest
;
1365 if (FORWARDER_BLOCK_P (d
))
1368 for (s2
= src1
->succ
; ; s2
= s2
->succ_next
)
1370 basic_block d2
= s2
->dest
;
1371 if (FORWARDER_BLOCK_P (d2
))
1372 d2
= d2
->succ
->dest
;
1377 s
->count
+= s2
->count
;
1379 /* Take care to update possible forwarder blocks. We verified
1380 that there is no more than one in the chain, so we can't run
1381 into infinite loop. */
1382 if (FORWARDER_BLOCK_P (s
->dest
))
1384 s
->dest
->succ
->count
+= s2
->count
;
1385 s
->dest
->count
+= s2
->count
;
1386 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
1389 if (FORWARDER_BLOCK_P (s2
->dest
))
1391 s2
->dest
->succ
->count
-= s2
->count
;
1392 if (s2
->dest
->succ
->count
< 0)
1393 s2
->dest
->succ
->count
= 0;
1394 s2
->dest
->count
-= s2
->count
;
1395 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
1396 if (s2
->dest
->frequency
< 0)
1397 s2
->dest
->frequency
= 0;
1398 if (s2
->dest
->count
< 0)
1399 s2
->dest
->count
= 0;
1402 if (!redirect_to
->frequency
&& !src1
->frequency
)
1403 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
1406 = ((s
->probability
* redirect_to
->frequency
+
1407 s2
->probability
* src1
->frequency
)
1408 / (redirect_to
->frequency
+ src1
->frequency
));
1411 update_br_prob_note (redirect_to
);
1413 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1415 /* Skip possible basic block header. */
1416 if (GET_CODE (newpos1
) == CODE_LABEL
)
1417 newpos1
= NEXT_INSN (newpos1
);
1419 if (GET_CODE (newpos1
) == NOTE
)
1420 newpos1
= NEXT_INSN (newpos1
);
1423 /* Emit the jump insn. */
1424 label
= block_label (redirect_to
);
1425 emit_jump_insn_after (gen_jump (label
), src1
->end
);
1426 JUMP_LABEL (src1
->end
) = label
;
1427 LABEL_NUSES (label
)++;
1429 /* Delete the now unreachable instructions. */
1430 delete_insn_chain (newpos1
, last
);
1432 /* Make sure there is a barrier after the new jump. */
1433 last
= next_nonnote_insn (src1
->end
);
1434 if (!last
|| GET_CODE (last
) != BARRIER
)
1435 emit_barrier_after (src1
->end
);
1439 remove_edge (src1
->succ
);
1440 make_single_succ_edge (src1
, redirect_to
, 0);
1442 update_forwarder_flag (src1
);
1447 /* Search the predecessors of BB for common insn sequences. When found,
1448 share code between them by redirecting control flow. Return true if
1449 any changes made. */
1452 try_crossjump_bb (mode
, bb
)
1456 edge e
, e2
, nexte2
, nexte
, fallthru
;
1459 /* Nothing to do if there is not at least two incoming edges. */
1460 if (!bb
->pred
|| !bb
->pred
->pred_next
)
1463 /* It is always cheapest to redirect a block that ends in a branch to
1464 a block that falls through into BB, as that adds no branches to the
1465 program. We'll try that combination first. */
1466 for (fallthru
= bb
->pred
; fallthru
; fallthru
= fallthru
->pred_next
)
1467 if (fallthru
->flags
& EDGE_FALLTHRU
)
1471 for (e
= bb
->pred
; e
; e
= nexte
)
1473 nexte
= e
->pred_next
;
1475 /* As noted above, first try with the fallthru predecessor. */
1478 /* Don't combine the fallthru edge into anything else.
1479 If there is a match, we'll do it the other way around. */
1483 if (try_crossjump_to_edge (mode
, e
, fallthru
))
1491 /* Non-obvious work limiting check: Recognize that we're going
1492 to call try_crossjump_bb on every basic block. So if we have
1493 two blocks with lots of outgoing edges (a switch) and they
1494 share lots of common destinations, then we would do the
1495 cross-jump check once for each common destination.
1497 Now, if the blocks actually are cross-jump candidates, then
1498 all of their destinations will be shared. Which means that
1499 we only need check them for cross-jump candidacy once. We
1500 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1501 choosing to do the check from the block for which the edge
1502 in question is the first successor of A. */
1503 if (e
->src
->succ
!= e
)
1506 for (e2
= bb
->pred
; e2
; e2
= nexte2
)
1508 nexte2
= e2
->pred_next
;
1513 /* We've already checked the fallthru edge above. */
1517 /* The "first successor" check above only prevents multiple
1518 checks of crossjump(A,B). In order to prevent redundant
1519 checks of crossjump(B,A), require that A be the block
1520 with the lowest index. */
1521 if (e
->src
->index
> e2
->src
->index
)
1524 if (try_crossjump_to_edge (mode
, e
, e2
))
1536 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1537 instructions etc. Return nonzero if changes were made. */
1540 try_optimize_cfg (mode
)
1544 bool changed_overall
= false;
1548 if (mode
& CLEANUP_CROSSJUMP
)
1549 add_noreturn_fake_exit_edges ();
1551 for (i
= 0; i
< n_basic_blocks
; i
++)
1552 update_forwarder_flag (BASIC_BLOCK (i
));
1554 if (mode
& CLEANUP_UPDATE_LIFE
)
1557 if (! (* targetm
.cannot_modify_jumps_p
) ())
1559 /* Attempt to merge blocks as made possible by edge removal. If
1560 a block has only one successor, and the successor has only
1561 one predecessor, they may be combined. */
1568 fprintf (rtl_dump_file
,
1569 "\n\ntry_optimize_cfg iteration %i\n\n",
1572 for (i
= 0; i
< n_basic_blocks
;)
1574 basic_block c
, b
= BASIC_BLOCK (i
);
1576 bool changed_here
= false;
1578 /* Delete trivially dead basic blocks. */
1579 while (b
->pred
== NULL
)
1581 c
= BASIC_BLOCK (b
->index
- 1);
1583 fprintf (rtl_dump_file
, "Deleting block %i.\n",
1586 flow_delete_block (b
);
1591 /* Remove code labels no longer used. Don't do this
1592 before CALL_PLACEHOLDER is removed, as some branches
1593 may be hidden within. */
1594 if (b
->pred
->pred_next
== NULL
1595 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1596 && !(b
->pred
->flags
& EDGE_COMPLEX
)
1597 && GET_CODE (b
->head
) == CODE_LABEL
1598 && (!(mode
& CLEANUP_PRE_SIBCALL
)
1599 || !tail_recursion_label_p (b
->head
))
1600 /* If the previous block ends with a branch to this
1601 block, we can't delete the label. Normally this
1602 is a condjump that is yet to be simplified, but
1603 if CASE_DROPS_THRU, this can be a tablejump with
1604 some element going to the same place as the
1605 default (fallthru). */
1606 && (b
->pred
->src
== ENTRY_BLOCK_PTR
1607 || GET_CODE (b
->pred
->src
->end
) != JUMP_INSN
1608 || ! label_is_jump_target_p (b
->head
,
1609 b
->pred
->src
->end
)))
1611 rtx label
= b
->head
;
1613 b
->head
= NEXT_INSN (b
->head
);
1614 delete_insn_chain (label
, label
);
1616 fprintf (rtl_dump_file
, "Deleted label in block %i.\n",
1620 /* If we fall through an empty block, we can remove it. */
1621 if (b
->pred
->pred_next
== NULL
1622 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1623 && GET_CODE (b
->head
) != CODE_LABEL
1624 && FORWARDER_BLOCK_P (b
)
1625 /* Note that forwarder_block_p true ensures that
1626 there is a successor for this block. */
1627 && (b
->succ
->flags
& EDGE_FALLTHRU
)
1628 && n_basic_blocks
> 1)
1631 fprintf (rtl_dump_file
,
1632 "Deleting fallthru block %i.\n",
1635 c
= BASIC_BLOCK (b
->index
? b
->index
- 1 : 1);
1636 redirect_edge_succ_nodup (b
->pred
, b
->succ
->dest
);
1637 flow_delete_block (b
);
1642 /* Merge blocks. Loop because chains of blocks might be
1644 while ((s
= b
->succ
) != NULL
1645 && s
->succ_next
== NULL
1646 && !(s
->flags
& EDGE_COMPLEX
)
1647 && (c
= s
->dest
) != EXIT_BLOCK_PTR
1648 && c
->pred
->pred_next
== NULL
1649 /* If the jump insn has side effects,
1650 we can't kill the edge. */
1651 && (GET_CODE (b
->end
) != JUMP_INSN
1652 || onlyjump_p (b
->end
))
1653 && merge_blocks (s
, b
, c
, mode
))
1654 changed_here
= true;
1656 /* Simplify branch over branch. */
1657 if ((mode
& CLEANUP_EXPENSIVE
) && try_simplify_condjump (b
))
1658 changed_here
= true;
1660 /* If B has a single outgoing edge, but uses a
1661 non-trivial jump instruction without side-effects, we
1662 can either delete the jump entirely, or replace it
1663 with a simple unconditional jump. Use
1664 redirect_edge_and_branch to do the dirty work. */
1666 && ! b
->succ
->succ_next
1667 && b
->succ
->dest
!= EXIT_BLOCK_PTR
1668 && onlyjump_p (b
->end
)
1669 && redirect_edge_and_branch (b
->succ
, b
->succ
->dest
))
1671 update_forwarder_flag (b
);
1672 changed_here
= true;
1675 /* Simplify branch to branch. */
1676 if (try_forward_edges (mode
, b
))
1677 changed_here
= true;
1679 /* Look for shared code between blocks. */
1680 if ((mode
& CLEANUP_CROSSJUMP
)
1681 && try_crossjump_bb (mode
, b
))
1682 changed_here
= true;
1684 /* Don't get confused by the index shift caused by
1692 if ((mode
& CLEANUP_CROSSJUMP
)
1693 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
1696 #ifdef ENABLE_CHECKING
1698 verify_flow_info ();
1701 changed_overall
|= changed
;
1706 if (mode
& CLEANUP_CROSSJUMP
)
1707 remove_fake_edges ();
1709 for (i
= 0; i
< n_basic_blocks
; i
++)
1710 BASIC_BLOCK (i
)->aux
= NULL
;
1712 return changed_overall
;
1715 /* Delete all unreachable basic blocks. */
1718 delete_unreachable_blocks ()
1721 bool changed
= false;
1723 find_unreachable_blocks ();
1725 /* Delete all unreachable basic blocks. Count down so that we
1726 don't interfere with the block renumbering that happens in
1727 flow_delete_block. */
1729 for (i
= n_basic_blocks
- 1; i
>= 0; --i
)
1731 basic_block b
= BASIC_BLOCK (i
);
1733 if (!(b
->flags
& BB_REACHABLE
))
1734 flow_delete_block (b
), changed
= true;
1738 tidy_fallthru_edges ();
1742 /* Tidy the CFG by deleting unreachable code and whatnot. */
1748 bool changed
= false;
1750 timevar_push (TV_CLEANUP_CFG
);
1751 if (delete_unreachable_blocks ())
1754 /* We've possibly created trivially dead code. Cleanup it right
1755 now to introduce more oppurtunities for try_optimize_cfg. */
1756 if (!(mode
& (CLEANUP_UPDATE_LIFE
| CLEANUP_PRE_SIBCALL
))
1757 && !reload_completed
)
1758 delete_trivially_dead_insns (get_insns(), max_reg_num ());
1760 while (try_optimize_cfg (mode
))
1762 delete_unreachable_blocks (), changed
= true;
1763 if (mode
& CLEANUP_UPDATE_LIFE
)
1765 /* Cleaning up CFG introduces more oppurtunities for dead code
1766 removal that in turn may introduce more oppurtunities for
1767 cleaning up the CFG. */
1768 if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL
,
1770 | PROP_SCAN_DEAD_CODE
1771 | PROP_KILL_DEAD_CODE
1775 else if (!(mode
& CLEANUP_PRE_SIBCALL
) && !reload_completed
)
1777 if (!delete_trivially_dead_insns (get_insns(), max_reg_num ()))
1782 delete_dead_jumptables ();
1785 /* Kill the data we won't maintain. */
1786 free_EXPR_LIST_list (&label_value_list
);
1787 free_EXPR_LIST_list (&tail_recursion_label_list
);
1788 timevar_pop (TV_CLEANUP_CFG
);