1 /* Control flow optimization code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003 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. */
36 #include "coretypes.h"
39 #include "hard-reg-set.h"
40 #include "basic-block.h"
43 #include "insn-config.h"
52 /* cleanup_cfg maintains following flags for each basic block. */
56 /* Set if BB is the forwarder block to avoid too many
57 forwarder_block_p calls. */
58 BB_FORWARDER_BLOCK
= 1,
59 BB_NONTHREADABLE_BLOCK
= 2
62 #define BB_FLAGS(BB) (enum bb_flags) (BB)->aux
63 #define BB_SET_FLAG(BB, FLAG) \
64 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux | (FLAG))
65 #define BB_CLEAR_FLAG(BB, FLAG) \
66 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux & ~(FLAG))
68 #define FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK)
70 static bool try_crossjump_to_edge (int, edge
, edge
);
71 static bool try_crossjump_bb (int, basic_block
);
72 static bool outgoing_edges_match (int, basic_block
, basic_block
);
73 static int flow_find_cross_jump (int, basic_block
, basic_block
, rtx
*, rtx
*);
74 static bool insns_match_p (int, rtx
, rtx
);
76 static bool tail_recursion_label_p (rtx
);
77 static void merge_blocks_move_predecessor_nojumps (basic_block
, basic_block
);
78 static void merge_blocks_move_successor_nojumps (basic_block
, basic_block
);
79 static bool try_optimize_cfg (int);
80 static bool try_simplify_condjump (basic_block
);
81 static bool try_forward_edges (int, basic_block
);
82 static edge
thread_jump (int, edge
, basic_block
);
83 static bool mark_effect (rtx
, bitmap
);
84 static void notice_new_block (basic_block
);
85 static void update_forwarder_flag (basic_block
);
86 static int mentions_nonequal_regs (rtx
*, void *);
88 /* Set flags for newly created block. */
91 notice_new_block (basic_block bb
)
96 if (forwarder_block_p (bb
))
97 BB_SET_FLAG (bb
, BB_FORWARDER_BLOCK
);
100 /* Recompute forwarder flag after block has been modified. */
103 update_forwarder_flag (basic_block bb
)
105 if (forwarder_block_p (bb
))
106 BB_SET_FLAG (bb
, BB_FORWARDER_BLOCK
);
108 BB_CLEAR_FLAG (bb
, BB_FORWARDER_BLOCK
);
111 /* Simplify a conditional jump around an unconditional jump.
112 Return true if something changed. */
115 try_simplify_condjump (basic_block cbranch_block
)
117 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
118 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
123 /* Verify that there are exactly two successors. */
124 if (!cbranch_block
->succ
125 || !cbranch_block
->succ
->succ_next
126 || cbranch_block
->succ
->succ_next
->succ_next
)
129 /* Verify that we've got a normal conditional branch at the end
131 cbranch_insn
= BB_END (cbranch_block
);
132 if (!any_condjump_p (cbranch_insn
))
135 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
136 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
138 /* The next block must not have multiple predecessors, must not
139 be the last block in the function, and must contain just the
140 unconditional jump. */
141 jump_block
= cbranch_fallthru_edge
->dest
;
142 if (jump_block
->pred
->pred_next
143 || jump_block
->next_bb
== EXIT_BLOCK_PTR
144 || !FORWARDER_BLOCK_P (jump_block
))
146 jump_dest_block
= jump_block
->succ
->dest
;
148 /* The conditional branch must target the block after the
149 unconditional branch. */
150 cbranch_dest_block
= cbranch_jump_edge
->dest
;
152 if (!can_fallthru (jump_block
, cbranch_dest_block
))
155 /* Invert the conditional branch. */
156 if (!invert_jump (cbranch_insn
, block_label (jump_dest_block
), 0))
160 fprintf (rtl_dump_file
, "Simplifying condjump %i around jump %i\n",
161 INSN_UID (cbranch_insn
), INSN_UID (BB_END (jump_block
)));
163 /* Success. Update the CFG to match. Note that after this point
164 the edge variable names appear backwards; the redirection is done
165 this way to preserve edge profile data. */
166 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
168 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
170 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
171 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
172 update_br_prob_note (cbranch_block
);
174 end
= BB_END (jump_block
);
175 /* Deleting a block may produce unreachable code warning even when we are
176 not deleting anything live. Suppress it by moving all the line number
177 notes out of the block. */
178 for (insn
= BB_HEAD (jump_block
); insn
!= NEXT_INSN (BB_END (jump_block
));
181 next
= NEXT_INSN (insn
);
182 if (GET_CODE (insn
) == NOTE
&& NOTE_LINE_NUMBER (insn
) > 0)
184 if (insn
== BB_END (jump_block
))
186 BB_END (jump_block
) = PREV_INSN (insn
);
190 reorder_insns_nobb (insn
, insn
, end
);
194 /* Delete the block with the unconditional jump, and clean up the mess. */
195 delete_block (jump_block
);
196 tidy_fallthru_edge (cbranch_jump_edge
, cbranch_block
, cbranch_dest_block
);
201 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
202 on register. Used by jump threading. */
205 mark_effect (rtx exp
, regset nonequal
)
209 switch (GET_CODE (exp
))
211 /* In case we do clobber the register, mark it as equal, as we know the
212 value is dead so it don't have to match. */
214 if (REG_P (XEXP (exp
, 0)))
216 dest
= XEXP (exp
, 0);
217 regno
= REGNO (dest
);
218 CLEAR_REGNO_REG_SET (nonequal
, regno
);
219 if (regno
< FIRST_PSEUDO_REGISTER
)
221 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
223 CLEAR_REGNO_REG_SET (nonequal
, regno
+ n
);
229 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
231 dest
= SET_DEST (exp
);
236 regno
= REGNO (dest
);
237 SET_REGNO_REG_SET (nonequal
, regno
);
238 if (regno
< FIRST_PSEUDO_REGISTER
)
240 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
242 SET_REGNO_REG_SET (nonequal
, regno
+ n
);
251 /* Return nonzero if X is a register set in regset DATA.
252 Called via for_each_rtx. */
254 mentions_nonequal_regs (rtx
*x
, void *data
)
256 regset nonequal
= (regset
) data
;
262 if (REGNO_REG_SET_P (nonequal
, regno
))
264 if (regno
< FIRST_PSEUDO_REGISTER
)
266 int n
= HARD_REGNO_NREGS (regno
, GET_MODE (*x
));
268 if (REGNO_REG_SET_P (nonequal
, regno
+ n
))
274 /* Attempt to prove that the basic block B will have no side effects and
275 always continues in the same edge if reached via E. Return the edge
276 if exist, NULL otherwise. */
279 thread_jump (int mode
, edge e
, basic_block b
)
281 rtx set1
, set2
, cond1
, cond2
, insn
;
282 enum rtx_code code1
, code2
, reversed_code2
;
283 bool reverse1
= false;
288 if (BB_FLAGS (b
) & BB_NONTHREADABLE_BLOCK
)
291 /* At the moment, we do handle only conditional jumps, but later we may
292 want to extend this code to tablejumps and others. */
293 if (!e
->src
->succ
->succ_next
|| e
->src
->succ
->succ_next
->succ_next
)
295 if (!b
->succ
|| !b
->succ
->succ_next
|| b
->succ
->succ_next
->succ_next
)
297 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
301 /* Second branch must end with onlyjump, as we will eliminate the jump. */
302 if (!any_condjump_p (BB_END (e
->src
)))
305 if (!any_condjump_p (BB_END (b
)) || !onlyjump_p (BB_END (b
)))
307 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
311 set1
= pc_set (BB_END (e
->src
));
312 set2
= pc_set (BB_END (b
));
313 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
314 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
317 cond1
= XEXP (SET_SRC (set1
), 0);
318 cond2
= XEXP (SET_SRC (set2
), 0);
320 code1
= reversed_comparison_code (cond1
, BB_END (e
->src
));
322 code1
= GET_CODE (cond1
);
324 code2
= GET_CODE (cond2
);
325 reversed_code2
= reversed_comparison_code (cond2
, BB_END (b
));
327 if (!comparison_dominates_p (code1
, code2
)
328 && !comparison_dominates_p (code1
, reversed_code2
))
331 /* Ensure that the comparison operators are equivalent.
332 ??? This is far too pessimistic. We should allow swapped operands,
333 different CCmodes, or for example comparisons for interval, that
334 dominate even when operands are not equivalent. */
335 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
336 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
339 /* Short circuit cases where block B contains some side effects, as we can't
341 for (insn
= NEXT_INSN (BB_HEAD (b
)); insn
!= NEXT_INSN (BB_END (b
));
342 insn
= NEXT_INSN (insn
))
343 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
345 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
351 /* First process all values computed in the source basic block. */
352 for (insn
= NEXT_INSN (BB_HEAD (e
->src
)); insn
!= NEXT_INSN (BB_END (e
->src
));
353 insn
= NEXT_INSN (insn
))
355 cselib_process_insn (insn
);
357 nonequal
= BITMAP_XMALLOC();
358 CLEAR_REG_SET (nonequal
);
360 /* Now assume that we've continued by the edge E to B and continue
361 processing as if it were same basic block.
362 Our goal is to prove that whole block is an NOOP. */
364 for (insn
= NEXT_INSN (BB_HEAD (b
)); insn
!= NEXT_INSN (BB_END (b
)) && !failed
;
365 insn
= NEXT_INSN (insn
))
369 rtx pat
= PATTERN (insn
);
371 if (GET_CODE (pat
) == PARALLEL
)
373 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
374 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
377 failed
|= mark_effect (pat
, nonequal
);
380 cselib_process_insn (insn
);
383 /* Later we should clear nonequal of dead registers. So far we don't
384 have life information in cfg_cleanup. */
387 BB_SET_FLAG (b
, BB_NONTHREADABLE_BLOCK
);
391 /* cond2 must not mention any register that is not equal to the
393 if (for_each_rtx (&cond2
, mentions_nonequal_regs
, nonequal
))
396 /* In case liveness information is available, we need to prove equivalence
397 only of the live values. */
398 if (mode
& CLEANUP_UPDATE_LIFE
)
399 AND_REG_SET (nonequal
, b
->global_live_at_end
);
401 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, goto failed_exit
;);
403 BITMAP_XFREE (nonequal
);
405 if ((comparison_dominates_p (code1
, code2
) != 0)
406 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
407 return BRANCH_EDGE (b
);
409 return FALLTHRU_EDGE (b
);
412 BITMAP_XFREE (nonequal
);
417 /* Attempt to forward edges leaving basic block B.
418 Return true if successful. */
421 try_forward_edges (int mode
, basic_block b
)
423 bool changed
= false;
424 edge e
, next
, *threaded_edges
= NULL
;
426 for (e
= b
->succ
; e
; e
= next
)
428 basic_block target
, first
;
430 bool threaded
= false;
431 int nthreaded_edges
= 0;
435 /* Skip complex edges because we don't know how to update them.
437 Still handle fallthru edges, as we can succeed to forward fallthru
438 edge to the same place as the branch edge of conditional branch
439 and turn conditional branch to an unconditional branch. */
440 if (e
->flags
& EDGE_COMPLEX
)
443 target
= first
= e
->dest
;
446 while (counter
< n_basic_blocks
)
448 basic_block new_target
= NULL
;
449 bool new_target_threaded
= false;
451 if (FORWARDER_BLOCK_P (target
)
452 && target
->succ
->dest
!= EXIT_BLOCK_PTR
)
454 /* Bypass trivial infinite loops. */
455 if (target
== target
->succ
->dest
)
456 counter
= n_basic_blocks
;
457 new_target
= target
->succ
->dest
;
460 /* Allow to thread only over one edge at time to simplify updating
462 else if (mode
& CLEANUP_THREADING
)
464 edge t
= thread_jump (mode
, e
, target
);
468 threaded_edges
= xmalloc (sizeof (*threaded_edges
)
474 /* Detect an infinite loop across blocks not
475 including the start block. */
476 for (i
= 0; i
< nthreaded_edges
; ++i
)
477 if (threaded_edges
[i
] == t
)
479 if (i
< nthreaded_edges
)
481 counter
= n_basic_blocks
;
486 /* Detect an infinite loop across the start block. */
490 if (nthreaded_edges
>= n_basic_blocks
)
492 threaded_edges
[nthreaded_edges
++] = t
;
494 new_target
= t
->dest
;
495 new_target_threaded
= true;
502 /* Avoid killing of loop pre-headers, as it is the place loop
503 optimizer wants to hoist code to.
505 For fallthru forwarders, the LOOP_BEG note must appear between
506 the header of block and CODE_LABEL of the loop, for non forwarders
507 it must appear before the JUMP_INSN. */
508 if ((mode
& CLEANUP_PRE_LOOP
) && optimize
)
510 rtx insn
= (target
->succ
->flags
& EDGE_FALLTHRU
511 ? BB_HEAD (target
) : prev_nonnote_insn (BB_END (target
)));
513 if (GET_CODE (insn
) != NOTE
)
514 insn
= NEXT_INSN (insn
);
516 for (; insn
&& GET_CODE (insn
) != CODE_LABEL
&& !INSN_P (insn
);
517 insn
= NEXT_INSN (insn
))
518 if (GET_CODE (insn
) == NOTE
519 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
522 if (GET_CODE (insn
) == NOTE
)
525 /* Do not clean up branches to just past the end of a loop
526 at this time; it can mess up the loop optimizer's
527 recognition of some patterns. */
529 insn
= PREV_INSN (BB_HEAD (target
));
530 if (insn
&& GET_CODE (insn
) == NOTE
531 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
537 threaded
|= new_target_threaded
;
540 if (counter
>= n_basic_blocks
)
543 fprintf (rtl_dump_file
, "Infinite loop in BB %i.\n",
546 else if (target
== first
)
547 ; /* We didn't do anything. */
550 /* Save the values now, as the edge may get removed. */
551 gcov_type edge_count
= e
->count
;
552 int edge_probability
= e
->probability
;
556 /* Don't force if target is exit block. */
557 if (threaded
&& target
!= EXIT_BLOCK_PTR
)
559 notice_new_block (redirect_edge_and_branch_force (e
, target
));
561 fprintf (rtl_dump_file
, "Conditionals threaded.\n");
563 else if (!redirect_edge_and_branch (e
, target
))
566 fprintf (rtl_dump_file
,
567 "Forwarding edge %i->%i to %i failed.\n",
568 b
->index
, e
->dest
->index
, target
->index
);
572 /* We successfully forwarded the edge. Now update profile
573 data: for each edge we traversed in the chain, remove
574 the original edge's execution count. */
575 edge_frequency
= ((edge_probability
* b
->frequency
576 + REG_BR_PROB_BASE
/ 2)
579 if (!FORWARDER_BLOCK_P (b
) && forwarder_block_p (b
))
580 BB_SET_FLAG (b
, BB_FORWARDER_BLOCK
);
586 first
->count
-= edge_count
;
587 if (first
->count
< 0)
589 first
->frequency
-= edge_frequency
;
590 if (first
->frequency
< 0)
591 first
->frequency
= 0;
592 if (first
->succ
->succ_next
)
596 if (n
>= nthreaded_edges
)
598 t
= threaded_edges
[n
++];
601 if (first
->frequency
)
602 prob
= edge_frequency
* REG_BR_PROB_BASE
/ first
->frequency
;
605 if (prob
> t
->probability
)
606 prob
= t
->probability
;
607 t
->probability
-= prob
;
608 prob
= REG_BR_PROB_BASE
- prob
;
611 first
->succ
->probability
= REG_BR_PROB_BASE
;
612 first
->succ
->succ_next
->probability
= 0;
615 for (e
= first
->succ
; e
; e
= e
->succ_next
)
616 e
->probability
= ((e
->probability
* REG_BR_PROB_BASE
)
618 update_br_prob_note (first
);
622 /* It is possible that as the result of
623 threading we've removed edge as it is
624 threaded to the fallthru edge. Avoid
625 getting out of sync. */
626 if (n
< nthreaded_edges
627 && first
== threaded_edges
[n
]->src
)
632 t
->count
-= edge_count
;
637 while (first
!= target
);
644 free (threaded_edges
);
648 /* Return true if LABEL is used for tail recursion. */
651 tail_recursion_label_p (rtx label
)
655 for (x
= tail_recursion_label_list
; x
; x
= XEXP (x
, 1))
656 if (label
== XEXP (x
, 0))
662 /* Blocks A and B are to be merged into a single block. A has no incoming
663 fallthru edge, so it can be moved before B without adding or modifying
664 any jumps (aside from the jump from A to B). */
667 merge_blocks_move_predecessor_nojumps (basic_block a
, basic_block b
)
671 barrier
= next_nonnote_insn (BB_END (a
));
672 if (GET_CODE (barrier
) != BARRIER
)
674 delete_insn (barrier
);
676 /* Move block and loop notes out of the chain so that we do not
679 ??? A better solution would be to squeeze out all the non-nested notes
680 and adjust the block trees appropriately. Even better would be to have
681 a tighter connection between block trees and rtl so that this is not
683 if (squeeze_notes (&BB_HEAD (a
), &BB_END (a
)))
686 /* Scramble the insn chain. */
687 if (BB_END (a
) != PREV_INSN (BB_HEAD (b
)))
688 reorder_insns_nobb (BB_HEAD (a
), BB_END (a
), PREV_INSN (BB_HEAD (b
)));
689 a
->flags
|= BB_DIRTY
;
692 fprintf (rtl_dump_file
, "Moved block %d before %d and merged.\n",
695 /* Swap the records for the two blocks around. */
698 link_block (a
, b
->prev_bb
);
700 /* Now blocks A and B are contiguous. Merge them. */
704 /* Blocks A and B are to be merged into a single block. B has no outgoing
705 fallthru edge, so it can be moved after A without adding or modifying
706 any jumps (aside from the jump from A to B). */
709 merge_blocks_move_successor_nojumps (basic_block a
, basic_block b
)
711 rtx barrier
, real_b_end
;
714 real_b_end
= BB_END (b
);
716 /* If there is a jump table following block B temporarily add the jump table
717 to block B so that it will also be moved to the correct location. */
718 if (tablejump_p (BB_END (b
), &label
, &table
)
719 && prev_active_insn (label
) == BB_END (b
))
724 /* There had better have been a barrier there. Delete it. */
725 barrier
= NEXT_INSN (BB_END (b
));
726 if (barrier
&& GET_CODE (barrier
) == BARRIER
)
727 delete_insn (barrier
);
729 /* Move block and loop notes out of the chain so that we do not
732 ??? A better solution would be to squeeze out all the non-nested notes
733 and adjust the block trees appropriately. Even better would be to have
734 a tighter connection between block trees and rtl so that this is not
736 if (squeeze_notes (&BB_HEAD (b
), &BB_END (b
)))
739 /* Scramble the insn chain. */
740 reorder_insns_nobb (BB_HEAD (b
), BB_END (b
), BB_END (a
));
742 /* Restore the real end of b. */
743 BB_END (b
) = real_b_end
;
746 fprintf (rtl_dump_file
, "Moved block %d after %d and merged.\n",
749 /* Now blocks A and B are contiguous. Merge them. */
753 /* Attempt to merge basic blocks that are potentially non-adjacent.
754 Return NULL iff the attempt failed, otherwise return basic block
755 where cleanup_cfg should continue. Because the merging commonly
756 moves basic block away or introduces another optimization
757 possibility, return basic block just before B so cleanup_cfg don't
760 It may be good idea to return basic block before C in the case
761 C has been moved after B and originally appeared earlier in the
762 insn sequence, but we have no information available about the
763 relative ordering of these two. Hopefully it is not too common. */
766 merge_blocks_move (edge e
, basic_block b
, basic_block c
, int mode
)
769 /* If C has a tail recursion label, do not merge. There is no
770 edge recorded from the call_placeholder back to this label, as
771 that would make optimize_sibling_and_tail_recursive_calls more
772 complex for no gain. */
773 if ((mode
& CLEANUP_PRE_SIBCALL
)
774 && GET_CODE (BB_HEAD (c
)) == CODE_LABEL
775 && tail_recursion_label_p (BB_HEAD (c
)))
778 /* If B has a fallthru edge to C, no need to move anything. */
779 if (e
->flags
& EDGE_FALLTHRU
)
781 int b_index
= b
->index
, c_index
= c
->index
;
783 update_forwarder_flag (b
);
786 fprintf (rtl_dump_file
, "Merged %d and %d without moving.\n",
789 return b
->prev_bb
== ENTRY_BLOCK_PTR
? b
: b
->prev_bb
;
792 /* Otherwise we will need to move code around. Do that only if expensive
793 transformations are allowed. */
794 else if (mode
& CLEANUP_EXPENSIVE
)
796 edge tmp_edge
, b_fallthru_edge
;
797 bool c_has_outgoing_fallthru
;
798 bool b_has_incoming_fallthru
;
800 /* Avoid overactive code motion, as the forwarder blocks should be
801 eliminated by edge redirection instead. One exception might have
802 been if B is a forwarder block and C has no fallthru edge, but
803 that should be cleaned up by bb-reorder instead. */
804 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
807 /* We must make sure to not munge nesting of lexical blocks,
808 and loop notes. This is done by squeezing out all the notes
809 and leaving them there to lie. Not ideal, but functional. */
811 for (tmp_edge
= c
->succ
; tmp_edge
; tmp_edge
= tmp_edge
->succ_next
)
812 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
815 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
817 for (tmp_edge
= b
->pred
; tmp_edge
; tmp_edge
= tmp_edge
->pred_next
)
818 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
821 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
822 b_fallthru_edge
= tmp_edge
;
825 next
= next
->prev_bb
;
827 /* Otherwise, we're going to try to move C after B. If C does
828 not have an outgoing fallthru, then it can be moved
829 immediately after B without introducing or modifying jumps. */
830 if (! c_has_outgoing_fallthru
)
832 merge_blocks_move_successor_nojumps (b
, c
);
833 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
836 /* If B does not have an incoming fallthru, then it can be moved
837 immediately before C without introducing or modifying jumps.
838 C cannot be the first block, so we do not have to worry about
839 accessing a non-existent block. */
841 if (b_has_incoming_fallthru
)
845 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
847 bb
= force_nonfallthru (b_fallthru_edge
);
849 notice_new_block (bb
);
852 merge_blocks_move_predecessor_nojumps (b
, c
);
853 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
860 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
863 insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx i1
, rtx i2
)
867 /* Verify that I1 and I2 are equivalent. */
868 if (GET_CODE (i1
) != GET_CODE (i2
))
874 if (GET_CODE (p1
) != GET_CODE (p2
))
877 /* If this is a CALL_INSN, compare register usage information.
878 If we don't check this on stack register machines, the two
879 CALL_INSNs might be merged leaving reg-stack.c with mismatching
880 numbers of stack registers in the same basic block.
881 If we don't check this on machines with delay slots, a delay slot may
882 be filled that clobbers a parameter expected by the subroutine.
884 ??? We take the simple route for now and assume that if they're
885 equal, they were constructed identically. */
887 if (GET_CODE (i1
) == CALL_INSN
888 && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
889 CALL_INSN_FUNCTION_USAGE (i2
))
890 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
)))
894 /* If cross_jump_death_matters is not 0, the insn's mode
895 indicates whether or not the insn contains any stack-like
898 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
900 /* If register stack conversion has already been done, then
901 death notes must also be compared before it is certain that
902 the two instruction streams match. */
905 HARD_REG_SET i1_regset
, i2_regset
;
907 CLEAR_HARD_REG_SET (i1_regset
);
908 CLEAR_HARD_REG_SET (i2_regset
);
910 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
911 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
912 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
914 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
915 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
916 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
918 GO_IF_HARD_REG_EQUAL (i1_regset
, i2_regset
, done
);
928 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
931 /* Do not do EQUIV substitution after reload. First, we're undoing the
932 work of reload_cse. Second, we may be undoing the work of the post-
933 reload splitting pass. */
934 /* ??? Possibly add a new phase switch variable that can be used by
935 targets to disallow the troublesome insns after splitting. */
936 if (!reload_completed
)
938 /* The following code helps take care of G++ cleanups. */
939 rtx equiv1
= find_reg_equal_equiv_note (i1
);
940 rtx equiv2
= find_reg_equal_equiv_note (i2
);
943 /* If the equivalences are not to a constant, they may
944 reference pseudos that no longer exist, so we can't
946 && (! reload_completed
947 || (CONSTANT_P (XEXP (equiv1
, 0))
948 && rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))))
950 rtx s1
= single_set (i1
);
951 rtx s2
= single_set (i2
);
952 if (s1
!= 0 && s2
!= 0
953 && rtx_renumbered_equal_p (SET_DEST (s1
), SET_DEST (s2
)))
955 validate_change (i1
, &SET_SRC (s1
), XEXP (equiv1
, 0), 1);
956 validate_change (i2
, &SET_SRC (s2
), XEXP (equiv2
, 0), 1);
957 if (! rtx_renumbered_equal_p (p1
, p2
))
959 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 (int mode ATTRIBUTE_UNUSED
, basic_block bb1
,
977 basic_block bb2
, rtx
*f1
, rtx
*f2
)
979 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
982 /* Skip simple jumps at the end of the blocks. Complex jumps still
983 need to be compared for equivalence, which we'll do below. */
986 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
988 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
996 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
999 /* Count everything except for unconditional jump as insn. */
1000 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1002 i2
= PREV_INSN (i2
);
1008 while (!INSN_P (i1
) && i1
!= BB_HEAD (bb1
))
1009 i1
= PREV_INSN (i1
);
1011 while (!INSN_P (i2
) && i2
!= BB_HEAD (bb2
))
1012 i2
= PREV_INSN (i2
);
1014 if (i1
== BB_HEAD (bb1
) || i2
== BB_HEAD (bb2
))
1017 if (!insns_match_p (mode
, i1
, i2
))
1020 /* Don't begin a cross-jump with a NOTE insn. */
1023 /* If the merged insns have different REG_EQUAL notes, then
1025 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1026 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1028 if (equiv1
&& !equiv2
)
1029 remove_note (i1
, equiv1
);
1030 else if (!equiv1
&& equiv2
)
1031 remove_note (i2
, equiv2
);
1032 else if (equiv1
&& equiv2
1033 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1035 remove_note (i1
, equiv1
);
1036 remove_note (i2
, equiv2
);
1039 afterlast1
= last1
, afterlast2
= last2
;
1040 last1
= i1
, last2
= i2
;
1044 i1
= PREV_INSN (i1
);
1045 i2
= PREV_INSN (i2
);
1049 /* Don't allow the insn after a compare to be shared by
1050 cross-jumping unless the compare is also shared. */
1051 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1052 last1
= afterlast1
, last2
= afterlast2
, ninsns
--;
1055 /* Include preceding notes and labels in the cross-jump. One,
1056 this may bring us to the head of the blocks as requested above.
1057 Two, it keeps line number notes as matched as may be. */
1060 while (last1
!= BB_HEAD (bb1
) && !INSN_P (PREV_INSN (last1
)))
1061 last1
= PREV_INSN (last1
);
1063 if (last1
!= BB_HEAD (bb1
) && GET_CODE (PREV_INSN (last1
)) == CODE_LABEL
)
1064 last1
= PREV_INSN (last1
);
1066 while (last2
!= BB_HEAD (bb2
) && !INSN_P (PREV_INSN (last2
)))
1067 last2
= PREV_INSN (last2
);
1069 if (last2
!= BB_HEAD (bb2
) && GET_CODE (PREV_INSN (last2
)) == CODE_LABEL
)
1070 last2
= PREV_INSN (last2
);
1079 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1080 the branch instruction. This means that if we commonize the control
1081 flow before end of the basic block, the semantic remains unchanged.
1083 We may assume that there exists one edge with a common destination. */
1086 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1088 int nehedges1
= 0, nehedges2
= 0;
1089 edge fallthru1
= 0, fallthru2
= 0;
1092 /* If BB1 has only one successor, we may be looking at either an
1093 unconditional jump, or a fake edge to exit. */
1094 if (bb1
->succ
&& !bb1
->succ
->succ_next
1095 && (bb1
->succ
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1096 && (GET_CODE (BB_END (bb1
)) != JUMP_INSN
|| simplejump_p (BB_END (bb1
))))
1097 return (bb2
->succ
&& !bb2
->succ
->succ_next
1098 && (bb2
->succ
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1099 && (GET_CODE (BB_END (bb2
)) != JUMP_INSN
|| simplejump_p (BB_END (bb2
))));
1101 /* Match conditional jumps - this may get tricky when fallthru and branch
1102 edges are crossed. */
1104 && bb1
->succ
->succ_next
1105 && !bb1
->succ
->succ_next
->succ_next
1106 && any_condjump_p (BB_END (bb1
))
1107 && onlyjump_p (BB_END (bb1
)))
1109 edge b1
, f1
, b2
, f2
;
1110 bool reverse
, match
;
1111 rtx set1
, set2
, cond1
, cond2
;
1112 enum rtx_code code1
, code2
;
1115 || !bb2
->succ
->succ_next
1116 || bb2
->succ
->succ_next
->succ_next
1117 || !any_condjump_p (BB_END (bb2
))
1118 || !onlyjump_p (BB_END (bb2
)))
1121 b1
= BRANCH_EDGE (bb1
);
1122 b2
= BRANCH_EDGE (bb2
);
1123 f1
= FALLTHRU_EDGE (bb1
);
1124 f2
= FALLTHRU_EDGE (bb2
);
1126 /* Get around possible forwarders on fallthru edges. Other cases
1127 should be optimized out already. */
1128 if (FORWARDER_BLOCK_P (f1
->dest
))
1129 f1
= f1
->dest
->succ
;
1131 if (FORWARDER_BLOCK_P (f2
->dest
))
1132 f2
= f2
->dest
->succ
;
1134 /* To simplify use of this function, return false if there are
1135 unneeded forwarder blocks. These will get eliminated later
1136 during cleanup_cfg. */
1137 if (FORWARDER_BLOCK_P (f1
->dest
)
1138 || FORWARDER_BLOCK_P (f2
->dest
)
1139 || FORWARDER_BLOCK_P (b1
->dest
)
1140 || FORWARDER_BLOCK_P (b2
->dest
))
1143 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1145 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1150 set1
= pc_set (BB_END (bb1
));
1151 set2
= pc_set (BB_END (bb2
));
1152 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1153 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1156 cond1
= XEXP (SET_SRC (set1
), 0);
1157 cond2
= XEXP (SET_SRC (set2
), 0);
1158 code1
= GET_CODE (cond1
);
1160 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
1162 code2
= GET_CODE (cond2
);
1164 if (code2
== UNKNOWN
)
1167 /* Verify codes and operands match. */
1168 match
= ((code1
== code2
1169 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1170 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1171 || (code1
== swap_condition (code2
)
1172 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1174 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1177 /* If we return true, we will join the blocks. Which means that
1178 we will only have one branch prediction bit to work with. Thus
1179 we require the existing branches to have probabilities that are
1183 && maybe_hot_bb_p (bb1
)
1184 && maybe_hot_bb_p (bb2
))
1188 if (b1
->dest
== b2
->dest
)
1189 prob2
= b2
->probability
;
1191 /* Do not use f2 probability as f2 may be forwarded. */
1192 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1194 /* Fail if the difference in probabilities is greater than 50%.
1195 This rules out two well-predicted branches with opposite
1197 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1200 fprintf (rtl_dump_file
,
1201 "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
1202 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1208 if (rtl_dump_file
&& match
)
1209 fprintf (rtl_dump_file
, "Conditionals in bb %i and %i match.\n",
1210 bb1
->index
, bb2
->index
);
1215 /* Generic case - we are seeing a computed jump, table jump or trapping
1218 #ifndef CASE_DROPS_THROUGH
1219 /* Check whether there are tablejumps in the end of BB1 and BB2.
1220 Return true if they are identical. */
1225 if (tablejump_p (BB_END (bb1
), &label1
, &table1
)
1226 && tablejump_p (BB_END (bb2
), &label2
, &table2
)
1227 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1229 /* The labels should never be the same rtx. If they really are same
1230 the jump tables are same too. So disable crossjumping of blocks BB1
1231 and BB2 because when deleting the common insns in the end of BB1
1232 by delete_block () the jump table would be deleted too. */
1233 /* If LABEL2 is referenced in BB1->END do not do anything
1234 because we would loose information when replacing
1235 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1236 if (label1
!= label2
&& !rtx_referenced_p (label2
, BB_END (bb1
)))
1238 /* Set IDENTICAL to true when the tables are identical. */
1239 bool identical
= false;
1242 p1
= PATTERN (table1
);
1243 p2
= PATTERN (table2
);
1244 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1248 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1249 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1250 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1251 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1256 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1257 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1263 replace_label_data rr
;
1266 /* Temporarily replace references to LABEL1 with LABEL2
1267 in BB1->END so that we could compare the instructions. */
1270 rr
.update_label_nuses
= false;
1271 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1273 match
= insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
));
1274 if (rtl_dump_file
&& match
)
1275 fprintf (rtl_dump_file
,
1276 "Tablejumps in bb %i and %i match.\n",
1277 bb1
->index
, bb2
->index
);
1279 /* Set the original label in BB1->END because when deleting
1280 a block whose end is a tablejump, the tablejump referenced
1281 from the instruction is deleted too. */
1284 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1294 /* First ensure that the instructions match. There may be many outgoing
1295 edges so this test is generally cheaper. */
1296 if (!insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
)))
1299 /* Search the outgoing edges, ensure that the counts do match, find possible
1300 fallthru and exception handling edges since these needs more
1302 for (e1
= bb1
->succ
, e2
= bb2
->succ
; e1
&& e2
;
1303 e1
= e1
->succ_next
, e2
= e2
->succ_next
)
1305 if (e1
->flags
& EDGE_EH
)
1308 if (e2
->flags
& EDGE_EH
)
1311 if (e1
->flags
& EDGE_FALLTHRU
)
1313 if (e2
->flags
& EDGE_FALLTHRU
)
1317 /* If number of edges of various types does not match, fail. */
1319 || nehedges1
!= nehedges2
1320 || (fallthru1
!= 0) != (fallthru2
!= 0))
1323 /* fallthru edges must be forwarded to the same destination. */
1326 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1327 ? fallthru1
->dest
->succ
->dest
: fallthru1
->dest
);
1328 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1329 ? fallthru2
->dest
->succ
->dest
: fallthru2
->dest
);
1335 /* Ensure the same EH region. */
1337 rtx n1
= find_reg_note (BB_END (bb1
), REG_EH_REGION
, 0);
1338 rtx n2
= find_reg_note (BB_END (bb2
), REG_EH_REGION
, 0);
1343 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1347 /* We don't need to match the rest of edges as above checks should be enough
1348 to ensure that they are equivalent. */
1352 /* E1 and E2 are edges with the same destination block. Search their
1353 predecessors for common code. If found, redirect control flow from
1354 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1357 try_crossjump_to_edge (int mode
, edge e1
, edge e2
)
1360 basic_block src1
= e1
->src
, src2
= e2
->src
;
1361 basic_block redirect_to
, redirect_from
, to_remove
;
1362 rtx newpos1
, newpos2
;
1365 /* Search backward through forwarder blocks. We don't need to worry
1366 about multiple entry or chained forwarders, as they will be optimized
1367 away. We do this to look past the unconditional jump following a
1368 conditional jump that is required due to the current CFG shape. */
1370 && !src1
->pred
->pred_next
1371 && FORWARDER_BLOCK_P (src1
))
1372 e1
= src1
->pred
, src1
= e1
->src
;
1375 && !src2
->pred
->pred_next
1376 && FORWARDER_BLOCK_P (src2
))
1377 e2
= src2
->pred
, src2
= e2
->src
;
1379 /* Nothing to do if we reach ENTRY, or a common source block. */
1380 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1385 /* Seeing more than 1 forwarder blocks would confuse us later... */
1386 if (FORWARDER_BLOCK_P (e1
->dest
)
1387 && FORWARDER_BLOCK_P (e1
->dest
->succ
->dest
))
1390 if (FORWARDER_BLOCK_P (e2
->dest
)
1391 && FORWARDER_BLOCK_P (e2
->dest
->succ
->dest
))
1394 /* Likewise with dead code (possibly newly created by the other optimizations
1396 if (!src1
->pred
|| !src2
->pred
)
1399 /* Look for the common insn sequence, part the first ... */
1400 if (!outgoing_edges_match (mode
, src1
, src2
))
1403 /* ... and part the second. */
1404 nmatch
= flow_find_cross_jump (mode
, src1
, src2
, &newpos1
, &newpos2
);
1408 #ifndef CASE_DROPS_THROUGH
1409 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1411 If we have tablejumps in the end of SRC1 and SRC2
1412 they have been already compared for equivalence in outgoing_edges_match ()
1413 so replace the references to TABLE1 by references to TABLE2. */
1418 if (tablejump_p (BB_END (src1
), &label1
, &table1
)
1419 && tablejump_p (BB_END (src2
), &label2
, &table2
)
1420 && label1
!= label2
)
1422 replace_label_data rr
;
1425 /* Replace references to LABEL1 with LABEL2. */
1428 rr
.update_label_nuses
= true;
1429 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1431 /* Do not replace the label in SRC1->END because when deleting
1432 a block whose end is a tablejump, the tablejump referenced
1433 from the instruction is deleted too. */
1434 if (insn
!= BB_END (src1
))
1435 for_each_rtx (&insn
, replace_label
, &rr
);
1441 /* Avoid splitting if possible. */
1442 if (newpos2
== BB_HEAD (src2
))
1447 fprintf (rtl_dump_file
, "Splitting bb %i before %i insns\n",
1448 src2
->index
, nmatch
);
1449 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
1453 fprintf (rtl_dump_file
,
1454 "Cross jumping from bb %i to bb %i; %i common insns\n",
1455 src1
->index
, src2
->index
, nmatch
);
1457 redirect_to
->count
+= src1
->count
;
1458 redirect_to
->frequency
+= src1
->frequency
;
1459 /* We may have some registers visible trought the block. */
1460 redirect_to
->flags
|= BB_DIRTY
;
1462 /* Recompute the frequencies and counts of outgoing edges. */
1463 for (s
= redirect_to
->succ
; s
; s
= s
->succ_next
)
1466 basic_block d
= s
->dest
;
1468 if (FORWARDER_BLOCK_P (d
))
1471 for (s2
= src1
->succ
; ; s2
= s2
->succ_next
)
1473 basic_block d2
= s2
->dest
;
1474 if (FORWARDER_BLOCK_P (d2
))
1475 d2
= d2
->succ
->dest
;
1480 s
->count
+= s2
->count
;
1482 /* Take care to update possible forwarder blocks. We verified
1483 that there is no more than one in the chain, so we can't run
1484 into infinite loop. */
1485 if (FORWARDER_BLOCK_P (s
->dest
))
1487 s
->dest
->succ
->count
+= s2
->count
;
1488 s
->dest
->count
+= s2
->count
;
1489 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
1492 if (FORWARDER_BLOCK_P (s2
->dest
))
1494 s2
->dest
->succ
->count
-= s2
->count
;
1495 if (s2
->dest
->succ
->count
< 0)
1496 s2
->dest
->succ
->count
= 0;
1497 s2
->dest
->count
-= s2
->count
;
1498 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
1499 if (s2
->dest
->frequency
< 0)
1500 s2
->dest
->frequency
= 0;
1501 if (s2
->dest
->count
< 0)
1502 s2
->dest
->count
= 0;
1505 if (!redirect_to
->frequency
&& !src1
->frequency
)
1506 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
1509 = ((s
->probability
* redirect_to
->frequency
+
1510 s2
->probability
* src1
->frequency
)
1511 / (redirect_to
->frequency
+ src1
->frequency
));
1514 update_br_prob_note (redirect_to
);
1516 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1518 /* Skip possible basic block header. */
1519 if (GET_CODE (newpos1
) == CODE_LABEL
)
1520 newpos1
= NEXT_INSN (newpos1
);
1522 if (GET_CODE (newpos1
) == NOTE
)
1523 newpos1
= NEXT_INSN (newpos1
);
1525 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
1526 to_remove
= redirect_from
->succ
->dest
;
1528 redirect_edge_and_branch_force (redirect_from
->succ
, redirect_to
);
1529 delete_block (to_remove
);
1531 update_forwarder_flag (redirect_from
);
1536 /* Search the predecessors of BB for common insn sequences. When found,
1537 share code between them by redirecting control flow. Return true if
1538 any changes made. */
1541 try_crossjump_bb (int mode
, basic_block bb
)
1543 edge e
, e2
, nexte2
, nexte
, fallthru
;
1547 /* Nothing to do if there is not at least two incoming edges. */
1548 if (!bb
->pred
|| !bb
->pred
->pred_next
)
1551 /* It is always cheapest to redirect a block that ends in a branch to
1552 a block that falls through into BB, as that adds no branches to the
1553 program. We'll try that combination first. */
1555 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
1556 for (e
= bb
->pred
; e
; e
= e
->pred_next
, n
++)
1558 if (e
->flags
& EDGE_FALLTHRU
)
1565 for (e
= bb
->pred
; e
; e
= nexte
)
1567 nexte
= e
->pred_next
;
1569 /* As noted above, first try with the fallthru predecessor. */
1572 /* Don't combine the fallthru edge into anything else.
1573 If there is a match, we'll do it the other way around. */
1577 if (try_crossjump_to_edge (mode
, e
, fallthru
))
1585 /* Non-obvious work limiting check: Recognize that we're going
1586 to call try_crossjump_bb on every basic block. So if we have
1587 two blocks with lots of outgoing edges (a switch) and they
1588 share lots of common destinations, then we would do the
1589 cross-jump check once for each common destination.
1591 Now, if the blocks actually are cross-jump candidates, then
1592 all of their destinations will be shared. Which means that
1593 we only need check them for cross-jump candidacy once. We
1594 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1595 choosing to do the check from the block for which the edge
1596 in question is the first successor of A. */
1597 if (e
->src
->succ
!= e
)
1600 for (e2
= bb
->pred
; e2
; e2
= nexte2
)
1602 nexte2
= e2
->pred_next
;
1607 /* We've already checked the fallthru edge above. */
1611 /* The "first successor" check above only prevents multiple
1612 checks of crossjump(A,B). In order to prevent redundant
1613 checks of crossjump(B,A), require that A be the block
1614 with the lowest index. */
1615 if (e
->src
->index
> e2
->src
->index
)
1618 if (try_crossjump_to_edge (mode
, e
, e2
))
1630 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1631 instructions etc. Return nonzero if changes were made. */
1634 try_optimize_cfg (int mode
)
1636 bool changed_overall
= false;
1639 basic_block bb
, b
, next
;
1641 if (mode
& CLEANUP_CROSSJUMP
)
1642 add_noreturn_fake_exit_edges ();
1645 update_forwarder_flag (bb
);
1647 if (mode
& CLEANUP_UPDATE_LIFE
)
1650 if (! (* targetm
.cannot_modify_jumps_p
) ())
1652 /* Attempt to merge blocks as made possible by edge removal. If
1653 a block has only one successor, and the successor has only
1654 one predecessor, they may be combined. */
1661 fprintf (rtl_dump_file
,
1662 "\n\ntry_optimize_cfg iteration %i\n\n",
1665 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
;)
1669 bool changed_here
= false;
1671 /* Delete trivially dead basic blocks. */
1672 while (b
->pred
== NULL
)
1676 fprintf (rtl_dump_file
, "Deleting block %i.\n",
1680 if (!(mode
& CLEANUP_CFGLAYOUT
))
1685 /* Remove code labels no longer used. Don't do this
1686 before CALL_PLACEHOLDER is removed, as some branches
1687 may be hidden within. */
1688 if (b
->pred
->pred_next
== NULL
1689 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1690 && !(b
->pred
->flags
& EDGE_COMPLEX
)
1691 && GET_CODE (BB_HEAD (b
)) == CODE_LABEL
1692 && (!(mode
& CLEANUP_PRE_SIBCALL
)
1693 || !tail_recursion_label_p (BB_HEAD (b
)))
1694 /* If the previous block ends with a branch to this
1695 block, we can't delete the label. Normally this
1696 is a condjump that is yet to be simplified, but
1697 if CASE_DROPS_THRU, this can be a tablejump with
1698 some element going to the same place as the
1699 default (fallthru). */
1700 && (b
->pred
->src
== ENTRY_BLOCK_PTR
1701 || GET_CODE (BB_END (b
->pred
->src
)) != JUMP_INSN
1702 || ! label_is_jump_target_p (BB_HEAD (b
),
1703 BB_END (b
->pred
->src
))))
1705 rtx label
= BB_HEAD (b
);
1707 delete_insn_chain (label
, label
);
1708 /* In the case label is undeletable, move it after the
1709 BASIC_BLOCK note. */
1710 if (NOTE_LINE_NUMBER (BB_HEAD (b
)) == NOTE_INSN_DELETED_LABEL
)
1712 rtx bb_note
= NEXT_INSN (BB_HEAD (b
));
1714 reorder_insns_nobb (label
, label
, bb_note
);
1715 BB_HEAD (b
) = bb_note
;
1718 fprintf (rtl_dump_file
, "Deleted label in block %i.\n",
1722 /* If we fall through an empty block, we can remove it. */
1723 if (!(mode
& CLEANUP_CFGLAYOUT
)
1724 && b
->pred
->pred_next
== NULL
1725 && (b
->pred
->flags
& EDGE_FALLTHRU
)
1726 && GET_CODE (BB_HEAD (b
)) != CODE_LABEL
1727 && FORWARDER_BLOCK_P (b
)
1728 /* Note that forwarder_block_p true ensures that
1729 there is a successor for this block. */
1730 && (b
->succ
->flags
& EDGE_FALLTHRU
)
1731 && n_basic_blocks
> 1)
1734 fprintf (rtl_dump_file
,
1735 "Deleting fallthru block %i.\n",
1738 c
= b
->prev_bb
== ENTRY_BLOCK_PTR
? b
->next_bb
: b
->prev_bb
;
1739 redirect_edge_succ_nodup (b
->pred
, b
->succ
->dest
);
1745 if ((s
= b
->succ
) != NULL
1746 && s
->succ_next
== NULL
1747 && !(s
->flags
& EDGE_COMPLEX
)
1748 && (c
= s
->dest
) != EXIT_BLOCK_PTR
1749 && c
->pred
->pred_next
== NULL
1752 /* When not in cfg_layout mode use code aware of reordering
1753 INSN. This code possibly creates new basic blocks so it
1754 does not fit merge_blocks interface and is kept here in
1755 hope that it will become useless once more of compiler
1756 is transformed to use cfg_layout mode. */
1758 if ((mode
& CLEANUP_CFGLAYOUT
)
1759 && can_merge_blocks_p (b
, c
))
1761 merge_blocks (b
, c
);
1762 update_forwarder_flag (b
);
1763 changed_here
= true;
1765 else if (!(mode
& CLEANUP_CFGLAYOUT
)
1766 /* If the jump insn has side effects,
1767 we can't kill the edge. */
1768 && (GET_CODE (BB_END (b
)) != JUMP_INSN
1769 || (reload_completed
1770 ? simplejump_p (BB_END (b
))
1771 : onlyjump_p (BB_END (b
))))
1772 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
1775 changed_here
= true;
1779 /* Simplify branch over branch. */
1780 if ((mode
& CLEANUP_EXPENSIVE
)
1781 && !(mode
& CLEANUP_CFGLAYOUT
)
1782 && try_simplify_condjump (b
))
1783 changed_here
= true;
1785 /* If B has a single outgoing edge, but uses a
1786 non-trivial jump instruction without side-effects, we
1787 can either delete the jump entirely, or replace it
1788 with a simple unconditional jump. */
1790 && ! b
->succ
->succ_next
1791 && b
->succ
->dest
!= EXIT_BLOCK_PTR
1792 && onlyjump_p (BB_END (b
))
1793 && try_redirect_by_replacing_jump (b
->succ
, b
->succ
->dest
,
1794 (mode
& CLEANUP_CFGLAYOUT
)))
1796 update_forwarder_flag (b
);
1797 changed_here
= true;
1800 /* Simplify branch to branch. */
1801 if (try_forward_edges (mode
, b
))
1802 changed_here
= true;
1804 /* Look for shared code between blocks. */
1805 if ((mode
& CLEANUP_CROSSJUMP
)
1806 && try_crossjump_bb (mode
, b
))
1807 changed_here
= true;
1809 /* Don't get confused by the index shift caused by
1817 if ((mode
& CLEANUP_CROSSJUMP
)
1818 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
1821 #ifdef ENABLE_CHECKING
1823 verify_flow_info ();
1826 changed_overall
|= changed
;
1831 if (mode
& CLEANUP_CROSSJUMP
)
1832 remove_fake_edges ();
1834 clear_aux_for_blocks ();
1836 return changed_overall
;
1839 /* Delete all unreachable basic blocks. */
1842 delete_unreachable_blocks (void)
1844 bool changed
= false;
1845 basic_block b
, next_bb
;
1847 find_unreachable_blocks ();
1849 /* Delete all unreachable basic blocks. */
1851 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
; b
= next_bb
)
1853 next_bb
= b
->next_bb
;
1855 if (!(b
->flags
& BB_REACHABLE
))
1863 tidy_fallthru_edges ();
1867 /* Tidy the CFG by deleting unreachable code and whatnot. */
1870 cleanup_cfg (int mode
)
1872 bool changed
= false;
1874 timevar_push (TV_CLEANUP_CFG
);
1875 if (delete_unreachable_blocks ())
1878 /* We've possibly created trivially dead code. Cleanup it right
1879 now to introduce more opportunities for try_optimize_cfg. */
1880 if (!(mode
& (CLEANUP_NO_INSN_DEL
1881 | CLEANUP_UPDATE_LIFE
| CLEANUP_PRE_SIBCALL
))
1882 && !reload_completed
)
1883 delete_trivially_dead_insns (get_insns(), max_reg_num ());
1888 while (try_optimize_cfg (mode
))
1890 delete_unreachable_blocks (), changed
= true;
1891 if (mode
& CLEANUP_UPDATE_LIFE
)
1893 /* Cleaning up CFG introduces more opportunities for dead code
1894 removal that in turn may introduce more opportunities for
1895 cleaning up the CFG. */
1896 if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES
,
1898 | PROP_SCAN_DEAD_CODE
1899 | PROP_KILL_DEAD_CODE
1903 else if (!(mode
& (CLEANUP_NO_INSN_DEL
| CLEANUP_PRE_SIBCALL
))
1904 && (mode
& CLEANUP_EXPENSIVE
)
1905 && !reload_completed
)
1907 if (!delete_trivially_dead_insns (get_insns(), max_reg_num ()))
1912 delete_dead_jumptables ();
1915 /* Kill the data we won't maintain. */
1916 free_EXPR_LIST_list (&label_value_list
);
1917 timevar_pop (TV_CLEANUP_CFG
);