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 occurred 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 /* Protect the loop latches. */
784 if (current_loops
&& c
->loop_father
->latch
== c
)
788 update_forwarder_flag (b
);
791 fprintf (dump_file
, "Merged %d and %d without moving.\n",
794 return b
->prev_bb
== ENTRY_BLOCK_PTR
? b
: b
->prev_bb
;
797 /* Otherwise we will need to move code around. Do that only if expensive
798 transformations are allowed. */
799 else if (mode
& CLEANUP_EXPENSIVE
)
801 edge tmp_edge
, b_fallthru_edge
;
802 bool c_has_outgoing_fallthru
;
803 bool b_has_incoming_fallthru
;
805 /* Avoid overactive code motion, as the forwarder blocks should be
806 eliminated by edge redirection instead. One exception might have
807 been if B is a forwarder block and C has no fallthru edge, but
808 that should be cleaned up by bb-reorder instead. */
809 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
812 /* We must make sure to not munge nesting of lexical blocks,
813 and loop notes. This is done by squeezing out all the notes
814 and leaving them there to lie. Not ideal, but functional. */
816 tmp_edge
= find_fallthru_edge (c
->succs
);
817 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
819 tmp_edge
= find_fallthru_edge (b
->preds
);
820 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
821 b_fallthru_edge
= tmp_edge
;
824 next
= next
->prev_bb
;
826 /* Otherwise, we're going to try to move C after B. If C does
827 not have an outgoing fallthru, then it can be moved
828 immediately after B without introducing or modifying jumps. */
829 if (! c_has_outgoing_fallthru
)
831 merge_blocks_move_successor_nojumps (b
, c
);
832 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
835 /* If B does not have an incoming fallthru, then it can be moved
836 immediately before C without introducing or modifying jumps.
837 C cannot be the first block, so we do not have to worry about
838 accessing a non-existent block. */
840 if (b_has_incoming_fallthru
)
844 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
846 bb
= force_nonfallthru (b_fallthru_edge
);
848 notice_new_block (bb
);
851 merge_blocks_move_predecessor_nojumps (b
, c
);
852 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
859 /* Removes the memory attributes of MEM expression
860 if they are not equal. */
863 merge_memattrs (rtx x
, rtx y
)
872 if (x
== 0 || y
== 0)
877 if (code
!= GET_CODE (y
))
880 if (GET_MODE (x
) != GET_MODE (y
))
883 if (code
== MEM
&& MEM_ATTRS (x
) != MEM_ATTRS (y
))
887 else if (! MEM_ATTRS (y
))
891 HOST_WIDE_INT mem_size
;
893 if (MEM_ALIAS_SET (x
) != MEM_ALIAS_SET (y
))
895 set_mem_alias_set (x
, 0);
896 set_mem_alias_set (y
, 0);
899 if (! mem_expr_equal_p (MEM_EXPR (x
), MEM_EXPR (y
)))
903 clear_mem_offset (x
);
904 clear_mem_offset (y
);
906 else if (MEM_OFFSET_KNOWN_P (x
) != MEM_OFFSET_KNOWN_P (y
)
907 || (MEM_OFFSET_KNOWN_P (x
)
908 && MEM_OFFSET (x
) != MEM_OFFSET (y
)))
910 clear_mem_offset (x
);
911 clear_mem_offset (y
);
914 if (MEM_SIZE_KNOWN_P (x
) && MEM_SIZE_KNOWN_P (y
))
916 mem_size
= MAX (MEM_SIZE (x
), MEM_SIZE (y
));
917 set_mem_size (x
, mem_size
);
918 set_mem_size (y
, mem_size
);
926 set_mem_align (x
, MIN (MEM_ALIGN (x
), MEM_ALIGN (y
)));
927 set_mem_align (y
, MEM_ALIGN (x
));
931 fmt
= GET_RTX_FORMAT (code
);
932 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
937 /* Two vectors must have the same length. */
938 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
941 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
942 merge_memattrs (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
));
947 merge_memattrs (XEXP (x
, i
), XEXP (y
, i
));
954 /* Checks if patterns P1 and P2 are equivalent, apart from the possibly
955 different single sets S1 and S2. */
958 equal_different_set_p (rtx p1
, rtx s1
, rtx p2
, rtx s2
)
963 if (p1
== s1
&& p2
== s2
)
966 if (GET_CODE (p1
) != PARALLEL
|| GET_CODE (p2
) != PARALLEL
)
969 if (XVECLEN (p1
, 0) != XVECLEN (p2
, 0))
972 for (i
= 0; i
< XVECLEN (p1
, 0); i
++)
974 e1
= XVECEXP (p1
, 0, i
);
975 e2
= XVECEXP (p2
, 0, i
);
976 if (e1
== s1
&& e2
== s2
)
979 ? rtx_renumbered_equal_p (e1
, e2
) : rtx_equal_p (e1
, e2
))
988 /* Examine register notes on I1 and I2 and return:
989 - dir_forward if I1 can be replaced by I2, or
990 - dir_backward if I2 can be replaced by I1, or
991 - dir_both if both are the case. */
993 static enum replace_direction
994 can_replace_by (rtx i1
, rtx i2
)
996 rtx s1
, s2
, d1
, d2
, src1
, src2
, note1
, note2
;
999 /* Check for 2 sets. */
1000 s1
= single_set (i1
);
1001 s2
= single_set (i2
);
1002 if (s1
== NULL_RTX
|| s2
== NULL_RTX
)
1005 /* Check that the 2 sets set the same dest. */
1008 if (!(reload_completed
1009 ? rtx_renumbered_equal_p (d1
, d2
) : rtx_equal_p (d1
, d2
)))
1012 /* Find identical req_equiv or reg_equal note, which implies that the 2 sets
1013 set dest to the same value. */
1014 note1
= find_reg_equal_equiv_note (i1
);
1015 note2
= find_reg_equal_equiv_note (i2
);
1016 if (!note1
|| !note2
|| !rtx_equal_p (XEXP (note1
, 0), XEXP (note2
, 0))
1017 || !CONST_INT_P (XEXP (note1
, 0)))
1020 if (!equal_different_set_p (PATTERN (i1
), s1
, PATTERN (i2
), s2
))
1023 /* Although the 2 sets set dest to the same value, we cannot replace
1024 (set (dest) (const_int))
1027 because we don't know if the reg is live and has the same value at the
1028 location of replacement. */
1029 src1
= SET_SRC (s1
);
1030 src2
= SET_SRC (s2
);
1031 c1
= CONST_INT_P (src1
);
1032 c2
= CONST_INT_P (src2
);
1038 return dir_backward
;
1043 /* Merges directions A and B. */
1045 static enum replace_direction
1046 merge_dir (enum replace_direction a
, enum replace_direction b
)
1048 /* Implements the following table:
1067 /* Examine I1 and I2 and return:
1068 - dir_forward if I1 can be replaced by I2, or
1069 - dir_backward if I2 can be replaced by I1, or
1070 - dir_both if both are the case. */
1072 static enum replace_direction
1073 old_insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx i1
, rtx i2
)
1077 /* Verify that I1 and I2 are equivalent. */
1078 if (GET_CODE (i1
) != GET_CODE (i2
))
1081 /* __builtin_unreachable() may lead to empty blocks (ending with
1082 NOTE_INSN_BASIC_BLOCK). They may be crossjumped. */
1083 if (NOTE_INSN_BASIC_BLOCK_P (i1
) && NOTE_INSN_BASIC_BLOCK_P (i2
))
1086 /* ??? Do not allow cross-jumping between different stack levels. */
1087 p1
= find_reg_note (i1
, REG_ARGS_SIZE
, NULL
);
1088 p2
= find_reg_note (i2
, REG_ARGS_SIZE
, NULL
);
1093 if (!rtx_equal_p (p1
, p2
))
1096 /* ??? Worse, this adjustment had better be constant lest we
1097 have differing incoming stack levels. */
1098 if (!frame_pointer_needed
1099 && find_args_size_adjust (i1
) == HOST_WIDE_INT_MIN
)
1108 if (GET_CODE (p1
) != GET_CODE (p2
))
1111 /* If this is a CALL_INSN, compare register usage information.
1112 If we don't check this on stack register machines, the two
1113 CALL_INSNs might be merged leaving reg-stack.c with mismatching
1114 numbers of stack registers in the same basic block.
1115 If we don't check this on machines with delay slots, a delay slot may
1116 be filled that clobbers a parameter expected by the subroutine.
1118 ??? We take the simple route for now and assume that if they're
1119 equal, they were constructed identically.
1121 Also check for identical exception regions. */
1125 /* Ensure the same EH region. */
1126 rtx n1
= find_reg_note (i1
, REG_EH_REGION
, 0);
1127 rtx n2
= find_reg_note (i2
, REG_EH_REGION
, 0);
1132 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1135 if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
1136 CALL_INSN_FUNCTION_USAGE (i2
))
1137 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
))
1142 /* If cross_jump_death_matters is not 0, the insn's mode
1143 indicates whether or not the insn contains any stack-like
1146 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
1148 /* If register stack conversion has already been done, then
1149 death notes must also be compared before it is certain that
1150 the two instruction streams match. */
1153 HARD_REG_SET i1_regset
, i2_regset
;
1155 CLEAR_HARD_REG_SET (i1_regset
);
1156 CLEAR_HARD_REG_SET (i2_regset
);
1158 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
1159 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1160 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
1162 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
1163 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1164 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
1166 if (!hard_reg_set_equal_p (i1_regset
, i2_regset
))
1171 if (reload_completed
1172 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
1175 return can_replace_by (i1
, i2
);
1178 /* When comparing insns I1 and I2 in flow_find_cross_jump or
1179 flow_find_head_matching_sequence, ensure the notes match. */
1182 merge_notes (rtx i1
, rtx i2
)
1184 /* If the merged insns have different REG_EQUAL notes, then
1186 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1187 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1189 if (equiv1
&& !equiv2
)
1190 remove_note (i1
, equiv1
);
1191 else if (!equiv1
&& equiv2
)
1192 remove_note (i2
, equiv2
);
1193 else if (equiv1
&& equiv2
1194 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1196 remove_note (i1
, equiv1
);
1197 remove_note (i2
, equiv2
);
1201 /* Walks from I1 in BB1 backward till the next non-debug insn, and returns the
1202 resulting insn in I1, and the corresponding bb in BB1. At the head of a
1203 bb, if there is a predecessor bb that reaches this bb via fallthru, and
1204 FOLLOW_FALLTHRU, walks further in the predecessor bb and registers this in
1205 DID_FALLTHRU. Otherwise, stops at the head of the bb. */
1208 walk_to_nondebug_insn (rtx
*i1
, basic_block
*bb1
, bool follow_fallthru
,
1213 *did_fallthru
= false;
1216 while (!NONDEBUG_INSN_P (*i1
))
1218 if (*i1
!= BB_HEAD (*bb1
))
1220 *i1
= PREV_INSN (*i1
);
1224 if (!follow_fallthru
)
1227 fallthru
= find_fallthru_edge ((*bb1
)->preds
);
1228 if (!fallthru
|| fallthru
->src
== ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
)
1229 || !single_succ_p (fallthru
->src
))
1232 *bb1
= fallthru
->src
;
1233 *i1
= BB_END (*bb1
);
1234 *did_fallthru
= true;
1238 /* Look through the insns at the end of BB1 and BB2 and find the longest
1239 sequence that are either equivalent, or allow forward or backward
1240 replacement. Store the first insns for that sequence in *F1 and *F2 and
1241 return the sequence length.
1243 DIR_P indicates the allowed replacement direction on function entry, and
1244 the actual replacement direction on function exit. If NULL, only equivalent
1245 sequences are allowed.
1247 To simplify callers of this function, if the blocks match exactly,
1248 store the head of the blocks in *F1 and *F2. */
1251 flow_find_cross_jump (basic_block bb1
, basic_block bb2
, rtx
*f1
, rtx
*f2
,
1252 enum replace_direction
*dir_p
)
1254 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
1257 enum replace_direction dir
, last_dir
, afterlast_dir
;
1258 bool follow_fallthru
, did_fallthru
;
1264 afterlast_dir
= dir
;
1265 last_dir
= afterlast_dir
;
1267 /* Skip simple jumps at the end of the blocks. Complex jumps still
1268 need to be compared for equivalence, which we'll do below. */
1271 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
1273 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1276 i1
= PREV_INSN (i1
);
1281 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1284 /* Count everything except for unconditional jump as insn. */
1285 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1287 i2
= PREV_INSN (i2
);
1292 /* In the following example, we can replace all jumps to C by jumps to A.
1294 This removes 4 duplicate insns.
1295 [bb A] insn1 [bb C] insn1
1301 We could also replace all jumps to A by jumps to C, but that leaves B
1302 alive, and removes only 2 duplicate insns. In a subsequent crossjump
1303 step, all jumps to B would be replaced with jumps to the middle of C,
1304 achieving the same result with more effort.
1305 So we allow only the first possibility, which means that we don't allow
1306 fallthru in the block that's being replaced. */
1308 follow_fallthru
= dir_p
&& dir
!= dir_forward
;
1309 walk_to_nondebug_insn (&i1
, &bb1
, follow_fallthru
, &did_fallthru
);
1313 follow_fallthru
= dir_p
&& dir
!= dir_backward
;
1314 walk_to_nondebug_insn (&i2
, &bb2
, follow_fallthru
, &did_fallthru
);
1318 if (i1
== BB_HEAD (bb1
) || i2
== BB_HEAD (bb2
))
1321 dir
= merge_dir (dir
, old_insns_match_p (0, i1
, i2
));
1322 if (dir
== dir_none
|| (!dir_p
&& dir
!= dir_both
))
1325 merge_memattrs (i1
, i2
);
1327 /* Don't begin a cross-jump with a NOTE insn. */
1330 merge_notes (i1
, i2
);
1332 afterlast1
= last1
, afterlast2
= last2
;
1333 last1
= i1
, last2
= i2
;
1334 afterlast_dir
= last_dir
;
1337 if (!(GET_CODE (p1
) == USE
|| GET_CODE (p1
) == CLOBBER
))
1341 i1
= PREV_INSN (i1
);
1342 i2
= PREV_INSN (i2
);
1346 /* Don't allow the insn after a compare to be shared by
1347 cross-jumping unless the compare is also shared. */
1348 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1349 last1
= afterlast1
, last2
= afterlast2
, last_dir
= afterlast_dir
, ninsns
--;
1352 /* Include preceding notes and labels in the cross-jump. One,
1353 this may bring us to the head of the blocks as requested above.
1354 Two, it keeps line number notes as matched as may be. */
1357 bb1
= BLOCK_FOR_INSN (last1
);
1358 while (last1
!= BB_HEAD (bb1
) && !NONDEBUG_INSN_P (PREV_INSN (last1
)))
1359 last1
= PREV_INSN (last1
);
1361 if (last1
!= BB_HEAD (bb1
) && LABEL_P (PREV_INSN (last1
)))
1362 last1
= PREV_INSN (last1
);
1364 bb2
= BLOCK_FOR_INSN (last2
);
1365 while (last2
!= BB_HEAD (bb2
) && !NONDEBUG_INSN_P (PREV_INSN (last2
)))
1366 last2
= PREV_INSN (last2
);
1368 if (last2
!= BB_HEAD (bb2
) && LABEL_P (PREV_INSN (last2
)))
1369 last2
= PREV_INSN (last2
);
1380 /* Like flow_find_cross_jump, except start looking for a matching sequence from
1381 the head of the two blocks. Do not include jumps at the end.
1382 If STOP_AFTER is nonzero, stop after finding that many matching
1386 flow_find_head_matching_sequence (basic_block bb1
, basic_block bb2
, rtx
*f1
,
1387 rtx
*f2
, int stop_after
)
1389 rtx i1
, i2
, last1
, last2
, beforelast1
, beforelast2
;
1393 int nehedges1
= 0, nehedges2
= 0;
1395 FOR_EACH_EDGE (e
, ei
, bb1
->succs
)
1396 if (e
->flags
& EDGE_EH
)
1398 FOR_EACH_EDGE (e
, ei
, bb2
->succs
)
1399 if (e
->flags
& EDGE_EH
)
1404 last1
= beforelast1
= last2
= beforelast2
= NULL_RTX
;
1408 /* Ignore notes, except NOTE_INSN_EPILOGUE_BEG. */
1409 while (!NONDEBUG_INSN_P (i1
) && i1
!= BB_END (bb1
))
1411 if (NOTE_P (i1
) && NOTE_KIND (i1
) == NOTE_INSN_EPILOGUE_BEG
)
1413 i1
= NEXT_INSN (i1
);
1416 while (!NONDEBUG_INSN_P (i2
) && i2
!= BB_END (bb2
))
1418 if (NOTE_P (i2
) && NOTE_KIND (i2
) == NOTE_INSN_EPILOGUE_BEG
)
1420 i2
= NEXT_INSN (i2
);
1423 if ((i1
== BB_END (bb1
) && !NONDEBUG_INSN_P (i1
))
1424 || (i2
== BB_END (bb2
) && !NONDEBUG_INSN_P (i2
)))
1427 if (NOTE_P (i1
) || NOTE_P (i2
)
1428 || JUMP_P (i1
) || JUMP_P (i2
))
1431 /* A sanity check to make sure we're not merging insns with different
1432 effects on EH. If only one of them ends a basic block, it shouldn't
1433 have an EH edge; if both end a basic block, there should be the same
1434 number of EH edges. */
1435 if ((i1
== BB_END (bb1
) && i2
!= BB_END (bb2
)
1437 || (i2
== BB_END (bb2
) && i1
!= BB_END (bb1
)
1439 || (i1
== BB_END (bb1
) && i2
== BB_END (bb2
)
1440 && nehedges1
!= nehedges2
))
1443 if (old_insns_match_p (0, i1
, i2
) != dir_both
)
1446 merge_memattrs (i1
, i2
);
1448 /* Don't begin a cross-jump with a NOTE insn. */
1451 merge_notes (i1
, i2
);
1453 beforelast1
= last1
, beforelast2
= last2
;
1454 last1
= i1
, last2
= i2
;
1458 if (i1
== BB_END (bb1
) || i2
== BB_END (bb2
)
1459 || (stop_after
> 0 && ninsns
== stop_after
))
1462 i1
= NEXT_INSN (i1
);
1463 i2
= NEXT_INSN (i2
);
1467 /* Don't allow a compare to be shared by cross-jumping unless the insn
1468 after the compare is also shared. */
1469 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && sets_cc0_p (last1
))
1470 last1
= beforelast1
, last2
= beforelast2
, ninsns
--;
1482 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1483 the branch instruction. This means that if we commonize the control
1484 flow before end of the basic block, the semantic remains unchanged.
1486 We may assume that there exists one edge with a common destination. */
1489 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1491 int nehedges1
= 0, nehedges2
= 0;
1492 edge fallthru1
= 0, fallthru2
= 0;
1496 /* If we performed shrink-wrapping, edges to the EXIT_BLOCK_PTR can
1497 only be distinguished for JUMP_INSNs. The two paths may differ in
1498 whether they went through the prologue. Sibcalls are fine, we know
1499 that we either didn't need or inserted an epilogue before them. */
1500 if (crtl
->shrink_wrapped
1501 && single_succ_p (bb1
) && single_succ (bb1
) == EXIT_BLOCK_PTR
1502 && !JUMP_P (BB_END (bb1
))
1503 && !(CALL_P (BB_END (bb1
)) && SIBLING_CALL_P (BB_END (bb1
))))
1506 /* If BB1 has only one successor, we may be looking at either an
1507 unconditional jump, or a fake edge to exit. */
1508 if (single_succ_p (bb1
)
1509 && (single_succ_edge (bb1
)->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1510 && (!JUMP_P (BB_END (bb1
)) || simplejump_p (BB_END (bb1
))))
1511 return (single_succ_p (bb2
)
1512 && (single_succ_edge (bb2
)->flags
1513 & (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1514 && (!JUMP_P (BB_END (bb2
)) || simplejump_p (BB_END (bb2
))));
1516 /* Match conditional jumps - this may get tricky when fallthru and branch
1517 edges are crossed. */
1518 if (EDGE_COUNT (bb1
->succs
) == 2
1519 && any_condjump_p (BB_END (bb1
))
1520 && onlyjump_p (BB_END (bb1
)))
1522 edge b1
, f1
, b2
, f2
;
1523 bool reverse
, match
;
1524 rtx set1
, set2
, cond1
, cond2
;
1525 enum rtx_code code1
, code2
;
1527 if (EDGE_COUNT (bb2
->succs
) != 2
1528 || !any_condjump_p (BB_END (bb2
))
1529 || !onlyjump_p (BB_END (bb2
)))
1532 b1
= BRANCH_EDGE (bb1
);
1533 b2
= BRANCH_EDGE (bb2
);
1534 f1
= FALLTHRU_EDGE (bb1
);
1535 f2
= FALLTHRU_EDGE (bb2
);
1537 /* Get around possible forwarders on fallthru edges. Other cases
1538 should be optimized out already. */
1539 if (FORWARDER_BLOCK_P (f1
->dest
))
1540 f1
= single_succ_edge (f1
->dest
);
1542 if (FORWARDER_BLOCK_P (f2
->dest
))
1543 f2
= single_succ_edge (f2
->dest
);
1545 /* To simplify use of this function, return false if there are
1546 unneeded forwarder blocks. These will get eliminated later
1547 during cleanup_cfg. */
1548 if (FORWARDER_BLOCK_P (f1
->dest
)
1549 || FORWARDER_BLOCK_P (f2
->dest
)
1550 || FORWARDER_BLOCK_P (b1
->dest
)
1551 || FORWARDER_BLOCK_P (b2
->dest
))
1554 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1556 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1561 set1
= pc_set (BB_END (bb1
));
1562 set2
= pc_set (BB_END (bb2
));
1563 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1564 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1567 cond1
= XEXP (SET_SRC (set1
), 0);
1568 cond2
= XEXP (SET_SRC (set2
), 0);
1569 code1
= GET_CODE (cond1
);
1571 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
1573 code2
= GET_CODE (cond2
);
1575 if (code2
== UNKNOWN
)
1578 /* Verify codes and operands match. */
1579 match
= ((code1
== code2
1580 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1581 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1582 || (code1
== swap_condition (code2
)
1583 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1585 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1588 /* If we return true, we will join the blocks. Which means that
1589 we will only have one branch prediction bit to work with. Thus
1590 we require the existing branches to have probabilities that are
1593 && optimize_bb_for_speed_p (bb1
)
1594 && optimize_bb_for_speed_p (bb2
))
1598 if (b1
->dest
== b2
->dest
)
1599 prob2
= b2
->probability
;
1601 /* Do not use f2 probability as f2 may be forwarded. */
1602 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1604 /* Fail if the difference in probabilities is greater than 50%.
1605 This rules out two well-predicted branches with opposite
1607 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1611 "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
1612 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1618 if (dump_file
&& match
)
1619 fprintf (dump_file
, "Conditionals in bb %i and %i match.\n",
1620 bb1
->index
, bb2
->index
);
1625 /* Generic case - we are seeing a computed jump, table jump or trapping
1628 /* Check whether there are tablejumps in the end of BB1 and BB2.
1629 Return true if they are identical. */
1634 if (tablejump_p (BB_END (bb1
), &label1
, &table1
)
1635 && tablejump_p (BB_END (bb2
), &label2
, &table2
)
1636 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1638 /* The labels should never be the same rtx. If they really are same
1639 the jump tables are same too. So disable crossjumping of blocks BB1
1640 and BB2 because when deleting the common insns in the end of BB1
1641 by delete_basic_block () the jump table would be deleted too. */
1642 /* If LABEL2 is referenced in BB1->END do not do anything
1643 because we would loose information when replacing
1644 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1645 if (label1
!= label2
&& !rtx_referenced_p (label2
, BB_END (bb1
)))
1647 /* Set IDENTICAL to true when the tables are identical. */
1648 bool identical
= false;
1651 p1
= PATTERN (table1
);
1652 p2
= PATTERN (table2
);
1653 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1657 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1658 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1659 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1660 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1665 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1666 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1672 replace_label_data rr
;
1675 /* Temporarily replace references to LABEL1 with LABEL2
1676 in BB1->END so that we could compare the instructions. */
1679 rr
.update_label_nuses
= false;
1680 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1682 match
= (old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
))
1684 if (dump_file
&& match
)
1686 "Tablejumps in bb %i and %i match.\n",
1687 bb1
->index
, bb2
->index
);
1689 /* Set the original label in BB1->END because when deleting
1690 a block whose end is a tablejump, the tablejump referenced
1691 from the instruction is deleted too. */
1694 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1703 /* First ensure that the instructions match. There may be many outgoing
1704 edges so this test is generally cheaper. */
1705 if (old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
)) != dir_both
)
1708 /* Search the outgoing edges, ensure that the counts do match, find possible
1709 fallthru and exception handling edges since these needs more
1711 if (EDGE_COUNT (bb1
->succs
) != EDGE_COUNT (bb2
->succs
))
1714 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1716 e2
= EDGE_SUCC (bb2
, ei
.index
);
1718 if (e1
->flags
& EDGE_EH
)
1721 if (e2
->flags
& EDGE_EH
)
1724 if (e1
->flags
& EDGE_FALLTHRU
)
1726 if (e2
->flags
& EDGE_FALLTHRU
)
1730 /* If number of edges of various types does not match, fail. */
1731 if (nehedges1
!= nehedges2
1732 || (fallthru1
!= 0) != (fallthru2
!= 0))
1735 /* fallthru edges must be forwarded to the same destination. */
1738 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1739 ? single_succ (fallthru1
->dest
): fallthru1
->dest
);
1740 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1741 ? single_succ (fallthru2
->dest
): fallthru2
->dest
);
1747 /* Ensure the same EH region. */
1749 rtx n1
= find_reg_note (BB_END (bb1
), REG_EH_REGION
, 0);
1750 rtx n2
= find_reg_note (BB_END (bb2
), REG_EH_REGION
, 0);
1755 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1759 /* The same checks as in try_crossjump_to_edge. It is required for RTL
1760 version of sequence abstraction. */
1761 FOR_EACH_EDGE (e1
, ei
, bb2
->succs
)
1765 basic_block d1
= e1
->dest
;
1767 if (FORWARDER_BLOCK_P (d1
))
1768 d1
= EDGE_SUCC (d1
, 0)->dest
;
1770 FOR_EACH_EDGE (e2
, ei
, bb1
->succs
)
1772 basic_block d2
= e2
->dest
;
1773 if (FORWARDER_BLOCK_P (d2
))
1774 d2
= EDGE_SUCC (d2
, 0)->dest
;
1786 /* Returns true if BB basic block has a preserve label. */
1789 block_has_preserve_label (basic_block bb
)
1793 && LABEL_PRESERVE_P (block_label (bb
)));
1796 /* E1 and E2 are edges with the same destination block. Search their
1797 predecessors for common code. If found, redirect control flow from
1798 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC (dir_forward),
1799 or the other way around (dir_backward). DIR specifies the allowed
1800 replacement direction. */
1803 try_crossjump_to_edge (int mode
, edge e1
, edge e2
,
1804 enum replace_direction dir
)
1807 basic_block src1
= e1
->src
, src2
= e2
->src
;
1808 basic_block redirect_to
, redirect_from
, to_remove
;
1809 basic_block osrc1
, osrc2
, redirect_edges_to
, tmp
;
1810 rtx newpos1
, newpos2
;
1814 newpos1
= newpos2
= NULL_RTX
;
1816 /* If we have partitioned hot/cold basic blocks, it is a bad idea
1817 to try this optimization.
1819 Basic block partitioning may result in some jumps that appear to
1820 be optimizable (or blocks that appear to be mergeable), but which really
1821 must be left untouched (they are required to make it safely across
1822 partition boundaries). See the comments at the top of
1823 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1825 if (flag_reorder_blocks_and_partition
&& reload_completed
)
1828 /* Search backward through forwarder blocks. We don't need to worry
1829 about multiple entry or chained forwarders, as they will be optimized
1830 away. We do this to look past the unconditional jump following a
1831 conditional jump that is required due to the current CFG shape. */
1832 if (single_pred_p (src1
)
1833 && FORWARDER_BLOCK_P (src1
))
1834 e1
= single_pred_edge (src1
), src1
= e1
->src
;
1836 if (single_pred_p (src2
)
1837 && FORWARDER_BLOCK_P (src2
))
1838 e2
= single_pred_edge (src2
), src2
= e2
->src
;
1840 /* Nothing to do if we reach ENTRY, or a common source block. */
1841 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1846 /* Seeing more than 1 forwarder blocks would confuse us later... */
1847 if (FORWARDER_BLOCK_P (e1
->dest
)
1848 && FORWARDER_BLOCK_P (single_succ (e1
->dest
)))
1851 if (FORWARDER_BLOCK_P (e2
->dest
)
1852 && FORWARDER_BLOCK_P (single_succ (e2
->dest
)))
1855 /* Likewise with dead code (possibly newly created by the other optimizations
1857 if (EDGE_COUNT (src1
->preds
) == 0 || EDGE_COUNT (src2
->preds
) == 0)
1860 /* Look for the common insn sequence, part the first ... */
1861 if (!outgoing_edges_match (mode
, src1
, src2
))
1864 /* ... and part the second. */
1865 nmatch
= flow_find_cross_jump (src1
, src2
, &newpos1
, &newpos2
, &dir
);
1869 if (newpos1
!= NULL_RTX
)
1870 src1
= BLOCK_FOR_INSN (newpos1
);
1871 if (newpos2
!= NULL_RTX
)
1872 src2
= BLOCK_FOR_INSN (newpos2
);
1874 if (dir
== dir_backward
)
1876 #define SWAP(T, X, Y) do { T tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
1877 SWAP (basic_block
, osrc1
, osrc2
);
1878 SWAP (basic_block
, src1
, src2
);
1879 SWAP (edge
, e1
, e2
);
1880 SWAP (rtx
, newpos1
, newpos2
);
1884 /* Don't proceed with the crossjump unless we found a sufficient number
1885 of matching instructions or the 'from' block was totally matched
1886 (such that its predecessors will hopefully be redirected and the
1888 if ((nmatch
< PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS
))
1889 && (newpos1
!= BB_HEAD (src1
)))
1892 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */
1893 if (block_has_preserve_label (e1
->dest
)
1894 && (e1
->flags
& EDGE_ABNORMAL
))
1897 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1899 If we have tablejumps in the end of SRC1 and SRC2
1900 they have been already compared for equivalence in outgoing_edges_match ()
1901 so replace the references to TABLE1 by references to TABLE2. */
1906 if (tablejump_p (BB_END (osrc1
), &label1
, &table1
)
1907 && tablejump_p (BB_END (osrc2
), &label2
, &table2
)
1908 && label1
!= label2
)
1910 replace_label_data rr
;
1913 /* Replace references to LABEL1 with LABEL2. */
1916 rr
.update_label_nuses
= true;
1917 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1919 /* Do not replace the label in SRC1->END because when deleting
1920 a block whose end is a tablejump, the tablejump referenced
1921 from the instruction is deleted too. */
1922 if (insn
!= BB_END (osrc1
))
1923 for_each_rtx (&insn
, replace_label
, &rr
);
1928 /* Avoid splitting if possible. We must always split when SRC2 has
1929 EH predecessor edges, or we may end up with basic blocks with both
1930 normal and EH predecessor edges. */
1931 if (newpos2
== BB_HEAD (src2
)
1932 && !(EDGE_PRED (src2
, 0)->flags
& EDGE_EH
))
1936 if (newpos2
== BB_HEAD (src2
))
1938 /* Skip possible basic block header. */
1939 if (LABEL_P (newpos2
))
1940 newpos2
= NEXT_INSN (newpos2
);
1941 while (DEBUG_INSN_P (newpos2
))
1942 newpos2
= NEXT_INSN (newpos2
);
1943 if (NOTE_P (newpos2
))
1944 newpos2
= NEXT_INSN (newpos2
);
1945 while (DEBUG_INSN_P (newpos2
))
1946 newpos2
= NEXT_INSN (newpos2
);
1950 fprintf (dump_file
, "Splitting bb %i before %i insns\n",
1951 src2
->index
, nmatch
);
1952 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
1957 "Cross jumping from bb %i to bb %i; %i common insns\n",
1958 src1
->index
, src2
->index
, nmatch
);
1960 /* We may have some registers visible through the block. */
1961 df_set_bb_dirty (redirect_to
);
1964 redirect_edges_to
= redirect_to
;
1966 redirect_edges_to
= osrc2
;
1968 /* Recompute the frequencies and counts of outgoing edges. */
1969 FOR_EACH_EDGE (s
, ei
, redirect_edges_to
->succs
)
1973 basic_block d
= s
->dest
;
1975 if (FORWARDER_BLOCK_P (d
))
1976 d
= single_succ (d
);
1978 FOR_EACH_EDGE (s2
, ei
, src1
->succs
)
1980 basic_block d2
= s2
->dest
;
1981 if (FORWARDER_BLOCK_P (d2
))
1982 d2
= single_succ (d2
);
1987 s
->count
+= s2
->count
;
1989 /* Take care to update possible forwarder blocks. We verified
1990 that there is no more than one in the chain, so we can't run
1991 into infinite loop. */
1992 if (FORWARDER_BLOCK_P (s
->dest
))
1994 single_succ_edge (s
->dest
)->count
+= s2
->count
;
1995 s
->dest
->count
+= s2
->count
;
1996 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
1999 if (FORWARDER_BLOCK_P (s2
->dest
))
2001 single_succ_edge (s2
->dest
)->count
-= s2
->count
;
2002 if (single_succ_edge (s2
->dest
)->count
< 0)
2003 single_succ_edge (s2
->dest
)->count
= 0;
2004 s2
->dest
->count
-= s2
->count
;
2005 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
2006 if (s2
->dest
->frequency
< 0)
2007 s2
->dest
->frequency
= 0;
2008 if (s2
->dest
->count
< 0)
2009 s2
->dest
->count
= 0;
2012 if (!redirect_edges_to
->frequency
&& !src1
->frequency
)
2013 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
2016 = ((s
->probability
* redirect_edges_to
->frequency
+
2017 s2
->probability
* src1
->frequency
)
2018 / (redirect_edges_to
->frequency
+ src1
->frequency
));
2021 /* Adjust count and frequency for the block. An earlier jump
2022 threading pass may have left the profile in an inconsistent
2023 state (see update_bb_profile_for_threading) so we must be
2024 prepared for overflows. */
2028 tmp
->count
+= src1
->count
;
2029 tmp
->frequency
+= src1
->frequency
;
2030 if (tmp
->frequency
> BB_FREQ_MAX
)
2031 tmp
->frequency
= BB_FREQ_MAX
;
2032 if (tmp
== redirect_edges_to
)
2034 tmp
= find_fallthru_edge (tmp
->succs
)->dest
;
2037 update_br_prob_note (redirect_edges_to
);
2039 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
2041 /* Skip possible basic block header. */
2042 if (LABEL_P (newpos1
))
2043 newpos1
= NEXT_INSN (newpos1
);
2045 while (DEBUG_INSN_P (newpos1
))
2046 newpos1
= NEXT_INSN (newpos1
);
2048 if (NOTE_INSN_BASIC_BLOCK_P (newpos1
))
2049 newpos1
= NEXT_INSN (newpos1
);
2051 while (DEBUG_INSN_P (newpos1
))
2052 newpos1
= NEXT_INSN (newpos1
);
2054 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
2055 to_remove
= single_succ (redirect_from
);
2057 redirect_edge_and_branch_force (single_succ_edge (redirect_from
), redirect_to
);
2058 delete_basic_block (to_remove
);
2060 update_forwarder_flag (redirect_from
);
2061 if (redirect_to
!= src2
)
2062 update_forwarder_flag (src2
);
2067 /* Search the predecessors of BB for common insn sequences. When found,
2068 share code between them by redirecting control flow. Return true if
2069 any changes made. */
2072 try_crossjump_bb (int mode
, basic_block bb
)
2074 edge e
, e2
, fallthru
;
2076 unsigned max
, ix
, ix2
;
2078 /* Nothing to do if there is not at least two incoming edges. */
2079 if (EDGE_COUNT (bb
->preds
) < 2)
2082 /* Don't crossjump if this block ends in a computed jump,
2083 unless we are optimizing for size. */
2084 if (optimize_bb_for_size_p (bb
)
2085 && bb
!= EXIT_BLOCK_PTR
2086 && computed_jump_p (BB_END (bb
)))
2089 /* If we are partitioning hot/cold basic blocks, we don't want to
2090 mess up unconditional or indirect jumps that cross between hot
2093 Basic block partitioning may result in some jumps that appear to
2094 be optimizable (or blocks that appear to be mergeable), but which really
2095 must be left untouched (they are required to make it safely across
2096 partition boundaries). See the comments at the top of
2097 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
2099 if (BB_PARTITION (EDGE_PRED (bb
, 0)->src
) !=
2100 BB_PARTITION (EDGE_PRED (bb
, 1)->src
)
2101 || (EDGE_PRED (bb
, 0)->flags
& EDGE_CROSSING
))
2104 /* It is always cheapest to redirect a block that ends in a branch to
2105 a block that falls through into BB, as that adds no branches to the
2106 program. We'll try that combination first. */
2108 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
2110 if (EDGE_COUNT (bb
->preds
) > max
)
2113 fallthru
= find_fallthru_edge (bb
->preds
);
2116 for (ix
= 0; ix
< EDGE_COUNT (bb
->preds
);)
2118 e
= EDGE_PRED (bb
, ix
);
2121 /* As noted above, first try with the fallthru predecessor (or, a
2122 fallthru predecessor if we are in cfglayout mode). */
2125 /* Don't combine the fallthru edge into anything else.
2126 If there is a match, we'll do it the other way around. */
2129 /* If nothing changed since the last attempt, there is nothing
2132 && !((e
->src
->flags
& BB_MODIFIED
)
2133 || (fallthru
->src
->flags
& BB_MODIFIED
)))
2136 if (try_crossjump_to_edge (mode
, e
, fallthru
, dir_forward
))
2144 /* Non-obvious work limiting check: Recognize that we're going
2145 to call try_crossjump_bb on every basic block. So if we have
2146 two blocks with lots of outgoing edges (a switch) and they
2147 share lots of common destinations, then we would do the
2148 cross-jump check once for each common destination.
2150 Now, if the blocks actually are cross-jump candidates, then
2151 all of their destinations will be shared. Which means that
2152 we only need check them for cross-jump candidacy once. We
2153 can eliminate redundant checks of crossjump(A,B) by arbitrarily
2154 choosing to do the check from the block for which the edge
2155 in question is the first successor of A. */
2156 if (EDGE_SUCC (e
->src
, 0) != e
)
2159 for (ix2
= 0; ix2
< EDGE_COUNT (bb
->preds
); ix2
++)
2161 e2
= EDGE_PRED (bb
, ix2
);
2166 /* We've already checked the fallthru edge above. */
2170 /* The "first successor" check above only prevents multiple
2171 checks of crossjump(A,B). In order to prevent redundant
2172 checks of crossjump(B,A), require that A be the block
2173 with the lowest index. */
2174 if (e
->src
->index
> e2
->src
->index
)
2177 /* If nothing changed since the last attempt, there is nothing
2180 && !((e
->src
->flags
& BB_MODIFIED
)
2181 || (e2
->src
->flags
& BB_MODIFIED
)))
2184 /* Both e and e2 are not fallthru edges, so we can crossjump in either
2186 if (try_crossjump_to_edge (mode
, e
, e2
, dir_both
))
2196 crossjumps_occured
= true;
2201 /* Search the successors of BB for common insn sequences. When found,
2202 share code between them by moving it across the basic block
2203 boundary. Return true if any changes made. */
2206 try_head_merge_bb (basic_block bb
)
2208 basic_block final_dest_bb
= NULL
;
2209 int max_match
= INT_MAX
;
2211 rtx
*headptr
, *currptr
, *nextptr
;
2212 bool changed
, moveall
;
2214 rtx e0_last_head
, cond
, move_before
;
2215 unsigned nedges
= EDGE_COUNT (bb
->succs
);
2216 rtx jump
= BB_END (bb
);
2217 regset live
, live_union
;
2219 /* Nothing to do if there is not at least two outgoing edges. */
2223 /* Don't crossjump if this block ends in a computed jump,
2224 unless we are optimizing for size. */
2225 if (optimize_bb_for_size_p (bb
)
2226 && bb
!= EXIT_BLOCK_PTR
2227 && computed_jump_p (BB_END (bb
)))
2230 cond
= get_condition (jump
, &move_before
, true, false);
2231 if (cond
== NULL_RTX
)
2234 if (reg_mentioned_p (cc0_rtx
, jump
))
2235 move_before
= prev_nonnote_nondebug_insn (jump
);
2241 for (ix
= 0; ix
< nedges
; ix
++)
2242 if (EDGE_SUCC (bb
, ix
)->dest
== EXIT_BLOCK_PTR
)
2245 for (ix
= 0; ix
< nedges
; ix
++)
2247 edge e
= EDGE_SUCC (bb
, ix
);
2248 basic_block other_bb
= e
->dest
;
2250 if (df_get_bb_dirty (other_bb
))
2252 block_was_dirty
= true;
2256 if (e
->flags
& EDGE_ABNORMAL
)
2259 /* Normally, all destination blocks must only be reachable from this
2260 block, i.e. they must have one incoming edge.
2262 There is one special case we can handle, that of multiple consecutive
2263 jumps where the first jumps to one of the targets of the second jump.
2264 This happens frequently in switch statements for default labels.
2265 The structure is as follows:
2271 jump with targets A, B, C, D...
2273 has two incoming edges, from FINAL_DEST_BB and BB
2275 In this case, we can try to move the insns through BB and into
2277 if (EDGE_COUNT (other_bb
->preds
) != 1)
2279 edge incoming_edge
, incoming_bb_other_edge
;
2282 if (final_dest_bb
!= NULL
2283 || EDGE_COUNT (other_bb
->preds
) != 2)
2286 /* We must be able to move the insns across the whole block. */
2287 move_before
= BB_HEAD (bb
);
2288 while (!NONDEBUG_INSN_P (move_before
))
2289 move_before
= NEXT_INSN (move_before
);
2291 if (EDGE_COUNT (bb
->preds
) != 1)
2293 incoming_edge
= EDGE_PRED (bb
, 0);
2294 final_dest_bb
= incoming_edge
->src
;
2295 if (EDGE_COUNT (final_dest_bb
->succs
) != 2)
2297 FOR_EACH_EDGE (incoming_bb_other_edge
, ei
, final_dest_bb
->succs
)
2298 if (incoming_bb_other_edge
!= incoming_edge
)
2300 if (incoming_bb_other_edge
->dest
!= other_bb
)
2305 e0
= EDGE_SUCC (bb
, 0);
2306 e0_last_head
= NULL_RTX
;
2309 for (ix
= 1; ix
< nedges
; ix
++)
2311 edge e
= EDGE_SUCC (bb
, ix
);
2312 rtx e0_last
, e_last
;
2315 nmatch
= flow_find_head_matching_sequence (e0
->dest
, e
->dest
,
2316 &e0_last
, &e_last
, 0);
2320 if (nmatch
< max_match
)
2323 e0_last_head
= e0_last
;
2327 /* If we matched an entire block, we probably have to avoid moving the
2330 && e0_last_head
== BB_END (e0
->dest
)
2331 && (find_reg_note (e0_last_head
, REG_EH_REGION
, 0)
2332 || control_flow_insn_p (e0_last_head
)))
2338 e0_last_head
= prev_real_insn (e0_last_head
);
2339 while (DEBUG_INSN_P (e0_last_head
));
2345 /* We must find a union of the live registers at each of the end points. */
2346 live
= BITMAP_ALLOC (NULL
);
2347 live_union
= BITMAP_ALLOC (NULL
);
2349 currptr
= XNEWVEC (rtx
, nedges
);
2350 headptr
= XNEWVEC (rtx
, nedges
);
2351 nextptr
= XNEWVEC (rtx
, nedges
);
2353 for (ix
= 0; ix
< nedges
; ix
++)
2356 basic_block merge_bb
= EDGE_SUCC (bb
, ix
)->dest
;
2357 rtx head
= BB_HEAD (merge_bb
);
2359 while (!NONDEBUG_INSN_P (head
))
2360 head
= NEXT_INSN (head
);
2364 /* Compute the end point and live information */
2365 for (j
= 1; j
< max_match
; j
++)
2367 head
= NEXT_INSN (head
);
2368 while (!NONDEBUG_INSN_P (head
));
2369 simulate_backwards_to_point (merge_bb
, live
, head
);
2370 IOR_REG_SET (live_union
, live
);
2373 /* If we're moving across two blocks, verify the validity of the
2374 first move, then adjust the target and let the loop below deal
2375 with the final move. */
2376 if (final_dest_bb
!= NULL
)
2380 moveall
= can_move_insns_across (currptr
[0], e0_last_head
, move_before
,
2381 jump
, e0
->dest
, live_union
,
2385 if (move_upto
== NULL_RTX
)
2388 while (e0_last_head
!= move_upto
)
2390 df_simulate_one_insn_backwards (e0
->dest
, e0_last_head
,
2392 e0_last_head
= PREV_INSN (e0_last_head
);
2395 if (e0_last_head
== NULL_RTX
)
2398 jump
= BB_END (final_dest_bb
);
2399 cond
= get_condition (jump
, &move_before
, true, false);
2400 if (cond
== NULL_RTX
)
2403 if (reg_mentioned_p (cc0_rtx
, jump
))
2404 move_before
= prev_nonnote_nondebug_insn (jump
);
2414 moveall
= can_move_insns_across (currptr
[0], e0_last_head
,
2415 move_before
, jump
, e0
->dest
, live_union
,
2417 if (!moveall
&& move_upto
== NULL_RTX
)
2419 if (jump
== move_before
)
2422 /* Try again, using a different insertion point. */
2426 /* Don't try moving before a cc0 user, as that may invalidate
2428 if (reg_mentioned_p (cc0_rtx
, jump
))
2435 if (final_dest_bb
&& !moveall
)
2436 /* We haven't checked whether a partial move would be OK for the first
2437 move, so we have to fail this case. */
2443 if (currptr
[0] == move_upto
)
2445 for (ix
= 0; ix
< nedges
; ix
++)
2447 rtx curr
= currptr
[ix
];
2449 curr
= NEXT_INSN (curr
);
2450 while (!NONDEBUG_INSN_P (curr
));
2455 /* If we can't currently move all of the identical insns, remember
2456 each insn after the range that we'll merge. */
2458 for (ix
= 0; ix
< nedges
; ix
++)
2460 rtx curr
= currptr
[ix
];
2462 curr
= NEXT_INSN (curr
);
2463 while (!NONDEBUG_INSN_P (curr
));
2467 reorder_insns (headptr
[0], currptr
[0], PREV_INSN (move_before
));
2468 df_set_bb_dirty (EDGE_SUCC (bb
, 0)->dest
);
2469 if (final_dest_bb
!= NULL
)
2470 df_set_bb_dirty (final_dest_bb
);
2471 df_set_bb_dirty (bb
);
2472 for (ix
= 1; ix
< nedges
; ix
++)
2474 df_set_bb_dirty (EDGE_SUCC (bb
, ix
)->dest
);
2475 delete_insn_chain (headptr
[ix
], currptr
[ix
], false);
2479 if (jump
== move_before
)
2482 /* For the unmerged insns, try a different insertion point. */
2486 /* Don't try moving before a cc0 user, as that may invalidate
2488 if (reg_mentioned_p (cc0_rtx
, jump
))
2492 for (ix
= 0; ix
< nedges
; ix
++)
2493 currptr
[ix
] = headptr
[ix
] = nextptr
[ix
];
2503 crossjumps_occured
|= changed
;
2508 /* Return true if BB contains just bb note, or bb note followed
2509 by only DEBUG_INSNs. */
2512 trivially_empty_bb_p (basic_block bb
)
2514 rtx insn
= BB_END (bb
);
2518 if (insn
== BB_HEAD (bb
))
2520 if (!DEBUG_INSN_P (insn
))
2522 insn
= PREV_INSN (insn
);
2526 /* Do simple CFG optimizations - basic block merging, simplifying of jump
2527 instructions etc. Return nonzero if changes were made. */
2530 try_optimize_cfg (int mode
)
2532 bool changed_overall
= false;
2535 basic_block bb
, b
, next
;
2537 if (mode
& (CLEANUP_CROSSJUMP
| CLEANUP_THREADING
))
2540 crossjumps_occured
= false;
2543 update_forwarder_flag (bb
);
2545 if (! targetm
.cannot_modify_jumps_p ())
2548 /* Attempt to merge blocks as made possible by edge removal. If
2549 a block has only one successor, and the successor has only
2550 one predecessor, they may be combined. */
2553 block_was_dirty
= false;
2559 "\n\ntry_optimize_cfg iteration %i\n\n",
2562 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
;)
2566 bool changed_here
= false;
2568 /* Delete trivially dead basic blocks. This is either
2569 blocks with no predecessors, or empty blocks with no
2570 successors. However if the empty block with no
2571 successors is the successor of the ENTRY_BLOCK, it is
2572 kept. This ensures that the ENTRY_BLOCK will have a
2573 successor which is a precondition for many RTL
2574 passes. Empty blocks may result from expanding
2575 __builtin_unreachable (). */
2576 if (EDGE_COUNT (b
->preds
) == 0
2577 || (EDGE_COUNT (b
->succs
) == 0
2578 && trivially_empty_bb_p (b
)
2579 && single_succ_edge (ENTRY_BLOCK_PTR
)->dest
!= b
))
2582 if (EDGE_COUNT (b
->preds
) > 0)
2587 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2590 && BARRIER_P (BB_FOOTER (b
)))
2591 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2592 if ((e
->flags
& EDGE_FALLTHRU
)
2593 && BB_FOOTER (e
->src
) == NULL
)
2597 BB_FOOTER (e
->src
) = BB_FOOTER (b
);
2598 BB_FOOTER (b
) = NULL
;
2603 BB_FOOTER (e
->src
) = emit_barrier ();
2610 rtx last
= get_last_bb_insn (b
);
2611 if (last
&& BARRIER_P (last
))
2612 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2613 if ((e
->flags
& EDGE_FALLTHRU
))
2614 emit_barrier_after (BB_END (e
->src
));
2617 delete_basic_block (b
);
2619 /* Avoid trying to remove ENTRY_BLOCK_PTR. */
2620 b
= (c
== ENTRY_BLOCK_PTR
? c
->next_bb
: c
);
2624 /* Remove code labels no longer used. */
2625 if (single_pred_p (b
)
2626 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2627 && !(single_pred_edge (b
)->flags
& EDGE_COMPLEX
)
2628 && LABEL_P (BB_HEAD (b
))
2629 /* If the previous block ends with a branch to this
2630 block, we can't delete the label. Normally this
2631 is a condjump that is yet to be simplified, but
2632 if CASE_DROPS_THRU, this can be a tablejump with
2633 some element going to the same place as the
2634 default (fallthru). */
2635 && (single_pred (b
) == ENTRY_BLOCK_PTR
2636 || !JUMP_P (BB_END (single_pred (b
)))
2637 || ! label_is_jump_target_p (BB_HEAD (b
),
2638 BB_END (single_pred (b
)))))
2640 delete_insn (BB_HEAD (b
));
2642 fprintf (dump_file
, "Deleted label in block %i.\n",
2646 /* If we fall through an empty block, we can remove it. */
2647 if (!(mode
& (CLEANUP_CFGLAYOUT
| CLEANUP_NO_INSN_DEL
))
2648 && single_pred_p (b
)
2649 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2650 && !LABEL_P (BB_HEAD (b
))
2651 && FORWARDER_BLOCK_P (b
)
2652 /* Note that forwarder_block_p true ensures that
2653 there is a successor for this block. */
2654 && (single_succ_edge (b
)->flags
& EDGE_FALLTHRU
)
2655 && n_basic_blocks
> NUM_FIXED_BLOCKS
+ 1)
2659 "Deleting fallthru block %i.\n",
2662 c
= b
->prev_bb
== ENTRY_BLOCK_PTR
? b
->next_bb
: b
->prev_bb
;
2663 redirect_edge_succ_nodup (single_pred_edge (b
),
2665 delete_basic_block (b
);
2671 /* Merge B with its single successor, if any. */
2672 if (single_succ_p (b
)
2673 && (s
= single_succ_edge (b
))
2674 && !(s
->flags
& EDGE_COMPLEX
)
2675 && (c
= s
->dest
) != EXIT_BLOCK_PTR
2676 && single_pred_p (c
)
2679 /* When not in cfg_layout mode use code aware of reordering
2680 INSN. This code possibly creates new basic blocks so it
2681 does not fit merge_blocks interface and is kept here in
2682 hope that it will become useless once more of compiler
2683 is transformed to use cfg_layout mode. */
2685 if ((mode
& CLEANUP_CFGLAYOUT
)
2686 && can_merge_blocks_p (b
, c
))
2688 merge_blocks (b
, c
);
2689 update_forwarder_flag (b
);
2690 changed_here
= true;
2692 else if (!(mode
& CLEANUP_CFGLAYOUT
)
2693 /* If the jump insn has side effects,
2694 we can't kill the edge. */
2695 && (!JUMP_P (BB_END (b
))
2696 || (reload_completed
2697 ? simplejump_p (BB_END (b
))
2698 : (onlyjump_p (BB_END (b
))
2699 && !tablejump_p (BB_END (b
),
2701 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
2704 changed_here
= true;
2708 /* Simplify branch over branch. */
2709 if ((mode
& CLEANUP_EXPENSIVE
)
2710 && !(mode
& CLEANUP_CFGLAYOUT
)
2711 && try_simplify_condjump (b
))
2712 changed_here
= true;
2714 /* If B has a single outgoing edge, but uses a
2715 non-trivial jump instruction without side-effects, we
2716 can either delete the jump entirely, or replace it
2717 with a simple unconditional jump. */
2718 if (single_succ_p (b
)
2719 && single_succ (b
) != EXIT_BLOCK_PTR
2720 && onlyjump_p (BB_END (b
))
2721 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
)
2722 && try_redirect_by_replacing_jump (single_succ_edge (b
),
2724 (mode
& CLEANUP_CFGLAYOUT
) != 0))
2726 update_forwarder_flag (b
);
2727 changed_here
= true;
2730 /* Simplify branch to branch. */
2731 if (try_forward_edges (mode
, b
))
2733 update_forwarder_flag (b
);
2734 changed_here
= true;
2737 /* Look for shared code between blocks. */
2738 if ((mode
& CLEANUP_CROSSJUMP
)
2739 && try_crossjump_bb (mode
, b
))
2740 changed_here
= true;
2742 if ((mode
& CLEANUP_CROSSJUMP
)
2743 /* This can lengthen register lifetimes. Do it only after
2746 && try_head_merge_bb (b
))
2747 changed_here
= true;
2749 /* Don't get confused by the index shift caused by
2757 if ((mode
& CLEANUP_CROSSJUMP
)
2758 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
2761 if (block_was_dirty
)
2763 /* This should only be set by head-merging. */
2764 gcc_assert (mode
& CLEANUP_CROSSJUMP
);
2768 #ifdef ENABLE_CHECKING
2770 verify_flow_info ();
2773 changed_overall
|= changed
;
2780 b
->flags
&= ~(BB_FORWARDER_BLOCK
| BB_NONTHREADABLE_BLOCK
);
2782 return changed_overall
;
2785 /* Delete all unreachable basic blocks. */
2788 delete_unreachable_blocks (void)
2790 bool changed
= false;
2791 basic_block b
, prev_bb
;
2793 find_unreachable_blocks ();
2795 /* When we're in GIMPLE mode and there may be debug insns, we should
2796 delete blocks in reverse dominator order, so as to get a chance
2797 to substitute all released DEFs into debug stmts. If we don't
2798 have dominators information, walking blocks backward gets us a
2799 better chance of retaining most debug information than
2801 if (MAY_HAVE_DEBUG_STMTS
&& current_ir_type () == IR_GIMPLE
2802 && dom_info_available_p (CDI_DOMINATORS
))
2804 for (b
= EXIT_BLOCK_PTR
->prev_bb
; b
!= ENTRY_BLOCK_PTR
; b
= prev_bb
)
2806 prev_bb
= b
->prev_bb
;
2808 if (!(b
->flags
& BB_REACHABLE
))
2810 /* Speed up the removal of blocks that don't dominate
2811 others. Walking backwards, this should be the common
2813 if (!first_dom_son (CDI_DOMINATORS
, b
))
2814 delete_basic_block (b
);
2817 VEC (basic_block
, heap
) *h
2818 = get_all_dominated_blocks (CDI_DOMINATORS
, b
);
2820 while (VEC_length (basic_block
, h
))
2822 b
= VEC_pop (basic_block
, h
);
2824 prev_bb
= b
->prev_bb
;
2826 gcc_assert (!(b
->flags
& BB_REACHABLE
));
2828 delete_basic_block (b
);
2831 VEC_free (basic_block
, heap
, h
);
2840 for (b
= EXIT_BLOCK_PTR
->prev_bb
; b
!= ENTRY_BLOCK_PTR
; b
= prev_bb
)
2842 prev_bb
= b
->prev_bb
;
2844 if (!(b
->flags
& BB_REACHABLE
))
2846 delete_basic_block (b
);
2853 tidy_fallthru_edges ();
2857 /* Delete any jump tables never referenced. We can't delete them at the
2858 time of removing tablejump insn as they are referenced by the preceding
2859 insns computing the destination, so we delay deleting and garbagecollect
2860 them once life information is computed. */
2862 delete_dead_jumptables (void)
2866 /* A dead jump table does not belong to any basic block. Scan insns
2867 between two adjacent basic blocks. */
2872 for (insn
= NEXT_INSN (BB_END (bb
));
2873 insn
&& !NOTE_INSN_BASIC_BLOCK_P (insn
);
2876 next
= NEXT_INSN (insn
);
2878 && LABEL_NUSES (insn
) == LABEL_PRESERVE_P (insn
)
2879 && JUMP_TABLE_DATA_P (next
))
2881 rtx label
= insn
, jump
= next
;
2884 fprintf (dump_file
, "Dead jumptable %i removed\n",
2887 next
= NEXT_INSN (next
);
2889 delete_insn (label
);
2896 /* Tidy the CFG by deleting unreachable code and whatnot. */
2899 cleanup_cfg (int mode
)
2901 bool changed
= false;
2903 /* Set the cfglayout mode flag here. We could update all the callers
2904 but that is just inconvenient, especially given that we eventually
2905 want to have cfglayout mode as the default. */
2906 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2907 mode
|= CLEANUP_CFGLAYOUT
;
2909 timevar_push (TV_CLEANUP_CFG
);
2910 if (delete_unreachable_blocks ())
2913 /* We've possibly created trivially dead code. Cleanup it right
2914 now to introduce more opportunities for try_optimize_cfg. */
2915 if (!(mode
& (CLEANUP_NO_INSN_DEL
))
2916 && !reload_completed
)
2917 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2922 /* To tail-merge blocks ending in the same noreturn function (e.g.
2923 a call to abort) we have to insert fake edges to exit. Do this
2924 here once. The fake edges do not interfere with any other CFG
2926 if (mode
& CLEANUP_CROSSJUMP
)
2927 add_noreturn_fake_exit_edges ();
2929 if (!dbg_cnt (cfg_cleanup
))
2932 while (try_optimize_cfg (mode
))
2934 delete_unreachable_blocks (), changed
= true;
2935 if (!(mode
& CLEANUP_NO_INSN_DEL
))
2937 /* Try to remove some trivially dead insns when doing an expensive
2938 cleanup. But delete_trivially_dead_insns doesn't work after
2939 reload (it only handles pseudos) and run_fast_dce is too costly
2940 to run in every iteration.
2942 For effective cross jumping, we really want to run a fast DCE to
2943 clean up any dead conditions, or they get in the way of performing
2946 Other transformations in cleanup_cfg are not so sensitive to dead
2947 code, so delete_trivially_dead_insns or even doing nothing at all
2949 if ((mode
& CLEANUP_EXPENSIVE
) && !reload_completed
2950 && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
2952 if ((mode
& CLEANUP_CROSSJUMP
) && crossjumps_occured
)
2959 if (mode
& CLEANUP_CROSSJUMP
)
2960 remove_fake_exit_edges ();
2962 /* Don't call delete_dead_jumptables in cfglayout mode, because
2963 that function assumes that jump tables are in the insns stream.
2964 But we also don't _have_ to delete dead jumptables in cfglayout
2965 mode because we shouldn't even be looking at things that are
2966 not in a basic block. Dead jumptables are cleaned up when
2967 going out of cfglayout mode. */
2968 if (!(mode
& CLEANUP_CFGLAYOUT
))
2969 delete_dead_jumptables ();
2971 /* ??? We probably do this way too often. */
2974 || (mode
& CLEANUP_CFG_CHANGED
)))
2977 timevar_push (TV_REPAIR_LOOPS
);
2978 /* The above doesn't preserve dominance info if available. */
2979 gcc_assert (!dom_info_available_p (CDI_DOMINATORS
));
2980 calculate_dominance_info (CDI_DOMINATORS
);
2981 changed_bbs
= BITMAP_ALLOC (NULL
);
2982 fix_loop_structure (changed_bbs
);
2983 BITMAP_FREE (changed_bbs
);
2984 free_dominance_info (CDI_DOMINATORS
);
2985 timevar_pop (TV_REPAIR_LOOPS
);
2988 timevar_pop (TV_CLEANUP_CFG
);
2994 rest_of_handle_jump2 (void)
2996 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2998 dump_flow_info (dump_file
, dump_flags
);
2999 cleanup_cfg ((optimize
? CLEANUP_EXPENSIVE
: 0)
3000 | (flag_thread_jumps
? CLEANUP_THREADING
: 0));
3005 struct rtl_opt_pass pass_jump2
=
3011 rest_of_handle_jump2
, /* execute */
3014 0, /* static_pass_number */
3015 TV_JUMP
, /* tv_id */
3016 0, /* properties_required */
3017 0, /* properties_provided */
3018 0, /* properties_destroyed */
3019 TODO_ggc_collect
, /* todo_flags_start */
3020 TODO_verify_rtl_sharing
, /* todo_flags_finish */