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"
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 /* Set to true when we are running first pass of try_optimize_cfg loop. */
71 static bool first_pass;
72 static bool try_crossjump_to_edge (int, edge, edge);
73 static bool try_crossjump_bb (int, basic_block);
74 static bool outgoing_edges_match (int, basic_block, basic_block);
75 static int flow_find_cross_jump (int, basic_block, basic_block, rtx *, rtx *);
76 static bool insns_match_p (int, rtx, rtx);
78 static bool tail_recursion_label_p (rtx);
79 static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
80 static void merge_blocks_move_successor_nojumps (basic_block, basic_block);
81 static bool try_optimize_cfg (int);
82 static bool try_simplify_condjump (basic_block);
83 static bool try_forward_edges (int, basic_block);
84 static edge thread_jump (int, edge, basic_block);
85 static bool mark_effect (rtx, bitmap);
86 static void notice_new_block (basic_block);
87 static void update_forwarder_flag (basic_block);
88 static int mentions_nonequal_regs (rtx *, void *);
90 /* Set flags for newly created block. */
93 notice_new_block (basic_block bb)
98 if (forwarder_block_p (bb))
99 BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
102 /* Recompute forwarder flag after block has been modified. */
105 update_forwarder_flag (basic_block bb)
107 if (forwarder_block_p (bb))
108 BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
110 BB_CLEAR_FLAG (bb, BB_FORWARDER_BLOCK);
113 /* Simplify a conditional jump around an unconditional jump.
114 Return true if something changed. */
117 try_simplify_condjump (basic_block cbranch_block)
119 basic_block jump_block, jump_dest_block, cbranch_dest_block;
120 edge cbranch_jump_edge, cbranch_fallthru_edge;
125 /* Verify that there are exactly two successors. */
126 if (!cbranch_block->succ
127 || !cbranch_block->succ->succ_next
128 || cbranch_block->succ->succ_next->succ_next)
131 /* Verify that we've got a normal conditional branch at the end
133 cbranch_insn = BB_END (cbranch_block);
134 if (!any_condjump_p (cbranch_insn))
137 cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
138 cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
140 /* The next block must not have multiple predecessors, must not
141 be the last block in the function, and must contain just the
142 unconditional jump. */
143 jump_block = cbranch_fallthru_edge->dest;
144 if (jump_block->pred->pred_next
145 || jump_block->next_bb == EXIT_BLOCK_PTR
146 || !FORWARDER_BLOCK_P (jump_block))
148 jump_dest_block = jump_block->succ->dest;
150 /* The conditional branch must target the block after the
151 unconditional branch. */
152 cbranch_dest_block = cbranch_jump_edge->dest;
154 if (!can_fallthru (jump_block, cbranch_dest_block))
157 /* Invert the conditional branch. */
158 if (!invert_jump (cbranch_insn, block_label (jump_dest_block), 0))
162 fprintf (rtl_dump_file, "Simplifying condjump %i around jump %i\n",
163 INSN_UID (cbranch_insn), INSN_UID (BB_END (jump_block)));
165 /* Success. Update the CFG to match. Note that after this point
166 the edge variable names appear backwards; the redirection is done
167 this way to preserve edge profile data. */
168 cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
170 cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
172 cbranch_jump_edge->flags |= EDGE_FALLTHRU;
173 cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
174 update_br_prob_note (cbranch_block);
176 end = BB_END (jump_block);
177 /* Deleting a block may produce unreachable code warning even when we are
178 not deleting anything live. Suppress it by moving all the line number
179 notes out of the block. */
180 for (insn = BB_HEAD (jump_block); insn != NEXT_INSN (BB_END (jump_block));
183 next = NEXT_INSN (insn);
184 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
186 if (insn == BB_END (jump_block))
188 BB_END (jump_block) = PREV_INSN (insn);
192 reorder_insns_nobb (insn, insn, end);
196 /* Delete the block with the unconditional jump, and clean up the mess. */
197 delete_block (jump_block);
198 tidy_fallthru_edge (cbranch_jump_edge, cbranch_block, cbranch_dest_block);
203 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
204 on register. Used by jump threading. */
207 mark_effect (rtx exp, regset nonequal)
211 switch (GET_CODE (exp))
213 /* In case we do clobber the register, mark it as equal, as we know the
214 value is dead so it don't have to match. */
216 if (REG_P (XEXP (exp, 0)))
218 dest = XEXP (exp, 0);
219 regno = REGNO (dest);
220 CLEAR_REGNO_REG_SET (nonequal, regno);
221 if (regno < FIRST_PSEUDO_REGISTER)
223 int n = HARD_REGNO_NREGS (regno, GET_MODE (dest));
225 CLEAR_REGNO_REG_SET (nonequal, regno + n);
231 if (rtx_equal_for_cselib_p (SET_DEST (exp), SET_SRC (exp)))
233 dest = SET_DEST (exp);
238 regno = REGNO (dest);
239 SET_REGNO_REG_SET (nonequal, regno);
240 if (regno < FIRST_PSEUDO_REGISTER)
242 int n = HARD_REGNO_NREGS (regno, GET_MODE (dest));
244 SET_REGNO_REG_SET (nonequal, regno + n);
253 /* Return nonzero if X is a register set in regset DATA.
254 Called via for_each_rtx. */
256 mentions_nonequal_regs (rtx *x, void *data)
258 regset nonequal = (regset) data;
264 if (REGNO_REG_SET_P (nonequal, regno))
266 if (regno < FIRST_PSEUDO_REGISTER)
268 int n = HARD_REGNO_NREGS (regno, GET_MODE (*x));
270 if (REGNO_REG_SET_P (nonequal, regno + n))
276 /* Attempt to prove that the basic block B will have no side effects and
277 always continues in the same edge if reached via E. Return the edge
278 if exist, NULL otherwise. */
281 thread_jump (int mode, edge e, basic_block b)
283 rtx set1, set2, cond1, cond2, insn;
284 enum rtx_code code1, code2, reversed_code2;
285 bool reverse1 = false;
290 if (BB_FLAGS (b) & BB_NONTHREADABLE_BLOCK)
293 /* At the moment, we do handle only conditional jumps, but later we may
294 want to extend this code to tablejumps and others. */
295 if (!e->src->succ->succ_next || e->src->succ->succ_next->succ_next)
297 if (!b->succ || !b->succ->succ_next || b->succ->succ_next->succ_next)
299 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
303 /* Second branch must end with onlyjump, as we will eliminate the jump. */
304 if (!any_condjump_p (BB_END (e->src)))
307 if (!any_condjump_p (BB_END (b)) || !onlyjump_p (BB_END (b)))
309 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
313 set1 = pc_set (BB_END (e->src));
314 set2 = pc_set (BB_END (b));
315 if (((e->flags & EDGE_FALLTHRU) != 0)
316 != (XEXP (SET_SRC (set1), 1) == pc_rtx))
319 cond1 = XEXP (SET_SRC (set1), 0);
320 cond2 = XEXP (SET_SRC (set2), 0);
322 code1 = reversed_comparison_code (cond1, BB_END (e->src));
324 code1 = GET_CODE (cond1);
326 code2 = GET_CODE (cond2);
327 reversed_code2 = reversed_comparison_code (cond2, BB_END (b));
329 if (!comparison_dominates_p (code1, code2)
330 && !comparison_dominates_p (code1, reversed_code2))
333 /* Ensure that the comparison operators are equivalent.
334 ??? This is far too pessimistic. We should allow swapped operands,
335 different CCmodes, or for example comparisons for interval, that
336 dominate even when operands are not equivalent. */
337 if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
338 || !rtx_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
341 /* Short circuit cases where block B contains some side effects, as we can't
343 for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b));
344 insn = NEXT_INSN (insn))
345 if (INSN_P (insn) && side_effects_p (PATTERN (insn)))
347 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
353 /* First process all values computed in the source basic block. */
354 for (insn = NEXT_INSN (BB_HEAD (e->src)); insn != NEXT_INSN (BB_END (e->src));
355 insn = NEXT_INSN (insn))
357 cselib_process_insn (insn);
359 nonequal = BITMAP_XMALLOC();
360 CLEAR_REG_SET (nonequal);
362 /* Now assume that we've continued by the edge E to B and continue
363 processing as if it were same basic block.
364 Our goal is to prove that whole block is an NOOP. */
366 for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b)) && !failed;
367 insn = NEXT_INSN (insn))
371 rtx pat = PATTERN (insn);
373 if (GET_CODE (pat) == PARALLEL)
375 for (i = 0; i < XVECLEN (pat, 0); i++)
376 failed |= mark_effect (XVECEXP (pat, 0, i), nonequal);
379 failed |= mark_effect (pat, nonequal);
382 cselib_process_insn (insn);
385 /* Later we should clear nonequal of dead registers. So far we don't
386 have life information in cfg_cleanup. */
389 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
393 /* cond2 must not mention any register that is not equal to the
395 if (for_each_rtx (&cond2, mentions_nonequal_regs, nonequal))
398 /* In case liveness information is available, we need to prove equivalence
399 only of the live values. */
400 if (mode & CLEANUP_UPDATE_LIFE)
401 AND_REG_SET (nonequal, b->global_live_at_end);
403 EXECUTE_IF_SET_IN_REG_SET (nonequal, 0, i, goto failed_exit;);
405 BITMAP_XFREE (nonequal);
407 if ((comparison_dominates_p (code1, code2) != 0)
408 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
409 return BRANCH_EDGE (b);
411 return FALLTHRU_EDGE (b);
414 BITMAP_XFREE (nonequal);
419 /* Attempt to forward edges leaving basic block B.
420 Return true if successful. */
423 try_forward_edges (int mode, basic_block b)
425 bool changed = false;
426 edge e, next, *threaded_edges = NULL;
428 for (e = b->succ; e; e = next)
430 basic_block target, first;
432 bool threaded = false;
433 int nthreaded_edges = 0;
434 bool may_thread = first_pass | (b->flags & BB_DIRTY);
438 /* Skip complex edges because we don't know how to update them.
440 Still handle fallthru edges, as we can succeed to forward fallthru
441 edge to the same place as the branch edge of conditional branch
442 and turn conditional branch to an unconditional branch. */
443 if (e->flags & EDGE_COMPLEX)
446 target = first = e->dest;
449 while (counter < n_basic_blocks)
451 basic_block new_target = NULL;
452 bool new_target_threaded = false;
453 may_thread |= target->flags & BB_DIRTY;
455 if (FORWARDER_BLOCK_P (target)
456 && target->succ->dest != EXIT_BLOCK_PTR)
458 /* Bypass trivial infinite loops. */
459 if (target == target->succ->dest)
460 counter = n_basic_blocks;
461 new_target = target->succ->dest;
464 /* Allow to thread only over one edge at time to simplify updating
466 else if ((mode & CLEANUP_THREADING) && may_thread)
468 edge t = thread_jump (mode, e, target);
472 threaded_edges = xmalloc (sizeof (*threaded_edges)
478 /* Detect an infinite loop across blocks not
479 including the start block. */
480 for (i = 0; i < nthreaded_edges; ++i)
481 if (threaded_edges[i] == t)
483 if (i < nthreaded_edges)
485 counter = n_basic_blocks;
490 /* Detect an infinite loop across the start block. */
494 if (nthreaded_edges >= n_basic_blocks)
496 threaded_edges[nthreaded_edges++] = t;
498 new_target = t->dest;
499 new_target_threaded = true;
506 /* Avoid killing of loop pre-headers, as it is the place loop
507 optimizer wants to hoist code to.
509 For fallthru forwarders, the LOOP_BEG note must appear between
510 the header of block and CODE_LABEL of the loop, for non forwarders
511 it must appear before the JUMP_INSN. */
512 if ((mode & CLEANUP_PRE_LOOP) && optimize)
514 rtx insn = (target->succ->flags & EDGE_FALLTHRU
515 ? BB_HEAD (target) : prev_nonnote_insn (BB_END (target)));
517 if (GET_CODE (insn) != NOTE)
518 insn = NEXT_INSN (insn);
520 for (; insn && GET_CODE (insn) != CODE_LABEL && !INSN_P (insn);
521 insn = NEXT_INSN (insn))
522 if (GET_CODE (insn) == NOTE
523 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
526 if (GET_CODE (insn) == NOTE)
529 /* Do not clean up branches to just past the end of a loop
530 at this time; it can mess up the loop optimizer's
531 recognition of some patterns. */
533 insn = PREV_INSN (BB_HEAD (target));
534 if (insn && GET_CODE (insn) == NOTE
535 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
541 threaded |= new_target_threaded;
544 if (counter >= n_basic_blocks)
547 fprintf (rtl_dump_file, "Infinite loop in BB %i.\n",
550 else if (target == first)
551 ; /* We didn't do anything. */
554 /* Save the values now, as the edge may get removed. */
555 gcov_type edge_count = e->count;
556 int edge_probability = e->probability;
560 /* Don't force if target is exit block. */
561 if (threaded && target != EXIT_BLOCK_PTR)
563 notice_new_block (redirect_edge_and_branch_force (e, target));
565 fprintf (rtl_dump_file, "Conditionals threaded.\n");
567 else if (!redirect_edge_and_branch (e, target))
570 fprintf (rtl_dump_file,
571 "Forwarding edge %i->%i to %i failed.\n",
572 b->index, e->dest->index, target->index);
576 /* We successfully forwarded the edge. Now update profile
577 data: for each edge we traversed in the chain, remove
578 the original edge's execution count. */
579 edge_frequency = ((edge_probability * b->frequency
580 + REG_BR_PROB_BASE / 2)
583 if (!FORWARDER_BLOCK_P (b) && forwarder_block_p (b))
584 BB_SET_FLAG (b, BB_FORWARDER_BLOCK);
590 first->count -= edge_count;
591 if (first->count < 0)
593 first->frequency -= edge_frequency;
594 if (first->frequency < 0)
595 first->frequency = 0;
596 if (first->succ->succ_next)
600 if (n >= nthreaded_edges)
602 t = threaded_edges [n++];
605 if (first->frequency)
606 prob = edge_frequency * REG_BR_PROB_BASE / first->frequency;
609 if (prob > t->probability)
610 prob = t->probability;
611 t->probability -= prob;
612 prob = REG_BR_PROB_BASE - prob;
615 first->succ->probability = REG_BR_PROB_BASE;
616 first->succ->succ_next->probability = 0;
619 for (e = first->succ; e; e = e->succ_next)
620 e->probability = ((e->probability * REG_BR_PROB_BASE)
622 update_br_prob_note (first);
626 /* It is possible that as the result of
627 threading we've removed edge as it is
628 threaded to the fallthru edge. Avoid
629 getting out of sync. */
630 if (n < nthreaded_edges
631 && first == threaded_edges [n]->src)
636 t->count -= edge_count;
641 while (first != target);
648 free (threaded_edges);
652 /* Return true if LABEL is used for tail recursion. */
655 tail_recursion_label_p (rtx label)
659 for (x = tail_recursion_label_list; x; x = XEXP (x, 1))
660 if (label == XEXP (x, 0))
666 /* Blocks A and B are to be merged into a single block. A has no incoming
667 fallthru edge, so it can be moved before B without adding or modifying
668 any jumps (aside from the jump from A to B). */
671 merge_blocks_move_predecessor_nojumps (basic_block a, basic_block b)
675 barrier = next_nonnote_insn (BB_END (a));
676 if (GET_CODE (barrier) != BARRIER)
678 delete_insn (barrier);
680 /* Move block and loop notes out of the chain so that we do not
683 ??? A better solution would be to squeeze out all the non-nested notes
684 and adjust the block trees appropriately. Even better would be to have
685 a tighter connection between block trees and rtl so that this is not
687 if (squeeze_notes (&BB_HEAD (a), &BB_END (a)))
690 /* Scramble the insn chain. */
691 if (BB_END (a) != PREV_INSN (BB_HEAD (b)))
692 reorder_insns_nobb (BB_HEAD (a), BB_END (a), PREV_INSN (BB_HEAD (b)));
693 a->flags |= BB_DIRTY;
696 fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
699 /* Swap the records for the two blocks around. */
702 link_block (a, b->prev_bb);
704 /* Now blocks A and B are contiguous. Merge them. */
708 /* Blocks A and B are to be merged into a single block. B has no outgoing
709 fallthru edge, so it can be moved after A without adding or modifying
710 any jumps (aside from the jump from A to B). */
713 merge_blocks_move_successor_nojumps (basic_block a, basic_block b)
715 rtx barrier, real_b_end;
718 real_b_end = BB_END (b);
720 /* If there is a jump table following block B temporarily add the jump table
721 to block B so that it will also be moved to the correct location. */
722 if (tablejump_p (BB_END (b), &label, &table)
723 && prev_active_insn (label) == BB_END (b))
728 /* There had better have been a barrier there. Delete it. */
729 barrier = NEXT_INSN (BB_END (b));
730 if (barrier && GET_CODE (barrier) == BARRIER)
731 delete_insn (barrier);
733 /* Move block and loop notes out of the chain so that we do not
736 ??? A better solution would be to squeeze out all the non-nested notes
737 and adjust the block trees appropriately. Even better would be to have
738 a tighter connection between block trees and rtl so that this is not
740 if (squeeze_notes (&BB_HEAD (b), &BB_END (b)))
743 /* Scramble the insn chain. */
744 reorder_insns_nobb (BB_HEAD (b), BB_END (b), BB_END (a));
746 /* Restore the real end of b. */
747 BB_END (b) = real_b_end;
750 fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
753 /* Now blocks A and B are contiguous. Merge them. */
757 /* Attempt to merge basic blocks that are potentially non-adjacent.
758 Return NULL iff the attempt failed, otherwise return basic block
759 where cleanup_cfg should continue. Because the merging commonly
760 moves basic block away or introduces another optimization
761 possibility, return basic block just before B so cleanup_cfg don't
764 It may be good idea to return basic block before C in the case
765 C has been moved after B and originally appeared earlier in the
766 insn sequence, but we have no information available about the
767 relative ordering of these two. Hopefully it is not too common. */
770 merge_blocks_move (edge e, basic_block b, basic_block c, int mode)
773 /* If C has a tail recursion label, do not merge. There is no
774 edge recorded from the call_placeholder back to this label, as
775 that would make optimize_sibling_and_tail_recursive_calls more
776 complex for no gain. */
777 if ((mode & CLEANUP_PRE_SIBCALL)
778 && GET_CODE (BB_HEAD (c)) == CODE_LABEL
779 && tail_recursion_label_p (BB_HEAD (c)))
782 /* If B has a fallthru edge to C, no need to move anything. */
783 if (e->flags & EDGE_FALLTHRU)
785 int b_index = b->index, c_index = c->index;
787 update_forwarder_flag (b);
790 fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
793 return b->prev_bb == ENTRY_BLOCK_PTR ? b : b->prev_bb;
796 /* Otherwise we will need to move code around. Do that only if expensive
797 transformations are allowed. */
798 else if (mode & CLEANUP_EXPENSIVE)
800 edge tmp_edge, b_fallthru_edge;
801 bool c_has_outgoing_fallthru;
802 bool b_has_incoming_fallthru;
804 /* Avoid overactive code motion, as the forwarder blocks should be
805 eliminated by edge redirection instead. One exception might have
806 been if B is a forwarder block and C has no fallthru edge, but
807 that should be cleaned up by bb-reorder instead. */
808 if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
811 /* We must make sure to not munge nesting of lexical blocks,
812 and loop notes. This is done by squeezing out all the notes
813 and leaving them there to lie. Not ideal, but functional. */
815 for (tmp_edge = c->succ; tmp_edge; tmp_edge = tmp_edge->succ_next)
816 if (tmp_edge->flags & EDGE_FALLTHRU)
819 c_has_outgoing_fallthru = (tmp_edge != NULL);
821 for (tmp_edge = b->pred; tmp_edge; tmp_edge = tmp_edge->pred_next)
822 if (tmp_edge->flags & EDGE_FALLTHRU)
825 b_has_incoming_fallthru = (tmp_edge != NULL);
826 b_fallthru_edge = tmp_edge;
829 next = next->prev_bb;
831 /* Otherwise, we're going to try to move C after B. If C does
832 not have an outgoing fallthru, then it can be moved
833 immediately after B without introducing or modifying jumps. */
834 if (! c_has_outgoing_fallthru)
836 merge_blocks_move_successor_nojumps (b, c);
837 return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
840 /* If B does not have an incoming fallthru, then it can be moved
841 immediately before C without introducing or modifying jumps.
842 C cannot be the first block, so we do not have to worry about
843 accessing a non-existent block. */
845 if (b_has_incoming_fallthru)
849 if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
851 bb = force_nonfallthru (b_fallthru_edge);
853 notice_new_block (bb);
856 merge_blocks_move_predecessor_nojumps (b, c);
857 return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
864 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
867 insns_match_p (int mode ATTRIBUTE_UNUSED, rtx i1, rtx i2)
871 /* Verify that I1 and I2 are equivalent. */
872 if (GET_CODE (i1) != GET_CODE (i2))
878 if (GET_CODE (p1) != GET_CODE (p2))
881 /* If this is a CALL_INSN, compare register usage information.
882 If we don't check this on stack register machines, the two
883 CALL_INSNs might be merged leaving reg-stack.c with mismatching
884 numbers of stack registers in the same basic block.
885 If we don't check this on machines with delay slots, a delay slot may
886 be filled that clobbers a parameter expected by the subroutine.
888 ??? We take the simple route for now and assume that if they're
889 equal, they were constructed identically. */
891 if (GET_CODE (i1) == CALL_INSN
892 && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
893 CALL_INSN_FUNCTION_USAGE (i2))
894 || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)))
898 /* If cross_jump_death_matters is not 0, the insn's mode
899 indicates whether or not the insn contains any stack-like
902 if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
904 /* If register stack conversion has already been done, then
905 death notes must also be compared before it is certain that
906 the two instruction streams match. */
909 HARD_REG_SET i1_regset, i2_regset;
911 CLEAR_HARD_REG_SET (i1_regset);
912 CLEAR_HARD_REG_SET (i2_regset);
914 for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
915 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
916 SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
918 for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
919 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
920 SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
922 GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
932 ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
935 /* Do not do EQUIV substitution after reload. First, we're undoing the
936 work of reload_cse. Second, we may be undoing the work of the post-
937 reload splitting pass. */
938 /* ??? Possibly add a new phase switch variable that can be used by
939 targets to disallow the troublesome insns after splitting. */
940 if (!reload_completed)
942 /* The following code helps take care of G++ cleanups. */
943 rtx equiv1 = find_reg_equal_equiv_note (i1);
944 rtx equiv2 = find_reg_equal_equiv_note (i2);
947 /* If the equivalences are not to a constant, they may
948 reference pseudos that no longer exist, so we can't
950 && (! reload_completed
951 || (CONSTANT_P (XEXP (equiv1, 0))
952 && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
954 rtx s1 = single_set (i1);
955 rtx s2 = single_set (i2);
956 if (s1 != 0 && s2 != 0
957 && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
959 validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
960 validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
961 if (! rtx_renumbered_equal_p (p1, p2))
963 else if (apply_change_group ())
972 /* Look through the insns at the end of BB1 and BB2 and find the longest
973 sequence that are equivalent. Store the first insns for that sequence
974 in *F1 and *F2 and return the sequence length.
976 To simplify callers of this function, if the blocks match exactly,
977 store the head of the blocks in *F1 and *F2. */
980 flow_find_cross_jump (int mode ATTRIBUTE_UNUSED, basic_block bb1,
981 basic_block bb2, rtx *f1, rtx *f2)
983 rtx i1, i2, last1, last2, afterlast1, afterlast2;
986 /* Skip simple jumps at the end of the blocks. Complex jumps still
987 need to be compared for equivalence, which we'll do below. */
990 last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
992 || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
1000 || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
1003 /* Count everything except for unconditional jump as insn. */
1004 if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
1006 i2 = PREV_INSN (i2);
1012 while (!INSN_P (i1) && i1 != BB_HEAD (bb1))
1013 i1 = PREV_INSN (i1);
1015 while (!INSN_P (i2) && i2 != BB_HEAD (bb2))
1016 i2 = PREV_INSN (i2);
1018 if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
1021 if (!insns_match_p (mode, i1, i2))
1024 /* Don't begin a cross-jump with a NOTE insn. */
1027 /* If the merged insns have different REG_EQUAL notes, then
1029 rtx equiv1 = find_reg_equal_equiv_note (i1);
1030 rtx equiv2 = find_reg_equal_equiv_note (i2);
1032 if (equiv1 && !equiv2)
1033 remove_note (i1, equiv1);
1034 else if (!equiv1 && equiv2)
1035 remove_note (i2, equiv2);
1036 else if (equiv1 && equiv2
1037 && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
1039 remove_note (i1, equiv1);
1040 remove_note (i2, equiv2);
1043 afterlast1 = last1, afterlast2 = last2;
1044 last1 = i1, last2 = i2;
1048 i1 = PREV_INSN (i1);
1049 i2 = PREV_INSN (i2);
1053 /* Don't allow the insn after a compare to be shared by
1054 cross-jumping unless the compare is also shared. */
1055 if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
1056 last1 = afterlast1, last2 = afterlast2, ninsns--;
1059 /* Include preceding notes and labels in the cross-jump. One,
1060 this may bring us to the head of the blocks as requested above.
1061 Two, it keeps line number notes as matched as may be. */
1064 while (last1 != BB_HEAD (bb1) && !INSN_P (PREV_INSN (last1)))
1065 last1 = PREV_INSN (last1);
1067 if (last1 != BB_HEAD (bb1) && GET_CODE (PREV_INSN (last1)) == CODE_LABEL)
1068 last1 = PREV_INSN (last1);
1070 while (last2 != BB_HEAD (bb2) && !INSN_P (PREV_INSN (last2)))
1071 last2 = PREV_INSN (last2);
1073 if (last2 != BB_HEAD (bb2) && GET_CODE (PREV_INSN (last2)) == CODE_LABEL)
1074 last2 = PREV_INSN (last2);
1083 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1084 the branch instruction. This means that if we commonize the control
1085 flow before end of the basic block, the semantic remains unchanged.
1087 We may assume that there exists one edge with a common destination. */
1090 outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
1092 int nehedges1 = 0, nehedges2 = 0;
1093 edge fallthru1 = 0, fallthru2 = 0;
1096 /* If BB1 has only one successor, we may be looking at either an
1097 unconditional jump, or a fake edge to exit. */
1098 if (bb1->succ && !bb1->succ->succ_next
1099 && (bb1->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1100 && (GET_CODE (BB_END (bb1)) != JUMP_INSN || simplejump_p (BB_END (bb1))))
1101 return (bb2->succ && !bb2->succ->succ_next
1102 && (bb2->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1103 && (GET_CODE (BB_END (bb2)) != JUMP_INSN || simplejump_p (BB_END (bb2))));
1105 /* Match conditional jumps - this may get tricky when fallthru and branch
1106 edges are crossed. */
1108 && bb1->succ->succ_next
1109 && !bb1->succ->succ_next->succ_next
1110 && any_condjump_p (BB_END (bb1))
1111 && onlyjump_p (BB_END (bb1)))
1113 edge b1, f1, b2, f2;
1114 bool reverse, match;
1115 rtx set1, set2, cond1, cond2;
1116 enum rtx_code code1, code2;
1119 || !bb2->succ->succ_next
1120 || bb2->succ->succ_next->succ_next
1121 || !any_condjump_p (BB_END (bb2))
1122 || !onlyjump_p (BB_END (bb2)))
1125 b1 = BRANCH_EDGE (bb1);
1126 b2 = BRANCH_EDGE (bb2);
1127 f1 = FALLTHRU_EDGE (bb1);
1128 f2 = FALLTHRU_EDGE (bb2);
1130 /* Get around possible forwarders on fallthru edges. Other cases
1131 should be optimized out already. */
1132 if (FORWARDER_BLOCK_P (f1->dest))
1133 f1 = f1->dest->succ;
1135 if (FORWARDER_BLOCK_P (f2->dest))
1136 f2 = f2->dest->succ;
1138 /* To simplify use of this function, return false if there are
1139 unneeded forwarder blocks. These will get eliminated later
1140 during cleanup_cfg. */
1141 if (FORWARDER_BLOCK_P (f1->dest)
1142 || FORWARDER_BLOCK_P (f2->dest)
1143 || FORWARDER_BLOCK_P (b1->dest)
1144 || FORWARDER_BLOCK_P (b2->dest))
1147 if (f1->dest == f2->dest && b1->dest == b2->dest)
1149 else if (f1->dest == b2->dest && b1->dest == f2->dest)
1154 set1 = pc_set (BB_END (bb1));
1155 set2 = pc_set (BB_END (bb2));
1156 if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
1157 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
1160 cond1 = XEXP (SET_SRC (set1), 0);
1161 cond2 = XEXP (SET_SRC (set2), 0);
1162 code1 = GET_CODE (cond1);
1164 code2 = reversed_comparison_code (cond2, BB_END (bb2));
1166 code2 = GET_CODE (cond2);
1168 if (code2 == UNKNOWN)
1171 /* Verify codes and operands match. */
1172 match = ((code1 == code2
1173 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
1174 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
1175 || (code1 == swap_condition (code2)
1176 && rtx_renumbered_equal_p (XEXP (cond1, 1),
1178 && rtx_renumbered_equal_p (XEXP (cond1, 0),
1181 /* If we return true, we will join the blocks. Which means that
1182 we will only have one branch prediction bit to work with. Thus
1183 we require the existing branches to have probabilities that are
1187 && maybe_hot_bb_p (bb1)
1188 && maybe_hot_bb_p (bb2))
1192 if (b1->dest == b2->dest)
1193 prob2 = b2->probability;
1195 /* Do not use f2 probability as f2 may be forwarded. */
1196 prob2 = REG_BR_PROB_BASE - b2->probability;
1198 /* Fail if the difference in probabilities is greater than 50%.
1199 This rules out two well-predicted branches with opposite
1201 if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
1204 fprintf (rtl_dump_file,
1205 "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
1206 bb1->index, bb2->index, b1->probability, prob2);
1212 if (rtl_dump_file && match)
1213 fprintf (rtl_dump_file, "Conditionals in bb %i and %i match.\n",
1214 bb1->index, bb2->index);
1219 /* Generic case - we are seeing a computed jump, table jump or trapping
1222 #ifndef CASE_DROPS_THROUGH
1223 /* Check whether there are tablejumps in the end of BB1 and BB2.
1224 Return true if they are identical. */
1229 if (tablejump_p (BB_END (bb1), &label1, &table1)
1230 && tablejump_p (BB_END (bb2), &label2, &table2)
1231 && GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2)))
1233 /* The labels should never be the same rtx. If they really are same
1234 the jump tables are same too. So disable crossjumping of blocks BB1
1235 and BB2 because when deleting the common insns in the end of BB1
1236 by delete_block () the jump table would be deleted too. */
1237 /* If LABEL2 is referenced in BB1->END do not do anything
1238 because we would loose information when replacing
1239 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1240 if (label1 != label2 && !rtx_referenced_p (label2, BB_END (bb1)))
1242 /* Set IDENTICAL to true when the tables are identical. */
1243 bool identical = false;
1246 p1 = PATTERN (table1);
1247 p2 = PATTERN (table2);
1248 if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2))
1252 else if (GET_CODE (p1) == ADDR_DIFF_VEC
1253 && (XVECLEN (p1, 1) == XVECLEN (p2, 1))
1254 && rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2))
1255 && rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3)))
1260 for (i = XVECLEN (p1, 1) - 1; i >= 0 && identical; i--)
1261 if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i)))
1267 replace_label_data rr;
1270 /* Temporarily replace references to LABEL1 with LABEL2
1271 in BB1->END so that we could compare the instructions. */
1274 rr.update_label_nuses = false;
1275 for_each_rtx (&BB_END (bb1), replace_label, &rr);
1277 match = insns_match_p (mode, BB_END (bb1), BB_END (bb2));
1278 if (rtl_dump_file && match)
1279 fprintf (rtl_dump_file,
1280 "Tablejumps in bb %i and %i match.\n",
1281 bb1->index, bb2->index);
1283 /* Set the original label in BB1->END because when deleting
1284 a block whose end is a tablejump, the tablejump referenced
1285 from the instruction is deleted too. */
1288 for_each_rtx (&BB_END (bb1), replace_label, &rr);
1298 /* First ensure that the instructions match. There may be many outgoing
1299 edges so this test is generally cheaper. */
1300 if (!insns_match_p (mode, BB_END (bb1), BB_END (bb2)))
1303 /* Search the outgoing edges, ensure that the counts do match, find possible
1304 fallthru and exception handling edges since these needs more
1306 for (e1 = bb1->succ, e2 = bb2->succ; e1 && e2;
1307 e1 = e1->succ_next, e2 = e2->succ_next)
1309 if (e1->flags & EDGE_EH)
1312 if (e2->flags & EDGE_EH)
1315 if (e1->flags & EDGE_FALLTHRU)
1317 if (e2->flags & EDGE_FALLTHRU)
1321 /* If number of edges of various types does not match, fail. */
1323 || nehedges1 != nehedges2
1324 || (fallthru1 != 0) != (fallthru2 != 0))
1327 /* fallthru edges must be forwarded to the same destination. */
1330 basic_block d1 = (forwarder_block_p (fallthru1->dest)
1331 ? fallthru1->dest->succ->dest: fallthru1->dest);
1332 basic_block d2 = (forwarder_block_p (fallthru2->dest)
1333 ? fallthru2->dest->succ->dest: fallthru2->dest);
1339 /* Ensure the same EH region. */
1341 rtx n1 = find_reg_note (BB_END (bb1), REG_EH_REGION, 0);
1342 rtx n2 = find_reg_note (BB_END (bb2), REG_EH_REGION, 0);
1347 if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
1351 /* We don't need to match the rest of edges as above checks should be enough
1352 to ensure that they are equivalent. */
1356 /* E1 and E2 are edges with the same destination block. Search their
1357 predecessors for common code. If found, redirect control flow from
1358 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1361 try_crossjump_to_edge (int mode, edge e1, edge e2)
1364 basic_block src1 = e1->src, src2 = e2->src;
1365 basic_block redirect_to, redirect_from, to_remove;
1366 rtx newpos1, newpos2;
1369 /* Search backward through forwarder blocks. We don't need to worry
1370 about multiple entry or chained forwarders, as they will be optimized
1371 away. We do this to look past the unconditional jump following a
1372 conditional jump that is required due to the current CFG shape. */
1374 && !src1->pred->pred_next
1375 && FORWARDER_BLOCK_P (src1))
1376 e1 = src1->pred, src1 = e1->src;
1379 && !src2->pred->pred_next
1380 && FORWARDER_BLOCK_P (src2))
1381 e2 = src2->pred, src2 = e2->src;
1383 /* Nothing to do if we reach ENTRY, or a common source block. */
1384 if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
1389 /* Seeing more than 1 forwarder blocks would confuse us later... */
1390 if (FORWARDER_BLOCK_P (e1->dest)
1391 && FORWARDER_BLOCK_P (e1->dest->succ->dest))
1394 if (FORWARDER_BLOCK_P (e2->dest)
1395 && FORWARDER_BLOCK_P (e2->dest->succ->dest))
1398 /* Likewise with dead code (possibly newly created by the other optimizations
1400 if (!src1->pred || !src2->pred)
1403 /* Look for the common insn sequence, part the first ... */
1404 if (!outgoing_edges_match (mode, src1, src2))
1407 /* ... and part the second. */
1408 nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
1412 #ifndef CASE_DROPS_THROUGH
1413 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1415 If we have tablejumps in the end of SRC1 and SRC2
1416 they have been already compared for equivalence in outgoing_edges_match ()
1417 so replace the references to TABLE1 by references to TABLE2. */
1422 if (tablejump_p (BB_END (src1), &label1, &table1)
1423 && tablejump_p (BB_END (src2), &label2, &table2)
1424 && label1 != label2)
1426 replace_label_data rr;
1429 /* Replace references to LABEL1 with LABEL2. */
1432 rr.update_label_nuses = true;
1433 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1435 /* Do not replace the label in SRC1->END because when deleting
1436 a block whose end is a tablejump, the tablejump referenced
1437 from the instruction is deleted too. */
1438 if (insn != BB_END (src1))
1439 for_each_rtx (&insn, replace_label, &rr);
1445 /* Avoid splitting if possible. */
1446 if (newpos2 == BB_HEAD (src2))
1451 fprintf (rtl_dump_file, "Splitting bb %i before %i insns\n",
1452 src2->index, nmatch);
1453 redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
1457 fprintf (rtl_dump_file,
1458 "Cross jumping from bb %i to bb %i; %i common insns\n",
1459 src1->index, src2->index, nmatch);
1461 redirect_to->count += src1->count;
1462 redirect_to->frequency += src1->frequency;
1463 /* We may have some registers visible trought the block. */
1464 redirect_to->flags |= BB_DIRTY;
1466 /* Recompute the frequencies and counts of outgoing edges. */
1467 for (s = redirect_to->succ; s; s = s->succ_next)
1470 basic_block d = s->dest;
1472 if (FORWARDER_BLOCK_P (d))
1475 for (s2 = src1->succ; ; s2 = s2->succ_next)
1477 basic_block d2 = s2->dest;
1478 if (FORWARDER_BLOCK_P (d2))
1479 d2 = d2->succ->dest;
1484 s->count += s2->count;
1486 /* Take care to update possible forwarder blocks. We verified
1487 that there is no more than one in the chain, so we can't run
1488 into infinite loop. */
1489 if (FORWARDER_BLOCK_P (s->dest))
1491 s->dest->succ->count += s2->count;
1492 s->dest->count += s2->count;
1493 s->dest->frequency += EDGE_FREQUENCY (s);
1496 if (FORWARDER_BLOCK_P (s2->dest))
1498 s2->dest->succ->count -= s2->count;
1499 if (s2->dest->succ->count < 0)
1500 s2->dest->succ->count = 0;
1501 s2->dest->count -= s2->count;
1502 s2->dest->frequency -= EDGE_FREQUENCY (s);
1503 if (s2->dest->frequency < 0)
1504 s2->dest->frequency = 0;
1505 if (s2->dest->count < 0)
1506 s2->dest->count = 0;
1509 if (!redirect_to->frequency && !src1->frequency)
1510 s->probability = (s->probability + s2->probability) / 2;
1513 = ((s->probability * redirect_to->frequency +
1514 s2->probability * src1->frequency)
1515 / (redirect_to->frequency + src1->frequency));
1518 update_br_prob_note (redirect_to);
1520 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1522 /* Skip possible basic block header. */
1523 if (GET_CODE (newpos1) == CODE_LABEL)
1524 newpos1 = NEXT_INSN (newpos1);
1526 if (GET_CODE (newpos1) == NOTE)
1527 newpos1 = NEXT_INSN (newpos1);
1529 redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
1530 to_remove = redirect_from->succ->dest;
1532 redirect_edge_and_branch_force (redirect_from->succ, redirect_to);
1533 delete_block (to_remove);
1535 update_forwarder_flag (redirect_from);
1540 /* Search the predecessors of BB for common insn sequences. When found,
1541 share code between them by redirecting control flow. Return true if
1542 any changes made. */
1545 try_crossjump_bb (int mode, basic_block bb)
1547 edge e, e2, nexte2, nexte, fallthru;
1551 /* Nothing to do if there is not at least two incoming edges. */
1552 if (!bb->pred || !bb->pred->pred_next)
1555 /* It is always cheapest to redirect a block that ends in a branch to
1556 a block that falls through into BB, as that adds no branches to the
1557 program. We'll try that combination first. */
1559 max = PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES);
1560 for (e = bb->pred; e ; e = e->pred_next, n++)
1562 if (e->flags & EDGE_FALLTHRU)
1569 for (e = bb->pred; e; e = nexte)
1571 nexte = e->pred_next;
1573 /* As noted above, first try with the fallthru predecessor. */
1576 /* Don't combine the fallthru edge into anything else.
1577 If there is a match, we'll do it the other way around. */
1580 /* If nothing changed since the last attempt, there is nothing
1583 && (!(e->src->flags & BB_DIRTY)
1584 && !(fallthru->src->flags & BB_DIRTY)))
1587 if (try_crossjump_to_edge (mode, e, fallthru))
1595 /* Non-obvious work limiting check: Recognize that we're going
1596 to call try_crossjump_bb on every basic block. So if we have
1597 two blocks with lots of outgoing edges (a switch) and they
1598 share lots of common destinations, then we would do the
1599 cross-jump check once for each common destination.
1601 Now, if the blocks actually are cross-jump candidates, then
1602 all of their destinations will be shared. Which means that
1603 we only need check them for cross-jump candidacy once. We
1604 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1605 choosing to do the check from the block for which the edge
1606 in question is the first successor of A. */
1607 if (e->src->succ != e)
1610 for (e2 = bb->pred; e2; e2 = nexte2)
1612 nexte2 = e2->pred_next;
1617 /* We've already checked the fallthru edge above. */
1621 /* The "first successor" check above only prevents multiple
1622 checks of crossjump(A,B). In order to prevent redundant
1623 checks of crossjump(B,A), require that A be the block
1624 with the lowest index. */
1625 if (e->src->index > e2->src->index)
1628 /* If nothing changed since the last attempt, there is nothing
1631 && (!(e->src->flags & BB_DIRTY)
1632 && !(e2->src->flags & BB_DIRTY)))
1635 if (try_crossjump_to_edge (mode, e, e2))
1647 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1648 instructions etc. Return nonzero if changes were made. */
1651 try_optimize_cfg (int mode)
1653 bool changed_overall = false;
1656 basic_block bb, b, next;
1658 if (mode & CLEANUP_CROSSJUMP)
1659 add_noreturn_fake_exit_edges ();
1662 update_forwarder_flag (bb);
1664 if (mode & (CLEANUP_UPDATE_LIFE | CLEANUP_CROSSJUMP | CLEANUP_THREADING))
1667 if (! (* targetm.cannot_modify_jumps_p) ())
1670 /* Attempt to merge blocks as made possible by edge removal. If
1671 a block has only one successor, and the successor has only
1672 one predecessor, they may be combined. */
1679 fprintf (rtl_dump_file,
1680 "\n\ntry_optimize_cfg iteration %i\n\n",
1683 for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR;)
1687 bool changed_here = false;
1689 /* Delete trivially dead basic blocks. */
1690 while (b->pred == NULL)
1694 fprintf (rtl_dump_file, "Deleting block %i.\n",
1698 if (!(mode & CLEANUP_CFGLAYOUT))
1703 /* Remove code labels no longer used. Don't do this
1704 before CALL_PLACEHOLDER is removed, as some branches
1705 may be hidden within. */
1706 if (b->pred->pred_next == NULL
1707 && (b->pred->flags & EDGE_FALLTHRU)
1708 && !(b->pred->flags & EDGE_COMPLEX)
1709 && GET_CODE (BB_HEAD (b)) == CODE_LABEL
1710 && (!(mode & CLEANUP_PRE_SIBCALL)
1711 || !tail_recursion_label_p (BB_HEAD (b)))
1712 /* If the previous block ends with a branch to this
1713 block, we can't delete the label. Normally this
1714 is a condjump that is yet to be simplified, but
1715 if CASE_DROPS_THRU, this can be a tablejump with
1716 some element going to the same place as the
1717 default (fallthru). */
1718 && (b->pred->src == ENTRY_BLOCK_PTR
1719 || GET_CODE (BB_END (b->pred->src)) != JUMP_INSN
1720 || ! label_is_jump_target_p (BB_HEAD (b),
1721 BB_END (b->pred->src))))
1723 rtx label = BB_HEAD (b);
1725 delete_insn_chain (label, label);
1726 /* In the case label is undeletable, move it after the
1727 BASIC_BLOCK note. */
1728 if (NOTE_LINE_NUMBER (BB_HEAD (b)) == NOTE_INSN_DELETED_LABEL)
1730 rtx bb_note = NEXT_INSN (BB_HEAD (b));
1732 reorder_insns_nobb (label, label, bb_note);
1733 BB_HEAD (b) = bb_note;
1736 fprintf (rtl_dump_file, "Deleted label in block %i.\n",
1740 /* If we fall through an empty block, we can remove it. */
1741 if (!(mode & CLEANUP_CFGLAYOUT)
1742 && b->pred->pred_next == NULL
1743 && (b->pred->flags & EDGE_FALLTHRU)
1744 && GET_CODE (BB_HEAD (b)) != CODE_LABEL
1745 && FORWARDER_BLOCK_P (b)
1746 /* Note that forwarder_block_p true ensures that
1747 there is a successor for this block. */
1748 && (b->succ->flags & EDGE_FALLTHRU)
1749 && n_basic_blocks > 1)
1752 fprintf (rtl_dump_file,
1753 "Deleting fallthru block %i.\n",
1756 c = b->prev_bb == ENTRY_BLOCK_PTR ? b->next_bb : b->prev_bb;
1757 redirect_edge_succ_nodup (b->pred, b->succ->dest);
1763 if ((s = b->succ) != NULL
1764 && s->succ_next == NULL
1765 && !(s->flags & EDGE_COMPLEX)
1766 && (c = s->dest) != EXIT_BLOCK_PTR
1767 && c->pred->pred_next == NULL
1770 /* When not in cfg_layout mode use code aware of reordering
1771 INSN. This code possibly creates new basic blocks so it
1772 does not fit merge_blocks interface and is kept here in
1773 hope that it will become useless once more of compiler
1774 is transformed to use cfg_layout mode. */
1776 if ((mode & CLEANUP_CFGLAYOUT)
1777 && can_merge_blocks_p (b, c))
1779 merge_blocks (b, c);
1780 update_forwarder_flag (b);
1781 changed_here = true;
1783 else if (!(mode & CLEANUP_CFGLAYOUT)
1784 /* If the jump insn has side effects,
1785 we can't kill the edge. */
1786 && (GET_CODE (BB_END (b)) != JUMP_INSN
1787 || (reload_completed
1788 ? simplejump_p (BB_END (b))
1789 : onlyjump_p (BB_END (b))))
1790 && (next = merge_blocks_move (s, b, c, mode)))
1793 changed_here = true;
1797 /* Simplify branch over branch. */
1798 if ((mode & CLEANUP_EXPENSIVE)
1799 && !(mode & CLEANUP_CFGLAYOUT)
1800 && try_simplify_condjump (b))
1801 changed_here = true;
1803 /* If B has a single outgoing edge, but uses a
1804 non-trivial jump instruction without side-effects, we
1805 can either delete the jump entirely, or replace it
1806 with a simple unconditional jump. */
1808 && ! b->succ->succ_next
1809 && b->succ->dest != EXIT_BLOCK_PTR
1810 && onlyjump_p (BB_END (b))
1811 && try_redirect_by_replacing_jump (b->succ, b->succ->dest,
1812 (mode & CLEANUP_CFGLAYOUT) != 0))
1814 update_forwarder_flag (b);
1815 changed_here = true;
1818 /* Simplify branch to branch. */
1819 if (try_forward_edges (mode, b))
1820 changed_here = true;
1822 /* Look for shared code between blocks. */
1823 if ((mode & CLEANUP_CROSSJUMP)
1824 && try_crossjump_bb (mode, b))
1825 changed_here = true;
1827 /* Don't get confused by the index shift caused by
1835 if ((mode & CLEANUP_CROSSJUMP)
1836 && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
1839 #ifdef ENABLE_CHECKING
1841 verify_flow_info ();
1844 changed_overall |= changed;
1850 if (mode & CLEANUP_CROSSJUMP)
1851 remove_fake_edges ();
1853 clear_aux_for_blocks ();
1855 return changed_overall;
1858 /* Delete all unreachable basic blocks. */
1861 delete_unreachable_blocks (void)
1863 bool changed = false;
1864 basic_block b, next_bb;
1866 find_unreachable_blocks ();
1868 /* Delete all unreachable basic blocks. */
1870 for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
1872 next_bb = b->next_bb;
1874 if (!(b->flags & BB_REACHABLE))
1882 tidy_fallthru_edges ();
1886 /* Tidy the CFG by deleting unreachable code and whatnot. */
1889 cleanup_cfg (int mode)
1891 bool changed = false;
1893 timevar_push (TV_CLEANUP_CFG);
1894 if (delete_unreachable_blocks ())
1897 /* We've possibly created trivially dead code. Cleanup it right
1898 now to introduce more opportunities for try_optimize_cfg. */
1899 if (!(mode & (CLEANUP_NO_INSN_DEL
1900 | CLEANUP_UPDATE_LIFE | CLEANUP_PRE_SIBCALL))
1901 && !reload_completed)
1902 delete_trivially_dead_insns (get_insns(), max_reg_num ());
1907 while (try_optimize_cfg (mode))
1909 delete_unreachable_blocks (), changed = true;
1910 if (mode & CLEANUP_UPDATE_LIFE)
1912 /* Cleaning up CFG introduces more opportunities for dead code
1913 removal that in turn may introduce more opportunities for
1914 cleaning up the CFG. */
1915 if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
1917 | PROP_SCAN_DEAD_CODE
1918 | PROP_KILL_DEAD_CODE
1919 | ((mode & CLEANUP_LOG_LINKS)
1920 ? PROP_LOG_LINKS : 0)))
1923 else if (!(mode & (CLEANUP_NO_INSN_DEL | CLEANUP_PRE_SIBCALL))
1924 && (mode & CLEANUP_EXPENSIVE)
1925 && !reload_completed)
1927 if (!delete_trivially_dead_insns (get_insns(), max_reg_num ()))
1932 delete_dead_jumptables ();
1935 /* Kill the data we won't maintain. */
1936 free_EXPR_LIST_list (&label_value_list);
1937 timevar_pop (TV_CLEANUP_CFG);