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 life info needs to be recomputed for given BB. */
57 /* Set if BB is the forwarder block to avoid too many
58 forwarder_block_p calls. */
59 BB_FORWARDER_BLOCK = 2
62 #define BB_FLAGS(BB) (enum bb_flags) (BB)->aux
63 #define BB_SET_FLAG(BB, FLAG) \
64 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux | (FLAG))
65 #define BB_CLEAR_FLAG(BB, FLAG) \
66 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux & ~(FLAG))
68 #define FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK)
70 static bool try_crossjump_to_edge PARAMS ((int, edge, edge));
71 static bool try_crossjump_bb PARAMS ((int, basic_block));
72 static bool outgoing_edges_match PARAMS ((int,
73 basic_block, basic_block));
74 static int flow_find_cross_jump PARAMS ((int, basic_block, basic_block,
76 static bool insns_match_p PARAMS ((int, rtx, rtx));
78 static bool delete_unreachable_blocks PARAMS ((void));
79 static bool label_is_jump_target_p PARAMS ((rtx, rtx));
80 static bool tail_recursion_label_p PARAMS ((rtx));
81 static void merge_blocks_move_predecessor_nojumps PARAMS ((basic_block,
83 static void merge_blocks_move_successor_nojumps PARAMS ((basic_block,
85 static bool merge_blocks PARAMS ((edge,basic_block,basic_block,
87 static bool try_optimize_cfg PARAMS ((int));
88 static bool try_simplify_condjump PARAMS ((basic_block));
89 static bool try_forward_edges PARAMS ((int, basic_block));
90 static edge thread_jump PARAMS ((int, edge, basic_block));
91 static bool mark_effect PARAMS ((rtx, bitmap));
92 static void notice_new_block PARAMS ((basic_block));
93 static void update_forwarder_flag PARAMS ((basic_block));
95 /* Set flags for newly created block. */
104 BB_SET_FLAG (bb, BB_UPDATE_LIFE);
105 if (forwarder_block_p (bb))
106 BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
109 /* Recompute forwarder flag after block has been modified. */
112 update_forwarder_flag (bb)
115 if (forwarder_block_p (bb))
116 BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
118 BB_CLEAR_FLAG (bb, BB_FORWARDER_BLOCK);
121 /* Simplify a conditional jump around an unconditional jump.
122 Return true if something changed. */
125 try_simplify_condjump (cbranch_block)
126 basic_block cbranch_block;
128 basic_block jump_block, jump_dest_block, cbranch_dest_block;
129 edge cbranch_jump_edge, cbranch_fallthru_edge;
132 /* Verify that there are exactly two successors. */
133 if (!cbranch_block->succ
134 || !cbranch_block->succ->succ_next
135 || cbranch_block->succ->succ_next->succ_next)
138 /* Verify that we've got a normal conditional branch at the end
140 cbranch_insn = cbranch_block->end;
141 if (!any_condjump_p (cbranch_insn))
144 cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
145 cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
147 /* The next block must not have multiple predecessors, must not
148 be the last block in the function, and must contain just the
149 unconditional jump. */
150 jump_block = cbranch_fallthru_edge->dest;
151 if (jump_block->pred->pred_next
152 || jump_block->index == n_basic_blocks - 1
153 || !FORWARDER_BLOCK_P (jump_block))
155 jump_dest_block = jump_block->succ->dest;
157 /* The conditional branch must target the block after the
158 unconditional branch. */
159 cbranch_dest_block = cbranch_jump_edge->dest;
161 if (!can_fallthru (jump_block, cbranch_dest_block))
164 /* Invert the conditional branch. */
165 if (!invert_jump (cbranch_insn, block_label (jump_dest_block), 0))
169 fprintf (rtl_dump_file, "Simplifying condjump %i around jump %i\n",
170 INSN_UID (cbranch_insn), INSN_UID (jump_block->end));
172 /* Success. Update the CFG to match. Note that after this point
173 the edge variable names appear backwards; the redirection is done
174 this way to preserve edge profile data. */
175 cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
177 cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
179 cbranch_jump_edge->flags |= EDGE_FALLTHRU;
180 cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
181 update_br_prob_note (cbranch_block);
183 /* Delete the block with the unconditional jump, and clean up the mess. */
184 flow_delete_block (jump_block);
185 tidy_fallthru_edge (cbranch_jump_edge, cbranch_block, cbranch_dest_block);
190 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
191 on register. Used by jump threading. */
194 mark_effect (exp, nonequal)
200 switch (GET_CODE (exp))
202 /* In case we do clobber the register, mark it as equal, as we know the
203 value is dead so it don't have to match. */
205 if (REG_P (XEXP (exp, 0)))
207 dest = XEXP (exp, 0);
208 regno = REGNO (dest);
209 CLEAR_REGNO_REG_SET (nonequal, regno);
210 if (regno < FIRST_PSEUDO_REGISTER)
212 int n = HARD_REGNO_NREGS (regno, GET_MODE (dest));
214 CLEAR_REGNO_REG_SET (nonequal, regno + n);
220 if (rtx_equal_for_cselib_p (SET_DEST (exp), SET_SRC (exp)))
222 dest = SET_DEST (exp);
227 regno = REGNO (dest);
228 SET_REGNO_REG_SET (nonequal, regno);
229 if (regno < FIRST_PSEUDO_REGISTER)
231 int n = HARD_REGNO_NREGS (regno, GET_MODE (dest));
233 SET_REGNO_REG_SET (nonequal, regno + n);
241 /* Attempt to prove that the basic block B will have no side effects and
242 allways continues in the same edge if reached via E. Return the edge
243 if exist, NULL otherwise. */
246 thread_jump (mode, e, b)
251 rtx set1, set2, cond1, cond2, insn;
252 enum rtx_code code1, code2, reversed_code2;
253 bool reverse1 = false;
258 /* At the moment, we do handle only conditional jumps, but later we may
259 want to extend this code to tablejumps and others. */
260 if (!e->src->succ->succ_next || e->src->succ->succ_next->succ_next)
262 if (!b->succ || !b->succ->succ_next || b->succ->succ_next->succ_next)
265 /* Second branch must end with onlyjump, as we will eliminate the jump. */
266 if (!any_condjump_p (e->src->end) || !any_condjump_p (b->end)
267 || !onlyjump_p (b->end))
270 set1 = pc_set (e->src->end);
271 set2 = pc_set (b->end);
272 if (((e->flags & EDGE_FALLTHRU) != 0)
273 != (XEXP (SET_SRC (set1), 1) == pc_rtx))
276 cond1 = XEXP (SET_SRC (set1), 0);
277 cond2 = XEXP (SET_SRC (set2), 0);
279 code1 = reversed_comparison_code (cond1, e->src->end);
281 code1 = GET_CODE (cond1);
283 code2 = GET_CODE (cond2);
284 reversed_code2 = reversed_comparison_code (cond2, b->end);
286 if (!comparison_dominates_p (code1, code2)
287 && !comparison_dominates_p (code1, reversed_code2))
290 /* Ensure that the comparison operators are equivalent.
291 ??? This is far too pesimistic. We should allow swapped operands,
292 different CCmodes, or for example comparisons for interval, that
293 dominate even when operands are not equivalent. */
294 if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
295 || !rtx_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
298 /* Short circuit cases where block B contains some side effects, as we can't
300 for (insn = NEXT_INSN (b->head); insn != NEXT_INSN (b->end);
301 insn = NEXT_INSN (insn))
302 if (INSN_P (insn) && side_effects_p (PATTERN (insn)))
307 /* First process all values computed in the source basic block. */
308 for (insn = NEXT_INSN (e->src->head); insn != NEXT_INSN (e->src->end);
309 insn = NEXT_INSN (insn))
311 cselib_process_insn (insn);
313 nonequal = BITMAP_XMALLOC();
314 CLEAR_REG_SET (nonequal);
316 /* Now assume that we've continued by the edge E to B and continue
317 processing as if it were same basic block.
318 Our goal is to prove that whole block is an NOOP. */
320 for (insn = NEXT_INSN (b->head); insn != NEXT_INSN (b->end) && !failed;
321 insn = NEXT_INSN (insn))
325 rtx pat = PATTERN (insn);
327 if (GET_CODE (pat) == PARALLEL)
329 for (i = 0; i < XVECLEN (pat, 0); i++)
330 failed |= mark_effect (XVECEXP (pat, 0, i), nonequal);
333 failed |= mark_effect (pat, nonequal);
336 cselib_process_insn (insn);
339 /* Later we should clear nonequal of dead registers. So far we don't
340 have life information in cfg_cleanup. */
344 /* In case liveness information is available, we need to prove equivalence
345 only of the live values. */
346 if (mode & CLEANUP_UPDATE_LIFE)
347 AND_REG_SET (nonequal, b->global_live_at_end);
349 EXECUTE_IF_SET_IN_REG_SET (nonequal, 0, i, goto failed_exit;);
351 BITMAP_XFREE (nonequal);
353 if ((comparison_dominates_p (code1, code2) != 0)
354 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
355 return BRANCH_EDGE (b);
357 return FALLTHRU_EDGE (b);
360 BITMAP_XFREE (nonequal);
365 /* Attempt to forward edges leaving basic block B.
366 Return true if successful. */
369 try_forward_edges (mode, b)
373 bool changed = false;
374 edge e, next, *threaded_edges = NULL;
376 for (e = b->succ; e; e = next)
378 basic_block target, first;
380 bool threaded = false;
381 int nthreaded_edges = 0;
385 /* Skip complex edges because we don't know how to update them.
387 Still handle fallthru edges, as we can succeed to forward fallthru
388 edge to the same place as the branch edge of conditional branch
389 and turn conditional branch to an unconditional branch. */
390 if (e->flags & EDGE_COMPLEX)
393 target = first = e->dest;
396 while (counter < n_basic_blocks)
398 basic_block new_target = NULL;
399 bool new_target_threaded = false;
401 if (FORWARDER_BLOCK_P (target)
402 && target->succ->dest != EXIT_BLOCK_PTR)
404 /* Bypass trivial infinite loops. */
405 if (target == target->succ->dest)
406 counter = n_basic_blocks;
407 new_target = target->succ->dest;
410 /* Allow to thread only over one edge at time to simplify updating
412 else if (mode & CLEANUP_THREADING)
414 edge t = thread_jump (mode, e, target);
418 threaded_edges = xmalloc (sizeof (*threaded_edges)
424 /* Detect an infinite loop across blocks not
425 including the start block. */
426 for (i = 0; i < nthreaded_edges; ++i)
427 if (threaded_edges[i] == t)
429 if (i < nthreaded_edges)
431 counter = n_basic_blocks;
436 /* Detect an infinite loop across the start block. */
440 if (nthreaded_edges >= n_basic_blocks)
442 threaded_edges[nthreaded_edges++] = t;
444 new_target = t->dest;
445 new_target_threaded = true;
452 /* Avoid killing of loop pre-headers, as it is the place loop
453 optimizer wants to hoist code to.
455 For fallthru forwarders, the LOOP_BEG note must appear between
456 the header of block and CODE_LABEL of the loop, for non forwarders
457 it must appear before the JUMP_INSN. */
458 if (mode & CLEANUP_PRE_LOOP)
460 rtx insn = (target->succ->flags & EDGE_FALLTHRU
461 ? target->head : prev_nonnote_insn (target->end));
463 if (GET_CODE (insn) != NOTE)
464 insn = NEXT_INSN (insn);
466 for (; insn && GET_CODE (insn) != CODE_LABEL && !INSN_P (insn);
467 insn = NEXT_INSN (insn))
468 if (GET_CODE (insn) == NOTE
469 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
472 if (GET_CODE (insn) == NOTE)
478 threaded |= new_target_threaded;
481 if (counter >= n_basic_blocks)
484 fprintf (rtl_dump_file, "Infinite loop in BB %i.\n",
487 else if (target == first)
488 ; /* We didn't do anything. */
491 /* Save the values now, as the edge may get removed. */
492 gcov_type edge_count = e->count;
493 int edge_probability = e->probability;
497 /* Don't force if target is exit block. */
498 if (threaded && target != EXIT_BLOCK_PTR)
500 notice_new_block (redirect_edge_and_branch_force (e, target));
502 fprintf (rtl_dump_file, "Conditionals threaded.\n");
504 else if (!redirect_edge_and_branch (e, target))
507 fprintf (rtl_dump_file,
508 "Forwarding edge %i->%i to %i failed.\n",
509 b->index, e->dest->index, target->index);
513 /* We successfully forwarded the edge. Now update profile
514 data: for each edge we traversed in the chain, remove
515 the original edge's execution count. */
516 edge_frequency = ((edge_probability * b->frequency
517 + REG_BR_PROB_BASE / 2)
520 if (!FORWARDER_BLOCK_P (b) && forwarder_block_p (b))
521 BB_SET_FLAG (b, BB_FORWARDER_BLOCK);
522 BB_SET_FLAG (b, BB_UPDATE_LIFE);
528 first->count -= edge_count;
529 if (first->count < 0)
531 first->frequency -= edge_frequency;
532 if (first->frequency < 0)
533 first->frequency = 0;
534 if (first->succ->succ_next)
538 if (n >= nthreaded_edges)
540 t = threaded_edges [n++];
543 if (first->frequency)
544 prob = edge_frequency * REG_BR_PROB_BASE / first->frequency;
547 if (prob > t->probability)
548 prob = t->probability;
549 t->probability -= prob;
550 prob = REG_BR_PROB_BASE - prob;
553 first->succ->probability = REG_BR_PROB_BASE;
554 first->succ->succ_next->probability = 0;
557 for (e = first->succ; e; e = e->succ_next)
558 e->probability = ((e->probability * REG_BR_PROB_BASE)
560 update_br_prob_note (first);
564 /* It is possible that as the result of
565 threading we've removed edge as it is
566 threaded to the fallthru edge. Avoid
567 getting out of sync. */
568 if (n < nthreaded_edges
569 && first == threaded_edges [n]->src)
574 t->count -= edge_count;
579 while (first != target);
586 free (threaded_edges);
590 /* Return true if LABEL is a target of JUMP_INSN. This applies only
591 to non-complex jumps. That is, direct unconditional, conditional,
592 and tablejumps, but not computed jumps or returns. It also does
593 not apply to the fallthru case of a conditional jump. */
596 label_is_jump_target_p (label, jump_insn)
597 rtx label, jump_insn;
599 rtx tmp = JUMP_LABEL (jump_insn);
605 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
606 && GET_CODE (tmp) == JUMP_INSN
607 && (tmp = PATTERN (tmp),
608 GET_CODE (tmp) == ADDR_VEC
609 || GET_CODE (tmp) == ADDR_DIFF_VEC))
611 rtvec vec = XVEC (tmp, GET_CODE (tmp) == ADDR_DIFF_VEC);
612 int i, veclen = GET_NUM_ELEM (vec);
614 for (i = 0; i < veclen; ++i)
615 if (XEXP (RTVEC_ELT (vec, i), 0) == label)
622 /* Return true if LABEL is used for tail recursion. */
625 tail_recursion_label_p (label)
630 for (x = tail_recursion_label_list; x; x = XEXP (x, 1))
631 if (label == XEXP (x, 0))
637 /* Blocks A and B are to be merged into a single block. A has no incoming
638 fallthru edge, so it can be moved before B without adding or modifying
639 any jumps (aside from the jump from A to B). */
642 merge_blocks_move_predecessor_nojumps (a, b)
648 barrier = next_nonnote_insn (a->end);
649 if (GET_CODE (barrier) != BARRIER)
651 delete_insn (barrier);
653 /* Move block and loop notes out of the chain so that we do not
656 ??? A better solution would be to squeeze out all the non-nested notes
657 and adjust the block trees appropriately. Even better would be to have
658 a tighter connection between block trees and rtl so that this is not
660 if (squeeze_notes (&a->head, &a->end))
663 /* Scramble the insn chain. */
664 if (a->end != PREV_INSN (b->head))
665 reorder_insns_nobb (a->head, a->end, PREV_INSN (b->head));
666 BB_SET_FLAG (a, BB_UPDATE_LIFE);
669 fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
672 /* Swap the records for the two blocks around. Although we are deleting B,
673 A is now where B was and we want to compact the BB array from where
675 BASIC_BLOCK (a->index) = b;
676 BASIC_BLOCK (b->index) = a;
681 /* Now blocks A and B are contiguous. Merge them. */
682 merge_blocks_nomove (a, b);
685 /* Blocks A and B are to be merged into a single block. B has no outgoing
686 fallthru edge, so it can be moved after A without adding or modifying
687 any jumps (aside from the jump from A to B). */
690 merge_blocks_move_successor_nojumps (a, b)
693 rtx barrier, real_b_end;
696 barrier = NEXT_INSN (b->end);
698 /* Recognize a jump table following block B. */
700 && GET_CODE (barrier) == CODE_LABEL
701 && NEXT_INSN (barrier)
702 && GET_CODE (NEXT_INSN (barrier)) == JUMP_INSN
703 && (GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_VEC
704 || GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_DIFF_VEC))
706 /* Temporarily add the table jump insn to b, so that it will also
707 be moved to the correct location. */
708 b->end = NEXT_INSN (barrier);
709 barrier = NEXT_INSN (b->end);
712 /* There had better have been a barrier there. Delete it. */
713 if (barrier && GET_CODE (barrier) == BARRIER)
714 delete_insn (barrier);
716 /* Move block and loop notes out of the chain so that we do not
719 ??? A better solution would be to squeeze out all the non-nested notes
720 and adjust the block trees appropriately. Even better would be to have
721 a tighter connection between block trees and rtl so that this is not
723 if (squeeze_notes (&b->head, &b->end))
726 /* Scramble the insn chain. */
727 reorder_insns_nobb (b->head, b->end, a->end);
729 /* Restore the real end of b. */
732 /* Now blocks A and B are contiguous. Merge them. */
733 merge_blocks_nomove (a, b);
734 BB_SET_FLAG (a, BB_UPDATE_LIFE);
737 fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
741 /* Attempt to merge basic blocks that are potentially non-adjacent.
742 Return true iff the attempt succeeded. */
745 merge_blocks (e, b, c, mode)
750 /* If C has a tail recursion label, do not merge. There is no
751 edge recorded from the call_placeholder back to this label, as
752 that would make optimize_sibling_and_tail_recursive_calls more
753 complex for no gain. */
754 if ((mode & CLEANUP_PRE_SIBCALL)
755 && GET_CODE (c->head) == CODE_LABEL
756 && tail_recursion_label_p (c->head))
759 /* If B has a fallthru edge to C, no need to move anything. */
760 if (e->flags & EDGE_FALLTHRU)
762 int b_index = b->index, c_index = c->index;
763 /* We need to update liveness in case C already has broken liveness
764 or B ends by conditional jump to next instructions that will be
766 if ((BB_FLAGS (c) & BB_UPDATE_LIFE)
767 || GET_CODE (b->end) == JUMP_INSN)
768 BB_SET_FLAG (b, BB_UPDATE_LIFE);
769 merge_blocks_nomove (b, c);
770 update_forwarder_flag (b);
773 fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
779 /* Otherwise we will need to move code around. Do that only if expensive
780 transformations are allowed. */
781 else if (mode & CLEANUP_EXPENSIVE)
783 edge tmp_edge, b_fallthru_edge;
784 bool c_has_outgoing_fallthru;
785 bool b_has_incoming_fallthru;
787 /* Avoid overactive code motion, as the forwarder blocks should be
788 eliminated by edge redirection instead. One exception might have
789 been if B is a forwarder block and C has no fallthru edge, but
790 that should be cleaned up by bb-reorder instead. */
791 if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
794 /* We must make sure to not munge nesting of lexical blocks,
795 and loop notes. This is done by squeezing out all the notes
796 and leaving them there to lie. Not ideal, but functional. */
798 for (tmp_edge = c->succ; tmp_edge; tmp_edge = tmp_edge->succ_next)
799 if (tmp_edge->flags & EDGE_FALLTHRU)
802 c_has_outgoing_fallthru = (tmp_edge != NULL);
804 for (tmp_edge = b->pred; tmp_edge; tmp_edge = tmp_edge->pred_next)
805 if (tmp_edge->flags & EDGE_FALLTHRU)
808 b_has_incoming_fallthru = (tmp_edge != NULL);
809 b_fallthru_edge = tmp_edge;
811 /* Otherwise, we're going to try to move C after B. If C does
812 not have an outgoing fallthru, then it can be moved
813 immediately after B without introducing or modifying jumps. */
814 if (! c_has_outgoing_fallthru)
816 merge_blocks_move_successor_nojumps (b, c);
820 /* If B does not have an incoming fallthru, then it can be moved
821 immediately before C without introducing or modifying jumps.
822 C cannot be the first block, so we do not have to worry about
823 accessing a non-existent block. */
825 if (b_has_incoming_fallthru)
829 if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
831 bb = force_nonfallthru (b_fallthru_edge);
833 notice_new_block (bb);
835 BB_SET_FLAG (b_fallthru_edge->src, BB_UPDATE_LIFE);
838 merge_blocks_move_predecessor_nojumps (b, c);
846 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
849 insns_match_p (mode, i1, i2)
850 int mode ATTRIBUTE_UNUSED;
855 /* Verify that I1 and I2 are equivalent. */
856 if (GET_CODE (i1) != GET_CODE (i2))
862 if (GET_CODE (p1) != GET_CODE (p2))
865 /* If this is a CALL_INSN, compare register usage information.
866 If we don't check this on stack register machines, the two
867 CALL_INSNs might be merged leaving reg-stack.c with mismatching
868 numbers of stack registers in the same basic block.
869 If we don't check this on machines with delay slots, a delay slot may
870 be filled that clobbers a parameter expected by the subroutine.
872 ??? We take the simple route for now and assume that if they're
873 equal, they were constructed identically. */
875 if (GET_CODE (i1) == CALL_INSN
876 && !rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
877 CALL_INSN_FUNCTION_USAGE (i2)))
881 /* If cross_jump_death_matters is not 0, the insn's mode
882 indicates whether or not the insn contains any stack-like
885 if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
887 /* If register stack conversion has already been done, then
888 death notes must also be compared before it is certain that
889 the two instruction streams match. */
892 HARD_REG_SET i1_regset, i2_regset;
894 CLEAR_HARD_REG_SET (i1_regset);
895 CLEAR_HARD_REG_SET (i2_regset);
897 for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
898 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
899 SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
901 for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
902 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
903 SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
905 GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
915 ? ! rtx_renumbered_equal_p (p1, p2) : ! rtx_equal_p (p1, p2))
917 /* The following code helps take care of G++ cleanups. */
918 rtx equiv1 = find_reg_equal_equiv_note (i1);
919 rtx equiv2 = find_reg_equal_equiv_note (i2);
922 /* If the equivalences are not to a constant, they may
923 reference pseudos that no longer exist, so we can't
925 && (! reload_completed
926 || (CONSTANT_P (XEXP (equiv1, 0))
927 && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
929 rtx s1 = single_set (i1);
930 rtx s2 = single_set (i2);
931 if (s1 != 0 && s2 != 0
932 && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
934 validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
935 validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
936 if (! rtx_renumbered_equal_p (p1, p2))
938 else if (apply_change_group ())
949 /* Look through the insns at the end of BB1 and BB2 and find the longest
950 sequence that are equivalent. Store the first insns for that sequence
951 in *F1 and *F2 and return the sequence length.
953 To simplify callers of this function, if the blocks match exactly,
954 store the head of the blocks in *F1 and *F2. */
957 flow_find_cross_jump (mode, bb1, bb2, f1, f2)
958 int mode ATTRIBUTE_UNUSED;
959 basic_block bb1, bb2;
962 rtx i1, i2, last1, last2, afterlast1, afterlast2;
965 /* Skip simple jumps at the end of the blocks. Complex jumps still
966 need to be compared for equivalence, which we'll do below. */
969 last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
971 || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
979 || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
982 /* Count everything except for unconditional jump as insn. */
983 if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
991 while (!active_insn_p (i1) && i1 != bb1->head)
994 while (!active_insn_p (i2) && i2 != bb2->head)
997 if (i1 == bb1->head || i2 == bb2->head)
1000 if (!insns_match_p (mode, i1, i2))
1003 /* Don't begin a cross-jump with a USE or CLOBBER insn. */
1004 if (active_insn_p (i1))
1006 /* If the merged insns have different REG_EQUAL notes, then
1008 rtx equiv1 = find_reg_equal_equiv_note (i1);
1009 rtx equiv2 = find_reg_equal_equiv_note (i2);
1011 if (equiv1 && !equiv2)
1012 remove_note (i1, equiv1);
1013 else if (!equiv1 && equiv2)
1014 remove_note (i2, equiv2);
1015 else if (equiv1 && equiv2
1016 && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
1018 remove_note (i1, equiv1);
1019 remove_note (i2, equiv2);
1022 afterlast1 = last1, afterlast2 = last2;
1023 last1 = i1, last2 = i2;
1027 i1 = PREV_INSN (i1);
1028 i2 = PREV_INSN (i2);
1032 /* Don't allow the insn after a compare to be shared by
1033 cross-jumping unless the compare is also shared. */
1034 if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
1035 last1 = afterlast1, last2 = afterlast2, ninsns--;
1038 /* Include preceding notes and labels in the cross-jump. One,
1039 this may bring us to the head of the blocks as requested above.
1040 Two, it keeps line number notes as matched as may be. */
1043 while (last1 != bb1->head && !active_insn_p (PREV_INSN (last1)))
1044 last1 = PREV_INSN (last1);
1046 if (last1 != bb1->head && GET_CODE (PREV_INSN (last1)) == CODE_LABEL)
1047 last1 = PREV_INSN (last1);
1049 while (last2 != bb2->head && !active_insn_p (PREV_INSN (last2)))
1050 last2 = PREV_INSN (last2);
1052 if (last2 != bb2->head && GET_CODE (PREV_INSN (last2)) == CODE_LABEL)
1053 last2 = PREV_INSN (last2);
1062 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1063 the branch instruction. This means that if we commonize the control
1064 flow before end of the basic block, the semantic remains unchanged.
1066 We may assume that there exists one edge with a common destination. */
1069 outgoing_edges_match (mode, bb1, bb2)
1074 int nehedges1 = 0, nehedges2 = 0;
1075 edge fallthru1 = 0, fallthru2 = 0;
1078 /* If BB1 has only one successor, we may be looking at either an
1079 unconditional jump, or a fake edge to exit. */
1080 if (bb1->succ && !bb1->succ->succ_next
1081 && !(bb1->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)))
1082 return (bb2->succ && !bb2->succ->succ_next
1083 && (bb2->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0);
1085 /* Match conditional jumps - this may get tricky when fallthru and branch
1086 edges are crossed. */
1088 && bb1->succ->succ_next
1089 && !bb1->succ->succ_next->succ_next
1090 && any_condjump_p (bb1->end)
1091 && onlyjump_p (bb1->end))
1093 edge b1, f1, b2, f2;
1094 bool reverse, match;
1095 rtx set1, set2, cond1, cond2;
1096 enum rtx_code code1, code2;
1099 || !bb2->succ->succ_next
1100 || bb2->succ->succ_next->succ_next
1101 || !any_condjump_p (bb2->end)
1102 || !onlyjump_p (bb2->end))
1105 /* Do not crossjump across loop boundaries. This is a temporary
1106 workaround for the common scenario in which crossjumping results
1107 in killing the duplicated loop condition, making bb-reorder rotate
1108 the loop incorectly, leaving an extra unconditional jump inside
1111 This check should go away once bb-reorder knows how to duplicate
1112 code in this case or rotate the loops to avoid this scenario. */
1113 if (bb1->loop_depth != bb2->loop_depth)
1116 b1 = BRANCH_EDGE (bb1);
1117 b2 = BRANCH_EDGE (bb2);
1118 f1 = FALLTHRU_EDGE (bb1);
1119 f2 = FALLTHRU_EDGE (bb2);
1121 /* Get around possible forwarders on fallthru edges. Other cases
1122 should be optimized out already. */
1123 if (FORWARDER_BLOCK_P (f1->dest))
1124 f1 = f1->dest->succ;
1126 if (FORWARDER_BLOCK_P (f2->dest))
1127 f2 = f2->dest->succ;
1129 /* To simplify use of this function, return false if there are
1130 unneeded forwarder blocks. These will get eliminated later
1131 during cleanup_cfg. */
1132 if (FORWARDER_BLOCK_P (f1->dest)
1133 || FORWARDER_BLOCK_P (f2->dest)
1134 || FORWARDER_BLOCK_P (b1->dest)
1135 || FORWARDER_BLOCK_P (b2->dest))
1138 if (f1->dest == f2->dest && b1->dest == b2->dest)
1140 else if (f1->dest == b2->dest && b1->dest == f2->dest)
1145 set1 = pc_set (bb1->end);
1146 set2 = pc_set (bb2->end);
1147 if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
1148 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
1151 cond1 = XEXP (SET_SRC (set1), 0);
1152 cond2 = XEXP (SET_SRC (set2), 0);
1153 code1 = GET_CODE (cond1);
1155 code2 = reversed_comparison_code (cond2, bb2->end);
1157 code2 = GET_CODE (cond2);
1159 if (code2 == UNKNOWN)
1162 /* Verify codes and operands match. */
1163 match = ((code1 == code2
1164 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
1165 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
1166 || (code1 == swap_condition (code2)
1167 && rtx_renumbered_equal_p (XEXP (cond1, 1),
1169 && rtx_renumbered_equal_p (XEXP (cond1, 0),
1172 /* If we return true, we will join the blocks. Which means that
1173 we will only have one branch prediction bit to work with. Thus
1174 we require the existing branches to have probabilities that are
1178 && bb1->frequency > BB_FREQ_MAX / 1000
1179 && bb2->frequency > BB_FREQ_MAX / 1000)
1183 if (b1->dest == b2->dest)
1184 prob2 = b2->probability;
1186 /* Do not use f2 probability as f2 may be forwarded. */
1187 prob2 = REG_BR_PROB_BASE - b2->probability;
1189 /* Fail if the difference in probabilities is greater than 50%.
1190 This rules out two well-predicted branches with opposite
1192 if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
1195 fprintf (rtl_dump_file,
1196 "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
1197 bb1->index, bb2->index, b1->probability, prob2);
1203 if (rtl_dump_file && match)
1204 fprintf (rtl_dump_file, "Conditionals in bb %i and %i match.\n",
1205 bb1->index, bb2->index);
1210 /* Generic case - we are seeing an computed jump, table jump or trapping
1213 /* First ensure that the instructions match. There may be many outgoing
1214 edges so this test is generally cheaper.
1215 ??? Currently the tablejumps will never match, as they do have
1216 different tables. */
1217 if (!insns_match_p (mode, bb1->end, bb2->end))
1220 /* Search the outgoing edges, ensure that the counts do match, find possible
1221 fallthru and exception handling edges since these needs more
1223 for (e1 = bb1->succ, e2 = bb2->succ; e1 && e2;
1224 e1 = e1->succ_next, e2 = e2->succ_next)
1226 if (e1->flags & EDGE_EH)
1229 if (e2->flags & EDGE_EH)
1232 if (e1->flags & EDGE_FALLTHRU)
1234 if (e2->flags & EDGE_FALLTHRU)
1238 /* If number of edges of various types does not match, fail. */
1240 || nehedges1 != nehedges2
1241 || (fallthru1 != 0) != (fallthru2 != 0))
1244 /* fallthru edges must be forwarded to the same destination. */
1247 basic_block d1 = (forwarder_block_p (fallthru1->dest)
1248 ? fallthru1->dest->succ->dest: fallthru1->dest);
1249 basic_block d2 = (forwarder_block_p (fallthru2->dest)
1250 ? fallthru2->dest->succ->dest: fallthru2->dest);
1256 /* In case we do have EH edges, ensure we are in the same region. */
1259 rtx n1 = find_reg_note (bb1->end, REG_EH_REGION, 0);
1260 rtx n2 = find_reg_note (bb2->end, REG_EH_REGION, 0);
1262 if (XEXP (n1, 0) != XEXP (n2, 0))
1266 /* We don't need to match the rest of edges as above checks should be enought
1267 to ensure that they are equivalent. */
1271 /* E1 and E2 are edges with the same destination block. Search their
1272 predecessors for common code. If found, redirect control flow from
1273 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1276 try_crossjump_to_edge (mode, e1, e2)
1281 basic_block src1 = e1->src, src2 = e2->src;
1282 basic_block redirect_to;
1283 rtx newpos1, newpos2;
1288 /* Search backward through forwarder blocks. We don't need to worry
1289 about multiple entry or chained forwarders, as they will be optimized
1290 away. We do this to look past the unconditional jump following a
1291 conditional jump that is required due to the current CFG shape. */
1293 && FORWARDER_BLOCK_P (src1))
1294 e1 = src1->pred, src1 = e1->src;
1297 && FORWARDER_BLOCK_P (src2))
1298 e2 = src2->pred, src2 = e2->src;
1300 /* Nothing to do if we reach ENTRY, or a common source block. */
1301 if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
1306 /* Seeing more than 1 forwarder blocks would confuse us later... */
1307 if (FORWARDER_BLOCK_P (e1->dest)
1308 && FORWARDER_BLOCK_P (e1->dest->succ->dest))
1311 if (FORWARDER_BLOCK_P (e2->dest)
1312 && FORWARDER_BLOCK_P (e2->dest->succ->dest))
1315 /* Likewise with dead code (possibly newly created by the other optimizations
1317 if (!src1->pred || !src2->pred)
1320 /* Look for the common insn sequence, part the first ... */
1321 if (!outgoing_edges_match (mode, src1, src2))
1324 /* ... and part the second. */
1325 nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
1329 /* Avoid splitting if possible. */
1330 if (newpos2 == src2->head)
1335 fprintf (rtl_dump_file, "Splitting bb %i before %i insns\n",
1336 src2->index, nmatch);
1337 redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
1341 fprintf (rtl_dump_file,
1342 "Cross jumping from bb %i to bb %i; %i common insns\n",
1343 src1->index, src2->index, nmatch);
1345 redirect_to->count += src1->count;
1346 redirect_to->frequency += src1->frequency;
1348 /* Recompute the frequencies and counts of outgoing edges. */
1349 for (s = redirect_to->succ; s; s = s->succ_next)
1352 basic_block d = s->dest;
1354 if (FORWARDER_BLOCK_P (d))
1357 for (s2 = src1->succ; ; s2 = s2->succ_next)
1359 basic_block d2 = s2->dest;
1360 if (FORWARDER_BLOCK_P (d2))
1361 d2 = d2->succ->dest;
1366 s->count += s2->count;
1368 /* Take care to update possible forwarder blocks. We verified
1369 that there is no more than one in the chain, so we can't run
1370 into infinite loop. */
1371 if (FORWARDER_BLOCK_P (s->dest))
1373 s->dest->succ->count += s2->count;
1374 s->dest->count += s2->count;
1375 s->dest->frequency += EDGE_FREQUENCY (s);
1378 if (FORWARDER_BLOCK_P (s2->dest))
1380 s2->dest->succ->count -= s2->count;
1381 if (s2->dest->succ->count < 0)
1382 s2->dest->succ->count = 0;
1383 s2->dest->count -= s2->count;
1384 s2->dest->frequency -= EDGE_FREQUENCY (s);
1385 if (s2->dest->frequency < 0)
1386 s2->dest->frequency = 0;
1387 if (s2->dest->count < 0)
1388 s2->dest->count = 0;
1391 if (!redirect_to->frequency && !src1->frequency)
1392 s->probability = (s->probability + s2->probability) / 2;
1395 = ((s->probability * redirect_to->frequency +
1396 s2->probability * src1->frequency)
1397 / (redirect_to->frequency + src1->frequency));
1400 update_br_prob_note (redirect_to);
1402 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1404 /* Skip possible basic block header. */
1405 if (GET_CODE (newpos1) == CODE_LABEL)
1406 newpos1 = NEXT_INSN (newpos1);
1408 if (GET_CODE (newpos1) == NOTE)
1409 newpos1 = NEXT_INSN (newpos1);
1412 /* Emit the jump insn. */
1413 label = block_label (redirect_to);
1414 emit_jump_insn_after (gen_jump (label), src1->end);
1415 JUMP_LABEL (src1->end) = label;
1416 LABEL_NUSES (label)++;
1418 /* Delete the now unreachable instructions. */
1419 delete_insn_chain (newpos1, last);
1421 /* Make sure there is a barrier after the new jump. */
1422 last = next_nonnote_insn (src1->end);
1423 if (!last || GET_CODE (last) != BARRIER)
1424 emit_barrier_after (src1->end);
1428 remove_edge (src1->succ);
1429 make_single_succ_edge (src1, redirect_to, 0);
1431 BB_SET_FLAG (src1, BB_UPDATE_LIFE);
1432 update_forwarder_flag (src1);
1437 /* Search the predecessors of BB for common insn sequences. When found,
1438 share code between them by redirecting control flow. Return true if
1439 any changes made. */
1442 try_crossjump_bb (mode, bb)
1446 edge e, e2, nexte2, nexte, fallthru;
1449 /* Nothing to do if there is not at least two incoming edges. */
1450 if (!bb->pred || !bb->pred->pred_next)
1453 /* It is always cheapest to redirect a block that ends in a branch to
1454 a block that falls through into BB, as that adds no branches to the
1455 program. We'll try that combination first. */
1456 for (fallthru = bb->pred; fallthru; fallthru = fallthru->pred_next)
1457 if (fallthru->flags & EDGE_FALLTHRU)
1461 for (e = bb->pred; e; e = nexte)
1463 nexte = e->pred_next;
1465 /* As noted above, first try with the fallthru predecessor. */
1468 /* Don't combine the fallthru edge into anything else.
1469 If there is a match, we'll do it the other way around. */
1473 if (try_crossjump_to_edge (mode, e, fallthru))
1481 /* Non-obvious work limiting check: Recognize that we're going
1482 to call try_crossjump_bb on every basic block. So if we have
1483 two blocks with lots of outgoing edges (a switch) and they
1484 share lots of common destinations, then we would do the
1485 cross-jump check once for each common destination.
1487 Now, if the blocks actually are cross-jump candidates, then
1488 all of their destinations will be shared. Which means that
1489 we only need check them for cross-jump candidacy once. We
1490 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1491 choosing to do the check from the block for which the edge
1492 in question is the first successor of A. */
1493 if (e->src->succ != e)
1496 for (e2 = bb->pred; e2; e2 = nexte2)
1498 nexte2 = e2->pred_next;
1503 /* We've already checked the fallthru edge above. */
1507 /* The "first successor" check above only prevents multiple
1508 checks of crossjump(A,B). In order to prevent redundant
1509 checks of crossjump(B,A), require that A be the block
1510 with the lowest index. */
1511 if (e->src->index > e2->src->index)
1514 if (try_crossjump_to_edge (mode, e, e2))
1526 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1527 instructions etc. Return nonzero if changes were made. */
1530 try_optimize_cfg (mode)
1534 bool changed_overall = false;
1539 if (mode & CLEANUP_CROSSJUMP)
1540 add_noreturn_fake_exit_edges ();
1542 for (i = 0; i < n_basic_blocks; i++)
1543 update_forwarder_flag (BASIC_BLOCK (i));
1545 if (! (* targetm.cannot_modify_jumps_p) ())
1547 /* Attempt to merge blocks as made possible by edge removal. If
1548 a block has only one successor, and the successor has only
1549 one predecessor, they may be combined. */
1556 fprintf (rtl_dump_file,
1557 "\n\ntry_optimize_cfg iteration %i\n\n",
1560 for (i = 0; i < n_basic_blocks;)
1562 basic_block c, b = BASIC_BLOCK (i);
1564 bool changed_here = false;
1566 /* Delete trivially dead basic blocks. */
1567 while (b->pred == NULL)
1569 c = BASIC_BLOCK (b->index - 1);
1571 fprintf (rtl_dump_file, "Deleting block %i.\n",
1574 flow_delete_block (b);
1579 /* Remove code labels no longer used. Don't do this
1580 before CALL_PLACEHOLDER is removed, as some branches
1581 may be hidden within. */
1582 if (b->pred->pred_next == NULL
1583 && (b->pred->flags & EDGE_FALLTHRU)
1584 && !(b->pred->flags & EDGE_COMPLEX)
1585 && GET_CODE (b->head) == CODE_LABEL
1586 && (!(mode & CLEANUP_PRE_SIBCALL)
1587 || !tail_recursion_label_p (b->head))
1588 /* If the previous block ends with a branch to this
1589 block, we can't delete the label. Normally this
1590 is a condjump that is yet to be simplified, but
1591 if CASE_DROPS_THRU, this can be a tablejump with
1592 some element going to the same place as the
1593 default (fallthru). */
1594 && (b->pred->src == ENTRY_BLOCK_PTR
1595 || GET_CODE (b->pred->src->end) != JUMP_INSN
1596 || ! label_is_jump_target_p (b->head,
1597 b->pred->src->end)))
1599 rtx label = b->head;
1601 b->head = NEXT_INSN (b->head);
1602 delete_insn_chain (label, label);
1604 fprintf (rtl_dump_file, "Deleted label in block %i.\n",
1608 /* If we fall through an empty block, we can remove it. */
1609 if (b->pred->pred_next == NULL
1610 && (b->pred->flags & EDGE_FALLTHRU)
1611 && GET_CODE (b->head) != CODE_LABEL
1612 && FORWARDER_BLOCK_P (b)
1613 /* Note that forwarder_block_p true ensures that
1614 there is a successor for this block. */
1615 && (b->succ->flags & EDGE_FALLTHRU)
1616 && n_basic_blocks > 1)
1619 fprintf (rtl_dump_file,
1620 "Deleting fallthru block %i.\n",
1623 c = BASIC_BLOCK (b->index ? b->index - 1 : 1);
1624 redirect_edge_succ_nodup (b->pred, b->succ->dest);
1625 flow_delete_block (b);
1630 /* Merge blocks. Loop because chains of blocks might be
1632 while ((s = b->succ) != NULL
1633 && s->succ_next == NULL
1634 && !(s->flags & EDGE_COMPLEX)
1635 && (c = s->dest) != EXIT_BLOCK_PTR
1636 && c->pred->pred_next == NULL
1638 /* If the jump insn has side effects,
1639 we can't kill the edge. */
1640 && (GET_CODE (b->end) != JUMP_INSN
1641 || onlyjump_p (b->end))
1642 && merge_blocks (s, b, c, mode))
1643 changed_here = true;
1645 /* Simplify branch over branch. */
1646 if ((mode & CLEANUP_EXPENSIVE) && try_simplify_condjump (b))
1648 BB_SET_FLAG (b, BB_UPDATE_LIFE);
1649 changed_here = true;
1652 /* If B has a single outgoing edge, but uses a
1653 non-trivial jump instruction without side-effects, we
1654 can either delete the jump entirely, or replace it
1655 with a simple unconditional jump. Use
1656 redirect_edge_and_branch to do the dirty work. */
1658 && ! b->succ->succ_next
1659 && b->succ->dest != EXIT_BLOCK_PTR
1660 && onlyjump_p (b->end)
1661 && redirect_edge_and_branch (b->succ, b->succ->dest))
1663 BB_SET_FLAG (b, BB_UPDATE_LIFE);
1664 update_forwarder_flag (b);
1665 changed_here = true;
1668 /* Simplify branch to branch. */
1669 if (try_forward_edges (mode, b))
1670 changed_here = true;
1672 /* Look for shared code between blocks. */
1673 if ((mode & CLEANUP_CROSSJUMP)
1674 && try_crossjump_bb (mode, b))
1675 changed_here = true;
1677 /* Don't get confused by the index shift caused by
1685 if ((mode & CLEANUP_CROSSJUMP)
1686 && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
1689 #ifdef ENABLE_CHECKING
1691 verify_flow_info ();
1694 changed_overall |= changed;
1699 if (mode & CLEANUP_CROSSJUMP)
1700 remove_fake_edges ();
1702 if ((mode & CLEANUP_UPDATE_LIFE) && changed_overall)
1706 blocks = sbitmap_alloc (n_basic_blocks);
1707 sbitmap_zero (blocks);
1708 for (i = 0; i < n_basic_blocks; i++)
1709 if (BB_FLAGS (BASIC_BLOCK (i)) & BB_UPDATE_LIFE)
1712 SET_BIT (blocks, i);
1716 update_life_info (blocks, UPDATE_LIFE_GLOBAL,
1717 PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
1718 | PROP_KILL_DEAD_CODE);
1719 sbitmap_free (blocks);
1722 for (i = 0; i < n_basic_blocks; i++)
1723 BASIC_BLOCK (i)->aux = NULL;
1725 return changed_overall;
1728 /* Delete all unreachable basic blocks. */
1731 delete_unreachable_blocks ()
1734 bool changed = false;
1736 find_unreachable_blocks ();
1738 /* Delete all unreachable basic blocks. Do compaction concurrently,
1739 as otherwise we can wind up with O(N^2) behaviour here when we
1740 have oodles of dead code. */
1742 for (i = j = 0; i < n_basic_blocks; ++i)
1744 basic_block b = BASIC_BLOCK (i);
1746 if (!(b->flags & BB_REACHABLE))
1748 flow_delete_block_noexpunge (b);
1749 expunge_block_nocompact (b);
1754 BASIC_BLOCK (j) = b;
1759 basic_block_info->num_elements = j;
1762 tidy_fallthru_edges ();
1766 /* Tidy the CFG by deleting unreachable code and whatnot. */
1772 bool changed = false;
1774 timevar_push (TV_CLEANUP_CFG);
1775 changed = delete_unreachable_blocks ();
1776 if (try_optimize_cfg (mode))
1777 delete_unreachable_blocks (), changed = true;
1779 /* Kill the data we won't maintain. */
1780 free_EXPR_LIST_list (&label_value_list);
1781 free_EXPR_LIST_list (&tail_recursion_label_list);
1782 timevar_pop (TV_CLEANUP_CFG);