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"
42 #include "insn-config.h"
45 #include "diagnostic-core.h"
50 #include "function.h" /* For inline functions in emit-rtl.h they need crtl. */
52 #include "tree-pass.h"
59 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
61 /* Set to true when we are running first pass of try_optimize_cfg loop. */
62 static bool first_pass
;
64 /* Set to true if crossjumps occurred in the latest run of try_optimize_cfg. */
65 static bool crossjumps_occured
;
67 /* Set to true if we couldn't run an optimization due to stale liveness
68 information; we should run df_analyze to enable more opportunities. */
69 static bool block_was_dirty
;
71 static bool try_crossjump_to_edge (int, edge
, edge
, enum replace_direction
);
72 static bool try_crossjump_bb (int, basic_block
);
73 static bool outgoing_edges_match (int, basic_block
, basic_block
);
74 static enum replace_direction
old_insns_match_p (int, rtx
, rtx
);
76 static void merge_blocks_move_predecessor_nojumps (basic_block
, basic_block
);
77 static void merge_blocks_move_successor_nojumps (basic_block
, basic_block
);
78 static bool try_optimize_cfg (int);
79 static bool try_simplify_condjump (basic_block
);
80 static bool try_forward_edges (int, basic_block
);
81 static edge
thread_jump (edge
, basic_block
);
82 static bool mark_effect (rtx
, bitmap
);
83 static void notice_new_block (basic_block
);
84 static void update_forwarder_flag (basic_block
);
85 static int mentions_nonequal_regs (rtx
*, void *);
86 static void merge_memattrs (rtx
, rtx
);
88 /* Set flags for newly created block. */
91 notice_new_block (basic_block bb
)
96 if (forwarder_block_p (bb
))
97 bb
->flags
|= BB_FORWARDER_BLOCK
;
100 /* Recompute forwarder flag after block has been modified. */
103 update_forwarder_flag (basic_block bb
)
105 if (forwarder_block_p (bb
))
106 bb
->flags
|= BB_FORWARDER_BLOCK
;
108 bb
->flags
&= ~BB_FORWARDER_BLOCK
;
111 /* Simplify a conditional jump around an unconditional jump.
112 Return true if something changed. */
115 try_simplify_condjump (basic_block cbranch_block
)
117 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
118 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
121 /* Verify that there are exactly two successors. */
122 if (EDGE_COUNT (cbranch_block
->succs
) != 2)
125 /* Verify that we've got a normal conditional branch at the end
127 cbranch_insn
= BB_END (cbranch_block
);
128 if (!any_condjump_p (cbranch_insn
))
131 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
132 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
134 /* The next block must not have multiple predecessors, must not
135 be the last block in the function, and must contain just the
136 unconditional jump. */
137 jump_block
= cbranch_fallthru_edge
->dest
;
138 if (!single_pred_p (jump_block
)
139 || jump_block
->next_bb
== EXIT_BLOCK_PTR
140 || !FORWARDER_BLOCK_P (jump_block
))
142 jump_dest_block
= single_succ (jump_block
);
144 /* If we are partitioning hot/cold basic blocks, we don't want to
145 mess up unconditional or indirect jumps that cross between hot
148 Basic block partitioning may result in some jumps that appear to
149 be optimizable (or blocks that appear to be mergeable), but which really
150 must be left untouched (they are required to make it safely across
151 partition boundaries). See the comments at the top of
152 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
154 if (BB_PARTITION (jump_block
) != BB_PARTITION (jump_dest_block
)
155 || (cbranch_jump_edge
->flags
& EDGE_CROSSING
))
158 /* The conditional branch must target the block after the
159 unconditional branch. */
160 cbranch_dest_block
= cbranch_jump_edge
->dest
;
162 if (cbranch_dest_block
== EXIT_BLOCK_PTR
163 || !can_fallthru (jump_block
, cbranch_dest_block
))
166 /* Invert the conditional branch. */
167 if (!invert_jump (cbranch_insn
, block_label (jump_dest_block
), 0))
171 fprintf (dump_file
, "Simplifying condjump %i around jump %i\n",
172 INSN_UID (cbranch_insn
), INSN_UID (BB_END (jump_block
)));
174 /* Success. Update the CFG to match. Note that after this point
175 the edge variable names appear backwards; the redirection is done
176 this way to preserve edge profile data. */
177 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
179 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
181 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
182 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
183 update_br_prob_note (cbranch_block
);
185 /* Delete the block with the unconditional jump, and clean up the mess. */
186 delete_basic_block (jump_block
);
187 tidy_fallthru_edge (cbranch_jump_edge
);
188 update_forwarder_flag (cbranch_block
);
193 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
194 on register. Used by jump threading. */
197 mark_effect (rtx exp
, regset nonequal
)
201 switch (GET_CODE (exp
))
203 /* In case we do clobber the register, mark it as equal, as we know the
204 value is dead so it don't have to match. */
206 if (REG_P (XEXP (exp
, 0)))
208 dest
= XEXP (exp
, 0);
209 regno
= REGNO (dest
);
210 if (HARD_REGISTER_NUM_P (regno
))
211 bitmap_clear_range (nonequal
, regno
,
212 hard_regno_nregs
[regno
][GET_MODE (dest
)]);
214 bitmap_clear_bit (nonequal
, regno
);
219 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
221 dest
= SET_DEST (exp
);
226 regno
= REGNO (dest
);
227 if (HARD_REGISTER_NUM_P (regno
))
228 bitmap_set_range (nonequal
, regno
,
229 hard_regno_nregs
[regno
][GET_MODE (dest
)]);
231 bitmap_set_bit (nonequal
, regno
);
239 /* Return nonzero if X is a register set in regset DATA.
240 Called via for_each_rtx. */
242 mentions_nonequal_regs (rtx
*x
, void *data
)
244 regset nonequal
= (regset
) data
;
250 if (REGNO_REG_SET_P (nonequal
, regno
))
252 if (regno
< FIRST_PSEUDO_REGISTER
)
254 int n
= hard_regno_nregs
[regno
][GET_MODE (*x
)];
256 if (REGNO_REG_SET_P (nonequal
, regno
+ n
))
262 /* Attempt to prove that the basic block B will have no side effects and
263 always continues in the same edge if reached via E. Return the edge
264 if exist, NULL otherwise. */
267 thread_jump (edge e
, basic_block b
)
269 rtx set1
, set2
, cond1
, cond2
, insn
;
270 enum rtx_code code1
, code2
, reversed_code2
;
271 bool reverse1
= false;
275 reg_set_iterator rsi
;
277 if (b
->flags
& BB_NONTHREADABLE_BLOCK
)
280 /* At the moment, we do handle only conditional jumps, but later we may
281 want to extend this code to tablejumps and others. */
282 if (EDGE_COUNT (e
->src
->succs
) != 2)
284 if (EDGE_COUNT (b
->succs
) != 2)
286 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
290 /* Second branch must end with onlyjump, as we will eliminate the jump. */
291 if (!any_condjump_p (BB_END (e
->src
)))
294 if (!any_condjump_p (BB_END (b
)) || !onlyjump_p (BB_END (b
)))
296 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
300 set1
= pc_set (BB_END (e
->src
));
301 set2
= pc_set (BB_END (b
));
302 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
303 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
306 cond1
= XEXP (SET_SRC (set1
), 0);
307 cond2
= XEXP (SET_SRC (set2
), 0);
309 code1
= reversed_comparison_code (cond1
, BB_END (e
->src
));
311 code1
= GET_CODE (cond1
);
313 code2
= GET_CODE (cond2
);
314 reversed_code2
= reversed_comparison_code (cond2
, BB_END (b
));
316 if (!comparison_dominates_p (code1
, code2
)
317 && !comparison_dominates_p (code1
, reversed_code2
))
320 /* Ensure that the comparison operators are equivalent.
321 ??? This is far too pessimistic. We should allow swapped operands,
322 different CCmodes, or for example comparisons for interval, that
323 dominate even when operands are not equivalent. */
324 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
325 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
328 /* Short circuit cases where block B contains some side effects, as we can't
330 for (insn
= NEXT_INSN (BB_HEAD (b
)); insn
!= NEXT_INSN (BB_END (b
));
331 insn
= NEXT_INSN (insn
))
332 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
334 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
340 /* First process all values computed in the source basic block. */
341 for (insn
= NEXT_INSN (BB_HEAD (e
->src
));
342 insn
!= NEXT_INSN (BB_END (e
->src
));
343 insn
= NEXT_INSN (insn
))
345 cselib_process_insn (insn
);
347 nonequal
= BITMAP_ALLOC (NULL
);
348 CLEAR_REG_SET (nonequal
);
350 /* Now assume that we've continued by the edge E to B and continue
351 processing as if it were same basic block.
352 Our goal is to prove that whole block is an NOOP. */
354 for (insn
= NEXT_INSN (BB_HEAD (b
));
355 insn
!= NEXT_INSN (BB_END (b
)) && !failed
;
356 insn
= NEXT_INSN (insn
))
360 rtx pat
= PATTERN (insn
);
362 if (GET_CODE (pat
) == PARALLEL
)
364 for (i
= 0; i
< (unsigned)XVECLEN (pat
, 0); i
++)
365 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
368 failed
|= mark_effect (pat
, nonequal
);
371 cselib_process_insn (insn
);
374 /* Later we should clear nonequal of dead registers. So far we don't
375 have life information in cfg_cleanup. */
378 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
382 /* cond2 must not mention any register that is not equal to the
384 if (for_each_rtx (&cond2
, mentions_nonequal_regs
, nonequal
))
387 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, rsi
)
390 BITMAP_FREE (nonequal
);
392 if ((comparison_dominates_p (code1
, code2
) != 0)
393 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
394 return BRANCH_EDGE (b
);
396 return FALLTHRU_EDGE (b
);
399 BITMAP_FREE (nonequal
);
404 /* Attempt to forward edges leaving basic block B.
405 Return true if successful. */
408 try_forward_edges (int mode
, basic_block b
)
410 bool changed
= false;
412 edge e
, *threaded_edges
= NULL
;
414 /* If we are partitioning hot/cold basic blocks, we don't want to
415 mess up unconditional or indirect jumps that cross between hot
418 Basic block partitioning may result in some jumps that appear to
419 be optimizable (or blocks that appear to be mergeable), but which really
420 must be left untouched (they are required to make it safely across
421 partition boundaries). See the comments at the top of
422 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
424 if (find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
427 for (ei
= ei_start (b
->succs
); (e
= ei_safe_edge (ei
)); )
429 basic_block target
, first
;
430 int counter
, goto_locus
;
431 bool threaded
= false;
432 int nthreaded_edges
= 0;
433 bool may_thread
= first_pass
|| (b
->flags
& BB_MODIFIED
) != 0;
435 /* Skip complex edges because we don't know how to update them.
437 Still handle fallthru edges, as we can succeed to forward fallthru
438 edge to the same place as the branch edge of conditional branch
439 and turn conditional branch to an unconditional branch. */
440 if (e
->flags
& EDGE_COMPLEX
)
446 target
= first
= e
->dest
;
447 counter
= NUM_FIXED_BLOCKS
;
448 goto_locus
= e
->goto_locus
;
450 /* If we are partitioning hot/cold basic_blocks, we don't want to mess
451 up jumps that cross between hot/cold sections.
453 Basic block partitioning may result in some jumps that appear
454 to be optimizable (or blocks that appear to be mergeable), but which
455 really must be left untouched (they are required to make it safely
456 across partition boundaries). See the comments at the top of
457 bb-reorder.c:partition_hot_cold_basic_blocks for complete
460 if (first
!= EXIT_BLOCK_PTR
461 && find_reg_note (BB_END (first
), REG_CROSSING_JUMP
, NULL_RTX
))
464 while (counter
< n_basic_blocks
)
466 basic_block new_target
= NULL
;
467 bool new_target_threaded
= false;
468 may_thread
|= (target
->flags
& BB_MODIFIED
) != 0;
470 if (FORWARDER_BLOCK_P (target
)
471 && !(single_succ_edge (target
)->flags
& EDGE_CROSSING
)
472 && single_succ (target
) != EXIT_BLOCK_PTR
)
474 /* Bypass trivial infinite loops. */
475 new_target
= single_succ (target
);
476 if (target
== new_target
)
477 counter
= n_basic_blocks
;
480 /* When not optimizing, ensure that edges or forwarder
481 blocks with different locus are not optimized out. */
482 int new_locus
= single_succ_edge (target
)->goto_locus
;
483 int locus
= goto_locus
;
485 if (new_locus
&& locus
&& !locator_eq (new_locus
, locus
))
494 last
= BB_END (target
);
495 if (DEBUG_INSN_P (last
))
496 last
= prev_nondebug_insn (last
);
498 new_locus
= last
&& INSN_P (last
)
499 ? INSN_LOCATOR (last
) : 0;
501 if (new_locus
&& locus
&& !locator_eq (new_locus
, locus
))
514 /* Allow to thread only over one edge at time to simplify updating
516 else if ((mode
& CLEANUP_THREADING
) && may_thread
)
518 edge t
= thread_jump (e
, target
);
522 threaded_edges
= XNEWVEC (edge
, n_basic_blocks
);
527 /* Detect an infinite loop across blocks not
528 including the start block. */
529 for (i
= 0; i
< nthreaded_edges
; ++i
)
530 if (threaded_edges
[i
] == t
)
532 if (i
< nthreaded_edges
)
534 counter
= n_basic_blocks
;
539 /* Detect an infinite loop across the start block. */
543 gcc_assert (nthreaded_edges
< n_basic_blocks
- NUM_FIXED_BLOCKS
);
544 threaded_edges
[nthreaded_edges
++] = t
;
546 new_target
= t
->dest
;
547 new_target_threaded
= true;
556 threaded
|= new_target_threaded
;
559 if (counter
>= n_basic_blocks
)
562 fprintf (dump_file
, "Infinite loop in BB %i.\n",
565 else if (target
== first
)
566 ; /* We didn't do anything. */
569 /* Save the values now, as the edge may get removed. */
570 gcov_type edge_count
= e
->count
;
571 int edge_probability
= e
->probability
;
575 e
->goto_locus
= goto_locus
;
577 /* Don't force if target is exit block. */
578 if (threaded
&& target
!= EXIT_BLOCK_PTR
)
580 notice_new_block (redirect_edge_and_branch_force (e
, target
));
582 fprintf (dump_file
, "Conditionals threaded.\n");
584 else if (!redirect_edge_and_branch (e
, target
))
588 "Forwarding edge %i->%i to %i failed.\n",
589 b
->index
, e
->dest
->index
, target
->index
);
594 /* We successfully forwarded the edge. Now update profile
595 data: for each edge we traversed in the chain, remove
596 the original edge's execution count. */
597 edge_frequency
= ((edge_probability
* b
->frequency
598 + REG_BR_PROB_BASE
/ 2)
605 if (!single_succ_p (first
))
607 gcc_assert (n
< nthreaded_edges
);
608 t
= threaded_edges
[n
++];
609 gcc_assert (t
->src
== first
);
610 update_bb_profile_for_threading (first
, edge_frequency
,
612 update_br_prob_note (first
);
616 first
->count
-= edge_count
;
617 if (first
->count
< 0)
619 first
->frequency
-= edge_frequency
;
620 if (first
->frequency
< 0)
621 first
->frequency
= 0;
622 /* It is possible that as the result of
623 threading we've removed edge as it is
624 threaded to the fallthru edge. Avoid
625 getting out of sync. */
626 if (n
< nthreaded_edges
627 && first
== threaded_edges
[n
]->src
)
629 t
= single_succ_edge (first
);
632 t
->count
-= edge_count
;
637 while (first
!= target
);
645 free (threaded_edges
);
650 /* Blocks A and B are to be merged into a single block. A has no incoming
651 fallthru edge, so it can be moved before B without adding or modifying
652 any jumps (aside from the jump from A to B). */
655 merge_blocks_move_predecessor_nojumps (basic_block a
, basic_block b
)
659 /* If we are partitioning hot/cold basic blocks, we don't want to
660 mess up unconditional or indirect jumps that cross between hot
663 Basic block partitioning may result in some jumps that appear to
664 be optimizable (or blocks that appear to be mergeable), but which really
665 must be left untouched (they are required to make it safely across
666 partition boundaries). See the comments at the top of
667 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
669 if (BB_PARTITION (a
) != BB_PARTITION (b
))
672 barrier
= next_nonnote_insn (BB_END (a
));
673 gcc_assert (BARRIER_P (barrier
));
674 delete_insn (barrier
);
676 /* Scramble the insn chain. */
677 if (BB_END (a
) != PREV_INSN (BB_HEAD (b
)))
678 reorder_insns_nobb (BB_HEAD (a
), BB_END (a
), PREV_INSN (BB_HEAD (b
)));
682 fprintf (dump_file
, "Moved block %d before %d and merged.\n",
685 /* Swap the records for the two blocks around. */
688 link_block (a
, b
->prev_bb
);
690 /* Now blocks A and B are contiguous. Merge them. */
694 /* Blocks A and B are to be merged into a single block. B has no outgoing
695 fallthru edge, so it can be moved after A without adding or modifying
696 any jumps (aside from the jump from A to B). */
699 merge_blocks_move_successor_nojumps (basic_block a
, basic_block b
)
701 rtx barrier
, real_b_end
;
704 /* If we are partitioning hot/cold basic blocks, we don't want to
705 mess up unconditional or indirect jumps that cross between hot
708 Basic block partitioning may result in some jumps that appear to
709 be optimizable (or blocks that appear to be mergeable), but which really
710 must be left untouched (they are required to make it safely across
711 partition boundaries). See the comments at the top of
712 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
714 if (BB_PARTITION (a
) != BB_PARTITION (b
))
717 real_b_end
= BB_END (b
);
719 /* If there is a jump table following block B temporarily add the jump table
720 to block B so that it will also be moved to the correct location. */
721 if (tablejump_p (BB_END (b
), &label
, &table
)
722 && prev_active_insn (label
) == BB_END (b
))
727 /* There had better have been a barrier there. Delete it. */
728 barrier
= NEXT_INSN (BB_END (b
));
729 if (barrier
&& BARRIER_P (barrier
))
730 delete_insn (barrier
);
733 /* Scramble the insn chain. */
734 reorder_insns_nobb (BB_HEAD (b
), BB_END (b
), BB_END (a
));
736 /* Restore the real end of b. */
737 BB_END (b
) = real_b_end
;
740 fprintf (dump_file
, "Moved block %d after %d and merged.\n",
743 /* Now blocks A and B are contiguous. Merge them. */
747 /* Attempt to merge basic blocks that are potentially non-adjacent.
748 Return NULL iff the attempt failed, otherwise return basic block
749 where cleanup_cfg should continue. Because the merging commonly
750 moves basic block away or introduces another optimization
751 possibility, return basic block just before B so cleanup_cfg don't
754 It may be good idea to return basic block before C in the case
755 C has been moved after B and originally appeared earlier in the
756 insn sequence, but we have no information available about the
757 relative ordering of these two. Hopefully it is not too common. */
760 merge_blocks_move (edge e
, basic_block b
, basic_block c
, int mode
)
764 /* If we are partitioning hot/cold basic blocks, we don't want to
765 mess up unconditional or indirect jumps that cross between hot
768 Basic block partitioning may result in some jumps that appear to
769 be optimizable (or blocks that appear to be mergeable), but which really
770 must be left untouched (they are required to make it safely across
771 partition boundaries). See the comments at the top of
772 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
774 if (BB_PARTITION (b
) != BB_PARTITION (c
))
777 /* If B has a fallthru edge to C, no need to move anything. */
778 if (e
->flags
& EDGE_FALLTHRU
)
780 int b_index
= b
->index
, c_index
= c
->index
;
782 /* Protect the loop latches. */
783 if (current_loops
&& c
->loop_father
->latch
== c
)
787 update_forwarder_flag (b
);
790 fprintf (dump_file
, "Merged %d and %d without moving.\n",
793 return b
->prev_bb
== ENTRY_BLOCK_PTR
? b
: b
->prev_bb
;
796 /* Otherwise we will need to move code around. Do that only if expensive
797 transformations are allowed. */
798 else if (mode
& CLEANUP_EXPENSIVE
)
800 edge tmp_edge
, b_fallthru_edge
;
801 bool c_has_outgoing_fallthru
;
802 bool b_has_incoming_fallthru
;
804 /* Avoid overactive code motion, as the forwarder blocks should be
805 eliminated by edge redirection instead. One exception might have
806 been if B is a forwarder block and C has no fallthru edge, but
807 that should be cleaned up by bb-reorder instead. */
808 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
811 /* We must make sure to not munge nesting of lexical blocks,
812 and loop notes. This is done by squeezing out all the notes
813 and leaving them there to lie. Not ideal, but functional. */
815 tmp_edge
= find_fallthru_edge (c
->succs
);
816 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
818 tmp_edge
= find_fallthru_edge (b
->preds
);
819 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
820 b_fallthru_edge
= tmp_edge
;
823 next
= next
->prev_bb
;
825 /* Otherwise, we're going to try to move C after B. If C does
826 not have an outgoing fallthru, then it can be moved
827 immediately after B without introducing or modifying jumps. */
828 if (! c_has_outgoing_fallthru
)
830 merge_blocks_move_successor_nojumps (b
, c
);
831 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
834 /* If B does not have an incoming fallthru, then it can be moved
835 immediately before C without introducing or modifying jumps.
836 C cannot be the first block, so we do not have to worry about
837 accessing a non-existent block. */
839 if (b_has_incoming_fallthru
)
843 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
845 bb
= force_nonfallthru (b_fallthru_edge
);
847 notice_new_block (bb
);
850 merge_blocks_move_predecessor_nojumps (b
, c
);
851 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
858 /* Removes the memory attributes of MEM expression
859 if they are not equal. */
862 merge_memattrs (rtx x
, rtx y
)
871 if (x
== 0 || y
== 0)
876 if (code
!= GET_CODE (y
))
879 if (GET_MODE (x
) != GET_MODE (y
))
882 if (code
== MEM
&& MEM_ATTRS (x
) != MEM_ATTRS (y
))
886 else if (! MEM_ATTRS (y
))
890 HOST_WIDE_INT mem_size
;
892 if (MEM_ALIAS_SET (x
) != MEM_ALIAS_SET (y
))
894 set_mem_alias_set (x
, 0);
895 set_mem_alias_set (y
, 0);
898 if (! mem_expr_equal_p (MEM_EXPR (x
), MEM_EXPR (y
)))
902 clear_mem_offset (x
);
903 clear_mem_offset (y
);
905 else if (MEM_OFFSET_KNOWN_P (x
) != MEM_OFFSET_KNOWN_P (y
)
906 || (MEM_OFFSET_KNOWN_P (x
)
907 && MEM_OFFSET (x
) != MEM_OFFSET (y
)))
909 clear_mem_offset (x
);
910 clear_mem_offset (y
);
913 if (MEM_SIZE_KNOWN_P (x
) && MEM_SIZE_KNOWN_P (y
))
915 mem_size
= MAX (MEM_SIZE (x
), MEM_SIZE (y
));
916 set_mem_size (x
, mem_size
);
917 set_mem_size (y
, mem_size
);
925 set_mem_align (x
, MIN (MEM_ALIGN (x
), MEM_ALIGN (y
)));
926 set_mem_align (y
, MEM_ALIGN (x
));
930 fmt
= GET_RTX_FORMAT (code
);
931 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
936 /* Two vectors must have the same length. */
937 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
940 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
941 merge_memattrs (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
));
946 merge_memattrs (XEXP (x
, i
), XEXP (y
, i
));
953 /* Checks if patterns P1 and P2 are equivalent, apart from the possibly
954 different single sets S1 and S2. */
957 equal_different_set_p (rtx p1
, rtx s1
, rtx p2
, rtx s2
)
962 if (p1
== s1
&& p2
== s2
)
965 if (GET_CODE (p1
) != PARALLEL
|| GET_CODE (p2
) != PARALLEL
)
968 if (XVECLEN (p1
, 0) != XVECLEN (p2
, 0))
971 for (i
= 0; i
< XVECLEN (p1
, 0); i
++)
973 e1
= XVECEXP (p1
, 0, i
);
974 e2
= XVECEXP (p2
, 0, i
);
975 if (e1
== s1
&& e2
== s2
)
978 ? rtx_renumbered_equal_p (e1
, e2
) : rtx_equal_p (e1
, e2
))
987 /* Examine register notes on I1 and I2 and return:
988 - dir_forward if I1 can be replaced by I2, or
989 - dir_backward if I2 can be replaced by I1, or
990 - dir_both if both are the case. */
992 static enum replace_direction
993 can_replace_by (rtx i1
, rtx i2
)
995 rtx s1
, s2
, d1
, d2
, src1
, src2
, note1
, note2
;
998 /* Check for 2 sets. */
999 s1
= single_set (i1
);
1000 s2
= single_set (i2
);
1001 if (s1
== NULL_RTX
|| s2
== NULL_RTX
)
1004 /* Check that the 2 sets set the same dest. */
1007 if (!(reload_completed
1008 ? rtx_renumbered_equal_p (d1
, d2
) : rtx_equal_p (d1
, d2
)))
1011 /* Find identical req_equiv or reg_equal note, which implies that the 2 sets
1012 set dest to the same value. */
1013 note1
= find_reg_equal_equiv_note (i1
);
1014 note2
= find_reg_equal_equiv_note (i2
);
1015 if (!note1
|| !note2
|| !rtx_equal_p (XEXP (note1
, 0), XEXP (note2
, 0))
1016 || !CONST_INT_P (XEXP (note1
, 0)))
1019 if (!equal_different_set_p (PATTERN (i1
), s1
, PATTERN (i2
), s2
))
1022 /* Although the 2 sets set dest to the same value, we cannot replace
1023 (set (dest) (const_int))
1026 because we don't know if the reg is live and has the same value at the
1027 location of replacement. */
1028 src1
= SET_SRC (s1
);
1029 src2
= SET_SRC (s2
);
1030 c1
= CONST_INT_P (src1
);
1031 c2
= CONST_INT_P (src2
);
1037 return dir_backward
;
1042 /* Merges directions A and B. */
1044 static enum replace_direction
1045 merge_dir (enum replace_direction a
, enum replace_direction b
)
1047 /* Implements the following table:
1066 /* Examine I1 and I2 and return:
1067 - dir_forward if I1 can be replaced by I2, or
1068 - dir_backward if I2 can be replaced by I1, or
1069 - dir_both if both are the case. */
1071 static enum replace_direction
1072 old_insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx i1
, rtx i2
)
1076 /* Verify that I1 and I2 are equivalent. */
1077 if (GET_CODE (i1
) != GET_CODE (i2
))
1080 /* __builtin_unreachable() may lead to empty blocks (ending with
1081 NOTE_INSN_BASIC_BLOCK). They may be crossjumped. */
1082 if (NOTE_INSN_BASIC_BLOCK_P (i1
) && NOTE_INSN_BASIC_BLOCK_P (i2
))
1085 /* ??? Do not allow cross-jumping between different stack levels. */
1086 p1
= find_reg_note (i1
, REG_ARGS_SIZE
, NULL
);
1087 p2
= find_reg_note (i2
, REG_ARGS_SIZE
, NULL
);
1092 if (!rtx_equal_p (p1
, p2
))
1095 /* ??? Worse, this adjustment had better be constant lest we
1096 have differing incoming stack levels. */
1097 if (!frame_pointer_needed
1098 && find_args_size_adjust (i1
) == HOST_WIDE_INT_MIN
)
1107 if (GET_CODE (p1
) != GET_CODE (p2
))
1110 /* If this is a CALL_INSN, compare register usage information.
1111 If we don't check this on stack register machines, the two
1112 CALL_INSNs might be merged leaving reg-stack.c with mismatching
1113 numbers of stack registers in the same basic block.
1114 If we don't check this on machines with delay slots, a delay slot may
1115 be filled that clobbers a parameter expected by the subroutine.
1117 ??? We take the simple route for now and assume that if they're
1118 equal, they were constructed identically.
1120 Also check for identical exception regions. */
1124 /* Ensure the same EH region. */
1125 rtx n1
= find_reg_note (i1
, REG_EH_REGION
, 0);
1126 rtx n2
= find_reg_note (i2
, REG_EH_REGION
, 0);
1131 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1134 if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
1135 CALL_INSN_FUNCTION_USAGE (i2
))
1136 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
))
1141 /* If cross_jump_death_matters is not 0, the insn's mode
1142 indicates whether or not the insn contains any stack-like
1145 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
1147 /* If register stack conversion has already been done, then
1148 death notes must also be compared before it is certain that
1149 the two instruction streams match. */
1152 HARD_REG_SET i1_regset
, i2_regset
;
1154 CLEAR_HARD_REG_SET (i1_regset
);
1155 CLEAR_HARD_REG_SET (i2_regset
);
1157 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
1158 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1159 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
1161 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
1162 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1163 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
1165 if (!hard_reg_set_equal_p (i1_regset
, i2_regset
))
1170 if (reload_completed
1171 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
1174 return can_replace_by (i1
, i2
);
1177 /* When comparing insns I1 and I2 in flow_find_cross_jump or
1178 flow_find_head_matching_sequence, ensure the notes match. */
1181 merge_notes (rtx i1
, rtx i2
)
1183 /* If the merged insns have different REG_EQUAL notes, then
1185 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1186 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1188 if (equiv1
&& !equiv2
)
1189 remove_note (i1
, equiv1
);
1190 else if (!equiv1
&& equiv2
)
1191 remove_note (i2
, equiv2
);
1192 else if (equiv1
&& equiv2
1193 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1195 remove_note (i1
, equiv1
);
1196 remove_note (i2
, equiv2
);
1200 /* Walks from I1 in BB1 backward till the next non-debug insn, and returns the
1201 resulting insn in I1, and the corresponding bb in BB1. At the head of a
1202 bb, if there is a predecessor bb that reaches this bb via fallthru, and
1203 FOLLOW_FALLTHRU, walks further in the predecessor bb and registers this in
1204 DID_FALLTHRU. Otherwise, stops at the head of the bb. */
1207 walk_to_nondebug_insn (rtx
*i1
, basic_block
*bb1
, bool follow_fallthru
,
1212 *did_fallthru
= false;
1215 while (!NONDEBUG_INSN_P (*i1
))
1217 if (*i1
!= BB_HEAD (*bb1
))
1219 *i1
= PREV_INSN (*i1
);
1223 if (!follow_fallthru
)
1226 fallthru
= find_fallthru_edge ((*bb1
)->preds
);
1227 if (!fallthru
|| fallthru
->src
== ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
)
1228 || !single_succ_p (fallthru
->src
))
1231 *bb1
= fallthru
->src
;
1232 *i1
= BB_END (*bb1
);
1233 *did_fallthru
= true;
1237 /* Look through the insns at the end of BB1 and BB2 and find the longest
1238 sequence that are either equivalent, or allow forward or backward
1239 replacement. Store the first insns for that sequence in *F1 and *F2 and
1240 return the sequence length.
1242 DIR_P indicates the allowed replacement direction on function entry, and
1243 the actual replacement direction on function exit. If NULL, only equivalent
1244 sequences are allowed.
1246 To simplify callers of this function, if the blocks match exactly,
1247 store the head of the blocks in *F1 and *F2. */
1250 flow_find_cross_jump (basic_block bb1
, basic_block bb2
, rtx
*f1
, rtx
*f2
,
1251 enum replace_direction
*dir_p
)
1253 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
1256 enum replace_direction dir
, last_dir
, afterlast_dir
;
1257 bool follow_fallthru
, did_fallthru
;
1263 afterlast_dir
= dir
;
1264 last_dir
= afterlast_dir
;
1266 /* Skip simple jumps at the end of the blocks. Complex jumps still
1267 need to be compared for equivalence, which we'll do below. */
1270 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
1272 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1275 i1
= PREV_INSN (i1
);
1280 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1283 /* Count everything except for unconditional jump as insn. */
1284 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1286 i2
= PREV_INSN (i2
);
1291 /* In the following example, we can replace all jumps to C by jumps to A.
1293 This removes 4 duplicate insns.
1294 [bb A] insn1 [bb C] insn1
1300 We could also replace all jumps to A by jumps to C, but that leaves B
1301 alive, and removes only 2 duplicate insns. In a subsequent crossjump
1302 step, all jumps to B would be replaced with jumps to the middle of C,
1303 achieving the same result with more effort.
1304 So we allow only the first possibility, which means that we don't allow
1305 fallthru in the block that's being replaced. */
1307 follow_fallthru
= dir_p
&& dir
!= dir_forward
;
1308 walk_to_nondebug_insn (&i1
, &bb1
, follow_fallthru
, &did_fallthru
);
1312 follow_fallthru
= dir_p
&& dir
!= dir_backward
;
1313 walk_to_nondebug_insn (&i2
, &bb2
, follow_fallthru
, &did_fallthru
);
1317 if (i1
== BB_HEAD (bb1
) || i2
== BB_HEAD (bb2
))
1320 dir
= merge_dir (dir
, old_insns_match_p (0, i1
, i2
));
1321 if (dir
== dir_none
|| (!dir_p
&& dir
!= dir_both
))
1324 merge_memattrs (i1
, i2
);
1326 /* Don't begin a cross-jump with a NOTE insn. */
1329 merge_notes (i1
, i2
);
1331 afterlast1
= last1
, afterlast2
= last2
;
1332 last1
= i1
, last2
= i2
;
1333 afterlast_dir
= last_dir
;
1336 if (!(GET_CODE (p1
) == USE
|| GET_CODE (p1
) == CLOBBER
))
1340 i1
= PREV_INSN (i1
);
1341 i2
= PREV_INSN (i2
);
1345 /* Don't allow the insn after a compare to be shared by
1346 cross-jumping unless the compare is also shared. */
1347 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1348 last1
= afterlast1
, last2
= afterlast2
, last_dir
= afterlast_dir
, ninsns
--;
1351 /* Include preceding notes and labels in the cross-jump. One,
1352 this may bring us to the head of the blocks as requested above.
1353 Two, it keeps line number notes as matched as may be. */
1356 bb1
= BLOCK_FOR_INSN (last1
);
1357 while (last1
!= BB_HEAD (bb1
) && !NONDEBUG_INSN_P (PREV_INSN (last1
)))
1358 last1
= PREV_INSN (last1
);
1360 if (last1
!= BB_HEAD (bb1
) && LABEL_P (PREV_INSN (last1
)))
1361 last1
= PREV_INSN (last1
);
1363 bb2
= BLOCK_FOR_INSN (last2
);
1364 while (last2
!= BB_HEAD (bb2
) && !NONDEBUG_INSN_P (PREV_INSN (last2
)))
1365 last2
= PREV_INSN (last2
);
1367 if (last2
!= BB_HEAD (bb2
) && LABEL_P (PREV_INSN (last2
)))
1368 last2
= PREV_INSN (last2
);
1379 /* Like flow_find_cross_jump, except start looking for a matching sequence from
1380 the head of the two blocks. Do not include jumps at the end.
1381 If STOP_AFTER is nonzero, stop after finding that many matching
1385 flow_find_head_matching_sequence (basic_block bb1
, basic_block bb2
, rtx
*f1
,
1386 rtx
*f2
, int stop_after
)
1388 rtx i1
, i2
, last1
, last2
, beforelast1
, beforelast2
;
1392 int nehedges1
= 0, nehedges2
= 0;
1394 FOR_EACH_EDGE (e
, ei
, bb1
->succs
)
1395 if (e
->flags
& EDGE_EH
)
1397 FOR_EACH_EDGE (e
, ei
, bb2
->succs
)
1398 if (e
->flags
& EDGE_EH
)
1403 last1
= beforelast1
= last2
= beforelast2
= NULL_RTX
;
1407 /* Ignore notes, except NOTE_INSN_EPILOGUE_BEG. */
1408 while (!NONDEBUG_INSN_P (i1
) && i1
!= BB_END (bb1
))
1410 if (NOTE_P (i1
) && NOTE_KIND (i1
) == NOTE_INSN_EPILOGUE_BEG
)
1412 i1
= NEXT_INSN (i1
);
1415 while (!NONDEBUG_INSN_P (i2
) && i2
!= BB_END (bb2
))
1417 if (NOTE_P (i2
) && NOTE_KIND (i2
) == NOTE_INSN_EPILOGUE_BEG
)
1419 i2
= NEXT_INSN (i2
);
1422 if ((i1
== BB_END (bb1
) && !NONDEBUG_INSN_P (i1
))
1423 || (i2
== BB_END (bb2
) && !NONDEBUG_INSN_P (i2
)))
1426 if (NOTE_P (i1
) || NOTE_P (i2
)
1427 || JUMP_P (i1
) || JUMP_P (i2
))
1430 /* A sanity check to make sure we're not merging insns with different
1431 effects on EH. If only one of them ends a basic block, it shouldn't
1432 have an EH edge; if both end a basic block, there should be the same
1433 number of EH edges. */
1434 if ((i1
== BB_END (bb1
) && i2
!= BB_END (bb2
)
1436 || (i2
== BB_END (bb2
) && i1
!= BB_END (bb1
)
1438 || (i1
== BB_END (bb1
) && i2
== BB_END (bb2
)
1439 && nehedges1
!= nehedges2
))
1442 if (old_insns_match_p (0, i1
, i2
) != dir_both
)
1445 merge_memattrs (i1
, i2
);
1447 /* Don't begin a cross-jump with a NOTE insn. */
1450 merge_notes (i1
, i2
);
1452 beforelast1
= last1
, beforelast2
= last2
;
1453 last1
= i1
, last2
= i2
;
1457 if (i1
== BB_END (bb1
) || i2
== BB_END (bb2
)
1458 || (stop_after
> 0 && ninsns
== stop_after
))
1461 i1
= NEXT_INSN (i1
);
1462 i2
= NEXT_INSN (i2
);
1466 /* Don't allow a compare to be shared by cross-jumping unless the insn
1467 after the compare is also shared. */
1468 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && sets_cc0_p (last1
))
1469 last1
= beforelast1
, last2
= beforelast2
, ninsns
--;
1481 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1482 the branch instruction. This means that if we commonize the control
1483 flow before end of the basic block, the semantic remains unchanged.
1485 We may assume that there exists one edge with a common destination. */
1488 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1490 int nehedges1
= 0, nehedges2
= 0;
1491 edge fallthru1
= 0, fallthru2
= 0;
1495 /* If we performed shrink-wrapping, edges to the EXIT_BLOCK_PTR can
1496 only be distinguished for JUMP_INSNs. The two paths may differ in
1497 whether they went through the prologue. Sibcalls are fine, we know
1498 that we either didn't need or inserted an epilogue before them. */
1499 if (crtl
->shrink_wrapped
1500 && single_succ_p (bb1
) && single_succ (bb1
) == EXIT_BLOCK_PTR
1501 && !JUMP_P (BB_END (bb1
))
1502 && !(CALL_P (BB_END (bb1
)) && SIBLING_CALL_P (BB_END (bb1
))))
1505 /* If BB1 has only one successor, we may be looking at either an
1506 unconditional jump, or a fake edge to exit. */
1507 if (single_succ_p (bb1
)
1508 && (single_succ_edge (bb1
)->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1509 && (!JUMP_P (BB_END (bb1
)) || simplejump_p (BB_END (bb1
))))
1510 return (single_succ_p (bb2
)
1511 && (single_succ_edge (bb2
)->flags
1512 & (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1513 && (!JUMP_P (BB_END (bb2
)) || simplejump_p (BB_END (bb2
))));
1515 /* Match conditional jumps - this may get tricky when fallthru and branch
1516 edges are crossed. */
1517 if (EDGE_COUNT (bb1
->succs
) == 2
1518 && any_condjump_p (BB_END (bb1
))
1519 && onlyjump_p (BB_END (bb1
)))
1521 edge b1
, f1
, b2
, f2
;
1522 bool reverse
, match
;
1523 rtx set1
, set2
, cond1
, cond2
;
1524 enum rtx_code code1
, code2
;
1526 if (EDGE_COUNT (bb2
->succs
) != 2
1527 || !any_condjump_p (BB_END (bb2
))
1528 || !onlyjump_p (BB_END (bb2
)))
1531 b1
= BRANCH_EDGE (bb1
);
1532 b2
= BRANCH_EDGE (bb2
);
1533 f1
= FALLTHRU_EDGE (bb1
);
1534 f2
= FALLTHRU_EDGE (bb2
);
1536 /* Get around possible forwarders on fallthru edges. Other cases
1537 should be optimized out already. */
1538 if (FORWARDER_BLOCK_P (f1
->dest
))
1539 f1
= single_succ_edge (f1
->dest
);
1541 if (FORWARDER_BLOCK_P (f2
->dest
))
1542 f2
= single_succ_edge (f2
->dest
);
1544 /* To simplify use of this function, return false if there are
1545 unneeded forwarder blocks. These will get eliminated later
1546 during cleanup_cfg. */
1547 if (FORWARDER_BLOCK_P (f1
->dest
)
1548 || FORWARDER_BLOCK_P (f2
->dest
)
1549 || FORWARDER_BLOCK_P (b1
->dest
)
1550 || FORWARDER_BLOCK_P (b2
->dest
))
1553 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1555 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1560 set1
= pc_set (BB_END (bb1
));
1561 set2
= pc_set (BB_END (bb2
));
1562 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1563 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1566 cond1
= XEXP (SET_SRC (set1
), 0);
1567 cond2
= XEXP (SET_SRC (set2
), 0);
1568 code1
= GET_CODE (cond1
);
1570 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
1572 code2
= GET_CODE (cond2
);
1574 if (code2
== UNKNOWN
)
1577 /* Verify codes and operands match. */
1578 match
= ((code1
== code2
1579 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1580 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1581 || (code1
== swap_condition (code2
)
1582 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1584 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1587 /* If we return true, we will join the blocks. Which means that
1588 we will only have one branch prediction bit to work with. Thus
1589 we require the existing branches to have probabilities that are
1592 && optimize_bb_for_speed_p (bb1
)
1593 && optimize_bb_for_speed_p (bb2
))
1597 if (b1
->dest
== b2
->dest
)
1598 prob2
= b2
->probability
;
1600 /* Do not use f2 probability as f2 may be forwarded. */
1601 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1603 /* Fail if the difference in probabilities is greater than 50%.
1604 This rules out two well-predicted branches with opposite
1606 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1610 "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
1611 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1617 if (dump_file
&& match
)
1618 fprintf (dump_file
, "Conditionals in bb %i and %i match.\n",
1619 bb1
->index
, bb2
->index
);
1624 /* Generic case - we are seeing a computed jump, table jump or trapping
1627 /* Check whether there are tablejumps in the end of BB1 and BB2.
1628 Return true if they are identical. */
1633 if (tablejump_p (BB_END (bb1
), &label1
, &table1
)
1634 && tablejump_p (BB_END (bb2
), &label2
, &table2
)
1635 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1637 /* The labels should never be the same rtx. If they really are same
1638 the jump tables are same too. So disable crossjumping of blocks BB1
1639 and BB2 because when deleting the common insns in the end of BB1
1640 by delete_basic_block () the jump table would be deleted too. */
1641 /* If LABEL2 is referenced in BB1->END do not do anything
1642 because we would loose information when replacing
1643 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1644 if (label1
!= label2
&& !rtx_referenced_p (label2
, BB_END (bb1
)))
1646 /* Set IDENTICAL to true when the tables are identical. */
1647 bool identical
= false;
1650 p1
= PATTERN (table1
);
1651 p2
= PATTERN (table2
);
1652 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1656 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1657 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1658 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1659 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1664 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1665 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1671 replace_label_data rr
;
1674 /* Temporarily replace references to LABEL1 with LABEL2
1675 in BB1->END so that we could compare the instructions. */
1678 rr
.update_label_nuses
= false;
1679 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1681 match
= (old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
))
1683 if (dump_file
&& match
)
1685 "Tablejumps in bb %i and %i match.\n",
1686 bb1
->index
, bb2
->index
);
1688 /* Set the original label in BB1->END because when deleting
1689 a block whose end is a tablejump, the tablejump referenced
1690 from the instruction is deleted too. */
1693 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1702 /* First ensure that the instructions match. There may be many outgoing
1703 edges so this test is generally cheaper. */
1704 if (old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
)) != dir_both
)
1707 /* Search the outgoing edges, ensure that the counts do match, find possible
1708 fallthru and exception handling edges since these needs more
1710 if (EDGE_COUNT (bb1
->succs
) != EDGE_COUNT (bb2
->succs
))
1713 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1715 e2
= EDGE_SUCC (bb2
, ei
.index
);
1717 if (e1
->flags
& EDGE_EH
)
1720 if (e2
->flags
& EDGE_EH
)
1723 if (e1
->flags
& EDGE_FALLTHRU
)
1725 if (e2
->flags
& EDGE_FALLTHRU
)
1729 /* If number of edges of various types does not match, fail. */
1730 if (nehedges1
!= nehedges2
1731 || (fallthru1
!= 0) != (fallthru2
!= 0))
1734 /* fallthru edges must be forwarded to the same destination. */
1737 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1738 ? single_succ (fallthru1
->dest
): fallthru1
->dest
);
1739 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1740 ? single_succ (fallthru2
->dest
): fallthru2
->dest
);
1746 /* Ensure the same EH region. */
1748 rtx n1
= find_reg_note (BB_END (bb1
), REG_EH_REGION
, 0);
1749 rtx n2
= find_reg_note (BB_END (bb2
), REG_EH_REGION
, 0);
1754 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1758 /* The same checks as in try_crossjump_to_edge. It is required for RTL
1759 version of sequence abstraction. */
1760 FOR_EACH_EDGE (e1
, ei
, bb2
->succs
)
1764 basic_block d1
= e1
->dest
;
1766 if (FORWARDER_BLOCK_P (d1
))
1767 d1
= EDGE_SUCC (d1
, 0)->dest
;
1769 FOR_EACH_EDGE (e2
, ei
, bb1
->succs
)
1771 basic_block d2
= e2
->dest
;
1772 if (FORWARDER_BLOCK_P (d2
))
1773 d2
= EDGE_SUCC (d2
, 0)->dest
;
1785 /* Returns true if BB basic block has a preserve label. */
1788 block_has_preserve_label (basic_block bb
)
1792 && LABEL_PRESERVE_P (block_label (bb
)));
1795 /* E1 and E2 are edges with the same destination block. Search their
1796 predecessors for common code. If found, redirect control flow from
1797 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC (dir_forward),
1798 or the other way around (dir_backward). DIR specifies the allowed
1799 replacement direction. */
1802 try_crossjump_to_edge (int mode
, edge e1
, edge e2
,
1803 enum replace_direction dir
)
1806 basic_block src1
= e1
->src
, src2
= e2
->src
;
1807 basic_block redirect_to
, redirect_from
, to_remove
;
1808 basic_block osrc1
, osrc2
, redirect_edges_to
, tmp
;
1809 rtx newpos1
, newpos2
;
1813 newpos1
= newpos2
= NULL_RTX
;
1815 /* If we have partitioned hot/cold basic blocks, it is a bad idea
1816 to try this optimization.
1818 Basic block partitioning may result in some jumps that appear to
1819 be optimizable (or blocks that appear to be mergeable), but which really
1820 must be left untouched (they are required to make it safely across
1821 partition boundaries). See the comments at the top of
1822 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1824 if (flag_reorder_blocks_and_partition
&& reload_completed
)
1827 /* Search backward through forwarder blocks. We don't need to worry
1828 about multiple entry or chained forwarders, as they will be optimized
1829 away. We do this to look past the unconditional jump following a
1830 conditional jump that is required due to the current CFG shape. */
1831 if (single_pred_p (src1
)
1832 && FORWARDER_BLOCK_P (src1
))
1833 e1
= single_pred_edge (src1
), src1
= e1
->src
;
1835 if (single_pred_p (src2
)
1836 && FORWARDER_BLOCK_P (src2
))
1837 e2
= single_pred_edge (src2
), src2
= e2
->src
;
1839 /* Nothing to do if we reach ENTRY, or a common source block. */
1840 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1845 /* Seeing more than 1 forwarder blocks would confuse us later... */
1846 if (FORWARDER_BLOCK_P (e1
->dest
)
1847 && FORWARDER_BLOCK_P (single_succ (e1
->dest
)))
1850 if (FORWARDER_BLOCK_P (e2
->dest
)
1851 && FORWARDER_BLOCK_P (single_succ (e2
->dest
)))
1854 /* Likewise with dead code (possibly newly created by the other optimizations
1856 if (EDGE_COUNT (src1
->preds
) == 0 || EDGE_COUNT (src2
->preds
) == 0)
1859 /* Look for the common insn sequence, part the first ... */
1860 if (!outgoing_edges_match (mode
, src1
, src2
))
1863 /* ... and part the second. */
1864 nmatch
= flow_find_cross_jump (src1
, src2
, &newpos1
, &newpos2
, &dir
);
1868 if (newpos1
!= NULL_RTX
)
1869 src1
= BLOCK_FOR_INSN (newpos1
);
1870 if (newpos2
!= NULL_RTX
)
1871 src2
= BLOCK_FOR_INSN (newpos2
);
1873 if (dir
== dir_backward
)
1875 #define SWAP(T, X, Y) do { T tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
1876 SWAP (basic_block
, osrc1
, osrc2
);
1877 SWAP (basic_block
, src1
, src2
);
1878 SWAP (edge
, e1
, e2
);
1879 SWAP (rtx
, newpos1
, newpos2
);
1883 /* Don't proceed with the crossjump unless we found a sufficient number
1884 of matching instructions or the 'from' block was totally matched
1885 (such that its predecessors will hopefully be redirected and the
1887 if ((nmatch
< PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS
))
1888 && (newpos1
!= BB_HEAD (src1
)))
1891 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */
1892 if (block_has_preserve_label (e1
->dest
)
1893 && (e1
->flags
& EDGE_ABNORMAL
))
1896 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1898 If we have tablejumps in the end of SRC1 and SRC2
1899 they have been already compared for equivalence in outgoing_edges_match ()
1900 so replace the references to TABLE1 by references to TABLE2. */
1905 if (tablejump_p (BB_END (osrc1
), &label1
, &table1
)
1906 && tablejump_p (BB_END (osrc2
), &label2
, &table2
)
1907 && label1
!= label2
)
1909 replace_label_data rr
;
1912 /* Replace references to LABEL1 with LABEL2. */
1915 rr
.update_label_nuses
= true;
1916 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1918 /* Do not replace the label in SRC1->END because when deleting
1919 a block whose end is a tablejump, the tablejump referenced
1920 from the instruction is deleted too. */
1921 if (insn
!= BB_END (osrc1
))
1922 for_each_rtx (&insn
, replace_label
, &rr
);
1927 /* Avoid splitting if possible. We must always split when SRC2 has
1928 EH predecessor edges, or we may end up with basic blocks with both
1929 normal and EH predecessor edges. */
1930 if (newpos2
== BB_HEAD (src2
)
1931 && !(EDGE_PRED (src2
, 0)->flags
& EDGE_EH
))
1935 if (newpos2
== BB_HEAD (src2
))
1937 /* Skip possible basic block header. */
1938 if (LABEL_P (newpos2
))
1939 newpos2
= NEXT_INSN (newpos2
);
1940 while (DEBUG_INSN_P (newpos2
))
1941 newpos2
= NEXT_INSN (newpos2
);
1942 if (NOTE_P (newpos2
))
1943 newpos2
= NEXT_INSN (newpos2
);
1944 while (DEBUG_INSN_P (newpos2
))
1945 newpos2
= NEXT_INSN (newpos2
);
1949 fprintf (dump_file
, "Splitting bb %i before %i insns\n",
1950 src2
->index
, nmatch
);
1951 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
1956 "Cross jumping from bb %i to bb %i; %i common insns\n",
1957 src1
->index
, src2
->index
, nmatch
);
1959 /* We may have some registers visible through the block. */
1960 df_set_bb_dirty (redirect_to
);
1963 redirect_edges_to
= redirect_to
;
1965 redirect_edges_to
= osrc2
;
1967 /* Recompute the frequencies and counts of outgoing edges. */
1968 FOR_EACH_EDGE (s
, ei
, redirect_edges_to
->succs
)
1972 basic_block d
= s
->dest
;
1974 if (FORWARDER_BLOCK_P (d
))
1975 d
= single_succ (d
);
1977 FOR_EACH_EDGE (s2
, ei
, src1
->succs
)
1979 basic_block d2
= s2
->dest
;
1980 if (FORWARDER_BLOCK_P (d2
))
1981 d2
= single_succ (d2
);
1986 s
->count
+= s2
->count
;
1988 /* Take care to update possible forwarder blocks. We verified
1989 that there is no more than one in the chain, so we can't run
1990 into infinite loop. */
1991 if (FORWARDER_BLOCK_P (s
->dest
))
1993 single_succ_edge (s
->dest
)->count
+= s2
->count
;
1994 s
->dest
->count
+= s2
->count
;
1995 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
1998 if (FORWARDER_BLOCK_P (s2
->dest
))
2000 single_succ_edge (s2
->dest
)->count
-= s2
->count
;
2001 if (single_succ_edge (s2
->dest
)->count
< 0)
2002 single_succ_edge (s2
->dest
)->count
= 0;
2003 s2
->dest
->count
-= s2
->count
;
2004 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
2005 if (s2
->dest
->frequency
< 0)
2006 s2
->dest
->frequency
= 0;
2007 if (s2
->dest
->count
< 0)
2008 s2
->dest
->count
= 0;
2011 if (!redirect_edges_to
->frequency
&& !src1
->frequency
)
2012 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
2015 = ((s
->probability
* redirect_edges_to
->frequency
+
2016 s2
->probability
* src1
->frequency
)
2017 / (redirect_edges_to
->frequency
+ src1
->frequency
));
2020 /* Adjust count and frequency for the block. An earlier jump
2021 threading pass may have left the profile in an inconsistent
2022 state (see update_bb_profile_for_threading) so we must be
2023 prepared for overflows. */
2027 tmp
->count
+= src1
->count
;
2028 tmp
->frequency
+= src1
->frequency
;
2029 if (tmp
->frequency
> BB_FREQ_MAX
)
2030 tmp
->frequency
= BB_FREQ_MAX
;
2031 if (tmp
== redirect_edges_to
)
2033 tmp
= find_fallthru_edge (tmp
->succs
)->dest
;
2036 update_br_prob_note (redirect_edges_to
);
2038 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
2040 /* Skip possible basic block header. */
2041 if (LABEL_P (newpos1
))
2042 newpos1
= NEXT_INSN (newpos1
);
2044 while (DEBUG_INSN_P (newpos1
))
2045 newpos1
= NEXT_INSN (newpos1
);
2047 if (NOTE_INSN_BASIC_BLOCK_P (newpos1
))
2048 newpos1
= NEXT_INSN (newpos1
);
2050 while (DEBUG_INSN_P (newpos1
))
2051 newpos1
= NEXT_INSN (newpos1
);
2053 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
2054 to_remove
= single_succ (redirect_from
);
2056 redirect_edge_and_branch_force (single_succ_edge (redirect_from
), redirect_to
);
2057 delete_basic_block (to_remove
);
2059 update_forwarder_flag (redirect_from
);
2060 if (redirect_to
!= src2
)
2061 update_forwarder_flag (src2
);
2066 /* Search the predecessors of BB for common insn sequences. When found,
2067 share code between them by redirecting control flow. Return true if
2068 any changes made. */
2071 try_crossjump_bb (int mode
, basic_block bb
)
2073 edge e
, e2
, fallthru
;
2075 unsigned max
, ix
, ix2
;
2077 /* Nothing to do if there is not at least two incoming edges. */
2078 if (EDGE_COUNT (bb
->preds
) < 2)
2081 /* Don't crossjump if this block ends in a computed jump,
2082 unless we are optimizing for size. */
2083 if (optimize_bb_for_size_p (bb
)
2084 && bb
!= EXIT_BLOCK_PTR
2085 && computed_jump_p (BB_END (bb
)))
2088 /* If we are partitioning hot/cold basic blocks, we don't want to
2089 mess up unconditional or indirect jumps that cross between hot
2092 Basic block partitioning may result in some jumps that appear to
2093 be optimizable (or blocks that appear to be mergeable), but which really
2094 must be left untouched (they are required to make it safely across
2095 partition boundaries). See the comments at the top of
2096 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
2098 if (BB_PARTITION (EDGE_PRED (bb
, 0)->src
) !=
2099 BB_PARTITION (EDGE_PRED (bb
, 1)->src
)
2100 || (EDGE_PRED (bb
, 0)->flags
& EDGE_CROSSING
))
2103 /* It is always cheapest to redirect a block that ends in a branch to
2104 a block that falls through into BB, as that adds no branches to the
2105 program. We'll try that combination first. */
2107 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
2109 if (EDGE_COUNT (bb
->preds
) > max
)
2112 fallthru
= find_fallthru_edge (bb
->preds
);
2115 for (ix
= 0; ix
< EDGE_COUNT (bb
->preds
);)
2117 e
= EDGE_PRED (bb
, ix
);
2120 /* As noted above, first try with the fallthru predecessor (or, a
2121 fallthru predecessor if we are in cfglayout mode). */
2124 /* Don't combine the fallthru edge into anything else.
2125 If there is a match, we'll do it the other way around. */
2128 /* If nothing changed since the last attempt, there is nothing
2131 && !((e
->src
->flags
& BB_MODIFIED
)
2132 || (fallthru
->src
->flags
& BB_MODIFIED
)))
2135 if (try_crossjump_to_edge (mode
, e
, fallthru
, dir_forward
))
2143 /* Non-obvious work limiting check: Recognize that we're going
2144 to call try_crossjump_bb on every basic block. So if we have
2145 two blocks with lots of outgoing edges (a switch) and they
2146 share lots of common destinations, then we would do the
2147 cross-jump check once for each common destination.
2149 Now, if the blocks actually are cross-jump candidates, then
2150 all of their destinations will be shared. Which means that
2151 we only need check them for cross-jump candidacy once. We
2152 can eliminate redundant checks of crossjump(A,B) by arbitrarily
2153 choosing to do the check from the block for which the edge
2154 in question is the first successor of A. */
2155 if (EDGE_SUCC (e
->src
, 0) != e
)
2158 for (ix2
= 0; ix2
< EDGE_COUNT (bb
->preds
); ix2
++)
2160 e2
= EDGE_PRED (bb
, ix2
);
2165 /* We've already checked the fallthru edge above. */
2169 /* The "first successor" check above only prevents multiple
2170 checks of crossjump(A,B). In order to prevent redundant
2171 checks of crossjump(B,A), require that A be the block
2172 with the lowest index. */
2173 if (e
->src
->index
> e2
->src
->index
)
2176 /* If nothing changed since the last attempt, there is nothing
2179 && !((e
->src
->flags
& BB_MODIFIED
)
2180 || (e2
->src
->flags
& BB_MODIFIED
)))
2183 /* Both e and e2 are not fallthru edges, so we can crossjump in either
2185 if (try_crossjump_to_edge (mode
, e
, e2
, dir_both
))
2195 crossjumps_occured
= true;
2200 /* Search the successors of BB for common insn sequences. When found,
2201 share code between them by moving it across the basic block
2202 boundary. Return true if any changes made. */
2205 try_head_merge_bb (basic_block bb
)
2207 basic_block final_dest_bb
= NULL
;
2208 int max_match
= INT_MAX
;
2210 rtx
*headptr
, *currptr
, *nextptr
;
2211 bool changed
, moveall
;
2213 rtx e0_last_head
, cond
, move_before
;
2214 unsigned nedges
= EDGE_COUNT (bb
->succs
);
2215 rtx jump
= BB_END (bb
);
2216 regset live
, live_union
;
2218 /* Nothing to do if there is not at least two outgoing edges. */
2222 /* Don't crossjump if this block ends in a computed jump,
2223 unless we are optimizing for size. */
2224 if (optimize_bb_for_size_p (bb
)
2225 && bb
!= EXIT_BLOCK_PTR
2226 && computed_jump_p (BB_END (bb
)))
2229 cond
= get_condition (jump
, &move_before
, true, false);
2230 if (cond
== NULL_RTX
)
2233 if (reg_mentioned_p (cc0_rtx
, jump
))
2234 move_before
= prev_nonnote_nondebug_insn (jump
);
2240 for (ix
= 0; ix
< nedges
; ix
++)
2241 if (EDGE_SUCC (bb
, ix
)->dest
== EXIT_BLOCK_PTR
)
2244 for (ix
= 0; ix
< nedges
; ix
++)
2246 edge e
= EDGE_SUCC (bb
, ix
);
2247 basic_block other_bb
= e
->dest
;
2249 if (df_get_bb_dirty (other_bb
))
2251 block_was_dirty
= true;
2255 if (e
->flags
& EDGE_ABNORMAL
)
2258 /* Normally, all destination blocks must only be reachable from this
2259 block, i.e. they must have one incoming edge.
2261 There is one special case we can handle, that of multiple consecutive
2262 jumps where the first jumps to one of the targets of the second jump.
2263 This happens frequently in switch statements for default labels.
2264 The structure is as follows:
2270 jump with targets A, B, C, D...
2272 has two incoming edges, from FINAL_DEST_BB and BB
2274 In this case, we can try to move the insns through BB and into
2276 if (EDGE_COUNT (other_bb
->preds
) != 1)
2278 edge incoming_edge
, incoming_bb_other_edge
;
2281 if (final_dest_bb
!= NULL
2282 || EDGE_COUNT (other_bb
->preds
) != 2)
2285 /* We must be able to move the insns across the whole block. */
2286 move_before
= BB_HEAD (bb
);
2287 while (!NONDEBUG_INSN_P (move_before
))
2288 move_before
= NEXT_INSN (move_before
);
2290 if (EDGE_COUNT (bb
->preds
) != 1)
2292 incoming_edge
= EDGE_PRED (bb
, 0);
2293 final_dest_bb
= incoming_edge
->src
;
2294 if (EDGE_COUNT (final_dest_bb
->succs
) != 2)
2296 FOR_EACH_EDGE (incoming_bb_other_edge
, ei
, final_dest_bb
->succs
)
2297 if (incoming_bb_other_edge
!= incoming_edge
)
2299 if (incoming_bb_other_edge
->dest
!= other_bb
)
2304 e0
= EDGE_SUCC (bb
, 0);
2305 e0_last_head
= NULL_RTX
;
2308 for (ix
= 1; ix
< nedges
; ix
++)
2310 edge e
= EDGE_SUCC (bb
, ix
);
2311 rtx e0_last
, e_last
;
2314 nmatch
= flow_find_head_matching_sequence (e0
->dest
, e
->dest
,
2315 &e0_last
, &e_last
, 0);
2319 if (nmatch
< max_match
)
2322 e0_last_head
= e0_last
;
2326 /* If we matched an entire block, we probably have to avoid moving the
2329 && e0_last_head
== BB_END (e0
->dest
)
2330 && (find_reg_note (e0_last_head
, REG_EH_REGION
, 0)
2331 || control_flow_insn_p (e0_last_head
)))
2337 e0_last_head
= prev_real_insn (e0_last_head
);
2338 while (DEBUG_INSN_P (e0_last_head
));
2344 /* We must find a union of the live registers at each of the end points. */
2345 live
= BITMAP_ALLOC (NULL
);
2346 live_union
= BITMAP_ALLOC (NULL
);
2348 currptr
= XNEWVEC (rtx
, nedges
);
2349 headptr
= XNEWVEC (rtx
, nedges
);
2350 nextptr
= XNEWVEC (rtx
, nedges
);
2352 for (ix
= 0; ix
< nedges
; ix
++)
2355 basic_block merge_bb
= EDGE_SUCC (bb
, ix
)->dest
;
2356 rtx head
= BB_HEAD (merge_bb
);
2358 while (!NONDEBUG_INSN_P (head
))
2359 head
= NEXT_INSN (head
);
2363 /* Compute the end point and live information */
2364 for (j
= 1; j
< max_match
; j
++)
2366 head
= NEXT_INSN (head
);
2367 while (!NONDEBUG_INSN_P (head
));
2368 simulate_backwards_to_point (merge_bb
, live
, head
);
2369 IOR_REG_SET (live_union
, live
);
2372 /* If we're moving across two blocks, verify the validity of the
2373 first move, then adjust the target and let the loop below deal
2374 with the final move. */
2375 if (final_dest_bb
!= NULL
)
2379 moveall
= can_move_insns_across (currptr
[0], e0_last_head
, move_before
,
2380 jump
, e0
->dest
, live_union
,
2384 if (move_upto
== NULL_RTX
)
2387 while (e0_last_head
!= move_upto
)
2389 df_simulate_one_insn_backwards (e0
->dest
, e0_last_head
,
2391 e0_last_head
= PREV_INSN (e0_last_head
);
2394 if (e0_last_head
== NULL_RTX
)
2397 jump
= BB_END (final_dest_bb
);
2398 cond
= get_condition (jump
, &move_before
, true, false);
2399 if (cond
== NULL_RTX
)
2402 if (reg_mentioned_p (cc0_rtx
, jump
))
2403 move_before
= prev_nonnote_nondebug_insn (jump
);
2413 moveall
= can_move_insns_across (currptr
[0], e0_last_head
,
2414 move_before
, jump
, e0
->dest
, live_union
,
2416 if (!moveall
&& move_upto
== NULL_RTX
)
2418 if (jump
== move_before
)
2421 /* Try again, using a different insertion point. */
2425 /* Don't try moving before a cc0 user, as that may invalidate
2427 if (reg_mentioned_p (cc0_rtx
, jump
))
2434 if (final_dest_bb
&& !moveall
)
2435 /* We haven't checked whether a partial move would be OK for the first
2436 move, so we have to fail this case. */
2442 if (currptr
[0] == move_upto
)
2444 for (ix
= 0; ix
< nedges
; ix
++)
2446 rtx curr
= currptr
[ix
];
2448 curr
= NEXT_INSN (curr
);
2449 while (!NONDEBUG_INSN_P (curr
));
2454 /* If we can't currently move all of the identical insns, remember
2455 each insn after the range that we'll merge. */
2457 for (ix
= 0; ix
< nedges
; ix
++)
2459 rtx curr
= currptr
[ix
];
2461 curr
= NEXT_INSN (curr
);
2462 while (!NONDEBUG_INSN_P (curr
));
2466 reorder_insns (headptr
[0], currptr
[0], PREV_INSN (move_before
));
2467 df_set_bb_dirty (EDGE_SUCC (bb
, 0)->dest
);
2468 if (final_dest_bb
!= NULL
)
2469 df_set_bb_dirty (final_dest_bb
);
2470 df_set_bb_dirty (bb
);
2471 for (ix
= 1; ix
< nedges
; ix
++)
2473 df_set_bb_dirty (EDGE_SUCC (bb
, ix
)->dest
);
2474 delete_insn_chain (headptr
[ix
], currptr
[ix
], false);
2478 if (jump
== move_before
)
2481 /* For the unmerged insns, try a different insertion point. */
2485 /* Don't try moving before a cc0 user, as that may invalidate
2487 if (reg_mentioned_p (cc0_rtx
, jump
))
2491 for (ix
= 0; ix
< nedges
; ix
++)
2492 currptr
[ix
] = headptr
[ix
] = nextptr
[ix
];
2502 crossjumps_occured
|= changed
;
2507 /* Return true if BB contains just bb note, or bb note followed
2508 by only DEBUG_INSNs. */
2511 trivially_empty_bb_p (basic_block bb
)
2513 rtx insn
= BB_END (bb
);
2517 if (insn
== BB_HEAD (bb
))
2519 if (!DEBUG_INSN_P (insn
))
2521 insn
= PREV_INSN (insn
);
2525 /* Do simple CFG optimizations - basic block merging, simplifying of jump
2526 instructions etc. Return nonzero if changes were made. */
2529 try_optimize_cfg (int mode
)
2531 bool changed_overall
= false;
2534 basic_block bb
, b
, next
;
2536 if (mode
& (CLEANUP_CROSSJUMP
| CLEANUP_THREADING
))
2539 crossjumps_occured
= false;
2542 update_forwarder_flag (bb
);
2544 if (! targetm
.cannot_modify_jumps_p ())
2547 /* Attempt to merge blocks as made possible by edge removal. If
2548 a block has only one successor, and the successor has only
2549 one predecessor, they may be combined. */
2552 block_was_dirty
= false;
2558 "\n\ntry_optimize_cfg iteration %i\n\n",
2561 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
;)
2565 bool changed_here
= false;
2567 /* Delete trivially dead basic blocks. This is either
2568 blocks with no predecessors, or empty blocks with no
2569 successors. However if the empty block with no
2570 successors is the successor of the ENTRY_BLOCK, it is
2571 kept. This ensures that the ENTRY_BLOCK will have a
2572 successor which is a precondition for many RTL
2573 passes. Empty blocks may result from expanding
2574 __builtin_unreachable (). */
2575 if (EDGE_COUNT (b
->preds
) == 0
2576 || (EDGE_COUNT (b
->succs
) == 0
2577 && trivially_empty_bb_p (b
)
2578 && single_succ_edge (ENTRY_BLOCK_PTR
)->dest
!= b
))
2581 if (EDGE_COUNT (b
->preds
) > 0)
2586 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2589 && BARRIER_P (BB_FOOTER (b
)))
2590 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2591 if ((e
->flags
& EDGE_FALLTHRU
)
2592 && BB_FOOTER (e
->src
) == NULL
)
2596 BB_FOOTER (e
->src
) = BB_FOOTER (b
);
2597 BB_FOOTER (b
) = NULL
;
2602 BB_FOOTER (e
->src
) = emit_barrier ();
2609 rtx last
= get_last_bb_insn (b
);
2610 if (last
&& BARRIER_P (last
))
2611 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2612 if ((e
->flags
& EDGE_FALLTHRU
))
2613 emit_barrier_after (BB_END (e
->src
));
2616 delete_basic_block (b
);
2618 /* Avoid trying to remove ENTRY_BLOCK_PTR. */
2619 b
= (c
== ENTRY_BLOCK_PTR
? c
->next_bb
: c
);
2623 /* Remove code labels no longer used. */
2624 if (single_pred_p (b
)
2625 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2626 && !(single_pred_edge (b
)->flags
& EDGE_COMPLEX
)
2627 && LABEL_P (BB_HEAD (b
))
2628 /* If the previous block ends with a branch to this
2629 block, we can't delete the label. Normally this
2630 is a condjump that is yet to be simplified, but
2631 if CASE_DROPS_THRU, this can be a tablejump with
2632 some element going to the same place as the
2633 default (fallthru). */
2634 && (single_pred (b
) == ENTRY_BLOCK_PTR
2635 || !JUMP_P (BB_END (single_pred (b
)))
2636 || ! label_is_jump_target_p (BB_HEAD (b
),
2637 BB_END (single_pred (b
)))))
2639 delete_insn (BB_HEAD (b
));
2641 fprintf (dump_file
, "Deleted label in block %i.\n",
2645 /* If we fall through an empty block, we can remove it. */
2646 if (!(mode
& (CLEANUP_CFGLAYOUT
| CLEANUP_NO_INSN_DEL
))
2647 && single_pred_p (b
)
2648 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2649 && !LABEL_P (BB_HEAD (b
))
2650 && FORWARDER_BLOCK_P (b
)
2651 /* Note that forwarder_block_p true ensures that
2652 there is a successor for this block. */
2653 && (single_succ_edge (b
)->flags
& EDGE_FALLTHRU
)
2654 && n_basic_blocks
> NUM_FIXED_BLOCKS
+ 1)
2658 "Deleting fallthru block %i.\n",
2661 c
= b
->prev_bb
== ENTRY_BLOCK_PTR
? b
->next_bb
: b
->prev_bb
;
2662 redirect_edge_succ_nodup (single_pred_edge (b
),
2664 delete_basic_block (b
);
2670 /* Merge B with its single successor, if any. */
2671 if (single_succ_p (b
)
2672 && (s
= single_succ_edge (b
))
2673 && !(s
->flags
& EDGE_COMPLEX
)
2674 && (c
= s
->dest
) != EXIT_BLOCK_PTR
2675 && single_pred_p (c
)
2678 /* When not in cfg_layout mode use code aware of reordering
2679 INSN. This code possibly creates new basic blocks so it
2680 does not fit merge_blocks interface and is kept here in
2681 hope that it will become useless once more of compiler
2682 is transformed to use cfg_layout mode. */
2684 if ((mode
& CLEANUP_CFGLAYOUT
)
2685 && can_merge_blocks_p (b
, c
))
2687 merge_blocks (b
, c
);
2688 update_forwarder_flag (b
);
2689 changed_here
= true;
2691 else if (!(mode
& CLEANUP_CFGLAYOUT
)
2692 /* If the jump insn has side effects,
2693 we can't kill the edge. */
2694 && (!JUMP_P (BB_END (b
))
2695 || (reload_completed
2696 ? simplejump_p (BB_END (b
))
2697 : (onlyjump_p (BB_END (b
))
2698 && !tablejump_p (BB_END (b
),
2700 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
2703 changed_here
= true;
2707 /* Simplify branch over branch. */
2708 if ((mode
& CLEANUP_EXPENSIVE
)
2709 && !(mode
& CLEANUP_CFGLAYOUT
)
2710 && try_simplify_condjump (b
))
2711 changed_here
= true;
2713 /* If B has a single outgoing edge, but uses a
2714 non-trivial jump instruction without side-effects, we
2715 can either delete the jump entirely, or replace it
2716 with a simple unconditional jump. */
2717 if (single_succ_p (b
)
2718 && single_succ (b
) != EXIT_BLOCK_PTR
2719 && onlyjump_p (BB_END (b
))
2720 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
)
2721 && try_redirect_by_replacing_jump (single_succ_edge (b
),
2723 (mode
& CLEANUP_CFGLAYOUT
) != 0))
2725 update_forwarder_flag (b
);
2726 changed_here
= true;
2729 /* Simplify branch to branch. */
2730 if (try_forward_edges (mode
, b
))
2732 update_forwarder_flag (b
);
2733 changed_here
= true;
2736 /* Look for shared code between blocks. */
2737 if ((mode
& CLEANUP_CROSSJUMP
)
2738 && try_crossjump_bb (mode
, b
))
2739 changed_here
= true;
2741 if ((mode
& CLEANUP_CROSSJUMP
)
2742 /* This can lengthen register lifetimes. Do it only after
2745 && try_head_merge_bb (b
))
2746 changed_here
= true;
2748 /* Don't get confused by the index shift caused by
2756 if ((mode
& CLEANUP_CROSSJUMP
)
2757 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
2760 if (block_was_dirty
)
2762 /* This should only be set by head-merging. */
2763 gcc_assert (mode
& CLEANUP_CROSSJUMP
);
2767 #ifdef ENABLE_CHECKING
2769 verify_flow_info ();
2772 changed_overall
|= changed
;
2779 b
->flags
&= ~(BB_FORWARDER_BLOCK
| BB_NONTHREADABLE_BLOCK
);
2781 return changed_overall
;
2784 /* Delete all unreachable basic blocks. */
2787 delete_unreachable_blocks (void)
2789 bool changed
= false;
2790 basic_block b
, prev_bb
;
2792 find_unreachable_blocks ();
2794 /* When we're in GIMPLE mode and there may be debug insns, we should
2795 delete blocks in reverse dominator order, so as to get a chance
2796 to substitute all released DEFs into debug stmts. If we don't
2797 have dominators information, walking blocks backward gets us a
2798 better chance of retaining most debug information than
2800 if (MAY_HAVE_DEBUG_INSNS
&& current_ir_type () == IR_GIMPLE
2801 && dom_info_available_p (CDI_DOMINATORS
))
2803 for (b
= EXIT_BLOCK_PTR
->prev_bb
; b
!= ENTRY_BLOCK_PTR
; b
= prev_bb
)
2805 prev_bb
= b
->prev_bb
;
2807 if (!(b
->flags
& BB_REACHABLE
))
2809 /* Speed up the removal of blocks that don't dominate
2810 others. Walking backwards, this should be the common
2812 if (!first_dom_son (CDI_DOMINATORS
, b
))
2813 delete_basic_block (b
);
2816 VEC (basic_block
, heap
) *h
2817 = get_all_dominated_blocks (CDI_DOMINATORS
, b
);
2819 while (VEC_length (basic_block
, h
))
2821 b
= VEC_pop (basic_block
, h
);
2823 prev_bb
= b
->prev_bb
;
2825 gcc_assert (!(b
->flags
& BB_REACHABLE
));
2827 delete_basic_block (b
);
2830 VEC_free (basic_block
, heap
, h
);
2839 for (b
= EXIT_BLOCK_PTR
->prev_bb
; b
!= ENTRY_BLOCK_PTR
; b
= prev_bb
)
2841 prev_bb
= b
->prev_bb
;
2843 if (!(b
->flags
& BB_REACHABLE
))
2845 delete_basic_block (b
);
2852 tidy_fallthru_edges ();
2856 /* Delete any jump tables never referenced. We can't delete them at the
2857 time of removing tablejump insn as they are referenced by the preceding
2858 insns computing the destination, so we delay deleting and garbagecollect
2859 them once life information is computed. */
2861 delete_dead_jumptables (void)
2865 /* A dead jump table does not belong to any basic block. Scan insns
2866 between two adjacent basic blocks. */
2871 for (insn
= NEXT_INSN (BB_END (bb
));
2872 insn
&& !NOTE_INSN_BASIC_BLOCK_P (insn
);
2875 next
= NEXT_INSN (insn
);
2877 && LABEL_NUSES (insn
) == LABEL_PRESERVE_P (insn
)
2878 && JUMP_TABLE_DATA_P (next
))
2880 rtx label
= insn
, jump
= next
;
2883 fprintf (dump_file
, "Dead jumptable %i removed\n",
2886 next
= NEXT_INSN (next
);
2888 delete_insn (label
);
2895 /* Tidy the CFG by deleting unreachable code and whatnot. */
2898 cleanup_cfg (int mode
)
2900 bool changed
= false;
2902 /* Set the cfglayout mode flag here. We could update all the callers
2903 but that is just inconvenient, especially given that we eventually
2904 want to have cfglayout mode as the default. */
2905 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2906 mode
|= CLEANUP_CFGLAYOUT
;
2908 timevar_push (TV_CLEANUP_CFG
);
2909 if (delete_unreachable_blocks ())
2912 /* We've possibly created trivially dead code. Cleanup it right
2913 now to introduce more opportunities for try_optimize_cfg. */
2914 if (!(mode
& (CLEANUP_NO_INSN_DEL
))
2915 && !reload_completed
)
2916 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2921 /* To tail-merge blocks ending in the same noreturn function (e.g.
2922 a call to abort) we have to insert fake edges to exit. Do this
2923 here once. The fake edges do not interfere with any other CFG
2925 if (mode
& CLEANUP_CROSSJUMP
)
2926 add_noreturn_fake_exit_edges ();
2928 if (!dbg_cnt (cfg_cleanup
))
2931 while (try_optimize_cfg (mode
))
2933 delete_unreachable_blocks (), changed
= true;
2934 if (!(mode
& CLEANUP_NO_INSN_DEL
))
2936 /* Try to remove some trivially dead insns when doing an expensive
2937 cleanup. But delete_trivially_dead_insns doesn't work after
2938 reload (it only handles pseudos) and run_fast_dce is too costly
2939 to run in every iteration.
2941 For effective cross jumping, we really want to run a fast DCE to
2942 clean up any dead conditions, or they get in the way of performing
2945 Other transformations in cleanup_cfg are not so sensitive to dead
2946 code, so delete_trivially_dead_insns or even doing nothing at all
2948 if ((mode
& CLEANUP_EXPENSIVE
) && !reload_completed
2949 && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
2951 if ((mode
& CLEANUP_CROSSJUMP
) && crossjumps_occured
)
2958 if (mode
& CLEANUP_CROSSJUMP
)
2959 remove_fake_exit_edges ();
2961 /* Don't call delete_dead_jumptables in cfglayout mode, because
2962 that function assumes that jump tables are in the insns stream.
2963 But we also don't _have_ to delete dead jumptables in cfglayout
2964 mode because we shouldn't even be looking at things that are
2965 not in a basic block. Dead jumptables are cleaned up when
2966 going out of cfglayout mode. */
2967 if (!(mode
& CLEANUP_CFGLAYOUT
))
2968 delete_dead_jumptables ();
2970 /* ??? We probably do this way too often. */
2973 || (mode
& CLEANUP_CFG_CHANGED
)))
2976 timevar_push (TV_REPAIR_LOOPS
);
2977 /* The above doesn't preserve dominance info if available. */
2978 gcc_assert (!dom_info_available_p (CDI_DOMINATORS
));
2979 calculate_dominance_info (CDI_DOMINATORS
);
2980 changed_bbs
= BITMAP_ALLOC (NULL
);
2981 fix_loop_structure (changed_bbs
);
2982 BITMAP_FREE (changed_bbs
);
2983 free_dominance_info (CDI_DOMINATORS
);
2984 timevar_pop (TV_REPAIR_LOOPS
);
2987 timevar_pop (TV_CLEANUP_CFG
);
2995 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2997 dump_flow_info (dump_file
, dump_flags
);
2998 cleanup_cfg ((optimize
? CLEANUP_EXPENSIVE
: 0)
2999 | (flag_thread_jumps
? CLEANUP_THREADING
: 0));
3003 struct rtl_opt_pass pass_jump
=
3009 execute_jump
, /* execute */
3012 0, /* static_pass_number */
3013 TV_JUMP
, /* tv_id */
3014 0, /* properties_required */
3015 0, /* properties_provided */
3016 0, /* properties_destroyed */
3017 TODO_ggc_collect
, /* todo_flags_start */
3018 TODO_verify_rtl_sharing
, /* todo_flags_finish */
3023 execute_jump2 (void)
3025 cleanup_cfg (flag_crossjumping
? CLEANUP_CROSSJUMP
: 0);
3029 struct rtl_opt_pass pass_jump2
=
3035 execute_jump2
, /* execute */
3038 0, /* static_pass_number */
3039 TV_JUMP
, /* tv_id */
3040 0, /* properties_required */
3041 0, /* properties_provided */
3042 0, /* properties_destroyed */
3043 TODO_ggc_collect
, /* todo_flags_start */
3044 TODO_verify_rtl_sharing
, /* todo_flags_finish */