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, 2004 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"
53 /* cleanup_cfg maintains following flags for each basic block. */
57 /* Set if BB is the forwarder block to avoid too many
58 forwarder_block_p calls. */
59 BB_FORWARDER_BLOCK = 1,
60 BB_NONTHREADABLE_BLOCK = 2
63 #define BB_FLAGS(BB) (enum bb_flags) (BB)->aux
64 #define BB_SET_FLAG(BB, FLAG) \
65 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux | (FLAG))
66 #define BB_CLEAR_FLAG(BB, FLAG) \
67 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux & ~(FLAG))
69 #define FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK)
71 /* Set to true when we are running first pass of try_optimize_cfg loop. */
72 static bool first_pass;
73 static bool try_crossjump_to_edge (int, edge, edge);
74 static bool try_crossjump_bb (int, basic_block);
75 static bool outgoing_edges_match (int, basic_block, basic_block);
76 static int flow_find_cross_jump (int, basic_block, basic_block, rtx *, rtx *);
77 static bool insns_match_p (int, rtx, rtx);
79 static bool tail_recursion_label_p (rtx);
80 static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
81 static void merge_blocks_move_successor_nojumps (basic_block, basic_block);
82 static bool try_optimize_cfg (int);
83 static bool try_simplify_condjump (basic_block);
84 static bool try_forward_edges (int, basic_block);
85 static edge thread_jump (int, edge, basic_block);
86 static bool mark_effect (rtx, bitmap);
87 static void notice_new_block (basic_block);
88 static void update_forwarder_flag (basic_block);
89 static int mentions_nonequal_regs (rtx *, void *);
91 /* Set flags for newly created block. */
94 notice_new_block (basic_block bb)
99 if (forwarder_block_p (bb))
100 BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
103 /* Recompute forwarder flag after block has been modified. */
106 update_forwarder_flag (basic_block bb)
108 if (forwarder_block_p (bb))
109 BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
111 BB_CLEAR_FLAG (bb, BB_FORWARDER_BLOCK);
114 /* Simplify a conditional jump around an unconditional jump.
115 Return true if something changed. */
118 try_simplify_condjump (basic_block cbranch_block)
120 basic_block jump_block, jump_dest_block, cbranch_dest_block;
121 edge cbranch_jump_edge, cbranch_fallthru_edge;
126 /* Verify that there are exactly two successors. */
127 if (!cbranch_block->succ
128 || !cbranch_block->succ->succ_next
129 || cbranch_block->succ->succ_next->succ_next)
132 /* Verify that we've got a normal conditional branch at the end
134 cbranch_insn = BB_END (cbranch_block);
135 if (!any_condjump_p (cbranch_insn))
138 cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
139 cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
141 /* The next block must not have multiple predecessors, must not
142 be the last block in the function, and must contain just the
143 unconditional jump. */
144 jump_block = cbranch_fallthru_edge->dest;
145 if (jump_block->pred->pred_next
146 || jump_block->next_bb == EXIT_BLOCK_PTR
147 || !FORWARDER_BLOCK_P (jump_block))
149 jump_dest_block = jump_block->succ->dest;
151 /* The conditional branch must target the block after the
152 unconditional branch. */
153 cbranch_dest_block = cbranch_jump_edge->dest;
155 if (!can_fallthru (jump_block, cbranch_dest_block))
158 /* Invert the conditional branch. */
159 if (!invert_jump (cbranch_insn, block_label (jump_dest_block), 0))
163 fprintf (rtl_dump_file, "Simplifying condjump %i around jump %i\n",
164 INSN_UID (cbranch_insn), INSN_UID (BB_END (jump_block)));
166 /* Success. Update the CFG to match. Note that after this point
167 the edge variable names appear backwards; the redirection is done
168 this way to preserve edge profile data. */
169 cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
171 cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
173 cbranch_jump_edge->flags |= EDGE_FALLTHRU;
174 cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
175 update_br_prob_note (cbranch_block);
177 end = BB_END (jump_block);
178 /* Deleting a block may produce unreachable code warning even when we are
179 not deleting anything live. Suppress it by moving all the line number
180 notes out of the block. */
181 for (insn = BB_HEAD (jump_block); insn != NEXT_INSN (BB_END (jump_block));
184 next = NEXT_INSN (insn);
185 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
187 if (insn == BB_END (jump_block))
189 BB_END (jump_block) = PREV_INSN (insn);
193 reorder_insns_nobb (insn, insn, end);
197 /* Delete the block with the unconditional jump, and clean up the mess. */
198 delete_basic_block (jump_block);
199 tidy_fallthru_edge (cbranch_jump_edge);
204 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
205 on register. Used by jump threading. */
208 mark_effect (rtx exp, regset nonequal)
212 switch (GET_CODE (exp))
214 /* In case we do clobber the register, mark it as equal, as we know the
215 value is dead so it don't have to match. */
217 if (REG_P (XEXP (exp, 0)))
219 dest = XEXP (exp, 0);
220 regno = REGNO (dest);
221 CLEAR_REGNO_REG_SET (nonequal, regno);
222 if (regno < FIRST_PSEUDO_REGISTER)
224 int n = hard_regno_nregs[regno][GET_MODE (dest)];
226 CLEAR_REGNO_REG_SET (nonequal, regno + n);
232 if (rtx_equal_for_cselib_p (SET_DEST (exp), SET_SRC (exp)))
234 dest = SET_DEST (exp);
239 regno = REGNO (dest);
240 SET_REGNO_REG_SET (nonequal, regno);
241 if (regno < FIRST_PSEUDO_REGISTER)
243 int n = hard_regno_nregs[regno][GET_MODE (dest)];
245 SET_REGNO_REG_SET (nonequal, regno + n);
254 /* Return nonzero if X is a register set in regset DATA.
255 Called via for_each_rtx. */
257 mentions_nonequal_regs (rtx *x, void *data)
259 regset nonequal = (regset) data;
265 if (REGNO_REG_SET_P (nonequal, regno))
267 if (regno < FIRST_PSEUDO_REGISTER)
269 int n = hard_regno_nregs[regno][GET_MODE (*x)];
271 if (REGNO_REG_SET_P (nonequal, regno + n))
277 /* Attempt to prove that the basic block B will have no side effects and
278 always continues in the same edge if reached via E. Return the edge
279 if exist, NULL otherwise. */
282 thread_jump (int mode, edge e, basic_block b)
284 rtx set1, set2, cond1, cond2, insn;
285 enum rtx_code code1, code2, reversed_code2;
286 bool reverse1 = false;
291 if (BB_FLAGS (b) & BB_NONTHREADABLE_BLOCK)
294 /* At the moment, we do handle only conditional jumps, but later we may
295 want to extend this code to tablejumps and others. */
296 if (!e->src->succ->succ_next || e->src->succ->succ_next->succ_next)
298 if (!b->succ || !b->succ->succ_next || b->succ->succ_next->succ_next)
300 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
304 /* Second branch must end with onlyjump, as we will eliminate the jump. */
305 if (!any_condjump_p (BB_END (e->src)))
308 if (!any_condjump_p (BB_END (b)) || !onlyjump_p (BB_END (b)))
310 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
314 set1 = pc_set (BB_END (e->src));
315 set2 = pc_set (BB_END (b));
316 if (((e->flags & EDGE_FALLTHRU) != 0)
317 != (XEXP (SET_SRC (set1), 1) == pc_rtx))
320 cond1 = XEXP (SET_SRC (set1), 0);
321 cond2 = XEXP (SET_SRC (set2), 0);
323 code1 = reversed_comparison_code (cond1, BB_END (e->src));
325 code1 = GET_CODE (cond1);
327 code2 = GET_CODE (cond2);
328 reversed_code2 = reversed_comparison_code (cond2, BB_END (b));
330 if (!comparison_dominates_p (code1, code2)
331 && !comparison_dominates_p (code1, reversed_code2))
334 /* Ensure that the comparison operators are equivalent.
335 ??? This is far too pessimistic. We should allow swapped operands,
336 different CCmodes, or for example comparisons for interval, that
337 dominate even when operands are not equivalent. */
338 if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
339 || !rtx_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
342 /* Short circuit cases where block B contains some side effects, as we can't
344 for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b));
345 insn = NEXT_INSN (insn))
346 if (INSN_P (insn) && side_effects_p (PATTERN (insn)))
348 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
354 /* First process all values computed in the source basic block. */
355 for (insn = NEXT_INSN (BB_HEAD (e->src)); insn != NEXT_INSN (BB_END (e->src));
356 insn = NEXT_INSN (insn))
358 cselib_process_insn (insn);
360 nonequal = BITMAP_XMALLOC();
361 CLEAR_REG_SET (nonequal);
363 /* Now assume that we've continued by the edge E to B and continue
364 processing as if it were same basic block.
365 Our goal is to prove that whole block is an NOOP. */
367 for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b)) && !failed;
368 insn = NEXT_INSN (insn))
372 rtx pat = PATTERN (insn);
374 if (GET_CODE (pat) == PARALLEL)
376 for (i = 0; i < XVECLEN (pat, 0); i++)
377 failed |= mark_effect (XVECEXP (pat, 0, i), nonequal);
380 failed |= mark_effect (pat, nonequal);
383 cselib_process_insn (insn);
386 /* Later we should clear nonequal of dead registers. So far we don't
387 have life information in cfg_cleanup. */
390 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
394 /* cond2 must not mention any register that is not equal to the
396 if (for_each_rtx (&cond2, mentions_nonequal_regs, nonequal))
399 /* In case liveness information is available, we need to prove equivalence
400 only of the live values. */
401 if (mode & CLEANUP_UPDATE_LIFE)
402 AND_REG_SET (nonequal, b->global_live_at_end);
404 EXECUTE_IF_SET_IN_REG_SET (nonequal, 0, i, goto failed_exit;);
406 BITMAP_XFREE (nonequal);
408 if ((comparison_dominates_p (code1, code2) != 0)
409 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
410 return BRANCH_EDGE (b);
412 return FALLTHRU_EDGE (b);
415 BITMAP_XFREE (nonequal);
420 /* Attempt to forward edges leaving basic block B.
421 Return true if successful. */
424 try_forward_edges (int mode, basic_block b)
426 bool changed = false;
427 edge e, next, *threaded_edges = NULL;
429 for (e = b->succ; e; e = next)
431 basic_block target, first;
433 bool threaded = false;
434 int nthreaded_edges = 0;
435 bool may_thread = first_pass | (b->flags & BB_DIRTY);
439 /* Skip complex edges because we don't know how to update them.
441 Still handle fallthru edges, as we can succeed to forward fallthru
442 edge to the same place as the branch edge of conditional branch
443 and turn conditional branch to an unconditional branch. */
444 if (e->flags & EDGE_COMPLEX)
447 target = first = e->dest;
450 while (counter < n_basic_blocks)
452 basic_block new_target = NULL;
453 bool new_target_threaded = false;
454 may_thread |= target->flags & BB_DIRTY;
456 if (FORWARDER_BLOCK_P (target)
457 && target->succ->dest != EXIT_BLOCK_PTR)
459 /* Bypass trivial infinite loops. */
460 if (target == target->succ->dest)
461 counter = n_basic_blocks;
462 new_target = target->succ->dest;
465 /* Allow to thread only over one edge at time to simplify updating
467 else if ((mode & CLEANUP_THREADING) && may_thread)
469 edge t = thread_jump (mode, e, target);
473 threaded_edges = xmalloc (sizeof (*threaded_edges)
479 /* Detect an infinite loop across blocks not
480 including the start block. */
481 for (i = 0; i < nthreaded_edges; ++i)
482 if (threaded_edges[i] == t)
484 if (i < nthreaded_edges)
486 counter = n_basic_blocks;
491 /* Detect an infinite loop across the start block. */
495 if (nthreaded_edges >= n_basic_blocks)
497 threaded_edges[nthreaded_edges++] = t;
499 new_target = t->dest;
500 new_target_threaded = true;
507 /* Avoid killing of loop pre-headers, as it is the place loop
508 optimizer wants to hoist code to.
510 For fallthru forwarders, the LOOP_BEG note must appear between
511 the header of block and CODE_LABEL of the loop, for non forwarders
512 it must appear before the JUMP_INSN. */
513 if ((mode & CLEANUP_PRE_LOOP) && optimize)
515 rtx insn = (target->succ->flags & EDGE_FALLTHRU
516 ? BB_HEAD (target) : prev_nonnote_insn (BB_END (target)));
518 if (GET_CODE (insn) != NOTE)
519 insn = NEXT_INSN (insn);
521 for (; insn && GET_CODE (insn) != CODE_LABEL && !INSN_P (insn);
522 insn = NEXT_INSN (insn))
523 if (GET_CODE (insn) == NOTE
524 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
527 if (GET_CODE (insn) == NOTE)
530 /* Do not clean up branches to just past the end of a loop
531 at this time; it can mess up the loop optimizer's
532 recognition of some patterns. */
534 insn = PREV_INSN (BB_HEAD (target));
535 if (insn && GET_CODE (insn) == NOTE
536 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
542 threaded |= new_target_threaded;
545 if (counter >= n_basic_blocks)
548 fprintf (rtl_dump_file, "Infinite loop in BB %i.\n",
551 else if (target == first)
552 ; /* We didn't do anything. */
555 /* Save the values now, as the edge may get removed. */
556 gcov_type edge_count = e->count;
557 int edge_probability = e->probability;
561 /* Don't force if target is exit block. */
562 if (threaded && target != EXIT_BLOCK_PTR)
564 notice_new_block (redirect_edge_and_branch_force (e, target));
566 fprintf (rtl_dump_file, "Conditionals threaded.\n");
568 else if (!redirect_edge_and_branch (e, target))
571 fprintf (rtl_dump_file,
572 "Forwarding edge %i->%i to %i failed.\n",
573 b->index, e->dest->index, target->index);
577 /* We successfully forwarded the edge. Now update profile
578 data: for each edge we traversed in the chain, remove
579 the original edge's execution count. */
580 edge_frequency = ((edge_probability * b->frequency
581 + REG_BR_PROB_BASE / 2)
584 if (!FORWARDER_BLOCK_P (b) && forwarder_block_p (b))
585 BB_SET_FLAG (b, BB_FORWARDER_BLOCK);
591 first->count -= edge_count;
592 if (first->count < 0)
594 first->frequency -= edge_frequency;
595 if (first->frequency < 0)
596 first->frequency = 0;
597 if (first->succ->succ_next)
601 if (n >= nthreaded_edges)
603 t = threaded_edges [n++];
606 if (first->frequency)
607 prob = edge_frequency * REG_BR_PROB_BASE / first->frequency;
610 if (prob > t->probability)
611 prob = t->probability;
612 t->probability -= prob;
613 prob = REG_BR_PROB_BASE - prob;
616 first->succ->probability = REG_BR_PROB_BASE;
617 first->succ->succ_next->probability = 0;
620 for (e = first->succ; e; e = e->succ_next)
621 e->probability = ((e->probability * REG_BR_PROB_BASE)
623 update_br_prob_note (first);
627 /* It is possible that as the result of
628 threading we've removed edge as it is
629 threaded to the fallthru edge. Avoid
630 getting out of sync. */
631 if (n < nthreaded_edges
632 && first == threaded_edges [n]->src)
637 t->count -= edge_count;
642 while (first != target);
649 free (threaded_edges);
653 /* Return true if LABEL is used for tail recursion. */
656 tail_recursion_label_p (rtx label)
660 for (x = tail_recursion_label_list; x; x = XEXP (x, 1))
661 if (label == XEXP (x, 0))
667 /* Blocks A and B are to be merged into a single block. A has no incoming
668 fallthru edge, so it can be moved before B without adding or modifying
669 any jumps (aside from the jump from A to B). */
672 merge_blocks_move_predecessor_nojumps (basic_block a, basic_block b)
676 barrier = next_nonnote_insn (BB_END (a));
677 if (GET_CODE (barrier) != BARRIER)
679 delete_insn (barrier);
681 /* Move block and loop notes out of the chain so that we do not
684 ??? A better solution would be to squeeze out all the non-nested notes
685 and adjust the block trees appropriately. Even better would be to have
686 a tighter connection between block trees and rtl so that this is not
688 if (squeeze_notes (&BB_HEAD (a), &BB_END (a)))
691 /* Scramble the insn chain. */
692 if (BB_END (a) != PREV_INSN (BB_HEAD (b)))
693 reorder_insns_nobb (BB_HEAD (a), BB_END (a), PREV_INSN (BB_HEAD (b)));
694 a->flags |= BB_DIRTY;
697 fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
700 /* Swap the records for the two blocks around. */
703 link_block (a, b->prev_bb);
705 /* Now blocks A and B are contiguous. Merge them. */
709 /* Blocks A and B are to be merged into a single block. B has no outgoing
710 fallthru edge, so it can be moved after A without adding or modifying
711 any jumps (aside from the jump from A to B). */
714 merge_blocks_move_successor_nojumps (basic_block a, basic_block b)
716 rtx barrier, real_b_end;
719 real_b_end = BB_END (b);
721 /* If there is a jump table following block B temporarily add the jump table
722 to block B so that it will also be moved to the correct location. */
723 if (tablejump_p (BB_END (b), &label, &table)
724 && prev_active_insn (label) == BB_END (b))
729 /* There had better have been a barrier there. Delete it. */
730 barrier = NEXT_INSN (BB_END (b));
731 if (barrier && GET_CODE (barrier) == BARRIER)
732 delete_insn (barrier);
734 /* Move block and loop notes out of the chain so that we do not
737 ??? A better solution would be to squeeze out all the non-nested notes
738 and adjust the block trees appropriately. Even better would be to have
739 a tighter connection between block trees and rtl so that this is not
741 if (squeeze_notes (&BB_HEAD (b), &BB_END (b)))
744 /* Scramble the insn chain. */
745 reorder_insns_nobb (BB_HEAD (b), BB_END (b), BB_END (a));
747 /* Restore the real end of b. */
748 BB_END (b) = real_b_end;
751 fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
754 /* Now blocks A and B are contiguous. Merge them. */
758 /* Attempt to merge basic blocks that are potentially non-adjacent.
759 Return NULL iff the attempt failed, otherwise return basic block
760 where cleanup_cfg should continue. Because the merging commonly
761 moves basic block away or introduces another optimization
762 possibility, return basic block just before B so cleanup_cfg don't
765 It may be good idea to return basic block before C in the case
766 C has been moved after B and originally appeared earlier in the
767 insn sequence, but we have no information available about the
768 relative ordering of these two. Hopefully it is not too common. */
771 merge_blocks_move (edge e, basic_block b, basic_block c, int mode)
774 /* If C has a tail recursion label, do not merge. There is no
775 edge recorded from the call_placeholder back to this label, as
776 that would make optimize_sibling_and_tail_recursive_calls more
777 complex for no gain. */
778 if ((mode & CLEANUP_PRE_SIBCALL)
779 && GET_CODE (BB_HEAD (c)) == CODE_LABEL
780 && tail_recursion_label_p (BB_HEAD (c)))
783 /* If B has a fallthru edge to C, no need to move anything. */
784 if (e->flags & EDGE_FALLTHRU)
786 int b_index = b->index, c_index = c->index;
788 update_forwarder_flag (b);
791 fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
794 return b->prev_bb == ENTRY_BLOCK_PTR ? b : b->prev_bb;
797 /* Otherwise we will need to move code around. Do that only if expensive
798 transformations are allowed. */
799 else if (mode & CLEANUP_EXPENSIVE)
801 edge tmp_edge, b_fallthru_edge;
802 bool c_has_outgoing_fallthru;
803 bool b_has_incoming_fallthru;
805 /* Avoid overactive code motion, as the forwarder blocks should be
806 eliminated by edge redirection instead. One exception might have
807 been if B is a forwarder block and C has no fallthru edge, but
808 that should be cleaned up by bb-reorder instead. */
809 if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
812 /* We must make sure to not munge nesting of lexical blocks,
813 and loop notes. This is done by squeezing out all the notes
814 and leaving them there to lie. Not ideal, but functional. */
816 for (tmp_edge = c->succ; tmp_edge; tmp_edge = tmp_edge->succ_next)
817 if (tmp_edge->flags & EDGE_FALLTHRU)
820 c_has_outgoing_fallthru = (tmp_edge != NULL);
822 for (tmp_edge = b->pred; tmp_edge; tmp_edge = tmp_edge->pred_next)
823 if (tmp_edge->flags & EDGE_FALLTHRU)
826 b_has_incoming_fallthru = (tmp_edge != NULL);
827 b_fallthru_edge = tmp_edge;
830 next = next->prev_bb;
832 /* Otherwise, we're going to try to move C after B. If C does
833 not have an outgoing fallthru, then it can be moved
834 immediately after B without introducing or modifying jumps. */
835 if (! c_has_outgoing_fallthru)
837 merge_blocks_move_successor_nojumps (b, c);
838 return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
841 /* If B does not have an incoming fallthru, then it can be moved
842 immediately before C without introducing or modifying jumps.
843 C cannot be the first block, so we do not have to worry about
844 accessing a non-existent block. */
846 if (b_has_incoming_fallthru)
850 if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
852 bb = force_nonfallthru (b_fallthru_edge);
854 notice_new_block (bb);
857 merge_blocks_move_predecessor_nojumps (b, c);
858 return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
865 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
868 insns_match_p (int mode ATTRIBUTE_UNUSED, rtx i1, rtx i2)
872 /* Verify that I1 and I2 are equivalent. */
873 if (GET_CODE (i1) != GET_CODE (i2))
879 if (GET_CODE (p1) != GET_CODE (p2))
882 /* If this is a CALL_INSN, compare register usage information.
883 If we don't check this on stack register machines, the two
884 CALL_INSNs might be merged leaving reg-stack.c with mismatching
885 numbers of stack registers in the same basic block.
886 If we don't check this on machines with delay slots, a delay slot may
887 be filled that clobbers a parameter expected by the subroutine.
889 ??? We take the simple route for now and assume that if they're
890 equal, they were constructed identically. */
892 if (GET_CODE (i1) == CALL_INSN
893 && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
894 CALL_INSN_FUNCTION_USAGE (i2))
895 || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)))
899 /* If cross_jump_death_matters is not 0, the insn's mode
900 indicates whether or not the insn contains any stack-like
903 if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
905 /* If register stack conversion has already been done, then
906 death notes must also be compared before it is certain that
907 the two instruction streams match. */
910 HARD_REG_SET i1_regset, i2_regset;
912 CLEAR_HARD_REG_SET (i1_regset);
913 CLEAR_HARD_REG_SET (i2_regset);
915 for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
916 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
917 SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
919 for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
920 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
921 SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
923 GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
933 ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
936 /* Do not do EQUIV substitution after reload. First, we're undoing the
937 work of reload_cse. Second, we may be undoing the work of the post-
938 reload splitting pass. */
939 /* ??? Possibly add a new phase switch variable that can be used by
940 targets to disallow the troublesome insns after splitting. */
941 if (!reload_completed)
943 /* The following code helps take care of G++ cleanups. */
944 rtx equiv1 = find_reg_equal_equiv_note (i1);
945 rtx equiv2 = find_reg_equal_equiv_note (i2);
948 /* If the equivalences are not to a constant, they may
949 reference pseudos that no longer exist, so we can't
951 && (! reload_completed
952 || (CONSTANT_P (XEXP (equiv1, 0))
953 && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
955 rtx s1 = single_set (i1);
956 rtx s2 = single_set (i2);
957 if (s1 != 0 && s2 != 0
958 && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
960 validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
961 validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
962 if (! rtx_renumbered_equal_p (p1, p2))
964 else if (apply_change_group ())
973 /* Look through the insns at the end of BB1 and BB2 and find the longest
974 sequence that are equivalent. Store the first insns for that sequence
975 in *F1 and *F2 and return the sequence length.
977 To simplify callers of this function, if the blocks match exactly,
978 store the head of the blocks in *F1 and *F2. */
981 flow_find_cross_jump (int mode ATTRIBUTE_UNUSED, basic_block bb1,
982 basic_block bb2, rtx *f1, rtx *f2)
984 rtx i1, i2, last1, last2, afterlast1, afterlast2;
987 /* Skip simple jumps at the end of the blocks. Complex jumps still
988 need to be compared for equivalence, which we'll do below. */
991 last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
993 || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
1001 || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
1004 /* Count everything except for unconditional jump as insn. */
1005 if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
1007 i2 = PREV_INSN (i2);
1013 while (!INSN_P (i1) && i1 != BB_HEAD (bb1))
1014 i1 = PREV_INSN (i1);
1016 while (!INSN_P (i2) && i2 != BB_HEAD (bb2))
1017 i2 = PREV_INSN (i2);
1019 if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
1022 if (!insns_match_p (mode, i1, i2))
1025 /* Don't begin a cross-jump with a NOTE insn. */
1028 /* If the merged insns have different REG_EQUAL notes, then
1030 rtx equiv1 = find_reg_equal_equiv_note (i1);
1031 rtx equiv2 = find_reg_equal_equiv_note (i2);
1033 if (equiv1 && !equiv2)
1034 remove_note (i1, equiv1);
1035 else if (!equiv1 && equiv2)
1036 remove_note (i2, equiv2);
1037 else if (equiv1 && equiv2
1038 && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
1040 remove_note (i1, equiv1);
1041 remove_note (i2, equiv2);
1044 afterlast1 = last1, afterlast2 = last2;
1045 last1 = i1, last2 = i2;
1049 i1 = PREV_INSN (i1);
1050 i2 = PREV_INSN (i2);
1054 /* Don't allow the insn after a compare to be shared by
1055 cross-jumping unless the compare is also shared. */
1056 if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
1057 last1 = afterlast1, last2 = afterlast2, ninsns--;
1060 /* Include preceding notes and labels in the cross-jump. One,
1061 this may bring us to the head of the blocks as requested above.
1062 Two, it keeps line number notes as matched as may be. */
1065 while (last1 != BB_HEAD (bb1) && !INSN_P (PREV_INSN (last1)))
1066 last1 = PREV_INSN (last1);
1068 if (last1 != BB_HEAD (bb1) && GET_CODE (PREV_INSN (last1)) == CODE_LABEL)
1069 last1 = PREV_INSN (last1);
1071 while (last2 != BB_HEAD (bb2) && !INSN_P (PREV_INSN (last2)))
1072 last2 = PREV_INSN (last2);
1074 if (last2 != BB_HEAD (bb2) && GET_CODE (PREV_INSN (last2)) == CODE_LABEL)
1075 last2 = PREV_INSN (last2);
1084 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1085 the branch instruction. This means that if we commonize the control
1086 flow before end of the basic block, the semantic remains unchanged.
1088 We may assume that there exists one edge with a common destination. */
1091 outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
1093 int nehedges1 = 0, nehedges2 = 0;
1094 edge fallthru1 = 0, fallthru2 = 0;
1097 /* If BB1 has only one successor, we may be looking at either an
1098 unconditional jump, or a fake edge to exit. */
1099 if (bb1->succ && !bb1->succ->succ_next
1100 && (bb1->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1101 && (GET_CODE (BB_END (bb1)) != JUMP_INSN || simplejump_p (BB_END (bb1))))
1102 return (bb2->succ && !bb2->succ->succ_next
1103 && (bb2->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1104 && (GET_CODE (BB_END (bb2)) != JUMP_INSN || simplejump_p (BB_END (bb2))));
1106 /* Match conditional jumps - this may get tricky when fallthru and branch
1107 edges are crossed. */
1109 && bb1->succ->succ_next
1110 && !bb1->succ->succ_next->succ_next
1111 && any_condjump_p (BB_END (bb1))
1112 && onlyjump_p (BB_END (bb1)))
1114 edge b1, f1, b2, f2;
1115 bool reverse, match;
1116 rtx set1, set2, cond1, cond2;
1117 enum rtx_code code1, code2;
1120 || !bb2->succ->succ_next
1121 || bb2->succ->succ_next->succ_next
1122 || !any_condjump_p (BB_END (bb2))
1123 || !onlyjump_p (BB_END (bb2)))
1126 b1 = BRANCH_EDGE (bb1);
1127 b2 = BRANCH_EDGE (bb2);
1128 f1 = FALLTHRU_EDGE (bb1);
1129 f2 = FALLTHRU_EDGE (bb2);
1131 /* Get around possible forwarders on fallthru edges. Other cases
1132 should be optimized out already. */
1133 if (FORWARDER_BLOCK_P (f1->dest))
1134 f1 = f1->dest->succ;
1136 if (FORWARDER_BLOCK_P (f2->dest))
1137 f2 = f2->dest->succ;
1139 /* To simplify use of this function, return false if there are
1140 unneeded forwarder blocks. These will get eliminated later
1141 during cleanup_cfg. */
1142 if (FORWARDER_BLOCK_P (f1->dest)
1143 || FORWARDER_BLOCK_P (f2->dest)
1144 || FORWARDER_BLOCK_P (b1->dest)
1145 || FORWARDER_BLOCK_P (b2->dest))
1148 if (f1->dest == f2->dest && b1->dest == b2->dest)
1150 else if (f1->dest == b2->dest && b1->dest == f2->dest)
1155 set1 = pc_set (BB_END (bb1));
1156 set2 = pc_set (BB_END (bb2));
1157 if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
1158 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
1161 cond1 = XEXP (SET_SRC (set1), 0);
1162 cond2 = XEXP (SET_SRC (set2), 0);
1163 code1 = GET_CODE (cond1);
1165 code2 = reversed_comparison_code (cond2, BB_END (bb2));
1167 code2 = GET_CODE (cond2);
1169 if (code2 == UNKNOWN)
1172 /* Verify codes and operands match. */
1173 match = ((code1 == code2
1174 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
1175 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
1176 || (code1 == swap_condition (code2)
1177 && rtx_renumbered_equal_p (XEXP (cond1, 1),
1179 && rtx_renumbered_equal_p (XEXP (cond1, 0),
1182 /* If we return true, we will join the blocks. Which means that
1183 we will only have one branch prediction bit to work with. Thus
1184 we require the existing branches to have probabilities that are
1188 && maybe_hot_bb_p (bb1)
1189 && maybe_hot_bb_p (bb2))
1193 if (b1->dest == b2->dest)
1194 prob2 = b2->probability;
1196 /* Do not use f2 probability as f2 may be forwarded. */
1197 prob2 = REG_BR_PROB_BASE - b2->probability;
1199 /* Fail if the difference in probabilities is greater than 50%.
1200 This rules out two well-predicted branches with opposite
1202 if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
1205 fprintf (rtl_dump_file,
1206 "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
1207 bb1->index, bb2->index, b1->probability, prob2);
1213 if (rtl_dump_file && match)
1214 fprintf (rtl_dump_file, "Conditionals in bb %i and %i match.\n",
1215 bb1->index, bb2->index);
1220 /* Generic case - we are seeing a computed jump, table jump or trapping
1223 #ifndef CASE_DROPS_THROUGH
1224 /* Check whether there are tablejumps in the end of BB1 and BB2.
1225 Return true if they are identical. */
1230 if (tablejump_p (BB_END (bb1), &label1, &table1)
1231 && tablejump_p (BB_END (bb2), &label2, &table2)
1232 && GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2)))
1234 /* The labels should never be the same rtx. If they really are same
1235 the jump tables are same too. So disable crossjumping of blocks BB1
1236 and BB2 because when deleting the common insns in the end of BB1
1237 by delete_block () the jump table would be deleted too. */
1238 /* If LABEL2 is referenced in BB1->END do not do anything
1239 because we would loose information when replacing
1240 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1241 if (label1 != label2 && !rtx_referenced_p (label2, BB_END (bb1)))
1243 /* Set IDENTICAL to true when the tables are identical. */
1244 bool identical = false;
1247 p1 = PATTERN (table1);
1248 p2 = PATTERN (table2);
1249 if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2))
1253 else if (GET_CODE (p1) == ADDR_DIFF_VEC
1254 && (XVECLEN (p1, 1) == XVECLEN (p2, 1))
1255 && rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2))
1256 && rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3)))
1261 for (i = XVECLEN (p1, 1) - 1; i >= 0 && identical; i--)
1262 if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i)))
1268 replace_label_data rr;
1271 /* Temporarily replace references to LABEL1 with LABEL2
1272 in BB1->END so that we could compare the instructions. */
1275 rr.update_label_nuses = false;
1276 for_each_rtx (&BB_END (bb1), replace_label, &rr);
1278 match = insns_match_p (mode, BB_END (bb1), BB_END (bb2));
1279 if (rtl_dump_file && match)
1280 fprintf (rtl_dump_file,
1281 "Tablejumps in bb %i and %i match.\n",
1282 bb1->index, bb2->index);
1284 /* Set the original label in BB1->END because when deleting
1285 a block whose end is a tablejump, the tablejump referenced
1286 from the instruction is deleted too. */
1289 for_each_rtx (&BB_END (bb1), replace_label, &rr);
1299 /* First ensure that the instructions match. There may be many outgoing
1300 edges so this test is generally cheaper. */
1301 if (!insns_match_p (mode, BB_END (bb1), BB_END (bb2)))
1304 /* Search the outgoing edges, ensure that the counts do match, find possible
1305 fallthru and exception handling edges since these needs more
1307 for (e1 = bb1->succ, e2 = bb2->succ; e1 && e2;
1308 e1 = e1->succ_next, e2 = e2->succ_next)
1310 if (e1->flags & EDGE_EH)
1313 if (e2->flags & EDGE_EH)
1316 if (e1->flags & EDGE_FALLTHRU)
1318 if (e2->flags & EDGE_FALLTHRU)
1322 /* If number of edges of various types does not match, fail. */
1324 || nehedges1 != nehedges2
1325 || (fallthru1 != 0) != (fallthru2 != 0))
1328 /* fallthru edges must be forwarded to the same destination. */
1331 basic_block d1 = (forwarder_block_p (fallthru1->dest)
1332 ? fallthru1->dest->succ->dest: fallthru1->dest);
1333 basic_block d2 = (forwarder_block_p (fallthru2->dest)
1334 ? fallthru2->dest->succ->dest: fallthru2->dest);
1340 /* Ensure the same EH region. */
1342 rtx n1 = find_reg_note (BB_END (bb1), REG_EH_REGION, 0);
1343 rtx n2 = find_reg_note (BB_END (bb2), REG_EH_REGION, 0);
1348 if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
1352 /* We don't need to match the rest of edges as above checks should be enough
1353 to ensure that they are equivalent. */
1357 /* E1 and E2 are edges with the same destination block. Search their
1358 predecessors for common code. If found, redirect control flow from
1359 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1362 try_crossjump_to_edge (int mode, edge e1, edge e2)
1365 basic_block src1 = e1->src, src2 = e2->src;
1366 basic_block redirect_to, redirect_from, to_remove;
1367 rtx newpos1, newpos2;
1370 /* Search backward through forwarder blocks. We don't need to worry
1371 about multiple entry or chained forwarders, as they will be optimized
1372 away. We do this to look past the unconditional jump following a
1373 conditional jump that is required due to the current CFG shape. */
1375 && !src1->pred->pred_next
1376 && FORWARDER_BLOCK_P (src1))
1377 e1 = src1->pred, src1 = e1->src;
1380 && !src2->pred->pred_next
1381 && FORWARDER_BLOCK_P (src2))
1382 e2 = src2->pred, src2 = e2->src;
1384 /* Nothing to do if we reach ENTRY, or a common source block. */
1385 if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
1390 /* Seeing more than 1 forwarder blocks would confuse us later... */
1391 if (FORWARDER_BLOCK_P (e1->dest)
1392 && FORWARDER_BLOCK_P (e1->dest->succ->dest))
1395 if (FORWARDER_BLOCK_P (e2->dest)
1396 && FORWARDER_BLOCK_P (e2->dest->succ->dest))
1399 /* Likewise with dead code (possibly newly created by the other optimizations
1401 if (!src1->pred || !src2->pred)
1404 /* Look for the common insn sequence, part the first ... */
1405 if (!outgoing_edges_match (mode, src1, src2))
1408 /* ... and part the second. */
1409 nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
1413 #ifndef CASE_DROPS_THROUGH
1414 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1416 If we have tablejumps in the end of SRC1 and SRC2
1417 they have been already compared for equivalence in outgoing_edges_match ()
1418 so replace the references to TABLE1 by references to TABLE2. */
1423 if (tablejump_p (BB_END (src1), &label1, &table1)
1424 && tablejump_p (BB_END (src2), &label2, &table2)
1425 && label1 != label2)
1427 replace_label_data rr;
1430 /* Replace references to LABEL1 with LABEL2. */
1433 rr.update_label_nuses = true;
1434 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1436 /* Do not replace the label in SRC1->END because when deleting
1437 a block whose end is a tablejump, the tablejump referenced
1438 from the instruction is deleted too. */
1439 if (insn != BB_END (src1))
1440 for_each_rtx (&insn, replace_label, &rr);
1446 /* Avoid splitting if possible. */
1447 if (newpos2 == BB_HEAD (src2))
1452 fprintf (rtl_dump_file, "Splitting bb %i before %i insns\n",
1453 src2->index, nmatch);
1454 redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
1458 fprintf (rtl_dump_file,
1459 "Cross jumping from bb %i to bb %i; %i common insns\n",
1460 src1->index, src2->index, nmatch);
1462 redirect_to->count += src1->count;
1463 redirect_to->frequency += src1->frequency;
1464 /* We may have some registers visible trought the block. */
1465 redirect_to->flags |= BB_DIRTY;
1467 /* Recompute the frequencies and counts of outgoing edges. */
1468 for (s = redirect_to->succ; s; s = s->succ_next)
1471 basic_block d = s->dest;
1473 if (FORWARDER_BLOCK_P (d))
1476 for (s2 = src1->succ; ; s2 = s2->succ_next)
1478 basic_block d2 = s2->dest;
1479 if (FORWARDER_BLOCK_P (d2))
1480 d2 = d2->succ->dest;
1485 s->count += s2->count;
1487 /* Take care to update possible forwarder blocks. We verified
1488 that there is no more than one in the chain, so we can't run
1489 into infinite loop. */
1490 if (FORWARDER_BLOCK_P (s->dest))
1492 s->dest->succ->count += s2->count;
1493 s->dest->count += s2->count;
1494 s->dest->frequency += EDGE_FREQUENCY (s);
1497 if (FORWARDER_BLOCK_P (s2->dest))
1499 s2->dest->succ->count -= s2->count;
1500 if (s2->dest->succ->count < 0)
1501 s2->dest->succ->count = 0;
1502 s2->dest->count -= s2->count;
1503 s2->dest->frequency -= EDGE_FREQUENCY (s);
1504 if (s2->dest->frequency < 0)
1505 s2->dest->frequency = 0;
1506 if (s2->dest->count < 0)
1507 s2->dest->count = 0;
1510 if (!redirect_to->frequency && !src1->frequency)
1511 s->probability = (s->probability + s2->probability) / 2;
1514 = ((s->probability * redirect_to->frequency +
1515 s2->probability * src1->frequency)
1516 / (redirect_to->frequency + src1->frequency));
1519 update_br_prob_note (redirect_to);
1521 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1523 /* Skip possible basic block header. */
1524 if (GET_CODE (newpos1) == CODE_LABEL)
1525 newpos1 = NEXT_INSN (newpos1);
1527 if (GET_CODE (newpos1) == NOTE)
1528 newpos1 = NEXT_INSN (newpos1);
1530 redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
1531 to_remove = redirect_from->succ->dest;
1533 redirect_edge_and_branch_force (redirect_from->succ, redirect_to);
1534 delete_basic_block (to_remove);
1536 update_forwarder_flag (redirect_from);
1541 /* Search the predecessors of BB for common insn sequences. When found,
1542 share code between them by redirecting control flow. Return true if
1543 any changes made. */
1546 try_crossjump_bb (int mode, basic_block bb)
1548 edge e, e2, nexte2, nexte, fallthru;
1552 /* Nothing to do if there is not at least two incoming edges. */
1553 if (!bb->pred || !bb->pred->pred_next)
1556 /* It is always cheapest to redirect a block that ends in a branch to
1557 a block that falls through into BB, as that adds no branches to the
1558 program. We'll try that combination first. */
1560 max = PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES);
1561 for (e = bb->pred; e ; e = e->pred_next, n++)
1563 if (e->flags & EDGE_FALLTHRU)
1570 for (e = bb->pred; e; e = nexte)
1572 nexte = e->pred_next;
1574 /* As noted above, first try with the fallthru predecessor. */
1577 /* Don't combine the fallthru edge into anything else.
1578 If there is a match, we'll do it the other way around. */
1581 /* If nothing changed since the last attempt, there is nothing
1584 && (!(e->src->flags & BB_DIRTY)
1585 && !(fallthru->src->flags & BB_DIRTY)))
1588 if (try_crossjump_to_edge (mode, e, fallthru))
1596 /* Non-obvious work limiting check: Recognize that we're going
1597 to call try_crossjump_bb on every basic block. So if we have
1598 two blocks with lots of outgoing edges (a switch) and they
1599 share lots of common destinations, then we would do the
1600 cross-jump check once for each common destination.
1602 Now, if the blocks actually are cross-jump candidates, then
1603 all of their destinations will be shared. Which means that
1604 we only need check them for cross-jump candidacy once. We
1605 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1606 choosing to do the check from the block for which the edge
1607 in question is the first successor of A. */
1608 if (e->src->succ != e)
1611 for (e2 = bb->pred; e2; e2 = nexte2)
1613 nexte2 = e2->pred_next;
1618 /* We've already checked the fallthru edge above. */
1622 /* The "first successor" check above only prevents multiple
1623 checks of crossjump(A,B). In order to prevent redundant
1624 checks of crossjump(B,A), require that A be the block
1625 with the lowest index. */
1626 if (e->src->index > e2->src->index)
1629 /* If nothing changed since the last attempt, there is nothing
1632 && (!(e->src->flags & BB_DIRTY)
1633 && !(e2->src->flags & BB_DIRTY)))
1636 if (try_crossjump_to_edge (mode, e, e2))
1648 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1649 instructions etc. Return nonzero if changes were made. */
1652 try_optimize_cfg (int mode)
1654 bool changed_overall = false;
1657 basic_block bb, b, next;
1659 if (mode & CLEANUP_CROSSJUMP)
1660 add_noreturn_fake_exit_edges ();
1663 update_forwarder_flag (bb);
1665 if (mode & (CLEANUP_UPDATE_LIFE | CLEANUP_CROSSJUMP | CLEANUP_THREADING))
1668 if (! (* targetm.cannot_modify_jumps_p) ())
1671 /* Attempt to merge blocks as made possible by edge removal. If
1672 a block has only one successor, and the successor has only
1673 one predecessor, they may be combined. */
1680 fprintf (rtl_dump_file,
1681 "\n\ntry_optimize_cfg iteration %i\n\n",
1684 for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR;)
1688 bool changed_here = false;
1690 /* Delete trivially dead basic blocks. */
1691 while (b->pred == NULL)
1695 fprintf (rtl_dump_file, "Deleting block %i.\n",
1698 delete_basic_block (b);
1699 if (!(mode & CLEANUP_CFGLAYOUT))
1704 /* Remove code labels no longer used. Don't do this
1705 before CALL_PLACEHOLDER is removed, as some branches
1706 may be hidden within. */
1707 if (b->pred->pred_next == NULL
1708 && (b->pred->flags & EDGE_FALLTHRU)
1709 && !(b->pred->flags & EDGE_COMPLEX)
1710 && GET_CODE (BB_HEAD (b)) == CODE_LABEL
1711 && (!(mode & CLEANUP_PRE_SIBCALL)
1712 || !tail_recursion_label_p (BB_HEAD (b)))
1713 /* If the previous block ends with a branch to this
1714 block, we can't delete the label. Normally this
1715 is a condjump that is yet to be simplified, but
1716 if CASE_DROPS_THRU, this can be a tablejump with
1717 some element going to the same place as the
1718 default (fallthru). */
1719 && (b->pred->src == ENTRY_BLOCK_PTR
1720 || GET_CODE (BB_END (b->pred->src)) != JUMP_INSN
1721 || ! label_is_jump_target_p (BB_HEAD (b),
1722 BB_END (b->pred->src))))
1724 rtx label = BB_HEAD (b);
1726 delete_insn_chain (label, label);
1727 /* In the case label is undeletable, move it after the
1728 BASIC_BLOCK note. */
1729 if (NOTE_LINE_NUMBER (BB_HEAD (b)) == NOTE_INSN_DELETED_LABEL)
1731 rtx bb_note = NEXT_INSN (BB_HEAD (b));
1733 reorder_insns_nobb (label, label, bb_note);
1734 BB_HEAD (b) = bb_note;
1737 fprintf (rtl_dump_file, "Deleted label in block %i.\n",
1741 /* If we fall through an empty block, we can remove it. */
1742 if (!(mode & CLEANUP_CFGLAYOUT)
1743 && b->pred->pred_next == NULL
1744 && (b->pred->flags & EDGE_FALLTHRU)
1745 && GET_CODE (BB_HEAD (b)) != CODE_LABEL
1746 && FORWARDER_BLOCK_P (b)
1747 /* Note that forwarder_block_p true ensures that
1748 there is a successor for this block. */
1749 && (b->succ->flags & EDGE_FALLTHRU)
1750 && n_basic_blocks > 1)
1753 fprintf (rtl_dump_file,
1754 "Deleting fallthru block %i.\n",
1757 c = b->prev_bb == ENTRY_BLOCK_PTR ? b->next_bb : b->prev_bb;
1758 redirect_edge_succ_nodup (b->pred, b->succ->dest);
1759 delete_basic_block (b);
1764 if ((s = b->succ) != NULL
1765 && s->succ_next == NULL
1766 && !(s->flags & EDGE_COMPLEX)
1767 && (c = s->dest) != EXIT_BLOCK_PTR
1768 && c->pred->pred_next == NULL
1771 /* When not in cfg_layout mode use code aware of reordering
1772 INSN. This code possibly creates new basic blocks so it
1773 does not fit merge_blocks interface and is kept here in
1774 hope that it will become useless once more of compiler
1775 is transformed to use cfg_layout mode. */
1777 if ((mode & CLEANUP_CFGLAYOUT)
1778 && can_merge_blocks_p (b, c))
1780 merge_blocks (b, c);
1781 update_forwarder_flag (b);
1782 changed_here = true;
1784 else if (!(mode & CLEANUP_CFGLAYOUT)
1785 /* If the jump insn has side effects,
1786 we can't kill the edge. */
1787 && (GET_CODE (BB_END (b)) != JUMP_INSN
1788 || (reload_completed
1789 ? simplejump_p (BB_END (b))
1790 : onlyjump_p (BB_END (b))))
1791 && (next = merge_blocks_move (s, b, c, mode)))
1794 changed_here = true;
1798 /* Simplify branch over branch. */
1799 if ((mode & CLEANUP_EXPENSIVE)
1800 && !(mode & CLEANUP_CFGLAYOUT)
1801 && try_simplify_condjump (b))
1802 changed_here = true;
1804 /* If B has a single outgoing edge, but uses a
1805 non-trivial jump instruction without side-effects, we
1806 can either delete the jump entirely, or replace it
1807 with a simple unconditional jump. */
1809 && ! b->succ->succ_next
1810 && b->succ->dest != EXIT_BLOCK_PTR
1811 && onlyjump_p (BB_END (b))
1812 && try_redirect_by_replacing_jump (b->succ, b->succ->dest,
1813 (mode & CLEANUP_CFGLAYOUT) != 0))
1815 update_forwarder_flag (b);
1816 changed_here = true;
1819 /* Simplify branch to branch. */
1820 if (try_forward_edges (mode, b))
1821 changed_here = true;
1823 /* Look for shared code between blocks. */
1824 if ((mode & CLEANUP_CROSSJUMP)
1825 && try_crossjump_bb (mode, b))
1826 changed_here = true;
1828 /* Don't get confused by the index shift caused by
1836 if ((mode & CLEANUP_CROSSJUMP)
1837 && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
1840 #ifdef ENABLE_CHECKING
1842 verify_flow_info ();
1845 changed_overall |= changed;
1851 if (mode & CLEANUP_CROSSJUMP)
1852 remove_fake_edges ();
1854 clear_aux_for_blocks ();
1856 return changed_overall;
1859 /* Delete all unreachable basic blocks. */
1862 delete_unreachable_blocks (void)
1864 bool changed = false;
1865 basic_block b, next_bb;
1867 find_unreachable_blocks ();
1869 /* Delete all unreachable basic blocks. */
1871 for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
1873 next_bb = b->next_bb;
1875 if (!(b->flags & BB_REACHABLE))
1877 delete_basic_block (b);
1883 tidy_fallthru_edges ();
1887 /* Tidy the CFG by deleting unreachable code and whatnot. */
1890 cleanup_cfg (int mode)
1892 bool changed = false;
1894 timevar_push (TV_CLEANUP_CFG);
1895 if (delete_unreachable_blocks ())
1898 /* We've possibly created trivially dead code. Cleanup it right
1899 now to introduce more opportunities for try_optimize_cfg. */
1900 if (!(mode & (CLEANUP_NO_INSN_DEL
1901 | CLEANUP_UPDATE_LIFE | CLEANUP_PRE_SIBCALL))
1902 && !reload_completed)
1903 delete_trivially_dead_insns (get_insns(), max_reg_num ());
1908 while (try_optimize_cfg (mode))
1910 delete_unreachable_blocks (), changed = true;
1911 if (mode & CLEANUP_UPDATE_LIFE)
1913 /* Cleaning up CFG introduces more opportunities for dead code
1914 removal that in turn may introduce more opportunities for
1915 cleaning up the CFG. */
1916 if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
1918 | PROP_SCAN_DEAD_CODE
1919 | PROP_KILL_DEAD_CODE
1920 | ((mode & CLEANUP_LOG_LINKS)
1921 ? PROP_LOG_LINKS : 0)))
1924 else if (!(mode & (CLEANUP_NO_INSN_DEL | CLEANUP_PRE_SIBCALL))
1925 && (mode & CLEANUP_EXPENSIVE)
1926 && !reload_completed)
1928 if (!delete_trivially_dead_insns (get_insns(), max_reg_num ()))
1933 delete_dead_jumptables ();
1936 /* Kill the data we won't maintain. */
1937 free_EXPR_LIST_list (&label_value_list);
1938 timevar_pop (TV_CLEANUP_CFG);