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"
50 /* cleanup_cfg maintains following flags for each basic block. */
54 /* Set if life info needs to be recomputed for given BB. */
56 /* Set if BB is the forwarder block to avoid too many
57 forwarder_block_p calls. */
58 BB_FORWARDER_BLOCK
= 2
61 #define BB_FLAGS(BB) (enum bb_flags) (BB)->aux
62 #define BB_SET_FLAG(BB, FLAG) \
63 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux | (FLAG))
64 #define BB_CLEAR_FLAG(BB, FLAG) \
65 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux & ~(FLAG))
67 #define FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK)
69 static bool try_crossjump_to_edge
PARAMS ((int, edge
, edge
));
70 static bool try_crossjump_bb
PARAMS ((int, basic_block
));
71 static bool outgoing_edges_match
PARAMS ((int,
72 basic_block
, basic_block
));
73 static int flow_find_cross_jump
PARAMS ((int, basic_block
, basic_block
,
75 static bool insns_match_p
PARAMS ((int, rtx
, rtx
));
77 static bool delete_unreachable_blocks
PARAMS ((void));
78 static bool label_is_jump_target_p
PARAMS ((rtx
, rtx
));
79 static bool tail_recursion_label_p
PARAMS ((rtx
));
80 static void merge_blocks_move_predecessor_nojumps
PARAMS ((basic_block
,
82 static void merge_blocks_move_successor_nojumps
PARAMS ((basic_block
,
84 static bool merge_blocks
PARAMS ((edge
,basic_block
,basic_block
,
86 static bool try_optimize_cfg
PARAMS ((int));
87 static bool try_simplify_condjump
PARAMS ((basic_block
));
88 static bool try_forward_edges
PARAMS ((int, basic_block
));
89 static edge thread_jump
PARAMS ((int, edge
, basic_block
));
90 static bool mark_effect
PARAMS ((rtx
, bitmap
));
91 static void notice_new_block
PARAMS ((basic_block
));
92 static void update_forwarder_flag
PARAMS ((basic_block
));
94 /* Set flags for newly created block. */
103 BB_SET_FLAG (bb
, BB_UPDATE_LIFE
);
104 if (forwarder_block_p (bb
))
105 BB_SET_FLAG (bb
, BB_FORWARDER_BLOCK
);
108 /* Recompute forwarder flag after block has been modified. */
111 update_forwarder_flag (bb
)
114 if (forwarder_block_p (bb
))
115 BB_SET_FLAG (bb
, BB_FORWARDER_BLOCK
);
117 BB_CLEAR_FLAG (bb
, BB_FORWARDER_BLOCK
);
120 /* Simplify a conditional jump around an unconditional jump.
121 Return true if something changed. */
124 try_simplify_condjump (cbranch_block
)
125 basic_block cbranch_block
;
127 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
128 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
131 /* Verify that there are exactly two successors. */
132 if (!cbranch_block
->succ
133 || !cbranch_block
->succ
->succ_next
134 || cbranch_block
->succ
->succ_next
->succ_next
)
137 /* Verify that we've got a normal conditional branch at the end
139 cbranch_insn
= cbranch_block
->end
;
140 if (!any_condjump_p (cbranch_insn
))
143 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
144 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
146 /* The next block must not have multiple predecessors, must not
147 be the last block in the function, and must contain just the
148 unconditional jump. */
149 jump_block
= cbranch_fallthru_edge
->dest
;
150 if (jump_block
->pred
->pred_next
151 || jump_block
->index
== n_basic_blocks
- 1
152 || !FORWARDER_BLOCK_P (jump_block
))
154 jump_dest_block
= jump_block
->succ
->dest
;
156 /* The conditional branch must target the block after the
157 unconditional branch. */
158 cbranch_dest_block
= cbranch_jump_edge
->dest
;
160 if (!can_fallthru (jump_block
, cbranch_dest_block
))
163 /* Invert the conditional branch. */
164 if (!invert_jump (cbranch_insn
, block_label (jump_dest_block
), 0))
168 fprintf (rtl_dump_file
, "Simplifying condjump %i around jump %i\n",
169 INSN_UID (cbranch_insn
), INSN_UID (jump_block
->end
));
171 /* Success. Update the CFG to match. Note that after this point
172 the edge variable names appear backwards; the redirection is done
173 this way to preserve edge profile data. */
174 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
176 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
178 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
179 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
180 update_br_prob_note (cbranch_block
);
182 /* Delete the block with the unconditional jump, and clean up the mess. */
183 flow_delete_block (jump_block
);
184 tidy_fallthru_edge (cbranch_jump_edge
, cbranch_block
, cbranch_dest_block
);
189 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
190 on register. Used by jump threading. */
193 mark_effect (exp
, nonequal
)
199 switch (GET_CODE (exp
))
201 /* In case we do clobber the register, mark it as equal, as we know the
202 value is dead so it don't have to match. */
204 if (REG_P (XEXP (exp
, 0)))
206 dest
= XEXP (exp
, 0);
207 regno
= REGNO (dest
);
208 CLEAR_REGNO_REG_SET (nonequal
, regno
);
209 if (regno
< FIRST_PSEUDO_REGISTER
)
211 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
213 CLEAR_REGNO_REG_SET (nonequal
, regno
+ n
);
219 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
221 dest
= SET_DEST (exp
);
226 regno
= REGNO (dest
);
227 SET_REGNO_REG_SET (nonequal
, regno
);
228 if (regno
< FIRST_PSEUDO_REGISTER
)
230 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
232 SET_REGNO_REG_SET (nonequal
, regno
+ n
);
240 /* Attempt to prove that the basic block B will have no side effects and
241 allways continues in the same edge if reached via E. Return the edge
242 if exist, NULL otherwise. */
245 thread_jump (mode
, e
, b
)
250 rtx set1
, set2
, cond1
, cond2
, insn
;
251 enum rtx_code code1
, code2
, reversed_code2
;
252 bool reverse1
= false;
257 /* At the moment, we do handle only conditional jumps, but later we may
258 want to extend this code to tablejumps and others. */
259 if (!e
->src
->succ
->succ_next
|| e
->src
->succ
->succ_next
->succ_next
)
261 if (!b
->succ
|| !b
->succ
->succ_next
|| b
->succ
->succ_next
->succ_next
)
264 /* Second branch must end with onlyjump, as we will eliminate the jump. */
265 if (!any_condjump_p (e
->src
->end
) || !any_condjump_p (b
->end
)
266 || !onlyjump_p (b
->end
))
269 set1
= pc_set (e
->src
->end
);
270 set2
= pc_set (b
->end
);
271 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
272 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
275 cond1
= XEXP (SET_SRC (set1
), 0);
276 cond2
= XEXP (SET_SRC (set2
), 0);
278 code1
= reversed_comparison_code (cond1
, e
->src
->end
);
280 code1
= GET_CODE (cond1
);
282 code2
= GET_CODE (cond2
);
283 reversed_code2
= reversed_comparison_code (cond2
, b
->end
);
285 if (!comparison_dominates_p (code1
, code2
)
286 && !comparison_dominates_p (code1
, reversed_code2
))
289 /* Ensure that the comparison operators are equivalent.
290 ??? This is far too pesimistic. We should allow swapped operands,
291 different CCmodes, or for example comparisons for interval, that
292 dominate even when operands are not equivalent. */
293 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
294 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
297 /* Short circuit cases where block B contains some side effects, as we can't
299 for (insn
= NEXT_INSN (b
->head
); insn
!= NEXT_INSN (b
->end
);
300 insn
= NEXT_INSN (insn
))
301 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
306 /* First process all values computed in the source basic block. */
307 for (insn
= NEXT_INSN (e
->src
->head
); insn
!= NEXT_INSN (e
->src
->end
);
308 insn
= NEXT_INSN (insn
))
310 cselib_process_insn (insn
);
312 nonequal
= BITMAP_XMALLOC();
313 CLEAR_REG_SET (nonequal
);
315 /* Now assume that we've continued by the edge E to B and continue
316 processing as if it were same basic block.
317 Our goal is to prove that whole block is an NOOP. */
319 for (insn
= NEXT_INSN (b
->head
); insn
!= NEXT_INSN (b
->end
) && !failed
;
320 insn
= NEXT_INSN (insn
))
324 rtx pat
= PATTERN (insn
);
326 if (GET_CODE (pat
) == PARALLEL
)
328 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
329 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
332 failed
|= mark_effect (pat
, nonequal
);
335 cselib_process_insn (insn
);
338 /* Later we should clear nonequal of dead registers. So far we don't
339 have life information in cfg_cleanup. */
343 /* In case liveness information is available, we need to prove equivalence
344 only of the live values. */
345 if (mode
& CLEANUP_UPDATE_LIFE
)
346 AND_REG_SET (nonequal
, b
->global_live_at_end
);
348 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, goto failed_exit
;);
350 BITMAP_XFREE (nonequal
);
352 if ((comparison_dominates_p (code1
, code2
) != 0)
353 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
354 return BRANCH_EDGE (b
);
356 return FALLTHRU_EDGE (b
);
359 BITMAP_XFREE (nonequal
);
364 /* Attempt to forward edges leaving basic block B.
365 Return true if successful. */
368 try_forward_edges (mode
, b
)
372 bool changed
= false;
373 edge e
, next
, *threaded_edges
= NULL
;
375 for (e
= b
->succ
; e
; e
= next
)
377 basic_block target
, first
;
379 bool threaded
= false;
380 int nthreaded_edges
= 0;
384 /* Skip complex edges because we don't know how to update them.
386 Still handle fallthru edges, as we can succeed to forward fallthru
387 edge to the same place as the branch edge of conditional branch
388 and turn conditional branch to an unconditional branch. */
389 if (e
->flags
& EDGE_COMPLEX
)
392 target
= first
= e
->dest
;
395 while (counter
< n_basic_blocks
)
397 basic_block new_target
= NULL
;
398 bool new_target_threaded
= false;
400 if (FORWARDER_BLOCK_P (target
)
401 && target
->succ
->dest
!= EXIT_BLOCK_PTR
)
403 /* Bypass trivial infinite loops. */
404 if (target
== target
->succ
->dest
)
405 counter
= n_basic_blocks
;
406 new_target
= target
->succ
->dest
;
409 /* Allow to thread only over one edge at time to simplify updating
411 else if (mode
& CLEANUP_THREADING
)
413 edge t
= thread_jump (mode
, e
, target
);
417 threaded_edges
= xmalloc (sizeof (*threaded_edges
)
423 /* Detect an infinite loop across blocks not
424 including the start block. */
425 for (i
= 0; i
< nthreaded_edges
; ++i
)
426 if (threaded_edges
[i
] == t
)
428 if (i
< nthreaded_edges
)
430 counter
= n_basic_blocks
;
435 /* Detect an infinite loop across the start block. */
439 if (nthreaded_edges
>= n_basic_blocks
)
441 threaded_edges
[nthreaded_edges
++] = t
;
443 new_target
= t
->dest
;
444 new_target_threaded
= true;
451 /* Avoid killing of loop pre-headers, as it is the place loop
452 optimizer wants to hoist code to.
454 For fallthru forwarders, the LOOP_BEG note must appear between
455 the header of block and CODE_LABEL of the loop, for non forwarders
456 it must appear before the JUMP_INSN. */
457 if (mode
& CLEANUP_PRE_LOOP
)
459 rtx insn
= (target
->succ
->flags
& EDGE_FALLTHRU
460 ? target
->head
: prev_nonnote_insn (target
->end
));
462 if (GET_CODE (insn
) != NOTE
)
463 insn
= NEXT_INSN (insn
);
465 for (; insn
&& GET_CODE (insn
) != CODE_LABEL
&& !INSN_P (insn
);
466 insn
= NEXT_INSN (insn
))
467 if (GET_CODE (insn
) == NOTE
468 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
471 if (GET_CODE (insn
) == NOTE
)
477 threaded
|= new_target_threaded
;
480 if (counter
>= n_basic_blocks
)
483 fprintf (rtl_dump_file
, "Infinite loop in BB %i.\n",
486 else if (target
== first
)
487 ; /* We didn't do anything. */
490 /* Save the values now, as the edge may get removed. */
491 gcov_type edge_count
= e
->count
;
492 int edge_probability
= e
->probability
;
496 /* Don't force if target is exit block. */
497 if (threaded
&& target
!= EXIT_BLOCK_PTR
)
499 notice_new_block (redirect_edge_and_branch_force (e
, target
));
501 fprintf (rtl_dump_file
, "Conditionals threaded.\n");
503 else if (!redirect_edge_and_branch (e
, target
))
506 fprintf (rtl_dump_file
,
507 "Forwarding edge %i->%i to %i failed.\n",
508 b
->index
, e
->dest
->index
, target
->index
);
512 /* We successfully forwarded the edge. Now update profile
513 data: for each edge we traversed in the chain, remove
514 the original edge's execution count. */
515 edge_frequency
= ((edge_probability
* b
->frequency
516 + REG_BR_PROB_BASE
/ 2)
519 if (!FORWARDER_BLOCK_P (b
) && forwarder_block_p (b
))
520 BB_SET_FLAG (b
, BB_FORWARDER_BLOCK
);
521 BB_SET_FLAG (b
, BB_UPDATE_LIFE
);
527 first
->count
-= edge_count
;
528 if (first
->count
< 0)
530 first
->frequency
-= edge_frequency
;
531 if (first
->frequency
< 0)
532 first
->frequency
= 0;
533 if (first
->succ
->succ_next
)
537 if (n
>= nthreaded_edges
)
539 t
= threaded_edges
[n
++];
542 if (first
->frequency
)
543 prob
= edge_frequency
* REG_BR_PROB_BASE
/ first
->frequency
;
546 if (prob
> t
->probability
)
547 prob
= t
->probability
;
548 t
->probability
-= prob
;
549 prob
= REG_BR_PROB_BASE
- prob
;
552 first
->succ
->probability
= REG_BR_PROB_BASE
;
553 first
->succ
->succ_next
->probability
= 0;
556 for (e
= first
->succ
; e
; e
= e
->succ_next
)
557 e
->probability
= ((e
->probability
* REG_BR_PROB_BASE
)
559 update_br_prob_note (first
);
563 /* It is possible that as the result of
564 threading we've removed edge as it is
565 threaded to the fallthru edge. Avoid
566 getting out of sync. */
567 if (n
< nthreaded_edges
568 && first
== threaded_edges
[n
]->src
)
573 t
->count
-= edge_count
;
578 while (first
!= target
);
585 free (threaded_edges
);
589 /* Return true if LABEL is a target of JUMP_INSN. This applies only
590 to non-complex jumps. That is, direct unconditional, conditional,
591 and tablejumps, but not computed jumps or returns. It also does
592 not apply to the fallthru case of a conditional jump. */
595 label_is_jump_target_p (label
, jump_insn
)
596 rtx label
, jump_insn
;
598 rtx tmp
= JUMP_LABEL (jump_insn
);
604 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
605 && GET_CODE (tmp
) == JUMP_INSN
606 && (tmp
= PATTERN (tmp
),
607 GET_CODE (tmp
) == ADDR_VEC
608 || GET_CODE (tmp
) == ADDR_DIFF_VEC
))
610 rtvec vec
= XVEC (tmp
, GET_CODE (tmp
) == ADDR_DIFF_VEC
);
611 int i
, veclen
= GET_NUM_ELEM (vec
);
613 for (i
= 0; i
< veclen
; ++i
)
614 if (XEXP (RTVEC_ELT (vec
, i
), 0) == label
)
621 /* Return true if LABEL is used for tail recursion. */
624 tail_recursion_label_p (label
)
629 for (x
= tail_recursion_label_list
; x
; x
= XEXP (x
, 1))
630 if (label
== XEXP (x
, 0))
636 /* Blocks A and B are to be merged into a single block. A has no incoming
637 fallthru edge, so it can be moved before B without adding or modifying
638 any jumps (aside from the jump from A to B). */
641 merge_blocks_move_predecessor_nojumps (a
, b
)
647 barrier
= next_nonnote_insn (a
->end
);
648 if (GET_CODE (barrier
) != BARRIER
)
650 delete_insn (barrier
);
652 /* Move block and loop notes out of the chain so that we do not
655 ??? A better solution would be to squeeze out all the non-nested notes
656 and adjust the block trees appropriately. Even better would be to have
657 a tighter connection between block trees and rtl so that this is not
659 if (squeeze_notes (&a
->head
, &a
->end
))
662 /* Scramble the insn chain. */
663 if (a
->end
!= PREV_INSN (b
->head
))
664 reorder_insns_nobb (a
->head
, a
->end
, PREV_INSN (b
->head
));
665 BB_SET_FLAG (a
, BB_UPDATE_LIFE
);
668 fprintf (rtl_dump_file
, "Moved block %d before %d and merged.\n",
671 /* Swap the records for the two blocks around. Although we are deleting B,
672 A is now where B was and we want to compact the BB array from where
674 BASIC_BLOCK (a
->index
) = b
;
675 BASIC_BLOCK (b
->index
) = a
;
680 /* Now blocks A and B are contiguous. Merge them. */
681 merge_blocks_nomove (a
, b
);
684 /* Blocks A and B are to be merged into a single block. B has no outgoing
685 fallthru edge, so it can be moved after A without adding or modifying
686 any jumps (aside from the jump from A to B). */
689 merge_blocks_move_successor_nojumps (a
, b
)
692 rtx barrier
, real_b_end
;
695 barrier
= NEXT_INSN (b
->end
);
697 /* Recognize a jump table following block B. */
699 && GET_CODE (barrier
) == CODE_LABEL
700 && NEXT_INSN (barrier
)
701 && GET_CODE (NEXT_INSN (barrier
)) == JUMP_INSN
702 && (GET_CODE (PATTERN (NEXT_INSN (barrier
))) == ADDR_VEC
703 || GET_CODE (PATTERN (NEXT_INSN (barrier
))) == ADDR_DIFF_VEC
))
705 /* Temporarily add the table jump insn to b, so that it will also
706 be moved to the correct location. */
707 b
->end
= NEXT_INSN (barrier
);
708 barrier
= NEXT_INSN (b
->end
);
711 /* There had better have been a barrier there. Delete it. */
712 if (barrier
&& GET_CODE (barrier
) == BARRIER
)
713 delete_insn (barrier
);
715 /* Move block and loop notes out of the chain so that we do not
718 ??? A better solution would be to squeeze out all the non-nested notes
719 and adjust the block trees appropriately. Even better would be to have
720 a tighter connection between block trees and rtl so that this is not
722 if (squeeze_notes (&b
->head
, &b
->end
))
725 /* Scramble the insn chain. */
726 reorder_insns_nobb (b
->head
, b
->end
, a
->end
);
728 /* Restore the real end of b. */
731 /* Now blocks A and B are contiguous. Merge them. */
732 merge_blocks_nomove (a
, b
);
733 BB_SET_FLAG (a
, BB_UPDATE_LIFE
);
736 fprintf (rtl_dump_file
, "Moved block %d after %d and merged.\n",
740 /* Attempt to merge basic blocks that are potentially non-adjacent.
741 Return true iff the attempt succeeded. */
744 merge_blocks (e
, b
, c
, mode
)
749 /* If C has a tail recursion label, do not merge. There is no
750 edge recorded from the call_placeholder back to this label, as
751 that would make optimize_sibling_and_tail_recursive_calls more
752 complex for no gain. */
753 if ((mode
& CLEANUP_PRE_SIBCALL
)
754 && GET_CODE (c
->head
) == CODE_LABEL
755 && tail_recursion_label_p (c
->head
))
758 /* If B has a fallthru edge to C, no need to move anything. */
759 if (e
->flags
& EDGE_FALLTHRU
)
761 int b_index
= b
->index
, c_index
= c
->index
;
762 /* We need to update liveness in case C already has broken liveness
763 or B ends by conditional jump to next instructions that will be
765 if ((BB_FLAGS (c
) & BB_UPDATE_LIFE
)
766 || GET_CODE (b
->end
) == JUMP_INSN
)
767 BB_SET_FLAG (b
, BB_UPDATE_LIFE
);
768 merge_blocks_nomove (b
, c
);
769 update_forwarder_flag (b
);
772 fprintf (rtl_dump_file
, "Merged %d and %d without moving.\n",
778 /* Otherwise we will need to move code around. Do that only if expensive
779 transformations are allowed. */
780 else if (mode
& CLEANUP_EXPENSIVE
)
782 edge tmp_edge
, b_fallthru_edge
;
783 bool c_has_outgoing_fallthru
;
784 bool b_has_incoming_fallthru
;
786 /* Avoid overactive code motion, as the forwarder blocks should be
787 eliminated by edge redirection instead. One exception might have
788 been if B is a forwarder block and C has no fallthru edge, but
789 that should be cleaned up by bb-reorder instead. */
790 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
793 /* We must make sure to not munge nesting of lexical blocks,
794 and loop notes. This is done by squeezing out all the notes
795 and leaving them there to lie. Not ideal, but functional. */
797 for (tmp_edge
= c
->succ
; tmp_edge
; tmp_edge
= tmp_edge
->succ_next
)
798 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
801 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
803 for (tmp_edge
= b
->pred
; tmp_edge
; tmp_edge
= tmp_edge
->pred_next
)
804 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
807 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
808 b_fallthru_edge
= tmp_edge
;
810 /* Otherwise, we're going to try to move C after B. If C does
811 not have an outgoing fallthru, then it can be moved
812 immediately after B without introducing or modifying jumps. */
813 if (! c_has_outgoing_fallthru
)
815 merge_blocks_move_successor_nojumps (b
, c
);
819 /* If B does not have an incoming fallthru, then it can be moved
820 immediately before C without introducing or modifying jumps.
821 C cannot be the first block, so we do not have to worry about
822 accessing a non-existent block. */
824 if (b_has_incoming_fallthru
)
828 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
830 bb
= force_nonfallthru (b_fallthru_edge
);
832 notice_new_block (bb
);
834 BB_SET_FLAG (b_fallthru_edge
->src
, BB_UPDATE_LIFE
);
837 merge_blocks_move_predecessor_nojumps (b
, c
);
845 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
848 insns_match_p (mode
, i1
, i2
)
849 int mode ATTRIBUTE_UNUSED
;
854 /* Verify that I1 and I2 are equivalent. */
855 if (GET_CODE (i1
) != GET_CODE (i2
))
861 if (GET_CODE (p1
) != GET_CODE (p2
))
864 /* If this is a CALL_INSN, compare register usage information.
865 If we don't check this on stack register machines, the two
866 CALL_INSNs might be merged leaving reg-stack.c with mismatching
867 numbers of stack registers in the same basic block.
868 If we don't check this on machines with delay slots, a delay slot may
869 be filled that clobbers a parameter expected by the subroutine.
871 ??? We take the simple route for now and assume that if they're
872 equal, they were constructed identically. */
874 if (GET_CODE (i1
) == CALL_INSN
875 && !rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
876 CALL_INSN_FUNCTION_USAGE (i2
)))
880 /* If cross_jump_death_matters is not 0, the insn's mode
881 indicates whether or not the insn contains any stack-like
884 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
886 /* If register stack conversion has already been done, then
887 death notes must also be compared before it is certain that
888 the two instruction streams match. */
891 HARD_REG_SET i1_regset
, i2_regset
;
893 CLEAR_HARD_REG_SET (i1_regset
);
894 CLEAR_HARD_REG_SET (i2_regset
);
896 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
897 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
898 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
900 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
901 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
902 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
904 GO_IF_HARD_REG_EQUAL (i1_regset
, i2_regset
, done
);
914 ? ! rtx_renumbered_equal_p (p1
, p2
) : ! rtx_equal_p (p1
, p2
))
916 /* The following code helps take care of G++ cleanups. */
917 rtx equiv1
= find_reg_equal_equiv_note (i1
);
918 rtx equiv2
= find_reg_equal_equiv_note (i2
);
921 /* If the equivalences are not to a constant, they may
922 reference pseudos that no longer exist, so we can't
924 && (! reload_completed
925 || (CONSTANT_P (XEXP (equiv1
, 0))
926 && rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))))
928 rtx s1
= single_set (i1
);
929 rtx s2
= single_set (i2
);
930 if (s1
!= 0 && s2
!= 0
931 && rtx_renumbered_equal_p (SET_DEST (s1
), SET_DEST (s2
)))
933 validate_change (i1
, &SET_SRC (s1
), XEXP (equiv1
, 0), 1);
934 validate_change (i2
, &SET_SRC (s2
), XEXP (equiv2
, 0), 1);
935 if (! rtx_renumbered_equal_p (p1
, p2
))
937 else if (apply_change_group ())
948 /* Look through the insns at the end of BB1 and BB2 and find the longest
949 sequence that are equivalent. Store the first insns for that sequence
950 in *F1 and *F2 and return the sequence length.
952 To simplify callers of this function, if the blocks match exactly,
953 store the head of the blocks in *F1 and *F2. */
956 flow_find_cross_jump (mode
, bb1
, bb2
, f1
, f2
)
957 int mode ATTRIBUTE_UNUSED
;
958 basic_block bb1
, bb2
;
961 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
964 /* Skip simple jumps at the end of the blocks. Complex jumps still
965 need to be compared for equivalence, which we'll do below. */
968 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
970 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
978 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
981 /* Count everything except for unconditional jump as insn. */
982 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
990 while (!active_insn_p (i1
) && i1
!= bb1
->head
)
993 while (!active_insn_p (i2
) && i2
!= bb2
->head
)
996 if (i1
== bb1
->head
|| i2
== bb2
->head
)
999 if (!insns_match_p (mode
, i1
, i2
))
1002 /* Don't begin a cross-jump with a USE or CLOBBER insn. */
1003 if (active_insn_p (i1
))
1005 /* If the merged insns have different REG_EQUAL notes, then
1007 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1008 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1010 if (equiv1
&& !equiv2
)
1011 remove_note (i1
, equiv1
);
1012 else if (!equiv1
&& equiv2
)
1013 remove_note (i2
, equiv2
);
1014 else if (equiv1
&& equiv2
1015 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1017 remove_note (i1
, equiv1
);
1018 remove_note (i2
, equiv2
);
1021 afterlast1
= last1
, afterlast2
= last2
;
1022 last1
= i1
, last2
= i2
;
1026 i1
= PREV_INSN (i1
);
1027 i2
= PREV_INSN (i2
);
1031 /* Don't allow the insn after a compare to be shared by
1032 cross-jumping unless the compare is also shared. */
1033 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1034 last1
= afterlast1
, last2
= afterlast2
, ninsns
--;
1037 /* Include preceding notes and labels in the cross-jump. One,
1038 this may bring us to the head of the blocks as requested above.
1039 Two, it keeps line number notes as matched as may be. */
1042 while (last1
!= bb1
->head
&& !active_insn_p (PREV_INSN (last1
)))
1043 last1
= PREV_INSN (last1
);
1045 if (last1
!= bb1
->head
&& GET_CODE (PREV_INSN (last1
)) == CODE_LABEL
)
1046 last1
= PREV_INSN (last1
);
1048 while (last2
!= bb2
->head
&& !active_insn_p (PREV_INSN (last2
)))
1049 last2
= PREV_INSN (last2
);
1051 if (last2
!= bb2
->head
&& GET_CODE (PREV_INSN (last2
)) == CODE_LABEL
)
1052 last2
= PREV_INSN (last2
);
1061 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1062 the branch instruction. This means that if we commonize the control
1063 flow before end of the basic block, the semantic remains unchanged.
1065 We may assume that there exists one edge with a common destination. */
1068 outgoing_edges_match (mode
, bb1
, bb2
)
1073 int nehedges1
= 0, nehedges2
= 0;
1074 edge fallthru1
= 0, fallthru2
= 0;
1077 /* If BB1 has only one successor, we may be looking at either an
1078 unconditional jump, or a fake edge to exit. */
1079 if (bb1
->succ
&& !bb1
->succ
->succ_next
1080 && !(bb1
->succ
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
1081 return (bb2
->succ
&& !bb2
->succ
->succ_next
1082 && (bb2
->succ
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0);
1084 /* Match conditional jumps - this may get tricky when fallthru and branch
1085 edges are crossed. */
1087 && bb1
->succ
->succ_next
1088 && !bb1
->succ
->succ_next
->succ_next
1089 && any_condjump_p (bb1
->end
)
1090 && onlyjump_p (bb1
->end
))
1092 edge b1
, f1
, b2
, f2
;
1093 bool reverse
, match
;
1094 rtx set1
, set2
, cond1
, cond2
;
1095 enum rtx_code code1
, code2
;
1098 || !bb2
->succ
->succ_next
1099 || bb1
->succ
->succ_next
->succ_next
1100 || !any_condjump_p (bb2
->end
)
1101 || !onlyjump_p (bb1
->end
))
1104 b1
= BRANCH_EDGE (bb1
);
1105 b2
= BRANCH_EDGE (bb2
);
1106 f1
= FALLTHRU_EDGE (bb1
);
1107 f2
= FALLTHRU_EDGE (bb2
);
1109 /* Get around possible forwarders on fallthru edges. Other cases
1110 should be optimized out already. */
1111 if (FORWARDER_BLOCK_P (f1
->dest
))
1112 f1
= f1
->dest
->succ
;
1114 if (FORWARDER_BLOCK_P (f2
->dest
))
1115 f2
= f2
->dest
->succ
;
1117 /* To simplify use of this function, return false if there are
1118 unneeded forwarder blocks. These will get eliminated later
1119 during cleanup_cfg. */
1120 if (FORWARDER_BLOCK_P (f1
->dest
)
1121 || FORWARDER_BLOCK_P (f2
->dest
)
1122 || FORWARDER_BLOCK_P (b1
->dest
)
1123 || FORWARDER_BLOCK_P (b2
->dest
))
1126 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1128 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1133 set1
= pc_set (bb1
->end
);
1134 set2
= pc_set (bb2
->end
);
1135 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1136 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1139 cond1
= XEXP (SET_SRC (set1
), 0);
1140 cond2
= XEXP (SET_SRC (set2
), 0);
1141 code1
= GET_CODE (cond1
);
1143 code2
= reversed_comparison_code (cond2
, bb2
->end
);
1145 code2
= GET_CODE (cond2
);
1147 if (code2
== UNKNOWN
)
1150 /* Verify codes and operands match. */
1151 match
= ((code1
== code2
1152 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1153 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1154 || (code1
== swap_condition (code2
)
1155 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1157 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1160 /* If we return true, we will join the blocks. Which means that
1161 we will only have one branch prediction bit to work with. Thus
1162 we require the existing branches to have probabilities that are
1166 && bb1
->frequency
> BB_FREQ_MAX
/ 1000
1167 && bb2
->frequency
> BB_FREQ_MAX
/ 1000)
1171 if (b1
->dest
== b2
->dest
)
1172 prob2
= b2
->probability
;
1174 /* Do not use f2 probability as f2 may be forwarded. */
1175 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1177 /* Fail if the difference in probabilities is
1179 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 20)
1182 fprintf (rtl_dump_file
,
1183 "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
1184 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1190 if (rtl_dump_file
&& match
)
1191 fprintf (rtl_dump_file
, "Conditionals in bb %i and %i match.\n",
1192 bb1
->index
, bb2
->index
);
1197 /* Generic case - we are seeing an computed jump, table jump or trapping
1200 /* First ensure that the instructions match. There may be many outgoing
1201 edges so this test is generally cheaper.
1202 ??? Currently the tablejumps will never match, as they do have
1203 different tables. */
1204 if (!insns_match_p (mode
, bb1
->end
, bb2
->end
))
1207 /* Search the outgoing edges, ensure that the counts do match, find possible
1208 fallthru and exception handling edges since these needs more
1210 for (e1
= bb1
->succ
, e2
= bb2
->succ
; e1
&& e2
;
1211 e1
= e1
->succ_next
, e2
= e2
->succ_next
)
1213 if (e1
->flags
& EDGE_EH
)
1216 if (e2
->flags
& EDGE_EH
)
1219 if (e1
->flags
& EDGE_FALLTHRU
)
1221 if (e2
->flags
& EDGE_FALLTHRU
)
1225 /* If number of edges of various types does not match, fail. */
1227 || nehedges1
!= nehedges2
1228 || (fallthru1
!= 0) != (fallthru2
!= 0))
1231 /* fallthru edges must be forwarded to the same destination. */
1234 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1235 ? fallthru1
->dest
->succ
->dest
: fallthru1
->dest
);
1236 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1237 ? fallthru2
->dest
->succ
->dest
: fallthru2
->dest
);
1243 /* In case we do have EH edges, ensure we are in the same region. */
1246 rtx n1
= find_reg_note (bb1
->end
, REG_EH_REGION
, 0);
1247 rtx n2
= find_reg_note (bb2
->end
, REG_EH_REGION
, 0);
1249 if (XEXP (n1
, 0) != XEXP (n2
, 0))
1253 /* We don't need to match the rest of edges as above checks should be enought
1254 to ensure that they are equivalent. */
1258 /* E1 and E2 are edges with the same destination block. Search their
1259 predecessors for common code. If found, redirect control flow from
1260 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1263 try_crossjump_to_edge (mode
, e1
, e2
)
1268 basic_block src1
= e1
->src
, src2
= e2
->src
;
1269 basic_block redirect_to
;
1270 rtx newpos1
, newpos2
;
1275 /* Search backward through forwarder blocks. We don't need to worry
1276 about multiple entry or chained forwarders, as they will be optimized
1277 away. We do this to look past the unconditional jump following a
1278 conditional jump that is required due to the current CFG shape. */
1280 && !src1
->pred
->pred_next
1281 && FORWARDER_BLOCK_P (src1
))
1282 e1
= src1
->pred
, src1
= e1
->src
;
1285 && !src2
->pred
->pred_next
1286 && FORWARDER_BLOCK_P (src2
))
1287 e2
= src2
->pred
, src2
= e2
->src
;
1289 /* Nothing to do if we reach ENTRY, or a common source block. */
1290 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1295 /* Seeing more than 1 forwarder blocks would confuse us later... */
1296 if (FORWARDER_BLOCK_P (e1
->dest
)
1297 && FORWARDER_BLOCK_P (e1
->dest
->succ
->dest
))
1300 if (FORWARDER_BLOCK_P (e2
->dest
)
1301 && FORWARDER_BLOCK_P (e2
->dest
->succ
->dest
))
1304 /* Likewise with dead code (possibly newly created by the other optimizations
1306 if (!src1
->pred
|| !src2
->pred
)
1309 /* Look for the common insn sequence, part the first ... */
1310 if (!outgoing_edges_match (mode
, src1
, src2
))
1313 /* ... and part the second. */
1314 nmatch
= flow_find_cross_jump (mode
, src1
, src2
, &newpos1
, &newpos2
);
1318 /* Avoid splitting if possible. */
1319 if (newpos2
== src2
->head
)
1324 fprintf (rtl_dump_file
, "Splitting bb %i before %i insns\n",
1325 src2
->index
, nmatch
);
1326 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
1330 fprintf (rtl_dump_file
,
1331 "Cross jumping from bb %i to bb %i; %i common insns\n",
1332 src1
->index
, src2
->index
, nmatch
);
1334 redirect_to
->count
+= src1
->count
;
1335 redirect_to
->frequency
+= src1
->frequency
;
1337 /* Recompute the frequencies and counts of outgoing edges. */
1338 for (s
= redirect_to
->succ
; s
; s
= s
->succ_next
)
1341 basic_block d
= s
->dest
;
1343 if (FORWARDER_BLOCK_P (d
))
1346 for (s2
= src1
->succ
; ; s2
= s2
->succ_next
)
1348 basic_block d2
= s2
->dest
;
1349 if (FORWARDER_BLOCK_P (d2
))
1350 d2
= d2
->succ
->dest
;
1355 s
->count
+= s2
->count
;
1357 /* Take care to update possible forwarder blocks. We verified
1358 that there is no more than one in the chain, so we can't run
1359 into infinite loop. */
1360 if (FORWARDER_BLOCK_P (s
->dest
))
1362 s
->dest
->succ
->count
+= s2
->count
;
1363 s
->dest
->count
+= s2
->count
;
1364 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
1367 if (FORWARDER_BLOCK_P (s2
->dest
))
1369 s2
->dest
->succ
->count
-= s2
->count
;
1370 if (s2
->dest
->succ
->count
< 0)
1371 s2
->dest
->succ
->count
= 0;
1372 s2
->dest
->count
-= s2
->count
;
1373 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
1374 if (s2
->dest
->frequency
< 0)
1375 s2
->dest
->frequency
= 0;
1376 if (s2
->dest
->count
< 0)
1377 s2
->dest
->count
= 0;
1380 if (!redirect_to
->frequency
&& !src1
->frequency
)
1381 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
1384 = ((s
->probability
* redirect_to
->frequency
+
1385 s2
->probability
* src1
->frequency
)
1386 / (redirect_to
->frequency
+ src1
->frequency
));
1389 update_br_prob_note (redirect_to
);
1391 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1393 /* Skip possible basic block header. */
1394 if (GET_CODE (newpos1
) == CODE_LABEL
)
1395 newpos1
= NEXT_INSN (newpos1
);
1397 if (GET_CODE (newpos1
) == NOTE
)
1398 newpos1
= NEXT_INSN (newpos1
);
1401 /* Emit the jump insn. */
1402 label
= block_label (redirect_to
);
1403 emit_jump_insn_after (gen_jump (label
), src1
->end
);
1404 JUMP_LABEL (src1
->end
) = label
;
1405 LABEL_NUSES (label
)++;
1407 /* Delete the now unreachable instructions. */
1408 delete_insn_chain (newpos1
, last
);
1410 /* Make sure there is a barrier after the new jump. */
1411 last
= next_nonnote_insn (src1
->end
);
1412 if (!last
|| GET_CODE (last
) != BARRIER
)
1413 emit_barrier_after (src1
->end
);
1417 remove_edge (src1
->succ
);
1418 make_single_succ_edge (src1
, redirect_to
, 0);
1420 BB_SET_FLAG (src1
, BB_UPDATE_LIFE
);
1421 update_forwarder_flag (src1
);
1426 /* Search the predecessors of BB for common insn sequences. When found,
1427 share code between them by redirecting control flow. Return true if
1428 any changes made. */
1431 try_crossjump_bb (mode
, bb
)
1435 edge e
, e2
, nexte2
, nexte
, fallthru
;
1438 /* Nothing to do if there is not at least two incoming edges. */
1439 if (!bb
->pred
|| !bb
->pred
->pred_next
)
1442 /* It is always cheapest to redirect a block that ends in a branch to
1443 a block that falls through into BB, as that adds no branches to the
1444 program. We'll try that combination first. */
1445 for (fallthru
= bb
->pred
; fallthru
; fallthru
= fallthru
->pred_next
)
1446 if (fallthru
->flags
& EDGE_FALLTHRU
)
1450 for (e
= bb
->pred
; e
; e
= nexte
)
1452 nexte
= e
->pred_next
;
1454 /* As noted above, first try with the fallthru predecessor. */
1457 /* Don't combine the fallthru edge into anything else.
1458 If there is a match, we'll do it the other way around. */
1462 if (try_crossjump_to_edge (mode
, e
, fallthru
))
1470 /* Non-obvious work limiting check: Recognize that we're going
1471 to call try_crossjump_bb on every basic block. So if we have
1472 two blocks with lots of outgoing edges (a switch) and they
1473 share lots of common destinations, then we would do the
1474 cross-jump check once for each common destination.
1476 Now, if the blocks actually are cross-jump candidates, then
1477 all of their destinations will be shared. Which means that
1478 we only need check them for cross-jump candidacy once. We
1479 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1480 choosing to do the check from the block for which the edge
1481 in question is the first successor of A. */
1482 if (e
->src
->succ
!= e
)
1485 for (e2
= bb
->pred
; e2
; e2
= nexte2
)
1487 nexte2
= e2
->pred_next
;
1492 /* We've already checked the fallthru edge above. */
1496 /* The "first successor" check above only prevents multiple
1497 checks of crossjump(A,B). In order to prevent redundant
1498 checks of crossjump(B,A), require that A be the block
1499 with the lowest index. */
1500 if (e
->src
->index
> e2
->src
->index
)
1503 if (try_crossjump_to_edge (mode
, e
, e2
))
1515 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1516 instructions etc. Return nonzero if changes were made. */
1519 try_optimize_cfg (mode
)
1523 bool changed_overall
= false;
1528 if (mode
& CLEANUP_CROSSJUMP
)
1529 add_noreturn_fake_exit_edges ();
1531 for (i
= 0; i
< n_basic_blocks
; i
++)
1532 update_forwarder_flag (BASIC_BLOCK (i
));
1534 /* Attempt to merge blocks as made possible by edge removal. If a block
1535 has only one successor, and the successor has only one predecessor,
1536 they may be combined. */
1543 fprintf (rtl_dump_file
, "\n\ntry_optimize_cfg iteration %i\n\n",
1546 for (i
= 0; i
< n_basic_blocks
;)
1548 basic_block c
, b
= BASIC_BLOCK (i
);
1550 bool changed_here
= false;
1552 /* Delete trivially dead basic blocks. */
1553 while (b
->pred
== NULL
)
1555 c
= BASIC_BLOCK (b
->index
- 1);
1557 fprintf (rtl_dump_file
, "Deleting block %i.\n", b
->index
);
1559 flow_delete_block (b
);
1564 /* Remove code labels no longer used. Don't do this before
1565 CALL_PLACEHOLDER is removed, as some branches may be hidden
1567 if (b
->pred
->pred_next
== NULL
1568 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1569 && !(b
->pred
->flags
& EDGE_COMPLEX
)
1570 && GET_CODE (b
->head
) == CODE_LABEL
1571 && (!(mode
& CLEANUP_PRE_SIBCALL
)
1572 || !tail_recursion_label_p (b
->head
))
1573 /* If the previous block ends with a branch to this block,
1574 we can't delete the label. Normally this is a condjump
1575 that is yet to be simplified, but if CASE_DROPS_THRU,
1576 this can be a tablejump with some element going to the
1577 same place as the default (fallthru). */
1578 && (b
->pred
->src
== ENTRY_BLOCK_PTR
1579 || GET_CODE (b
->pred
->src
->end
) != JUMP_INSN
1580 || ! label_is_jump_target_p (b
->head
, b
->pred
->src
->end
)))
1582 rtx label
= b
->head
;
1584 b
->head
= NEXT_INSN (b
->head
);
1585 delete_insn_chain (label
, label
);
1587 fprintf (rtl_dump_file
, "Deleted label in block %i.\n",
1591 /* If we fall through an empty block, we can remove it. */
1592 if (b
->pred
->pred_next
== NULL
1593 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1594 && GET_CODE (b
->head
) != CODE_LABEL
1595 && FORWARDER_BLOCK_P (b
)
1596 /* Note that forwarder_block_p true ensures that there
1597 is a successor for this block. */
1598 && (b
->succ
->flags
& EDGE_FALLTHRU
)
1599 && n_basic_blocks
> 1)
1602 fprintf (rtl_dump_file
, "Deleting fallthru block %i.\n",
1605 c
= BASIC_BLOCK (b
->index
? b
->index
- 1 : 1);
1606 redirect_edge_succ_nodup (b
->pred
, b
->succ
->dest
);
1607 flow_delete_block (b
);
1612 /* Merge blocks. Loop because chains of blocks might be
1614 while ((s
= b
->succ
) != NULL
1615 && s
->succ_next
== NULL
1616 && !(s
->flags
& EDGE_COMPLEX
)
1617 && (c
= s
->dest
) != EXIT_BLOCK_PTR
1618 && c
->pred
->pred_next
== NULL
1619 /* If the jump insn has side effects,
1620 we can't kill the edge. */
1621 && (GET_CODE (b
->end
) != JUMP_INSN
1622 || onlyjump_p (b
->end
))
1623 && merge_blocks (s
, b
, c
, mode
))
1624 changed_here
= true;
1626 /* Simplify branch over branch. */
1627 if ((mode
& CLEANUP_EXPENSIVE
) && try_simplify_condjump (b
))
1629 BB_SET_FLAG (b
, BB_UPDATE_LIFE
);
1630 changed_here
= true;
1633 /* If B has a single outgoing edge, but uses a non-trivial jump
1634 instruction without side-effects, we can either delete the
1635 jump entirely, or replace it with a simple unconditional jump.
1636 Use redirect_edge_and_branch to do the dirty work. */
1638 && ! b
->succ
->succ_next
1639 && b
->succ
->dest
!= EXIT_BLOCK_PTR
1640 && onlyjump_p (b
->end
)
1641 && redirect_edge_and_branch (b
->succ
, b
->succ
->dest
))
1643 BB_SET_FLAG (b
, BB_UPDATE_LIFE
);
1644 update_forwarder_flag (b
);
1645 changed_here
= true;
1648 /* Simplify branch to branch. */
1649 if (try_forward_edges (mode
, b
))
1650 changed_here
= true;
1652 /* Look for shared code between blocks. */
1653 if ((mode
& CLEANUP_CROSSJUMP
)
1654 && try_crossjump_bb (mode
, b
))
1655 changed_here
= true;
1657 /* Don't get confused by the index shift caused by deleting
1665 if ((mode
& CLEANUP_CROSSJUMP
)
1666 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
1669 #ifdef ENABLE_CHECKING
1671 verify_flow_info ();
1674 changed_overall
|= changed
;
1678 if (mode
& CLEANUP_CROSSJUMP
)
1679 remove_fake_edges ();
1681 if ((mode
& CLEANUP_UPDATE_LIFE
) && changed_overall
)
1685 blocks
= sbitmap_alloc (n_basic_blocks
);
1686 sbitmap_zero (blocks
);
1687 for (i
= 0; i
< n_basic_blocks
; i
++)
1688 if (BB_FLAGS (BASIC_BLOCK (i
)) & BB_UPDATE_LIFE
)
1691 SET_BIT (blocks
, i
);
1695 update_life_info (blocks
, UPDATE_LIFE_GLOBAL
,
1696 PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
1697 | PROP_KILL_DEAD_CODE
);
1698 sbitmap_free (blocks
);
1701 for (i
= 0; i
< n_basic_blocks
; i
++)
1702 BASIC_BLOCK (i
)->aux
= NULL
;
1704 return changed_overall
;
1707 /* Delete all unreachable basic blocks. */
1710 delete_unreachable_blocks ()
1713 bool changed
= false;
1715 find_unreachable_blocks ();
1717 /* Delete all unreachable basic blocks. Count down so that we
1718 don't interfere with the block renumbering that happens in
1719 flow_delete_block. */
1721 for (i
= n_basic_blocks
- 1; i
>= 0; --i
)
1723 basic_block b
= BASIC_BLOCK (i
);
1725 if (!(b
->flags
& BB_REACHABLE
))
1726 flow_delete_block (b
), changed
= true;
1730 tidy_fallthru_edges ();
1734 /* Tidy the CFG by deleting unreachable code and whatnot. */
1740 bool changed
= false;
1742 timevar_push (TV_CLEANUP_CFG
);
1743 changed
= delete_unreachable_blocks ();
1744 if (try_optimize_cfg (mode
))
1745 delete_unreachable_blocks (), changed
= true;
1747 /* Kill the data we won't maintain. */
1748 free_EXPR_LIST_list (&label_value_list
);
1749 free_EXPR_LIST_list (&tail_recursion_label_list
);
1750 timevar_pop (TV_CLEANUP_CFG
);