1 /* Control flow optimization code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010, 2011
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file contains optimizer of the control flow. The main entry point is
23 cleanup_cfg. Following optimizations are performed:
25 - Unreachable blocks removal
26 - Edge forwarding (edge to the forwarder block is forwarded to its
27 successor. Simplification of the branch instruction is performed by
28 underlying infrastructure so branch can be converted to simplejump or
30 - Cross jumping (tail merging)
31 - Conditional jump-around-simplejump simplification
32 - Basic block merging. */
36 #include "coretypes.h"
39 #include "hard-reg-set.h"
43 #include "insn-config.h"
46 #include "diagnostic-core.h"
51 #include "cfglayout.h"
53 #include "tree-pass.h"
60 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
62 /* Set to true when we are running first pass of try_optimize_cfg loop. */
63 static bool first_pass
;
65 /* Set to true if crossjumps occured in the latest run of try_optimize_cfg. */
66 static bool crossjumps_occured
;
68 /* Set to true if we couldn't run an optimization due to stale liveness
69 information; we should run df_analyze to enable more opportunities. */
70 static bool block_was_dirty
;
72 static bool try_crossjump_to_edge (int, edge
, edge
);
73 static bool try_crossjump_bb (int, basic_block
);
74 static bool outgoing_edges_match (int, basic_block
, basic_block
);
75 static bool 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)
602 if (!FORWARDER_BLOCK_P (b
) && forwarder_block_p (b
))
603 b
->flags
|= BB_FORWARDER_BLOCK
;
609 if (!single_succ_p (first
))
611 gcc_assert (n
< nthreaded_edges
);
612 t
= threaded_edges
[n
++];
613 gcc_assert (t
->src
== first
);
614 update_bb_profile_for_threading (first
, edge_frequency
,
616 update_br_prob_note (first
);
620 first
->count
-= edge_count
;
621 if (first
->count
< 0)
623 first
->frequency
-= edge_frequency
;
624 if (first
->frequency
< 0)
625 first
->frequency
= 0;
626 /* It is possible that as the result of
627 threading we've removed edge as it is
628 threaded to the fallthru edge. Avoid
629 getting out of sync. */
630 if (n
< nthreaded_edges
631 && first
== threaded_edges
[n
]->src
)
633 t
= single_succ_edge (first
);
636 t
->count
-= edge_count
;
641 while (first
!= target
);
650 free (threaded_edges
);
655 /* Blocks A and B are to be merged into a single block. A has no incoming
656 fallthru edge, so it can be moved before B without adding or modifying
657 any jumps (aside from the jump from A to B). */
660 merge_blocks_move_predecessor_nojumps (basic_block a
, basic_block b
)
664 /* If we are partitioning hot/cold basic blocks, we don't want to
665 mess up unconditional or indirect jumps that cross between hot
668 Basic block partitioning may result in some jumps that appear to
669 be optimizable (or blocks that appear to be mergeable), but which really
670 must be left untouched (they are required to make it safely across
671 partition boundaries). See the comments at the top of
672 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
674 if (BB_PARTITION (a
) != BB_PARTITION (b
))
677 barrier
= next_nonnote_insn (BB_END (a
));
678 gcc_assert (BARRIER_P (barrier
));
679 delete_insn (barrier
);
681 /* Scramble the insn chain. */
682 if (BB_END (a
) != PREV_INSN (BB_HEAD (b
)))
683 reorder_insns_nobb (BB_HEAD (a
), BB_END (a
), PREV_INSN (BB_HEAD (b
)));
687 fprintf (dump_file
, "Moved block %d before %d and merged.\n",
690 /* Swap the records for the two blocks around. */
693 link_block (a
, b
->prev_bb
);
695 /* Now blocks A and B are contiguous. Merge them. */
699 /* Blocks A and B are to be merged into a single block. B has no outgoing
700 fallthru edge, so it can be moved after A without adding or modifying
701 any jumps (aside from the jump from A to B). */
704 merge_blocks_move_successor_nojumps (basic_block a
, basic_block b
)
706 rtx barrier
, real_b_end
;
709 /* If we are partitioning hot/cold basic blocks, we don't want to
710 mess up unconditional or indirect jumps that cross between hot
713 Basic block partitioning may result in some jumps that appear to
714 be optimizable (or blocks that appear to be mergeable), but which really
715 must be left untouched (they are required to make it safely across
716 partition boundaries). See the comments at the top of
717 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
719 if (BB_PARTITION (a
) != BB_PARTITION (b
))
722 real_b_end
= BB_END (b
);
724 /* If there is a jump table following block B temporarily add the jump table
725 to block B so that it will also be moved to the correct location. */
726 if (tablejump_p (BB_END (b
), &label
, &table
)
727 && prev_active_insn (label
) == BB_END (b
))
732 /* There had better have been a barrier there. Delete it. */
733 barrier
= NEXT_INSN (BB_END (b
));
734 if (barrier
&& BARRIER_P (barrier
))
735 delete_insn (barrier
);
738 /* Scramble the insn chain. */
739 reorder_insns_nobb (BB_HEAD (b
), BB_END (b
), BB_END (a
));
741 /* Restore the real end of b. */
742 BB_END (b
) = real_b_end
;
745 fprintf (dump_file
, "Moved block %d after %d and merged.\n",
748 /* Now blocks A and B are contiguous. Merge them. */
752 /* Attempt to merge basic blocks that are potentially non-adjacent.
753 Return NULL iff the attempt failed, otherwise return basic block
754 where cleanup_cfg should continue. Because the merging commonly
755 moves basic block away or introduces another optimization
756 possibility, return basic block just before B so cleanup_cfg don't
759 It may be good idea to return basic block before C in the case
760 C has been moved after B and originally appeared earlier in the
761 insn sequence, but we have no information available about the
762 relative ordering of these two. Hopefully it is not too common. */
765 merge_blocks_move (edge e
, basic_block b
, basic_block c
, int mode
)
769 /* If we are partitioning hot/cold basic blocks, we don't want to
770 mess up unconditional or indirect jumps that cross between hot
773 Basic block partitioning may result in some jumps that appear to
774 be optimizable (or blocks that appear to be mergeable), but which really
775 must be left untouched (they are required to make it safely across
776 partition boundaries). See the comments at the top of
777 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
779 if (BB_PARTITION (b
) != BB_PARTITION (c
))
782 /* If B has a fallthru edge to C, no need to move anything. */
783 if (e
->flags
& EDGE_FALLTHRU
)
785 int b_index
= b
->index
, c_index
= c
->index
;
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
))
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 set_mem_offset (x
, 0);
903 set_mem_offset (y
, 0);
905 else if (MEM_OFFSET (x
) != MEM_OFFSET (y
))
907 set_mem_offset (x
, 0);
908 set_mem_offset (y
, 0);
913 else if (!MEM_SIZE (y
))
916 mem_size
= GEN_INT (MAX (INTVAL (MEM_SIZE (x
)),
917 INTVAL (MEM_SIZE (y
))));
918 set_mem_size (x
, mem_size
);
919 set_mem_size (y
, mem_size
);
921 set_mem_align (x
, MIN (MEM_ALIGN (x
), MEM_ALIGN (y
)));
922 set_mem_align (y
, MEM_ALIGN (x
));
926 fmt
= GET_RTX_FORMAT (code
);
927 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
932 /* Two vectors must have the same length. */
933 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
936 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
937 merge_memattrs (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
));
942 merge_memattrs (XEXP (x
, i
), XEXP (y
, i
));
949 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
952 old_insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx i1
, rtx i2
)
956 /* Verify that I1 and I2 are equivalent. */
957 if (GET_CODE (i1
) != GET_CODE (i2
))
960 /* __builtin_unreachable() may lead to empty blocks (ending with
961 NOTE_INSN_BASIC_BLOCK). They may be crossjumped. */
962 if (NOTE_INSN_BASIC_BLOCK_P (i1
) && NOTE_INSN_BASIC_BLOCK_P (i2
))
968 if (GET_CODE (p1
) != GET_CODE (p2
))
971 /* If this is a CALL_INSN, compare register usage information.
972 If we don't check this on stack register machines, the two
973 CALL_INSNs might be merged leaving reg-stack.c with mismatching
974 numbers of stack registers in the same basic block.
975 If we don't check this on machines with delay slots, a delay slot may
976 be filled that clobbers a parameter expected by the subroutine.
978 ??? We take the simple route for now and assume that if they're
979 equal, they were constructed identically.
981 Also check for identical exception regions. */
985 /* Ensure the same EH region. */
986 rtx n1
= find_reg_note (i1
, REG_EH_REGION
, 0);
987 rtx n2
= find_reg_note (i2
, REG_EH_REGION
, 0);
992 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
995 if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
996 CALL_INSN_FUNCTION_USAGE (i2
))
997 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
))
1002 /* If cross_jump_death_matters is not 0, the insn's mode
1003 indicates whether or not the insn contains any stack-like
1006 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
1008 /* If register stack conversion has already been done, then
1009 death notes must also be compared before it is certain that
1010 the two instruction streams match. */
1013 HARD_REG_SET i1_regset
, i2_regset
;
1015 CLEAR_HARD_REG_SET (i1_regset
);
1016 CLEAR_HARD_REG_SET (i2_regset
);
1018 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
1019 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1020 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
1022 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
1023 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1024 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
1026 if (!hard_reg_set_equal_p (i1_regset
, i2_regset
))
1031 if (reload_completed
1032 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
1038 /* When comparing insns I1 and I2 in flow_find_cross_jump or
1039 flow_find_head_matching_sequence, ensure the notes match. */
1042 merge_notes (rtx i1
, rtx i2
)
1044 /* If the merged insns have different REG_EQUAL notes, then
1046 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1047 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1049 if (equiv1
&& !equiv2
)
1050 remove_note (i1
, equiv1
);
1051 else if (!equiv1
&& equiv2
)
1052 remove_note (i2
, equiv2
);
1053 else if (equiv1
&& equiv2
1054 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1056 remove_note (i1
, equiv1
);
1057 remove_note (i2
, equiv2
);
1061 /* Look through the insns at the end of BB1 and BB2 and find the longest
1062 sequence that are equivalent. Store the first insns for that sequence
1063 in *F1 and *F2 and return the sequence length.
1065 To simplify callers of this function, if the blocks match exactly,
1066 store the head of the blocks in *F1 and *F2. */
1069 flow_find_cross_jump (basic_block bb1
, basic_block bb2
, rtx
*f1
, rtx
*f2
)
1071 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
1074 /* Skip simple jumps at the end of the blocks. Complex jumps still
1075 need to be compared for equivalence, which we'll do below. */
1078 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
1080 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1083 i1
= PREV_INSN (i1
);
1088 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1091 /* Count everything except for unconditional jump as insn. */
1092 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1094 i2
= PREV_INSN (i2
);
1100 while (!NONDEBUG_INSN_P (i1
) && i1
!= BB_HEAD (bb1
))
1101 i1
= PREV_INSN (i1
);
1103 while (!NONDEBUG_INSN_P (i2
) && i2
!= BB_HEAD (bb2
))
1104 i2
= PREV_INSN (i2
);
1106 if (i1
== BB_HEAD (bb1
) || i2
== BB_HEAD (bb2
))
1109 if (!old_insns_match_p (0, i1
, i2
))
1112 merge_memattrs (i1
, i2
);
1114 /* Don't begin a cross-jump with a NOTE insn. */
1117 merge_notes (i1
, i2
);
1119 afterlast1
= last1
, afterlast2
= last2
;
1120 last1
= i1
, last2
= i2
;
1124 i1
= PREV_INSN (i1
);
1125 i2
= PREV_INSN (i2
);
1129 /* Don't allow the insn after a compare to be shared by
1130 cross-jumping unless the compare is also shared. */
1131 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1132 last1
= afterlast1
, last2
= afterlast2
, ninsns
--;
1135 /* Include preceding notes and labels in the cross-jump. One,
1136 this may bring us to the head of the blocks as requested above.
1137 Two, it keeps line number notes as matched as may be. */
1140 while (last1
!= BB_HEAD (bb1
) && !NONDEBUG_INSN_P (PREV_INSN (last1
)))
1141 last1
= PREV_INSN (last1
);
1143 if (last1
!= BB_HEAD (bb1
) && LABEL_P (PREV_INSN (last1
)))
1144 last1
= PREV_INSN (last1
);
1146 while (last2
!= BB_HEAD (bb2
) && !NONDEBUG_INSN_P (PREV_INSN (last2
)))
1147 last2
= PREV_INSN (last2
);
1149 if (last2
!= BB_HEAD (bb2
) && LABEL_P (PREV_INSN (last2
)))
1150 last2
= PREV_INSN (last2
);
1159 /* Like flow_find_cross_jump, except start looking for a matching sequence from
1160 the head of the two blocks. Do not include jumps at the end.
1161 If STOP_AFTER is nonzero, stop after finding that many matching
1165 flow_find_head_matching_sequence (basic_block bb1
, basic_block bb2
, rtx
*f1
,
1166 rtx
*f2
, int stop_after
)
1168 rtx i1
, i2
, last1
, last2
, beforelast1
, beforelast2
;
1172 int nehedges1
= 0, nehedges2
= 0;
1174 FOR_EACH_EDGE (e
, ei
, bb1
->succs
)
1175 if (e
->flags
& EDGE_EH
)
1177 FOR_EACH_EDGE (e
, ei
, bb2
->succs
)
1178 if (e
->flags
& EDGE_EH
)
1183 last1
= beforelast1
= last2
= beforelast2
= NULL_RTX
;
1187 /* Ignore notes, except NOTE_INSN_EPILOGUE_BEG. */
1188 while (!NONDEBUG_INSN_P (i1
) && i1
!= BB_END (bb1
))
1190 if (NOTE_P (i1
) && NOTE_KIND (i1
) == NOTE_INSN_EPILOGUE_BEG
)
1192 i1
= NEXT_INSN (i1
);
1195 while (!NONDEBUG_INSN_P (i2
) && i2
!= BB_END (bb2
))
1197 if (NOTE_P (i2
) && NOTE_KIND (i2
) == NOTE_INSN_EPILOGUE_BEG
)
1199 i2
= NEXT_INSN (i2
);
1202 if ((i1
== BB_END (bb1
) && !NONDEBUG_INSN_P (i1
))
1203 || (i2
== BB_END (bb2
) && !NONDEBUG_INSN_P (i2
)))
1206 if (NOTE_P (i1
) || NOTE_P (i2
)
1207 || JUMP_P (i1
) || JUMP_P (i2
))
1210 /* A sanity check to make sure we're not merging insns with different
1211 effects on EH. If only one of them ends a basic block, it shouldn't
1212 have an EH edge; if both end a basic block, there should be the same
1213 number of EH edges. */
1214 if ((i1
== BB_END (bb1
) && i2
!= BB_END (bb2
)
1216 || (i2
== BB_END (bb2
) && i1
!= BB_END (bb1
)
1218 || (i1
== BB_END (bb1
) && i2
== BB_END (bb2
)
1219 && nehedges1
!= nehedges2
))
1222 if (!old_insns_match_p (0, i1
, i2
))
1225 merge_memattrs (i1
, i2
);
1227 /* Don't begin a cross-jump with a NOTE insn. */
1230 merge_notes (i1
, i2
);
1232 beforelast1
= last1
, beforelast2
= last2
;
1233 last1
= i1
, last2
= i2
;
1237 if (i1
== BB_END (bb1
) || i2
== BB_END (bb2
)
1238 || (stop_after
> 0 && ninsns
== stop_after
))
1241 i1
= NEXT_INSN (i1
);
1242 i2
= NEXT_INSN (i2
);
1246 /* Don't allow a compare to be shared by cross-jumping unless the insn
1247 after the compare is also shared. */
1248 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && sets_cc0_p (last1
))
1249 last1
= beforelast1
, last2
= beforelast2
, ninsns
--;
1261 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1262 the branch instruction. This means that if we commonize the control
1263 flow before end of the basic block, the semantic remains unchanged.
1265 We may assume that there exists one edge with a common destination. */
1268 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1270 int nehedges1
= 0, nehedges2
= 0;
1271 edge fallthru1
= 0, fallthru2
= 0;
1275 /* If BB1 has only one successor, we may be looking at either an
1276 unconditional jump, or a fake edge to exit. */
1277 if (single_succ_p (bb1
)
1278 && (single_succ_edge (bb1
)->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1279 && (!JUMP_P (BB_END (bb1
)) || simplejump_p (BB_END (bb1
))))
1280 return (single_succ_p (bb2
)
1281 && (single_succ_edge (bb2
)->flags
1282 & (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1283 && (!JUMP_P (BB_END (bb2
)) || simplejump_p (BB_END (bb2
))));
1285 /* Match conditional jumps - this may get tricky when fallthru and branch
1286 edges are crossed. */
1287 if (EDGE_COUNT (bb1
->succs
) == 2
1288 && any_condjump_p (BB_END (bb1
))
1289 && onlyjump_p (BB_END (bb1
)))
1291 edge b1
, f1
, b2
, f2
;
1292 bool reverse
, match
;
1293 rtx set1
, set2
, cond1
, cond2
;
1294 enum rtx_code code1
, code2
;
1296 if (EDGE_COUNT (bb2
->succs
) != 2
1297 || !any_condjump_p (BB_END (bb2
))
1298 || !onlyjump_p (BB_END (bb2
)))
1301 b1
= BRANCH_EDGE (bb1
);
1302 b2
= BRANCH_EDGE (bb2
);
1303 f1
= FALLTHRU_EDGE (bb1
);
1304 f2
= FALLTHRU_EDGE (bb2
);
1306 /* Get around possible forwarders on fallthru edges. Other cases
1307 should be optimized out already. */
1308 if (FORWARDER_BLOCK_P (f1
->dest
))
1309 f1
= single_succ_edge (f1
->dest
);
1311 if (FORWARDER_BLOCK_P (f2
->dest
))
1312 f2
= single_succ_edge (f2
->dest
);
1314 /* To simplify use of this function, return false if there are
1315 unneeded forwarder blocks. These will get eliminated later
1316 during cleanup_cfg. */
1317 if (FORWARDER_BLOCK_P (f1
->dest
)
1318 || FORWARDER_BLOCK_P (f2
->dest
)
1319 || FORWARDER_BLOCK_P (b1
->dest
)
1320 || FORWARDER_BLOCK_P (b2
->dest
))
1323 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1325 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1330 set1
= pc_set (BB_END (bb1
));
1331 set2
= pc_set (BB_END (bb2
));
1332 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1333 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1336 cond1
= XEXP (SET_SRC (set1
), 0);
1337 cond2
= XEXP (SET_SRC (set2
), 0);
1338 code1
= GET_CODE (cond1
);
1340 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
1342 code2
= GET_CODE (cond2
);
1344 if (code2
== UNKNOWN
)
1347 /* Verify codes and operands match. */
1348 match
= ((code1
== code2
1349 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1350 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1351 || (code1
== swap_condition (code2
)
1352 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1354 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1357 /* If we return true, we will join the blocks. Which means that
1358 we will only have one branch prediction bit to work with. Thus
1359 we require the existing branches to have probabilities that are
1362 && optimize_bb_for_speed_p (bb1
)
1363 && optimize_bb_for_speed_p (bb2
))
1367 if (b1
->dest
== b2
->dest
)
1368 prob2
= b2
->probability
;
1370 /* Do not use f2 probability as f2 may be forwarded. */
1371 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1373 /* Fail if the difference in probabilities is greater than 50%.
1374 This rules out two well-predicted branches with opposite
1376 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1380 "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
1381 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1387 if (dump_file
&& match
)
1388 fprintf (dump_file
, "Conditionals in bb %i and %i match.\n",
1389 bb1
->index
, bb2
->index
);
1394 /* Generic case - we are seeing a computed jump, table jump or trapping
1397 /* Check whether there are tablejumps in the end of BB1 and BB2.
1398 Return true if they are identical. */
1403 if (tablejump_p (BB_END (bb1
), &label1
, &table1
)
1404 && tablejump_p (BB_END (bb2
), &label2
, &table2
)
1405 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1407 /* The labels should never be the same rtx. If they really are same
1408 the jump tables are same too. So disable crossjumping of blocks BB1
1409 and BB2 because when deleting the common insns in the end of BB1
1410 by delete_basic_block () the jump table would be deleted too. */
1411 /* If LABEL2 is referenced in BB1->END do not do anything
1412 because we would loose information when replacing
1413 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1414 if (label1
!= label2
&& !rtx_referenced_p (label2
, BB_END (bb1
)))
1416 /* Set IDENTICAL to true when the tables are identical. */
1417 bool identical
= false;
1420 p1
= PATTERN (table1
);
1421 p2
= PATTERN (table2
);
1422 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1426 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1427 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1428 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1429 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1434 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1435 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1441 replace_label_data rr
;
1444 /* Temporarily replace references to LABEL1 with LABEL2
1445 in BB1->END so that we could compare the instructions. */
1448 rr
.update_label_nuses
= false;
1449 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1451 match
= old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
));
1452 if (dump_file
&& match
)
1454 "Tablejumps in bb %i and %i match.\n",
1455 bb1
->index
, bb2
->index
);
1457 /* Set the original label in BB1->END because when deleting
1458 a block whose end is a tablejump, the tablejump referenced
1459 from the instruction is deleted too. */
1462 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1471 /* First ensure that the instructions match. There may be many outgoing
1472 edges so this test is generally cheaper. */
1473 if (!old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
)))
1476 /* Search the outgoing edges, ensure that the counts do match, find possible
1477 fallthru and exception handling edges since these needs more
1479 if (EDGE_COUNT (bb1
->succs
) != EDGE_COUNT (bb2
->succs
))
1482 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1484 e2
= EDGE_SUCC (bb2
, ei
.index
);
1486 if (e1
->flags
& EDGE_EH
)
1489 if (e2
->flags
& EDGE_EH
)
1492 if (e1
->flags
& EDGE_FALLTHRU
)
1494 if (e2
->flags
& EDGE_FALLTHRU
)
1498 /* If number of edges of various types does not match, fail. */
1499 if (nehedges1
!= nehedges2
1500 || (fallthru1
!= 0) != (fallthru2
!= 0))
1503 /* fallthru edges must be forwarded to the same destination. */
1506 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1507 ? single_succ (fallthru1
->dest
): fallthru1
->dest
);
1508 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1509 ? single_succ (fallthru2
->dest
): fallthru2
->dest
);
1515 /* Ensure the same EH region. */
1517 rtx n1
= find_reg_note (BB_END (bb1
), REG_EH_REGION
, 0);
1518 rtx n2
= find_reg_note (BB_END (bb2
), REG_EH_REGION
, 0);
1523 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1527 /* The same checks as in try_crossjump_to_edge. It is required for RTL
1528 version of sequence abstraction. */
1529 FOR_EACH_EDGE (e1
, ei
, bb2
->succs
)
1533 basic_block d1
= e1
->dest
;
1535 if (FORWARDER_BLOCK_P (d1
))
1536 d1
= EDGE_SUCC (d1
, 0)->dest
;
1538 FOR_EACH_EDGE (e2
, ei
, bb1
->succs
)
1540 basic_block d2
= e2
->dest
;
1541 if (FORWARDER_BLOCK_P (d2
))
1542 d2
= EDGE_SUCC (d2
, 0)->dest
;
1554 /* Returns true if BB basic block has a preserve label. */
1557 block_has_preserve_label (basic_block bb
)
1561 && LABEL_PRESERVE_P (block_label (bb
)));
1564 /* E1 and E2 are edges with the same destination block. Search their
1565 predecessors for common code. If found, redirect control flow from
1566 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1569 try_crossjump_to_edge (int mode
, edge e1
, edge e2
)
1572 basic_block src1
= e1
->src
, src2
= e2
->src
;
1573 basic_block redirect_to
, redirect_from
, to_remove
;
1574 rtx newpos1
, newpos2
;
1578 newpos1
= newpos2
= NULL_RTX
;
1580 /* If we have partitioned hot/cold basic blocks, it is a bad idea
1581 to try this optimization.
1583 Basic block partitioning may result in some jumps that appear to
1584 be optimizable (or blocks that appear to be mergeable), but which really
1585 must be left untouched (they are required to make it safely across
1586 partition boundaries). See the comments at the top of
1587 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1589 if (flag_reorder_blocks_and_partition
&& reload_completed
)
1592 /* Search backward through forwarder blocks. We don't need to worry
1593 about multiple entry or chained forwarders, as they will be optimized
1594 away. We do this to look past the unconditional jump following a
1595 conditional jump that is required due to the current CFG shape. */
1596 if (single_pred_p (src1
)
1597 && FORWARDER_BLOCK_P (src1
))
1598 e1
= single_pred_edge (src1
), src1
= e1
->src
;
1600 if (single_pred_p (src2
)
1601 && FORWARDER_BLOCK_P (src2
))
1602 e2
= single_pred_edge (src2
), src2
= e2
->src
;
1604 /* Nothing to do if we reach ENTRY, or a common source block. */
1605 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1610 /* Seeing more than 1 forwarder blocks would confuse us later... */
1611 if (FORWARDER_BLOCK_P (e1
->dest
)
1612 && FORWARDER_BLOCK_P (single_succ (e1
->dest
)))
1615 if (FORWARDER_BLOCK_P (e2
->dest
)
1616 && FORWARDER_BLOCK_P (single_succ (e2
->dest
)))
1619 /* Likewise with dead code (possibly newly created by the other optimizations
1621 if (EDGE_COUNT (src1
->preds
) == 0 || EDGE_COUNT (src2
->preds
) == 0)
1624 /* Look for the common insn sequence, part the first ... */
1625 if (!outgoing_edges_match (mode
, src1
, src2
))
1628 /* ... and part the second. */
1629 nmatch
= flow_find_cross_jump (src1
, src2
, &newpos1
, &newpos2
);
1631 /* Don't proceed with the crossjump unless we found a sufficient number
1632 of matching instructions or the 'from' block was totally matched
1633 (such that its predecessors will hopefully be redirected and the
1635 if ((nmatch
< PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS
))
1636 && (newpos1
!= BB_HEAD (src1
)))
1639 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */
1640 if (block_has_preserve_label (e1
->dest
)
1641 && (e1
->flags
& EDGE_ABNORMAL
))
1644 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1646 If we have tablejumps in the end of SRC1 and SRC2
1647 they have been already compared for equivalence in outgoing_edges_match ()
1648 so replace the references to TABLE1 by references to TABLE2. */
1653 if (tablejump_p (BB_END (src1
), &label1
, &table1
)
1654 && tablejump_p (BB_END (src2
), &label2
, &table2
)
1655 && label1
!= label2
)
1657 replace_label_data rr
;
1660 /* Replace references to LABEL1 with LABEL2. */
1663 rr
.update_label_nuses
= true;
1664 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1666 /* Do not replace the label in SRC1->END because when deleting
1667 a block whose end is a tablejump, the tablejump referenced
1668 from the instruction is deleted too. */
1669 if (insn
!= BB_END (src1
))
1670 for_each_rtx (&insn
, replace_label
, &rr
);
1675 /* Avoid splitting if possible. We must always split when SRC2 has
1676 EH predecessor edges, or we may end up with basic blocks with both
1677 normal and EH predecessor edges. */
1678 if (newpos2
== BB_HEAD (src2
)
1679 && !(EDGE_PRED (src2
, 0)->flags
& EDGE_EH
))
1683 if (newpos2
== BB_HEAD (src2
))
1685 /* Skip possible basic block header. */
1686 if (LABEL_P (newpos2
))
1687 newpos2
= NEXT_INSN (newpos2
);
1688 while (DEBUG_INSN_P (newpos2
))
1689 newpos2
= NEXT_INSN (newpos2
);
1690 if (NOTE_P (newpos2
))
1691 newpos2
= NEXT_INSN (newpos2
);
1692 while (DEBUG_INSN_P (newpos2
))
1693 newpos2
= NEXT_INSN (newpos2
);
1697 fprintf (dump_file
, "Splitting bb %i before %i insns\n",
1698 src2
->index
, nmatch
);
1699 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
1704 "Cross jumping from bb %i to bb %i; %i common insns\n",
1705 src1
->index
, src2
->index
, nmatch
);
1707 /* We may have some registers visible through the block. */
1708 df_set_bb_dirty (redirect_to
);
1710 /* Recompute the frequencies and counts of outgoing edges. */
1711 FOR_EACH_EDGE (s
, ei
, redirect_to
->succs
)
1715 basic_block d
= s
->dest
;
1717 if (FORWARDER_BLOCK_P (d
))
1718 d
= single_succ (d
);
1720 FOR_EACH_EDGE (s2
, ei
, src1
->succs
)
1722 basic_block d2
= s2
->dest
;
1723 if (FORWARDER_BLOCK_P (d2
))
1724 d2
= single_succ (d2
);
1729 s
->count
+= s2
->count
;
1731 /* Take care to update possible forwarder blocks. We verified
1732 that there is no more than one in the chain, so we can't run
1733 into infinite loop. */
1734 if (FORWARDER_BLOCK_P (s
->dest
))
1736 single_succ_edge (s
->dest
)->count
+= s2
->count
;
1737 s
->dest
->count
+= s2
->count
;
1738 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
1741 if (FORWARDER_BLOCK_P (s2
->dest
))
1743 single_succ_edge (s2
->dest
)->count
-= s2
->count
;
1744 if (single_succ_edge (s2
->dest
)->count
< 0)
1745 single_succ_edge (s2
->dest
)->count
= 0;
1746 s2
->dest
->count
-= s2
->count
;
1747 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
1748 if (s2
->dest
->frequency
< 0)
1749 s2
->dest
->frequency
= 0;
1750 if (s2
->dest
->count
< 0)
1751 s2
->dest
->count
= 0;
1754 if (!redirect_to
->frequency
&& !src1
->frequency
)
1755 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
1758 = ((s
->probability
* redirect_to
->frequency
+
1759 s2
->probability
* src1
->frequency
)
1760 / (redirect_to
->frequency
+ src1
->frequency
));
1763 /* Adjust count and frequency for the block. An earlier jump
1764 threading pass may have left the profile in an inconsistent
1765 state (see update_bb_profile_for_threading) so we must be
1766 prepared for overflows. */
1767 redirect_to
->count
+= src1
->count
;
1768 redirect_to
->frequency
+= src1
->frequency
;
1769 if (redirect_to
->frequency
> BB_FREQ_MAX
)
1770 redirect_to
->frequency
= BB_FREQ_MAX
;
1771 update_br_prob_note (redirect_to
);
1773 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1775 /* Skip possible basic block header. */
1776 if (LABEL_P (newpos1
))
1777 newpos1
= NEXT_INSN (newpos1
);
1779 while (DEBUG_INSN_P (newpos1
))
1780 newpos1
= NEXT_INSN (newpos1
);
1782 if (NOTE_INSN_BASIC_BLOCK_P (newpos1
))
1783 newpos1
= NEXT_INSN (newpos1
);
1785 while (DEBUG_INSN_P (newpos1
))
1786 newpos1
= NEXT_INSN (newpos1
);
1788 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
1789 to_remove
= single_succ (redirect_from
);
1791 redirect_edge_and_branch_force (single_succ_edge (redirect_from
), redirect_to
);
1792 delete_basic_block (to_remove
);
1794 update_forwarder_flag (redirect_from
);
1795 if (redirect_to
!= src2
)
1796 update_forwarder_flag (src2
);
1801 /* Search the predecessors of BB for common insn sequences. When found,
1802 share code between them by redirecting control flow. Return true if
1803 any changes made. */
1806 try_crossjump_bb (int mode
, basic_block bb
)
1808 edge e
, e2
, fallthru
;
1810 unsigned max
, ix
, ix2
;
1811 basic_block ev
, ev2
;
1813 /* Nothing to do if there is not at least two incoming edges. */
1814 if (EDGE_COUNT (bb
->preds
) < 2)
1817 /* Don't crossjump if this block ends in a computed jump,
1818 unless we are optimizing for size. */
1819 if (optimize_bb_for_size_p (bb
)
1820 && bb
!= EXIT_BLOCK_PTR
1821 && computed_jump_p (BB_END (bb
)))
1824 /* If we are partitioning hot/cold basic blocks, we don't want to
1825 mess up unconditional or indirect jumps that cross between hot
1828 Basic block partitioning may result in some jumps that appear to
1829 be optimizable (or blocks that appear to be mergeable), but which really
1830 must be left untouched (they are required to make it safely across
1831 partition boundaries). See the comments at the top of
1832 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1834 if (BB_PARTITION (EDGE_PRED (bb
, 0)->src
) !=
1835 BB_PARTITION (EDGE_PRED (bb
, 1)->src
)
1836 || (EDGE_PRED (bb
, 0)->flags
& EDGE_CROSSING
))
1839 /* It is always cheapest to redirect a block that ends in a branch to
1840 a block that falls through into BB, as that adds no branches to the
1841 program. We'll try that combination first. */
1843 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
1845 if (EDGE_COUNT (bb
->preds
) > max
)
1848 fallthru
= find_fallthru_edge (bb
->preds
);
1851 for (ix
= 0, ev
= bb
; ix
< EDGE_COUNT (ev
->preds
); )
1853 e
= EDGE_PRED (ev
, ix
);
1856 /* As noted above, first try with the fallthru predecessor (or, a
1857 fallthru predecessor if we are in cfglayout mode). */
1860 /* Don't combine the fallthru edge into anything else.
1861 If there is a match, we'll do it the other way around. */
1864 /* If nothing changed since the last attempt, there is nothing
1867 && !((e
->src
->flags
& BB_MODIFIED
)
1868 || (fallthru
->src
->flags
& BB_MODIFIED
)))
1871 if (try_crossjump_to_edge (mode
, e
, fallthru
))
1880 /* Non-obvious work limiting check: Recognize that we're going
1881 to call try_crossjump_bb on every basic block. So if we have
1882 two blocks with lots of outgoing edges (a switch) and they
1883 share lots of common destinations, then we would do the
1884 cross-jump check once for each common destination.
1886 Now, if the blocks actually are cross-jump candidates, then
1887 all of their destinations will be shared. Which means that
1888 we only need check them for cross-jump candidacy once. We
1889 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1890 choosing to do the check from the block for which the edge
1891 in question is the first successor of A. */
1892 if (EDGE_SUCC (e
->src
, 0) != e
)
1895 for (ix2
= 0, ev2
= bb
; ix2
< EDGE_COUNT (ev2
->preds
); )
1897 e2
= EDGE_PRED (ev2
, ix2
);
1903 /* We've already checked the fallthru edge above. */
1907 /* The "first successor" check above only prevents multiple
1908 checks of crossjump(A,B). In order to prevent redundant
1909 checks of crossjump(B,A), require that A be the block
1910 with the lowest index. */
1911 if (e
->src
->index
> e2
->src
->index
)
1914 /* If nothing changed since the last attempt, there is nothing
1917 && !((e
->src
->flags
& BB_MODIFIED
)
1918 || (e2
->src
->flags
& BB_MODIFIED
)))
1921 if (try_crossjump_to_edge (mode
, e
, e2
))
1932 crossjumps_occured
= true;
1937 /* Search the successors of BB for common insn sequences. When found,
1938 share code between them by moving it across the basic block
1939 boundary. Return true if any changes made. */
1942 try_head_merge_bb (basic_block bb
)
1944 basic_block final_dest_bb
= NULL
;
1945 int max_match
= INT_MAX
;
1947 rtx
*headptr
, *currptr
, *nextptr
;
1948 bool changed
, moveall
;
1950 rtx e0_last_head
, cond
, move_before
;
1951 unsigned nedges
= EDGE_COUNT (bb
->succs
);
1952 rtx jump
= BB_END (bb
);
1953 regset live
, live_union
;
1955 /* Nothing to do if there is not at least two outgoing edges. */
1959 /* Don't crossjump if this block ends in a computed jump,
1960 unless we are optimizing for size. */
1961 if (optimize_bb_for_size_p (bb
)
1962 && bb
!= EXIT_BLOCK_PTR
1963 && computed_jump_p (BB_END (bb
)))
1966 cond
= get_condition (jump
, &move_before
, true, false);
1967 if (cond
== NULL_RTX
)
1970 for (ix
= 0; ix
< nedges
; ix
++)
1971 if (EDGE_SUCC (bb
, ix
)->dest
== EXIT_BLOCK_PTR
)
1974 for (ix
= 0; ix
< nedges
; ix
++)
1976 edge e
= EDGE_SUCC (bb
, ix
);
1977 basic_block other_bb
= e
->dest
;
1979 if (df_get_bb_dirty (other_bb
))
1981 block_was_dirty
= true;
1985 if (e
->flags
& EDGE_ABNORMAL
)
1988 /* Normally, all destination blocks must only be reachable from this
1989 block, i.e. they must have one incoming edge.
1991 There is one special case we can handle, that of multiple consecutive
1992 jumps where the first jumps to one of the targets of the second jump.
1993 This happens frequently in switch statements for default labels.
1994 The structure is as follows:
2000 jump with targets A, B, C, D...
2002 has two incoming edges, from FINAL_DEST_BB and BB
2004 In this case, we can try to move the insns through BB and into
2006 if (EDGE_COUNT (other_bb
->preds
) != 1)
2008 edge incoming_edge
, incoming_bb_other_edge
;
2011 if (final_dest_bb
!= NULL
2012 || EDGE_COUNT (other_bb
->preds
) != 2)
2015 /* We must be able to move the insns across the whole block. */
2016 move_before
= BB_HEAD (bb
);
2017 while (!NONDEBUG_INSN_P (move_before
))
2018 move_before
= NEXT_INSN (move_before
);
2020 if (EDGE_COUNT (bb
->preds
) != 1)
2022 incoming_edge
= EDGE_PRED (bb
, 0);
2023 final_dest_bb
= incoming_edge
->src
;
2024 if (EDGE_COUNT (final_dest_bb
->succs
) != 2)
2026 FOR_EACH_EDGE (incoming_bb_other_edge
, ei
, final_dest_bb
->succs
)
2027 if (incoming_bb_other_edge
!= incoming_edge
)
2029 if (incoming_bb_other_edge
->dest
!= other_bb
)
2034 e0
= EDGE_SUCC (bb
, 0);
2035 e0_last_head
= NULL_RTX
;
2038 for (ix
= 1; ix
< nedges
; ix
++)
2040 edge e
= EDGE_SUCC (bb
, ix
);
2041 rtx e0_last
, e_last
;
2044 nmatch
= flow_find_head_matching_sequence (e0
->dest
, e
->dest
,
2045 &e0_last
, &e_last
, 0);
2049 if (nmatch
< max_match
)
2052 e0_last_head
= e0_last
;
2056 /* If we matched an entire block, we probably have to avoid moving the
2059 && e0_last_head
== BB_END (e0
->dest
)
2060 && (find_reg_note (e0_last_head
, REG_EH_REGION
, 0)
2061 || control_flow_insn_p (e0_last_head
)))
2067 e0_last_head
= prev_real_insn (e0_last_head
);
2068 while (DEBUG_INSN_P (e0_last_head
));
2074 /* We must find a union of the live registers at each of the end points. */
2075 live
= BITMAP_ALLOC (NULL
);
2076 live_union
= BITMAP_ALLOC (NULL
);
2078 currptr
= XNEWVEC (rtx
, nedges
);
2079 headptr
= XNEWVEC (rtx
, nedges
);
2080 nextptr
= XNEWVEC (rtx
, nedges
);
2082 for (ix
= 0; ix
< nedges
; ix
++)
2085 basic_block merge_bb
= EDGE_SUCC (bb
, ix
)->dest
;
2086 rtx head
= BB_HEAD (merge_bb
);
2088 while (!NONDEBUG_INSN_P (head
))
2089 head
= NEXT_INSN (head
);
2093 /* Compute the end point and live information */
2094 for (j
= 1; j
< max_match
; j
++)
2096 head
= NEXT_INSN (head
);
2097 while (!NONDEBUG_INSN_P (head
));
2098 simulate_backwards_to_point (merge_bb
, live
, head
);
2099 IOR_REG_SET (live_union
, live
);
2102 /* If we're moving across two blocks, verify the validity of the
2103 first move, then adjust the target and let the loop below deal
2104 with the final move. */
2105 if (final_dest_bb
!= NULL
)
2109 moveall
= can_move_insns_across (currptr
[0], e0_last_head
, move_before
,
2110 jump
, e0
->dest
, live_union
,
2114 if (move_upto
== NULL_RTX
)
2117 while (e0_last_head
!= move_upto
)
2119 df_simulate_one_insn_backwards (e0
->dest
, e0_last_head
,
2121 e0_last_head
= PREV_INSN (e0_last_head
);
2124 if (e0_last_head
== NULL_RTX
)
2127 jump
= BB_END (final_dest_bb
);
2128 cond
= get_condition (jump
, &move_before
, true, false);
2129 if (cond
== NULL_RTX
)
2136 moveall
= can_move_insns_across (currptr
[0], e0_last_head
,
2137 move_before
, jump
, e0
->dest
, live_union
,
2139 if (!moveall
&& move_upto
== NULL_RTX
)
2141 if (jump
== move_before
)
2144 /* Try again, using a different insertion point. */
2148 /* Don't try moving before a cc0 user, as that may invalidate
2150 if (reg_mentioned_p (cc0_rtx
, jump
))
2157 if (final_dest_bb
&& !moveall
)
2158 /* We haven't checked whether a partial move would be OK for the first
2159 move, so we have to fail this case. */
2165 if (currptr
[0] == move_upto
)
2167 for (ix
= 0; ix
< nedges
; ix
++)
2169 rtx curr
= currptr
[ix
];
2171 curr
= NEXT_INSN (curr
);
2172 while (!NONDEBUG_INSN_P (curr
));
2177 /* If we can't currently move all of the identical insns, remember
2178 each insn after the range that we'll merge. */
2180 for (ix
= 0; ix
< nedges
; ix
++)
2182 rtx curr
= currptr
[ix
];
2184 curr
= NEXT_INSN (curr
);
2185 while (!NONDEBUG_INSN_P (curr
));
2189 reorder_insns (headptr
[0], currptr
[0], PREV_INSN (move_before
));
2190 df_set_bb_dirty (EDGE_SUCC (bb
, 0)->dest
);
2191 if (final_dest_bb
!= NULL
)
2192 df_set_bb_dirty (final_dest_bb
);
2193 df_set_bb_dirty (bb
);
2194 for (ix
= 1; ix
< nedges
; ix
++)
2196 df_set_bb_dirty (EDGE_SUCC (bb
, ix
)->dest
);
2197 delete_insn_chain (headptr
[ix
], currptr
[ix
], false);
2201 if (jump
== move_before
)
2204 /* For the unmerged insns, try a different insertion point. */
2208 /* Don't try moving before a cc0 user, as that may invalidate
2210 if (reg_mentioned_p (cc0_rtx
, jump
))
2214 for (ix
= 0; ix
< nedges
; ix
++)
2215 currptr
[ix
] = headptr
[ix
] = nextptr
[ix
];
2225 crossjumps_occured
|= changed
;
2230 /* Return true if BB contains just bb note, or bb note followed
2231 by only DEBUG_INSNs. */
2234 trivially_empty_bb_p (basic_block bb
)
2236 rtx insn
= BB_END (bb
);
2240 if (insn
== BB_HEAD (bb
))
2242 if (!DEBUG_INSN_P (insn
))
2244 insn
= PREV_INSN (insn
);
2248 /* Do simple CFG optimizations - basic block merging, simplifying of jump
2249 instructions etc. Return nonzero if changes were made. */
2252 try_optimize_cfg (int mode
)
2254 bool changed_overall
= false;
2257 basic_block bb
, b
, next
;
2259 if (mode
& (CLEANUP_CROSSJUMP
| CLEANUP_THREADING
))
2262 crossjumps_occured
= false;
2265 update_forwarder_flag (bb
);
2267 if (! targetm
.cannot_modify_jumps_p ())
2270 /* Attempt to merge blocks as made possible by edge removal. If
2271 a block has only one successor, and the successor has only
2272 one predecessor, they may be combined. */
2275 block_was_dirty
= false;
2281 "\n\ntry_optimize_cfg iteration %i\n\n",
2284 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
;)
2288 bool changed_here
= false;
2290 /* Delete trivially dead basic blocks. This is either
2291 blocks with no predecessors, or empty blocks with no
2292 successors. However if the empty block with no
2293 successors is the successor of the ENTRY_BLOCK, it is
2294 kept. This ensures that the ENTRY_BLOCK will have a
2295 successor which is a precondition for many RTL
2296 passes. Empty blocks may result from expanding
2297 __builtin_unreachable (). */
2298 if (EDGE_COUNT (b
->preds
) == 0
2299 || (EDGE_COUNT (b
->succs
) == 0
2300 && trivially_empty_bb_p (b
)
2301 && single_succ_edge (ENTRY_BLOCK_PTR
)->dest
!= b
))
2304 if (EDGE_COUNT (b
->preds
) > 0)
2309 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2311 if (b
->il
.rtl
->footer
2312 && BARRIER_P (b
->il
.rtl
->footer
))
2313 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2314 if ((e
->flags
& EDGE_FALLTHRU
)
2315 && e
->src
->il
.rtl
->footer
== NULL
)
2317 if (b
->il
.rtl
->footer
)
2319 e
->src
->il
.rtl
->footer
= b
->il
.rtl
->footer
;
2320 b
->il
.rtl
->footer
= NULL
;
2325 e
->src
->il
.rtl
->footer
= emit_barrier ();
2332 rtx last
= get_last_bb_insn (b
);
2333 if (last
&& BARRIER_P (last
))
2334 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2335 if ((e
->flags
& EDGE_FALLTHRU
))
2336 emit_barrier_after (BB_END (e
->src
));
2339 delete_basic_block (b
);
2341 /* Avoid trying to remove ENTRY_BLOCK_PTR. */
2342 b
= (c
== ENTRY_BLOCK_PTR
? c
->next_bb
: c
);
2346 /* Remove code labels no longer used. */
2347 if (single_pred_p (b
)
2348 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2349 && !(single_pred_edge (b
)->flags
& EDGE_COMPLEX
)
2350 && LABEL_P (BB_HEAD (b
))
2351 /* If the previous block ends with a branch to this
2352 block, we can't delete the label. Normally this
2353 is a condjump that is yet to be simplified, but
2354 if CASE_DROPS_THRU, this can be a tablejump with
2355 some element going to the same place as the
2356 default (fallthru). */
2357 && (single_pred (b
) == ENTRY_BLOCK_PTR
2358 || !JUMP_P (BB_END (single_pred (b
)))
2359 || ! label_is_jump_target_p (BB_HEAD (b
),
2360 BB_END (single_pred (b
)))))
2362 rtx label
= BB_HEAD (b
);
2364 delete_insn_chain (label
, label
, false);
2365 /* If the case label is undeletable, move it after the
2366 BASIC_BLOCK note. */
2367 if (NOTE_KIND (BB_HEAD (b
)) == NOTE_INSN_DELETED_LABEL
)
2369 rtx bb_note
= NEXT_INSN (BB_HEAD (b
));
2371 reorder_insns_nobb (label
, label
, bb_note
);
2372 BB_HEAD (b
) = bb_note
;
2373 if (BB_END (b
) == bb_note
)
2377 fprintf (dump_file
, "Deleted label in block %i.\n",
2381 /* If we fall through an empty block, we can remove it. */
2382 if (!(mode
& CLEANUP_CFGLAYOUT
)
2383 && single_pred_p (b
)
2384 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2385 && !LABEL_P (BB_HEAD (b
))
2386 && FORWARDER_BLOCK_P (b
)
2387 /* Note that forwarder_block_p true ensures that
2388 there is a successor for this block. */
2389 && (single_succ_edge (b
)->flags
& EDGE_FALLTHRU
)
2390 && n_basic_blocks
> NUM_FIXED_BLOCKS
+ 1)
2394 "Deleting fallthru block %i.\n",
2397 c
= b
->prev_bb
== ENTRY_BLOCK_PTR
? b
->next_bb
: b
->prev_bb
;
2398 redirect_edge_succ_nodup (single_pred_edge (b
),
2400 delete_basic_block (b
);
2406 /* Merge B with its single successor, if any. */
2407 if (single_succ_p (b
)
2408 && (s
= single_succ_edge (b
))
2409 && !(s
->flags
& EDGE_COMPLEX
)
2410 && (c
= s
->dest
) != EXIT_BLOCK_PTR
2411 && single_pred_p (c
)
2414 /* When not in cfg_layout mode use code aware of reordering
2415 INSN. This code possibly creates new basic blocks so it
2416 does not fit merge_blocks interface and is kept here in
2417 hope that it will become useless once more of compiler
2418 is transformed to use cfg_layout mode. */
2420 if ((mode
& CLEANUP_CFGLAYOUT
)
2421 && can_merge_blocks_p (b
, c
))
2423 merge_blocks (b
, c
);
2424 update_forwarder_flag (b
);
2425 changed_here
= true;
2427 else if (!(mode
& CLEANUP_CFGLAYOUT
)
2428 /* If the jump insn has side effects,
2429 we can't kill the edge. */
2430 && (!JUMP_P (BB_END (b
))
2431 || (reload_completed
2432 ? simplejump_p (BB_END (b
))
2433 : (onlyjump_p (BB_END (b
))
2434 && !tablejump_p (BB_END (b
),
2436 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
2439 changed_here
= true;
2443 /* Simplify branch over branch. */
2444 if ((mode
& CLEANUP_EXPENSIVE
)
2445 && !(mode
& CLEANUP_CFGLAYOUT
)
2446 && try_simplify_condjump (b
))
2447 changed_here
= true;
2449 /* If B has a single outgoing edge, but uses a
2450 non-trivial jump instruction without side-effects, we
2451 can either delete the jump entirely, or replace it
2452 with a simple unconditional jump. */
2453 if (single_succ_p (b
)
2454 && single_succ (b
) != EXIT_BLOCK_PTR
2455 && onlyjump_p (BB_END (b
))
2456 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
)
2457 && try_redirect_by_replacing_jump (single_succ_edge (b
),
2459 (mode
& CLEANUP_CFGLAYOUT
) != 0))
2461 update_forwarder_flag (b
);
2462 changed_here
= true;
2465 /* Simplify branch to branch. */
2466 if (try_forward_edges (mode
, b
))
2467 changed_here
= true;
2469 /* Look for shared code between blocks. */
2470 if ((mode
& CLEANUP_CROSSJUMP
)
2471 && try_crossjump_bb (mode
, b
))
2472 changed_here
= true;
2474 if ((mode
& CLEANUP_CROSSJUMP
)
2475 /* This can lengthen register lifetimes. Do it only after
2478 && try_head_merge_bb (b
))
2479 changed_here
= true;
2481 /* Don't get confused by the index shift caused by
2489 if ((mode
& CLEANUP_CROSSJUMP
)
2490 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
2493 if (block_was_dirty
)
2495 /* This should only be set by head-merging. */
2496 gcc_assert (mode
& CLEANUP_CROSSJUMP
);
2500 #ifdef ENABLE_CHECKING
2502 verify_flow_info ();
2505 changed_overall
|= changed
;
2512 b
->flags
&= ~(BB_FORWARDER_BLOCK
| BB_NONTHREADABLE_BLOCK
);
2514 return changed_overall
;
2517 /* Delete all unreachable basic blocks. */
2520 delete_unreachable_blocks (void)
2522 bool changed
= false;
2523 basic_block b
, prev_bb
;
2525 find_unreachable_blocks ();
2527 /* When we're in GIMPLE mode and there may be debug insns, we should
2528 delete blocks in reverse dominator order, so as to get a chance
2529 to substitute all released DEFs into debug stmts. If we don't
2530 have dominators information, walking blocks backward gets us a
2531 better chance of retaining most debug information than
2533 if (MAY_HAVE_DEBUG_STMTS
&& current_ir_type () == IR_GIMPLE
2534 && dom_info_available_p (CDI_DOMINATORS
))
2536 for (b
= EXIT_BLOCK_PTR
->prev_bb
; b
!= ENTRY_BLOCK_PTR
; b
= prev_bb
)
2538 prev_bb
= b
->prev_bb
;
2540 if (!(b
->flags
& BB_REACHABLE
))
2542 /* Speed up the removal of blocks that don't dominate
2543 others. Walking backwards, this should be the common
2545 if (!first_dom_son (CDI_DOMINATORS
, b
))
2546 delete_basic_block (b
);
2549 VEC (basic_block
, heap
) *h
2550 = get_all_dominated_blocks (CDI_DOMINATORS
, b
);
2552 while (VEC_length (basic_block
, h
))
2554 b
= VEC_pop (basic_block
, h
);
2556 prev_bb
= b
->prev_bb
;
2558 gcc_assert (!(b
->flags
& BB_REACHABLE
));
2560 delete_basic_block (b
);
2563 VEC_free (basic_block
, heap
, h
);
2572 for (b
= EXIT_BLOCK_PTR
->prev_bb
; b
!= ENTRY_BLOCK_PTR
; b
= prev_bb
)
2574 prev_bb
= b
->prev_bb
;
2576 if (!(b
->flags
& BB_REACHABLE
))
2578 delete_basic_block (b
);
2585 tidy_fallthru_edges ();
2589 /* Delete any jump tables never referenced. We can't delete them at the
2590 time of removing tablejump insn as they are referenced by the preceding
2591 insns computing the destination, so we delay deleting and garbagecollect
2592 them once life information is computed. */
2594 delete_dead_jumptables (void)
2598 /* A dead jump table does not belong to any basic block. Scan insns
2599 between two adjacent basic blocks. */
2604 for (insn
= NEXT_INSN (BB_END (bb
));
2605 insn
&& !NOTE_INSN_BASIC_BLOCK_P (insn
);
2608 next
= NEXT_INSN (insn
);
2610 && LABEL_NUSES (insn
) == LABEL_PRESERVE_P (insn
)
2611 && JUMP_TABLE_DATA_P (next
))
2613 rtx label
= insn
, jump
= next
;
2616 fprintf (dump_file
, "Dead jumptable %i removed\n",
2619 next
= NEXT_INSN (next
);
2621 delete_insn (label
);
2628 /* Tidy the CFG by deleting unreachable code and whatnot. */
2631 cleanup_cfg (int mode
)
2633 bool changed
= false;
2635 /* Set the cfglayout mode flag here. We could update all the callers
2636 but that is just inconvenient, especially given that we eventually
2637 want to have cfglayout mode as the default. */
2638 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2639 mode
|= CLEANUP_CFGLAYOUT
;
2641 timevar_push (TV_CLEANUP_CFG
);
2642 if (delete_unreachable_blocks ())
2645 /* We've possibly created trivially dead code. Cleanup it right
2646 now to introduce more opportunities for try_optimize_cfg. */
2647 if (!(mode
& (CLEANUP_NO_INSN_DEL
))
2648 && !reload_completed
)
2649 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2654 /* To tail-merge blocks ending in the same noreturn function (e.g.
2655 a call to abort) we have to insert fake edges to exit. Do this
2656 here once. The fake edges do not interfere with any other CFG
2658 if (mode
& CLEANUP_CROSSJUMP
)
2659 add_noreturn_fake_exit_edges ();
2661 if (!dbg_cnt (cfg_cleanup
))
2664 while (try_optimize_cfg (mode
))
2666 delete_unreachable_blocks (), changed
= true;
2667 if (!(mode
& CLEANUP_NO_INSN_DEL
))
2669 /* Try to remove some trivially dead insns when doing an expensive
2670 cleanup. But delete_trivially_dead_insns doesn't work after
2671 reload (it only handles pseudos) and run_fast_dce is too costly
2672 to run in every iteration.
2674 For effective cross jumping, we really want to run a fast DCE to
2675 clean up any dead conditions, or they get in the way of performing
2678 Other transformations in cleanup_cfg are not so sensitive to dead
2679 code, so delete_trivially_dead_insns or even doing nothing at all
2681 if ((mode
& CLEANUP_EXPENSIVE
) && !reload_completed
2682 && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
2684 if ((mode
& CLEANUP_CROSSJUMP
) && crossjumps_occured
)
2691 if (mode
& CLEANUP_CROSSJUMP
)
2692 remove_fake_exit_edges ();
2694 /* Don't call delete_dead_jumptables in cfglayout mode, because
2695 that function assumes that jump tables are in the insns stream.
2696 But we also don't _have_ to delete dead jumptables in cfglayout
2697 mode because we shouldn't even be looking at things that are
2698 not in a basic block. Dead jumptables are cleaned up when
2699 going out of cfglayout mode. */
2700 if (!(mode
& CLEANUP_CFGLAYOUT
))
2701 delete_dead_jumptables ();
2703 timevar_pop (TV_CLEANUP_CFG
);
2709 rest_of_handle_jump (void)
2711 if (crtl
->tail_call_emit
)
2712 fixup_tail_calls ();
2716 struct rtl_opt_pass pass_jump
=
2720 "sibling", /* name */
2722 rest_of_handle_jump
, /* execute */
2725 0, /* static_pass_number */
2726 TV_JUMP
, /* tv_id */
2727 0, /* properties_required */
2728 0, /* properties_provided */
2729 0, /* properties_destroyed */
2730 TODO_ggc_collect
, /* todo_flags_start */
2731 TODO_verify_flow
, /* todo_flags_finish */
2737 rest_of_handle_jump2 (void)
2739 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2741 dump_flow_info (dump_file
, dump_flags
);
2742 cleanup_cfg ((optimize
? CLEANUP_EXPENSIVE
: 0)
2743 | (flag_thread_jumps
? CLEANUP_THREADING
: 0));
2748 struct rtl_opt_pass pass_jump2
=
2754 rest_of_handle_jump2
, /* execute */
2757 0, /* static_pass_number */
2758 TV_JUMP
, /* tv_id */
2759 0, /* properties_required */
2760 0, /* properties_provided */
2761 0, /* properties_destroyed */
2762 TODO_ggc_collect
, /* todo_flags_start */
2763 TODO_dump_func
| TODO_verify_rtl_sharing
,/* todo_flags_finish */