1 /* Control flow optimization code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010, 2011
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file contains optimizer of the control flow. The main entry point is
23 cleanup_cfg. Following optimizations are performed:
25 - Unreachable blocks removal
26 - Edge forwarding (edge to the forwarder block is forwarded to its
27 successor. Simplification of the branch instruction is performed by
28 underlying infrastructure so branch can be converted to simplejump or
30 - Cross jumping (tail merging)
31 - Conditional jump-around-simplejump simplification
32 - Basic block merging. */
36 #include "coretypes.h"
39 #include "hard-reg-set.h"
43 #include "insn-config.h"
46 #include "diagnostic-core.h"
51 #include "cfglayout.h"
53 #include "tree-pass.h"
60 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
62 /* Set to true when we are running first pass of try_optimize_cfg loop. */
63 static bool first_pass
;
65 /* Set to true if crossjumps occured in the latest run of try_optimize_cfg. */
66 static bool crossjumps_occured
;
68 /* Set to true if we couldn't run an optimization due to stale liveness
69 information; we should run df_analyze to enable more opportunities. */
70 static bool block_was_dirty
;
72 static bool try_crossjump_to_edge (int, edge
, edge
, enum replace_direction
);
73 static bool try_crossjump_bb (int, basic_block
);
74 static bool outgoing_edges_match (int, basic_block
, basic_block
);
75 static enum replace_direction
old_insns_match_p (int, rtx
, rtx
);
77 static void merge_blocks_move_predecessor_nojumps (basic_block
, basic_block
);
78 static void merge_blocks_move_successor_nojumps (basic_block
, basic_block
);
79 static bool try_optimize_cfg (int);
80 static bool try_simplify_condjump (basic_block
);
81 static bool try_forward_edges (int, basic_block
);
82 static edge
thread_jump (edge
, basic_block
);
83 static bool mark_effect (rtx
, bitmap
);
84 static void notice_new_block (basic_block
);
85 static void update_forwarder_flag (basic_block
);
86 static int mentions_nonequal_regs (rtx
*, void *);
87 static void merge_memattrs (rtx
, rtx
);
89 /* Set flags for newly created block. */
92 notice_new_block (basic_block bb
)
97 if (forwarder_block_p (bb
))
98 bb
->flags
|= BB_FORWARDER_BLOCK
;
101 /* Recompute forwarder flag after block has been modified. */
104 update_forwarder_flag (basic_block bb
)
106 if (forwarder_block_p (bb
))
107 bb
->flags
|= BB_FORWARDER_BLOCK
;
109 bb
->flags
&= ~BB_FORWARDER_BLOCK
;
112 /* Simplify a conditional jump around an unconditional jump.
113 Return true if something changed. */
116 try_simplify_condjump (basic_block cbranch_block
)
118 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
119 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
122 /* Verify that there are exactly two successors. */
123 if (EDGE_COUNT (cbranch_block
->succs
) != 2)
126 /* Verify that we've got a normal conditional branch at the end
128 cbranch_insn
= BB_END (cbranch_block
);
129 if (!any_condjump_p (cbranch_insn
))
132 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
133 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
135 /* The next block must not have multiple predecessors, must not
136 be the last block in the function, and must contain just the
137 unconditional jump. */
138 jump_block
= cbranch_fallthru_edge
->dest
;
139 if (!single_pred_p (jump_block
)
140 || jump_block
->next_bb
== EXIT_BLOCK_PTR
141 || !FORWARDER_BLOCK_P (jump_block
))
143 jump_dest_block
= single_succ (jump_block
);
145 /* If we are partitioning hot/cold basic blocks, we don't want to
146 mess up unconditional or indirect jumps that cross between hot
149 Basic block partitioning may result in some jumps that appear to
150 be optimizable (or blocks that appear to be mergeable), but which really
151 must be left untouched (they are required to make it safely across
152 partition boundaries). See the comments at the top of
153 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
155 if (BB_PARTITION (jump_block
) != BB_PARTITION (jump_dest_block
)
156 || (cbranch_jump_edge
->flags
& EDGE_CROSSING
))
159 /* The conditional branch must target the block after the
160 unconditional branch. */
161 cbranch_dest_block
= cbranch_jump_edge
->dest
;
163 if (cbranch_dest_block
== EXIT_BLOCK_PTR
164 || !can_fallthru (jump_block
, cbranch_dest_block
))
167 /* Invert the conditional branch. */
168 if (!invert_jump (cbranch_insn
, block_label (jump_dest_block
), 0))
172 fprintf (dump_file
, "Simplifying condjump %i around jump %i\n",
173 INSN_UID (cbranch_insn
), INSN_UID (BB_END (jump_block
)));
175 /* Success. Update the CFG to match. Note that after this point
176 the edge variable names appear backwards; the redirection is done
177 this way to preserve edge profile data. */
178 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
180 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
182 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
183 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
184 update_br_prob_note (cbranch_block
);
186 /* Delete the block with the unconditional jump, and clean up the mess. */
187 delete_basic_block (jump_block
);
188 tidy_fallthru_edge (cbranch_jump_edge
);
189 update_forwarder_flag (cbranch_block
);
194 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
195 on register. Used by jump threading. */
198 mark_effect (rtx exp
, regset nonequal
)
202 switch (GET_CODE (exp
))
204 /* In case we do clobber the register, mark it as equal, as we know the
205 value is dead so it don't have to match. */
207 if (REG_P (XEXP (exp
, 0)))
209 dest
= XEXP (exp
, 0);
210 regno
= REGNO (dest
);
211 if (HARD_REGISTER_NUM_P (regno
))
212 bitmap_clear_range (nonequal
, regno
,
213 hard_regno_nregs
[regno
][GET_MODE (dest
)]);
215 bitmap_clear_bit (nonequal
, regno
);
220 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
222 dest
= SET_DEST (exp
);
227 regno
= REGNO (dest
);
228 if (HARD_REGISTER_NUM_P (regno
))
229 bitmap_set_range (nonequal
, regno
,
230 hard_regno_nregs
[regno
][GET_MODE (dest
)]);
232 bitmap_set_bit (nonequal
, regno
);
240 /* Return nonzero if X is a register set in regset DATA.
241 Called via for_each_rtx. */
243 mentions_nonequal_regs (rtx
*x
, void *data
)
245 regset nonequal
= (regset
) data
;
251 if (REGNO_REG_SET_P (nonequal
, regno
))
253 if (regno
< FIRST_PSEUDO_REGISTER
)
255 int n
= hard_regno_nregs
[regno
][GET_MODE (*x
)];
257 if (REGNO_REG_SET_P (nonequal
, regno
+ n
))
263 /* Attempt to prove that the basic block B will have no side effects and
264 always continues in the same edge if reached via E. Return the edge
265 if exist, NULL otherwise. */
268 thread_jump (edge e
, basic_block b
)
270 rtx set1
, set2
, cond1
, cond2
, insn
;
271 enum rtx_code code1
, code2
, reversed_code2
;
272 bool reverse1
= false;
276 reg_set_iterator rsi
;
278 if (b
->flags
& BB_NONTHREADABLE_BLOCK
)
281 /* At the moment, we do handle only conditional jumps, but later we may
282 want to extend this code to tablejumps and others. */
283 if (EDGE_COUNT (e
->src
->succs
) != 2)
285 if (EDGE_COUNT (b
->succs
) != 2)
287 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
291 /* Second branch must end with onlyjump, as we will eliminate the jump. */
292 if (!any_condjump_p (BB_END (e
->src
)))
295 if (!any_condjump_p (BB_END (b
)) || !onlyjump_p (BB_END (b
)))
297 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
301 set1
= pc_set (BB_END (e
->src
));
302 set2
= pc_set (BB_END (b
));
303 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
304 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
307 cond1
= XEXP (SET_SRC (set1
), 0);
308 cond2
= XEXP (SET_SRC (set2
), 0);
310 code1
= reversed_comparison_code (cond1
, BB_END (e
->src
));
312 code1
= GET_CODE (cond1
);
314 code2
= GET_CODE (cond2
);
315 reversed_code2
= reversed_comparison_code (cond2
, BB_END (b
));
317 if (!comparison_dominates_p (code1
, code2
)
318 && !comparison_dominates_p (code1
, reversed_code2
))
321 /* Ensure that the comparison operators are equivalent.
322 ??? This is far too pessimistic. We should allow swapped operands,
323 different CCmodes, or for example comparisons for interval, that
324 dominate even when operands are not equivalent. */
325 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
326 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
329 /* Short circuit cases where block B contains some side effects, as we can't
331 for (insn
= NEXT_INSN (BB_HEAD (b
)); insn
!= NEXT_INSN (BB_END (b
));
332 insn
= NEXT_INSN (insn
))
333 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
335 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
341 /* First process all values computed in the source basic block. */
342 for (insn
= NEXT_INSN (BB_HEAD (e
->src
));
343 insn
!= NEXT_INSN (BB_END (e
->src
));
344 insn
= NEXT_INSN (insn
))
346 cselib_process_insn (insn
);
348 nonequal
= BITMAP_ALLOC (NULL
);
349 CLEAR_REG_SET (nonequal
);
351 /* Now assume that we've continued by the edge E to B and continue
352 processing as if it were same basic block.
353 Our goal is to prove that whole block is an NOOP. */
355 for (insn
= NEXT_INSN (BB_HEAD (b
));
356 insn
!= NEXT_INSN (BB_END (b
)) && !failed
;
357 insn
= NEXT_INSN (insn
))
361 rtx pat
= PATTERN (insn
);
363 if (GET_CODE (pat
) == PARALLEL
)
365 for (i
= 0; i
< (unsigned)XVECLEN (pat
, 0); i
++)
366 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
369 failed
|= mark_effect (pat
, nonequal
);
372 cselib_process_insn (insn
);
375 /* Later we should clear nonequal of dead registers. So far we don't
376 have life information in cfg_cleanup. */
379 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
383 /* cond2 must not mention any register that is not equal to the
385 if (for_each_rtx (&cond2
, mentions_nonequal_regs
, nonequal
))
388 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, rsi
)
391 BITMAP_FREE (nonequal
);
393 if ((comparison_dominates_p (code1
, code2
) != 0)
394 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
395 return BRANCH_EDGE (b
);
397 return FALLTHRU_EDGE (b
);
400 BITMAP_FREE (nonequal
);
405 /* Attempt to forward edges leaving basic block B.
406 Return true if successful. */
409 try_forward_edges (int mode
, basic_block b
)
411 bool changed
= false;
413 edge e
, *threaded_edges
= NULL
;
415 /* If we are partitioning hot/cold basic blocks, we don't want to
416 mess up unconditional or indirect jumps that cross between hot
419 Basic block partitioning may result in some jumps that appear to
420 be optimizable (or blocks that appear to be mergeable), but which really
421 must be left untouched (they are required to make it safely across
422 partition boundaries). See the comments at the top of
423 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
425 if (find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
428 for (ei
= ei_start (b
->succs
); (e
= ei_safe_edge (ei
)); )
430 basic_block target
, first
;
431 int counter
, goto_locus
;
432 bool threaded
= false;
433 int nthreaded_edges
= 0;
434 bool may_thread
= first_pass
|| (b
->flags
& BB_MODIFIED
) != 0;
436 /* Skip complex edges because we don't know how to update them.
438 Still handle fallthru edges, as we can succeed to forward fallthru
439 edge to the same place as the branch edge of conditional branch
440 and turn conditional branch to an unconditional branch. */
441 if (e
->flags
& EDGE_COMPLEX
)
447 target
= first
= e
->dest
;
448 counter
= NUM_FIXED_BLOCKS
;
449 goto_locus
= e
->goto_locus
;
451 /* If we are partitioning hot/cold basic_blocks, we don't want to mess
452 up jumps that cross between hot/cold sections.
454 Basic block partitioning may result in some jumps that appear
455 to be optimizable (or blocks that appear to be mergeable), but which
456 really must be left untouched (they are required to make it safely
457 across partition boundaries). See the comments at the top of
458 bb-reorder.c:partition_hot_cold_basic_blocks for complete
461 if (first
!= EXIT_BLOCK_PTR
462 && find_reg_note (BB_END (first
), REG_CROSSING_JUMP
, NULL_RTX
))
465 while (counter
< n_basic_blocks
)
467 basic_block new_target
= NULL
;
468 bool new_target_threaded
= false;
469 may_thread
|= (target
->flags
& BB_MODIFIED
) != 0;
471 if (FORWARDER_BLOCK_P (target
)
472 && !(single_succ_edge (target
)->flags
& EDGE_CROSSING
)
473 && single_succ (target
) != EXIT_BLOCK_PTR
)
475 /* Bypass trivial infinite loops. */
476 new_target
= single_succ (target
);
477 if (target
== new_target
)
478 counter
= n_basic_blocks
;
481 /* When not optimizing, ensure that edges or forwarder
482 blocks with different locus are not optimized out. */
483 int new_locus
= single_succ_edge (target
)->goto_locus
;
484 int locus
= goto_locus
;
486 if (new_locus
&& locus
&& !locator_eq (new_locus
, locus
))
495 last
= BB_END (target
);
496 if (DEBUG_INSN_P (last
))
497 last
= prev_nondebug_insn (last
);
499 new_locus
= last
&& INSN_P (last
)
500 ? INSN_LOCATOR (last
) : 0;
502 if (new_locus
&& locus
&& !locator_eq (new_locus
, locus
))
515 /* Allow to thread only over one edge at time to simplify updating
517 else if ((mode
& CLEANUP_THREADING
) && may_thread
)
519 edge t
= thread_jump (e
, target
);
523 threaded_edges
= XNEWVEC (edge
, n_basic_blocks
);
528 /* Detect an infinite loop across blocks not
529 including the start block. */
530 for (i
= 0; i
< nthreaded_edges
; ++i
)
531 if (threaded_edges
[i
] == t
)
533 if (i
< nthreaded_edges
)
535 counter
= n_basic_blocks
;
540 /* Detect an infinite loop across the start block. */
544 gcc_assert (nthreaded_edges
< n_basic_blocks
- NUM_FIXED_BLOCKS
);
545 threaded_edges
[nthreaded_edges
++] = t
;
547 new_target
= t
->dest
;
548 new_target_threaded
= true;
557 threaded
|= new_target_threaded
;
560 if (counter
>= n_basic_blocks
)
563 fprintf (dump_file
, "Infinite loop in BB %i.\n",
566 else if (target
== first
)
567 ; /* We didn't do anything. */
570 /* Save the values now, as the edge may get removed. */
571 gcov_type edge_count
= e
->count
;
572 int edge_probability
= e
->probability
;
576 e
->goto_locus
= goto_locus
;
578 /* Don't force if target is exit block. */
579 if (threaded
&& target
!= EXIT_BLOCK_PTR
)
581 notice_new_block (redirect_edge_and_branch_force (e
, target
));
583 fprintf (dump_file
, "Conditionals threaded.\n");
585 else if (!redirect_edge_and_branch (e
, target
))
589 "Forwarding edge %i->%i to %i failed.\n",
590 b
->index
, e
->dest
->index
, target
->index
);
595 /* We successfully forwarded the edge. Now update profile
596 data: for each edge we traversed in the chain, remove
597 the original edge's execution count. */
598 edge_frequency
= ((edge_probability
* b
->frequency
599 + REG_BR_PROB_BASE
/ 2)
606 if (!single_succ_p (first
))
608 gcc_assert (n
< nthreaded_edges
);
609 t
= threaded_edges
[n
++];
610 gcc_assert (t
->src
== first
);
611 update_bb_profile_for_threading (first
, edge_frequency
,
613 update_br_prob_note (first
);
617 first
->count
-= edge_count
;
618 if (first
->count
< 0)
620 first
->frequency
-= edge_frequency
;
621 if (first
->frequency
< 0)
622 first
->frequency
= 0;
623 /* It is possible that as the result of
624 threading we've removed edge as it is
625 threaded to the fallthru edge. Avoid
626 getting out of sync. */
627 if (n
< nthreaded_edges
628 && first
== threaded_edges
[n
]->src
)
630 t
= single_succ_edge (first
);
633 t
->count
-= edge_count
;
638 while (first
!= target
);
646 free (threaded_edges
);
651 /* Blocks A and B are to be merged into a single block. A has no incoming
652 fallthru edge, so it can be moved before B without adding or modifying
653 any jumps (aside from the jump from A to B). */
656 merge_blocks_move_predecessor_nojumps (basic_block a
, basic_block b
)
660 /* If we are partitioning hot/cold basic blocks, we don't want to
661 mess up unconditional or indirect jumps that cross between hot
664 Basic block partitioning may result in some jumps that appear to
665 be optimizable (or blocks that appear to be mergeable), but which really
666 must be left untouched (they are required to make it safely across
667 partition boundaries). See the comments at the top of
668 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
670 if (BB_PARTITION (a
) != BB_PARTITION (b
))
673 barrier
= next_nonnote_insn (BB_END (a
));
674 gcc_assert (BARRIER_P (barrier
));
675 delete_insn (barrier
);
677 /* Scramble the insn chain. */
678 if (BB_END (a
) != PREV_INSN (BB_HEAD (b
)))
679 reorder_insns_nobb (BB_HEAD (a
), BB_END (a
), PREV_INSN (BB_HEAD (b
)));
683 fprintf (dump_file
, "Moved block %d before %d and merged.\n",
686 /* Swap the records for the two blocks around. */
689 link_block (a
, b
->prev_bb
);
691 /* Now blocks A and B are contiguous. Merge them. */
695 /* Blocks A and B are to be merged into a single block. B has no outgoing
696 fallthru edge, so it can be moved after A without adding or modifying
697 any jumps (aside from the jump from A to B). */
700 merge_blocks_move_successor_nojumps (basic_block a
, basic_block b
)
702 rtx barrier
, real_b_end
;
705 /* If we are partitioning hot/cold basic blocks, we don't want to
706 mess up unconditional or indirect jumps that cross between hot
709 Basic block partitioning may result in some jumps that appear to
710 be optimizable (or blocks that appear to be mergeable), but which really
711 must be left untouched (they are required to make it safely across
712 partition boundaries). See the comments at the top of
713 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
715 if (BB_PARTITION (a
) != BB_PARTITION (b
))
718 real_b_end
= BB_END (b
);
720 /* If there is a jump table following block B temporarily add the jump table
721 to block B so that it will also be moved to the correct location. */
722 if (tablejump_p (BB_END (b
), &label
, &table
)
723 && prev_active_insn (label
) == BB_END (b
))
728 /* There had better have been a barrier there. Delete it. */
729 barrier
= NEXT_INSN (BB_END (b
));
730 if (barrier
&& BARRIER_P (barrier
))
731 delete_insn (barrier
);
734 /* Scramble the insn chain. */
735 reorder_insns_nobb (BB_HEAD (b
), BB_END (b
), BB_END (a
));
737 /* Restore the real end of b. */
738 BB_END (b
) = real_b_end
;
741 fprintf (dump_file
, "Moved block %d after %d and merged.\n",
744 /* Now blocks A and B are contiguous. Merge them. */
748 /* Attempt to merge basic blocks that are potentially non-adjacent.
749 Return NULL iff the attempt failed, otherwise return basic block
750 where cleanup_cfg should continue. Because the merging commonly
751 moves basic block away or introduces another optimization
752 possibility, return basic block just before B so cleanup_cfg don't
755 It may be good idea to return basic block before C in the case
756 C has been moved after B and originally appeared earlier in the
757 insn sequence, but we have no information available about the
758 relative ordering of these two. Hopefully it is not too common. */
761 merge_blocks_move (edge e
, basic_block b
, basic_block c
, int mode
)
765 /* If we are partitioning hot/cold basic blocks, we don't want to
766 mess up unconditional or indirect jumps that cross between hot
769 Basic block partitioning may result in some jumps that appear to
770 be optimizable (or blocks that appear to be mergeable), but which really
771 must be left untouched (they are required to make it safely across
772 partition boundaries). See the comments at the top of
773 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
775 if (BB_PARTITION (b
) != BB_PARTITION (c
))
778 /* If B has a fallthru edge to C, no need to move anything. */
779 if (e
->flags
& EDGE_FALLTHRU
)
781 int b_index
= b
->index
, c_index
= c
->index
;
783 update_forwarder_flag (b
);
786 fprintf (dump_file
, "Merged %d and %d without moving.\n",
789 return b
->prev_bb
== ENTRY_BLOCK_PTR
? b
: b
->prev_bb
;
792 /* Otherwise we will need to move code around. Do that only if expensive
793 transformations are allowed. */
794 else if (mode
& CLEANUP_EXPENSIVE
)
796 edge tmp_edge
, b_fallthru_edge
;
797 bool c_has_outgoing_fallthru
;
798 bool b_has_incoming_fallthru
;
800 /* Avoid overactive code motion, as the forwarder blocks should be
801 eliminated by edge redirection instead. One exception might have
802 been if B is a forwarder block and C has no fallthru edge, but
803 that should be cleaned up by bb-reorder instead. */
804 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
807 /* We must make sure to not munge nesting of lexical blocks,
808 and loop notes. This is done by squeezing out all the notes
809 and leaving them there to lie. Not ideal, but functional. */
811 tmp_edge
= find_fallthru_edge (c
->succs
);
812 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
814 tmp_edge
= find_fallthru_edge (b
->preds
);
815 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
816 b_fallthru_edge
= tmp_edge
;
819 next
= next
->prev_bb
;
821 /* Otherwise, we're going to try to move C after B. If C does
822 not have an outgoing fallthru, then it can be moved
823 immediately after B without introducing or modifying jumps. */
824 if (! c_has_outgoing_fallthru
)
826 merge_blocks_move_successor_nojumps (b
, c
);
827 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
830 /* If B does not have an incoming fallthru, then it can be moved
831 immediately before C without introducing or modifying jumps.
832 C cannot be the first block, so we do not have to worry about
833 accessing a non-existent block. */
835 if (b_has_incoming_fallthru
)
839 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
841 bb
= force_nonfallthru (b_fallthru_edge
);
843 notice_new_block (bb
);
846 merge_blocks_move_predecessor_nojumps (b
, c
);
847 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
854 /* Removes the memory attributes of MEM expression
855 if they are not equal. */
858 merge_memattrs (rtx x
, rtx y
)
867 if (x
== 0 || y
== 0)
872 if (code
!= GET_CODE (y
))
875 if (GET_MODE (x
) != GET_MODE (y
))
878 if (code
== MEM
&& MEM_ATTRS (x
) != MEM_ATTRS (y
))
882 else if (! MEM_ATTRS (y
))
886 HOST_WIDE_INT mem_size
;
888 if (MEM_ALIAS_SET (x
) != MEM_ALIAS_SET (y
))
890 set_mem_alias_set (x
, 0);
891 set_mem_alias_set (y
, 0);
894 if (! mem_expr_equal_p (MEM_EXPR (x
), MEM_EXPR (y
)))
898 clear_mem_offset (x
);
899 clear_mem_offset (y
);
901 else if (MEM_OFFSET_KNOWN_P (x
) != MEM_OFFSET_KNOWN_P (y
)
902 || (MEM_OFFSET_KNOWN_P (x
)
903 && MEM_OFFSET (x
) != MEM_OFFSET (y
)))
905 clear_mem_offset (x
);
906 clear_mem_offset (y
);
909 if (MEM_SIZE_KNOWN_P (x
) && MEM_SIZE_KNOWN_P (y
))
911 mem_size
= MAX (MEM_SIZE (x
), MEM_SIZE (y
));
912 set_mem_size (x
, mem_size
);
913 set_mem_size (y
, mem_size
);
921 set_mem_align (x
, MIN (MEM_ALIGN (x
), MEM_ALIGN (y
)));
922 set_mem_align (y
, MEM_ALIGN (x
));
926 fmt
= GET_RTX_FORMAT (code
);
927 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
932 /* Two vectors must have the same length. */
933 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
936 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
937 merge_memattrs (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
));
942 merge_memattrs (XEXP (x
, i
), XEXP (y
, i
));
949 /* Checks if patterns P1 and P2 are equivalent, apart from the possibly
950 different single sets S1 and S2. */
953 equal_different_set_p (rtx p1
, rtx s1
, rtx p2
, rtx s2
)
958 if (p1
== s1
&& p2
== s2
)
961 if (GET_CODE (p1
) != PARALLEL
|| GET_CODE (p2
) != PARALLEL
)
964 if (XVECLEN (p1
, 0) != XVECLEN (p2
, 0))
967 for (i
= 0; i
< XVECLEN (p1
, 0); i
++)
969 e1
= XVECEXP (p1
, 0, i
);
970 e2
= XVECEXP (p2
, 0, i
);
971 if (e1
== s1
&& e2
== s2
)
974 ? rtx_renumbered_equal_p (e1
, e2
) : rtx_equal_p (e1
, e2
))
983 /* Examine register notes on I1 and I2 and return:
984 - dir_forward if I1 can be replaced by I2, or
985 - dir_backward if I2 can be replaced by I1, or
986 - dir_both if both are the case. */
988 static enum replace_direction
989 can_replace_by (rtx i1
, rtx i2
)
991 rtx s1
, s2
, d1
, d2
, src1
, src2
, note1
, note2
;
994 /* Check for 2 sets. */
995 s1
= single_set (i1
);
996 s2
= single_set (i2
);
997 if (s1
== NULL_RTX
|| s2
== NULL_RTX
)
1000 /* Check that the 2 sets set the same dest. */
1003 if (!(reload_completed
1004 ? rtx_renumbered_equal_p (d1
, d2
) : rtx_equal_p (d1
, d2
)))
1007 /* Find identical req_equiv or reg_equal note, which implies that the 2 sets
1008 set dest to the same value. */
1009 note1
= find_reg_equal_equiv_note (i1
);
1010 note2
= find_reg_equal_equiv_note (i2
);
1011 if (!note1
|| !note2
|| !rtx_equal_p (XEXP (note1
, 0), XEXP (note2
, 0))
1012 || !CONST_INT_P (XEXP (note1
, 0)))
1015 if (!equal_different_set_p (PATTERN (i1
), s1
, PATTERN (i2
), s2
))
1018 /* Although the 2 sets set dest to the same value, we cannot replace
1019 (set (dest) (const_int))
1022 because we don't know if the reg is live and has the same value at the
1023 location of replacement. */
1024 src1
= SET_SRC (s1
);
1025 src2
= SET_SRC (s2
);
1026 c1
= CONST_INT_P (src1
);
1027 c2
= CONST_INT_P (src2
);
1033 return dir_backward
;
1038 /* Merges directions A and B. */
1040 static enum replace_direction
1041 merge_dir (enum replace_direction a
, enum replace_direction b
)
1043 /* Implements the following table:
1062 /* Examine I1 and I2 and return:
1063 - dir_forward if I1 can be replaced by I2, or
1064 - dir_backward if I2 can be replaced by I1, or
1065 - dir_both if both are the case. */
1067 static enum replace_direction
1068 old_insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx i1
, rtx i2
)
1072 /* Verify that I1 and I2 are equivalent. */
1073 if (GET_CODE (i1
) != GET_CODE (i2
))
1076 /* __builtin_unreachable() may lead to empty blocks (ending with
1077 NOTE_INSN_BASIC_BLOCK). They may be crossjumped. */
1078 if (NOTE_INSN_BASIC_BLOCK_P (i1
) && NOTE_INSN_BASIC_BLOCK_P (i2
))
1081 /* ??? Do not allow cross-jumping between different stack levels. */
1082 p1
= find_reg_note (i1
, REG_ARGS_SIZE
, NULL
);
1083 p2
= find_reg_note (i2
, REG_ARGS_SIZE
, NULL
);
1088 if (!rtx_equal_p (p1
, p2
))
1091 /* ??? Worse, this adjustment had better be constant lest we
1092 have differing incoming stack levels. */
1093 if (!frame_pointer_needed
1094 && find_args_size_adjust (i1
) == HOST_WIDE_INT_MIN
)
1103 if (GET_CODE (p1
) != GET_CODE (p2
))
1106 /* If this is a CALL_INSN, compare register usage information.
1107 If we don't check this on stack register machines, the two
1108 CALL_INSNs might be merged leaving reg-stack.c with mismatching
1109 numbers of stack registers in the same basic block.
1110 If we don't check this on machines with delay slots, a delay slot may
1111 be filled that clobbers a parameter expected by the subroutine.
1113 ??? We take the simple route for now and assume that if they're
1114 equal, they were constructed identically.
1116 Also check for identical exception regions. */
1120 /* Ensure the same EH region. */
1121 rtx n1
= find_reg_note (i1
, REG_EH_REGION
, 0);
1122 rtx n2
= find_reg_note (i2
, REG_EH_REGION
, 0);
1127 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1130 if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
1131 CALL_INSN_FUNCTION_USAGE (i2
))
1132 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
))
1137 /* If cross_jump_death_matters is not 0, the insn's mode
1138 indicates whether or not the insn contains any stack-like
1141 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
1143 /* If register stack conversion has already been done, then
1144 death notes must also be compared before it is certain that
1145 the two instruction streams match. */
1148 HARD_REG_SET i1_regset
, i2_regset
;
1150 CLEAR_HARD_REG_SET (i1_regset
);
1151 CLEAR_HARD_REG_SET (i2_regset
);
1153 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
1154 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1155 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
1157 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
1158 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1159 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
1161 if (!hard_reg_set_equal_p (i1_regset
, i2_regset
))
1166 if (reload_completed
1167 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
1170 return can_replace_by (i1
, i2
);
1173 /* When comparing insns I1 and I2 in flow_find_cross_jump or
1174 flow_find_head_matching_sequence, ensure the notes match. */
1177 merge_notes (rtx i1
, rtx i2
)
1179 /* If the merged insns have different REG_EQUAL notes, then
1181 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1182 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1184 if (equiv1
&& !equiv2
)
1185 remove_note (i1
, equiv1
);
1186 else if (!equiv1
&& equiv2
)
1187 remove_note (i2
, equiv2
);
1188 else if (equiv1
&& equiv2
1189 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1191 remove_note (i1
, equiv1
);
1192 remove_note (i2
, equiv2
);
1196 /* Walks from I1 in BB1 backward till the next non-debug insn, and returns the
1197 resulting insn in I1, and the corresponding bb in BB1. At the head of a
1198 bb, if there is a predecessor bb that reaches this bb via fallthru, and
1199 FOLLOW_FALLTHRU, walks further in the predecessor bb and registers this in
1200 DID_FALLTHRU. Otherwise, stops at the head of the bb. */
1203 walk_to_nondebug_insn (rtx
*i1
, basic_block
*bb1
, bool follow_fallthru
,
1208 *did_fallthru
= false;
1211 while (!NONDEBUG_INSN_P (*i1
))
1213 if (*i1
!= BB_HEAD (*bb1
))
1215 *i1
= PREV_INSN (*i1
);
1219 if (!follow_fallthru
)
1222 fallthru
= find_fallthru_edge ((*bb1
)->preds
);
1223 if (!fallthru
|| fallthru
->src
== ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
)
1224 || !single_succ_p (fallthru
->src
))
1227 *bb1
= fallthru
->src
;
1228 *i1
= BB_END (*bb1
);
1229 *did_fallthru
= true;
1233 /* Look through the insns at the end of BB1 and BB2 and find the longest
1234 sequence that are either equivalent, or allow forward or backward
1235 replacement. Store the first insns for that sequence in *F1 and *F2 and
1236 return the sequence length.
1238 DIR_P indicates the allowed replacement direction on function entry, and
1239 the actual replacement direction on function exit. If NULL, only equivalent
1240 sequences are allowed.
1242 To simplify callers of this function, if the blocks match exactly,
1243 store the head of the blocks in *F1 and *F2. */
1246 flow_find_cross_jump (basic_block bb1
, basic_block bb2
, rtx
*f1
, rtx
*f2
,
1247 enum replace_direction
*dir_p
)
1249 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
1252 enum replace_direction dir
, last_dir
, afterlast_dir
;
1253 bool follow_fallthru
, did_fallthru
;
1259 afterlast_dir
= dir
;
1260 last_dir
= afterlast_dir
;
1262 /* Skip simple jumps at the end of the blocks. Complex jumps still
1263 need to be compared for equivalence, which we'll do below. */
1266 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
1268 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1271 i1
= PREV_INSN (i1
);
1276 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1279 /* Count everything except for unconditional jump as insn. */
1280 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1282 i2
= PREV_INSN (i2
);
1287 /* In the following example, we can replace all jumps to C by jumps to A.
1289 This removes 4 duplicate insns.
1290 [bb A] insn1 [bb C] insn1
1296 We could also replace all jumps to A by jumps to C, but that leaves B
1297 alive, and removes only 2 duplicate insns. In a subsequent crossjump
1298 step, all jumps to B would be replaced with jumps to the middle of C,
1299 achieving the same result with more effort.
1300 So we allow only the first possibility, which means that we don't allow
1301 fallthru in the block that's being replaced. */
1303 follow_fallthru
= dir_p
&& dir
!= dir_forward
;
1304 walk_to_nondebug_insn (&i1
, &bb1
, follow_fallthru
, &did_fallthru
);
1308 follow_fallthru
= dir_p
&& dir
!= dir_backward
;
1309 walk_to_nondebug_insn (&i2
, &bb2
, follow_fallthru
, &did_fallthru
);
1313 if (i1
== BB_HEAD (bb1
) || i2
== BB_HEAD (bb2
))
1316 dir
= merge_dir (dir
, old_insns_match_p (0, i1
, i2
));
1317 if (dir
== dir_none
|| (!dir_p
&& dir
!= dir_both
))
1320 merge_memattrs (i1
, i2
);
1322 /* Don't begin a cross-jump with a NOTE insn. */
1325 merge_notes (i1
, i2
);
1327 afterlast1
= last1
, afterlast2
= last2
;
1328 last1
= i1
, last2
= i2
;
1329 afterlast_dir
= last_dir
;
1332 if (!(GET_CODE (p1
) == USE
|| GET_CODE (p1
) == CLOBBER
))
1336 i1
= PREV_INSN (i1
);
1337 i2
= PREV_INSN (i2
);
1341 /* Don't allow the insn after a compare to be shared by
1342 cross-jumping unless the compare is also shared. */
1343 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1344 last1
= afterlast1
, last2
= afterlast2
, last_dir
= afterlast_dir
, ninsns
--;
1347 /* Include preceding notes and labels in the cross-jump. One,
1348 this may bring us to the head of the blocks as requested above.
1349 Two, it keeps line number notes as matched as may be. */
1352 bb1
= BLOCK_FOR_INSN (last1
);
1353 while (last1
!= BB_HEAD (bb1
) && !NONDEBUG_INSN_P (PREV_INSN (last1
)))
1354 last1
= PREV_INSN (last1
);
1356 if (last1
!= BB_HEAD (bb1
) && LABEL_P (PREV_INSN (last1
)))
1357 last1
= PREV_INSN (last1
);
1359 bb2
= BLOCK_FOR_INSN (last2
);
1360 while (last2
!= BB_HEAD (bb2
) && !NONDEBUG_INSN_P (PREV_INSN (last2
)))
1361 last2
= PREV_INSN (last2
);
1363 if (last2
!= BB_HEAD (bb2
) && LABEL_P (PREV_INSN (last2
)))
1364 last2
= PREV_INSN (last2
);
1375 /* Like flow_find_cross_jump, except start looking for a matching sequence from
1376 the head of the two blocks. Do not include jumps at the end.
1377 If STOP_AFTER is nonzero, stop after finding that many matching
1381 flow_find_head_matching_sequence (basic_block bb1
, basic_block bb2
, rtx
*f1
,
1382 rtx
*f2
, int stop_after
)
1384 rtx i1
, i2
, last1
, last2
, beforelast1
, beforelast2
;
1388 int nehedges1
= 0, nehedges2
= 0;
1390 FOR_EACH_EDGE (e
, ei
, bb1
->succs
)
1391 if (e
->flags
& EDGE_EH
)
1393 FOR_EACH_EDGE (e
, ei
, bb2
->succs
)
1394 if (e
->flags
& EDGE_EH
)
1399 last1
= beforelast1
= last2
= beforelast2
= NULL_RTX
;
1403 /* Ignore notes, except NOTE_INSN_EPILOGUE_BEG. */
1404 while (!NONDEBUG_INSN_P (i1
) && i1
!= BB_END (bb1
))
1406 if (NOTE_P (i1
) && NOTE_KIND (i1
) == NOTE_INSN_EPILOGUE_BEG
)
1408 i1
= NEXT_INSN (i1
);
1411 while (!NONDEBUG_INSN_P (i2
) && i2
!= BB_END (bb2
))
1413 if (NOTE_P (i2
) && NOTE_KIND (i2
) == NOTE_INSN_EPILOGUE_BEG
)
1415 i2
= NEXT_INSN (i2
);
1418 if ((i1
== BB_END (bb1
) && !NONDEBUG_INSN_P (i1
))
1419 || (i2
== BB_END (bb2
) && !NONDEBUG_INSN_P (i2
)))
1422 if (NOTE_P (i1
) || NOTE_P (i2
)
1423 || JUMP_P (i1
) || JUMP_P (i2
))
1426 /* A sanity check to make sure we're not merging insns with different
1427 effects on EH. If only one of them ends a basic block, it shouldn't
1428 have an EH edge; if both end a basic block, there should be the same
1429 number of EH edges. */
1430 if ((i1
== BB_END (bb1
) && i2
!= BB_END (bb2
)
1432 || (i2
== BB_END (bb2
) && i1
!= BB_END (bb1
)
1434 || (i1
== BB_END (bb1
) && i2
== BB_END (bb2
)
1435 && nehedges1
!= nehedges2
))
1438 if (old_insns_match_p (0, i1
, i2
) != dir_both
)
1441 merge_memattrs (i1
, i2
);
1443 /* Don't begin a cross-jump with a NOTE insn. */
1446 merge_notes (i1
, i2
);
1448 beforelast1
= last1
, beforelast2
= last2
;
1449 last1
= i1
, last2
= i2
;
1453 if (i1
== BB_END (bb1
) || i2
== BB_END (bb2
)
1454 || (stop_after
> 0 && ninsns
== stop_after
))
1457 i1
= NEXT_INSN (i1
);
1458 i2
= NEXT_INSN (i2
);
1462 /* Don't allow a compare to be shared by cross-jumping unless the insn
1463 after the compare is also shared. */
1464 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && sets_cc0_p (last1
))
1465 last1
= beforelast1
, last2
= beforelast2
, ninsns
--;
1477 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1478 the branch instruction. This means that if we commonize the control
1479 flow before end of the basic block, the semantic remains unchanged.
1481 We may assume that there exists one edge with a common destination. */
1484 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1486 int nehedges1
= 0, nehedges2
= 0;
1487 edge fallthru1
= 0, fallthru2
= 0;
1491 /* If BB1 has only one successor, we may be looking at either an
1492 unconditional jump, or a fake edge to exit. */
1493 if (single_succ_p (bb1
)
1494 && (single_succ_edge (bb1
)->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1495 && (!JUMP_P (BB_END (bb1
)) || simplejump_p (BB_END (bb1
))))
1496 return (single_succ_p (bb2
)
1497 && (single_succ_edge (bb2
)->flags
1498 & (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1499 && (!JUMP_P (BB_END (bb2
)) || simplejump_p (BB_END (bb2
))));
1501 /* Match conditional jumps - this may get tricky when fallthru and branch
1502 edges are crossed. */
1503 if (EDGE_COUNT (bb1
->succs
) == 2
1504 && any_condjump_p (BB_END (bb1
))
1505 && onlyjump_p (BB_END (bb1
)))
1507 edge b1
, f1
, b2
, f2
;
1508 bool reverse
, match
;
1509 rtx set1
, set2
, cond1
, cond2
;
1510 enum rtx_code code1
, code2
;
1512 if (EDGE_COUNT (bb2
->succs
) != 2
1513 || !any_condjump_p (BB_END (bb2
))
1514 || !onlyjump_p (BB_END (bb2
)))
1517 b1
= BRANCH_EDGE (bb1
);
1518 b2
= BRANCH_EDGE (bb2
);
1519 f1
= FALLTHRU_EDGE (bb1
);
1520 f2
= FALLTHRU_EDGE (bb2
);
1522 /* Get around possible forwarders on fallthru edges. Other cases
1523 should be optimized out already. */
1524 if (FORWARDER_BLOCK_P (f1
->dest
))
1525 f1
= single_succ_edge (f1
->dest
);
1527 if (FORWARDER_BLOCK_P (f2
->dest
))
1528 f2
= single_succ_edge (f2
->dest
);
1530 /* To simplify use of this function, return false if there are
1531 unneeded forwarder blocks. These will get eliminated later
1532 during cleanup_cfg. */
1533 if (FORWARDER_BLOCK_P (f1
->dest
)
1534 || FORWARDER_BLOCK_P (f2
->dest
)
1535 || FORWARDER_BLOCK_P (b1
->dest
)
1536 || FORWARDER_BLOCK_P (b2
->dest
))
1539 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1541 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1546 set1
= pc_set (BB_END (bb1
));
1547 set2
= pc_set (BB_END (bb2
));
1548 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1549 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1552 cond1
= XEXP (SET_SRC (set1
), 0);
1553 cond2
= XEXP (SET_SRC (set2
), 0);
1554 code1
= GET_CODE (cond1
);
1556 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
1558 code2
= GET_CODE (cond2
);
1560 if (code2
== UNKNOWN
)
1563 /* Verify codes and operands match. */
1564 match
= ((code1
== code2
1565 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1566 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1567 || (code1
== swap_condition (code2
)
1568 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1570 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1573 /* If we return true, we will join the blocks. Which means that
1574 we will only have one branch prediction bit to work with. Thus
1575 we require the existing branches to have probabilities that are
1578 && optimize_bb_for_speed_p (bb1
)
1579 && optimize_bb_for_speed_p (bb2
))
1583 if (b1
->dest
== b2
->dest
)
1584 prob2
= b2
->probability
;
1586 /* Do not use f2 probability as f2 may be forwarded. */
1587 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1589 /* Fail if the difference in probabilities is greater than 50%.
1590 This rules out two well-predicted branches with opposite
1592 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1596 "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
1597 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1603 if (dump_file
&& match
)
1604 fprintf (dump_file
, "Conditionals in bb %i and %i match.\n",
1605 bb1
->index
, bb2
->index
);
1610 /* Generic case - we are seeing a computed jump, table jump or trapping
1613 /* Check whether there are tablejumps in the end of BB1 and BB2.
1614 Return true if they are identical. */
1619 if (tablejump_p (BB_END (bb1
), &label1
, &table1
)
1620 && tablejump_p (BB_END (bb2
), &label2
, &table2
)
1621 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1623 /* The labels should never be the same rtx. If they really are same
1624 the jump tables are same too. So disable crossjumping of blocks BB1
1625 and BB2 because when deleting the common insns in the end of BB1
1626 by delete_basic_block () the jump table would be deleted too. */
1627 /* If LABEL2 is referenced in BB1->END do not do anything
1628 because we would loose information when replacing
1629 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1630 if (label1
!= label2
&& !rtx_referenced_p (label2
, BB_END (bb1
)))
1632 /* Set IDENTICAL to true when the tables are identical. */
1633 bool identical
= false;
1636 p1
= PATTERN (table1
);
1637 p2
= PATTERN (table2
);
1638 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1642 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1643 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1644 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1645 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1650 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1651 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1657 replace_label_data rr
;
1660 /* Temporarily replace references to LABEL1 with LABEL2
1661 in BB1->END so that we could compare the instructions. */
1664 rr
.update_label_nuses
= false;
1665 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1667 match
= (old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
))
1669 if (dump_file
&& match
)
1671 "Tablejumps in bb %i and %i match.\n",
1672 bb1
->index
, bb2
->index
);
1674 /* Set the original label in BB1->END because when deleting
1675 a block whose end is a tablejump, the tablejump referenced
1676 from the instruction is deleted too. */
1679 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1688 /* First ensure that the instructions match. There may be many outgoing
1689 edges so this test is generally cheaper. */
1690 if (old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
)) != dir_both
)
1693 /* Search the outgoing edges, ensure that the counts do match, find possible
1694 fallthru and exception handling edges since these needs more
1696 if (EDGE_COUNT (bb1
->succs
) != EDGE_COUNT (bb2
->succs
))
1699 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1701 e2
= EDGE_SUCC (bb2
, ei
.index
);
1703 if (e1
->flags
& EDGE_EH
)
1706 if (e2
->flags
& EDGE_EH
)
1709 if (e1
->flags
& EDGE_FALLTHRU
)
1711 if (e2
->flags
& EDGE_FALLTHRU
)
1715 /* If number of edges of various types does not match, fail. */
1716 if (nehedges1
!= nehedges2
1717 || (fallthru1
!= 0) != (fallthru2
!= 0))
1720 /* fallthru edges must be forwarded to the same destination. */
1723 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1724 ? single_succ (fallthru1
->dest
): fallthru1
->dest
);
1725 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1726 ? single_succ (fallthru2
->dest
): fallthru2
->dest
);
1732 /* Ensure the same EH region. */
1734 rtx n1
= find_reg_note (BB_END (bb1
), REG_EH_REGION
, 0);
1735 rtx n2
= find_reg_note (BB_END (bb2
), REG_EH_REGION
, 0);
1740 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1744 /* The same checks as in try_crossjump_to_edge. It is required for RTL
1745 version of sequence abstraction. */
1746 FOR_EACH_EDGE (e1
, ei
, bb2
->succs
)
1750 basic_block d1
= e1
->dest
;
1752 if (FORWARDER_BLOCK_P (d1
))
1753 d1
= EDGE_SUCC (d1
, 0)->dest
;
1755 FOR_EACH_EDGE (e2
, ei
, bb1
->succs
)
1757 basic_block d2
= e2
->dest
;
1758 if (FORWARDER_BLOCK_P (d2
))
1759 d2
= EDGE_SUCC (d2
, 0)->dest
;
1771 /* Returns true if BB basic block has a preserve label. */
1774 block_has_preserve_label (basic_block bb
)
1778 && LABEL_PRESERVE_P (block_label (bb
)));
1781 /* E1 and E2 are edges with the same destination block. Search their
1782 predecessors for common code. If found, redirect control flow from
1783 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC (dir_forward),
1784 or the other way around (dir_backward). DIR specifies the allowed
1785 replacement direction. */
1788 try_crossjump_to_edge (int mode
, edge e1
, edge e2
,
1789 enum replace_direction dir
)
1792 basic_block src1
= e1
->src
, src2
= e2
->src
;
1793 basic_block redirect_to
, redirect_from
, to_remove
;
1794 basic_block osrc1
, osrc2
, redirect_edges_to
, tmp
;
1795 rtx newpos1
, newpos2
;
1799 newpos1
= newpos2
= NULL_RTX
;
1801 /* If we have partitioned hot/cold basic blocks, it is a bad idea
1802 to try this optimization.
1804 Basic block partitioning may result in some jumps that appear to
1805 be optimizable (or blocks that appear to be mergeable), but which really
1806 must be left untouched (they are required to make it safely across
1807 partition boundaries). See the comments at the top of
1808 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1810 if (flag_reorder_blocks_and_partition
&& reload_completed
)
1813 /* Search backward through forwarder blocks. We don't need to worry
1814 about multiple entry or chained forwarders, as they will be optimized
1815 away. We do this to look past the unconditional jump following a
1816 conditional jump that is required due to the current CFG shape. */
1817 if (single_pred_p (src1
)
1818 && FORWARDER_BLOCK_P (src1
))
1819 e1
= single_pred_edge (src1
), src1
= e1
->src
;
1821 if (single_pred_p (src2
)
1822 && FORWARDER_BLOCK_P (src2
))
1823 e2
= single_pred_edge (src2
), src2
= e2
->src
;
1825 /* Nothing to do if we reach ENTRY, or a common source block. */
1826 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1831 /* Seeing more than 1 forwarder blocks would confuse us later... */
1832 if (FORWARDER_BLOCK_P (e1
->dest
)
1833 && FORWARDER_BLOCK_P (single_succ (e1
->dest
)))
1836 if (FORWARDER_BLOCK_P (e2
->dest
)
1837 && FORWARDER_BLOCK_P (single_succ (e2
->dest
)))
1840 /* Likewise with dead code (possibly newly created by the other optimizations
1842 if (EDGE_COUNT (src1
->preds
) == 0 || EDGE_COUNT (src2
->preds
) == 0)
1845 /* Look for the common insn sequence, part the first ... */
1846 if (!outgoing_edges_match (mode
, src1
, src2
))
1849 /* ... and part the second. */
1850 nmatch
= flow_find_cross_jump (src1
, src2
, &newpos1
, &newpos2
, &dir
);
1854 if (newpos1
!= NULL_RTX
)
1855 src1
= BLOCK_FOR_INSN (newpos1
);
1856 if (newpos2
!= NULL_RTX
)
1857 src2
= BLOCK_FOR_INSN (newpos2
);
1859 if (dir
== dir_backward
)
1861 #define SWAP(T, X, Y) do { T tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
1862 SWAP (basic_block
, osrc1
, osrc2
);
1863 SWAP (basic_block
, src1
, src2
);
1864 SWAP (edge
, e1
, e2
);
1865 SWAP (rtx
, newpos1
, newpos2
);
1869 /* Don't proceed with the crossjump unless we found a sufficient number
1870 of matching instructions or the 'from' block was totally matched
1871 (such that its predecessors will hopefully be redirected and the
1873 if ((nmatch
< PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS
))
1874 && (newpos1
!= BB_HEAD (src1
)))
1877 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */
1878 if (block_has_preserve_label (e1
->dest
)
1879 && (e1
->flags
& EDGE_ABNORMAL
))
1882 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1884 If we have tablejumps in the end of SRC1 and SRC2
1885 they have been already compared for equivalence in outgoing_edges_match ()
1886 so replace the references to TABLE1 by references to TABLE2. */
1891 if (tablejump_p (BB_END (osrc1
), &label1
, &table1
)
1892 && tablejump_p (BB_END (osrc2
), &label2
, &table2
)
1893 && label1
!= label2
)
1895 replace_label_data rr
;
1898 /* Replace references to LABEL1 with LABEL2. */
1901 rr
.update_label_nuses
= true;
1902 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1904 /* Do not replace the label in SRC1->END because when deleting
1905 a block whose end is a tablejump, the tablejump referenced
1906 from the instruction is deleted too. */
1907 if (insn
!= BB_END (osrc1
))
1908 for_each_rtx (&insn
, replace_label
, &rr
);
1913 /* Avoid splitting if possible. We must always split when SRC2 has
1914 EH predecessor edges, or we may end up with basic blocks with both
1915 normal and EH predecessor edges. */
1916 if (newpos2
== BB_HEAD (src2
)
1917 && !(EDGE_PRED (src2
, 0)->flags
& EDGE_EH
))
1921 if (newpos2
== BB_HEAD (src2
))
1923 /* Skip possible basic block header. */
1924 if (LABEL_P (newpos2
))
1925 newpos2
= NEXT_INSN (newpos2
);
1926 while (DEBUG_INSN_P (newpos2
))
1927 newpos2
= NEXT_INSN (newpos2
);
1928 if (NOTE_P (newpos2
))
1929 newpos2
= NEXT_INSN (newpos2
);
1930 while (DEBUG_INSN_P (newpos2
))
1931 newpos2
= NEXT_INSN (newpos2
);
1935 fprintf (dump_file
, "Splitting bb %i before %i insns\n",
1936 src2
->index
, nmatch
);
1937 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
1942 "Cross jumping from bb %i to bb %i; %i common insns\n",
1943 src1
->index
, src2
->index
, nmatch
);
1945 /* We may have some registers visible through the block. */
1946 df_set_bb_dirty (redirect_to
);
1949 redirect_edges_to
= redirect_to
;
1951 redirect_edges_to
= osrc2
;
1953 /* Recompute the frequencies and counts of outgoing edges. */
1954 FOR_EACH_EDGE (s
, ei
, redirect_edges_to
->succs
)
1958 basic_block d
= s
->dest
;
1960 if (FORWARDER_BLOCK_P (d
))
1961 d
= single_succ (d
);
1963 FOR_EACH_EDGE (s2
, ei
, src1
->succs
)
1965 basic_block d2
= s2
->dest
;
1966 if (FORWARDER_BLOCK_P (d2
))
1967 d2
= single_succ (d2
);
1972 s
->count
+= s2
->count
;
1974 /* Take care to update possible forwarder blocks. We verified
1975 that there is no more than one in the chain, so we can't run
1976 into infinite loop. */
1977 if (FORWARDER_BLOCK_P (s
->dest
))
1979 single_succ_edge (s
->dest
)->count
+= s2
->count
;
1980 s
->dest
->count
+= s2
->count
;
1981 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
1984 if (FORWARDER_BLOCK_P (s2
->dest
))
1986 single_succ_edge (s2
->dest
)->count
-= s2
->count
;
1987 if (single_succ_edge (s2
->dest
)->count
< 0)
1988 single_succ_edge (s2
->dest
)->count
= 0;
1989 s2
->dest
->count
-= s2
->count
;
1990 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
1991 if (s2
->dest
->frequency
< 0)
1992 s2
->dest
->frequency
= 0;
1993 if (s2
->dest
->count
< 0)
1994 s2
->dest
->count
= 0;
1997 if (!redirect_edges_to
->frequency
&& !src1
->frequency
)
1998 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
2001 = ((s
->probability
* redirect_edges_to
->frequency
+
2002 s2
->probability
* src1
->frequency
)
2003 / (redirect_edges_to
->frequency
+ src1
->frequency
));
2006 /* Adjust count and frequency for the block. An earlier jump
2007 threading pass may have left the profile in an inconsistent
2008 state (see update_bb_profile_for_threading) so we must be
2009 prepared for overflows. */
2013 tmp
->count
+= src1
->count
;
2014 tmp
->frequency
+= src1
->frequency
;
2015 if (tmp
->frequency
> BB_FREQ_MAX
)
2016 tmp
->frequency
= BB_FREQ_MAX
;
2017 if (tmp
== redirect_edges_to
)
2019 tmp
= find_fallthru_edge (tmp
->succs
)->dest
;
2022 update_br_prob_note (redirect_edges_to
);
2024 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
2026 /* Skip possible basic block header. */
2027 if (LABEL_P (newpos1
))
2028 newpos1
= NEXT_INSN (newpos1
);
2030 while (DEBUG_INSN_P (newpos1
))
2031 newpos1
= NEXT_INSN (newpos1
);
2033 if (NOTE_INSN_BASIC_BLOCK_P (newpos1
))
2034 newpos1
= NEXT_INSN (newpos1
);
2036 while (DEBUG_INSN_P (newpos1
))
2037 newpos1
= NEXT_INSN (newpos1
);
2039 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
2040 to_remove
= single_succ (redirect_from
);
2042 redirect_edge_and_branch_force (single_succ_edge (redirect_from
), redirect_to
);
2043 delete_basic_block (to_remove
);
2045 update_forwarder_flag (redirect_from
);
2046 if (redirect_to
!= src2
)
2047 update_forwarder_flag (src2
);
2052 /* Search the predecessors of BB for common insn sequences. When found,
2053 share code between them by redirecting control flow. Return true if
2054 any changes made. */
2057 try_crossjump_bb (int mode
, basic_block bb
)
2059 edge e
, e2
, fallthru
;
2061 unsigned max
, ix
, ix2
;
2063 /* Nothing to do if there is not at least two incoming edges. */
2064 if (EDGE_COUNT (bb
->preds
) < 2)
2067 /* Don't crossjump if this block ends in a computed jump,
2068 unless we are optimizing for size. */
2069 if (optimize_bb_for_size_p (bb
)
2070 && bb
!= EXIT_BLOCK_PTR
2071 && computed_jump_p (BB_END (bb
)))
2074 /* If we are partitioning hot/cold basic blocks, we don't want to
2075 mess up unconditional or indirect jumps that cross between hot
2078 Basic block partitioning may result in some jumps that appear to
2079 be optimizable (or blocks that appear to be mergeable), but which really
2080 must be left untouched (they are required to make it safely across
2081 partition boundaries). See the comments at the top of
2082 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
2084 if (BB_PARTITION (EDGE_PRED (bb
, 0)->src
) !=
2085 BB_PARTITION (EDGE_PRED (bb
, 1)->src
)
2086 || (EDGE_PRED (bb
, 0)->flags
& EDGE_CROSSING
))
2089 /* It is always cheapest to redirect a block that ends in a branch to
2090 a block that falls through into BB, as that adds no branches to the
2091 program. We'll try that combination first. */
2093 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
2095 if (EDGE_COUNT (bb
->preds
) > max
)
2098 fallthru
= find_fallthru_edge (bb
->preds
);
2101 for (ix
= 0; ix
< EDGE_COUNT (bb
->preds
);)
2103 e
= EDGE_PRED (bb
, ix
);
2106 /* As noted above, first try with the fallthru predecessor (or, a
2107 fallthru predecessor if we are in cfglayout mode). */
2110 /* Don't combine the fallthru edge into anything else.
2111 If there is a match, we'll do it the other way around. */
2114 /* If nothing changed since the last attempt, there is nothing
2117 && !((e
->src
->flags
& BB_MODIFIED
)
2118 || (fallthru
->src
->flags
& BB_MODIFIED
)))
2121 if (try_crossjump_to_edge (mode
, e
, fallthru
, dir_forward
))
2129 /* Non-obvious work limiting check: Recognize that we're going
2130 to call try_crossjump_bb on every basic block. So if we have
2131 two blocks with lots of outgoing edges (a switch) and they
2132 share lots of common destinations, then we would do the
2133 cross-jump check once for each common destination.
2135 Now, if the blocks actually are cross-jump candidates, then
2136 all of their destinations will be shared. Which means that
2137 we only need check them for cross-jump candidacy once. We
2138 can eliminate redundant checks of crossjump(A,B) by arbitrarily
2139 choosing to do the check from the block for which the edge
2140 in question is the first successor of A. */
2141 if (EDGE_SUCC (e
->src
, 0) != e
)
2144 for (ix2
= 0; ix2
< EDGE_COUNT (bb
->preds
); ix2
++)
2146 e2
= EDGE_PRED (bb
, ix2
);
2151 /* We've already checked the fallthru edge above. */
2155 /* The "first successor" check above only prevents multiple
2156 checks of crossjump(A,B). In order to prevent redundant
2157 checks of crossjump(B,A), require that A be the block
2158 with the lowest index. */
2159 if (e
->src
->index
> e2
->src
->index
)
2162 /* If nothing changed since the last attempt, there is nothing
2165 && !((e
->src
->flags
& BB_MODIFIED
)
2166 || (e2
->src
->flags
& BB_MODIFIED
)))
2169 /* Both e and e2 are not fallthru edges, so we can crossjump in either
2171 if (try_crossjump_to_edge (mode
, e
, e2
, dir_both
))
2181 crossjumps_occured
= true;
2186 /* Search the successors of BB for common insn sequences. When found,
2187 share code between them by moving it across the basic block
2188 boundary. Return true if any changes made. */
2191 try_head_merge_bb (basic_block bb
)
2193 basic_block final_dest_bb
= NULL
;
2194 int max_match
= INT_MAX
;
2196 rtx
*headptr
, *currptr
, *nextptr
;
2197 bool changed
, moveall
;
2199 rtx e0_last_head
, cond
, move_before
;
2200 unsigned nedges
= EDGE_COUNT (bb
->succs
);
2201 rtx jump
= BB_END (bb
);
2202 regset live
, live_union
;
2204 /* Nothing to do if there is not at least two outgoing edges. */
2208 /* Don't crossjump if this block ends in a computed jump,
2209 unless we are optimizing for size. */
2210 if (optimize_bb_for_size_p (bb
)
2211 && bb
!= EXIT_BLOCK_PTR
2212 && computed_jump_p (BB_END (bb
)))
2215 cond
= get_condition (jump
, &move_before
, true, false);
2216 if (cond
== NULL_RTX
)
2219 for (ix
= 0; ix
< nedges
; ix
++)
2220 if (EDGE_SUCC (bb
, ix
)->dest
== EXIT_BLOCK_PTR
)
2223 for (ix
= 0; ix
< nedges
; ix
++)
2225 edge e
= EDGE_SUCC (bb
, ix
);
2226 basic_block other_bb
= e
->dest
;
2228 if (df_get_bb_dirty (other_bb
))
2230 block_was_dirty
= true;
2234 if (e
->flags
& EDGE_ABNORMAL
)
2237 /* Normally, all destination blocks must only be reachable from this
2238 block, i.e. they must have one incoming edge.
2240 There is one special case we can handle, that of multiple consecutive
2241 jumps where the first jumps to one of the targets of the second jump.
2242 This happens frequently in switch statements for default labels.
2243 The structure is as follows:
2249 jump with targets A, B, C, D...
2251 has two incoming edges, from FINAL_DEST_BB and BB
2253 In this case, we can try to move the insns through BB and into
2255 if (EDGE_COUNT (other_bb
->preds
) != 1)
2257 edge incoming_edge
, incoming_bb_other_edge
;
2260 if (final_dest_bb
!= NULL
2261 || EDGE_COUNT (other_bb
->preds
) != 2)
2264 /* We must be able to move the insns across the whole block. */
2265 move_before
= BB_HEAD (bb
);
2266 while (!NONDEBUG_INSN_P (move_before
))
2267 move_before
= NEXT_INSN (move_before
);
2269 if (EDGE_COUNT (bb
->preds
) != 1)
2271 incoming_edge
= EDGE_PRED (bb
, 0);
2272 final_dest_bb
= incoming_edge
->src
;
2273 if (EDGE_COUNT (final_dest_bb
->succs
) != 2)
2275 FOR_EACH_EDGE (incoming_bb_other_edge
, ei
, final_dest_bb
->succs
)
2276 if (incoming_bb_other_edge
!= incoming_edge
)
2278 if (incoming_bb_other_edge
->dest
!= other_bb
)
2283 e0
= EDGE_SUCC (bb
, 0);
2284 e0_last_head
= NULL_RTX
;
2287 for (ix
= 1; ix
< nedges
; ix
++)
2289 edge e
= EDGE_SUCC (bb
, ix
);
2290 rtx e0_last
, e_last
;
2293 nmatch
= flow_find_head_matching_sequence (e0
->dest
, e
->dest
,
2294 &e0_last
, &e_last
, 0);
2298 if (nmatch
< max_match
)
2301 e0_last_head
= e0_last
;
2305 /* If we matched an entire block, we probably have to avoid moving the
2308 && e0_last_head
== BB_END (e0
->dest
)
2309 && (find_reg_note (e0_last_head
, REG_EH_REGION
, 0)
2310 || control_flow_insn_p (e0_last_head
)))
2316 e0_last_head
= prev_real_insn (e0_last_head
);
2317 while (DEBUG_INSN_P (e0_last_head
));
2323 /* We must find a union of the live registers at each of the end points. */
2324 live
= BITMAP_ALLOC (NULL
);
2325 live_union
= BITMAP_ALLOC (NULL
);
2327 currptr
= XNEWVEC (rtx
, nedges
);
2328 headptr
= XNEWVEC (rtx
, nedges
);
2329 nextptr
= XNEWVEC (rtx
, nedges
);
2331 for (ix
= 0; ix
< nedges
; ix
++)
2334 basic_block merge_bb
= EDGE_SUCC (bb
, ix
)->dest
;
2335 rtx head
= BB_HEAD (merge_bb
);
2337 while (!NONDEBUG_INSN_P (head
))
2338 head
= NEXT_INSN (head
);
2342 /* Compute the end point and live information */
2343 for (j
= 1; j
< max_match
; j
++)
2345 head
= NEXT_INSN (head
);
2346 while (!NONDEBUG_INSN_P (head
));
2347 simulate_backwards_to_point (merge_bb
, live
, head
);
2348 IOR_REG_SET (live_union
, live
);
2351 /* If we're moving across two blocks, verify the validity of the
2352 first move, then adjust the target and let the loop below deal
2353 with the final move. */
2354 if (final_dest_bb
!= NULL
)
2358 moveall
= can_move_insns_across (currptr
[0], e0_last_head
, move_before
,
2359 jump
, e0
->dest
, live_union
,
2363 if (move_upto
== NULL_RTX
)
2366 while (e0_last_head
!= move_upto
)
2368 df_simulate_one_insn_backwards (e0
->dest
, e0_last_head
,
2370 e0_last_head
= PREV_INSN (e0_last_head
);
2373 if (e0_last_head
== NULL_RTX
)
2376 jump
= BB_END (final_dest_bb
);
2377 cond
= get_condition (jump
, &move_before
, true, false);
2378 if (cond
== NULL_RTX
)
2385 moveall
= can_move_insns_across (currptr
[0], e0_last_head
,
2386 move_before
, jump
, e0
->dest
, live_union
,
2388 if (!moveall
&& move_upto
== NULL_RTX
)
2390 if (jump
== move_before
)
2393 /* Try again, using a different insertion point. */
2397 /* Don't try moving before a cc0 user, as that may invalidate
2399 if (reg_mentioned_p (cc0_rtx
, jump
))
2406 if (final_dest_bb
&& !moveall
)
2407 /* We haven't checked whether a partial move would be OK for the first
2408 move, so we have to fail this case. */
2414 if (currptr
[0] == move_upto
)
2416 for (ix
= 0; ix
< nedges
; ix
++)
2418 rtx curr
= currptr
[ix
];
2420 curr
= NEXT_INSN (curr
);
2421 while (!NONDEBUG_INSN_P (curr
));
2426 /* If we can't currently move all of the identical insns, remember
2427 each insn after the range that we'll merge. */
2429 for (ix
= 0; ix
< nedges
; ix
++)
2431 rtx curr
= currptr
[ix
];
2433 curr
= NEXT_INSN (curr
);
2434 while (!NONDEBUG_INSN_P (curr
));
2438 reorder_insns (headptr
[0], currptr
[0], PREV_INSN (move_before
));
2439 df_set_bb_dirty (EDGE_SUCC (bb
, 0)->dest
);
2440 if (final_dest_bb
!= NULL
)
2441 df_set_bb_dirty (final_dest_bb
);
2442 df_set_bb_dirty (bb
);
2443 for (ix
= 1; ix
< nedges
; ix
++)
2445 df_set_bb_dirty (EDGE_SUCC (bb
, ix
)->dest
);
2446 delete_insn_chain (headptr
[ix
], currptr
[ix
], false);
2450 if (jump
== move_before
)
2453 /* For the unmerged insns, try a different insertion point. */
2457 /* Don't try moving before a cc0 user, as that may invalidate
2459 if (reg_mentioned_p (cc0_rtx
, jump
))
2463 for (ix
= 0; ix
< nedges
; ix
++)
2464 currptr
[ix
] = headptr
[ix
] = nextptr
[ix
];
2474 crossjumps_occured
|= changed
;
2479 /* Return true if BB contains just bb note, or bb note followed
2480 by only DEBUG_INSNs. */
2483 trivially_empty_bb_p (basic_block bb
)
2485 rtx insn
= BB_END (bb
);
2489 if (insn
== BB_HEAD (bb
))
2491 if (!DEBUG_INSN_P (insn
))
2493 insn
= PREV_INSN (insn
);
2497 /* Do simple CFG optimizations - basic block merging, simplifying of jump
2498 instructions etc. Return nonzero if changes were made. */
2501 try_optimize_cfg (int mode
)
2503 bool changed_overall
= false;
2506 basic_block bb
, b
, next
;
2508 if (mode
& (CLEANUP_CROSSJUMP
| CLEANUP_THREADING
))
2511 crossjumps_occured
= false;
2514 update_forwarder_flag (bb
);
2516 if (! targetm
.cannot_modify_jumps_p ())
2519 /* Attempt to merge blocks as made possible by edge removal. If
2520 a block has only one successor, and the successor has only
2521 one predecessor, they may be combined. */
2524 block_was_dirty
= false;
2530 "\n\ntry_optimize_cfg iteration %i\n\n",
2533 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
;)
2537 bool changed_here
= false;
2539 /* Delete trivially dead basic blocks. This is either
2540 blocks with no predecessors, or empty blocks with no
2541 successors. However if the empty block with no
2542 successors is the successor of the ENTRY_BLOCK, it is
2543 kept. This ensures that the ENTRY_BLOCK will have a
2544 successor which is a precondition for many RTL
2545 passes. Empty blocks may result from expanding
2546 __builtin_unreachable (). */
2547 if (EDGE_COUNT (b
->preds
) == 0
2548 || (EDGE_COUNT (b
->succs
) == 0
2549 && trivially_empty_bb_p (b
)
2550 && single_succ_edge (ENTRY_BLOCK_PTR
)->dest
!= b
))
2553 if (EDGE_COUNT (b
->preds
) > 0)
2558 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2560 if (b
->il
.rtl
->footer
2561 && BARRIER_P (b
->il
.rtl
->footer
))
2562 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2563 if ((e
->flags
& EDGE_FALLTHRU
)
2564 && e
->src
->il
.rtl
->footer
== NULL
)
2566 if (b
->il
.rtl
->footer
)
2568 e
->src
->il
.rtl
->footer
= b
->il
.rtl
->footer
;
2569 b
->il
.rtl
->footer
= NULL
;
2574 e
->src
->il
.rtl
->footer
= emit_barrier ();
2581 rtx last
= get_last_bb_insn (b
);
2582 if (last
&& BARRIER_P (last
))
2583 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2584 if ((e
->flags
& EDGE_FALLTHRU
))
2585 emit_barrier_after (BB_END (e
->src
));
2588 delete_basic_block (b
);
2590 /* Avoid trying to remove ENTRY_BLOCK_PTR. */
2591 b
= (c
== ENTRY_BLOCK_PTR
? c
->next_bb
: c
);
2595 /* Remove code labels no longer used. */
2596 if (single_pred_p (b
)
2597 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2598 && !(single_pred_edge (b
)->flags
& EDGE_COMPLEX
)
2599 && LABEL_P (BB_HEAD (b
))
2600 /* If the previous block ends with a branch to this
2601 block, we can't delete the label. Normally this
2602 is a condjump that is yet to be simplified, but
2603 if CASE_DROPS_THRU, this can be a tablejump with
2604 some element going to the same place as the
2605 default (fallthru). */
2606 && (single_pred (b
) == ENTRY_BLOCK_PTR
2607 || !JUMP_P (BB_END (single_pred (b
)))
2608 || ! label_is_jump_target_p (BB_HEAD (b
),
2609 BB_END (single_pred (b
)))))
2611 rtx label
= BB_HEAD (b
);
2613 delete_insn_chain (label
, label
, false);
2614 /* If the case label is undeletable, move it after the
2615 BASIC_BLOCK note. */
2616 if (NOTE_KIND (BB_HEAD (b
)) == NOTE_INSN_DELETED_LABEL
)
2618 rtx bb_note
= NEXT_INSN (BB_HEAD (b
));
2620 reorder_insns_nobb (label
, label
, bb_note
);
2621 BB_HEAD (b
) = bb_note
;
2622 if (BB_END (b
) == bb_note
)
2626 fprintf (dump_file
, "Deleted label in block %i.\n",
2630 /* If we fall through an empty block, we can remove it. */
2631 if (!(mode
& CLEANUP_CFGLAYOUT
)
2632 && single_pred_p (b
)
2633 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2634 && !LABEL_P (BB_HEAD (b
))
2635 && FORWARDER_BLOCK_P (b
)
2636 /* Note that forwarder_block_p true ensures that
2637 there is a successor for this block. */
2638 && (single_succ_edge (b
)->flags
& EDGE_FALLTHRU
)
2639 && n_basic_blocks
> NUM_FIXED_BLOCKS
+ 1)
2643 "Deleting fallthru block %i.\n",
2646 c
= b
->prev_bb
== ENTRY_BLOCK_PTR
? b
->next_bb
: b
->prev_bb
;
2647 redirect_edge_succ_nodup (single_pred_edge (b
),
2649 delete_basic_block (b
);
2655 /* Merge B with its single successor, if any. */
2656 if (single_succ_p (b
)
2657 && (s
= single_succ_edge (b
))
2658 && !(s
->flags
& EDGE_COMPLEX
)
2659 && (c
= s
->dest
) != EXIT_BLOCK_PTR
2660 && single_pred_p (c
)
2663 /* When not in cfg_layout mode use code aware of reordering
2664 INSN. This code possibly creates new basic blocks so it
2665 does not fit merge_blocks interface and is kept here in
2666 hope that it will become useless once more of compiler
2667 is transformed to use cfg_layout mode. */
2669 if ((mode
& CLEANUP_CFGLAYOUT
)
2670 && can_merge_blocks_p (b
, c
))
2672 merge_blocks (b
, c
);
2673 update_forwarder_flag (b
);
2674 changed_here
= true;
2676 else if (!(mode
& CLEANUP_CFGLAYOUT
)
2677 /* If the jump insn has side effects,
2678 we can't kill the edge. */
2679 && (!JUMP_P (BB_END (b
))
2680 || (reload_completed
2681 ? simplejump_p (BB_END (b
))
2682 : (onlyjump_p (BB_END (b
))
2683 && !tablejump_p (BB_END (b
),
2685 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
2688 changed_here
= true;
2692 /* Simplify branch over branch. */
2693 if ((mode
& CLEANUP_EXPENSIVE
)
2694 && !(mode
& CLEANUP_CFGLAYOUT
)
2695 && try_simplify_condjump (b
))
2696 changed_here
= true;
2698 /* If B has a single outgoing edge, but uses a
2699 non-trivial jump instruction without side-effects, we
2700 can either delete the jump entirely, or replace it
2701 with a simple unconditional jump. */
2702 if (single_succ_p (b
)
2703 && single_succ (b
) != EXIT_BLOCK_PTR
2704 && onlyjump_p (BB_END (b
))
2705 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
)
2706 && try_redirect_by_replacing_jump (single_succ_edge (b
),
2708 (mode
& CLEANUP_CFGLAYOUT
) != 0))
2710 update_forwarder_flag (b
);
2711 changed_here
= true;
2714 /* Simplify branch to branch. */
2715 if (try_forward_edges (mode
, b
))
2717 update_forwarder_flag (b
);
2718 changed_here
= true;
2721 /* Look for shared code between blocks. */
2722 if ((mode
& CLEANUP_CROSSJUMP
)
2723 && try_crossjump_bb (mode
, b
))
2724 changed_here
= true;
2726 if ((mode
& CLEANUP_CROSSJUMP
)
2727 /* This can lengthen register lifetimes. Do it only after
2730 && try_head_merge_bb (b
))
2731 changed_here
= true;
2733 /* Don't get confused by the index shift caused by
2741 if ((mode
& CLEANUP_CROSSJUMP
)
2742 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
2745 if (block_was_dirty
)
2747 /* This should only be set by head-merging. */
2748 gcc_assert (mode
& CLEANUP_CROSSJUMP
);
2752 #ifdef ENABLE_CHECKING
2754 verify_flow_info ();
2757 changed_overall
|= changed
;
2764 b
->flags
&= ~(BB_FORWARDER_BLOCK
| BB_NONTHREADABLE_BLOCK
);
2766 return changed_overall
;
2769 /* Delete all unreachable basic blocks. */
2772 delete_unreachable_blocks (void)
2774 bool changed
= false;
2775 basic_block b
, prev_bb
;
2777 find_unreachable_blocks ();
2779 /* When we're in GIMPLE mode and there may be debug insns, we should
2780 delete blocks in reverse dominator order, so as to get a chance
2781 to substitute all released DEFs into debug stmts. If we don't
2782 have dominators information, walking blocks backward gets us a
2783 better chance of retaining most debug information than
2785 if (MAY_HAVE_DEBUG_STMTS
&& current_ir_type () == IR_GIMPLE
2786 && dom_info_available_p (CDI_DOMINATORS
))
2788 for (b
= EXIT_BLOCK_PTR
->prev_bb
; b
!= ENTRY_BLOCK_PTR
; b
= prev_bb
)
2790 prev_bb
= b
->prev_bb
;
2792 if (!(b
->flags
& BB_REACHABLE
))
2794 /* Speed up the removal of blocks that don't dominate
2795 others. Walking backwards, this should be the common
2797 if (!first_dom_son (CDI_DOMINATORS
, b
))
2798 delete_basic_block (b
);
2801 VEC (basic_block
, heap
) *h
2802 = get_all_dominated_blocks (CDI_DOMINATORS
, b
);
2804 while (VEC_length (basic_block
, h
))
2806 b
= VEC_pop (basic_block
, h
);
2808 prev_bb
= b
->prev_bb
;
2810 gcc_assert (!(b
->flags
& BB_REACHABLE
));
2812 delete_basic_block (b
);
2815 VEC_free (basic_block
, heap
, h
);
2824 for (b
= EXIT_BLOCK_PTR
->prev_bb
; b
!= ENTRY_BLOCK_PTR
; b
= prev_bb
)
2826 prev_bb
= b
->prev_bb
;
2828 if (!(b
->flags
& BB_REACHABLE
))
2830 delete_basic_block (b
);
2837 tidy_fallthru_edges ();
2841 /* Delete any jump tables never referenced. We can't delete them at the
2842 time of removing tablejump insn as they are referenced by the preceding
2843 insns computing the destination, so we delay deleting and garbagecollect
2844 them once life information is computed. */
2846 delete_dead_jumptables (void)
2850 /* A dead jump table does not belong to any basic block. Scan insns
2851 between two adjacent basic blocks. */
2856 for (insn
= NEXT_INSN (BB_END (bb
));
2857 insn
&& !NOTE_INSN_BASIC_BLOCK_P (insn
);
2860 next
= NEXT_INSN (insn
);
2862 && LABEL_NUSES (insn
) == LABEL_PRESERVE_P (insn
)
2863 && JUMP_TABLE_DATA_P (next
))
2865 rtx label
= insn
, jump
= next
;
2868 fprintf (dump_file
, "Dead jumptable %i removed\n",
2871 next
= NEXT_INSN (next
);
2873 delete_insn (label
);
2880 /* Tidy the CFG by deleting unreachable code and whatnot. */
2883 cleanup_cfg (int mode
)
2885 bool changed
= false;
2887 /* Set the cfglayout mode flag here. We could update all the callers
2888 but that is just inconvenient, especially given that we eventually
2889 want to have cfglayout mode as the default. */
2890 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2891 mode
|= CLEANUP_CFGLAYOUT
;
2893 timevar_push (TV_CLEANUP_CFG
);
2894 if (delete_unreachable_blocks ())
2897 /* We've possibly created trivially dead code. Cleanup it right
2898 now to introduce more opportunities for try_optimize_cfg. */
2899 if (!(mode
& (CLEANUP_NO_INSN_DEL
))
2900 && !reload_completed
)
2901 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2906 /* To tail-merge blocks ending in the same noreturn function (e.g.
2907 a call to abort) we have to insert fake edges to exit. Do this
2908 here once. The fake edges do not interfere with any other CFG
2910 if (mode
& CLEANUP_CROSSJUMP
)
2911 add_noreturn_fake_exit_edges ();
2913 if (!dbg_cnt (cfg_cleanup
))
2916 while (try_optimize_cfg (mode
))
2918 delete_unreachable_blocks (), changed
= true;
2919 if (!(mode
& CLEANUP_NO_INSN_DEL
))
2921 /* Try to remove some trivially dead insns when doing an expensive
2922 cleanup. But delete_trivially_dead_insns doesn't work after
2923 reload (it only handles pseudos) and run_fast_dce is too costly
2924 to run in every iteration.
2926 For effective cross jumping, we really want to run a fast DCE to
2927 clean up any dead conditions, or they get in the way of performing
2930 Other transformations in cleanup_cfg are not so sensitive to dead
2931 code, so delete_trivially_dead_insns or even doing nothing at all
2933 if ((mode
& CLEANUP_EXPENSIVE
) && !reload_completed
2934 && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
2936 if ((mode
& CLEANUP_CROSSJUMP
) && crossjumps_occured
)
2943 if (mode
& CLEANUP_CROSSJUMP
)
2944 remove_fake_exit_edges ();
2946 /* Don't call delete_dead_jumptables in cfglayout mode, because
2947 that function assumes that jump tables are in the insns stream.
2948 But we also don't _have_ to delete dead jumptables in cfglayout
2949 mode because we shouldn't even be looking at things that are
2950 not in a basic block. Dead jumptables are cleaned up when
2951 going out of cfglayout mode. */
2952 if (!(mode
& CLEANUP_CFGLAYOUT
))
2953 delete_dead_jumptables ();
2955 timevar_pop (TV_CLEANUP_CFG
);
2961 rest_of_handle_jump (void)
2963 if (crtl
->tail_call_emit
)
2964 fixup_tail_calls ();
2968 struct rtl_opt_pass pass_jump
=
2972 "sibling", /* name */
2974 rest_of_handle_jump
, /* execute */
2977 0, /* static_pass_number */
2978 TV_JUMP
, /* tv_id */
2979 0, /* properties_required */
2980 0, /* properties_provided */
2981 0, /* properties_destroyed */
2982 TODO_ggc_collect
, /* todo_flags_start */
2983 TODO_verify_flow
, /* todo_flags_finish */
2989 rest_of_handle_jump2 (void)
2991 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2993 dump_flow_info (dump_file
, dump_flags
);
2994 cleanup_cfg ((optimize
? CLEANUP_EXPENSIVE
: 0)
2995 | (flag_thread_jumps
? CLEANUP_THREADING
: 0));
3000 struct rtl_opt_pass pass_jump2
=
3006 rest_of_handle_jump2
, /* execute */
3009 0, /* static_pass_number */
3010 TV_JUMP
, /* tv_id */
3011 0, /* properties_required */
3012 0, /* properties_provided */
3013 0, /* properties_destroyed */
3014 TODO_ggc_collect
, /* todo_flags_start */
3015 TODO_verify_rtl_sharing
, /* todo_flags_finish */