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 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* This file contains optimizer of the control flow. The main entrypoint is
23 cleanup_cfg. Following optimizations are performed:
25 - Unreachable blocks removal
26 - Edge forwarding (edge to the forwarder block is forwarded to it's
27 successor. Simplification of the branch instruction is performed by
28 underlying infrastructure so branch can be converted to simplejump or
30 - Cross jumping (tail merging)
31 - Conditional jump-around-simplejump simplification
32 - Basic block merging. */
37 #include "hard-reg-set.h"
38 #include "basic-block.h"
41 #include "insn-config.h"
51 /* cleanup_cfg maintains following flags for each basic block. */
55 /* Set if BB is the forwarder block to avoid too many
56 forwarder_block_p calls. */
57 BB_FORWARDER_BLOCK = 1,
58 BB_NONTHREADABLE_BLOCK = 2
61 #define BB_FLAGS(BB) (enum bb_flags) (BB)->aux
62 #define BB_SET_FLAG(BB, FLAG) \
63 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux | (FLAG))
64 #define BB_CLEAR_FLAG(BB, FLAG) \
65 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux & ~(FLAG))
67 #define FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK)
69 static bool try_crossjump_to_edge PARAMS ((int, edge, edge));
70 static bool try_crossjump_bb PARAMS ((int, basic_block));
71 static bool outgoing_edges_match PARAMS ((int,
72 basic_block, basic_block));
73 static int flow_find_cross_jump PARAMS ((int, basic_block, basic_block,
75 static bool insns_match_p PARAMS ((int, rtx, rtx));
77 static bool label_is_jump_target_p PARAMS ((rtx, rtx));
78 static bool tail_recursion_label_p PARAMS ((rtx));
79 static void merge_blocks_move_predecessor_nojumps PARAMS ((basic_block,
81 static void merge_blocks_move_successor_nojumps PARAMS ((basic_block,
83 static bool merge_blocks PARAMS ((edge,basic_block,basic_block,
85 static bool try_optimize_cfg PARAMS ((int));
86 static bool try_simplify_condjump PARAMS ((basic_block));
87 static bool try_forward_edges PARAMS ((int, basic_block));
88 static edge thread_jump PARAMS ((int, edge, basic_block));
89 static bool mark_effect PARAMS ((rtx, bitmap));
90 static void notice_new_block PARAMS ((basic_block));
91 static void update_forwarder_flag PARAMS ((basic_block));
92 static int mentions_nonequal_regs PARAMS ((rtx *, void *));
94 /* Set flags for newly created block. */
103 if (forwarder_block_p (bb))
104 BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
107 /* Recompute forwarder flag after block has been modified. */
110 update_forwarder_flag (bb)
113 if (forwarder_block_p (bb))
114 BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
116 BB_CLEAR_FLAG (bb, BB_FORWARDER_BLOCK);
119 /* Simplify a conditional jump around an unconditional jump.
120 Return true if something changed. */
123 try_simplify_condjump (cbranch_block)
124 basic_block cbranch_block;
126 basic_block jump_block, jump_dest_block, cbranch_dest_block;
127 edge cbranch_jump_edge, cbranch_fallthru_edge;
130 /* Verify that there are exactly two successors. */
131 if (!cbranch_block->succ
132 || !cbranch_block->succ->succ_next
133 || cbranch_block->succ->succ_next->succ_next)
136 /* Verify that we've got a normal conditional branch at the end
138 cbranch_insn = cbranch_block->end;
139 if (!any_condjump_p (cbranch_insn))
142 cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
143 cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
145 /* The next block must not have multiple predecessors, must not
146 be the last block in the function, and must contain just the
147 unconditional jump. */
148 jump_block = cbranch_fallthru_edge->dest;
149 if (jump_block->pred->pred_next
150 || jump_block->index == n_basic_blocks - 1
151 || !FORWARDER_BLOCK_P (jump_block))
153 jump_dest_block = jump_block->succ->dest;
155 /* The conditional branch must target the block after the
156 unconditional branch. */
157 cbranch_dest_block = cbranch_jump_edge->dest;
159 if (!can_fallthru (jump_block, cbranch_dest_block))
162 /* Invert the conditional branch. */
163 if (!invert_jump (cbranch_insn, block_label (jump_dest_block), 0))
167 fprintf (rtl_dump_file, "Simplifying condjump %i around jump %i\n",
168 INSN_UID (cbranch_insn), INSN_UID (jump_block->end));
170 /* Success. Update the CFG to match. Note that after this point
171 the edge variable names appear backwards; the redirection is done
172 this way to preserve edge profile data. */
173 cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
175 cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
177 cbranch_jump_edge->flags |= EDGE_FALLTHRU;
178 cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
179 update_br_prob_note (cbranch_block);
181 /* Delete the block with the unconditional jump, and clean up the mess. */
182 flow_delete_block (jump_block);
183 tidy_fallthru_edge (cbranch_jump_edge, cbranch_block, cbranch_dest_block);
188 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
189 on register. Used by jump threading. */
192 mark_effect (exp, nonequal)
198 switch (GET_CODE (exp))
200 /* In case we do clobber the register, mark it as equal, as we know the
201 value is dead so it don't have to match. */
203 if (REG_P (XEXP (exp, 0)))
205 dest = XEXP (exp, 0);
206 regno = REGNO (dest);
207 CLEAR_REGNO_REG_SET (nonequal, regno);
208 if (regno < FIRST_PSEUDO_REGISTER)
210 int n = HARD_REGNO_NREGS (regno, GET_MODE (dest));
212 CLEAR_REGNO_REG_SET (nonequal, regno + n);
218 if (rtx_equal_for_cselib_p (SET_DEST (exp), SET_SRC (exp)))
220 dest = SET_DEST (exp);
225 regno = REGNO (dest);
226 SET_REGNO_REG_SET (nonequal, regno);
227 if (regno < FIRST_PSEUDO_REGISTER)
229 int n = HARD_REGNO_NREGS (regno, GET_MODE (dest));
231 SET_REGNO_REG_SET (nonequal, regno + n);
240 /* Return nonzero if X is an register set in regset DATA.
241 Called via for_each_rtx. */
243 mentions_nonequal_regs (x, data)
247 regset nonequal = (regset) data;
253 if (REGNO_REG_SET_P (nonequal, regno))
255 if (regno < FIRST_PSEUDO_REGISTER)
257 int n = HARD_REGNO_NREGS (regno, GET_MODE (*x));
259 if (REGNO_REG_SET_P (nonequal, regno + n))
265 /* Attempt to prove that the basic block B will have no side effects and
266 allways continues in the same edge if reached via E. Return the edge
267 if exist, NULL otherwise. */
270 thread_jump (mode, e, b)
275 rtx set1, set2, cond1, cond2, insn;
276 enum rtx_code code1, code2, reversed_code2;
277 bool reverse1 = false;
282 if (BB_FLAGS (b) & BB_NONTHREADABLE_BLOCK)
285 /* At the moment, we do handle only conditional jumps, but later we may
286 want to extend this code to tablejumps and others. */
287 if (!e->src->succ->succ_next || e->src->succ->succ_next->succ_next)
289 if (!b->succ || !b->succ->succ_next || b->succ->succ_next->succ_next)
291 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
295 /* Second branch must end with onlyjump, as we will eliminate the jump. */
296 if (!any_condjump_p (e->src->end))
299 if (!any_condjump_p (b->end) || !onlyjump_p (b->end))
301 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
305 set1 = pc_set (e->src->end);
306 set2 = pc_set (b->end);
307 if (((e->flags & EDGE_FALLTHRU) != 0)
308 != (XEXP (SET_SRC (set1), 1) == pc_rtx))
311 cond1 = XEXP (SET_SRC (set1), 0);
312 cond2 = XEXP (SET_SRC (set2), 0);
314 code1 = reversed_comparison_code (cond1, e->src->end);
316 code1 = GET_CODE (cond1);
318 code2 = GET_CODE (cond2);
319 reversed_code2 = reversed_comparison_code (cond2, b->end);
321 if (!comparison_dominates_p (code1, code2)
322 && !comparison_dominates_p (code1, reversed_code2))
325 /* Ensure that the comparison operators are equivalent.
326 ??? This is far too pesimistic. We should allow swapped operands,
327 different CCmodes, or for example comparisons for interval, that
328 dominate even when operands are not equivalent. */
329 if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
330 || !rtx_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
333 /* Short circuit cases where block B contains some side effects, as we can't
335 for (insn = NEXT_INSN (b->head); insn != NEXT_INSN (b->end);
336 insn = NEXT_INSN (insn))
337 if (INSN_P (insn) && side_effects_p (PATTERN (insn)))
339 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
345 /* First process all values computed in the source basic block. */
346 for (insn = NEXT_INSN (e->src->head); insn != NEXT_INSN (e->src->end);
347 insn = NEXT_INSN (insn))
349 cselib_process_insn (insn);
351 nonequal = BITMAP_XMALLOC();
352 CLEAR_REG_SET (nonequal);
354 /* Now assume that we've continued by the edge E to B and continue
355 processing as if it were same basic block.
356 Our goal is to prove that whole block is an NOOP. */
358 for (insn = NEXT_INSN (b->head); insn != NEXT_INSN (b->end) && !failed;
359 insn = NEXT_INSN (insn))
363 rtx pat = PATTERN (insn);
365 if (GET_CODE (pat) == PARALLEL)
367 for (i = 0; i < XVECLEN (pat, 0); i++)
368 failed |= mark_effect (XVECEXP (pat, 0, i), nonequal);
371 failed |= mark_effect (pat, nonequal);
374 cselib_process_insn (insn);
377 /* Later we should clear nonequal of dead registers. So far we don't
378 have life information in cfg_cleanup. */
381 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
385 /* cond2 must not mention any register that is not equal to the
387 if (for_each_rtx (&cond2, mentions_nonequal_regs, nonequal))
390 /* In case liveness information is available, we need to prove equivalence
391 only of the live values. */
392 if (mode & CLEANUP_UPDATE_LIFE)
393 AND_REG_SET (nonequal, b->global_live_at_end);
395 EXECUTE_IF_SET_IN_REG_SET (nonequal, 0, i, goto failed_exit;);
397 BITMAP_XFREE (nonequal);
399 if ((comparison_dominates_p (code1, code2) != 0)
400 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
401 return BRANCH_EDGE (b);
403 return FALLTHRU_EDGE (b);
406 BITMAP_XFREE (nonequal);
411 /* Attempt to forward edges leaving basic block B.
412 Return true if successful. */
415 try_forward_edges (mode, b)
419 bool changed = false;
420 edge e, next, *threaded_edges = NULL;
422 for (e = b->succ; e; e = next)
424 basic_block target, first;
426 bool threaded = false;
427 int nthreaded_edges = 0;
431 /* Skip complex edges because we don't know how to update them.
433 Still handle fallthru edges, as we can succeed to forward fallthru
434 edge to the same place as the branch edge of conditional branch
435 and turn conditional branch to an unconditional branch. */
436 if (e->flags & EDGE_COMPLEX)
439 target = first = e->dest;
442 while (counter < n_basic_blocks)
444 basic_block new_target = NULL;
445 bool new_target_threaded = false;
447 if (FORWARDER_BLOCK_P (target)
448 && target->succ->dest != EXIT_BLOCK_PTR)
450 /* Bypass trivial infinite loops. */
451 if (target == target->succ->dest)
452 counter = n_basic_blocks;
453 new_target = target->succ->dest;
456 /* Allow to thread only over one edge at time to simplify updating
458 else if (mode & CLEANUP_THREADING)
460 edge t = thread_jump (mode, e, target);
464 threaded_edges = xmalloc (sizeof (*threaded_edges)
470 /* Detect an infinite loop across blocks not
471 including the start block. */
472 for (i = 0; i < nthreaded_edges; ++i)
473 if (threaded_edges[i] == t)
475 if (i < nthreaded_edges)
477 counter = n_basic_blocks;
482 /* Detect an infinite loop across the start block. */
486 if (nthreaded_edges >= n_basic_blocks)
488 threaded_edges[nthreaded_edges++] = t;
490 new_target = t->dest;
491 new_target_threaded = true;
498 /* Avoid killing of loop pre-headers, as it is the place loop
499 optimizer wants to hoist code to.
501 For fallthru forwarders, the LOOP_BEG note must appear between
502 the header of block and CODE_LABEL of the loop, for non forwarders
503 it must appear before the JUMP_INSN. */
504 if (mode & CLEANUP_PRE_LOOP)
506 rtx insn = (target->succ->flags & EDGE_FALLTHRU
507 ? target->head : prev_nonnote_insn (target->end));
509 if (GET_CODE (insn) != NOTE)
510 insn = NEXT_INSN (insn);
512 for (; insn && GET_CODE (insn) != CODE_LABEL && !INSN_P (insn);
513 insn = NEXT_INSN (insn))
514 if (GET_CODE (insn) == NOTE
515 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
518 if (GET_CODE (insn) == NOTE)
524 threaded |= new_target_threaded;
527 if (counter >= n_basic_blocks)
530 fprintf (rtl_dump_file, "Infinite loop in BB %i.\n",
533 else if (target == first)
534 ; /* We didn't do anything. */
537 /* Save the values now, as the edge may get removed. */
538 gcov_type edge_count = e->count;
539 int edge_probability = e->probability;
543 /* Don't force if target is exit block. */
544 if (threaded && target != EXIT_BLOCK_PTR)
546 notice_new_block (redirect_edge_and_branch_force (e, target));
548 fprintf (rtl_dump_file, "Conditionals threaded.\n");
550 else if (!redirect_edge_and_branch (e, target))
553 fprintf (rtl_dump_file,
554 "Forwarding edge %i->%i to %i failed.\n",
555 b->index, e->dest->index, target->index);
559 /* We successfully forwarded the edge. Now update profile
560 data: for each edge we traversed in the chain, remove
561 the original edge's execution count. */
562 edge_frequency = ((edge_probability * b->frequency
563 + REG_BR_PROB_BASE / 2)
566 if (!FORWARDER_BLOCK_P (b) && forwarder_block_p (b))
567 BB_SET_FLAG (b, BB_FORWARDER_BLOCK);
573 first->count -= edge_count;
574 if (first->count < 0)
576 first->frequency -= edge_frequency;
577 if (first->frequency < 0)
578 first->frequency = 0;
579 if (first->succ->succ_next)
583 if (n >= nthreaded_edges)
585 t = threaded_edges [n++];
588 if (first->frequency)
589 prob = edge_frequency * REG_BR_PROB_BASE / first->frequency;
592 if (prob > t->probability)
593 prob = t->probability;
594 t->probability -= prob;
595 prob = REG_BR_PROB_BASE - prob;
598 first->succ->probability = REG_BR_PROB_BASE;
599 first->succ->succ_next->probability = 0;
602 for (e = first->succ; e; e = e->succ_next)
603 e->probability = ((e->probability * REG_BR_PROB_BASE)
605 update_br_prob_note (first);
609 /* It is possible that as the result of
610 threading we've removed edge as it is
611 threaded to the fallthru edge. Avoid
612 getting out of sync. */
613 if (n < nthreaded_edges
614 && first == threaded_edges [n]->src)
619 t->count -= edge_count;
624 while (first != target);
631 free (threaded_edges);
635 /* Return true if LABEL is a target of JUMP_INSN. This applies only
636 to non-complex jumps. That is, direct unconditional, conditional,
637 and tablejumps, but not computed jumps or returns. It also does
638 not apply to the fallthru case of a conditional jump. */
641 label_is_jump_target_p (label, jump_insn)
642 rtx label, jump_insn;
644 rtx tmp = JUMP_LABEL (jump_insn);
650 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
651 && GET_CODE (tmp) == JUMP_INSN
652 && (tmp = PATTERN (tmp),
653 GET_CODE (tmp) == ADDR_VEC
654 || GET_CODE (tmp) == ADDR_DIFF_VEC))
656 rtvec vec = XVEC (tmp, GET_CODE (tmp) == ADDR_DIFF_VEC);
657 int i, veclen = GET_NUM_ELEM (vec);
659 for (i = 0; i < veclen; ++i)
660 if (XEXP (RTVEC_ELT (vec, i), 0) == label)
667 /* Return true if LABEL is used for tail recursion. */
670 tail_recursion_label_p (label)
675 for (x = tail_recursion_label_list; x; x = XEXP (x, 1))
676 if (label == XEXP (x, 0))
682 /* Blocks A and B are to be merged into a single block. A has no incoming
683 fallthru edge, so it can be moved before B without adding or modifying
684 any jumps (aside from the jump from A to B). */
687 merge_blocks_move_predecessor_nojumps (a, b)
693 barrier = next_nonnote_insn (a->end);
694 if (GET_CODE (barrier) != BARRIER)
696 delete_insn (barrier);
698 /* Move block and loop notes out of the chain so that we do not
701 ??? A better solution would be to squeeze out all the non-nested notes
702 and adjust the block trees appropriately. Even better would be to have
703 a tighter connection between block trees and rtl so that this is not
705 if (squeeze_notes (&a->head, &a->end))
708 /* Scramble the insn chain. */
709 if (a->end != PREV_INSN (b->head))
710 reorder_insns_nobb (a->head, a->end, PREV_INSN (b->head));
711 a->flags |= BB_DIRTY;
714 fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
717 /* Swap the records for the two blocks around. Although we are deleting B,
718 A is now where B was and we want to compact the BB array from where
720 BASIC_BLOCK (a->index) = b;
721 BASIC_BLOCK (b->index) = a;
726 /* Now blocks A and B are contiguous. Merge them. */
727 merge_blocks_nomove (a, b);
730 /* Blocks A and B are to be merged into a single block. B has no outgoing
731 fallthru edge, so it can be moved after A without adding or modifying
732 any jumps (aside from the jump from A to B). */
735 merge_blocks_move_successor_nojumps (a, b)
738 rtx barrier, real_b_end;
741 barrier = NEXT_INSN (b->end);
743 /* Recognize a jump table following block B. */
745 && GET_CODE (barrier) == CODE_LABEL
746 && NEXT_INSN (barrier)
747 && GET_CODE (NEXT_INSN (barrier)) == JUMP_INSN
748 && (GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_VEC
749 || GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_DIFF_VEC))
751 /* Temporarily add the table jump insn to b, so that it will also
752 be moved to the correct location. */
753 b->end = NEXT_INSN (barrier);
754 barrier = NEXT_INSN (b->end);
757 /* There had better have been a barrier there. Delete it. */
758 if (barrier && GET_CODE (barrier) == BARRIER)
759 delete_insn (barrier);
761 /* Move block and loop notes out of the chain so that we do not
764 ??? A better solution would be to squeeze out all the non-nested notes
765 and adjust the block trees appropriately. Even better would be to have
766 a tighter connection between block trees and rtl so that this is not
768 if (squeeze_notes (&b->head, &b->end))
771 /* Scramble the insn chain. */
772 reorder_insns_nobb (b->head, b->end, a->end);
774 /* Restore the real end of b. */
778 fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
781 /* Now blocks A and B are contiguous. Merge them. */
782 merge_blocks_nomove (a, b);
785 /* Attempt to merge basic blocks that are potentially non-adjacent.
786 Return true iff the attempt succeeded. */
789 merge_blocks (e, b, c, mode)
794 /* If C has a tail recursion label, do not merge. There is no
795 edge recorded from the call_placeholder back to this label, as
796 that would make optimize_sibling_and_tail_recursive_calls more
797 complex for no gain. */
798 if ((mode & CLEANUP_PRE_SIBCALL)
799 && GET_CODE (c->head) == CODE_LABEL
800 && tail_recursion_label_p (c->head))
803 /* If B has a fallthru edge to C, no need to move anything. */
804 if (e->flags & EDGE_FALLTHRU)
806 int b_index = b->index, c_index = c->index;
807 merge_blocks_nomove (b, c);
808 update_forwarder_flag (b);
811 fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
817 /* Otherwise we will need to move code around. Do that only if expensive
818 transformations are allowed. */
819 else if (mode & CLEANUP_EXPENSIVE)
821 edge tmp_edge, b_fallthru_edge;
822 bool c_has_outgoing_fallthru;
823 bool b_has_incoming_fallthru;
825 /* Avoid overactive code motion, as the forwarder blocks should be
826 eliminated by edge redirection instead. One exception might have
827 been if B is a forwarder block and C has no fallthru edge, but
828 that should be cleaned up by bb-reorder instead. */
829 if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
832 /* We must make sure to not munge nesting of lexical blocks,
833 and loop notes. This is done by squeezing out all the notes
834 and leaving them there to lie. Not ideal, but functional. */
836 for (tmp_edge = c->succ; tmp_edge; tmp_edge = tmp_edge->succ_next)
837 if (tmp_edge->flags & EDGE_FALLTHRU)
840 c_has_outgoing_fallthru = (tmp_edge != NULL);
842 for (tmp_edge = b->pred; tmp_edge; tmp_edge = tmp_edge->pred_next)
843 if (tmp_edge->flags & EDGE_FALLTHRU)
846 b_has_incoming_fallthru = (tmp_edge != NULL);
847 b_fallthru_edge = tmp_edge;
849 /* Otherwise, we're going to try to move C after B. If C does
850 not have an outgoing fallthru, then it can be moved
851 immediately after B without introducing or modifying jumps. */
852 if (! c_has_outgoing_fallthru)
854 merge_blocks_move_successor_nojumps (b, c);
858 /* If B does not have an incoming fallthru, then it can be moved
859 immediately before C without introducing or modifying jumps.
860 C cannot be the first block, so we do not have to worry about
861 accessing a non-existent block. */
863 if (b_has_incoming_fallthru)
867 if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
869 bb = force_nonfallthru (b_fallthru_edge);
871 notice_new_block (bb);
874 merge_blocks_move_predecessor_nojumps (b, c);
882 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
885 insns_match_p (mode, i1, i2)
886 int mode ATTRIBUTE_UNUSED;
891 /* Verify that I1 and I2 are equivalent. */
892 if (GET_CODE (i1) != GET_CODE (i2))
898 if (GET_CODE (p1) != GET_CODE (p2))
901 /* If this is a CALL_INSN, compare register usage information.
902 If we don't check this on stack register machines, the two
903 CALL_INSNs might be merged leaving reg-stack.c with mismatching
904 numbers of stack registers in the same basic block.
905 If we don't check this on machines with delay slots, a delay slot may
906 be filled that clobbers a parameter expected by the subroutine.
908 ??? We take the simple route for now and assume that if they're
909 equal, they were constructed identically. */
911 if (GET_CODE (i1) == CALL_INSN
912 && !rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
913 CALL_INSN_FUNCTION_USAGE (i2)))
917 /* If cross_jump_death_matters is not 0, the insn's mode
918 indicates whether or not the insn contains any stack-like
921 if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
923 /* If register stack conversion has already been done, then
924 death notes must also be compared before it is certain that
925 the two instruction streams match. */
928 HARD_REG_SET i1_regset, i2_regset;
930 CLEAR_HARD_REG_SET (i1_regset);
931 CLEAR_HARD_REG_SET (i2_regset);
933 for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
934 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
935 SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
937 for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
938 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
939 SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
941 GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
951 ? ! rtx_renumbered_equal_p (p1, p2) : ! rtx_equal_p (p1, p2))
953 /* The following code helps take care of G++ cleanups. */
954 rtx equiv1 = find_reg_equal_equiv_note (i1);
955 rtx equiv2 = find_reg_equal_equiv_note (i2);
958 /* If the equivalences are not to a constant, they may
959 reference pseudos that no longer exist, so we can't
961 && (! reload_completed
962 || (CONSTANT_P (XEXP (equiv1, 0))
963 && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
965 rtx s1 = single_set (i1);
966 rtx s2 = single_set (i2);
967 if (s1 != 0 && s2 != 0
968 && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
970 validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
971 validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
972 if (! rtx_renumbered_equal_p (p1, p2))
974 else if (apply_change_group ())
985 /* Look through the insns at the end of BB1 and BB2 and find the longest
986 sequence that are equivalent. Store the first insns for that sequence
987 in *F1 and *F2 and return the sequence length.
989 To simplify callers of this function, if the blocks match exactly,
990 store the head of the blocks in *F1 and *F2. */
993 flow_find_cross_jump (mode, bb1, bb2, f1, f2)
994 int mode ATTRIBUTE_UNUSED;
995 basic_block bb1, bb2;
998 rtx i1, i2, last1, last2, afterlast1, afterlast2;
1001 /* Skip simple jumps at the end of the blocks. Complex jumps still
1002 need to be compared for equivalence, which we'll do below. */
1005 last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
1007 || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
1010 i1 = PREV_INSN (i1);
1015 || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
1018 /* Count everything except for unconditional jump as insn. */
1019 if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
1021 i2 = PREV_INSN (i2);
1027 while (!active_insn_p (i1) && i1 != bb1->head)
1028 i1 = PREV_INSN (i1);
1030 while (!active_insn_p (i2) && i2 != bb2->head)
1031 i2 = PREV_INSN (i2);
1033 if (i1 == bb1->head || i2 == bb2->head)
1036 if (!insns_match_p (mode, i1, i2))
1039 /* Don't begin a cross-jump with a USE or CLOBBER insn. */
1040 if (active_insn_p (i1))
1042 /* If the merged insns have different REG_EQUAL notes, then
1044 rtx equiv1 = find_reg_equal_equiv_note (i1);
1045 rtx equiv2 = find_reg_equal_equiv_note (i2);
1047 if (equiv1 && !equiv2)
1048 remove_note (i1, equiv1);
1049 else if (!equiv1 && equiv2)
1050 remove_note (i2, equiv2);
1051 else if (equiv1 && equiv2
1052 && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
1054 remove_note (i1, equiv1);
1055 remove_note (i2, equiv2);
1058 afterlast1 = last1, afterlast2 = last2;
1059 last1 = i1, last2 = i2;
1063 i1 = PREV_INSN (i1);
1064 i2 = PREV_INSN (i2);
1068 /* Don't allow the insn after a compare to be shared by
1069 cross-jumping unless the compare is also shared. */
1070 if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
1071 last1 = afterlast1, last2 = afterlast2, ninsns--;
1074 /* Include preceding notes and labels in the cross-jump. One,
1075 this may bring us to the head of the blocks as requested above.
1076 Two, it keeps line number notes as matched as may be. */
1079 while (last1 != bb1->head && !active_insn_p (PREV_INSN (last1)))
1080 last1 = PREV_INSN (last1);
1082 if (last1 != bb1->head && GET_CODE (PREV_INSN (last1)) == CODE_LABEL)
1083 last1 = PREV_INSN (last1);
1085 while (last2 != bb2->head && !active_insn_p (PREV_INSN (last2)))
1086 last2 = PREV_INSN (last2);
1088 if (last2 != bb2->head && GET_CODE (PREV_INSN (last2)) == CODE_LABEL)
1089 last2 = PREV_INSN (last2);
1098 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1099 the branch instruction. This means that if we commonize the control
1100 flow before end of the basic block, the semantic remains unchanged.
1102 We may assume that there exists one edge with a common destination. */
1105 outgoing_edges_match (mode, bb1, bb2)
1110 int nehedges1 = 0, nehedges2 = 0;
1111 edge fallthru1 = 0, fallthru2 = 0;
1114 /* If BB1 has only one successor, we may be looking at either an
1115 unconditional jump, or a fake edge to exit. */
1116 if (bb1->succ && !bb1->succ->succ_next
1117 && !(bb1->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)))
1118 return (bb2->succ && !bb2->succ->succ_next
1119 && (bb2->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0);
1121 /* Match conditional jumps - this may get tricky when fallthru and branch
1122 edges are crossed. */
1124 && bb1->succ->succ_next
1125 && !bb1->succ->succ_next->succ_next
1126 && any_condjump_p (bb1->end)
1127 && onlyjump_p (bb1->end))
1129 edge b1, f1, b2, f2;
1130 bool reverse, match;
1131 rtx set1, set2, cond1, cond2;
1132 enum rtx_code code1, code2;
1135 || !bb2->succ->succ_next
1136 || bb2->succ->succ_next->succ_next
1137 || !any_condjump_p (bb2->end)
1138 || !onlyjump_p (bb2->end))
1141 /* Do not crossjump across loop boundaries. This is a temporary
1142 workaround for the common scenario in which crossjumping results
1143 in killing the duplicated loop condition, making bb-reorder rotate
1144 the loop incorectly, leaving an extra unconditional jump inside
1147 This check should go away once bb-reorder knows how to duplicate
1148 code in this case or rotate the loops to avoid this scenario. */
1149 if (bb1->loop_depth != bb2->loop_depth)
1152 b1 = BRANCH_EDGE (bb1);
1153 b2 = BRANCH_EDGE (bb2);
1154 f1 = FALLTHRU_EDGE (bb1);
1155 f2 = FALLTHRU_EDGE (bb2);
1157 /* Get around possible forwarders on fallthru edges. Other cases
1158 should be optimized out already. */
1159 if (FORWARDER_BLOCK_P (f1->dest))
1160 f1 = f1->dest->succ;
1162 if (FORWARDER_BLOCK_P (f2->dest))
1163 f2 = f2->dest->succ;
1165 /* To simplify use of this function, return false if there are
1166 unneeded forwarder blocks. These will get eliminated later
1167 during cleanup_cfg. */
1168 if (FORWARDER_BLOCK_P (f1->dest)
1169 || FORWARDER_BLOCK_P (f2->dest)
1170 || FORWARDER_BLOCK_P (b1->dest)
1171 || FORWARDER_BLOCK_P (b2->dest))
1174 if (f1->dest == f2->dest && b1->dest == b2->dest)
1176 else if (f1->dest == b2->dest && b1->dest == f2->dest)
1181 set1 = pc_set (bb1->end);
1182 set2 = pc_set (bb2->end);
1183 if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
1184 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
1187 cond1 = XEXP (SET_SRC (set1), 0);
1188 cond2 = XEXP (SET_SRC (set2), 0);
1189 code1 = GET_CODE (cond1);
1191 code2 = reversed_comparison_code (cond2, bb2->end);
1193 code2 = GET_CODE (cond2);
1195 if (code2 == UNKNOWN)
1198 /* Verify codes and operands match. */
1199 match = ((code1 == code2
1200 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
1201 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
1202 || (code1 == swap_condition (code2)
1203 && rtx_renumbered_equal_p (XEXP (cond1, 1),
1205 && rtx_renumbered_equal_p (XEXP (cond1, 0),
1208 /* If we return true, we will join the blocks. Which means that
1209 we will only have one branch prediction bit to work with. Thus
1210 we require the existing branches to have probabilities that are
1214 && maybe_hot_bb_p (bb1)
1215 && maybe_hot_bb_p (bb2))
1219 if (b1->dest == b2->dest)
1220 prob2 = b2->probability;
1222 /* Do not use f2 probability as f2 may be forwarded. */
1223 prob2 = REG_BR_PROB_BASE - b2->probability;
1225 /* Fail if the difference in probabilities is greater than 50%.
1226 This rules out two well-predicted branches with opposite
1228 if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
1231 fprintf (rtl_dump_file,
1232 "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
1233 bb1->index, bb2->index, b1->probability, prob2);
1239 if (rtl_dump_file && match)
1240 fprintf (rtl_dump_file, "Conditionals in bb %i and %i match.\n",
1241 bb1->index, bb2->index);
1246 /* Generic case - we are seeing an computed jump, table jump or trapping
1249 /* First ensure that the instructions match. There may be many outgoing
1250 edges so this test is generally cheaper.
1251 ??? Currently the tablejumps will never match, as they do have
1252 different tables. */
1253 if (!insns_match_p (mode, bb1->end, bb2->end))
1256 /* Search the outgoing edges, ensure that the counts do match, find possible
1257 fallthru and exception handling edges since these needs more
1259 for (e1 = bb1->succ, e2 = bb2->succ; e1 && e2;
1260 e1 = e1->succ_next, e2 = e2->succ_next)
1262 if (e1->flags & EDGE_EH)
1265 if (e2->flags & EDGE_EH)
1268 if (e1->flags & EDGE_FALLTHRU)
1270 if (e2->flags & EDGE_FALLTHRU)
1274 /* If number of edges of various types does not match, fail. */
1276 || nehedges1 != nehedges2
1277 || (fallthru1 != 0) != (fallthru2 != 0))
1280 /* fallthru edges must be forwarded to the same destination. */
1283 basic_block d1 = (forwarder_block_p (fallthru1->dest)
1284 ? fallthru1->dest->succ->dest: fallthru1->dest);
1285 basic_block d2 = (forwarder_block_p (fallthru2->dest)
1286 ? fallthru2->dest->succ->dest: fallthru2->dest);
1292 /* In case we do have EH edges, ensure we are in the same region. */
1295 rtx n1 = find_reg_note (bb1->end, REG_EH_REGION, 0);
1296 rtx n2 = find_reg_note (bb2->end, REG_EH_REGION, 0);
1298 if (XEXP (n1, 0) != XEXP (n2, 0))
1302 /* We don't need to match the rest of edges as above checks should be enought
1303 to ensure that they are equivalent. */
1307 /* E1 and E2 are edges with the same destination block. Search their
1308 predecessors for common code. If found, redirect control flow from
1309 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1312 try_crossjump_to_edge (mode, e1, e2)
1317 basic_block src1 = e1->src, src2 = e2->src;
1318 basic_block redirect_to;
1319 rtx newpos1, newpos2;
1324 /* Search backward through forwarder blocks. We don't need to worry
1325 about multiple entry or chained forwarders, as they will be optimized
1326 away. We do this to look past the unconditional jump following a
1327 conditional jump that is required due to the current CFG shape. */
1329 && !src1->pred->pred_next
1330 && FORWARDER_BLOCK_P (src1))
1331 e1 = src1->pred, src1 = e1->src;
1334 && !src2->pred->pred_next
1335 && FORWARDER_BLOCK_P (src2))
1336 e2 = src2->pred, src2 = e2->src;
1338 /* Nothing to do if we reach ENTRY, or a common source block. */
1339 if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
1344 /* Seeing more than 1 forwarder blocks would confuse us later... */
1345 if (FORWARDER_BLOCK_P (e1->dest)
1346 && FORWARDER_BLOCK_P (e1->dest->succ->dest))
1349 if (FORWARDER_BLOCK_P (e2->dest)
1350 && FORWARDER_BLOCK_P (e2->dest->succ->dest))
1353 /* Likewise with dead code (possibly newly created by the other optimizations
1355 if (!src1->pred || !src2->pred)
1358 /* Look for the common insn sequence, part the first ... */
1359 if (!outgoing_edges_match (mode, src1, src2))
1362 /* ... and part the second. */
1363 nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
1367 /* Avoid splitting if possible. */
1368 if (newpos2 == src2->head)
1373 fprintf (rtl_dump_file, "Splitting bb %i before %i insns\n",
1374 src2->index, nmatch);
1375 redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
1379 fprintf (rtl_dump_file,
1380 "Cross jumping from bb %i to bb %i; %i common insns\n",
1381 src1->index, src2->index, nmatch);
1383 redirect_to->count += src1->count;
1384 redirect_to->frequency += src1->frequency;
1385 /* We may have some registers visible trought the block. */
1386 redirect_to->flags |= BB_DIRTY;
1388 /* Recompute the frequencies and counts of outgoing edges. */
1389 for (s = redirect_to->succ; s; s = s->succ_next)
1392 basic_block d = s->dest;
1394 if (FORWARDER_BLOCK_P (d))
1397 for (s2 = src1->succ; ; s2 = s2->succ_next)
1399 basic_block d2 = s2->dest;
1400 if (FORWARDER_BLOCK_P (d2))
1401 d2 = d2->succ->dest;
1406 s->count += s2->count;
1408 /* Take care to update possible forwarder blocks. We verified
1409 that there is no more than one in the chain, so we can't run
1410 into infinite loop. */
1411 if (FORWARDER_BLOCK_P (s->dest))
1413 s->dest->succ->count += s2->count;
1414 s->dest->count += s2->count;
1415 s->dest->frequency += EDGE_FREQUENCY (s);
1418 if (FORWARDER_BLOCK_P (s2->dest))
1420 s2->dest->succ->count -= s2->count;
1421 if (s2->dest->succ->count < 0)
1422 s2->dest->succ->count = 0;
1423 s2->dest->count -= s2->count;
1424 s2->dest->frequency -= EDGE_FREQUENCY (s);
1425 if (s2->dest->frequency < 0)
1426 s2->dest->frequency = 0;
1427 if (s2->dest->count < 0)
1428 s2->dest->count = 0;
1431 if (!redirect_to->frequency && !src1->frequency)
1432 s->probability = (s->probability + s2->probability) / 2;
1435 = ((s->probability * redirect_to->frequency +
1436 s2->probability * src1->frequency)
1437 / (redirect_to->frequency + src1->frequency));
1440 update_br_prob_note (redirect_to);
1442 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1444 /* Skip possible basic block header. */
1445 if (GET_CODE (newpos1) == CODE_LABEL)
1446 newpos1 = NEXT_INSN (newpos1);
1448 if (GET_CODE (newpos1) == NOTE)
1449 newpos1 = NEXT_INSN (newpos1);
1452 /* Emit the jump insn. */
1453 label = block_label (redirect_to);
1454 emit_jump_insn_after (gen_jump (label), src1->end);
1455 JUMP_LABEL (src1->end) = label;
1456 LABEL_NUSES (label)++;
1458 /* Delete the now unreachable instructions. */
1459 delete_insn_chain (newpos1, last);
1461 /* Make sure there is a barrier after the new jump. */
1462 last = next_nonnote_insn (src1->end);
1463 if (!last || GET_CODE (last) != BARRIER)
1464 emit_barrier_after (src1->end);
1468 remove_edge (src1->succ);
1469 make_single_succ_edge (src1, redirect_to, 0);
1471 update_forwarder_flag (src1);
1476 /* Search the predecessors of BB for common insn sequences. When found,
1477 share code between them by redirecting control flow. Return true if
1478 any changes made. */
1481 try_crossjump_bb (mode, bb)
1485 edge e, e2, nexte2, nexte, fallthru;
1489 /* Nothing to do if there is not at least two incoming edges. */
1490 if (!bb->pred || !bb->pred->pred_next)
1493 /* It is always cheapest to redirect a block that ends in a branch to
1494 a block that falls through into BB, as that adds no branches to the
1495 program. We'll try that combination first. */
1496 for (fallthru = bb->pred; fallthru; fallthru = fallthru->pred_next, n++)
1498 if (fallthru->flags & EDGE_FALLTHRU)
1505 for (e = bb->pred; e; e = nexte)
1507 nexte = e->pred_next;
1509 /* As noted above, first try with the fallthru predecessor. */
1512 /* Don't combine the fallthru edge into anything else.
1513 If there is a match, we'll do it the other way around. */
1517 if (try_crossjump_to_edge (mode, e, fallthru))
1525 /* Non-obvious work limiting check: Recognize that we're going
1526 to call try_crossjump_bb on every basic block. So if we have
1527 two blocks with lots of outgoing edges (a switch) and they
1528 share lots of common destinations, then we would do the
1529 cross-jump check once for each common destination.
1531 Now, if the blocks actually are cross-jump candidates, then
1532 all of their destinations will be shared. Which means that
1533 we only need check them for cross-jump candidacy once. We
1534 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1535 choosing to do the check from the block for which the edge
1536 in question is the first successor of A. */
1537 if (e->src->succ != e)
1540 for (e2 = bb->pred; e2; e2 = nexte2)
1542 nexte2 = e2->pred_next;
1547 /* We've already checked the fallthru edge above. */
1551 /* The "first successor" check above only prevents multiple
1552 checks of crossjump(A,B). In order to prevent redundant
1553 checks of crossjump(B,A), require that A be the block
1554 with the lowest index. */
1555 if (e->src->index > e2->src->index)
1558 if (try_crossjump_to_edge (mode, e, e2))
1570 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1571 instructions etc. Return nonzero if changes were made. */
1574 try_optimize_cfg (mode)
1578 bool changed_overall = false;
1582 if (mode & CLEANUP_CROSSJUMP)
1583 add_noreturn_fake_exit_edges ();
1585 for (i = 0; i < n_basic_blocks; i++)
1586 update_forwarder_flag (BASIC_BLOCK (i));
1588 if (mode & CLEANUP_UPDATE_LIFE)
1591 if (! (* targetm.cannot_modify_jumps_p) ())
1593 /* Attempt to merge blocks as made possible by edge removal. If
1594 a block has only one successor, and the successor has only
1595 one predecessor, they may be combined. */
1602 fprintf (rtl_dump_file,
1603 "\n\ntry_optimize_cfg iteration %i\n\n",
1606 for (i = 0; i < n_basic_blocks;)
1608 basic_block c, b = BASIC_BLOCK (i);
1610 bool changed_here = false;
1612 /* Delete trivially dead basic blocks. */
1613 while (b->pred == NULL)
1615 c = BASIC_BLOCK (b->index - 1);
1617 fprintf (rtl_dump_file, "Deleting block %i.\n",
1620 flow_delete_block (b);
1625 /* Remove code labels no longer used. Don't do this
1626 before CALL_PLACEHOLDER is removed, as some branches
1627 may be hidden within. */
1628 if (b->pred->pred_next == NULL
1629 && (b->pred->flags & EDGE_FALLTHRU)
1630 && !(b->pred->flags & EDGE_COMPLEX)
1631 && GET_CODE (b->head) == CODE_LABEL
1632 && (!(mode & CLEANUP_PRE_SIBCALL)
1633 || !tail_recursion_label_p (b->head))
1634 /* If the previous block ends with a branch to this
1635 block, we can't delete the label. Normally this
1636 is a condjump that is yet to be simplified, but
1637 if CASE_DROPS_THRU, this can be a tablejump with
1638 some element going to the same place as the
1639 default (fallthru). */
1640 && (b->pred->src == ENTRY_BLOCK_PTR
1641 || GET_CODE (b->pred->src->end) != JUMP_INSN
1642 || ! label_is_jump_target_p (b->head,
1643 b->pred->src->end)))
1645 rtx label = b->head;
1647 b->head = NEXT_INSN (b->head);
1648 delete_insn_chain (label, label);
1650 fprintf (rtl_dump_file, "Deleted label in block %i.\n",
1654 /* If we fall through an empty block, we can remove it. */
1655 if (b->pred->pred_next == NULL
1656 && (b->pred->flags & EDGE_FALLTHRU)
1657 && GET_CODE (b->head) != CODE_LABEL
1658 && FORWARDER_BLOCK_P (b)
1659 /* Note that forwarder_block_p true ensures that
1660 there is a successor for this block. */
1661 && (b->succ->flags & EDGE_FALLTHRU)
1662 && n_basic_blocks > 1)
1665 fprintf (rtl_dump_file,
1666 "Deleting fallthru block %i.\n",
1669 c = BASIC_BLOCK (b->index ? b->index - 1 : 1);
1670 redirect_edge_succ_nodup (b->pred, b->succ->dest);
1671 flow_delete_block (b);
1676 /* Merge blocks. Loop because chains of blocks might be
1678 while ((s = b->succ) != NULL
1679 && s->succ_next == NULL
1680 && !(s->flags & EDGE_COMPLEX)
1681 && (c = s->dest) != EXIT_BLOCK_PTR
1682 && c->pred->pred_next == NULL
1683 /* If the jump insn has side effects,
1684 we can't kill the edge. */
1685 && (GET_CODE (b->end) != JUMP_INSN
1686 || simplejump_p (b->end))
1687 && merge_blocks (s, b, c, mode))
1688 changed_here = true;
1690 /* Simplify branch over branch. */
1691 if ((mode & CLEANUP_EXPENSIVE) && try_simplify_condjump (b))
1692 changed_here = true;
1694 /* If B has a single outgoing edge, but uses a
1695 non-trivial jump instruction without side-effects, we
1696 can either delete the jump entirely, or replace it
1697 with a simple unconditional jump. Use
1698 redirect_edge_and_branch to do the dirty work. */
1700 && ! b->succ->succ_next
1701 && b->succ->dest != EXIT_BLOCK_PTR
1702 && onlyjump_p (b->end)
1703 && redirect_edge_and_branch (b->succ, b->succ->dest))
1705 update_forwarder_flag (b);
1706 changed_here = true;
1709 /* Simplify branch to branch. */
1710 if (try_forward_edges (mode, b))
1711 changed_here = true;
1713 /* Look for shared code between blocks. */
1714 if ((mode & CLEANUP_CROSSJUMP)
1715 && try_crossjump_bb (mode, b))
1716 changed_here = true;
1718 /* Don't get confused by the index shift caused by
1726 if ((mode & CLEANUP_CROSSJUMP)
1727 && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
1730 #ifdef ENABLE_CHECKING
1732 verify_flow_info ();
1735 changed_overall |= changed;
1740 if (mode & CLEANUP_CROSSJUMP)
1741 remove_fake_edges ();
1743 clear_aux_for_blocks ();
1745 return changed_overall;
1748 /* Delete all unreachable basic blocks. */
1751 delete_unreachable_blocks ()
1754 bool changed = false;
1756 find_unreachable_blocks ();
1758 /* Delete all unreachable basic blocks. Do compaction concurrently,
1759 as otherwise we can wind up with O(N^2) behaviour here when we
1760 have oodles of dead code. */
1762 for (i = j = 0; i < n_basic_blocks; ++i)
1764 basic_block b = BASIC_BLOCK (i);
1766 if (!(b->flags & BB_REACHABLE))
1768 flow_delete_block_noexpunge (b);
1769 expunge_block_nocompact (b);
1774 BASIC_BLOCK (j) = b;
1779 basic_block_info->num_elements = j;
1782 tidy_fallthru_edges ();
1786 /* Tidy the CFG by deleting unreachable code and whatnot. */
1792 bool changed = false;
1794 timevar_push (TV_CLEANUP_CFG);
1795 if (delete_unreachable_blocks ())
1798 /* We've possibly created trivially dead code. Cleanup it right
1799 now to introduce more oppurtunities for try_optimize_cfg. */
1800 if (!(mode & (CLEANUP_UPDATE_LIFE | CLEANUP_PRE_SIBCALL))
1801 && !reload_completed)
1802 delete_trivially_dead_insns (get_insns(), max_reg_num ());
1804 while (try_optimize_cfg (mode))
1806 delete_unreachable_blocks (), changed = true;
1807 if (mode & CLEANUP_UPDATE_LIFE)
1809 /* Cleaning up CFG introduces more oppurtunities for dead code
1810 removal that in turn may introduce more oppurtunities for
1811 cleaning up the CFG. */
1812 if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
1814 | PROP_SCAN_DEAD_CODE
1815 | PROP_KILL_DEAD_CODE
1819 else if (!(mode & CLEANUP_PRE_SIBCALL) && !reload_completed)
1821 if (!delete_trivially_dead_insns (get_insns(), max_reg_num ()))
1826 delete_dead_jumptables ();
1829 /* Kill the data we won't maintain. */
1830 free_EXPR_LIST_list (&label_value_list);
1831 timevar_pop (TV_CLEANUP_CFG);