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 entry point is
23 cleanup_cfg. Following optimizations are performed:
25 - Unreachable blocks removal
26 - Edge forwarding (edge to the forwarder block is forwarded to its
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 #include "cfglayout.h"
55 /* cleanup_cfg maintains following flags for each basic block. */
59 /* Set if BB is the forwarder block to avoid too many
60 forwarder_block_p calls. */
61 BB_FORWARDER_BLOCK = 1,
62 BB_NONTHREADABLE_BLOCK = 2
65 #define BB_FLAGS(BB) (enum bb_flags) (BB)->aux
66 #define BB_SET_FLAG(BB, FLAG) \
67 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux | (FLAG))
68 #define BB_CLEAR_FLAG(BB, FLAG) \
69 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux & ~(FLAG))
71 #define FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK)
73 /* Set to true when we are running first pass of try_optimize_cfg loop. */
74 static bool first_pass;
75 static bool try_crossjump_to_edge (int, edge, edge);
76 static bool try_crossjump_bb (int, basic_block);
77 static bool outgoing_edges_match (int, basic_block, basic_block);
78 static int flow_find_cross_jump (int, basic_block, basic_block, rtx *, rtx *);
79 static bool insns_match_p (int, rtx, rtx);
81 static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
82 static void merge_blocks_move_successor_nojumps (basic_block, basic_block);
83 static bool try_optimize_cfg (int);
84 static bool try_simplify_condjump (basic_block);
85 static bool try_forward_edges (int, basic_block);
86 static edge thread_jump (int, edge, basic_block);
87 static bool mark_effect (rtx, bitmap);
88 static void notice_new_block (basic_block);
89 static void update_forwarder_flag (basic_block);
90 static int mentions_nonequal_regs (rtx *, void *);
91 static void merge_memattrs (rtx, rtx);
93 /* Set flags for newly created block. */
96 notice_new_block (basic_block bb)
101 if (forwarder_block_p (bb))
102 BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
105 /* Recompute forwarder flag after block has been modified. */
108 update_forwarder_flag (basic_block bb)
110 if (forwarder_block_p (bb))
111 BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
113 BB_CLEAR_FLAG (bb, BB_FORWARDER_BLOCK);
116 /* Simplify a conditional jump around an unconditional jump.
117 Return true if something changed. */
120 try_simplify_condjump (basic_block cbranch_block)
122 basic_block jump_block, jump_dest_block, cbranch_dest_block;
123 edge cbranch_jump_edge, cbranch_fallthru_edge;
126 /* Verify that there are exactly two successors. */
127 if (!cbranch_block->succ
128 || !cbranch_block->succ->succ_next
129 || cbranch_block->succ->succ_next->succ_next)
132 /* Verify that we've got a normal conditional branch at the end
134 cbranch_insn = BB_END (cbranch_block);
135 if (!any_condjump_p (cbranch_insn))
138 cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
139 cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
141 /* The next block must not have multiple predecessors, must not
142 be the last block in the function, and must contain just the
143 unconditional jump. */
144 jump_block = cbranch_fallthru_edge->dest;
145 if (jump_block->pred->pred_next
146 || jump_block->next_bb == EXIT_BLOCK_PTR
147 || !FORWARDER_BLOCK_P (jump_block))
149 jump_dest_block = jump_block->succ->dest;
151 /* If we are partitioning hot/cold basic blocks, we don't want to
152 mess up unconditional or indirect jumps that cross between hot
155 Basic block partitioning may result in some jumps that appear to
156 be optimizable (or blocks that appear to be mergeable), but which really
157 must be left untouched (they are required to make it safely across
158 partition boundaries). See the comments at the top of
159 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
161 if (flag_reorder_blocks_and_partition
162 && (BB_PARTITION (jump_block) != BB_PARTITION (jump_dest_block)
163 || (cbranch_jump_edge->flags & EDGE_CROSSING)))
166 /* The conditional branch must target the block after the
167 unconditional branch. */
168 cbranch_dest_block = cbranch_jump_edge->dest;
170 if (cbranch_dest_block == EXIT_BLOCK_PTR
171 || !can_fallthru (jump_block, cbranch_dest_block))
174 /* Invert the conditional branch. */
175 if (!invert_jump (cbranch_insn, block_label (jump_dest_block), 0))
179 fprintf (dump_file, "Simplifying condjump %i around jump %i\n",
180 INSN_UID (cbranch_insn), INSN_UID (BB_END (jump_block)));
182 /* Success. Update the CFG to match. Note that after this point
183 the edge variable names appear backwards; the redirection is done
184 this way to preserve edge profile data. */
185 cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
187 cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
189 cbranch_jump_edge->flags |= EDGE_FALLTHRU;
190 cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
191 update_br_prob_note (cbranch_block);
193 /* Delete the block with the unconditional jump, and clean up the mess. */
194 delete_basic_block (jump_block);
195 tidy_fallthru_edge (cbranch_jump_edge);
196 update_forwarder_flag (cbranch_block);
201 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
202 on register. Used by jump threading. */
205 mark_effect (rtx exp, regset nonequal)
209 switch (GET_CODE (exp))
211 /* In case we do clobber the register, mark it as equal, as we know the
212 value is dead so it don't have to match. */
214 if (REG_P (XEXP (exp, 0)))
216 dest = XEXP (exp, 0);
217 regno = REGNO (dest);
218 CLEAR_REGNO_REG_SET (nonequal, regno);
219 if (regno < FIRST_PSEUDO_REGISTER)
221 int n = hard_regno_nregs[regno][GET_MODE (dest)];
223 CLEAR_REGNO_REG_SET (nonequal, regno + n);
229 if (rtx_equal_for_cselib_p (SET_DEST (exp), SET_SRC (exp)))
231 dest = SET_DEST (exp);
236 regno = REGNO (dest);
237 SET_REGNO_REG_SET (nonequal, regno);
238 if (regno < FIRST_PSEUDO_REGISTER)
240 int n = hard_regno_nregs[regno][GET_MODE (dest)];
242 SET_REGNO_REG_SET (nonequal, regno + n);
251 /* Return nonzero if X is a register set in regset DATA.
252 Called via for_each_rtx. */
254 mentions_nonequal_regs (rtx *x, void *data)
256 regset nonequal = (regset) data;
262 if (REGNO_REG_SET_P (nonequal, regno))
264 if (regno < FIRST_PSEUDO_REGISTER)
266 int n = hard_regno_nregs[regno][GET_MODE (*x)];
268 if (REGNO_REG_SET_P (nonequal, regno + n))
274 /* Attempt to prove that the basic block B will have no side effects and
275 always continues in the same edge if reached via E. Return the edge
276 if exist, NULL otherwise. */
279 thread_jump (int mode, edge e, basic_block b)
281 rtx set1, set2, cond1, cond2, insn;
282 enum rtx_code code1, code2, reversed_code2;
283 bool reverse1 = false;
288 if (BB_FLAGS (b) & BB_NONTHREADABLE_BLOCK)
291 /* At the moment, we do handle only conditional jumps, but later we may
292 want to extend this code to tablejumps and others. */
293 if (!e->src->succ->succ_next || e->src->succ->succ_next->succ_next)
295 if (!b->succ || !b->succ->succ_next || b->succ->succ_next->succ_next)
297 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
301 /* Second branch must end with onlyjump, as we will eliminate the jump. */
302 if (!any_condjump_p (BB_END (e->src)))
305 if (!any_condjump_p (BB_END (b)) || !onlyjump_p (BB_END (b)))
307 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
311 set1 = pc_set (BB_END (e->src));
312 set2 = pc_set (BB_END (b));
313 if (((e->flags & EDGE_FALLTHRU) != 0)
314 != (XEXP (SET_SRC (set1), 1) == pc_rtx))
317 cond1 = XEXP (SET_SRC (set1), 0);
318 cond2 = XEXP (SET_SRC (set2), 0);
320 code1 = reversed_comparison_code (cond1, BB_END (e->src));
322 code1 = GET_CODE (cond1);
324 code2 = GET_CODE (cond2);
325 reversed_code2 = reversed_comparison_code (cond2, BB_END (b));
327 if (!comparison_dominates_p (code1, code2)
328 && !comparison_dominates_p (code1, reversed_code2))
331 /* Ensure that the comparison operators are equivalent.
332 ??? This is far too pessimistic. We should allow swapped operands,
333 different CCmodes, or for example comparisons for interval, that
334 dominate even when operands are not equivalent. */
335 if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
336 || !rtx_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
339 /* Short circuit cases where block B contains some side effects, as we can't
341 for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b));
342 insn = NEXT_INSN (insn))
343 if (INSN_P (insn) && side_effects_p (PATTERN (insn)))
345 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
351 /* First process all values computed in the source basic block. */
352 for (insn = NEXT_INSN (BB_HEAD (e->src)); insn != NEXT_INSN (BB_END (e->src));
353 insn = NEXT_INSN (insn))
355 cselib_process_insn (insn);
357 nonequal = BITMAP_XMALLOC();
358 CLEAR_REG_SET (nonequal);
360 /* Now assume that we've continued by the edge E to B and continue
361 processing as if it were same basic block.
362 Our goal is to prove that whole block is an NOOP. */
364 for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b)) && !failed;
365 insn = NEXT_INSN (insn))
369 rtx pat = PATTERN (insn);
371 if (GET_CODE (pat) == PARALLEL)
373 for (i = 0; i < XVECLEN (pat, 0); i++)
374 failed |= mark_effect (XVECEXP (pat, 0, i), nonequal);
377 failed |= mark_effect (pat, nonequal);
380 cselib_process_insn (insn);
383 /* Later we should clear nonequal of dead registers. So far we don't
384 have life information in cfg_cleanup. */
387 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
391 /* cond2 must not mention any register that is not equal to the
393 if (for_each_rtx (&cond2, mentions_nonequal_regs, nonequal))
396 /* In case liveness information is available, we need to prove equivalence
397 only of the live values. */
398 if (mode & CLEANUP_UPDATE_LIFE)
399 AND_REG_SET (nonequal, b->global_live_at_end);
401 EXECUTE_IF_SET_IN_REG_SET (nonequal, 0, i, goto failed_exit;);
403 BITMAP_XFREE (nonequal);
405 if ((comparison_dominates_p (code1, code2) != 0)
406 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
407 return BRANCH_EDGE (b);
409 return FALLTHRU_EDGE (b);
412 BITMAP_XFREE (nonequal);
417 /* Attempt to forward edges leaving basic block B.
418 Return true if successful. */
421 try_forward_edges (int mode, basic_block b)
423 bool changed = false;
424 edge e, next, *threaded_edges = NULL;
426 /* If we are partitioning hot/cold basic blocks, we don't want to
427 mess up unconditional or indirect jumps that cross between hot
430 Basic block partitioning may result in some jumps that appear to
431 be optimizable (or blocks that appear to be mergeable), but which really m
432 ust be left untouched (they are required to make it safely across
433 partition boundaries). See the comments at the top of
434 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
436 if (flag_reorder_blocks_and_partition
437 && find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
440 for (e = b->succ; e; e = next)
442 basic_block target, first;
444 bool threaded = false;
445 int nthreaded_edges = 0;
446 bool may_thread = first_pass | (b->flags & BB_DIRTY);
450 /* Skip complex edges because we don't know how to update them.
452 Still handle fallthru edges, as we can succeed to forward fallthru
453 edge to the same place as the branch edge of conditional branch
454 and turn conditional branch to an unconditional branch. */
455 if (e->flags & EDGE_COMPLEX)
458 target = first = e->dest;
461 /* If we are partitioning hot/cold basic_blocks, we don't want to mess
462 up jumps that cross between hot/cold sections.
464 Basic block partitioning may result in some jumps that appear
465 to be optimizable (or blocks that appear to be mergeable), but which
466 really must be left untouched (they are required to make it safely
467 across partition boundaries). See the comments at the top of
468 bb-reorder.c:partition_hot_cold_basic_blocks for complete
471 if (flag_reorder_blocks_and_partition
472 && first != EXIT_BLOCK_PTR
473 && find_reg_note (BB_END (first), REG_CROSSING_JUMP, NULL_RTX))
476 while (counter < n_basic_blocks)
478 basic_block new_target = NULL;
479 bool new_target_threaded = false;
480 may_thread |= target->flags & BB_DIRTY;
482 if (FORWARDER_BLOCK_P (target)
483 && !(target->succ->flags & EDGE_CROSSING)
484 && target->succ->dest != EXIT_BLOCK_PTR)
486 /* Bypass trivial infinite loops. */
487 if (target == target->succ->dest)
488 counter = n_basic_blocks;
489 new_target = target->succ->dest;
492 /* Allow to thread only over one edge at time to simplify updating
494 else if ((mode & CLEANUP_THREADING) && may_thread)
496 edge t = thread_jump (mode, e, target);
500 threaded_edges = xmalloc (sizeof (*threaded_edges)
506 /* Detect an infinite loop across blocks not
507 including the start block. */
508 for (i = 0; i < nthreaded_edges; ++i)
509 if (threaded_edges[i] == t)
511 if (i < nthreaded_edges)
513 counter = n_basic_blocks;
518 /* Detect an infinite loop across the start block. */
522 gcc_assert (nthreaded_edges < n_basic_blocks);
523 threaded_edges[nthreaded_edges++] = t;
525 new_target = t->dest;
526 new_target_threaded = true;
533 /* Avoid killing of loop pre-headers, as it is the place loop
534 optimizer wants to hoist code to.
536 For fallthru forwarders, the LOOP_BEG note must appear between
537 the header of block and CODE_LABEL of the loop, for non forwarders
538 it must appear before the JUMP_INSN. */
539 if ((mode & CLEANUP_PRE_LOOP) && optimize)
541 rtx insn = (target->succ->flags & EDGE_FALLTHRU
542 ? BB_HEAD (target) : prev_nonnote_insn (BB_END (target)));
545 insn = NEXT_INSN (insn);
547 for (; insn && !LABEL_P (insn) && !INSN_P (insn);
548 insn = NEXT_INSN (insn))
550 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
556 /* Do not clean up branches to just past the end of a loop
557 at this time; it can mess up the loop optimizer's
558 recognition of some patterns. */
560 insn = PREV_INSN (BB_HEAD (target));
561 if (insn && NOTE_P (insn)
562 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
568 threaded |= new_target_threaded;
571 if (counter >= n_basic_blocks)
574 fprintf (dump_file, "Infinite loop in BB %i.\n",
577 else if (target == first)
578 ; /* We didn't do anything. */
581 /* Save the values now, as the edge may get removed. */
582 gcov_type edge_count = e->count;
583 int edge_probability = e->probability;
587 /* Don't force if target is exit block. */
588 if (threaded && target != EXIT_BLOCK_PTR)
590 notice_new_block (redirect_edge_and_branch_force (e, target));
592 fprintf (dump_file, "Conditionals threaded.\n");
594 else if (!redirect_edge_and_branch (e, target))
598 "Forwarding edge %i->%i to %i failed.\n",
599 b->index, e->dest->index, target->index);
603 /* We successfully forwarded the edge. Now update profile
604 data: for each edge we traversed in the chain, remove
605 the original edge's execution count. */
606 edge_frequency = ((edge_probability * b->frequency
607 + REG_BR_PROB_BASE / 2)
610 if (!FORWARDER_BLOCK_P (b) && forwarder_block_p (b))
611 BB_SET_FLAG (b, BB_FORWARDER_BLOCK);
617 if (first->succ->succ_next)
619 gcc_assert (n < nthreaded_edges);
620 t = threaded_edges [n++];
621 gcc_assert (t->src == first);
622 update_bb_profile_for_threading (first, edge_frequency,
624 update_br_prob_note (first);
628 first->count -= edge_count;
629 if (first->count < 0)
631 first->frequency -= edge_frequency;
632 if (first->frequency < 0)
633 first->frequency = 0;
634 /* It is possible that as the result of
635 threading we've removed edge as it is
636 threaded to the fallthru edge. Avoid
637 getting out of sync. */
638 if (n < nthreaded_edges
639 && first == threaded_edges [n]->src)
644 t->count -= edge_count;
649 while (first != target);
656 free (threaded_edges);
661 /* Blocks A and B are to be merged into a single block. A has no incoming
662 fallthru edge, so it can be moved before B without adding or modifying
663 any jumps (aside from the jump from A to B). */
666 merge_blocks_move_predecessor_nojumps (basic_block a, basic_block b)
671 /* If we are partitioning hot/cold basic blocks, we don't want to
672 mess up unconditional or indirect jumps that cross between hot
675 Basic block partitioning may result in some jumps that appear to
676 be optimizable (or blocks that appear to be mergeable), but which really
677 must be left untouched (they are required to make it safely across
678 partition boundaries). See the comments at the top of
679 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
681 if (flag_reorder_blocks_and_partition
682 && (BB_PARTITION (a) != BB_PARTITION (b)
683 || find_reg_note (BB_END (a), REG_CROSSING_JUMP, NULL_RTX)))
686 barrier = next_nonnote_insn (BB_END (a));
687 gcc_assert (BARRIER_P (barrier));
688 delete_insn (barrier);
690 /* Move block and loop notes out of the chain so that we do not
693 ??? A better solution would be to squeeze out all the non-nested notes
694 and adjust the block trees appropriately. Even better would be to have
695 a tighter connection between block trees and rtl so that this is not
697 only_notes = squeeze_notes (&BB_HEAD (a), &BB_END (a));
698 gcc_assert (!only_notes);
700 /* Scramble the insn chain. */
701 if (BB_END (a) != PREV_INSN (BB_HEAD (b)))
702 reorder_insns_nobb (BB_HEAD (a), BB_END (a), PREV_INSN (BB_HEAD (b)));
703 a->flags |= BB_DIRTY;
706 fprintf (dump_file, "Moved block %d before %d and merged.\n",
709 /* Swap the records for the two blocks around. */
712 link_block (a, b->prev_bb);
714 /* Now blocks A and B are contiguous. Merge them. */
718 /* Blocks A and B are to be merged into a single block. B has no outgoing
719 fallthru edge, so it can be moved after A without adding or modifying
720 any jumps (aside from the jump from A to B). */
723 merge_blocks_move_successor_nojumps (basic_block a, basic_block b)
725 rtx barrier, real_b_end;
729 /* If we are partitioning hot/cold basic blocks, we don't want to
730 mess up unconditional or indirect jumps that cross between hot
733 Basic block partitioning may result in some jumps that appear to
734 be optimizable (or blocks that appear to be mergeable), but which really
735 must be left untouched (they are required to make it safely across
736 partition boundaries). See the comments at the top of
737 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
739 if (flag_reorder_blocks_and_partition
740 && (find_reg_note (BB_END (a), REG_CROSSING_JUMP, NULL_RTX)
741 || BB_PARTITION (a) != BB_PARTITION (b)))
744 real_b_end = BB_END (b);
746 /* If there is a jump table following block B temporarily add the jump table
747 to block B so that it will also be moved to the correct location. */
748 if (tablejump_p (BB_END (b), &label, &table)
749 && prev_active_insn (label) == BB_END (b))
754 /* There had better have been a barrier there. Delete it. */
755 barrier = NEXT_INSN (BB_END (b));
756 if (barrier && BARRIER_P (barrier))
757 delete_insn (barrier);
759 /* Move block and loop notes out of the chain so that we do not
762 ??? A better solution would be to squeeze out all the non-nested notes
763 and adjust the block trees appropriately. Even better would be to have
764 a tighter connection between block trees and rtl so that this is not
766 only_notes = squeeze_notes (&BB_HEAD (b), &BB_END (b));
767 gcc_assert (!only_notes);
770 /* Scramble the insn chain. */
771 reorder_insns_nobb (BB_HEAD (b), BB_END (b), BB_END (a));
773 /* Restore the real end of b. */
774 BB_END (b) = real_b_end;
777 fprintf (dump_file, "Moved block %d after %d and merged.\n",
780 /* Now blocks A and B are contiguous. Merge them. */
784 /* Attempt to merge basic blocks that are potentially non-adjacent.
785 Return NULL iff the attempt failed, otherwise return basic block
786 where cleanup_cfg should continue. Because the merging commonly
787 moves basic block away or introduces another optimization
788 possibility, return basic block just before B so cleanup_cfg don't
791 It may be good idea to return basic block before C in the case
792 C has been moved after B and originally appeared earlier in the
793 insn sequence, but we have no information available about the
794 relative ordering of these two. Hopefully it is not too common. */
797 merge_blocks_move (edge e, basic_block b, basic_block c, int mode)
801 /* If we are partitioning hot/cold basic blocks, we don't want to
802 mess up unconditional or indirect jumps that cross between hot
805 Basic block partitioning may result in some jumps that appear to
806 be optimizable (or blocks that appear to be mergeable), but which really
807 must be left untouched (they are required to make it safely across
808 partition boundaries). See the comments at the top of
809 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
811 if (flag_reorder_blocks_and_partition
812 && (find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)
813 || find_reg_note (BB_END (c), REG_CROSSING_JUMP, NULL_RTX)
814 || BB_PARTITION (b) != BB_PARTITION (c)))
819 /* If B has a fallthru edge to C, no need to move anything. */
820 if (e->flags & EDGE_FALLTHRU)
822 int b_index = b->index, c_index = c->index;
824 update_forwarder_flag (b);
827 fprintf (dump_file, "Merged %d and %d without moving.\n",
830 return b->prev_bb == ENTRY_BLOCK_PTR ? b : b->prev_bb;
833 /* Otherwise we will need to move code around. Do that only if expensive
834 transformations are allowed. */
835 else if (mode & CLEANUP_EXPENSIVE)
837 edge tmp_edge, b_fallthru_edge;
838 bool c_has_outgoing_fallthru;
839 bool b_has_incoming_fallthru;
841 /* Avoid overactive code motion, as the forwarder blocks should be
842 eliminated by edge redirection instead. One exception might have
843 been if B is a forwarder block and C has no fallthru edge, but
844 that should be cleaned up by bb-reorder instead. */
845 if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
848 /* We must make sure to not munge nesting of lexical blocks,
849 and loop notes. This is done by squeezing out all the notes
850 and leaving them there to lie. Not ideal, but functional. */
852 for (tmp_edge = c->succ; tmp_edge; tmp_edge = tmp_edge->succ_next)
853 if (tmp_edge->flags & EDGE_FALLTHRU)
856 c_has_outgoing_fallthru = (tmp_edge != NULL);
858 for (tmp_edge = b->pred; tmp_edge; tmp_edge = tmp_edge->pred_next)
859 if (tmp_edge->flags & EDGE_FALLTHRU)
862 b_has_incoming_fallthru = (tmp_edge != NULL);
863 b_fallthru_edge = tmp_edge;
866 next = next->prev_bb;
868 /* Otherwise, we're going to try to move C after B. If C does
869 not have an outgoing fallthru, then it can be moved
870 immediately after B without introducing or modifying jumps. */
871 if (! c_has_outgoing_fallthru)
873 merge_blocks_move_successor_nojumps (b, c);
874 return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
877 /* If B does not have an incoming fallthru, then it can be moved
878 immediately before C without introducing or modifying jumps.
879 C cannot be the first block, so we do not have to worry about
880 accessing a non-existent block. */
882 if (b_has_incoming_fallthru)
886 if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
888 bb = force_nonfallthru (b_fallthru_edge);
890 notice_new_block (bb);
893 merge_blocks_move_predecessor_nojumps (b, c);
894 return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
901 /* Removes the memory attributes of MEM expression
902 if they are not equal. */
905 merge_memattrs (rtx x, rtx y)
914 if (x == 0 || y == 0)
919 if (code != GET_CODE (y))
922 if (GET_MODE (x) != GET_MODE (y))
925 if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y))
929 else if (! MEM_ATTRS (y))
933 if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
935 set_mem_alias_set (x, 0);
936 set_mem_alias_set (y, 0);
939 if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
943 set_mem_offset (x, 0);
944 set_mem_offset (y, 0);
946 else if (MEM_OFFSET (x) != MEM_OFFSET (y))
948 set_mem_offset (x, 0);
949 set_mem_offset (y, 0);
952 set_mem_size (x, GEN_INT (MAX (INTVAL (MEM_SIZE (x)),
953 INTVAL (MEM_SIZE (y)))));
954 set_mem_size (y, MEM_SIZE (x));
956 set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
957 set_mem_align (y, MEM_ALIGN (x));
961 fmt = GET_RTX_FORMAT (code);
962 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
967 /* Two vectors must have the same length. */
968 if (XVECLEN (x, i) != XVECLEN (y, i))
971 for (j = 0; j < XVECLEN (x, i); j++)
972 merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
977 merge_memattrs (XEXP (x, i), XEXP (y, i));
984 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
987 insns_match_p (int mode ATTRIBUTE_UNUSED, rtx i1, rtx i2)
991 /* Verify that I1 and I2 are equivalent. */
992 if (GET_CODE (i1) != GET_CODE (i2))
998 if (GET_CODE (p1) != GET_CODE (p2))
1001 /* If this is a CALL_INSN, compare register usage information.
1002 If we don't check this on stack register machines, the two
1003 CALL_INSNs might be merged leaving reg-stack.c with mismatching
1004 numbers of stack registers in the same basic block.
1005 If we don't check this on machines with delay slots, a delay slot may
1006 be filled that clobbers a parameter expected by the subroutine.
1008 ??? We take the simple route for now and assume that if they're
1009 equal, they were constructed identically. */
1012 && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
1013 CALL_INSN_FUNCTION_USAGE (i2))
1014 || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)))
1018 /* If cross_jump_death_matters is not 0, the insn's mode
1019 indicates whether or not the insn contains any stack-like
1022 if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
1024 /* If register stack conversion has already been done, then
1025 death notes must also be compared before it is certain that
1026 the two instruction streams match. */
1029 HARD_REG_SET i1_regset, i2_regset;
1031 CLEAR_HARD_REG_SET (i1_regset);
1032 CLEAR_HARD_REG_SET (i2_regset);
1034 for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
1035 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
1036 SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
1038 for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
1039 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
1040 SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
1042 GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
1051 if (reload_completed
1052 ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
1055 /* Do not do EQUIV substitution after reload. First, we're undoing the
1056 work of reload_cse. Second, we may be undoing the work of the post-
1057 reload splitting pass. */
1058 /* ??? Possibly add a new phase switch variable that can be used by
1059 targets to disallow the troublesome insns after splitting. */
1060 if (!reload_completed)
1062 /* The following code helps take care of G++ cleanups. */
1063 rtx equiv1 = find_reg_equal_equiv_note (i1);
1064 rtx equiv2 = find_reg_equal_equiv_note (i2);
1066 if (equiv1 && equiv2
1067 /* If the equivalences are not to a constant, they may
1068 reference pseudos that no longer exist, so we can't
1070 && (! reload_completed
1071 || (CONSTANT_P (XEXP (equiv1, 0))
1072 && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
1074 rtx s1 = single_set (i1);
1075 rtx s2 = single_set (i2);
1076 if (s1 != 0 && s2 != 0
1077 && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
1079 validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
1080 validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
1081 if (! rtx_renumbered_equal_p (p1, p2))
1083 else if (apply_change_group ())
1092 /* Look through the insns at the end of BB1 and BB2 and find the longest
1093 sequence that are equivalent. Store the first insns for that sequence
1094 in *F1 and *F2 and return the sequence length.
1096 To simplify callers of this function, if the blocks match exactly,
1097 store the head of the blocks in *F1 and *F2. */
1100 flow_find_cross_jump (int mode ATTRIBUTE_UNUSED, basic_block bb1,
1101 basic_block bb2, rtx *f1, rtx *f2)
1103 rtx i1, i2, last1, last2, afterlast1, afterlast2;
1106 /* Skip simple jumps at the end of the blocks. Complex jumps still
1107 need to be compared for equivalence, which we'll do below. */
1110 last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
1112 || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
1115 i1 = PREV_INSN (i1);
1120 || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
1123 /* Count everything except for unconditional jump as insn. */
1124 if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
1126 i2 = PREV_INSN (i2);
1132 while (!INSN_P (i1) && i1 != BB_HEAD (bb1))
1133 i1 = PREV_INSN (i1);
1135 while (!INSN_P (i2) && i2 != BB_HEAD (bb2))
1136 i2 = PREV_INSN (i2);
1138 if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
1141 if (!insns_match_p (mode, i1, i2))
1144 merge_memattrs (i1, i2);
1146 /* Don't begin a cross-jump with a NOTE insn. */
1149 /* If the merged insns have different REG_EQUAL notes, then
1151 rtx equiv1 = find_reg_equal_equiv_note (i1);
1152 rtx equiv2 = find_reg_equal_equiv_note (i2);
1154 if (equiv1 && !equiv2)
1155 remove_note (i1, equiv1);
1156 else if (!equiv1 && equiv2)
1157 remove_note (i2, equiv2);
1158 else if (equiv1 && equiv2
1159 && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
1161 remove_note (i1, equiv1);
1162 remove_note (i2, equiv2);
1165 afterlast1 = last1, afterlast2 = last2;
1166 last1 = i1, last2 = i2;
1170 i1 = PREV_INSN (i1);
1171 i2 = PREV_INSN (i2);
1175 /* Don't allow the insn after a compare to be shared by
1176 cross-jumping unless the compare is also shared. */
1177 if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
1178 last1 = afterlast1, last2 = afterlast2, ninsns--;
1181 /* Include preceding notes and labels in the cross-jump. One,
1182 this may bring us to the head of the blocks as requested above.
1183 Two, it keeps line number notes as matched as may be. */
1186 while (last1 != BB_HEAD (bb1) && !INSN_P (PREV_INSN (last1)))
1187 last1 = PREV_INSN (last1);
1189 if (last1 != BB_HEAD (bb1) && LABEL_P (PREV_INSN (last1)))
1190 last1 = PREV_INSN (last1);
1192 while (last2 != BB_HEAD (bb2) && !INSN_P (PREV_INSN (last2)))
1193 last2 = PREV_INSN (last2);
1195 if (last2 != BB_HEAD (bb2) && LABEL_P (PREV_INSN (last2)))
1196 last2 = PREV_INSN (last2);
1205 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1206 the branch instruction. This means that if we commonize the control
1207 flow before end of the basic block, the semantic remains unchanged.
1209 We may assume that there exists one edge with a common destination. */
1212 outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
1214 int nehedges1 = 0, nehedges2 = 0;
1215 edge fallthru1 = 0, fallthru2 = 0;
1218 /* If BB1 has only one successor, we may be looking at either an
1219 unconditional jump, or a fake edge to exit. */
1220 if (bb1->succ && !bb1->succ->succ_next
1221 && (bb1->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1222 && (!JUMP_P (BB_END (bb1)) || simplejump_p (BB_END (bb1))))
1223 return (bb2->succ && !bb2->succ->succ_next
1224 && (bb2->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1225 && (!JUMP_P (BB_END (bb2)) || simplejump_p (BB_END (bb2))));
1227 /* Match conditional jumps - this may get tricky when fallthru and branch
1228 edges are crossed. */
1230 && bb1->succ->succ_next
1231 && !bb1->succ->succ_next->succ_next
1232 && any_condjump_p (BB_END (bb1))
1233 && onlyjump_p (BB_END (bb1)))
1235 edge b1, f1, b2, f2;
1236 bool reverse, match;
1237 rtx set1, set2, cond1, cond2;
1238 enum rtx_code code1, code2;
1241 || !bb2->succ->succ_next
1242 || bb2->succ->succ_next->succ_next
1243 || !any_condjump_p (BB_END (bb2))
1244 || !onlyjump_p (BB_END (bb2)))
1247 b1 = BRANCH_EDGE (bb1);
1248 b2 = BRANCH_EDGE (bb2);
1249 f1 = FALLTHRU_EDGE (bb1);
1250 f2 = FALLTHRU_EDGE (bb2);
1252 /* Get around possible forwarders on fallthru edges. Other cases
1253 should be optimized out already. */
1254 if (FORWARDER_BLOCK_P (f1->dest))
1255 f1 = f1->dest->succ;
1257 if (FORWARDER_BLOCK_P (f2->dest))
1258 f2 = f2->dest->succ;
1260 /* To simplify use of this function, return false if there are
1261 unneeded forwarder blocks. These will get eliminated later
1262 during cleanup_cfg. */
1263 if (FORWARDER_BLOCK_P (f1->dest)
1264 || FORWARDER_BLOCK_P (f2->dest)
1265 || FORWARDER_BLOCK_P (b1->dest)
1266 || FORWARDER_BLOCK_P (b2->dest))
1269 if (f1->dest == f2->dest && b1->dest == b2->dest)
1271 else if (f1->dest == b2->dest && b1->dest == f2->dest)
1276 set1 = pc_set (BB_END (bb1));
1277 set2 = pc_set (BB_END (bb2));
1278 if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
1279 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
1282 cond1 = XEXP (SET_SRC (set1), 0);
1283 cond2 = XEXP (SET_SRC (set2), 0);
1284 code1 = GET_CODE (cond1);
1286 code2 = reversed_comparison_code (cond2, BB_END (bb2));
1288 code2 = GET_CODE (cond2);
1290 if (code2 == UNKNOWN)
1293 /* Verify codes and operands match. */
1294 match = ((code1 == code2
1295 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
1296 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
1297 || (code1 == swap_condition (code2)
1298 && rtx_renumbered_equal_p (XEXP (cond1, 1),
1300 && rtx_renumbered_equal_p (XEXP (cond1, 0),
1303 /* If we return true, we will join the blocks. Which means that
1304 we will only have one branch prediction bit to work with. Thus
1305 we require the existing branches to have probabilities that are
1309 && maybe_hot_bb_p (bb1)
1310 && maybe_hot_bb_p (bb2))
1314 if (b1->dest == b2->dest)
1315 prob2 = b2->probability;
1317 /* Do not use f2 probability as f2 may be forwarded. */
1318 prob2 = REG_BR_PROB_BASE - b2->probability;
1320 /* Fail if the difference in probabilities is greater than 50%.
1321 This rules out two well-predicted branches with opposite
1323 if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
1327 "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
1328 bb1->index, bb2->index, b1->probability, prob2);
1334 if (dump_file && match)
1335 fprintf (dump_file, "Conditionals in bb %i and %i match.\n",
1336 bb1->index, bb2->index);
1341 /* Generic case - we are seeing a computed jump, table jump or trapping
1344 #ifndef CASE_DROPS_THROUGH
1345 /* Check whether there are tablejumps in the end of BB1 and BB2.
1346 Return true if they are identical. */
1351 if (tablejump_p (BB_END (bb1), &label1, &table1)
1352 && tablejump_p (BB_END (bb2), &label2, &table2)
1353 && GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2)))
1355 /* The labels should never be the same rtx. If they really are same
1356 the jump tables are same too. So disable crossjumping of blocks BB1
1357 and BB2 because when deleting the common insns in the end of BB1
1358 by delete_basic_block () the jump table would be deleted too. */
1359 /* If LABEL2 is referenced in BB1->END do not do anything
1360 because we would loose information when replacing
1361 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1362 if (label1 != label2 && !rtx_referenced_p (label2, BB_END (bb1)))
1364 /* Set IDENTICAL to true when the tables are identical. */
1365 bool identical = false;
1368 p1 = PATTERN (table1);
1369 p2 = PATTERN (table2);
1370 if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2))
1374 else if (GET_CODE (p1) == ADDR_DIFF_VEC
1375 && (XVECLEN (p1, 1) == XVECLEN (p2, 1))
1376 && rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2))
1377 && rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3)))
1382 for (i = XVECLEN (p1, 1) - 1; i >= 0 && identical; i--)
1383 if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i)))
1389 replace_label_data rr;
1392 /* Temporarily replace references to LABEL1 with LABEL2
1393 in BB1->END so that we could compare the instructions. */
1396 rr.update_label_nuses = false;
1397 for_each_rtx (&BB_END (bb1), replace_label, &rr);
1399 match = insns_match_p (mode, BB_END (bb1), BB_END (bb2));
1400 if (dump_file && match)
1402 "Tablejumps in bb %i and %i match.\n",
1403 bb1->index, bb2->index);
1405 /* Set the original label in BB1->END because when deleting
1406 a block whose end is a tablejump, the tablejump referenced
1407 from the instruction is deleted too. */
1410 for_each_rtx (&BB_END (bb1), replace_label, &rr);
1420 /* First ensure that the instructions match. There may be many outgoing
1421 edges so this test is generally cheaper. */
1422 if (!insns_match_p (mode, BB_END (bb1), BB_END (bb2)))
1425 /* Search the outgoing edges, ensure that the counts do match, find possible
1426 fallthru and exception handling edges since these needs more
1428 for (e1 = bb1->succ, e2 = bb2->succ; e1 && e2;
1429 e1 = e1->succ_next, e2 = e2->succ_next)
1431 if (e1->flags & EDGE_EH)
1434 if (e2->flags & EDGE_EH)
1437 if (e1->flags & EDGE_FALLTHRU)
1439 if (e2->flags & EDGE_FALLTHRU)
1443 /* If number of edges of various types does not match, fail. */
1445 || nehedges1 != nehedges2
1446 || (fallthru1 != 0) != (fallthru2 != 0))
1449 /* fallthru edges must be forwarded to the same destination. */
1452 basic_block d1 = (forwarder_block_p (fallthru1->dest)
1453 ? fallthru1->dest->succ->dest: fallthru1->dest);
1454 basic_block d2 = (forwarder_block_p (fallthru2->dest)
1455 ? fallthru2->dest->succ->dest: fallthru2->dest);
1461 /* Ensure the same EH region. */
1463 rtx n1 = find_reg_note (BB_END (bb1), REG_EH_REGION, 0);
1464 rtx n2 = find_reg_note (BB_END (bb2), REG_EH_REGION, 0);
1469 if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
1473 /* We don't need to match the rest of edges as above checks should be enough
1474 to ensure that they are equivalent. */
1478 /* E1 and E2 are edges with the same destination block. Search their
1479 predecessors for common code. If found, redirect control flow from
1480 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1483 try_crossjump_to_edge (int mode, edge e1, edge e2)
1486 basic_block src1 = e1->src, src2 = e2->src;
1487 basic_block redirect_to, redirect_from, to_remove;
1488 rtx newpos1, newpos2;
1491 newpos1 = newpos2 = NULL_RTX;
1493 /* If we have partitioned hot/cold basic blocks, it is a bad idea
1494 to try this optimization.
1496 Basic block partitioning may result in some jumps that appear to
1497 be optimizable (or blocks that appear to be mergeable), but which really
1498 must be left untouched (they are required to make it safely across
1499 partition boundaries). See the comments at the top of
1500 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1502 if (flag_reorder_blocks_and_partition && no_new_pseudos)
1505 /* Search backward through forwarder blocks. We don't need to worry
1506 about multiple entry or chained forwarders, as they will be optimized
1507 away. We do this to look past the unconditional jump following a
1508 conditional jump that is required due to the current CFG shape. */
1510 && !src1->pred->pred_next
1511 && FORWARDER_BLOCK_P (src1))
1512 e1 = src1->pred, src1 = e1->src;
1515 && !src2->pred->pred_next
1516 && FORWARDER_BLOCK_P (src2))
1517 e2 = src2->pred, src2 = e2->src;
1519 /* Nothing to do if we reach ENTRY, or a common source block. */
1520 if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
1525 /* Seeing more than 1 forwarder blocks would confuse us later... */
1526 if (FORWARDER_BLOCK_P (e1->dest)
1527 && FORWARDER_BLOCK_P (e1->dest->succ->dest))
1530 if (FORWARDER_BLOCK_P (e2->dest)
1531 && FORWARDER_BLOCK_P (e2->dest->succ->dest))
1534 /* Likewise with dead code (possibly newly created by the other optimizations
1536 if (!src1->pred || !src2->pred)
1539 /* Look for the common insn sequence, part the first ... */
1540 if (!outgoing_edges_match (mode, src1, src2))
1543 /* ... and part the second. */
1544 nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
1546 /* Don't proceed with the crossjump unless we found a sufficient number
1547 of matching instructions or the 'from' block was totally matched
1548 (such that its predecessors will hopefully be redirected and the
1550 if ((nmatch < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
1551 && (newpos1 != BB_HEAD (src1)))
1554 #ifndef CASE_DROPS_THROUGH
1555 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1557 If we have tablejumps in the end of SRC1 and SRC2
1558 they have been already compared for equivalence in outgoing_edges_match ()
1559 so replace the references to TABLE1 by references to TABLE2. */
1564 if (tablejump_p (BB_END (src1), &label1, &table1)
1565 && tablejump_p (BB_END (src2), &label2, &table2)
1566 && label1 != label2)
1568 replace_label_data rr;
1571 /* Replace references to LABEL1 with LABEL2. */
1574 rr.update_label_nuses = true;
1575 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1577 /* Do not replace the label in SRC1->END because when deleting
1578 a block whose end is a tablejump, the tablejump referenced
1579 from the instruction is deleted too. */
1580 if (insn != BB_END (src1))
1581 for_each_rtx (&insn, replace_label, &rr);
1587 /* Avoid splitting if possible. */
1588 if (newpos2 == BB_HEAD (src2))
1593 fprintf (dump_file, "Splitting bb %i before %i insns\n",
1594 src2->index, nmatch);
1595 redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
1600 "Cross jumping from bb %i to bb %i; %i common insns\n",
1601 src1->index, src2->index, nmatch);
1603 redirect_to->count += src1->count;
1604 redirect_to->frequency += src1->frequency;
1605 /* We may have some registers visible trought the block. */
1606 redirect_to->flags |= BB_DIRTY;
1608 /* Recompute the frequencies and counts of outgoing edges. */
1609 for (s = redirect_to->succ; s; s = s->succ_next)
1612 basic_block d = s->dest;
1614 if (FORWARDER_BLOCK_P (d))
1617 for (s2 = src1->succ; ; s2 = s2->succ_next)
1619 basic_block d2 = s2->dest;
1620 if (FORWARDER_BLOCK_P (d2))
1621 d2 = d2->succ->dest;
1626 s->count += s2->count;
1628 /* Take care to update possible forwarder blocks. We verified
1629 that there is no more than one in the chain, so we can't run
1630 into infinite loop. */
1631 if (FORWARDER_BLOCK_P (s->dest))
1633 s->dest->succ->count += s2->count;
1634 s->dest->count += s2->count;
1635 s->dest->frequency += EDGE_FREQUENCY (s);
1638 if (FORWARDER_BLOCK_P (s2->dest))
1640 s2->dest->succ->count -= s2->count;
1641 if (s2->dest->succ->count < 0)
1642 s2->dest->succ->count = 0;
1643 s2->dest->count -= s2->count;
1644 s2->dest->frequency -= EDGE_FREQUENCY (s);
1645 if (s2->dest->frequency < 0)
1646 s2->dest->frequency = 0;
1647 if (s2->dest->count < 0)
1648 s2->dest->count = 0;
1651 if (!redirect_to->frequency && !src1->frequency)
1652 s->probability = (s->probability + s2->probability) / 2;
1655 = ((s->probability * redirect_to->frequency +
1656 s2->probability * src1->frequency)
1657 / (redirect_to->frequency + src1->frequency));
1660 update_br_prob_note (redirect_to);
1662 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1664 /* Skip possible basic block header. */
1665 if (LABEL_P (newpos1))
1666 newpos1 = NEXT_INSN (newpos1);
1668 if (NOTE_P (newpos1))
1669 newpos1 = NEXT_INSN (newpos1);
1671 redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
1672 to_remove = redirect_from->succ->dest;
1674 redirect_edge_and_branch_force (redirect_from->succ, redirect_to);
1675 delete_basic_block (to_remove);
1677 update_forwarder_flag (redirect_from);
1682 /* Search the predecessors of BB for common insn sequences. When found,
1683 share code between them by redirecting control flow. Return true if
1684 any changes made. */
1687 try_crossjump_bb (int mode, basic_block bb)
1689 edge e, e2, nexte2, nexte, fallthru;
1693 /* Nothing to do if there is not at least two incoming edges. */
1694 if (!bb->pred || !bb->pred->pred_next)
1697 /* If we are partitioning hot/cold basic blocks, we don't want to
1698 mess up unconditional or indirect jumps that cross between hot
1701 Basic block partitioning may result in some jumps that appear to
1702 be optimizable (or blocks that appear to be mergeable), but which really
1703 must be left untouched (they are required to make it safely across
1704 partition boundaries). See the comments at the top of
1705 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1707 if (flag_reorder_blocks_and_partition
1708 && (BB_PARTITION (bb->pred->src) != BB_PARTITION (bb->pred->pred_next->src)
1709 || (bb->pred->flags & EDGE_CROSSING)))
1712 /* It is always cheapest to redirect a block that ends in a branch to
1713 a block that falls through into BB, as that adds no branches to the
1714 program. We'll try that combination first. */
1716 max = PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES);
1717 for (e = bb->pred; e ; e = e->pred_next, n++)
1719 if (e->flags & EDGE_FALLTHRU)
1726 for (e = bb->pred; e; e = nexte)
1728 nexte = e->pred_next;
1730 /* As noted above, first try with the fallthru predecessor. */
1733 /* Don't combine the fallthru edge into anything else.
1734 If there is a match, we'll do it the other way around. */
1737 /* If nothing changed since the last attempt, there is nothing
1740 && (!(e->src->flags & BB_DIRTY)
1741 && !(fallthru->src->flags & BB_DIRTY)))
1744 if (try_crossjump_to_edge (mode, e, fallthru))
1752 /* Non-obvious work limiting check: Recognize that we're going
1753 to call try_crossjump_bb on every basic block. So if we have
1754 two blocks with lots of outgoing edges (a switch) and they
1755 share lots of common destinations, then we would do the
1756 cross-jump check once for each common destination.
1758 Now, if the blocks actually are cross-jump candidates, then
1759 all of their destinations will be shared. Which means that
1760 we only need check them for cross-jump candidacy once. We
1761 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1762 choosing to do the check from the block for which the edge
1763 in question is the first successor of A. */
1764 if (e->src->succ != e)
1767 for (e2 = bb->pred; e2; e2 = nexte2)
1769 nexte2 = e2->pred_next;
1774 /* We've already checked the fallthru edge above. */
1778 /* The "first successor" check above only prevents multiple
1779 checks of crossjump(A,B). In order to prevent redundant
1780 checks of crossjump(B,A), require that A be the block
1781 with the lowest index. */
1782 if (e->src->index > e2->src->index)
1785 /* If nothing changed since the last attempt, there is nothing
1788 && (!(e->src->flags & BB_DIRTY)
1789 && !(e2->src->flags & BB_DIRTY)))
1792 if (try_crossjump_to_edge (mode, e, e2))
1804 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1805 instructions etc. Return nonzero if changes were made. */
1808 try_optimize_cfg (int mode)
1810 bool changed_overall = false;
1813 basic_block bb, b, next;
1815 if (mode & CLEANUP_CROSSJUMP)
1816 add_noreturn_fake_exit_edges ();
1819 update_forwarder_flag (bb);
1821 if (mode & (CLEANUP_UPDATE_LIFE | CLEANUP_CROSSJUMP | CLEANUP_THREADING))
1824 if (! targetm.cannot_modify_jumps_p ())
1827 /* Attempt to merge blocks as made possible by edge removal. If
1828 a block has only one successor, and the successor has only
1829 one predecessor, they may be combined. */
1837 "\n\ntry_optimize_cfg iteration %i\n\n",
1840 for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR;)
1844 bool changed_here = false;
1846 /* Delete trivially dead basic blocks. */
1847 while (b->pred == NULL)
1851 fprintf (dump_file, "Deleting block %i.\n",
1854 delete_basic_block (b);
1855 if (!(mode & CLEANUP_CFGLAYOUT))
1860 /* Remove code labels no longer used. */
1861 if (b->pred->pred_next == NULL
1862 && (b->pred->flags & EDGE_FALLTHRU)
1863 && !(b->pred->flags & EDGE_COMPLEX)
1864 && LABEL_P (BB_HEAD (b))
1865 /* If the previous block ends with a branch to this
1866 block, we can't delete the label. Normally this
1867 is a condjump that is yet to be simplified, but
1868 if CASE_DROPS_THRU, this can be a tablejump with
1869 some element going to the same place as the
1870 default (fallthru). */
1871 && (b->pred->src == ENTRY_BLOCK_PTR
1872 || !JUMP_P (BB_END (b->pred->src))
1873 || ! label_is_jump_target_p (BB_HEAD (b),
1874 BB_END (b->pred->src))))
1876 rtx label = BB_HEAD (b);
1878 delete_insn_chain (label, label);
1879 /* In the case label is undeletable, move it after the
1880 BASIC_BLOCK note. */
1881 if (NOTE_LINE_NUMBER (BB_HEAD (b)) == NOTE_INSN_DELETED_LABEL)
1883 rtx bb_note = NEXT_INSN (BB_HEAD (b));
1885 reorder_insns_nobb (label, label, bb_note);
1886 BB_HEAD (b) = bb_note;
1889 fprintf (dump_file, "Deleted label in block %i.\n",
1893 /* If we fall through an empty block, we can remove it. */
1894 if (!(mode & CLEANUP_CFGLAYOUT)
1895 && b->pred->pred_next == NULL
1896 && (b->pred->flags & EDGE_FALLTHRU)
1897 && !LABEL_P (BB_HEAD (b))
1898 && FORWARDER_BLOCK_P (b)
1899 /* Note that forwarder_block_p true ensures that
1900 there is a successor for this block. */
1901 && (b->succ->flags & EDGE_FALLTHRU)
1902 && n_basic_blocks > 1)
1906 "Deleting fallthru block %i.\n",
1909 c = b->prev_bb == ENTRY_BLOCK_PTR ? b->next_bb : b->prev_bb;
1910 redirect_edge_succ_nodup (b->pred, b->succ->dest);
1911 delete_basic_block (b);
1916 if ((s = b->succ) != NULL
1917 && s->succ_next == NULL
1918 && !(s->flags & EDGE_COMPLEX)
1919 && (c = s->dest) != EXIT_BLOCK_PTR
1920 && c->pred->pred_next == NULL
1923 /* When not in cfg_layout mode use code aware of reordering
1924 INSN. This code possibly creates new basic blocks so it
1925 does not fit merge_blocks interface and is kept here in
1926 hope that it will become useless once more of compiler
1927 is transformed to use cfg_layout mode. */
1929 if ((mode & CLEANUP_CFGLAYOUT)
1930 && can_merge_blocks_p (b, c))
1932 merge_blocks (b, c);
1933 update_forwarder_flag (b);
1934 changed_here = true;
1936 else if (!(mode & CLEANUP_CFGLAYOUT)
1937 /* If the jump insn has side effects,
1938 we can't kill the edge. */
1939 && (!JUMP_P (BB_END (b))
1940 || (reload_completed
1941 ? simplejump_p (BB_END (b))
1942 : (onlyjump_p (BB_END (b))
1943 && !tablejump_p (BB_END (b),
1945 && (next = merge_blocks_move (s, b, c, mode)))
1948 changed_here = true;
1952 /* Simplify branch over branch. */
1953 if ((mode & CLEANUP_EXPENSIVE)
1954 && !(mode & CLEANUP_CFGLAYOUT)
1955 && try_simplify_condjump (b))
1956 changed_here = true;
1958 /* If B has a single outgoing edge, but uses a
1959 non-trivial jump instruction without side-effects, we
1960 can either delete the jump entirely, or replace it
1961 with a simple unconditional jump. */
1963 && ! b->succ->succ_next
1964 && b->succ->dest != EXIT_BLOCK_PTR
1965 && onlyjump_p (BB_END (b))
1966 && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)
1967 && try_redirect_by_replacing_jump (b->succ, b->succ->dest,
1968 (mode & CLEANUP_CFGLAYOUT) != 0))
1970 update_forwarder_flag (b);
1971 changed_here = true;
1974 /* Simplify branch to branch. */
1975 if (try_forward_edges (mode, b))
1976 changed_here = true;
1978 /* Look for shared code between blocks. */
1979 if ((mode & CLEANUP_CROSSJUMP)
1980 && try_crossjump_bb (mode, b))
1981 changed_here = true;
1983 /* Don't get confused by the index shift caused by
1991 if ((mode & CLEANUP_CROSSJUMP)
1992 && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
1995 #ifdef ENABLE_CHECKING
1997 verify_flow_info ();
2000 changed_overall |= changed;
2006 if (mode & CLEANUP_CROSSJUMP)
2007 remove_fake_exit_edges ();
2009 clear_aux_for_blocks ();
2011 return changed_overall;
2014 /* Delete all unreachable basic blocks. */
2017 delete_unreachable_blocks (void)
2019 bool changed = false;
2020 basic_block b, next_bb;
2022 find_unreachable_blocks ();
2024 /* Delete all unreachable basic blocks. */
2026 for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
2028 next_bb = b->next_bb;
2030 if (!(b->flags & BB_REACHABLE))
2032 delete_basic_block (b);
2038 tidy_fallthru_edges ();
2042 /* Merges sequential blocks if possible. */
2045 merge_seq_blocks (void)
2048 bool changed = false;
2050 for (bb = ENTRY_BLOCK_PTR->next_bb; bb != EXIT_BLOCK_PTR; )
2053 && !bb->succ->succ_next
2054 && can_merge_blocks_p (bb, bb->succ->dest))
2056 /* Merge the blocks and retry. */
2057 merge_blocks (bb, bb->succ->dest);
2068 /* Tidy the CFG by deleting unreachable code and whatnot. */
2071 cleanup_cfg (int mode)
2073 bool changed = false;
2075 timevar_push (TV_CLEANUP_CFG);
2076 if (delete_unreachable_blocks ())
2079 /* We've possibly created trivially dead code. Cleanup it right
2080 now to introduce more opportunities for try_optimize_cfg. */
2081 if (!(mode & (CLEANUP_NO_INSN_DEL | CLEANUP_UPDATE_LIFE))
2082 && !reload_completed)
2083 delete_trivially_dead_insns (get_insns(), max_reg_num ());
2088 while (try_optimize_cfg (mode))
2090 delete_unreachable_blocks (), changed = true;
2091 if (mode & CLEANUP_UPDATE_LIFE)
2093 /* Cleaning up CFG introduces more opportunities for dead code
2094 removal that in turn may introduce more opportunities for
2095 cleaning up the CFG. */
2096 if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
2098 | PROP_SCAN_DEAD_CODE
2099 | PROP_KILL_DEAD_CODE
2100 | ((mode & CLEANUP_LOG_LINKS)
2101 ? PROP_LOG_LINKS : 0)))
2104 else if (!(mode & CLEANUP_NO_INSN_DEL)
2105 && (mode & CLEANUP_EXPENSIVE)
2106 && !reload_completed)
2108 if (!delete_trivially_dead_insns (get_insns(), max_reg_num ()))
2113 delete_dead_jumptables ();
2116 /* Kill the data we won't maintain. */
2117 free_EXPR_LIST_list (&label_value_list);
2118 timevar_pop (TV_CLEANUP_CFG);