1 /* Control flow optimization code for GNU compiler.
2 Copyright (C) 1987-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file contains optimizer of the control flow. The main entry point is
21 cleanup_cfg. Following optimizations are performed:
23 - Unreachable blocks removal
24 - Edge forwarding (edge to the forwarder block is forwarded to its
25 successor. Simplification of the branch instruction is performed by
26 underlying infrastructure so branch can be converted to simplejump or
28 - Cross jumping (tail merging)
29 - Conditional jump-around-simplejump simplification
30 - Basic block merging. */
34 #include "coretypes.h"
37 #include "hard-reg-set.h"
39 #include "insn-config.h"
42 #include "diagnostic-core.h"
47 #include "function.h" /* For inline functions in emit-rtl.h they need crtl. */
49 #include "tree-pass.h"
56 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
58 /* Set to true when we are running first pass of try_optimize_cfg loop. */
59 static bool first_pass
;
61 /* Set to true if crossjumps occurred in the latest run of try_optimize_cfg. */
62 static bool crossjumps_occured
;
64 /* Set to true if we couldn't run an optimization due to stale liveness
65 information; we should run df_analyze to enable more opportunities. */
66 static bool block_was_dirty
;
68 static bool try_crossjump_to_edge (int, edge
, edge
, enum replace_direction
);
69 static bool try_crossjump_bb (int, basic_block
);
70 static bool outgoing_edges_match (int, basic_block
, basic_block
);
71 static enum replace_direction
old_insns_match_p (int, rtx
, rtx
);
73 static void merge_blocks_move_predecessor_nojumps (basic_block
, basic_block
);
74 static void merge_blocks_move_successor_nojumps (basic_block
, basic_block
);
75 static bool try_optimize_cfg (int);
76 static bool try_simplify_condjump (basic_block
);
77 static bool try_forward_edges (int, basic_block
);
78 static edge
thread_jump (edge
, basic_block
);
79 static bool mark_effect (rtx
, bitmap
);
80 static void notice_new_block (basic_block
);
81 static void update_forwarder_flag (basic_block
);
82 static int mentions_nonequal_regs (rtx
*, void *);
83 static void merge_memattrs (rtx
, rtx
);
85 /* Set flags for newly created block. */
88 notice_new_block (basic_block bb
)
93 if (forwarder_block_p (bb
))
94 bb
->flags
|= BB_FORWARDER_BLOCK
;
97 /* Recompute forwarder flag after block has been modified. */
100 update_forwarder_flag (basic_block bb
)
102 if (forwarder_block_p (bb
))
103 bb
->flags
|= BB_FORWARDER_BLOCK
;
105 bb
->flags
&= ~BB_FORWARDER_BLOCK
;
108 /* Simplify a conditional jump around an unconditional jump.
109 Return true if something changed. */
112 try_simplify_condjump (basic_block cbranch_block
)
114 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
115 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
118 /* Verify that there are exactly two successors. */
119 if (EDGE_COUNT (cbranch_block
->succs
) != 2)
122 /* Verify that we've got a normal conditional branch at the end
124 cbranch_insn
= BB_END (cbranch_block
);
125 if (!any_condjump_p (cbranch_insn
))
128 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
129 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
131 /* The next block must not have multiple predecessors, must not
132 be the last block in the function, and must contain just the
133 unconditional jump. */
134 jump_block
= cbranch_fallthru_edge
->dest
;
135 if (!single_pred_p (jump_block
)
136 || jump_block
->next_bb
== EXIT_BLOCK_PTR
137 || !FORWARDER_BLOCK_P (jump_block
))
139 jump_dest_block
= single_succ (jump_block
);
141 /* If we are partitioning hot/cold basic blocks, we don't want to
142 mess up unconditional or indirect jumps that cross between hot
145 Basic block partitioning may result in some jumps that appear to
146 be optimizable (or blocks that appear to be mergeable), but which really
147 must be left untouched (they are required to make it safely across
148 partition boundaries). See the comments at the top of
149 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
151 if (BB_PARTITION (jump_block
) != BB_PARTITION (jump_dest_block
)
152 || (cbranch_jump_edge
->flags
& EDGE_CROSSING
))
155 /* The conditional branch must target the block after the
156 unconditional branch. */
157 cbranch_dest_block
= cbranch_jump_edge
->dest
;
159 if (cbranch_dest_block
== EXIT_BLOCK_PTR
160 || !can_fallthru (jump_block
, cbranch_dest_block
))
163 /* Invert the conditional branch. */
164 if (!invert_jump (cbranch_insn
, block_label (jump_dest_block
), 0))
168 fprintf (dump_file
, "Simplifying condjump %i around jump %i\n",
169 INSN_UID (cbranch_insn
), INSN_UID (BB_END (jump_block
)));
171 /* Success. Update the CFG to match. Note that after this point
172 the edge variable names appear backwards; the redirection is done
173 this way to preserve edge profile data. */
174 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
176 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
178 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
179 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
180 update_br_prob_note (cbranch_block
);
182 /* Delete the block with the unconditional jump, and clean up the mess. */
183 delete_basic_block (jump_block
);
184 tidy_fallthru_edge (cbranch_jump_edge
);
185 update_forwarder_flag (cbranch_block
);
190 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
191 on register. Used by jump threading. */
194 mark_effect (rtx exp
, regset nonequal
)
198 switch (GET_CODE (exp
))
200 /* In case we do clobber the register, mark it as equal, as we know the
201 value is dead so it don't have to match. */
203 if (REG_P (XEXP (exp
, 0)))
205 dest
= XEXP (exp
, 0);
206 regno
= REGNO (dest
);
207 if (HARD_REGISTER_NUM_P (regno
))
208 bitmap_clear_range (nonequal
, regno
,
209 hard_regno_nregs
[regno
][GET_MODE (dest
)]);
211 bitmap_clear_bit (nonequal
, regno
);
216 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
218 dest
= SET_DEST (exp
);
223 regno
= REGNO (dest
);
224 if (HARD_REGISTER_NUM_P (regno
))
225 bitmap_set_range (nonequal
, regno
,
226 hard_regno_nregs
[regno
][GET_MODE (dest
)]);
228 bitmap_set_bit (nonequal
, regno
);
236 /* Return nonzero if X is a register set in regset DATA.
237 Called via for_each_rtx. */
239 mentions_nonequal_regs (rtx
*x
, void *data
)
241 regset nonequal
= (regset
) data
;
247 if (REGNO_REG_SET_P (nonequal
, regno
))
249 if (regno
< FIRST_PSEUDO_REGISTER
)
251 int n
= hard_regno_nregs
[regno
][GET_MODE (*x
)];
253 if (REGNO_REG_SET_P (nonequal
, regno
+ n
))
259 /* Attempt to prove that the basic block B will have no side effects and
260 always continues in the same edge if reached via E. Return the edge
261 if exist, NULL otherwise. */
264 thread_jump (edge e
, basic_block b
)
266 rtx set1
, set2
, cond1
, cond2
, insn
;
267 enum rtx_code code1
, code2
, reversed_code2
;
268 bool reverse1
= false;
272 reg_set_iterator rsi
;
274 if (b
->flags
& BB_NONTHREADABLE_BLOCK
)
277 /* At the moment, we do handle only conditional jumps, but later we may
278 want to extend this code to tablejumps and others. */
279 if (EDGE_COUNT (e
->src
->succs
) != 2)
281 if (EDGE_COUNT (b
->succs
) != 2)
283 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
287 /* Second branch must end with onlyjump, as we will eliminate the jump. */
288 if (!any_condjump_p (BB_END (e
->src
)))
291 if (!any_condjump_p (BB_END (b
)) || !onlyjump_p (BB_END (b
)))
293 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
297 set1
= pc_set (BB_END (e
->src
));
298 set2
= pc_set (BB_END (b
));
299 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
300 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
303 cond1
= XEXP (SET_SRC (set1
), 0);
304 cond2
= XEXP (SET_SRC (set2
), 0);
306 code1
= reversed_comparison_code (cond1
, BB_END (e
->src
));
308 code1
= GET_CODE (cond1
);
310 code2
= GET_CODE (cond2
);
311 reversed_code2
= reversed_comparison_code (cond2
, BB_END (b
));
313 if (!comparison_dominates_p (code1
, code2
)
314 && !comparison_dominates_p (code1
, reversed_code2
))
317 /* Ensure that the comparison operators are equivalent.
318 ??? This is far too pessimistic. We should allow swapped operands,
319 different CCmodes, or for example comparisons for interval, that
320 dominate even when operands are not equivalent. */
321 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
322 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
325 /* Short circuit cases where block B contains some side effects, as we can't
327 for (insn
= NEXT_INSN (BB_HEAD (b
)); insn
!= NEXT_INSN (BB_END (b
));
328 insn
= NEXT_INSN (insn
))
329 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
331 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
337 /* First process all values computed in the source basic block. */
338 for (insn
= NEXT_INSN (BB_HEAD (e
->src
));
339 insn
!= NEXT_INSN (BB_END (e
->src
));
340 insn
= NEXT_INSN (insn
))
342 cselib_process_insn (insn
);
344 nonequal
= BITMAP_ALLOC (NULL
);
345 CLEAR_REG_SET (nonequal
);
347 /* Now assume that we've continued by the edge E to B and continue
348 processing as if it were same basic block.
349 Our goal is to prove that whole block is an NOOP. */
351 for (insn
= NEXT_INSN (BB_HEAD (b
));
352 insn
!= NEXT_INSN (BB_END (b
)) && !failed
;
353 insn
= NEXT_INSN (insn
))
357 rtx pat
= PATTERN (insn
);
359 if (GET_CODE (pat
) == PARALLEL
)
361 for (i
= 0; i
< (unsigned)XVECLEN (pat
, 0); i
++)
362 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
365 failed
|= mark_effect (pat
, nonequal
);
368 cselib_process_insn (insn
);
371 /* Later we should clear nonequal of dead registers. So far we don't
372 have life information in cfg_cleanup. */
375 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
379 /* cond2 must not mention any register that is not equal to the
381 if (for_each_rtx (&cond2
, mentions_nonequal_regs
, nonequal
))
384 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, rsi
)
387 BITMAP_FREE (nonequal
);
389 if ((comparison_dominates_p (code1
, code2
) != 0)
390 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
391 return BRANCH_EDGE (b
);
393 return FALLTHRU_EDGE (b
);
396 BITMAP_FREE (nonequal
);
401 /* Attempt to forward edges leaving basic block B.
402 Return true if successful. */
405 try_forward_edges (int mode
, basic_block b
)
407 bool changed
= false;
409 edge e
, *threaded_edges
= NULL
;
411 /* If we are partitioning hot/cold basic blocks, we don't want to
412 mess up unconditional or indirect jumps that cross between hot
415 Basic block partitioning may result in some jumps that appear to
416 be optimizable (or blocks that appear to be mergeable), but which really
417 must be left untouched (they are required to make it safely across
418 partition boundaries). See the comments at the top of
419 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
421 if (find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
424 for (ei
= ei_start (b
->succs
); (e
= ei_safe_edge (ei
)); )
426 basic_block target
, first
;
427 int counter
, goto_locus
;
428 bool threaded
= false;
429 int nthreaded_edges
= 0;
430 bool may_thread
= first_pass
|| (b
->flags
& BB_MODIFIED
) != 0;
432 /* Skip complex edges because we don't know how to update them.
434 Still handle fallthru edges, as we can succeed to forward fallthru
435 edge to the same place as the branch edge of conditional branch
436 and turn conditional branch to an unconditional branch. */
437 if (e
->flags
& EDGE_COMPLEX
)
443 target
= first
= e
->dest
;
444 counter
= NUM_FIXED_BLOCKS
;
445 goto_locus
= e
->goto_locus
;
447 /* If we are partitioning hot/cold basic_blocks, we don't want to mess
448 up jumps that cross between hot/cold sections.
450 Basic block partitioning may result in some jumps that appear
451 to be optimizable (or blocks that appear to be mergeable), but which
452 really must be left untouched (they are required to make it safely
453 across partition boundaries). See the comments at the top of
454 bb-reorder.c:partition_hot_cold_basic_blocks for complete
457 if (first
!= EXIT_BLOCK_PTR
458 && find_reg_note (BB_END (first
), REG_CROSSING_JUMP
, NULL_RTX
))
461 while (counter
< n_basic_blocks
)
463 basic_block new_target
= NULL
;
464 bool new_target_threaded
= false;
465 may_thread
|= (target
->flags
& BB_MODIFIED
) != 0;
467 if (FORWARDER_BLOCK_P (target
)
468 && !(single_succ_edge (target
)->flags
& EDGE_CROSSING
)
469 && single_succ (target
) != EXIT_BLOCK_PTR
)
471 /* Bypass trivial infinite loops. */
472 new_target
= single_succ (target
);
473 if (target
== new_target
)
474 counter
= n_basic_blocks
;
477 /* When not optimizing, ensure that edges or forwarder
478 blocks with different locus are not optimized out. */
479 int new_locus
= single_succ_edge (target
)->goto_locus
;
480 int locus
= goto_locus
;
482 if (new_locus
!= UNKNOWN_LOCATION
483 && locus
!= UNKNOWN_LOCATION
484 && new_locus
!= locus
)
490 if (new_locus
!= UNKNOWN_LOCATION
)
493 last
= BB_END (target
);
494 if (DEBUG_INSN_P (last
))
495 last
= prev_nondebug_insn (last
);
497 new_locus
= last
&& INSN_P (last
)
498 ? INSN_LOCATION (last
) : 0;
500 if (new_locus
!= UNKNOWN_LOCATION
501 && locus
!= UNKNOWN_LOCATION
502 && new_locus
!= locus
)
506 if (new_locus
!= UNKNOWN_LOCATION
)
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
= apply_probability (b
->frequency
, edge_probability
);
604 if (!single_succ_p (first
))
606 gcc_assert (n
< nthreaded_edges
);
607 t
= threaded_edges
[n
++];
608 gcc_assert (t
->src
== first
);
609 update_bb_profile_for_threading (first
, edge_frequency
,
611 update_br_prob_note (first
);
615 first
->count
-= edge_count
;
616 if (first
->count
< 0)
618 first
->frequency
-= edge_frequency
;
619 if (first
->frequency
< 0)
620 first
->frequency
= 0;
621 /* It is possible that as the result of
622 threading we've removed edge as it is
623 threaded to the fallthru edge. Avoid
624 getting out of sync. */
625 if (n
< nthreaded_edges
626 && first
== threaded_edges
[n
]->src
)
628 t
= single_succ_edge (first
);
631 t
->count
-= edge_count
;
636 while (first
!= target
);
644 free (threaded_edges
);
649 /* Blocks A and B are to be merged into a single block. A has no incoming
650 fallthru edge, so it can be moved before B without adding or modifying
651 any jumps (aside from the jump from A to B). */
654 merge_blocks_move_predecessor_nojumps (basic_block a
, basic_block b
)
658 /* If we are partitioning hot/cold basic blocks, we don't want to
659 mess up unconditional or indirect jumps that cross between hot
662 Basic block partitioning may result in some jumps that appear to
663 be optimizable (or blocks that appear to be mergeable), but which really
664 must be left untouched (they are required to make it safely across
665 partition boundaries). See the comments at the top of
666 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
668 if (BB_PARTITION (a
) != BB_PARTITION (b
))
671 barrier
= next_nonnote_insn (BB_END (a
));
672 gcc_assert (BARRIER_P (barrier
));
673 delete_insn (barrier
);
675 /* Scramble the insn chain. */
676 if (BB_END (a
) != PREV_INSN (BB_HEAD (b
)))
677 reorder_insns_nobb (BB_HEAD (a
), BB_END (a
), PREV_INSN (BB_HEAD (b
)));
681 fprintf (dump_file
, "Moved block %d before %d and merged.\n",
684 /* Swap the records for the two blocks around. */
687 link_block (a
, b
->prev_bb
);
689 /* Now blocks A and B are contiguous. Merge them. */
693 /* Blocks A and B are to be merged into a single block. B has no outgoing
694 fallthru edge, so it can be moved after A without adding or modifying
695 any jumps (aside from the jump from A to B). */
698 merge_blocks_move_successor_nojumps (basic_block a
, basic_block b
)
700 rtx barrier
, real_b_end
;
703 /* If we are partitioning hot/cold basic blocks, we don't want to
704 mess up unconditional or indirect jumps that cross between hot
707 Basic block partitioning may result in some jumps that appear to
708 be optimizable (or blocks that appear to be mergeable), but which really
709 must be left untouched (they are required to make it safely across
710 partition boundaries). See the comments at the top of
711 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
713 if (BB_PARTITION (a
) != BB_PARTITION (b
))
716 real_b_end
= BB_END (b
);
718 /* If there is a jump table following block B temporarily add the jump table
719 to block B so that it will also be moved to the correct location. */
720 if (tablejump_p (BB_END (b
), &label
, &table
)
721 && prev_active_insn (label
) == BB_END (b
))
726 /* There had better have been a barrier there. Delete it. */
727 barrier
= NEXT_INSN (BB_END (b
));
728 if (barrier
&& BARRIER_P (barrier
))
729 delete_insn (barrier
);
732 /* Scramble the insn chain. */
733 reorder_insns_nobb (BB_HEAD (b
), BB_END (b
), BB_END (a
));
735 /* Restore the real end of b. */
736 BB_END (b
) = real_b_end
;
739 fprintf (dump_file
, "Moved block %d after %d and merged.\n",
742 /* Now blocks A and B are contiguous. Merge them. */
746 /* Attempt to merge basic blocks that are potentially non-adjacent.
747 Return NULL iff the attempt failed, otherwise return basic block
748 where cleanup_cfg should continue. Because the merging commonly
749 moves basic block away or introduces another optimization
750 possibility, return basic block just before B so cleanup_cfg don't
753 It may be good idea to return basic block before C in the case
754 C has been moved after B and originally appeared earlier in the
755 insn sequence, but we have no information available about the
756 relative ordering of these two. Hopefully it is not too common. */
759 merge_blocks_move (edge e
, basic_block b
, basic_block c
, int mode
)
763 /* If we are partitioning hot/cold basic blocks, we don't want to
764 mess up unconditional or indirect jumps that cross between hot
767 Basic block partitioning may result in some jumps that appear to
768 be optimizable (or blocks that appear to be mergeable), but which really
769 must be left untouched (they are required to make it safely across
770 partition boundaries). See the comments at the top of
771 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
773 if (BB_PARTITION (b
) != BB_PARTITION (c
))
776 /* If B has a fallthru edge to C, no need to move anything. */
777 if (e
->flags
& EDGE_FALLTHRU
)
779 int b_index
= b
->index
, c_index
= c
->index
;
781 /* Protect the loop latches. */
782 if (current_loops
&& c
->loop_father
->latch
== c
)
786 update_forwarder_flag (b
);
789 fprintf (dump_file
, "Merged %d and %d without moving.\n",
792 return b
->prev_bb
== ENTRY_BLOCK_PTR
? b
: b
->prev_bb
;
795 /* Otherwise we will need to move code around. Do that only if expensive
796 transformations are allowed. */
797 else if (mode
& CLEANUP_EXPENSIVE
)
799 edge tmp_edge
, b_fallthru_edge
;
800 bool c_has_outgoing_fallthru
;
801 bool b_has_incoming_fallthru
;
803 /* Avoid overactive code motion, as the forwarder blocks should be
804 eliminated by edge redirection instead. One exception might have
805 been if B is a forwarder block and C has no fallthru edge, but
806 that should be cleaned up by bb-reorder instead. */
807 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
810 /* We must make sure to not munge nesting of lexical blocks,
811 and loop notes. This is done by squeezing out all the notes
812 and leaving them there to lie. Not ideal, but functional. */
814 tmp_edge
= find_fallthru_edge (c
->succs
);
815 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
817 tmp_edge
= find_fallthru_edge (b
->preds
);
818 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
819 b_fallthru_edge
= tmp_edge
;
822 next
= next
->prev_bb
;
824 /* Otherwise, we're going to try to move C after B. If C does
825 not have an outgoing fallthru, then it can be moved
826 immediately after B without introducing or modifying jumps. */
827 if (! c_has_outgoing_fallthru
)
829 merge_blocks_move_successor_nojumps (b
, c
);
830 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
833 /* If B does not have an incoming fallthru, then it can be moved
834 immediately before C without introducing or modifying jumps.
835 C cannot be the first block, so we do not have to worry about
836 accessing a non-existent block. */
838 if (b_has_incoming_fallthru
)
842 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
844 bb
= force_nonfallthru (b_fallthru_edge
);
846 notice_new_block (bb
);
849 merge_blocks_move_predecessor_nojumps (b
, c
);
850 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
857 /* Removes the memory attributes of MEM expression
858 if they are not equal. */
861 merge_memattrs (rtx x
, rtx y
)
870 if (x
== 0 || y
== 0)
875 if (code
!= GET_CODE (y
))
878 if (GET_MODE (x
) != GET_MODE (y
))
881 if (code
== MEM
&& MEM_ATTRS (x
) != MEM_ATTRS (y
))
885 else if (! MEM_ATTRS (y
))
889 HOST_WIDE_INT mem_size
;
891 if (MEM_ALIAS_SET (x
) != MEM_ALIAS_SET (y
))
893 set_mem_alias_set (x
, 0);
894 set_mem_alias_set (y
, 0);
897 if (! mem_expr_equal_p (MEM_EXPR (x
), MEM_EXPR (y
)))
901 clear_mem_offset (x
);
902 clear_mem_offset (y
);
904 else if (MEM_OFFSET_KNOWN_P (x
) != MEM_OFFSET_KNOWN_P (y
)
905 || (MEM_OFFSET_KNOWN_P (x
)
906 && MEM_OFFSET (x
) != MEM_OFFSET (y
)))
908 clear_mem_offset (x
);
909 clear_mem_offset (y
);
912 if (MEM_SIZE_KNOWN_P (x
) && MEM_SIZE_KNOWN_P (y
))
914 mem_size
= MAX (MEM_SIZE (x
), MEM_SIZE (y
));
915 set_mem_size (x
, mem_size
);
916 set_mem_size (y
, mem_size
);
924 set_mem_align (x
, MIN (MEM_ALIGN (x
), MEM_ALIGN (y
)));
925 set_mem_align (y
, MEM_ALIGN (x
));
929 fmt
= GET_RTX_FORMAT (code
);
930 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
935 /* Two vectors must have the same length. */
936 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
939 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
940 merge_memattrs (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
));
945 merge_memattrs (XEXP (x
, i
), XEXP (y
, i
));
952 /* Checks if patterns P1 and P2 are equivalent, apart from the possibly
953 different single sets S1 and S2. */
956 equal_different_set_p (rtx p1
, rtx s1
, rtx p2
, rtx s2
)
961 if (p1
== s1
&& p2
== s2
)
964 if (GET_CODE (p1
) != PARALLEL
|| GET_CODE (p2
) != PARALLEL
)
967 if (XVECLEN (p1
, 0) != XVECLEN (p2
, 0))
970 for (i
= 0; i
< XVECLEN (p1
, 0); i
++)
972 e1
= XVECEXP (p1
, 0, i
);
973 e2
= XVECEXP (p2
, 0, i
);
974 if (e1
== s1
&& e2
== s2
)
977 ? rtx_renumbered_equal_p (e1
, e2
) : rtx_equal_p (e1
, e2
))
986 /* Examine register notes on I1 and I2 and return:
987 - dir_forward if I1 can be replaced by I2, or
988 - dir_backward if I2 can be replaced by I1, or
989 - dir_both if both are the case. */
991 static enum replace_direction
992 can_replace_by (rtx i1
, rtx i2
)
994 rtx s1
, s2
, d1
, d2
, src1
, src2
, note1
, note2
;
997 /* Check for 2 sets. */
998 s1
= single_set (i1
);
999 s2
= single_set (i2
);
1000 if (s1
== NULL_RTX
|| s2
== NULL_RTX
)
1003 /* Check that the 2 sets set the same dest. */
1006 if (!(reload_completed
1007 ? rtx_renumbered_equal_p (d1
, d2
) : rtx_equal_p (d1
, d2
)))
1010 /* Find identical req_equiv or reg_equal note, which implies that the 2 sets
1011 set dest to the same value. */
1012 note1
= find_reg_equal_equiv_note (i1
);
1013 note2
= find_reg_equal_equiv_note (i2
);
1014 if (!note1
|| !note2
|| !rtx_equal_p (XEXP (note1
, 0), XEXP (note2
, 0))
1015 || !CONST_INT_P (XEXP (note1
, 0)))
1018 if (!equal_different_set_p (PATTERN (i1
), s1
, PATTERN (i2
), s2
))
1021 /* Although the 2 sets set dest to the same value, we cannot replace
1022 (set (dest) (const_int))
1025 because we don't know if the reg is live and has the same value at the
1026 location of replacement. */
1027 src1
= SET_SRC (s1
);
1028 src2
= SET_SRC (s2
);
1029 c1
= CONST_INT_P (src1
);
1030 c2
= CONST_INT_P (src2
);
1036 return dir_backward
;
1041 /* Merges directions A and B. */
1043 static enum replace_direction
1044 merge_dir (enum replace_direction a
, enum replace_direction b
)
1046 /* Implements the following table:
1065 /* Examine I1 and I2 and return:
1066 - dir_forward if I1 can be replaced by I2, or
1067 - dir_backward if I2 can be replaced by I1, or
1068 - dir_both if both are the case. */
1070 static enum replace_direction
1071 old_insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx i1
, rtx i2
)
1075 /* Verify that I1 and I2 are equivalent. */
1076 if (GET_CODE (i1
) != GET_CODE (i2
))
1079 /* __builtin_unreachable() may lead to empty blocks (ending with
1080 NOTE_INSN_BASIC_BLOCK). They may be crossjumped. */
1081 if (NOTE_INSN_BASIC_BLOCK_P (i1
) && NOTE_INSN_BASIC_BLOCK_P (i2
))
1084 /* ??? Do not allow cross-jumping between different stack levels. */
1085 p1
= find_reg_note (i1
, REG_ARGS_SIZE
, NULL
);
1086 p2
= find_reg_note (i2
, REG_ARGS_SIZE
, NULL
);
1091 if (!rtx_equal_p (p1
, p2
))
1094 /* ??? Worse, this adjustment had better be constant lest we
1095 have differing incoming stack levels. */
1096 if (!frame_pointer_needed
1097 && find_args_size_adjust (i1
) == HOST_WIDE_INT_MIN
)
1106 if (GET_CODE (p1
) != GET_CODE (p2
))
1109 /* If this is a CALL_INSN, compare register usage information.
1110 If we don't check this on stack register machines, the two
1111 CALL_INSNs might be merged leaving reg-stack.c with mismatching
1112 numbers of stack registers in the same basic block.
1113 If we don't check this on machines with delay slots, a delay slot may
1114 be filled that clobbers a parameter expected by the subroutine.
1116 ??? We take the simple route for now and assume that if they're
1117 equal, they were constructed identically.
1119 Also check for identical exception regions. */
1123 /* Ensure the same EH region. */
1124 rtx n1
= find_reg_note (i1
, REG_EH_REGION
, 0);
1125 rtx n2
= find_reg_note (i2
, REG_EH_REGION
, 0);
1130 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1133 if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
1134 CALL_INSN_FUNCTION_USAGE (i2
))
1135 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
))
1138 /* For address sanitizer, never crossjump __asan_report_* builtins,
1139 otherwise errors might be reported on incorrect lines. */
1140 if (flag_sanitize
& SANITIZE_ADDRESS
)
1142 rtx call
= get_call_rtx_from (i1
);
1143 if (call
&& GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
1145 rtx symbol
= XEXP (XEXP (call
, 0), 0);
1146 if (SYMBOL_REF_DECL (symbol
)
1147 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
1149 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
1151 && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
))
1152 >= BUILT_IN_ASAN_REPORT_LOAD1
1153 && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
))
1154 <= BUILT_IN_ASAN_REPORT_STORE16
)
1162 /* If cross_jump_death_matters is not 0, the insn's mode
1163 indicates whether or not the insn contains any stack-like
1166 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
1168 /* If register stack conversion has already been done, then
1169 death notes must also be compared before it is certain that
1170 the two instruction streams match. */
1173 HARD_REG_SET i1_regset
, i2_regset
;
1175 CLEAR_HARD_REG_SET (i1_regset
);
1176 CLEAR_HARD_REG_SET (i2_regset
);
1178 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
1179 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1180 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
1182 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
1183 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1184 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
1186 if (!hard_reg_set_equal_p (i1_regset
, i2_regset
))
1191 if (reload_completed
1192 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
1195 return can_replace_by (i1
, i2
);
1198 /* When comparing insns I1 and I2 in flow_find_cross_jump or
1199 flow_find_head_matching_sequence, ensure the notes match. */
1202 merge_notes (rtx i1
, rtx i2
)
1204 /* If the merged insns have different REG_EQUAL notes, then
1206 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1207 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1209 if (equiv1
&& !equiv2
)
1210 remove_note (i1
, equiv1
);
1211 else if (!equiv1
&& equiv2
)
1212 remove_note (i2
, equiv2
);
1213 else if (equiv1
&& equiv2
1214 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1216 remove_note (i1
, equiv1
);
1217 remove_note (i2
, equiv2
);
1221 /* Walks from I1 in BB1 backward till the next non-debug insn, and returns the
1222 resulting insn in I1, and the corresponding bb in BB1. At the head of a
1223 bb, if there is a predecessor bb that reaches this bb via fallthru, and
1224 FOLLOW_FALLTHRU, walks further in the predecessor bb and registers this in
1225 DID_FALLTHRU. Otherwise, stops at the head of the bb. */
1228 walk_to_nondebug_insn (rtx
*i1
, basic_block
*bb1
, bool follow_fallthru
,
1233 *did_fallthru
= false;
1236 while (!NONDEBUG_INSN_P (*i1
))
1238 if (*i1
!= BB_HEAD (*bb1
))
1240 *i1
= PREV_INSN (*i1
);
1244 if (!follow_fallthru
)
1247 fallthru
= find_fallthru_edge ((*bb1
)->preds
);
1248 if (!fallthru
|| fallthru
->src
== ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
)
1249 || !single_succ_p (fallthru
->src
))
1252 *bb1
= fallthru
->src
;
1253 *i1
= BB_END (*bb1
);
1254 *did_fallthru
= true;
1258 /* Look through the insns at the end of BB1 and BB2 and find the longest
1259 sequence that are either equivalent, or allow forward or backward
1260 replacement. Store the first insns for that sequence in *F1 and *F2 and
1261 return the sequence length.
1263 DIR_P indicates the allowed replacement direction on function entry, and
1264 the actual replacement direction on function exit. If NULL, only equivalent
1265 sequences are allowed.
1267 To simplify callers of this function, if the blocks match exactly,
1268 store the head of the blocks in *F1 and *F2. */
1271 flow_find_cross_jump (basic_block bb1
, basic_block bb2
, rtx
*f1
, rtx
*f2
,
1272 enum replace_direction
*dir_p
)
1274 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
1277 enum replace_direction dir
, last_dir
, afterlast_dir
;
1278 bool follow_fallthru
, did_fallthru
;
1284 afterlast_dir
= dir
;
1285 last_dir
= afterlast_dir
;
1287 /* Skip simple jumps at the end of the blocks. Complex jumps still
1288 need to be compared for equivalence, which we'll do below. */
1291 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
1293 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1296 i1
= PREV_INSN (i1
);
1301 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1304 /* Count everything except for unconditional jump as insn. */
1305 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1307 i2
= PREV_INSN (i2
);
1312 /* In the following example, we can replace all jumps to C by jumps to A.
1314 This removes 4 duplicate insns.
1315 [bb A] insn1 [bb C] insn1
1321 We could also replace all jumps to A by jumps to C, but that leaves B
1322 alive, and removes only 2 duplicate insns. In a subsequent crossjump
1323 step, all jumps to B would be replaced with jumps to the middle of C,
1324 achieving the same result with more effort.
1325 So we allow only the first possibility, which means that we don't allow
1326 fallthru in the block that's being replaced. */
1328 follow_fallthru
= dir_p
&& dir
!= dir_forward
;
1329 walk_to_nondebug_insn (&i1
, &bb1
, follow_fallthru
, &did_fallthru
);
1333 follow_fallthru
= dir_p
&& dir
!= dir_backward
;
1334 walk_to_nondebug_insn (&i2
, &bb2
, follow_fallthru
, &did_fallthru
);
1338 if (i1
== BB_HEAD (bb1
) || i2
== BB_HEAD (bb2
))
1341 dir
= merge_dir (dir
, old_insns_match_p (0, i1
, i2
));
1342 if (dir
== dir_none
|| (!dir_p
&& dir
!= dir_both
))
1345 merge_memattrs (i1
, i2
);
1347 /* Don't begin a cross-jump with a NOTE insn. */
1350 merge_notes (i1
, i2
);
1352 afterlast1
= last1
, afterlast2
= last2
;
1353 last1
= i1
, last2
= i2
;
1354 afterlast_dir
= last_dir
;
1357 if (!(GET_CODE (p1
) == USE
|| GET_CODE (p1
) == CLOBBER
))
1361 i1
= PREV_INSN (i1
);
1362 i2
= PREV_INSN (i2
);
1366 /* Don't allow the insn after a compare to be shared by
1367 cross-jumping unless the compare is also shared. */
1368 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1369 last1
= afterlast1
, last2
= afterlast2
, last_dir
= afterlast_dir
, ninsns
--;
1372 /* Include preceding notes and labels in the cross-jump. One,
1373 this may bring us to the head of the blocks as requested above.
1374 Two, it keeps line number notes as matched as may be. */
1377 bb1
= BLOCK_FOR_INSN (last1
);
1378 while (last1
!= BB_HEAD (bb1
) && !NONDEBUG_INSN_P (PREV_INSN (last1
)))
1379 last1
= PREV_INSN (last1
);
1381 if (last1
!= BB_HEAD (bb1
) && LABEL_P (PREV_INSN (last1
)))
1382 last1
= PREV_INSN (last1
);
1384 bb2
= BLOCK_FOR_INSN (last2
);
1385 while (last2
!= BB_HEAD (bb2
) && !NONDEBUG_INSN_P (PREV_INSN (last2
)))
1386 last2
= PREV_INSN (last2
);
1388 if (last2
!= BB_HEAD (bb2
) && LABEL_P (PREV_INSN (last2
)))
1389 last2
= PREV_INSN (last2
);
1400 /* Like flow_find_cross_jump, except start looking for a matching sequence from
1401 the head of the two blocks. Do not include jumps at the end.
1402 If STOP_AFTER is nonzero, stop after finding that many matching
1406 flow_find_head_matching_sequence (basic_block bb1
, basic_block bb2
, rtx
*f1
,
1407 rtx
*f2
, int stop_after
)
1409 rtx i1
, i2
, last1
, last2
, beforelast1
, beforelast2
;
1413 int nehedges1
= 0, nehedges2
= 0;
1415 FOR_EACH_EDGE (e
, ei
, bb1
->succs
)
1416 if (e
->flags
& EDGE_EH
)
1418 FOR_EACH_EDGE (e
, ei
, bb2
->succs
)
1419 if (e
->flags
& EDGE_EH
)
1424 last1
= beforelast1
= last2
= beforelast2
= NULL_RTX
;
1428 /* Ignore notes, except NOTE_INSN_EPILOGUE_BEG. */
1429 while (!NONDEBUG_INSN_P (i1
) && i1
!= BB_END (bb1
))
1431 if (NOTE_P (i1
) && NOTE_KIND (i1
) == NOTE_INSN_EPILOGUE_BEG
)
1433 i1
= NEXT_INSN (i1
);
1436 while (!NONDEBUG_INSN_P (i2
) && i2
!= BB_END (bb2
))
1438 if (NOTE_P (i2
) && NOTE_KIND (i2
) == NOTE_INSN_EPILOGUE_BEG
)
1440 i2
= NEXT_INSN (i2
);
1443 if ((i1
== BB_END (bb1
) && !NONDEBUG_INSN_P (i1
))
1444 || (i2
== BB_END (bb2
) && !NONDEBUG_INSN_P (i2
)))
1447 if (NOTE_P (i1
) || NOTE_P (i2
)
1448 || JUMP_P (i1
) || JUMP_P (i2
))
1451 /* A sanity check to make sure we're not merging insns with different
1452 effects on EH. If only one of them ends a basic block, it shouldn't
1453 have an EH edge; if both end a basic block, there should be the same
1454 number of EH edges. */
1455 if ((i1
== BB_END (bb1
) && i2
!= BB_END (bb2
)
1457 || (i2
== BB_END (bb2
) && i1
!= BB_END (bb1
)
1459 || (i1
== BB_END (bb1
) && i2
== BB_END (bb2
)
1460 && nehedges1
!= nehedges2
))
1463 if (old_insns_match_p (0, i1
, i2
) != dir_both
)
1466 merge_memattrs (i1
, i2
);
1468 /* Don't begin a cross-jump with a NOTE insn. */
1471 merge_notes (i1
, i2
);
1473 beforelast1
= last1
, beforelast2
= last2
;
1474 last1
= i1
, last2
= i2
;
1478 if (i1
== BB_END (bb1
) || i2
== BB_END (bb2
)
1479 || (stop_after
> 0 && ninsns
== stop_after
))
1482 i1
= NEXT_INSN (i1
);
1483 i2
= NEXT_INSN (i2
);
1487 /* Don't allow a compare to be shared by cross-jumping unless the insn
1488 after the compare is also shared. */
1489 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && sets_cc0_p (last1
))
1490 last1
= beforelast1
, last2
= beforelast2
, ninsns
--;
1502 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1503 the branch instruction. This means that if we commonize the control
1504 flow before end of the basic block, the semantic remains unchanged.
1506 We may assume that there exists one edge with a common destination. */
1509 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1511 int nehedges1
= 0, nehedges2
= 0;
1512 edge fallthru1
= 0, fallthru2
= 0;
1516 /* If we performed shrink-wrapping, edges to the EXIT_BLOCK_PTR can
1517 only be distinguished for JUMP_INSNs. The two paths may differ in
1518 whether they went through the prologue. Sibcalls are fine, we know
1519 that we either didn't need or inserted an epilogue before them. */
1520 if (crtl
->shrink_wrapped
1521 && single_succ_p (bb1
) && single_succ (bb1
) == EXIT_BLOCK_PTR
1522 && !JUMP_P (BB_END (bb1
))
1523 && !(CALL_P (BB_END (bb1
)) && SIBLING_CALL_P (BB_END (bb1
))))
1526 /* If BB1 has only one successor, we may be looking at either an
1527 unconditional jump, or a fake edge to exit. */
1528 if (single_succ_p (bb1
)
1529 && (single_succ_edge (bb1
)->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1530 && (!JUMP_P (BB_END (bb1
)) || simplejump_p (BB_END (bb1
))))
1531 return (single_succ_p (bb2
)
1532 && (single_succ_edge (bb2
)->flags
1533 & (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1534 && (!JUMP_P (BB_END (bb2
)) || simplejump_p (BB_END (bb2
))));
1536 /* Match conditional jumps - this may get tricky when fallthru and branch
1537 edges are crossed. */
1538 if (EDGE_COUNT (bb1
->succs
) == 2
1539 && any_condjump_p (BB_END (bb1
))
1540 && onlyjump_p (BB_END (bb1
)))
1542 edge b1
, f1
, b2
, f2
;
1543 bool reverse
, match
;
1544 rtx set1
, set2
, cond1
, cond2
;
1545 enum rtx_code code1
, code2
;
1547 if (EDGE_COUNT (bb2
->succs
) != 2
1548 || !any_condjump_p (BB_END (bb2
))
1549 || !onlyjump_p (BB_END (bb2
)))
1552 b1
= BRANCH_EDGE (bb1
);
1553 b2
= BRANCH_EDGE (bb2
);
1554 f1
= FALLTHRU_EDGE (bb1
);
1555 f2
= FALLTHRU_EDGE (bb2
);
1557 /* Get around possible forwarders on fallthru edges. Other cases
1558 should be optimized out already. */
1559 if (FORWARDER_BLOCK_P (f1
->dest
))
1560 f1
= single_succ_edge (f1
->dest
);
1562 if (FORWARDER_BLOCK_P (f2
->dest
))
1563 f2
= single_succ_edge (f2
->dest
);
1565 /* To simplify use of this function, return false if there are
1566 unneeded forwarder blocks. These will get eliminated later
1567 during cleanup_cfg. */
1568 if (FORWARDER_BLOCK_P (f1
->dest
)
1569 || FORWARDER_BLOCK_P (f2
->dest
)
1570 || FORWARDER_BLOCK_P (b1
->dest
)
1571 || FORWARDER_BLOCK_P (b2
->dest
))
1574 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1576 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1581 set1
= pc_set (BB_END (bb1
));
1582 set2
= pc_set (BB_END (bb2
));
1583 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1584 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1587 cond1
= XEXP (SET_SRC (set1
), 0);
1588 cond2
= XEXP (SET_SRC (set2
), 0);
1589 code1
= GET_CODE (cond1
);
1591 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
1593 code2
= GET_CODE (cond2
);
1595 if (code2
== UNKNOWN
)
1598 /* Verify codes and operands match. */
1599 match
= ((code1
== code2
1600 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1601 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1602 || (code1
== swap_condition (code2
)
1603 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1605 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1608 /* If we return true, we will join the blocks. Which means that
1609 we will only have one branch prediction bit to work with. Thus
1610 we require the existing branches to have probabilities that are
1613 && optimize_bb_for_speed_p (bb1
)
1614 && optimize_bb_for_speed_p (bb2
))
1618 if (b1
->dest
== b2
->dest
)
1619 prob2
= b2
->probability
;
1621 /* Do not use f2 probability as f2 may be forwarded. */
1622 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1624 /* Fail if the difference in probabilities is greater than 50%.
1625 This rules out two well-predicted branches with opposite
1627 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1631 "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
1632 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1638 if (dump_file
&& match
)
1639 fprintf (dump_file
, "Conditionals in bb %i and %i match.\n",
1640 bb1
->index
, bb2
->index
);
1645 /* Generic case - we are seeing a computed jump, table jump or trapping
1648 /* Check whether there are tablejumps in the end of BB1 and BB2.
1649 Return true if they are identical. */
1654 if (tablejump_p (BB_END (bb1
), &label1
, &table1
)
1655 && tablejump_p (BB_END (bb2
), &label2
, &table2
)
1656 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1658 /* The labels should never be the same rtx. If they really are same
1659 the jump tables are same too. So disable crossjumping of blocks BB1
1660 and BB2 because when deleting the common insns in the end of BB1
1661 by delete_basic_block () the jump table would be deleted too. */
1662 /* If LABEL2 is referenced in BB1->END do not do anything
1663 because we would loose information when replacing
1664 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1665 if (label1
!= label2
&& !rtx_referenced_p (label2
, BB_END (bb1
)))
1667 /* Set IDENTICAL to true when the tables are identical. */
1668 bool identical
= false;
1671 p1
= PATTERN (table1
);
1672 p2
= PATTERN (table2
);
1673 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1677 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1678 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1679 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1680 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1685 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1686 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1692 replace_label_data rr
;
1695 /* Temporarily replace references to LABEL1 with LABEL2
1696 in BB1->END so that we could compare the instructions. */
1699 rr
.update_label_nuses
= false;
1700 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1702 match
= (old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
))
1704 if (dump_file
&& match
)
1706 "Tablejumps in bb %i and %i match.\n",
1707 bb1
->index
, bb2
->index
);
1709 /* Set the original label in BB1->END because when deleting
1710 a block whose end is a tablejump, the tablejump referenced
1711 from the instruction is deleted too. */
1714 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1723 rtx last1
= BB_END (bb1
);
1724 rtx last2
= BB_END (bb2
);
1725 if (DEBUG_INSN_P (last1
))
1726 last1
= prev_nondebug_insn (last1
);
1727 if (DEBUG_INSN_P (last2
))
1728 last2
= prev_nondebug_insn (last2
);
1729 /* First ensure that the instructions match. There may be many outgoing
1730 edges so this test is generally cheaper. */
1731 if (old_insns_match_p (mode
, last1
, last2
) != dir_both
)
1734 /* Search the outgoing edges, ensure that the counts do match, find possible
1735 fallthru and exception handling edges since these needs more
1737 if (EDGE_COUNT (bb1
->succs
) != EDGE_COUNT (bb2
->succs
))
1740 bool nonfakeedges
= false;
1741 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1743 e2
= EDGE_SUCC (bb2
, ei
.index
);
1745 if ((e1
->flags
& EDGE_FAKE
) == 0)
1746 nonfakeedges
= true;
1748 if (e1
->flags
& EDGE_EH
)
1751 if (e2
->flags
& EDGE_EH
)
1754 if (e1
->flags
& EDGE_FALLTHRU
)
1756 if (e2
->flags
& EDGE_FALLTHRU
)
1760 /* If number of edges of various types does not match, fail. */
1761 if (nehedges1
!= nehedges2
1762 || (fallthru1
!= 0) != (fallthru2
!= 0))
1765 /* If !ACCUMULATE_OUTGOING_ARGS, bb1 (and bb2) have no successors
1766 and the last real insn doesn't have REG_ARGS_SIZE note, don't
1767 attempt to optimize, as the two basic blocks might have different
1768 REG_ARGS_SIZE depths. For noreturn calls and unconditional
1769 traps there should be REG_ARG_SIZE notes, they could be missing
1770 for __builtin_unreachable () uses though. */
1772 && !ACCUMULATE_OUTGOING_ARGS
1774 || !find_reg_note (last1
, REG_ARGS_SIZE
, NULL
)))
1777 /* fallthru edges must be forwarded to the same destination. */
1780 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1781 ? single_succ (fallthru1
->dest
): fallthru1
->dest
);
1782 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1783 ? single_succ (fallthru2
->dest
): fallthru2
->dest
);
1789 /* Ensure the same EH region. */
1791 rtx n1
= find_reg_note (BB_END (bb1
), REG_EH_REGION
, 0);
1792 rtx n2
= find_reg_note (BB_END (bb2
), REG_EH_REGION
, 0);
1797 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1801 /* The same checks as in try_crossjump_to_edge. It is required for RTL
1802 version of sequence abstraction. */
1803 FOR_EACH_EDGE (e1
, ei
, bb2
->succs
)
1807 basic_block d1
= e1
->dest
;
1809 if (FORWARDER_BLOCK_P (d1
))
1810 d1
= EDGE_SUCC (d1
, 0)->dest
;
1812 FOR_EACH_EDGE (e2
, ei
, bb1
->succs
)
1814 basic_block d2
= e2
->dest
;
1815 if (FORWARDER_BLOCK_P (d2
))
1816 d2
= EDGE_SUCC (d2
, 0)->dest
;
1828 /* Returns true if BB basic block has a preserve label. */
1831 block_has_preserve_label (basic_block bb
)
1835 && LABEL_PRESERVE_P (block_label (bb
)));
1838 /* E1 and E2 are edges with the same destination block. Search their
1839 predecessors for common code. If found, redirect control flow from
1840 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC (dir_forward),
1841 or the other way around (dir_backward). DIR specifies the allowed
1842 replacement direction. */
1845 try_crossjump_to_edge (int mode
, edge e1
, edge e2
,
1846 enum replace_direction dir
)
1849 basic_block src1
= e1
->src
, src2
= e2
->src
;
1850 basic_block redirect_to
, redirect_from
, to_remove
;
1851 basic_block osrc1
, osrc2
, redirect_edges_to
, tmp
;
1852 rtx newpos1
, newpos2
;
1856 newpos1
= newpos2
= NULL_RTX
;
1858 /* If we have partitioned hot/cold basic blocks, it is a bad idea
1859 to try this optimization.
1861 Basic block partitioning may result in some jumps that appear to
1862 be optimizable (or blocks that appear to be mergeable), but which really
1863 must be left untouched (they are required to make it safely across
1864 partition boundaries). See the comments at the top of
1865 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1867 if (crtl
->has_bb_partition
&& reload_completed
)
1870 /* Search backward through forwarder blocks. We don't need to worry
1871 about multiple entry or chained forwarders, as they will be optimized
1872 away. We do this to look past the unconditional jump following a
1873 conditional jump that is required due to the current CFG shape. */
1874 if (single_pred_p (src1
)
1875 && FORWARDER_BLOCK_P (src1
))
1876 e1
= single_pred_edge (src1
), src1
= e1
->src
;
1878 if (single_pred_p (src2
)
1879 && FORWARDER_BLOCK_P (src2
))
1880 e2
= single_pred_edge (src2
), src2
= e2
->src
;
1882 /* Nothing to do if we reach ENTRY, or a common source block. */
1883 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1888 /* Seeing more than 1 forwarder blocks would confuse us later... */
1889 if (FORWARDER_BLOCK_P (e1
->dest
)
1890 && FORWARDER_BLOCK_P (single_succ (e1
->dest
)))
1893 if (FORWARDER_BLOCK_P (e2
->dest
)
1894 && FORWARDER_BLOCK_P (single_succ (e2
->dest
)))
1897 /* Likewise with dead code (possibly newly created by the other optimizations
1899 if (EDGE_COUNT (src1
->preds
) == 0 || EDGE_COUNT (src2
->preds
) == 0)
1902 /* Look for the common insn sequence, part the first ... */
1903 if (!outgoing_edges_match (mode
, src1
, src2
))
1906 /* ... and part the second. */
1907 nmatch
= flow_find_cross_jump (src1
, src2
, &newpos1
, &newpos2
, &dir
);
1911 if (newpos1
!= NULL_RTX
)
1912 src1
= BLOCK_FOR_INSN (newpos1
);
1913 if (newpos2
!= NULL_RTX
)
1914 src2
= BLOCK_FOR_INSN (newpos2
);
1916 if (dir
== dir_backward
)
1918 #define SWAP(T, X, Y) do { T tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
1919 SWAP (basic_block
, osrc1
, osrc2
);
1920 SWAP (basic_block
, src1
, src2
);
1921 SWAP (edge
, e1
, e2
);
1922 SWAP (rtx
, newpos1
, newpos2
);
1926 /* Don't proceed with the crossjump unless we found a sufficient number
1927 of matching instructions or the 'from' block was totally matched
1928 (such that its predecessors will hopefully be redirected and the
1930 if ((nmatch
< PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS
))
1931 && (newpos1
!= BB_HEAD (src1
)))
1934 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */
1935 if (block_has_preserve_label (e1
->dest
)
1936 && (e1
->flags
& EDGE_ABNORMAL
))
1939 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1941 If we have tablejumps in the end of SRC1 and SRC2
1942 they have been already compared for equivalence in outgoing_edges_match ()
1943 so replace the references to TABLE1 by references to TABLE2. */
1948 if (tablejump_p (BB_END (osrc1
), &label1
, &table1
)
1949 && tablejump_p (BB_END (osrc2
), &label2
, &table2
)
1950 && label1
!= label2
)
1952 replace_label_data rr
;
1955 /* Replace references to LABEL1 with LABEL2. */
1958 rr
.update_label_nuses
= true;
1959 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1961 /* Do not replace the label in SRC1->END because when deleting
1962 a block whose end is a tablejump, the tablejump referenced
1963 from the instruction is deleted too. */
1964 if (insn
!= BB_END (osrc1
))
1965 for_each_rtx (&insn
, replace_label
, &rr
);
1970 /* Avoid splitting if possible. We must always split when SRC2 has
1971 EH predecessor edges, or we may end up with basic blocks with both
1972 normal and EH predecessor edges. */
1973 if (newpos2
== BB_HEAD (src2
)
1974 && !(EDGE_PRED (src2
, 0)->flags
& EDGE_EH
))
1978 if (newpos2
== BB_HEAD (src2
))
1980 /* Skip possible basic block header. */
1981 if (LABEL_P (newpos2
))
1982 newpos2
= NEXT_INSN (newpos2
);
1983 while (DEBUG_INSN_P (newpos2
))
1984 newpos2
= NEXT_INSN (newpos2
);
1985 if (NOTE_P (newpos2
))
1986 newpos2
= NEXT_INSN (newpos2
);
1987 while (DEBUG_INSN_P (newpos2
))
1988 newpos2
= NEXT_INSN (newpos2
);
1992 fprintf (dump_file
, "Splitting bb %i before %i insns\n",
1993 src2
->index
, nmatch
);
1994 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
1999 "Cross jumping from bb %i to bb %i; %i common insns\n",
2000 src1
->index
, src2
->index
, nmatch
);
2002 /* We may have some registers visible through the block. */
2003 df_set_bb_dirty (redirect_to
);
2006 redirect_edges_to
= redirect_to
;
2008 redirect_edges_to
= osrc2
;
2010 /* Recompute the frequencies and counts of outgoing edges. */
2011 FOR_EACH_EDGE (s
, ei
, redirect_edges_to
->succs
)
2015 basic_block d
= s
->dest
;
2017 if (FORWARDER_BLOCK_P (d
))
2018 d
= single_succ (d
);
2020 FOR_EACH_EDGE (s2
, ei
, src1
->succs
)
2022 basic_block d2
= s2
->dest
;
2023 if (FORWARDER_BLOCK_P (d2
))
2024 d2
= single_succ (d2
);
2029 s
->count
+= s2
->count
;
2031 /* Take care to update possible forwarder blocks. We verified
2032 that there is no more than one in the chain, so we can't run
2033 into infinite loop. */
2034 if (FORWARDER_BLOCK_P (s
->dest
))
2036 single_succ_edge (s
->dest
)->count
+= s2
->count
;
2037 s
->dest
->count
+= s2
->count
;
2038 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
2041 if (FORWARDER_BLOCK_P (s2
->dest
))
2043 single_succ_edge (s2
->dest
)->count
-= s2
->count
;
2044 if (single_succ_edge (s2
->dest
)->count
< 0)
2045 single_succ_edge (s2
->dest
)->count
= 0;
2046 s2
->dest
->count
-= s2
->count
;
2047 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
2048 if (s2
->dest
->frequency
< 0)
2049 s2
->dest
->frequency
= 0;
2050 if (s2
->dest
->count
< 0)
2051 s2
->dest
->count
= 0;
2054 if (!redirect_edges_to
->frequency
&& !src1
->frequency
)
2055 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
2058 = ((s
->probability
* redirect_edges_to
->frequency
+
2059 s2
->probability
* src1
->frequency
)
2060 / (redirect_edges_to
->frequency
+ src1
->frequency
));
2063 /* Adjust count and frequency for the block. An earlier jump
2064 threading pass may have left the profile in an inconsistent
2065 state (see update_bb_profile_for_threading) so we must be
2066 prepared for overflows. */
2070 tmp
->count
+= src1
->count
;
2071 tmp
->frequency
+= src1
->frequency
;
2072 if (tmp
->frequency
> BB_FREQ_MAX
)
2073 tmp
->frequency
= BB_FREQ_MAX
;
2074 if (tmp
== redirect_edges_to
)
2076 tmp
= find_fallthru_edge (tmp
->succs
)->dest
;
2079 update_br_prob_note (redirect_edges_to
);
2081 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
2083 /* Skip possible basic block header. */
2084 if (LABEL_P (newpos1
))
2085 newpos1
= NEXT_INSN (newpos1
);
2087 while (DEBUG_INSN_P (newpos1
))
2088 newpos1
= NEXT_INSN (newpos1
);
2090 if (NOTE_INSN_BASIC_BLOCK_P (newpos1
))
2091 newpos1
= NEXT_INSN (newpos1
);
2093 while (DEBUG_INSN_P (newpos1
))
2094 newpos1
= NEXT_INSN (newpos1
);
2096 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
2097 to_remove
= single_succ (redirect_from
);
2099 redirect_edge_and_branch_force (single_succ_edge (redirect_from
), redirect_to
);
2100 delete_basic_block (to_remove
);
2102 update_forwarder_flag (redirect_from
);
2103 if (redirect_to
!= src2
)
2104 update_forwarder_flag (src2
);
2109 /* Search the predecessors of BB for common insn sequences. When found,
2110 share code between them by redirecting control flow. Return true if
2111 any changes made. */
2114 try_crossjump_bb (int mode
, basic_block bb
)
2116 edge e
, e2
, fallthru
;
2118 unsigned max
, ix
, ix2
;
2120 /* Nothing to do if there is not at least two incoming edges. */
2121 if (EDGE_COUNT (bb
->preds
) < 2)
2124 /* Don't crossjump if this block ends in a computed jump,
2125 unless we are optimizing for size. */
2126 if (optimize_bb_for_size_p (bb
)
2127 && bb
!= EXIT_BLOCK_PTR
2128 && computed_jump_p (BB_END (bb
)))
2131 /* If we are partitioning hot/cold basic blocks, we don't want to
2132 mess up unconditional or indirect jumps that cross between hot
2135 Basic block partitioning may result in some jumps that appear to
2136 be optimizable (or blocks that appear to be mergeable), but which really
2137 must be left untouched (they are required to make it safely across
2138 partition boundaries). See the comments at the top of
2139 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
2141 if (BB_PARTITION (EDGE_PRED (bb
, 0)->src
) !=
2142 BB_PARTITION (EDGE_PRED (bb
, 1)->src
)
2143 || (EDGE_PRED (bb
, 0)->flags
& EDGE_CROSSING
))
2146 /* It is always cheapest to redirect a block that ends in a branch to
2147 a block that falls through into BB, as that adds no branches to the
2148 program. We'll try that combination first. */
2150 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
2152 if (EDGE_COUNT (bb
->preds
) > max
)
2155 fallthru
= find_fallthru_edge (bb
->preds
);
2158 for (ix
= 0; ix
< EDGE_COUNT (bb
->preds
);)
2160 e
= EDGE_PRED (bb
, ix
);
2163 /* As noted above, first try with the fallthru predecessor (or, a
2164 fallthru predecessor if we are in cfglayout mode). */
2167 /* Don't combine the fallthru edge into anything else.
2168 If there is a match, we'll do it the other way around. */
2171 /* If nothing changed since the last attempt, there is nothing
2174 && !((e
->src
->flags
& BB_MODIFIED
)
2175 || (fallthru
->src
->flags
& BB_MODIFIED
)))
2178 if (try_crossjump_to_edge (mode
, e
, fallthru
, dir_forward
))
2186 /* Non-obvious work limiting check: Recognize that we're going
2187 to call try_crossjump_bb on every basic block. So if we have
2188 two blocks with lots of outgoing edges (a switch) and they
2189 share lots of common destinations, then we would do the
2190 cross-jump check once for each common destination.
2192 Now, if the blocks actually are cross-jump candidates, then
2193 all of their destinations will be shared. Which means that
2194 we only need check them for cross-jump candidacy once. We
2195 can eliminate redundant checks of crossjump(A,B) by arbitrarily
2196 choosing to do the check from the block for which the edge
2197 in question is the first successor of A. */
2198 if (EDGE_SUCC (e
->src
, 0) != e
)
2201 for (ix2
= 0; ix2
< EDGE_COUNT (bb
->preds
); ix2
++)
2203 e2
= EDGE_PRED (bb
, ix2
);
2208 /* We've already checked the fallthru edge above. */
2212 /* The "first successor" check above only prevents multiple
2213 checks of crossjump(A,B). In order to prevent redundant
2214 checks of crossjump(B,A), require that A be the block
2215 with the lowest index. */
2216 if (e
->src
->index
> e2
->src
->index
)
2219 /* If nothing changed since the last attempt, there is nothing
2222 && !((e
->src
->flags
& BB_MODIFIED
)
2223 || (e2
->src
->flags
& BB_MODIFIED
)))
2226 /* Both e and e2 are not fallthru edges, so we can crossjump in either
2228 if (try_crossjump_to_edge (mode
, e
, e2
, dir_both
))
2238 crossjumps_occured
= true;
2243 /* Search the successors of BB for common insn sequences. When found,
2244 share code between them by moving it across the basic block
2245 boundary. Return true if any changes made. */
2248 try_head_merge_bb (basic_block bb
)
2250 basic_block final_dest_bb
= NULL
;
2251 int max_match
= INT_MAX
;
2253 rtx
*headptr
, *currptr
, *nextptr
;
2254 bool changed
, moveall
;
2256 rtx e0_last_head
, cond
, move_before
;
2257 unsigned nedges
= EDGE_COUNT (bb
->succs
);
2258 rtx jump
= BB_END (bb
);
2259 regset live
, live_union
;
2261 /* Nothing to do if there is not at least two outgoing edges. */
2265 /* Don't crossjump if this block ends in a computed jump,
2266 unless we are optimizing for size. */
2267 if (optimize_bb_for_size_p (bb
)
2268 && bb
!= EXIT_BLOCK_PTR
2269 && computed_jump_p (BB_END (bb
)))
2272 cond
= get_condition (jump
, &move_before
, true, false);
2273 if (cond
== NULL_RTX
)
2276 if (reg_mentioned_p (cc0_rtx
, jump
))
2277 move_before
= prev_nonnote_nondebug_insn (jump
);
2283 for (ix
= 0; ix
< nedges
; ix
++)
2284 if (EDGE_SUCC (bb
, ix
)->dest
== EXIT_BLOCK_PTR
)
2287 for (ix
= 0; ix
< nedges
; ix
++)
2289 edge e
= EDGE_SUCC (bb
, ix
);
2290 basic_block other_bb
= e
->dest
;
2292 if (df_get_bb_dirty (other_bb
))
2294 block_was_dirty
= true;
2298 if (e
->flags
& EDGE_ABNORMAL
)
2301 /* Normally, all destination blocks must only be reachable from this
2302 block, i.e. they must have one incoming edge.
2304 There is one special case we can handle, that of multiple consecutive
2305 jumps where the first jumps to one of the targets of the second jump.
2306 This happens frequently in switch statements for default labels.
2307 The structure is as follows:
2313 jump with targets A, B, C, D...
2315 has two incoming edges, from FINAL_DEST_BB and BB
2317 In this case, we can try to move the insns through BB and into
2319 if (EDGE_COUNT (other_bb
->preds
) != 1)
2321 edge incoming_edge
, incoming_bb_other_edge
;
2324 if (final_dest_bb
!= NULL
2325 || EDGE_COUNT (other_bb
->preds
) != 2)
2328 /* We must be able to move the insns across the whole block. */
2329 move_before
= BB_HEAD (bb
);
2330 while (!NONDEBUG_INSN_P (move_before
))
2331 move_before
= NEXT_INSN (move_before
);
2333 if (EDGE_COUNT (bb
->preds
) != 1)
2335 incoming_edge
= EDGE_PRED (bb
, 0);
2336 final_dest_bb
= incoming_edge
->src
;
2337 if (EDGE_COUNT (final_dest_bb
->succs
) != 2)
2339 FOR_EACH_EDGE (incoming_bb_other_edge
, ei
, final_dest_bb
->succs
)
2340 if (incoming_bb_other_edge
!= incoming_edge
)
2342 if (incoming_bb_other_edge
->dest
!= other_bb
)
2347 e0
= EDGE_SUCC (bb
, 0);
2348 e0_last_head
= NULL_RTX
;
2351 for (ix
= 1; ix
< nedges
; ix
++)
2353 edge e
= EDGE_SUCC (bb
, ix
);
2354 rtx e0_last
, e_last
;
2357 nmatch
= flow_find_head_matching_sequence (e0
->dest
, e
->dest
,
2358 &e0_last
, &e_last
, 0);
2362 if (nmatch
< max_match
)
2365 e0_last_head
= e0_last
;
2369 /* If we matched an entire block, we probably have to avoid moving the
2372 && e0_last_head
== BB_END (e0
->dest
)
2373 && (find_reg_note (e0_last_head
, REG_EH_REGION
, 0)
2374 || control_flow_insn_p (e0_last_head
)))
2380 e0_last_head
= prev_real_insn (e0_last_head
);
2381 while (DEBUG_INSN_P (e0_last_head
));
2387 /* We must find a union of the live registers at each of the end points. */
2388 live
= BITMAP_ALLOC (NULL
);
2389 live_union
= BITMAP_ALLOC (NULL
);
2391 currptr
= XNEWVEC (rtx
, nedges
);
2392 headptr
= XNEWVEC (rtx
, nedges
);
2393 nextptr
= XNEWVEC (rtx
, nedges
);
2395 for (ix
= 0; ix
< nedges
; ix
++)
2398 basic_block merge_bb
= EDGE_SUCC (bb
, ix
)->dest
;
2399 rtx head
= BB_HEAD (merge_bb
);
2401 while (!NONDEBUG_INSN_P (head
))
2402 head
= NEXT_INSN (head
);
2406 /* Compute the end point and live information */
2407 for (j
= 1; j
< max_match
; j
++)
2409 head
= NEXT_INSN (head
);
2410 while (!NONDEBUG_INSN_P (head
));
2411 simulate_backwards_to_point (merge_bb
, live
, head
);
2412 IOR_REG_SET (live_union
, live
);
2415 /* If we're moving across two blocks, verify the validity of the
2416 first move, then adjust the target and let the loop below deal
2417 with the final move. */
2418 if (final_dest_bb
!= NULL
)
2422 moveall
= can_move_insns_across (currptr
[0], e0_last_head
, move_before
,
2423 jump
, e0
->dest
, live_union
,
2427 if (move_upto
== NULL_RTX
)
2430 while (e0_last_head
!= move_upto
)
2432 df_simulate_one_insn_backwards (e0
->dest
, e0_last_head
,
2434 e0_last_head
= PREV_INSN (e0_last_head
);
2437 if (e0_last_head
== NULL_RTX
)
2440 jump
= BB_END (final_dest_bb
);
2441 cond
= get_condition (jump
, &move_before
, true, false);
2442 if (cond
== NULL_RTX
)
2445 if (reg_mentioned_p (cc0_rtx
, jump
))
2446 move_before
= prev_nonnote_nondebug_insn (jump
);
2456 moveall
= can_move_insns_across (currptr
[0], e0_last_head
,
2457 move_before
, jump
, e0
->dest
, live_union
,
2459 if (!moveall
&& move_upto
== NULL_RTX
)
2461 if (jump
== move_before
)
2464 /* Try again, using a different insertion point. */
2468 /* Don't try moving before a cc0 user, as that may invalidate
2470 if (reg_mentioned_p (cc0_rtx
, jump
))
2477 if (final_dest_bb
&& !moveall
)
2478 /* We haven't checked whether a partial move would be OK for the first
2479 move, so we have to fail this case. */
2485 if (currptr
[0] == move_upto
)
2487 for (ix
= 0; ix
< nedges
; ix
++)
2489 rtx curr
= currptr
[ix
];
2491 curr
= NEXT_INSN (curr
);
2492 while (!NONDEBUG_INSN_P (curr
));
2497 /* If we can't currently move all of the identical insns, remember
2498 each insn after the range that we'll merge. */
2500 for (ix
= 0; ix
< nedges
; ix
++)
2502 rtx curr
= currptr
[ix
];
2504 curr
= NEXT_INSN (curr
);
2505 while (!NONDEBUG_INSN_P (curr
));
2509 reorder_insns (headptr
[0], currptr
[0], PREV_INSN (move_before
));
2510 df_set_bb_dirty (EDGE_SUCC (bb
, 0)->dest
);
2511 if (final_dest_bb
!= NULL
)
2512 df_set_bb_dirty (final_dest_bb
);
2513 df_set_bb_dirty (bb
);
2514 for (ix
= 1; ix
< nedges
; ix
++)
2516 df_set_bb_dirty (EDGE_SUCC (bb
, ix
)->dest
);
2517 delete_insn_chain (headptr
[ix
], currptr
[ix
], false);
2521 if (jump
== move_before
)
2524 /* For the unmerged insns, try a different insertion point. */
2528 /* Don't try moving before a cc0 user, as that may invalidate
2530 if (reg_mentioned_p (cc0_rtx
, jump
))
2534 for (ix
= 0; ix
< nedges
; ix
++)
2535 currptr
[ix
] = headptr
[ix
] = nextptr
[ix
];
2545 crossjumps_occured
|= changed
;
2550 /* Return true if BB contains just bb note, or bb note followed
2551 by only DEBUG_INSNs. */
2554 trivially_empty_bb_p (basic_block bb
)
2556 rtx insn
= BB_END (bb
);
2560 if (insn
== BB_HEAD (bb
))
2562 if (!DEBUG_INSN_P (insn
))
2564 insn
= PREV_INSN (insn
);
2568 /* Do simple CFG optimizations - basic block merging, simplifying of jump
2569 instructions etc. Return nonzero if changes were made. */
2572 try_optimize_cfg (int mode
)
2574 bool changed_overall
= false;
2577 basic_block bb
, b
, next
;
2579 if (mode
& (CLEANUP_CROSSJUMP
| CLEANUP_THREADING
))
2582 crossjumps_occured
= false;
2585 update_forwarder_flag (bb
);
2587 if (! targetm
.cannot_modify_jumps_p ())
2590 /* Attempt to merge blocks as made possible by edge removal. If
2591 a block has only one successor, and the successor has only
2592 one predecessor, they may be combined. */
2595 block_was_dirty
= false;
2601 "\n\ntry_optimize_cfg iteration %i\n\n",
2604 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
;)
2608 bool changed_here
= false;
2610 /* Delete trivially dead basic blocks. This is either
2611 blocks with no predecessors, or empty blocks with no
2612 successors. However if the empty block with no
2613 successors is the successor of the ENTRY_BLOCK, it is
2614 kept. This ensures that the ENTRY_BLOCK will have a
2615 successor which is a precondition for many RTL
2616 passes. Empty blocks may result from expanding
2617 __builtin_unreachable (). */
2618 if (EDGE_COUNT (b
->preds
) == 0
2619 || (EDGE_COUNT (b
->succs
) == 0
2620 && trivially_empty_bb_p (b
)
2621 && single_succ_edge (ENTRY_BLOCK_PTR
)->dest
!= b
))
2624 if (EDGE_COUNT (b
->preds
) > 0)
2629 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2632 && BARRIER_P (BB_FOOTER (b
)))
2633 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2634 if ((e
->flags
& EDGE_FALLTHRU
)
2635 && BB_FOOTER (e
->src
) == NULL
)
2639 BB_FOOTER (e
->src
) = BB_FOOTER (b
);
2640 BB_FOOTER (b
) = NULL
;
2645 BB_FOOTER (e
->src
) = emit_barrier ();
2652 rtx last
= get_last_bb_insn (b
);
2653 if (last
&& BARRIER_P (last
))
2654 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2655 if ((e
->flags
& EDGE_FALLTHRU
))
2656 emit_barrier_after (BB_END (e
->src
));
2659 delete_basic_block (b
);
2661 /* Avoid trying to remove ENTRY_BLOCK_PTR. */
2662 b
= (c
== ENTRY_BLOCK_PTR
? c
->next_bb
: c
);
2666 /* Remove code labels no longer used. */
2667 if (single_pred_p (b
)
2668 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2669 && !(single_pred_edge (b
)->flags
& EDGE_COMPLEX
)
2670 && LABEL_P (BB_HEAD (b
))
2671 /* If the previous block ends with a branch to this
2672 block, we can't delete the label. Normally this
2673 is a condjump that is yet to be simplified, but
2674 if CASE_DROPS_THRU, this can be a tablejump with
2675 some element going to the same place as the
2676 default (fallthru). */
2677 && (single_pred (b
) == ENTRY_BLOCK_PTR
2678 || !JUMP_P (BB_END (single_pred (b
)))
2679 || ! label_is_jump_target_p (BB_HEAD (b
),
2680 BB_END (single_pred (b
)))))
2682 delete_insn (BB_HEAD (b
));
2684 fprintf (dump_file
, "Deleted label in block %i.\n",
2688 /* If we fall through an empty block, we can remove it. */
2689 if (!(mode
& (CLEANUP_CFGLAYOUT
| CLEANUP_NO_INSN_DEL
))
2690 && single_pred_p (b
)
2691 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2692 && !LABEL_P (BB_HEAD (b
))
2693 && FORWARDER_BLOCK_P (b
)
2694 /* Note that forwarder_block_p true ensures that
2695 there is a successor for this block. */
2696 && (single_succ_edge (b
)->flags
& EDGE_FALLTHRU
)
2697 && n_basic_blocks
> NUM_FIXED_BLOCKS
+ 1)
2701 "Deleting fallthru block %i.\n",
2704 c
= b
->prev_bb
== ENTRY_BLOCK_PTR
? b
->next_bb
: b
->prev_bb
;
2705 redirect_edge_succ_nodup (single_pred_edge (b
),
2707 delete_basic_block (b
);
2713 /* Merge B with its single successor, if any. */
2714 if (single_succ_p (b
)
2715 && (s
= single_succ_edge (b
))
2716 && !(s
->flags
& EDGE_COMPLEX
)
2717 && (c
= s
->dest
) != EXIT_BLOCK_PTR
2718 && single_pred_p (c
)
2721 /* When not in cfg_layout mode use code aware of reordering
2722 INSN. This code possibly creates new basic blocks so it
2723 does not fit merge_blocks interface and is kept here in
2724 hope that it will become useless once more of compiler
2725 is transformed to use cfg_layout mode. */
2727 if ((mode
& CLEANUP_CFGLAYOUT
)
2728 && can_merge_blocks_p (b
, c
))
2730 merge_blocks (b
, c
);
2731 update_forwarder_flag (b
);
2732 changed_here
= true;
2734 else if (!(mode
& CLEANUP_CFGLAYOUT
)
2735 /* If the jump insn has side effects,
2736 we can't kill the edge. */
2737 && (!JUMP_P (BB_END (b
))
2738 || (reload_completed
2739 ? simplejump_p (BB_END (b
))
2740 : (onlyjump_p (BB_END (b
))
2741 && !tablejump_p (BB_END (b
),
2743 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
2746 changed_here
= true;
2750 /* Simplify branch over branch. */
2751 if ((mode
& CLEANUP_EXPENSIVE
)
2752 && !(mode
& CLEANUP_CFGLAYOUT
)
2753 && try_simplify_condjump (b
))
2754 changed_here
= true;
2756 /* If B has a single outgoing edge, but uses a
2757 non-trivial jump instruction without side-effects, we
2758 can either delete the jump entirely, or replace it
2759 with a simple unconditional jump. */
2760 if (single_succ_p (b
)
2761 && single_succ (b
) != EXIT_BLOCK_PTR
2762 && onlyjump_p (BB_END (b
))
2763 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
)
2764 && try_redirect_by_replacing_jump (single_succ_edge (b
),
2766 (mode
& CLEANUP_CFGLAYOUT
) != 0))
2768 update_forwarder_flag (b
);
2769 changed_here
= true;
2772 /* Simplify branch to branch. */
2773 if (try_forward_edges (mode
, b
))
2775 update_forwarder_flag (b
);
2776 changed_here
= true;
2779 /* Look for shared code between blocks. */
2780 if ((mode
& CLEANUP_CROSSJUMP
)
2781 && try_crossjump_bb (mode
, b
))
2782 changed_here
= true;
2784 if ((mode
& CLEANUP_CROSSJUMP
)
2785 /* This can lengthen register lifetimes. Do it only after
2788 && try_head_merge_bb (b
))
2789 changed_here
= true;
2791 /* Don't get confused by the index shift caused by
2799 if ((mode
& CLEANUP_CROSSJUMP
)
2800 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
2803 if (block_was_dirty
)
2805 /* This should only be set by head-merging. */
2806 gcc_assert (mode
& CLEANUP_CROSSJUMP
);
2812 /* Edge forwarding in particular can cause hot blocks previously
2813 reached by both hot and cold blocks to become dominated only
2814 by cold blocks. This will cause the verification below to fail,
2815 and lead to now cold code in the hot section. This is not easy
2816 to detect and fix during edge forwarding, and in some cases
2817 is only visible after newly unreachable blocks are deleted,
2818 which will be done in fixup_partitions. */
2819 fixup_partitions ();
2821 #ifdef ENABLE_CHECKING
2822 verify_flow_info ();
2826 changed_overall
|= changed
;
2833 b
->flags
&= ~(BB_FORWARDER_BLOCK
| BB_NONTHREADABLE_BLOCK
);
2835 return changed_overall
;
2838 /* Delete all unreachable basic blocks. */
2841 delete_unreachable_blocks (void)
2843 bool changed
= false;
2844 basic_block b
, prev_bb
;
2846 find_unreachable_blocks ();
2848 /* When we're in GIMPLE mode and there may be debug insns, we should
2849 delete blocks in reverse dominator order, so as to get a chance
2850 to substitute all released DEFs into debug stmts. If we don't
2851 have dominators information, walking blocks backward gets us a
2852 better chance of retaining most debug information than
2854 if (MAY_HAVE_DEBUG_INSNS
&& current_ir_type () == IR_GIMPLE
2855 && dom_info_available_p (CDI_DOMINATORS
))
2857 for (b
= EXIT_BLOCK_PTR
->prev_bb
; b
!= ENTRY_BLOCK_PTR
; b
= prev_bb
)
2859 prev_bb
= b
->prev_bb
;
2861 if (!(b
->flags
& BB_REACHABLE
))
2863 /* Speed up the removal of blocks that don't dominate
2864 others. Walking backwards, this should be the common
2866 if (!first_dom_son (CDI_DOMINATORS
, b
))
2867 delete_basic_block (b
);
2871 = get_all_dominated_blocks (CDI_DOMINATORS
, b
);
2877 prev_bb
= b
->prev_bb
;
2879 gcc_assert (!(b
->flags
& BB_REACHABLE
));
2881 delete_basic_block (b
);
2893 for (b
= EXIT_BLOCK_PTR
->prev_bb
; b
!= ENTRY_BLOCK_PTR
; b
= prev_bb
)
2895 prev_bb
= b
->prev_bb
;
2897 if (!(b
->flags
& BB_REACHABLE
))
2899 delete_basic_block (b
);
2906 tidy_fallthru_edges ();
2910 /* Delete any jump tables never referenced. We can't delete them at the
2911 time of removing tablejump insn as they are referenced by the preceding
2912 insns computing the destination, so we delay deleting and garbagecollect
2913 them once life information is computed. */
2915 delete_dead_jumptables (void)
2919 /* A dead jump table does not belong to any basic block. Scan insns
2920 between two adjacent basic blocks. */
2925 for (insn
= NEXT_INSN (BB_END (bb
));
2926 insn
&& !NOTE_INSN_BASIC_BLOCK_P (insn
);
2929 next
= NEXT_INSN (insn
);
2931 && LABEL_NUSES (insn
) == LABEL_PRESERVE_P (insn
)
2932 && JUMP_TABLE_DATA_P (next
))
2934 rtx label
= insn
, jump
= next
;
2937 fprintf (dump_file
, "Dead jumptable %i removed\n",
2940 next
= NEXT_INSN (next
);
2942 delete_insn (label
);
2949 /* Tidy the CFG by deleting unreachable code and whatnot. */
2952 cleanup_cfg (int mode
)
2954 bool changed
= false;
2956 /* Set the cfglayout mode flag here. We could update all the callers
2957 but that is just inconvenient, especially given that we eventually
2958 want to have cfglayout mode as the default. */
2959 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2960 mode
|= CLEANUP_CFGLAYOUT
;
2962 timevar_push (TV_CLEANUP_CFG
);
2963 if (delete_unreachable_blocks ())
2966 /* We've possibly created trivially dead code. Cleanup it right
2967 now to introduce more opportunities for try_optimize_cfg. */
2968 if (!(mode
& (CLEANUP_NO_INSN_DEL
))
2969 && !reload_completed
)
2970 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2975 /* To tail-merge blocks ending in the same noreturn function (e.g.
2976 a call to abort) we have to insert fake edges to exit. Do this
2977 here once. The fake edges do not interfere with any other CFG
2979 if (mode
& CLEANUP_CROSSJUMP
)
2980 add_noreturn_fake_exit_edges ();
2982 if (!dbg_cnt (cfg_cleanup
))
2985 while (try_optimize_cfg (mode
))
2987 delete_unreachable_blocks (), changed
= true;
2988 if (!(mode
& CLEANUP_NO_INSN_DEL
))
2990 /* Try to remove some trivially dead insns when doing an expensive
2991 cleanup. But delete_trivially_dead_insns doesn't work after
2992 reload (it only handles pseudos) and run_fast_dce is too costly
2993 to run in every iteration.
2995 For effective cross jumping, we really want to run a fast DCE to
2996 clean up any dead conditions, or they get in the way of performing
2999 Other transformations in cleanup_cfg are not so sensitive to dead
3000 code, so delete_trivially_dead_insns or even doing nothing at all
3002 if ((mode
& CLEANUP_EXPENSIVE
) && !reload_completed
3003 && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
3005 if ((mode
& CLEANUP_CROSSJUMP
) && crossjumps_occured
)
3012 if (mode
& CLEANUP_CROSSJUMP
)
3013 remove_fake_exit_edges ();
3015 /* Don't call delete_dead_jumptables in cfglayout mode, because
3016 that function assumes that jump tables are in the insns stream.
3017 But we also don't _have_ to delete dead jumptables in cfglayout
3018 mode because we shouldn't even be looking at things that are
3019 not in a basic block. Dead jumptables are cleaned up when
3020 going out of cfglayout mode. */
3021 if (!(mode
& CLEANUP_CFGLAYOUT
))
3022 delete_dead_jumptables ();
3024 /* ??? We probably do this way too often. */
3027 || (mode
& CLEANUP_CFG_CHANGED
)))
3029 timevar_push (TV_REPAIR_LOOPS
);
3030 /* The above doesn't preserve dominance info if available. */
3031 gcc_assert (!dom_info_available_p (CDI_DOMINATORS
));
3032 calculate_dominance_info (CDI_DOMINATORS
);
3033 fix_loop_structure (NULL
);
3034 free_dominance_info (CDI_DOMINATORS
);
3035 timevar_pop (TV_REPAIR_LOOPS
);
3038 timevar_pop (TV_CLEANUP_CFG
);
3046 delete_trivially_dead_insns (get_insns (), max_reg_num ());
3048 dump_flow_info (dump_file
, dump_flags
);
3049 cleanup_cfg ((optimize
? CLEANUP_EXPENSIVE
: 0)
3050 | (flag_thread_jumps
? CLEANUP_THREADING
: 0));
3056 const pass_data pass_data_jump
=
3058 RTL_PASS
, /* type */
3060 OPTGROUP_NONE
, /* optinfo_flags */
3061 false, /* has_gate */
3062 true, /* has_execute */
3063 TV_JUMP
, /* tv_id */
3064 0, /* properties_required */
3065 0, /* properties_provided */
3066 0, /* properties_destroyed */
3067 0, /* todo_flags_start */
3068 TODO_verify_rtl_sharing
, /* todo_flags_finish */
3071 class pass_jump
: public rtl_opt_pass
3074 pass_jump(gcc::context
*ctxt
)
3075 : rtl_opt_pass(pass_data_jump
, ctxt
)
3078 /* opt_pass methods: */
3079 unsigned int execute () { return execute_jump (); }
3081 }; // class pass_jump
3086 make_pass_jump (gcc::context
*ctxt
)
3088 return new pass_jump (ctxt
);
3092 execute_jump2 (void)
3094 cleanup_cfg (flag_crossjumping
? CLEANUP_CROSSJUMP
: 0);
3100 const pass_data pass_data_jump2
=
3102 RTL_PASS
, /* type */
3104 OPTGROUP_NONE
, /* optinfo_flags */
3105 false, /* has_gate */
3106 true, /* has_execute */
3107 TV_JUMP
, /* tv_id */
3108 0, /* properties_required */
3109 0, /* properties_provided */
3110 0, /* properties_destroyed */
3111 0, /* todo_flags_start */
3112 TODO_verify_rtl_sharing
, /* todo_flags_finish */
3115 class pass_jump2
: public rtl_opt_pass
3118 pass_jump2(gcc::context
*ctxt
)
3119 : rtl_opt_pass(pass_data_jump2
, ctxt
)
3122 /* opt_pass methods: */
3123 unsigned int execute () { return execute_jump2 (); }
3125 }; // class pass_jump2
3130 make_pass_jump2 (gcc::context
*ctxt
)
3132 return new pass_jump2 (ctxt
);