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, 2005, 2006, 2007, 2008, 2010, 2011
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
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"
43 #include "insn-config.h"
46 #include "diagnostic-core.h"
51 #include "cfglayout.h"
53 #include "tree-pass.h"
60 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
62 /* Set to true when we are running first pass of try_optimize_cfg loop. */
63 static bool first_pass;
65 /* Set to true if crossjumps occured in the latest run of try_optimize_cfg. */
66 static bool crossjumps_occured;
68 /* Set to true if we couldn't run an optimization due to stale liveness
69 information; we should run df_analyze to enable more opportunities. */
70 static bool block_was_dirty;
72 static bool try_crossjump_to_edge (int, edge, edge, enum replace_direction);
73 static bool try_crossjump_bb (int, basic_block);
74 static bool outgoing_edges_match (int, basic_block, basic_block);
75 static enum replace_direction old_insns_match_p (int, rtx, rtx);
77 static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
78 static void merge_blocks_move_successor_nojumps (basic_block, basic_block);
79 static bool try_optimize_cfg (int);
80 static bool try_simplify_condjump (basic_block);
81 static bool try_forward_edges (int, basic_block);
82 static edge thread_jump (edge, basic_block);
83 static bool mark_effect (rtx, bitmap);
84 static void notice_new_block (basic_block);
85 static void update_forwarder_flag (basic_block);
86 static int mentions_nonequal_regs (rtx *, void *);
87 static void merge_memattrs (rtx, rtx);
89 /* Set flags for newly created block. */
92 notice_new_block (basic_block bb)
97 if (forwarder_block_p (bb))
98 bb->flags |= BB_FORWARDER_BLOCK;
101 /* Recompute forwarder flag after block has been modified. */
104 update_forwarder_flag (basic_block bb)
106 if (forwarder_block_p (bb))
107 bb->flags |= BB_FORWARDER_BLOCK;
109 bb->flags &= ~BB_FORWARDER_BLOCK;
112 /* Simplify a conditional jump around an unconditional jump.
113 Return true if something changed. */
116 try_simplify_condjump (basic_block cbranch_block)
118 basic_block jump_block, jump_dest_block, cbranch_dest_block;
119 edge cbranch_jump_edge, cbranch_fallthru_edge;
122 /* Verify that there are exactly two successors. */
123 if (EDGE_COUNT (cbranch_block->succs) != 2)
126 /* Verify that we've got a normal conditional branch at the end
128 cbranch_insn = BB_END (cbranch_block);
129 if (!any_condjump_p (cbranch_insn))
132 cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
133 cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
135 /* The next block must not have multiple predecessors, must not
136 be the last block in the function, and must contain just the
137 unconditional jump. */
138 jump_block = cbranch_fallthru_edge->dest;
139 if (!single_pred_p (jump_block)
140 || jump_block->next_bb == EXIT_BLOCK_PTR
141 || !FORWARDER_BLOCK_P (jump_block))
143 jump_dest_block = single_succ (jump_block);
145 /* If we are partitioning hot/cold basic blocks, we don't want to
146 mess up unconditional or indirect jumps that cross between hot
149 Basic block partitioning may result in some jumps that appear to
150 be optimizable (or blocks that appear to be mergeable), but which really
151 must be left untouched (they are required to make it safely across
152 partition boundaries). See the comments at the top of
153 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
155 if (BB_PARTITION (jump_block) != BB_PARTITION (jump_dest_block)
156 || (cbranch_jump_edge->flags & EDGE_CROSSING))
159 /* The conditional branch must target the block after the
160 unconditional branch. */
161 cbranch_dest_block = cbranch_jump_edge->dest;
163 if (cbranch_dest_block == EXIT_BLOCK_PTR
164 || !can_fallthru (jump_block, cbranch_dest_block))
167 /* Invert the conditional branch. */
168 if (!invert_jump (cbranch_insn, block_label (jump_dest_block), 0))
172 fprintf (dump_file, "Simplifying condjump %i around jump %i\n",
173 INSN_UID (cbranch_insn), INSN_UID (BB_END (jump_block)));
175 /* Success. Update the CFG to match. Note that after this point
176 the edge variable names appear backwards; the redirection is done
177 this way to preserve edge profile data. */
178 cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
180 cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
182 cbranch_jump_edge->flags |= EDGE_FALLTHRU;
183 cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
184 update_br_prob_note (cbranch_block);
186 /* Delete the block with the unconditional jump, and clean up the mess. */
187 delete_basic_block (jump_block);
188 tidy_fallthru_edge (cbranch_jump_edge);
189 update_forwarder_flag (cbranch_block);
194 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
195 on register. Used by jump threading. */
198 mark_effect (rtx exp, regset nonequal)
202 switch (GET_CODE (exp))
204 /* In case we do clobber the register, mark it as equal, as we know the
205 value is dead so it don't have to match. */
207 if (REG_P (XEXP (exp, 0)))
209 dest = XEXP (exp, 0);
210 regno = REGNO (dest);
211 if (HARD_REGISTER_NUM_P (regno))
212 bitmap_clear_range (nonequal, regno,
213 hard_regno_nregs[regno][GET_MODE (dest)]);
215 bitmap_clear_bit (nonequal, regno);
220 if (rtx_equal_for_cselib_p (SET_DEST (exp), SET_SRC (exp)))
222 dest = SET_DEST (exp);
227 regno = REGNO (dest);
228 if (HARD_REGISTER_NUM_P (regno))
229 bitmap_set_range (nonequal, regno,
230 hard_regno_nregs[regno][GET_MODE (dest)]);
232 bitmap_set_bit (nonequal, regno);
240 /* Return nonzero if X is a register set in regset DATA.
241 Called via for_each_rtx. */
243 mentions_nonequal_regs (rtx *x, void *data)
245 regset nonequal = (regset) data;
251 if (REGNO_REG_SET_P (nonequal, regno))
253 if (regno < FIRST_PSEUDO_REGISTER)
255 int n = hard_regno_nregs[regno][GET_MODE (*x)];
257 if (REGNO_REG_SET_P (nonequal, regno + n))
263 /* Attempt to prove that the basic block B will have no side effects and
264 always continues in the same edge if reached via E. Return the edge
265 if exist, NULL otherwise. */
268 thread_jump (edge e, basic_block b)
270 rtx set1, set2, cond1, cond2, insn;
271 enum rtx_code code1, code2, reversed_code2;
272 bool reverse1 = false;
276 reg_set_iterator rsi;
278 if (b->flags & BB_NONTHREADABLE_BLOCK)
281 /* At the moment, we do handle only conditional jumps, but later we may
282 want to extend this code to tablejumps and others. */
283 if (EDGE_COUNT (e->src->succs) != 2)
285 if (EDGE_COUNT (b->succs) != 2)
287 b->flags |= BB_NONTHREADABLE_BLOCK;
291 /* Second branch must end with onlyjump, as we will eliminate the jump. */
292 if (!any_condjump_p (BB_END (e->src)))
295 if (!any_condjump_p (BB_END (b)) || !onlyjump_p (BB_END (b)))
297 b->flags |= BB_NONTHREADABLE_BLOCK;
301 set1 = pc_set (BB_END (e->src));
302 set2 = pc_set (BB_END (b));
303 if (((e->flags & EDGE_FALLTHRU) != 0)
304 != (XEXP (SET_SRC (set1), 1) == pc_rtx))
307 cond1 = XEXP (SET_SRC (set1), 0);
308 cond2 = XEXP (SET_SRC (set2), 0);
310 code1 = reversed_comparison_code (cond1, BB_END (e->src));
312 code1 = GET_CODE (cond1);
314 code2 = GET_CODE (cond2);
315 reversed_code2 = reversed_comparison_code (cond2, BB_END (b));
317 if (!comparison_dominates_p (code1, code2)
318 && !comparison_dominates_p (code1, reversed_code2))
321 /* Ensure that the comparison operators are equivalent.
322 ??? This is far too pessimistic. We should allow swapped operands,
323 different CCmodes, or for example comparisons for interval, that
324 dominate even when operands are not equivalent. */
325 if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
326 || !rtx_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
329 /* Short circuit cases where block B contains some side effects, as we can't
331 for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b));
332 insn = NEXT_INSN (insn))
333 if (INSN_P (insn) && side_effects_p (PATTERN (insn)))
335 b->flags |= BB_NONTHREADABLE_BLOCK;
341 /* First process all values computed in the source basic block. */
342 for (insn = NEXT_INSN (BB_HEAD (e->src));
343 insn != NEXT_INSN (BB_END (e->src));
344 insn = NEXT_INSN (insn))
346 cselib_process_insn (insn);
348 nonequal = BITMAP_ALLOC (NULL);
349 CLEAR_REG_SET (nonequal);
351 /* Now assume that we've continued by the edge E to B and continue
352 processing as if it were same basic block.
353 Our goal is to prove that whole block is an NOOP. */
355 for (insn = NEXT_INSN (BB_HEAD (b));
356 insn != NEXT_INSN (BB_END (b)) && !failed;
357 insn = NEXT_INSN (insn))
361 rtx pat = PATTERN (insn);
363 if (GET_CODE (pat) == PARALLEL)
365 for (i = 0; i < (unsigned)XVECLEN (pat, 0); i++)
366 failed |= mark_effect (XVECEXP (pat, 0, i), nonequal);
369 failed |= mark_effect (pat, nonequal);
372 cselib_process_insn (insn);
375 /* Later we should clear nonequal of dead registers. So far we don't
376 have life information in cfg_cleanup. */
379 b->flags |= BB_NONTHREADABLE_BLOCK;
383 /* cond2 must not mention any register that is not equal to the
385 if (for_each_rtx (&cond2, mentions_nonequal_regs, nonequal))
388 EXECUTE_IF_SET_IN_REG_SET (nonequal, 0, i, rsi)
391 BITMAP_FREE (nonequal);
393 if ((comparison_dominates_p (code1, code2) != 0)
394 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
395 return BRANCH_EDGE (b);
397 return FALLTHRU_EDGE (b);
400 BITMAP_FREE (nonequal);
405 /* Attempt to forward edges leaving basic block B.
406 Return true if successful. */
409 try_forward_edges (int mode, basic_block b)
411 bool changed = false;
413 edge e, *threaded_edges = NULL;
415 /* If we are partitioning hot/cold basic blocks, we don't want to
416 mess up unconditional or indirect jumps that cross between hot
419 Basic block partitioning may result in some jumps that appear to
420 be optimizable (or blocks that appear to be mergeable), but which really
421 must be left untouched (they are required to make it safely across
422 partition boundaries). See the comments at the top of
423 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
425 if (find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
428 for (ei = ei_start (b->succs); (e = ei_safe_edge (ei)); )
430 basic_block target, first;
431 int counter, goto_locus;
432 bool threaded = false;
433 int nthreaded_edges = 0;
434 bool may_thread = first_pass || (b->flags & BB_MODIFIED) != 0;
436 /* Skip complex edges because we don't know how to update them.
438 Still handle fallthru edges, as we can succeed to forward fallthru
439 edge to the same place as the branch edge of conditional branch
440 and turn conditional branch to an unconditional branch. */
441 if (e->flags & EDGE_COMPLEX)
447 target = first = e->dest;
448 counter = NUM_FIXED_BLOCKS;
449 goto_locus = e->goto_locus;
451 /* If we are partitioning hot/cold basic_blocks, we don't want to mess
452 up jumps that cross between hot/cold sections.
454 Basic block partitioning may result in some jumps that appear
455 to be optimizable (or blocks that appear to be mergeable), but which
456 really must be left untouched (they are required to make it safely
457 across partition boundaries). See the comments at the top of
458 bb-reorder.c:partition_hot_cold_basic_blocks for complete
461 if (first != EXIT_BLOCK_PTR
462 && find_reg_note (BB_END (first), REG_CROSSING_JUMP, NULL_RTX))
465 while (counter < n_basic_blocks)
467 basic_block new_target = NULL;
468 bool new_target_threaded = false;
469 may_thread |= (target->flags & BB_MODIFIED) != 0;
471 if (FORWARDER_BLOCK_P (target)
472 && !(single_succ_edge (target)->flags & EDGE_CROSSING)
473 && single_succ (target) != EXIT_BLOCK_PTR)
475 /* Bypass trivial infinite loops. */
476 new_target = single_succ (target);
477 if (target == new_target)
478 counter = n_basic_blocks;
481 /* When not optimizing, ensure that edges or forwarder
482 blocks with different locus are not optimized out. */
483 int new_locus = single_succ_edge (target)->goto_locus;
484 int locus = goto_locus;
486 if (new_locus && locus && !locator_eq (new_locus, locus))
495 last = BB_END (target);
496 if (DEBUG_INSN_P (last))
497 last = prev_nondebug_insn (last);
499 new_locus = last && INSN_P (last)
500 ? INSN_LOCATOR (last) : 0;
502 if (new_locus && locus && !locator_eq (new_locus, locus))
515 /* Allow to thread only over one edge at time to simplify updating
517 else if ((mode & CLEANUP_THREADING) && may_thread)
519 edge t = thread_jump (e, target);
523 threaded_edges = XNEWVEC (edge, n_basic_blocks);
528 /* Detect an infinite loop across blocks not
529 including the start block. */
530 for (i = 0; i < nthreaded_edges; ++i)
531 if (threaded_edges[i] == t)
533 if (i < nthreaded_edges)
535 counter = n_basic_blocks;
540 /* Detect an infinite loop across the start block. */
544 gcc_assert (nthreaded_edges < n_basic_blocks - NUM_FIXED_BLOCKS);
545 threaded_edges[nthreaded_edges++] = t;
547 new_target = t->dest;
548 new_target_threaded = true;
557 threaded |= new_target_threaded;
560 if (counter >= n_basic_blocks)
563 fprintf (dump_file, "Infinite loop in BB %i.\n",
566 else if (target == first)
567 ; /* We didn't do anything. */
570 /* Save the values now, as the edge may get removed. */
571 gcov_type edge_count = e->count;
572 int edge_probability = e->probability;
576 e->goto_locus = goto_locus;
578 /* Don't force if target is exit block. */
579 if (threaded && target != EXIT_BLOCK_PTR)
581 notice_new_block (redirect_edge_and_branch_force (e, target));
583 fprintf (dump_file, "Conditionals threaded.\n");
585 else if (!redirect_edge_and_branch (e, target))
589 "Forwarding edge %i->%i to %i failed.\n",
590 b->index, e->dest->index, target->index);
595 /* We successfully forwarded the edge. Now update profile
596 data: for each edge we traversed in the chain, remove
597 the original edge's execution count. */
598 edge_frequency = ((edge_probability * b->frequency
599 + REG_BR_PROB_BASE / 2)
606 if (!single_succ_p (first))
608 gcc_assert (n < nthreaded_edges);
609 t = threaded_edges [n++];
610 gcc_assert (t->src == first);
611 update_bb_profile_for_threading (first, edge_frequency,
613 update_br_prob_note (first);
617 first->count -= edge_count;
618 if (first->count < 0)
620 first->frequency -= edge_frequency;
621 if (first->frequency < 0)
622 first->frequency = 0;
623 /* It is possible that as the result of
624 threading we've removed edge as it is
625 threaded to the fallthru edge. Avoid
626 getting out of sync. */
627 if (n < nthreaded_edges
628 && first == threaded_edges [n]->src)
630 t = single_succ_edge (first);
633 t->count -= edge_count;
638 while (first != target);
646 free (threaded_edges);
651 /* Blocks A and B are to be merged into a single block. A has no incoming
652 fallthru edge, so it can be moved before B without adding or modifying
653 any jumps (aside from the jump from A to B). */
656 merge_blocks_move_predecessor_nojumps (basic_block a, basic_block b)
660 /* If we are partitioning hot/cold basic blocks, we don't want to
661 mess up unconditional or indirect jumps that cross between hot
664 Basic block partitioning may result in some jumps that appear to
665 be optimizable (or blocks that appear to be mergeable), but which really
666 must be left untouched (they are required to make it safely across
667 partition boundaries). See the comments at the top of
668 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
670 if (BB_PARTITION (a) != BB_PARTITION (b))
673 barrier = next_nonnote_insn (BB_END (a));
674 gcc_assert (BARRIER_P (barrier));
675 delete_insn (barrier);
677 /* Scramble the insn chain. */
678 if (BB_END (a) != PREV_INSN (BB_HEAD (b)))
679 reorder_insns_nobb (BB_HEAD (a), BB_END (a), PREV_INSN (BB_HEAD (b)));
683 fprintf (dump_file, "Moved block %d before %d and merged.\n",
686 /* Swap the records for the two blocks around. */
689 link_block (a, b->prev_bb);
691 /* Now blocks A and B are contiguous. Merge them. */
695 /* Blocks A and B are to be merged into a single block. B has no outgoing
696 fallthru edge, so it can be moved after A without adding or modifying
697 any jumps (aside from the jump from A to B). */
700 merge_blocks_move_successor_nojumps (basic_block a, basic_block b)
702 rtx barrier, real_b_end;
705 /* If we are partitioning hot/cold basic blocks, we don't want to
706 mess up unconditional or indirect jumps that cross between hot
709 Basic block partitioning may result in some jumps that appear to
710 be optimizable (or blocks that appear to be mergeable), but which really
711 must be left untouched (they are required to make it safely across
712 partition boundaries). See the comments at the top of
713 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
715 if (BB_PARTITION (a) != BB_PARTITION (b))
718 real_b_end = BB_END (b);
720 /* If there is a jump table following block B temporarily add the jump table
721 to block B so that it will also be moved to the correct location. */
722 if (tablejump_p (BB_END (b), &label, &table)
723 && prev_active_insn (label) == BB_END (b))
728 /* There had better have been a barrier there. Delete it. */
729 barrier = NEXT_INSN (BB_END (b));
730 if (barrier && BARRIER_P (barrier))
731 delete_insn (barrier);
734 /* Scramble the insn chain. */
735 reorder_insns_nobb (BB_HEAD (b), BB_END (b), BB_END (a));
737 /* Restore the real end of b. */
738 BB_END (b) = real_b_end;
741 fprintf (dump_file, "Moved block %d after %d and merged.\n",
744 /* Now blocks A and B are contiguous. Merge them. */
748 /* Attempt to merge basic blocks that are potentially non-adjacent.
749 Return NULL iff the attempt failed, otherwise return basic block
750 where cleanup_cfg should continue. Because the merging commonly
751 moves basic block away or introduces another optimization
752 possibility, return basic block just before B so cleanup_cfg don't
755 It may be good idea to return basic block before C in the case
756 C has been moved after B and originally appeared earlier in the
757 insn sequence, but we have no information available about the
758 relative ordering of these two. Hopefully it is not too common. */
761 merge_blocks_move (edge e, basic_block b, basic_block c, int mode)
765 /* If we are partitioning hot/cold basic blocks, we don't want to
766 mess up unconditional or indirect jumps that cross between hot
769 Basic block partitioning may result in some jumps that appear to
770 be optimizable (or blocks that appear to be mergeable), but which really
771 must be left untouched (they are required to make it safely across
772 partition boundaries). See the comments at the top of
773 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
775 if (BB_PARTITION (b) != BB_PARTITION (c))
778 /* If B has a fallthru edge to C, no need to move anything. */
779 if (e->flags & EDGE_FALLTHRU)
781 int b_index = b->index, c_index = c->index;
783 update_forwarder_flag (b);
786 fprintf (dump_file, "Merged %d and %d without moving.\n",
789 return b->prev_bb == ENTRY_BLOCK_PTR ? b : b->prev_bb;
792 /* Otherwise we will need to move code around. Do that only if expensive
793 transformations are allowed. */
794 else if (mode & CLEANUP_EXPENSIVE)
796 edge tmp_edge, b_fallthru_edge;
797 bool c_has_outgoing_fallthru;
798 bool b_has_incoming_fallthru;
800 /* Avoid overactive code motion, as the forwarder blocks should be
801 eliminated by edge redirection instead. One exception might have
802 been if B is a forwarder block and C has no fallthru edge, but
803 that should be cleaned up by bb-reorder instead. */
804 if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
807 /* We must make sure to not munge nesting of lexical blocks,
808 and loop notes. This is done by squeezing out all the notes
809 and leaving them there to lie. Not ideal, but functional. */
811 tmp_edge = find_fallthru_edge (c->succs);
812 c_has_outgoing_fallthru = (tmp_edge != NULL);
814 tmp_edge = find_fallthru_edge (b->preds);
815 b_has_incoming_fallthru = (tmp_edge != NULL);
816 b_fallthru_edge = tmp_edge;
819 next = next->prev_bb;
821 /* Otherwise, we're going to try to move C after B. If C does
822 not have an outgoing fallthru, then it can be moved
823 immediately after B without introducing or modifying jumps. */
824 if (! c_has_outgoing_fallthru)
826 merge_blocks_move_successor_nojumps (b, c);
827 return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
830 /* If B does not have an incoming fallthru, then it can be moved
831 immediately before C without introducing or modifying jumps.
832 C cannot be the first block, so we do not have to worry about
833 accessing a non-existent block. */
835 if (b_has_incoming_fallthru)
839 if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
841 bb = force_nonfallthru (b_fallthru_edge);
843 notice_new_block (bb);
846 merge_blocks_move_predecessor_nojumps (b, c);
847 return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
854 /* Removes the memory attributes of MEM expression
855 if they are not equal. */
858 merge_memattrs (rtx x, rtx y)
867 if (x == 0 || y == 0)
872 if (code != GET_CODE (y))
875 if (GET_MODE (x) != GET_MODE (y))
878 if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y))
882 else if (! MEM_ATTRS (y))
886 HOST_WIDE_INT mem_size;
888 if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
890 set_mem_alias_set (x, 0);
891 set_mem_alias_set (y, 0);
894 if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
898 clear_mem_offset (x);
899 clear_mem_offset (y);
901 else if (MEM_OFFSET_KNOWN_P (x) != MEM_OFFSET_KNOWN_P (y)
902 || (MEM_OFFSET_KNOWN_P (x)
903 && MEM_OFFSET (x) != MEM_OFFSET (y)))
905 clear_mem_offset (x);
906 clear_mem_offset (y);
909 if (MEM_SIZE_KNOWN_P (x) && MEM_SIZE_KNOWN_P (y))
911 mem_size = MAX (MEM_SIZE (x), MEM_SIZE (y));
912 set_mem_size (x, mem_size);
913 set_mem_size (y, mem_size);
921 set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
922 set_mem_align (y, MEM_ALIGN (x));
926 fmt = GET_RTX_FORMAT (code);
927 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
932 /* Two vectors must have the same length. */
933 if (XVECLEN (x, i) != XVECLEN (y, i))
936 for (j = 0; j < XVECLEN (x, i); j++)
937 merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
942 merge_memattrs (XEXP (x, i), XEXP (y, i));
949 /* Checks if patterns P1 and P2 are equivalent, apart from the possibly
950 different single sets S1 and S2. */
953 equal_different_set_p (rtx p1, rtx s1, rtx p2, rtx s2)
958 if (p1 == s1 && p2 == s2)
961 if (GET_CODE (p1) != PARALLEL || GET_CODE (p2) != PARALLEL)
964 if (XVECLEN (p1, 0) != XVECLEN (p2, 0))
967 for (i = 0; i < XVECLEN (p1, 0); i++)
969 e1 = XVECEXP (p1, 0, i);
970 e2 = XVECEXP (p2, 0, i);
971 if (e1 == s1 && e2 == s2)
974 ? rtx_renumbered_equal_p (e1, e2) : rtx_equal_p (e1, e2))
983 /* Examine register notes on I1 and I2 and return:
984 - dir_forward if I1 can be replaced by I2, or
985 - dir_backward if I2 can be replaced by I1, or
986 - dir_both if both are the case. */
988 static enum replace_direction
989 can_replace_by (rtx i1, rtx i2)
991 rtx s1, s2, d1, d2, src1, src2, note1, note2;
994 /* Check for 2 sets. */
995 s1 = single_set (i1);
996 s2 = single_set (i2);
997 if (s1 == NULL_RTX || s2 == NULL_RTX)
1000 /* Check that the 2 sets set the same dest. */
1003 if (!(reload_completed
1004 ? rtx_renumbered_equal_p (d1, d2) : rtx_equal_p (d1, d2)))
1007 /* Find identical req_equiv or reg_equal note, which implies that the 2 sets
1008 set dest to the same value. */
1009 note1 = find_reg_equal_equiv_note (i1);
1010 note2 = find_reg_equal_equiv_note (i2);
1011 if (!note1 || !note2 || !rtx_equal_p (XEXP (note1, 0), XEXP (note2, 0))
1012 || !CONST_INT_P (XEXP (note1, 0)))
1015 if (!equal_different_set_p (PATTERN (i1), s1, PATTERN (i2), s2))
1018 /* Although the 2 sets set dest to the same value, we cannot replace
1019 (set (dest) (const_int))
1022 because we don't know if the reg is live and has the same value at the
1023 location of replacement. */
1024 src1 = SET_SRC (s1);
1025 src2 = SET_SRC (s2);
1026 c1 = CONST_INT_P (src1);
1027 c2 = CONST_INT_P (src2);
1033 return dir_backward;
1038 /* Merges directions A and B. */
1040 static enum replace_direction
1041 merge_dir (enum replace_direction a, enum replace_direction b)
1043 /* Implements the following table:
1062 /* Examine I1 and I2 and return:
1063 - dir_forward if I1 can be replaced by I2, or
1064 - dir_backward if I2 can be replaced by I1, or
1065 - dir_both if both are the case. */
1067 static enum replace_direction
1068 old_insns_match_p (int mode ATTRIBUTE_UNUSED, rtx i1, rtx i2)
1072 /* Verify that I1 and I2 are equivalent. */
1073 if (GET_CODE (i1) != GET_CODE (i2))
1076 /* __builtin_unreachable() may lead to empty blocks (ending with
1077 NOTE_INSN_BASIC_BLOCK). They may be crossjumped. */
1078 if (NOTE_INSN_BASIC_BLOCK_P (i1) && NOTE_INSN_BASIC_BLOCK_P (i2))
1081 /* ??? Do not allow cross-jumping between different stack levels. */
1082 p1 = find_reg_note (i1, REG_ARGS_SIZE, NULL);
1083 p2 = find_reg_note (i2, REG_ARGS_SIZE, NULL);
1088 if (!rtx_equal_p (p1, p2))
1094 if (GET_CODE (p1) != GET_CODE (p2))
1097 /* If this is a CALL_INSN, compare register usage information.
1098 If we don't check this on stack register machines, the two
1099 CALL_INSNs might be merged leaving reg-stack.c with mismatching
1100 numbers of stack registers in the same basic block.
1101 If we don't check this on machines with delay slots, a delay slot may
1102 be filled that clobbers a parameter expected by the subroutine.
1104 ??? We take the simple route for now and assume that if they're
1105 equal, they were constructed identically.
1107 Also check for identical exception regions. */
1111 /* Ensure the same EH region. */
1112 rtx n1 = find_reg_note (i1, REG_EH_REGION, 0);
1113 rtx n2 = find_reg_note (i2, REG_EH_REGION, 0);
1118 if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
1121 if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
1122 CALL_INSN_FUNCTION_USAGE (i2))
1123 || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2))
1128 /* If cross_jump_death_matters is not 0, the insn's mode
1129 indicates whether or not the insn contains any stack-like
1132 if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
1134 /* If register stack conversion has already been done, then
1135 death notes must also be compared before it is certain that
1136 the two instruction streams match. */
1139 HARD_REG_SET i1_regset, i2_regset;
1141 CLEAR_HARD_REG_SET (i1_regset);
1142 CLEAR_HARD_REG_SET (i2_regset);
1144 for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
1145 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
1146 SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
1148 for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
1149 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
1150 SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
1152 if (!hard_reg_set_equal_p (i1_regset, i2_regset))
1157 if (reload_completed
1158 ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
1161 return can_replace_by (i1, i2);
1164 /* When comparing insns I1 and I2 in flow_find_cross_jump or
1165 flow_find_head_matching_sequence, ensure the notes match. */
1168 merge_notes (rtx i1, rtx i2)
1170 /* If the merged insns have different REG_EQUAL notes, then
1172 rtx equiv1 = find_reg_equal_equiv_note (i1);
1173 rtx equiv2 = find_reg_equal_equiv_note (i2);
1175 if (equiv1 && !equiv2)
1176 remove_note (i1, equiv1);
1177 else if (!equiv1 && equiv2)
1178 remove_note (i2, equiv2);
1179 else if (equiv1 && equiv2
1180 && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
1182 remove_note (i1, equiv1);
1183 remove_note (i2, equiv2);
1187 /* Walks from I1 in BB1 backward till the next non-debug insn, and returns the
1188 resulting insn in I1, and the corresponding bb in BB1. At the head of a
1189 bb, if there is a predecessor bb that reaches this bb via fallthru, and
1190 FOLLOW_FALLTHRU, walks further in the predecessor bb and registers this in
1191 DID_FALLTHRU. Otherwise, stops at the head of the bb. */
1194 walk_to_nondebug_insn (rtx *i1, basic_block *bb1, bool follow_fallthru,
1199 *did_fallthru = false;
1202 while (!NONDEBUG_INSN_P (*i1))
1204 if (*i1 != BB_HEAD (*bb1))
1206 *i1 = PREV_INSN (*i1);
1210 if (!follow_fallthru)
1213 fallthru = find_fallthru_edge ((*bb1)->preds);
1214 if (!fallthru || fallthru->src == ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun)
1215 || !single_succ_p (fallthru->src))
1218 *bb1 = fallthru->src;
1219 *i1 = BB_END (*bb1);
1220 *did_fallthru = true;
1224 /* Look through the insns at the end of BB1 and BB2 and find the longest
1225 sequence that are either equivalent, or allow forward or backward
1226 replacement. Store the first insns for that sequence in *F1 and *F2 and
1227 return the sequence length.
1229 DIR_P indicates the allowed replacement direction on function entry, and
1230 the actual replacement direction on function exit. If NULL, only equivalent
1231 sequences are allowed.
1233 To simplify callers of this function, if the blocks match exactly,
1234 store the head of the blocks in *F1 and *F2. */
1237 flow_find_cross_jump (basic_block bb1, basic_block bb2, rtx *f1, rtx *f2,
1238 enum replace_direction *dir_p)
1240 rtx i1, i2, last1, last2, afterlast1, afterlast2;
1243 enum replace_direction dir, last_dir, afterlast_dir;
1244 bool follow_fallthru, did_fallthru;
1250 afterlast_dir = dir;
1251 last_dir = afterlast_dir;
1253 /* Skip simple jumps at the end of the blocks. Complex jumps still
1254 need to be compared for equivalence, which we'll do below. */
1257 last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
1259 || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
1262 i1 = PREV_INSN (i1);
1267 || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
1270 /* Count everything except for unconditional jump as insn. */
1271 if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
1273 i2 = PREV_INSN (i2);
1278 /* In the following example, we can replace all jumps to C by jumps to A.
1280 This removes 4 duplicate insns.
1281 [bb A] insn1 [bb C] insn1
1287 We could also replace all jumps to A by jumps to C, but that leaves B
1288 alive, and removes only 2 duplicate insns. In a subsequent crossjump
1289 step, all jumps to B would be replaced with jumps to the middle of C,
1290 achieving the same result with more effort.
1291 So we allow only the first possibility, which means that we don't allow
1292 fallthru in the block that's being replaced. */
1294 follow_fallthru = dir_p && dir != dir_forward;
1295 walk_to_nondebug_insn (&i1, &bb1, follow_fallthru, &did_fallthru);
1299 follow_fallthru = dir_p && dir != dir_backward;
1300 walk_to_nondebug_insn (&i2, &bb2, follow_fallthru, &did_fallthru);
1304 if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
1307 dir = merge_dir (dir, old_insns_match_p (0, i1, i2));
1308 if (dir == dir_none || (!dir_p && dir != dir_both))
1311 merge_memattrs (i1, i2);
1313 /* Don't begin a cross-jump with a NOTE insn. */
1316 merge_notes (i1, i2);
1318 afterlast1 = last1, afterlast2 = last2;
1319 last1 = i1, last2 = i2;
1320 afterlast_dir = last_dir;
1323 if (!(GET_CODE (p1) == USE || GET_CODE (p1) == CLOBBER))
1327 i1 = PREV_INSN (i1);
1328 i2 = PREV_INSN (i2);
1332 /* Don't allow the insn after a compare to be shared by
1333 cross-jumping unless the compare is also shared. */
1334 if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
1335 last1 = afterlast1, last2 = afterlast2, last_dir = afterlast_dir, ninsns--;
1338 /* Include preceding notes and labels in the cross-jump. One,
1339 this may bring us to the head of the blocks as requested above.
1340 Two, it keeps line number notes as matched as may be. */
1343 bb1 = BLOCK_FOR_INSN (last1);
1344 while (last1 != BB_HEAD (bb1) && !NONDEBUG_INSN_P (PREV_INSN (last1)))
1345 last1 = PREV_INSN (last1);
1347 if (last1 != BB_HEAD (bb1) && LABEL_P (PREV_INSN (last1)))
1348 last1 = PREV_INSN (last1);
1350 bb2 = BLOCK_FOR_INSN (last2);
1351 while (last2 != BB_HEAD (bb2) && !NONDEBUG_INSN_P (PREV_INSN (last2)))
1352 last2 = PREV_INSN (last2);
1354 if (last2 != BB_HEAD (bb2) && LABEL_P (PREV_INSN (last2)))
1355 last2 = PREV_INSN (last2);
1366 /* Like flow_find_cross_jump, except start looking for a matching sequence from
1367 the head of the two blocks. Do not include jumps at the end.
1368 If STOP_AFTER is nonzero, stop after finding that many matching
1372 flow_find_head_matching_sequence (basic_block bb1, basic_block bb2, rtx *f1,
1373 rtx *f2, int stop_after)
1375 rtx i1, i2, last1, last2, beforelast1, beforelast2;
1379 int nehedges1 = 0, nehedges2 = 0;
1381 FOR_EACH_EDGE (e, ei, bb1->succs)
1382 if (e->flags & EDGE_EH)
1384 FOR_EACH_EDGE (e, ei, bb2->succs)
1385 if (e->flags & EDGE_EH)
1390 last1 = beforelast1 = last2 = beforelast2 = NULL_RTX;
1394 /* Ignore notes, except NOTE_INSN_EPILOGUE_BEG. */
1395 while (!NONDEBUG_INSN_P (i1) && i1 != BB_END (bb1))
1397 if (NOTE_P (i1) && NOTE_KIND (i1) == NOTE_INSN_EPILOGUE_BEG)
1399 i1 = NEXT_INSN (i1);
1402 while (!NONDEBUG_INSN_P (i2) && i2 != BB_END (bb2))
1404 if (NOTE_P (i2) && NOTE_KIND (i2) == NOTE_INSN_EPILOGUE_BEG)
1406 i2 = NEXT_INSN (i2);
1409 if ((i1 == BB_END (bb1) && !NONDEBUG_INSN_P (i1))
1410 || (i2 == BB_END (bb2) && !NONDEBUG_INSN_P (i2)))
1413 if (NOTE_P (i1) || NOTE_P (i2)
1414 || JUMP_P (i1) || JUMP_P (i2))
1417 /* A sanity check to make sure we're not merging insns with different
1418 effects on EH. If only one of them ends a basic block, it shouldn't
1419 have an EH edge; if both end a basic block, there should be the same
1420 number of EH edges. */
1421 if ((i1 == BB_END (bb1) && i2 != BB_END (bb2)
1423 || (i2 == BB_END (bb2) && i1 != BB_END (bb1)
1425 || (i1 == BB_END (bb1) && i2 == BB_END (bb2)
1426 && nehedges1 != nehedges2))
1429 if (old_insns_match_p (0, i1, i2) != dir_both)
1432 merge_memattrs (i1, i2);
1434 /* Don't begin a cross-jump with a NOTE insn. */
1437 merge_notes (i1, i2);
1439 beforelast1 = last1, beforelast2 = last2;
1440 last1 = i1, last2 = i2;
1444 if (i1 == BB_END (bb1) || i2 == BB_END (bb2)
1445 || (stop_after > 0 && ninsns == stop_after))
1448 i1 = NEXT_INSN (i1);
1449 i2 = NEXT_INSN (i2);
1453 /* Don't allow a compare to be shared by cross-jumping unless the insn
1454 after the compare is also shared. */
1455 if (ninsns && reg_mentioned_p (cc0_rtx, last1) && sets_cc0_p (last1))
1456 last1 = beforelast1, last2 = beforelast2, ninsns--;
1468 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1469 the branch instruction. This means that if we commonize the control
1470 flow before end of the basic block, the semantic remains unchanged.
1472 We may assume that there exists one edge with a common destination. */
1475 outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
1477 int nehedges1 = 0, nehedges2 = 0;
1478 edge fallthru1 = 0, fallthru2 = 0;
1482 /* If BB1 has only one successor, we may be looking at either an
1483 unconditional jump, or a fake edge to exit. */
1484 if (single_succ_p (bb1)
1485 && (single_succ_edge (bb1)->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1486 && (!JUMP_P (BB_END (bb1)) || simplejump_p (BB_END (bb1))))
1487 return (single_succ_p (bb2)
1488 && (single_succ_edge (bb2)->flags
1489 & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1490 && (!JUMP_P (BB_END (bb2)) || simplejump_p (BB_END (bb2))));
1492 /* Match conditional jumps - this may get tricky when fallthru and branch
1493 edges are crossed. */
1494 if (EDGE_COUNT (bb1->succs) == 2
1495 && any_condjump_p (BB_END (bb1))
1496 && onlyjump_p (BB_END (bb1)))
1498 edge b1, f1, b2, f2;
1499 bool reverse, match;
1500 rtx set1, set2, cond1, cond2;
1501 enum rtx_code code1, code2;
1503 if (EDGE_COUNT (bb2->succs) != 2
1504 || !any_condjump_p (BB_END (bb2))
1505 || !onlyjump_p (BB_END (bb2)))
1508 b1 = BRANCH_EDGE (bb1);
1509 b2 = BRANCH_EDGE (bb2);
1510 f1 = FALLTHRU_EDGE (bb1);
1511 f2 = FALLTHRU_EDGE (bb2);
1513 /* Get around possible forwarders on fallthru edges. Other cases
1514 should be optimized out already. */
1515 if (FORWARDER_BLOCK_P (f1->dest))
1516 f1 = single_succ_edge (f1->dest);
1518 if (FORWARDER_BLOCK_P (f2->dest))
1519 f2 = single_succ_edge (f2->dest);
1521 /* To simplify use of this function, return false if there are
1522 unneeded forwarder blocks. These will get eliminated later
1523 during cleanup_cfg. */
1524 if (FORWARDER_BLOCK_P (f1->dest)
1525 || FORWARDER_BLOCK_P (f2->dest)
1526 || FORWARDER_BLOCK_P (b1->dest)
1527 || FORWARDER_BLOCK_P (b2->dest))
1530 if (f1->dest == f2->dest && b1->dest == b2->dest)
1532 else if (f1->dest == b2->dest && b1->dest == f2->dest)
1537 set1 = pc_set (BB_END (bb1));
1538 set2 = pc_set (BB_END (bb2));
1539 if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
1540 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
1543 cond1 = XEXP (SET_SRC (set1), 0);
1544 cond2 = XEXP (SET_SRC (set2), 0);
1545 code1 = GET_CODE (cond1);
1547 code2 = reversed_comparison_code (cond2, BB_END (bb2));
1549 code2 = GET_CODE (cond2);
1551 if (code2 == UNKNOWN)
1554 /* Verify codes and operands match. */
1555 match = ((code1 == code2
1556 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
1557 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
1558 || (code1 == swap_condition (code2)
1559 && rtx_renumbered_equal_p (XEXP (cond1, 1),
1561 && rtx_renumbered_equal_p (XEXP (cond1, 0),
1564 /* If we return true, we will join the blocks. Which means that
1565 we will only have one branch prediction bit to work with. Thus
1566 we require the existing branches to have probabilities that are
1569 && optimize_bb_for_speed_p (bb1)
1570 && optimize_bb_for_speed_p (bb2))
1574 if (b1->dest == b2->dest)
1575 prob2 = b2->probability;
1577 /* Do not use f2 probability as f2 may be forwarded. */
1578 prob2 = REG_BR_PROB_BASE - b2->probability;
1580 /* Fail if the difference in probabilities is greater than 50%.
1581 This rules out two well-predicted branches with opposite
1583 if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
1587 "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
1588 bb1->index, bb2->index, b1->probability, prob2);
1594 if (dump_file && match)
1595 fprintf (dump_file, "Conditionals in bb %i and %i match.\n",
1596 bb1->index, bb2->index);
1601 /* Generic case - we are seeing a computed jump, table jump or trapping
1604 /* Check whether there are tablejumps in the end of BB1 and BB2.
1605 Return true if they are identical. */
1610 if (tablejump_p (BB_END (bb1), &label1, &table1)
1611 && tablejump_p (BB_END (bb2), &label2, &table2)
1612 && GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2)))
1614 /* The labels should never be the same rtx. If they really are same
1615 the jump tables are same too. So disable crossjumping of blocks BB1
1616 and BB2 because when deleting the common insns in the end of BB1
1617 by delete_basic_block () the jump table would be deleted too. */
1618 /* If LABEL2 is referenced in BB1->END do not do anything
1619 because we would loose information when replacing
1620 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1621 if (label1 != label2 && !rtx_referenced_p (label2, BB_END (bb1)))
1623 /* Set IDENTICAL to true when the tables are identical. */
1624 bool identical = false;
1627 p1 = PATTERN (table1);
1628 p2 = PATTERN (table2);
1629 if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2))
1633 else if (GET_CODE (p1) == ADDR_DIFF_VEC
1634 && (XVECLEN (p1, 1) == XVECLEN (p2, 1))
1635 && rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2))
1636 && rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3)))
1641 for (i = XVECLEN (p1, 1) - 1; i >= 0 && identical; i--)
1642 if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i)))
1648 replace_label_data rr;
1651 /* Temporarily replace references to LABEL1 with LABEL2
1652 in BB1->END so that we could compare the instructions. */
1655 rr.update_label_nuses = false;
1656 for_each_rtx (&BB_END (bb1), replace_label, &rr);
1658 match = (old_insns_match_p (mode, BB_END (bb1), BB_END (bb2))
1660 if (dump_file && match)
1662 "Tablejumps in bb %i and %i match.\n",
1663 bb1->index, bb2->index);
1665 /* Set the original label in BB1->END because when deleting
1666 a block whose end is a tablejump, the tablejump referenced
1667 from the instruction is deleted too. */
1670 for_each_rtx (&BB_END (bb1), replace_label, &rr);
1679 /* First ensure that the instructions match. There may be many outgoing
1680 edges so this test is generally cheaper. */
1681 if (old_insns_match_p (mode, BB_END (bb1), BB_END (bb2)) != dir_both)
1684 /* Search the outgoing edges, ensure that the counts do match, find possible
1685 fallthru and exception handling edges since these needs more
1687 if (EDGE_COUNT (bb1->succs) != EDGE_COUNT (bb2->succs))
1690 FOR_EACH_EDGE (e1, ei, bb1->succs)
1692 e2 = EDGE_SUCC (bb2, ei.index);
1694 if (e1->flags & EDGE_EH)
1697 if (e2->flags & EDGE_EH)
1700 if (e1->flags & EDGE_FALLTHRU)
1702 if (e2->flags & EDGE_FALLTHRU)
1706 /* If number of edges of various types does not match, fail. */
1707 if (nehedges1 != nehedges2
1708 || (fallthru1 != 0) != (fallthru2 != 0))
1711 /* fallthru edges must be forwarded to the same destination. */
1714 basic_block d1 = (forwarder_block_p (fallthru1->dest)
1715 ? single_succ (fallthru1->dest): fallthru1->dest);
1716 basic_block d2 = (forwarder_block_p (fallthru2->dest)
1717 ? single_succ (fallthru2->dest): fallthru2->dest);
1723 /* Ensure the same EH region. */
1725 rtx n1 = find_reg_note (BB_END (bb1), REG_EH_REGION, 0);
1726 rtx n2 = find_reg_note (BB_END (bb2), REG_EH_REGION, 0);
1731 if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
1735 /* The same checks as in try_crossjump_to_edge. It is required for RTL
1736 version of sequence abstraction. */
1737 FOR_EACH_EDGE (e1, ei, bb2->succs)
1741 basic_block d1 = e1->dest;
1743 if (FORWARDER_BLOCK_P (d1))
1744 d1 = EDGE_SUCC (d1, 0)->dest;
1746 FOR_EACH_EDGE (e2, ei, bb1->succs)
1748 basic_block d2 = e2->dest;
1749 if (FORWARDER_BLOCK_P (d2))
1750 d2 = EDGE_SUCC (d2, 0)->dest;
1762 /* Returns true if BB basic block has a preserve label. */
1765 block_has_preserve_label (basic_block bb)
1769 && LABEL_PRESERVE_P (block_label (bb)));
1772 /* E1 and E2 are edges with the same destination block. Search their
1773 predecessors for common code. If found, redirect control flow from
1774 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC (dir_forward),
1775 or the other way around (dir_backward). DIR specifies the allowed
1776 replacement direction. */
1779 try_crossjump_to_edge (int mode, edge e1, edge e2,
1780 enum replace_direction dir)
1783 basic_block src1 = e1->src, src2 = e2->src;
1784 basic_block redirect_to, redirect_from, to_remove;
1785 basic_block osrc1, osrc2, redirect_edges_to, tmp;
1786 rtx newpos1, newpos2;
1790 newpos1 = newpos2 = NULL_RTX;
1792 /* If we have partitioned hot/cold basic blocks, it is a bad idea
1793 to try this optimization.
1795 Basic block partitioning may result in some jumps that appear to
1796 be optimizable (or blocks that appear to be mergeable), but which really
1797 must be left untouched (they are required to make it safely across
1798 partition boundaries). See the comments at the top of
1799 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1801 if (flag_reorder_blocks_and_partition && reload_completed)
1804 /* Search backward through forwarder blocks. We don't need to worry
1805 about multiple entry or chained forwarders, as they will be optimized
1806 away. We do this to look past the unconditional jump following a
1807 conditional jump that is required due to the current CFG shape. */
1808 if (single_pred_p (src1)
1809 && FORWARDER_BLOCK_P (src1))
1810 e1 = single_pred_edge (src1), src1 = e1->src;
1812 if (single_pred_p (src2)
1813 && FORWARDER_BLOCK_P (src2))
1814 e2 = single_pred_edge (src2), src2 = e2->src;
1816 /* Nothing to do if we reach ENTRY, or a common source block. */
1817 if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
1822 /* Seeing more than 1 forwarder blocks would confuse us later... */
1823 if (FORWARDER_BLOCK_P (e1->dest)
1824 && FORWARDER_BLOCK_P (single_succ (e1->dest)))
1827 if (FORWARDER_BLOCK_P (e2->dest)
1828 && FORWARDER_BLOCK_P (single_succ (e2->dest)))
1831 /* Likewise with dead code (possibly newly created by the other optimizations
1833 if (EDGE_COUNT (src1->preds) == 0 || EDGE_COUNT (src2->preds) == 0)
1836 /* Look for the common insn sequence, part the first ... */
1837 if (!outgoing_edges_match (mode, src1, src2))
1840 /* ... and part the second. */
1841 nmatch = flow_find_cross_jump (src1, src2, &newpos1, &newpos2, &dir);
1845 if (newpos1 != NULL_RTX)
1846 src1 = BLOCK_FOR_INSN (newpos1);
1847 if (newpos2 != NULL_RTX)
1848 src2 = BLOCK_FOR_INSN (newpos2);
1850 if (dir == dir_backward)
1852 #define SWAP(T, X, Y) do { T tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
1853 SWAP (basic_block, osrc1, osrc2);
1854 SWAP (basic_block, src1, src2);
1855 SWAP (edge, e1, e2);
1856 SWAP (rtx, newpos1, newpos2);
1860 /* Don't proceed with the crossjump unless we found a sufficient number
1861 of matching instructions or the 'from' block was totally matched
1862 (such that its predecessors will hopefully be redirected and the
1864 if ((nmatch < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
1865 && (newpos1 != BB_HEAD (src1)))
1868 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */
1869 if (block_has_preserve_label (e1->dest)
1870 && (e1->flags & EDGE_ABNORMAL))
1873 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1875 If we have tablejumps in the end of SRC1 and SRC2
1876 they have been already compared for equivalence in outgoing_edges_match ()
1877 so replace the references to TABLE1 by references to TABLE2. */
1882 if (tablejump_p (BB_END (osrc1), &label1, &table1)
1883 && tablejump_p (BB_END (osrc2), &label2, &table2)
1884 && label1 != label2)
1886 replace_label_data rr;
1889 /* Replace references to LABEL1 with LABEL2. */
1892 rr.update_label_nuses = true;
1893 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1895 /* Do not replace the label in SRC1->END because when deleting
1896 a block whose end is a tablejump, the tablejump referenced
1897 from the instruction is deleted too. */
1898 if (insn != BB_END (osrc1))
1899 for_each_rtx (&insn, replace_label, &rr);
1904 /* Avoid splitting if possible. We must always split when SRC2 has
1905 EH predecessor edges, or we may end up with basic blocks with both
1906 normal and EH predecessor edges. */
1907 if (newpos2 == BB_HEAD (src2)
1908 && !(EDGE_PRED (src2, 0)->flags & EDGE_EH))
1912 if (newpos2 == BB_HEAD (src2))
1914 /* Skip possible basic block header. */
1915 if (LABEL_P (newpos2))
1916 newpos2 = NEXT_INSN (newpos2);
1917 while (DEBUG_INSN_P (newpos2))
1918 newpos2 = NEXT_INSN (newpos2);
1919 if (NOTE_P (newpos2))
1920 newpos2 = NEXT_INSN (newpos2);
1921 while (DEBUG_INSN_P (newpos2))
1922 newpos2 = NEXT_INSN (newpos2);
1926 fprintf (dump_file, "Splitting bb %i before %i insns\n",
1927 src2->index, nmatch);
1928 redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
1933 "Cross jumping from bb %i to bb %i; %i common insns\n",
1934 src1->index, src2->index, nmatch);
1936 /* We may have some registers visible through the block. */
1937 df_set_bb_dirty (redirect_to);
1940 redirect_edges_to = redirect_to;
1942 redirect_edges_to = osrc2;
1944 /* Recompute the frequencies and counts of outgoing edges. */
1945 FOR_EACH_EDGE (s, ei, redirect_edges_to->succs)
1949 basic_block d = s->dest;
1951 if (FORWARDER_BLOCK_P (d))
1952 d = single_succ (d);
1954 FOR_EACH_EDGE (s2, ei, src1->succs)
1956 basic_block d2 = s2->dest;
1957 if (FORWARDER_BLOCK_P (d2))
1958 d2 = single_succ (d2);
1963 s->count += s2->count;
1965 /* Take care to update possible forwarder blocks. We verified
1966 that there is no more than one in the chain, so we can't run
1967 into infinite loop. */
1968 if (FORWARDER_BLOCK_P (s->dest))
1970 single_succ_edge (s->dest)->count += s2->count;
1971 s->dest->count += s2->count;
1972 s->dest->frequency += EDGE_FREQUENCY (s);
1975 if (FORWARDER_BLOCK_P (s2->dest))
1977 single_succ_edge (s2->dest)->count -= s2->count;
1978 if (single_succ_edge (s2->dest)->count < 0)
1979 single_succ_edge (s2->dest)->count = 0;
1980 s2->dest->count -= s2->count;
1981 s2->dest->frequency -= EDGE_FREQUENCY (s);
1982 if (s2->dest->frequency < 0)
1983 s2->dest->frequency = 0;
1984 if (s2->dest->count < 0)
1985 s2->dest->count = 0;
1988 if (!redirect_edges_to->frequency && !src1->frequency)
1989 s->probability = (s->probability + s2->probability) / 2;
1992 = ((s->probability * redirect_edges_to->frequency +
1993 s2->probability * src1->frequency)
1994 / (redirect_edges_to->frequency + src1->frequency));
1997 /* Adjust count and frequency for the block. An earlier jump
1998 threading pass may have left the profile in an inconsistent
1999 state (see update_bb_profile_for_threading) so we must be
2000 prepared for overflows. */
2004 tmp->count += src1->count;
2005 tmp->frequency += src1->frequency;
2006 if (tmp->frequency > BB_FREQ_MAX)
2007 tmp->frequency = BB_FREQ_MAX;
2008 if (tmp == redirect_edges_to)
2010 tmp = find_fallthru_edge (tmp->succs)->dest;
2013 update_br_prob_note (redirect_edges_to);
2015 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
2017 /* Skip possible basic block header. */
2018 if (LABEL_P (newpos1))
2019 newpos1 = NEXT_INSN (newpos1);
2021 while (DEBUG_INSN_P (newpos1))
2022 newpos1 = NEXT_INSN (newpos1);
2024 if (NOTE_INSN_BASIC_BLOCK_P (newpos1))
2025 newpos1 = NEXT_INSN (newpos1);
2027 while (DEBUG_INSN_P (newpos1))
2028 newpos1 = NEXT_INSN (newpos1);
2030 redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
2031 to_remove = single_succ (redirect_from);
2033 redirect_edge_and_branch_force (single_succ_edge (redirect_from), redirect_to);
2034 delete_basic_block (to_remove);
2036 update_forwarder_flag (redirect_from);
2037 if (redirect_to != src2)
2038 update_forwarder_flag (src2);
2043 /* Search the predecessors of BB for common insn sequences. When found,
2044 share code between them by redirecting control flow. Return true if
2045 any changes made. */
2048 try_crossjump_bb (int mode, basic_block bb)
2050 edge e, e2, fallthru;
2052 unsigned max, ix, ix2;
2054 /* Nothing to do if there is not at least two incoming edges. */
2055 if (EDGE_COUNT (bb->preds) < 2)
2058 /* Don't crossjump if this block ends in a computed jump,
2059 unless we are optimizing for size. */
2060 if (optimize_bb_for_size_p (bb)
2061 && bb != EXIT_BLOCK_PTR
2062 && computed_jump_p (BB_END (bb)))
2065 /* If we are partitioning hot/cold basic blocks, we don't want to
2066 mess up unconditional or indirect jumps that cross between hot
2069 Basic block partitioning may result in some jumps that appear to
2070 be optimizable (or blocks that appear to be mergeable), but which really
2071 must be left untouched (they are required to make it safely across
2072 partition boundaries). See the comments at the top of
2073 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
2075 if (BB_PARTITION (EDGE_PRED (bb, 0)->src) !=
2076 BB_PARTITION (EDGE_PRED (bb, 1)->src)
2077 || (EDGE_PRED (bb, 0)->flags & EDGE_CROSSING))
2080 /* It is always cheapest to redirect a block that ends in a branch to
2081 a block that falls through into BB, as that adds no branches to the
2082 program. We'll try that combination first. */
2084 max = PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES);
2086 if (EDGE_COUNT (bb->preds) > max)
2089 fallthru = find_fallthru_edge (bb->preds);
2092 for (ix = 0; ix < EDGE_COUNT (bb->preds);)
2094 e = EDGE_PRED (bb, ix);
2097 /* As noted above, first try with the fallthru predecessor (or, a
2098 fallthru predecessor if we are in cfglayout mode). */
2101 /* Don't combine the fallthru edge into anything else.
2102 If there is a match, we'll do it the other way around. */
2105 /* If nothing changed since the last attempt, there is nothing
2108 && !((e->src->flags & BB_MODIFIED)
2109 || (fallthru->src->flags & BB_MODIFIED)))
2112 if (try_crossjump_to_edge (mode, e, fallthru, dir_forward))
2120 /* Non-obvious work limiting check: Recognize that we're going
2121 to call try_crossjump_bb on every basic block. So if we have
2122 two blocks with lots of outgoing edges (a switch) and they
2123 share lots of common destinations, then we would do the
2124 cross-jump check once for each common destination.
2126 Now, if the blocks actually are cross-jump candidates, then
2127 all of their destinations will be shared. Which means that
2128 we only need check them for cross-jump candidacy once. We
2129 can eliminate redundant checks of crossjump(A,B) by arbitrarily
2130 choosing to do the check from the block for which the edge
2131 in question is the first successor of A. */
2132 if (EDGE_SUCC (e->src, 0) != e)
2135 for (ix2 = 0; ix2 < EDGE_COUNT (bb->preds); ix2++)
2137 e2 = EDGE_PRED (bb, ix2);
2142 /* We've already checked the fallthru edge above. */
2146 /* The "first successor" check above only prevents multiple
2147 checks of crossjump(A,B). In order to prevent redundant
2148 checks of crossjump(B,A), require that A be the block
2149 with the lowest index. */
2150 if (e->src->index > e2->src->index)
2153 /* If nothing changed since the last attempt, there is nothing
2156 && !((e->src->flags & BB_MODIFIED)
2157 || (e2->src->flags & BB_MODIFIED)))
2160 /* Both e and e2 are not fallthru edges, so we can crossjump in either
2162 if (try_crossjump_to_edge (mode, e, e2, dir_both))
2172 crossjumps_occured = true;
2177 /* Search the successors of BB for common insn sequences. When found,
2178 share code between them by moving it across the basic block
2179 boundary. Return true if any changes made. */
2182 try_head_merge_bb (basic_block bb)
2184 basic_block final_dest_bb = NULL;
2185 int max_match = INT_MAX;
2187 rtx *headptr, *currptr, *nextptr;
2188 bool changed, moveall;
2190 rtx e0_last_head, cond, move_before;
2191 unsigned nedges = EDGE_COUNT (bb->succs);
2192 rtx jump = BB_END (bb);
2193 regset live, live_union;
2195 /* Nothing to do if there is not at least two outgoing edges. */
2199 /* Don't crossjump if this block ends in a computed jump,
2200 unless we are optimizing for size. */
2201 if (optimize_bb_for_size_p (bb)
2202 && bb != EXIT_BLOCK_PTR
2203 && computed_jump_p (BB_END (bb)))
2206 cond = get_condition (jump, &move_before, true, false);
2207 if (cond == NULL_RTX)
2210 for (ix = 0; ix < nedges; ix++)
2211 if (EDGE_SUCC (bb, ix)->dest == EXIT_BLOCK_PTR)
2214 for (ix = 0; ix < nedges; ix++)
2216 edge e = EDGE_SUCC (bb, ix);
2217 basic_block other_bb = e->dest;
2219 if (df_get_bb_dirty (other_bb))
2221 block_was_dirty = true;
2225 if (e->flags & EDGE_ABNORMAL)
2228 /* Normally, all destination blocks must only be reachable from this
2229 block, i.e. they must have one incoming edge.
2231 There is one special case we can handle, that of multiple consecutive
2232 jumps where the first jumps to one of the targets of the second jump.
2233 This happens frequently in switch statements for default labels.
2234 The structure is as follows:
2240 jump with targets A, B, C, D...
2242 has two incoming edges, from FINAL_DEST_BB and BB
2244 In this case, we can try to move the insns through BB and into
2246 if (EDGE_COUNT (other_bb->preds) != 1)
2248 edge incoming_edge, incoming_bb_other_edge;
2251 if (final_dest_bb != NULL
2252 || EDGE_COUNT (other_bb->preds) != 2)
2255 /* We must be able to move the insns across the whole block. */
2256 move_before = BB_HEAD (bb);
2257 while (!NONDEBUG_INSN_P (move_before))
2258 move_before = NEXT_INSN (move_before);
2260 if (EDGE_COUNT (bb->preds) != 1)
2262 incoming_edge = EDGE_PRED (bb, 0);
2263 final_dest_bb = incoming_edge->src;
2264 if (EDGE_COUNT (final_dest_bb->succs) != 2)
2266 FOR_EACH_EDGE (incoming_bb_other_edge, ei, final_dest_bb->succs)
2267 if (incoming_bb_other_edge != incoming_edge)
2269 if (incoming_bb_other_edge->dest != other_bb)
2274 e0 = EDGE_SUCC (bb, 0);
2275 e0_last_head = NULL_RTX;
2278 for (ix = 1; ix < nedges; ix++)
2280 edge e = EDGE_SUCC (bb, ix);
2281 rtx e0_last, e_last;
2284 nmatch = flow_find_head_matching_sequence (e0->dest, e->dest,
2285 &e0_last, &e_last, 0);
2289 if (nmatch < max_match)
2292 e0_last_head = e0_last;
2296 /* If we matched an entire block, we probably have to avoid moving the
2299 && e0_last_head == BB_END (e0->dest)
2300 && (find_reg_note (e0_last_head, REG_EH_REGION, 0)
2301 || control_flow_insn_p (e0_last_head)))
2307 e0_last_head = prev_real_insn (e0_last_head);
2308 while (DEBUG_INSN_P (e0_last_head));
2314 /* We must find a union of the live registers at each of the end points. */
2315 live = BITMAP_ALLOC (NULL);
2316 live_union = BITMAP_ALLOC (NULL);
2318 currptr = XNEWVEC (rtx, nedges);
2319 headptr = XNEWVEC (rtx, nedges);
2320 nextptr = XNEWVEC (rtx, nedges);
2322 for (ix = 0; ix < nedges; ix++)
2325 basic_block merge_bb = EDGE_SUCC (bb, ix)->dest;
2326 rtx head = BB_HEAD (merge_bb);
2328 while (!NONDEBUG_INSN_P (head))
2329 head = NEXT_INSN (head);
2333 /* Compute the end point and live information */
2334 for (j = 1; j < max_match; j++)
2336 head = NEXT_INSN (head);
2337 while (!NONDEBUG_INSN_P (head));
2338 simulate_backwards_to_point (merge_bb, live, head);
2339 IOR_REG_SET (live_union, live);
2342 /* If we're moving across two blocks, verify the validity of the
2343 first move, then adjust the target and let the loop below deal
2344 with the final move. */
2345 if (final_dest_bb != NULL)
2349 moveall = can_move_insns_across (currptr[0], e0_last_head, move_before,
2350 jump, e0->dest, live_union,
2354 if (move_upto == NULL_RTX)
2357 while (e0_last_head != move_upto)
2359 df_simulate_one_insn_backwards (e0->dest, e0_last_head,
2361 e0_last_head = PREV_INSN (e0_last_head);
2364 if (e0_last_head == NULL_RTX)
2367 jump = BB_END (final_dest_bb);
2368 cond = get_condition (jump, &move_before, true, false);
2369 if (cond == NULL_RTX)
2376 moveall = can_move_insns_across (currptr[0], e0_last_head,
2377 move_before, jump, e0->dest, live_union,
2379 if (!moveall && move_upto == NULL_RTX)
2381 if (jump == move_before)
2384 /* Try again, using a different insertion point. */
2388 /* Don't try moving before a cc0 user, as that may invalidate
2390 if (reg_mentioned_p (cc0_rtx, jump))
2397 if (final_dest_bb && !moveall)
2398 /* We haven't checked whether a partial move would be OK for the first
2399 move, so we have to fail this case. */
2405 if (currptr[0] == move_upto)
2407 for (ix = 0; ix < nedges; ix++)
2409 rtx curr = currptr[ix];
2411 curr = NEXT_INSN (curr);
2412 while (!NONDEBUG_INSN_P (curr));
2417 /* If we can't currently move all of the identical insns, remember
2418 each insn after the range that we'll merge. */
2420 for (ix = 0; ix < nedges; ix++)
2422 rtx curr = currptr[ix];
2424 curr = NEXT_INSN (curr);
2425 while (!NONDEBUG_INSN_P (curr));
2429 reorder_insns (headptr[0], currptr[0], PREV_INSN (move_before));
2430 df_set_bb_dirty (EDGE_SUCC (bb, 0)->dest);
2431 if (final_dest_bb != NULL)
2432 df_set_bb_dirty (final_dest_bb);
2433 df_set_bb_dirty (bb);
2434 for (ix = 1; ix < nedges; ix++)
2436 df_set_bb_dirty (EDGE_SUCC (bb, ix)->dest);
2437 delete_insn_chain (headptr[ix], currptr[ix], false);
2441 if (jump == move_before)
2444 /* For the unmerged insns, try a different insertion point. */
2448 /* Don't try moving before a cc0 user, as that may invalidate
2450 if (reg_mentioned_p (cc0_rtx, jump))
2454 for (ix = 0; ix < nedges; ix++)
2455 currptr[ix] = headptr[ix] = nextptr[ix];
2465 crossjumps_occured |= changed;
2470 /* Return true if BB contains just bb note, or bb note followed
2471 by only DEBUG_INSNs. */
2474 trivially_empty_bb_p (basic_block bb)
2476 rtx insn = BB_END (bb);
2480 if (insn == BB_HEAD (bb))
2482 if (!DEBUG_INSN_P (insn))
2484 insn = PREV_INSN (insn);
2488 /* Do simple CFG optimizations - basic block merging, simplifying of jump
2489 instructions etc. Return nonzero if changes were made. */
2492 try_optimize_cfg (int mode)
2494 bool changed_overall = false;
2497 basic_block bb, b, next;
2499 if (mode & (CLEANUP_CROSSJUMP | CLEANUP_THREADING))
2502 crossjumps_occured = false;
2505 update_forwarder_flag (bb);
2507 if (! targetm.cannot_modify_jumps_p ())
2510 /* Attempt to merge blocks as made possible by edge removal. If
2511 a block has only one successor, and the successor has only
2512 one predecessor, they may be combined. */
2515 block_was_dirty = false;
2521 "\n\ntry_optimize_cfg iteration %i\n\n",
2524 for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR;)
2528 bool changed_here = false;
2530 /* Delete trivially dead basic blocks. This is either
2531 blocks with no predecessors, or empty blocks with no
2532 successors. However if the empty block with no
2533 successors is the successor of the ENTRY_BLOCK, it is
2534 kept. This ensures that the ENTRY_BLOCK will have a
2535 successor which is a precondition for many RTL
2536 passes. Empty blocks may result from expanding
2537 __builtin_unreachable (). */
2538 if (EDGE_COUNT (b->preds) == 0
2539 || (EDGE_COUNT (b->succs) == 0
2540 && trivially_empty_bb_p (b)
2541 && single_succ_edge (ENTRY_BLOCK_PTR)->dest != b))
2544 if (EDGE_COUNT (b->preds) > 0)
2549 if (current_ir_type () == IR_RTL_CFGLAYOUT)
2551 if (b->il.rtl->footer
2552 && BARRIER_P (b->il.rtl->footer))
2553 FOR_EACH_EDGE (e, ei, b->preds)
2554 if ((e->flags & EDGE_FALLTHRU)
2555 && e->src->il.rtl->footer == NULL)
2557 if (b->il.rtl->footer)
2559 e->src->il.rtl->footer = b->il.rtl->footer;
2560 b->il.rtl->footer = NULL;
2565 e->src->il.rtl->footer = emit_barrier ();
2572 rtx last = get_last_bb_insn (b);
2573 if (last && BARRIER_P (last))
2574 FOR_EACH_EDGE (e, ei, b->preds)
2575 if ((e->flags & EDGE_FALLTHRU))
2576 emit_barrier_after (BB_END (e->src));
2579 delete_basic_block (b);
2581 /* Avoid trying to remove ENTRY_BLOCK_PTR. */
2582 b = (c == ENTRY_BLOCK_PTR ? c->next_bb : c);
2586 /* Remove code labels no longer used. */
2587 if (single_pred_p (b)
2588 && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
2589 && !(single_pred_edge (b)->flags & EDGE_COMPLEX)
2590 && LABEL_P (BB_HEAD (b))
2591 /* If the previous block ends with a branch to this
2592 block, we can't delete the label. Normally this
2593 is a condjump that is yet to be simplified, but
2594 if CASE_DROPS_THRU, this can be a tablejump with
2595 some element going to the same place as the
2596 default (fallthru). */
2597 && (single_pred (b) == ENTRY_BLOCK_PTR
2598 || !JUMP_P (BB_END (single_pred (b)))
2599 || ! label_is_jump_target_p (BB_HEAD (b),
2600 BB_END (single_pred (b)))))
2602 rtx label = BB_HEAD (b);
2604 delete_insn_chain (label, label, false);
2605 /* If the case label is undeletable, move it after the
2606 BASIC_BLOCK note. */
2607 if (NOTE_KIND (BB_HEAD (b)) == NOTE_INSN_DELETED_LABEL)
2609 rtx bb_note = NEXT_INSN (BB_HEAD (b));
2611 reorder_insns_nobb (label, label, bb_note);
2612 BB_HEAD (b) = bb_note;
2613 if (BB_END (b) == bb_note)
2617 fprintf (dump_file, "Deleted label in block %i.\n",
2621 /* If we fall through an empty block, we can remove it. */
2622 if (!(mode & CLEANUP_CFGLAYOUT)
2623 && single_pred_p (b)
2624 && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
2625 && !LABEL_P (BB_HEAD (b))
2626 && FORWARDER_BLOCK_P (b)
2627 /* Note that forwarder_block_p true ensures that
2628 there is a successor for this block. */
2629 && (single_succ_edge (b)->flags & EDGE_FALLTHRU)
2630 && n_basic_blocks > NUM_FIXED_BLOCKS + 1)
2634 "Deleting fallthru block %i.\n",
2637 c = b->prev_bb == ENTRY_BLOCK_PTR ? b->next_bb : b->prev_bb;
2638 redirect_edge_succ_nodup (single_pred_edge (b),
2640 delete_basic_block (b);
2646 /* Merge B with its single successor, if any. */
2647 if (single_succ_p (b)
2648 && (s = single_succ_edge (b))
2649 && !(s->flags & EDGE_COMPLEX)
2650 && (c = s->dest) != EXIT_BLOCK_PTR
2651 && single_pred_p (c)
2654 /* When not in cfg_layout mode use code aware of reordering
2655 INSN. This code possibly creates new basic blocks so it
2656 does not fit merge_blocks interface and is kept here in
2657 hope that it will become useless once more of compiler
2658 is transformed to use cfg_layout mode. */
2660 if ((mode & CLEANUP_CFGLAYOUT)
2661 && can_merge_blocks_p (b, c))
2663 merge_blocks (b, c);
2664 update_forwarder_flag (b);
2665 changed_here = true;
2667 else if (!(mode & CLEANUP_CFGLAYOUT)
2668 /* If the jump insn has side effects,
2669 we can't kill the edge. */
2670 && (!JUMP_P (BB_END (b))
2671 || (reload_completed
2672 ? simplejump_p (BB_END (b))
2673 : (onlyjump_p (BB_END (b))
2674 && !tablejump_p (BB_END (b),
2676 && (next = merge_blocks_move (s, b, c, mode)))
2679 changed_here = true;
2683 /* Simplify branch over branch. */
2684 if ((mode & CLEANUP_EXPENSIVE)
2685 && !(mode & CLEANUP_CFGLAYOUT)
2686 && try_simplify_condjump (b))
2687 changed_here = true;
2689 /* If B has a single outgoing edge, but uses a
2690 non-trivial jump instruction without side-effects, we
2691 can either delete the jump entirely, or replace it
2692 with a simple unconditional jump. */
2693 if (single_succ_p (b)
2694 && single_succ (b) != EXIT_BLOCK_PTR
2695 && onlyjump_p (BB_END (b))
2696 && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)
2697 && try_redirect_by_replacing_jump (single_succ_edge (b),
2699 (mode & CLEANUP_CFGLAYOUT) != 0))
2701 update_forwarder_flag (b);
2702 changed_here = true;
2705 /* Simplify branch to branch. */
2706 if (try_forward_edges (mode, b))
2708 update_forwarder_flag (b);
2709 changed_here = true;
2712 /* Look for shared code between blocks. */
2713 if ((mode & CLEANUP_CROSSJUMP)
2714 && try_crossjump_bb (mode, b))
2715 changed_here = true;
2717 if ((mode & CLEANUP_CROSSJUMP)
2718 /* This can lengthen register lifetimes. Do it only after
2721 && try_head_merge_bb (b))
2722 changed_here = true;
2724 /* Don't get confused by the index shift caused by
2732 if ((mode & CLEANUP_CROSSJUMP)
2733 && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
2736 if (block_was_dirty)
2738 /* This should only be set by head-merging. */
2739 gcc_assert (mode & CLEANUP_CROSSJUMP);
2743 #ifdef ENABLE_CHECKING
2745 verify_flow_info ();
2748 changed_overall |= changed;
2755 b->flags &= ~(BB_FORWARDER_BLOCK | BB_NONTHREADABLE_BLOCK);
2757 return changed_overall;
2760 /* Delete all unreachable basic blocks. */
2763 delete_unreachable_blocks (void)
2765 bool changed = false;
2766 basic_block b, prev_bb;
2768 find_unreachable_blocks ();
2770 /* When we're in GIMPLE mode and there may be debug insns, we should
2771 delete blocks in reverse dominator order, so as to get a chance
2772 to substitute all released DEFs into debug stmts. If we don't
2773 have dominators information, walking blocks backward gets us a
2774 better chance of retaining most debug information than
2776 if (MAY_HAVE_DEBUG_STMTS && current_ir_type () == IR_GIMPLE
2777 && dom_info_available_p (CDI_DOMINATORS))
2779 for (b = EXIT_BLOCK_PTR->prev_bb; b != ENTRY_BLOCK_PTR; b = prev_bb)
2781 prev_bb = b->prev_bb;
2783 if (!(b->flags & BB_REACHABLE))
2785 /* Speed up the removal of blocks that don't dominate
2786 others. Walking backwards, this should be the common
2788 if (!first_dom_son (CDI_DOMINATORS, b))
2789 delete_basic_block (b);
2792 VEC (basic_block, heap) *h
2793 = get_all_dominated_blocks (CDI_DOMINATORS, b);
2795 while (VEC_length (basic_block, h))
2797 b = VEC_pop (basic_block, h);
2799 prev_bb = b->prev_bb;
2801 gcc_assert (!(b->flags & BB_REACHABLE));
2803 delete_basic_block (b);
2806 VEC_free (basic_block, heap, h);
2815 for (b = EXIT_BLOCK_PTR->prev_bb; b != ENTRY_BLOCK_PTR; b = prev_bb)
2817 prev_bb = b->prev_bb;
2819 if (!(b->flags & BB_REACHABLE))
2821 delete_basic_block (b);
2828 tidy_fallthru_edges ();
2832 /* Delete any jump tables never referenced. We can't delete them at the
2833 time of removing tablejump insn as they are referenced by the preceding
2834 insns computing the destination, so we delay deleting and garbagecollect
2835 them once life information is computed. */
2837 delete_dead_jumptables (void)
2841 /* A dead jump table does not belong to any basic block. Scan insns
2842 between two adjacent basic blocks. */
2847 for (insn = NEXT_INSN (BB_END (bb));
2848 insn && !NOTE_INSN_BASIC_BLOCK_P (insn);
2851 next = NEXT_INSN (insn);
2853 && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn)
2854 && JUMP_TABLE_DATA_P (next))
2856 rtx label = insn, jump = next;
2859 fprintf (dump_file, "Dead jumptable %i removed\n",
2862 next = NEXT_INSN (next);
2864 delete_insn (label);
2871 /* Tidy the CFG by deleting unreachable code and whatnot. */
2874 cleanup_cfg (int mode)
2876 bool changed = false;
2878 /* Set the cfglayout mode flag here. We could update all the callers
2879 but that is just inconvenient, especially given that we eventually
2880 want to have cfglayout mode as the default. */
2881 if (current_ir_type () == IR_RTL_CFGLAYOUT)
2882 mode |= CLEANUP_CFGLAYOUT;
2884 timevar_push (TV_CLEANUP_CFG);
2885 if (delete_unreachable_blocks ())
2888 /* We've possibly created trivially dead code. Cleanup it right
2889 now to introduce more opportunities for try_optimize_cfg. */
2890 if (!(mode & (CLEANUP_NO_INSN_DEL))
2891 && !reload_completed)
2892 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2897 /* To tail-merge blocks ending in the same noreturn function (e.g.
2898 a call to abort) we have to insert fake edges to exit. Do this
2899 here once. The fake edges do not interfere with any other CFG
2901 if (mode & CLEANUP_CROSSJUMP)
2902 add_noreturn_fake_exit_edges ();
2904 if (!dbg_cnt (cfg_cleanup))
2907 while (try_optimize_cfg (mode))
2909 delete_unreachable_blocks (), changed = true;
2910 if (!(mode & CLEANUP_NO_INSN_DEL))
2912 /* Try to remove some trivially dead insns when doing an expensive
2913 cleanup. But delete_trivially_dead_insns doesn't work after
2914 reload (it only handles pseudos) and run_fast_dce is too costly
2915 to run in every iteration.
2917 For effective cross jumping, we really want to run a fast DCE to
2918 clean up any dead conditions, or they get in the way of performing
2921 Other transformations in cleanup_cfg are not so sensitive to dead
2922 code, so delete_trivially_dead_insns or even doing nothing at all
2924 if ((mode & CLEANUP_EXPENSIVE) && !reload_completed
2925 && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
2927 if ((mode & CLEANUP_CROSSJUMP) && crossjumps_occured)
2934 if (mode & CLEANUP_CROSSJUMP)
2935 remove_fake_exit_edges ();
2937 /* Don't call delete_dead_jumptables in cfglayout mode, because
2938 that function assumes that jump tables are in the insns stream.
2939 But we also don't _have_ to delete dead jumptables in cfglayout
2940 mode because we shouldn't even be looking at things that are
2941 not in a basic block. Dead jumptables are cleaned up when
2942 going out of cfglayout mode. */
2943 if (!(mode & CLEANUP_CFGLAYOUT))
2944 delete_dead_jumptables ();
2946 timevar_pop (TV_CLEANUP_CFG);
2952 rest_of_handle_jump (void)
2954 if (crtl->tail_call_emit)
2955 fixup_tail_calls ();
2959 struct rtl_opt_pass pass_jump =
2963 "sibling", /* name */
2965 rest_of_handle_jump, /* execute */
2968 0, /* static_pass_number */
2969 TV_JUMP, /* tv_id */
2970 0, /* properties_required */
2971 0, /* properties_provided */
2972 0, /* properties_destroyed */
2973 TODO_ggc_collect, /* todo_flags_start */
2974 TODO_verify_flow, /* todo_flags_finish */
2980 rest_of_handle_jump2 (void)
2982 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2984 dump_flow_info (dump_file, dump_flags);
2985 cleanup_cfg ((optimize ? CLEANUP_EXPENSIVE : 0)
2986 | (flag_thread_jumps ? CLEANUP_THREADING : 0));
2991 struct rtl_opt_pass pass_jump2 =
2997 rest_of_handle_jump2, /* execute */
3000 0, /* static_pass_number */
3001 TV_JUMP, /* tv_id */
3002 0, /* properties_required */
3003 0, /* properties_provided */
3004 0, /* properties_destroyed */
3005 TODO_ggc_collect, /* todo_flags_start */
3006 TODO_verify_rtl_sharing, /* todo_flags_finish */