1 /* Control flow optimization code for GNU compiler.
2 Copyright (C) 1987-2017 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"
43 #include "insn-config.h"
47 #include "tree-pass.h"
52 #include "cfgcleanup.h"
57 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
59 /* Set to true when we are running first pass of try_optimize_cfg loop. */
60 static bool first_pass
;
62 /* Set to true if crossjumps occurred in the latest run of try_optimize_cfg. */
63 static bool crossjumps_occurred
;
65 /* Set to true if we couldn't run an optimization due to stale liveness
66 information; we should run df_analyze to enable more opportunities. */
67 static bool block_was_dirty
;
69 static bool try_crossjump_to_edge (int, edge
, edge
, enum replace_direction
);
70 static bool try_crossjump_bb (int, basic_block
);
71 static bool outgoing_edges_match (int, basic_block
, basic_block
);
72 static enum replace_direction
old_insns_match_p (int, rtx_insn
*, rtx_insn
*);
74 static void merge_blocks_move_predecessor_nojumps (basic_block
, basic_block
);
75 static void merge_blocks_move_successor_nojumps (basic_block
, basic_block
);
76 static bool try_optimize_cfg (int);
77 static bool try_simplify_condjump (basic_block
);
78 static bool try_forward_edges (int, basic_block
);
79 static edge
thread_jump (edge
, basic_block
);
80 static bool mark_effect (rtx
, bitmap
);
81 static void notice_new_block (basic_block
);
82 static void update_forwarder_flag (basic_block
);
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
;
116 rtx_insn
*cbranch_insn
;
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_FOR_FN (cfun
)
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_FOR_FN (cfun
)
160 || jump_dest_block
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
161 || !can_fallthru (jump_block
, cbranch_dest_block
))
164 /* Invert the conditional branch. */
165 if (!invert_jump (as_a
<rtx_jump_insn
*> (cbranch_insn
),
166 block_label (jump_dest_block
), 0))
170 fprintf (dump_file
, "Simplifying condjump %i around jump %i\n",
171 INSN_UID (cbranch_insn
), INSN_UID (BB_END (jump_block
)));
173 /* Success. Update the CFG to match. Note that after this point
174 the edge variable names appear backwards; the redirection is done
175 this way to preserve edge profile data. */
176 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
178 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
180 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
181 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
182 update_br_prob_note (cbranch_block
);
184 /* Delete the block with the unconditional jump, and clean up the mess. */
185 delete_basic_block (jump_block
);
186 tidy_fallthru_edge (cbranch_jump_edge
);
187 update_forwarder_flag (cbranch_block
);
192 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
193 on register. Used by jump threading. */
196 mark_effect (rtx exp
, regset nonequal
)
199 switch (GET_CODE (exp
))
201 /* In case we do clobber the register, mark it as equal, as we know the
202 value is dead so it don't have to match. */
204 dest
= XEXP (exp
, 0);
206 bitmap_clear_range (nonequal
, REGNO (dest
), REG_NREGS (dest
));
210 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
212 dest
= SET_DEST (exp
);
217 bitmap_set_range (nonequal
, REGNO (dest
), REG_NREGS (dest
));
225 /* Return true if X contains a register in NONEQUAL. */
227 mentions_nonequal_regs (const_rtx x
, regset nonequal
)
229 subrtx_iterator::array_type array
;
230 FOR_EACH_SUBRTX (iter
, array
, x
, NONCONST
)
235 unsigned int end_regno
= END_REGNO (x
);
236 for (unsigned int regno
= REGNO (x
); regno
< end_regno
; ++regno
)
237 if (REGNO_REG_SET_P (nonequal
, regno
))
244 /* Attempt to prove that the basic block B will have no side effects and
245 always continues in the same edge if reached via E. Return the edge
246 if exist, NULL otherwise. */
249 thread_jump (edge e
, basic_block b
)
251 rtx set1
, set2
, cond1
, cond2
;
253 enum rtx_code code1
, code2
, reversed_code2
;
254 bool reverse1
= false;
258 reg_set_iterator rsi
;
260 if (b
->flags
& BB_NONTHREADABLE_BLOCK
)
263 /* At the moment, we do handle only conditional jumps, but later we may
264 want to extend this code to tablejumps and others. */
265 if (EDGE_COUNT (e
->src
->succs
) != 2)
267 if (EDGE_COUNT (b
->succs
) != 2)
269 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
273 /* Second branch must end with onlyjump, as we will eliminate the jump. */
274 if (!any_condjump_p (BB_END (e
->src
)))
277 if (!any_condjump_p (BB_END (b
)) || !onlyjump_p (BB_END (b
)))
279 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
283 set1
= pc_set (BB_END (e
->src
));
284 set2
= pc_set (BB_END (b
));
285 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
286 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
289 cond1
= XEXP (SET_SRC (set1
), 0);
290 cond2
= XEXP (SET_SRC (set2
), 0);
292 code1
= reversed_comparison_code (cond1
, BB_END (e
->src
));
294 code1
= GET_CODE (cond1
);
296 code2
= GET_CODE (cond2
);
297 reversed_code2
= reversed_comparison_code (cond2
, BB_END (b
));
299 if (!comparison_dominates_p (code1
, code2
)
300 && !comparison_dominates_p (code1
, reversed_code2
))
303 /* Ensure that the comparison operators are equivalent.
304 ??? This is far too pessimistic. We should allow swapped operands,
305 different CCmodes, or for example comparisons for interval, that
306 dominate even when operands are not equivalent. */
307 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
308 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
311 /* Short circuit cases where block B contains some side effects, as we can't
313 for (insn
= NEXT_INSN (BB_HEAD (b
)); insn
!= NEXT_INSN (BB_END (b
));
314 insn
= NEXT_INSN (insn
))
315 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
317 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
323 /* First process all values computed in the source basic block. */
324 for (insn
= NEXT_INSN (BB_HEAD (e
->src
));
325 insn
!= NEXT_INSN (BB_END (e
->src
));
326 insn
= NEXT_INSN (insn
))
328 cselib_process_insn (insn
);
330 nonequal
= BITMAP_ALLOC (NULL
);
331 CLEAR_REG_SET (nonequal
);
333 /* Now assume that we've continued by the edge E to B and continue
334 processing as if it were same basic block.
335 Our goal is to prove that whole block is an NOOP. */
337 for (insn
= NEXT_INSN (BB_HEAD (b
));
338 insn
!= NEXT_INSN (BB_END (b
)) && !failed
;
339 insn
= NEXT_INSN (insn
))
343 rtx pat
= PATTERN (insn
);
345 if (GET_CODE (pat
) == PARALLEL
)
347 for (i
= 0; i
< (unsigned)XVECLEN (pat
, 0); i
++)
348 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
351 failed
|= mark_effect (pat
, nonequal
);
354 cselib_process_insn (insn
);
357 /* Later we should clear nonequal of dead registers. So far we don't
358 have life information in cfg_cleanup. */
361 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
365 /* cond2 must not mention any register that is not equal to the
367 if (mentions_nonequal_regs (cond2
, nonequal
))
370 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, rsi
)
373 BITMAP_FREE (nonequal
);
375 if ((comparison_dominates_p (code1
, code2
) != 0)
376 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
377 return BRANCH_EDGE (b
);
379 return FALLTHRU_EDGE (b
);
382 BITMAP_FREE (nonequal
);
387 /* Attempt to forward edges leaving basic block B.
388 Return true if successful. */
391 try_forward_edges (int mode
, basic_block b
)
393 bool changed
= false;
395 edge e
, *threaded_edges
= NULL
;
397 /* If we are partitioning hot/cold basic blocks, we don't want to
398 mess up unconditional or indirect jumps that cross between hot
401 Basic block partitioning may result in some jumps that appear to
402 be optimizable (or blocks that appear to be mergeable), but which really
403 must be left untouched (they are required to make it safely across
404 partition boundaries). See the comments at the top of
405 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
407 if (JUMP_P (BB_END (b
)) && CROSSING_JUMP_P (BB_END (b
)))
410 for (ei
= ei_start (b
->succs
); (e
= ei_safe_edge (ei
)); )
412 basic_block target
, first
;
413 location_t goto_locus
;
415 bool threaded
= false;
416 int nthreaded_edges
= 0;
417 bool may_thread
= first_pass
|| (b
->flags
& BB_MODIFIED
) != 0;
419 /* Skip complex edges because we don't know how to update them.
421 Still handle fallthru edges, as we can succeed to forward fallthru
422 edge to the same place as the branch edge of conditional branch
423 and turn conditional branch to an unconditional branch. */
424 if (e
->flags
& EDGE_COMPLEX
)
430 target
= first
= e
->dest
;
431 counter
= NUM_FIXED_BLOCKS
;
432 goto_locus
= e
->goto_locus
;
434 /* If we are partitioning hot/cold basic_blocks, we don't want to mess
435 up jumps that cross between hot/cold sections.
437 Basic block partitioning may result in some jumps that appear
438 to be optimizable (or blocks that appear to be mergeable), but which
439 really must be left untouched (they are required to make it safely
440 across partition boundaries). See the comments at the top of
441 bb-reorder.c:partition_hot_cold_basic_blocks for complete
444 if (first
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
445 && JUMP_P (BB_END (first
))
446 && CROSSING_JUMP_P (BB_END (first
)))
449 while (counter
< n_basic_blocks_for_fn (cfun
))
451 basic_block new_target
= NULL
;
452 bool new_target_threaded
= false;
453 may_thread
|= (target
->flags
& BB_MODIFIED
) != 0;
455 if (FORWARDER_BLOCK_P (target
)
456 && !(single_succ_edge (target
)->flags
& EDGE_CROSSING
)
457 && single_succ (target
) != EXIT_BLOCK_PTR_FOR_FN (cfun
))
459 /* Bypass trivial infinite loops. */
460 new_target
= single_succ (target
);
461 if (target
== new_target
)
462 counter
= n_basic_blocks_for_fn (cfun
);
465 /* When not optimizing, ensure that edges or forwarder
466 blocks with different locus are not optimized out. */
467 location_t new_locus
= single_succ_edge (target
)->goto_locus
;
468 location_t locus
= goto_locus
;
470 if (LOCATION_LOCUS (new_locus
) != UNKNOWN_LOCATION
471 && LOCATION_LOCUS (locus
) != UNKNOWN_LOCATION
472 && new_locus
!= locus
)
476 if (LOCATION_LOCUS (new_locus
) != UNKNOWN_LOCATION
)
479 rtx_insn
*last
= BB_END (target
);
480 if (DEBUG_INSN_P (last
))
481 last
= prev_nondebug_insn (last
);
482 if (last
&& INSN_P (last
))
483 new_locus
= INSN_LOCATION (last
);
485 new_locus
= UNKNOWN_LOCATION
;
487 if (LOCATION_LOCUS (new_locus
) != UNKNOWN_LOCATION
488 && LOCATION_LOCUS (locus
) != UNKNOWN_LOCATION
489 && new_locus
!= locus
)
493 if (LOCATION_LOCUS (new_locus
) != UNKNOWN_LOCATION
)
502 /* Allow to thread only over one edge at time to simplify updating
504 else if ((mode
& CLEANUP_THREADING
) && may_thread
)
506 edge t
= thread_jump (e
, target
);
510 threaded_edges
= XNEWVEC (edge
,
511 n_basic_blocks_for_fn (cfun
));
516 /* Detect an infinite loop across blocks not
517 including the start block. */
518 for (i
= 0; i
< nthreaded_edges
; ++i
)
519 if (threaded_edges
[i
] == t
)
521 if (i
< nthreaded_edges
)
523 counter
= n_basic_blocks_for_fn (cfun
);
528 /* Detect an infinite loop across the start block. */
532 gcc_assert (nthreaded_edges
533 < (n_basic_blocks_for_fn (cfun
)
534 - NUM_FIXED_BLOCKS
));
535 threaded_edges
[nthreaded_edges
++] = t
;
537 new_target
= t
->dest
;
538 new_target_threaded
= true;
547 threaded
|= new_target_threaded
;
550 if (counter
>= n_basic_blocks_for_fn (cfun
))
553 fprintf (dump_file
, "Infinite loop in BB %i.\n",
556 else if (target
== first
)
557 ; /* We didn't do anything. */
560 /* Save the values now, as the edge may get removed. */
561 profile_count edge_count
= e
->count
;
562 profile_probability edge_probability
= e
->probability
;
566 e
->goto_locus
= goto_locus
;
568 /* Don't force if target is exit block. */
569 if (threaded
&& target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
571 notice_new_block (redirect_edge_and_branch_force (e
, target
));
573 fprintf (dump_file
, "Conditionals threaded.\n");
575 else if (!redirect_edge_and_branch (e
, target
))
579 "Forwarding edge %i->%i to %i failed.\n",
580 b
->index
, e
->dest
->index
, target
->index
);
585 /* We successfully forwarded the edge. Now update profile
586 data: for each edge we traversed in the chain, remove
587 the original edge's execution count. */
588 edge_frequency
= edge_probability
.apply (b
->frequency
);
594 if (!single_succ_p (first
))
596 gcc_assert (n
< nthreaded_edges
);
597 t
= threaded_edges
[n
++];
598 gcc_assert (t
->src
== first
);
599 update_bb_profile_for_threading (first
, edge_frequency
,
601 update_br_prob_note (first
);
605 first
->count
-= edge_count
;
606 first
->frequency
-= edge_frequency
;
607 if (first
->frequency
< 0)
608 first
->frequency
= 0;
609 /* It is possible that as the result of
610 threading we've removed edge as it is
611 threaded to the fallthru edge. Avoid
612 getting out of sync. */
613 if (n
< nthreaded_edges
614 && first
== threaded_edges
[n
]->src
)
616 t
= single_succ_edge (first
);
619 t
->count
-= edge_count
;
622 while (first
!= target
);
630 free (threaded_edges
);
635 /* Blocks A and B are to be merged into a single block. A has no incoming
636 fallthru edge, so it can be moved before B without adding or modifying
637 any jumps (aside from the jump from A to B). */
640 merge_blocks_move_predecessor_nojumps (basic_block a
, basic_block b
)
644 /* If we are partitioning hot/cold basic blocks, we don't want to
645 mess up unconditional or indirect jumps that cross between hot
648 Basic block partitioning may result in some jumps that appear to
649 be optimizable (or blocks that appear to be mergeable), but which really
650 must be left untouched (they are required to make it safely across
651 partition boundaries). See the comments at the top of
652 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
654 if (BB_PARTITION (a
) != BB_PARTITION (b
))
657 barrier
= next_nonnote_insn (BB_END (a
));
658 gcc_assert (BARRIER_P (barrier
));
659 delete_insn (barrier
);
661 /* Scramble the insn chain. */
662 if (BB_END (a
) != PREV_INSN (BB_HEAD (b
)))
663 reorder_insns_nobb (BB_HEAD (a
), BB_END (a
), PREV_INSN (BB_HEAD (b
)));
667 fprintf (dump_file
, "Moved block %d before %d and merged.\n",
670 /* Swap the records for the two blocks around. */
673 link_block (a
, b
->prev_bb
);
675 /* Now blocks A and B are contiguous. Merge them. */
679 /* Blocks A and B are to be merged into a single block. B has no outgoing
680 fallthru edge, so it can be moved after A without adding or modifying
681 any jumps (aside from the jump from A to B). */
684 merge_blocks_move_successor_nojumps (basic_block a
, basic_block b
)
686 rtx_insn
*barrier
, *real_b_end
;
688 rtx_jump_table_data
*table
;
690 /* If we are partitioning hot/cold basic blocks, we don't want to
691 mess up unconditional or indirect jumps that cross between hot
694 Basic block partitioning may result in some jumps that appear to
695 be optimizable (or blocks that appear to be mergeable), but which really
696 must be left untouched (they are required to make it safely across
697 partition boundaries). See the comments at the top of
698 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
700 if (BB_PARTITION (a
) != BB_PARTITION (b
))
703 real_b_end
= BB_END (b
);
705 /* If there is a jump table following block B temporarily add the jump table
706 to block B so that it will also be moved to the correct location. */
707 if (tablejump_p (BB_END (b
), &label
, &table
)
708 && prev_active_insn (label
) == BB_END (b
))
713 /* There had better have been a barrier there. Delete it. */
714 barrier
= NEXT_INSN (BB_END (b
));
715 if (barrier
&& BARRIER_P (barrier
))
716 delete_insn (barrier
);
719 /* Scramble the insn chain. */
720 reorder_insns_nobb (BB_HEAD (b
), BB_END (b
), BB_END (a
));
722 /* Restore the real end of b. */
723 BB_END (b
) = real_b_end
;
726 fprintf (dump_file
, "Moved block %d after %d and merged.\n",
729 /* Now blocks A and B are contiguous. Merge them. */
733 /* Attempt to merge basic blocks that are potentially non-adjacent.
734 Return NULL iff the attempt failed, otherwise return basic block
735 where cleanup_cfg should continue. Because the merging commonly
736 moves basic block away or introduces another optimization
737 possibility, return basic block just before B so cleanup_cfg don't
740 It may be good idea to return basic block before C in the case
741 C has been moved after B and originally appeared earlier in the
742 insn sequence, but we have no information available about the
743 relative ordering of these two. Hopefully it is not too common. */
746 merge_blocks_move (edge e
, basic_block b
, basic_block c
, int mode
)
750 /* If we are partitioning hot/cold basic blocks, we don't want to
751 mess up unconditional or indirect jumps that cross between hot
754 Basic block partitioning may result in some jumps that appear to
755 be optimizable (or blocks that appear to be mergeable), but which really
756 must be left untouched (they are required to make it safely across
757 partition boundaries). See the comments at the top of
758 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
760 if (BB_PARTITION (b
) != BB_PARTITION (c
))
763 /* If B has a fallthru edge to C, no need to move anything. */
764 if (e
->flags
& EDGE_FALLTHRU
)
766 int b_index
= b
->index
, c_index
= c
->index
;
768 /* Protect the loop latches. */
769 if (current_loops
&& c
->loop_father
->latch
== c
)
773 update_forwarder_flag (b
);
776 fprintf (dump_file
, "Merged %d and %d without moving.\n",
779 return b
->prev_bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) ? b
: b
->prev_bb
;
782 /* Otherwise we will need to move code around. Do that only if expensive
783 transformations are allowed. */
784 else if (mode
& CLEANUP_EXPENSIVE
)
786 edge tmp_edge
, b_fallthru_edge
;
787 bool c_has_outgoing_fallthru
;
788 bool b_has_incoming_fallthru
;
790 /* Avoid overactive code motion, as the forwarder blocks should be
791 eliminated by edge redirection instead. One exception might have
792 been if B is a forwarder block and C has no fallthru edge, but
793 that should be cleaned up by bb-reorder instead. */
794 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
797 /* We must make sure to not munge nesting of lexical blocks,
798 and loop notes. This is done by squeezing out all the notes
799 and leaving them there to lie. Not ideal, but functional. */
801 tmp_edge
= find_fallthru_edge (c
->succs
);
802 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
804 tmp_edge
= find_fallthru_edge (b
->preds
);
805 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
806 b_fallthru_edge
= tmp_edge
;
809 next
= next
->prev_bb
;
811 /* Otherwise, we're going to try to move C after B. If C does
812 not have an outgoing fallthru, then it can be moved
813 immediately after B without introducing or modifying jumps. */
814 if (! c_has_outgoing_fallthru
)
816 merge_blocks_move_successor_nojumps (b
, c
);
817 return next
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) ? next
->next_bb
: next
;
820 /* If B does not have an incoming fallthru, then it can be moved
821 immediately before C without introducing or modifying jumps.
822 C cannot be the first block, so we do not have to worry about
823 accessing a non-existent block. */
825 if (b_has_incoming_fallthru
)
829 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
831 bb
= force_nonfallthru (b_fallthru_edge
);
833 notice_new_block (bb
);
836 merge_blocks_move_predecessor_nojumps (b
, c
);
837 return next
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) ? next
->next_bb
: next
;
844 /* Removes the memory attributes of MEM expression
845 if they are not equal. */
848 merge_memattrs (rtx x
, rtx y
)
857 if (x
== 0 || y
== 0)
862 if (code
!= GET_CODE (y
))
865 if (GET_MODE (x
) != GET_MODE (y
))
868 if (code
== MEM
&& !mem_attrs_eq_p (MEM_ATTRS (x
), MEM_ATTRS (y
)))
872 else if (! MEM_ATTRS (y
))
876 HOST_WIDE_INT mem_size
;
878 if (MEM_ALIAS_SET (x
) != MEM_ALIAS_SET (y
))
880 set_mem_alias_set (x
, 0);
881 set_mem_alias_set (y
, 0);
884 if (! mem_expr_equal_p (MEM_EXPR (x
), MEM_EXPR (y
)))
888 clear_mem_offset (x
);
889 clear_mem_offset (y
);
891 else if (MEM_OFFSET_KNOWN_P (x
) != MEM_OFFSET_KNOWN_P (y
)
892 || (MEM_OFFSET_KNOWN_P (x
)
893 && MEM_OFFSET (x
) != MEM_OFFSET (y
)))
895 clear_mem_offset (x
);
896 clear_mem_offset (y
);
899 if (MEM_SIZE_KNOWN_P (x
) && MEM_SIZE_KNOWN_P (y
))
901 mem_size
= MAX (MEM_SIZE (x
), MEM_SIZE (y
));
902 set_mem_size (x
, mem_size
);
903 set_mem_size (y
, mem_size
);
911 set_mem_align (x
, MIN (MEM_ALIGN (x
), MEM_ALIGN (y
)));
912 set_mem_align (y
, MEM_ALIGN (x
));
917 if (MEM_READONLY_P (x
) != MEM_READONLY_P (y
))
919 MEM_READONLY_P (x
) = 0;
920 MEM_READONLY_P (y
) = 0;
922 if (MEM_NOTRAP_P (x
) != MEM_NOTRAP_P (y
))
924 MEM_NOTRAP_P (x
) = 0;
925 MEM_NOTRAP_P (y
) = 0;
927 if (MEM_VOLATILE_P (x
) != MEM_VOLATILE_P (y
))
929 MEM_VOLATILE_P (x
) = 1;
930 MEM_VOLATILE_P (y
) = 1;
934 fmt
= GET_RTX_FORMAT (code
);
935 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
940 /* Two vectors must have the same length. */
941 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
944 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
945 merge_memattrs (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
));
950 merge_memattrs (XEXP (x
, i
), XEXP (y
, i
));
957 /* Checks if patterns P1 and P2 are equivalent, apart from the possibly
958 different single sets S1 and S2. */
961 equal_different_set_p (rtx p1
, rtx s1
, rtx p2
, rtx s2
)
966 if (p1
== s1
&& p2
== s2
)
969 if (GET_CODE (p1
) != PARALLEL
|| GET_CODE (p2
) != PARALLEL
)
972 if (XVECLEN (p1
, 0) != XVECLEN (p2
, 0))
975 for (i
= 0; i
< XVECLEN (p1
, 0); i
++)
977 e1
= XVECEXP (p1
, 0, i
);
978 e2
= XVECEXP (p2
, 0, i
);
979 if (e1
== s1
&& e2
== s2
)
982 ? rtx_renumbered_equal_p (e1
, e2
) : rtx_equal_p (e1
, e2
))
992 /* NOTE1 is the REG_EQUAL note, if any, attached to an insn
993 that is a single_set with a SET_SRC of SRC1. Similarly
996 So effectively NOTE1/NOTE2 are an alternate form of
997 SRC1/SRC2 respectively.
999 Return nonzero if SRC1 or NOTE1 has the same constant
1000 integer value as SRC2 or NOTE2. Else return zero. */
1002 values_equal_p (rtx note1
, rtx note2
, rtx src1
, rtx src2
)
1006 && CONST_INT_P (XEXP (note1
, 0))
1007 && rtx_equal_p (XEXP (note1
, 0), XEXP (note2
, 0)))
1012 && CONST_INT_P (src1
)
1013 && CONST_INT_P (src2
)
1014 && rtx_equal_p (src1
, src2
))
1018 && CONST_INT_P (src2
)
1019 && rtx_equal_p (XEXP (note1
, 0), src2
))
1023 && CONST_INT_P (src1
)
1024 && rtx_equal_p (XEXP (note2
, 0), src1
))
1030 /* Examine register notes on I1 and I2 and return:
1031 - dir_forward if I1 can be replaced by I2, or
1032 - dir_backward if I2 can be replaced by I1, or
1033 - dir_both if both are the case. */
1035 static enum replace_direction
1036 can_replace_by (rtx_insn
*i1
, rtx_insn
*i2
)
1038 rtx s1
, s2
, d1
, d2
, src1
, src2
, note1
, note2
;
1041 /* Check for 2 sets. */
1042 s1
= single_set (i1
);
1043 s2
= single_set (i2
);
1044 if (s1
== NULL_RTX
|| s2
== NULL_RTX
)
1047 /* Check that the 2 sets set the same dest. */
1050 if (!(reload_completed
1051 ? rtx_renumbered_equal_p (d1
, d2
) : rtx_equal_p (d1
, d2
)))
1054 /* Find identical req_equiv or reg_equal note, which implies that the 2 sets
1055 set dest to the same value. */
1056 note1
= find_reg_equal_equiv_note (i1
);
1057 note2
= find_reg_equal_equiv_note (i2
);
1059 src1
= SET_SRC (s1
);
1060 src2
= SET_SRC (s2
);
1062 if (!values_equal_p (note1
, note2
, src1
, src2
))
1065 if (!equal_different_set_p (PATTERN (i1
), s1
, PATTERN (i2
), s2
))
1068 /* Although the 2 sets set dest to the same value, we cannot replace
1069 (set (dest) (const_int))
1072 because we don't know if the reg is live and has the same value at the
1073 location of replacement. */
1074 c1
= CONST_INT_P (src1
);
1075 c2
= CONST_INT_P (src2
);
1081 return dir_backward
;
1086 /* Merges directions A and B. */
1088 static enum replace_direction
1089 merge_dir (enum replace_direction a
, enum replace_direction b
)
1091 /* Implements the following table:
1110 /* Array of flags indexed by reg note kind, true if the given
1111 reg note is CFA related. */
1112 static const bool reg_note_cfa_p
[] = {
1114 #define DEF_REG_NOTE(NAME) false,
1115 #define REG_CFA_NOTE(NAME) true,
1116 #include "reg-notes.def"
1122 /* Return true if I1 and I2 have identical CFA notes (the same order
1123 and equivalent content). */
1126 insns_have_identical_cfa_notes (rtx_insn
*i1
, rtx_insn
*i2
)
1129 for (n1
= REG_NOTES (i1
), n2
= REG_NOTES (i2
); ;
1130 n1
= XEXP (n1
, 1), n2
= XEXP (n2
, 1))
1132 /* Skip over reg notes not related to CFI information. */
1133 while (n1
&& !reg_note_cfa_p
[REG_NOTE_KIND (n1
)])
1135 while (n2
&& !reg_note_cfa_p
[REG_NOTE_KIND (n2
)])
1137 if (n1
== NULL_RTX
&& n2
== NULL_RTX
)
1139 if (n1
== NULL_RTX
|| n2
== NULL_RTX
)
1141 if (XEXP (n1
, 0) == XEXP (n2
, 0))
1143 else if (XEXP (n1
, 0) == NULL_RTX
|| XEXP (n2
, 0) == NULL_RTX
)
1145 else if (!(reload_completed
1146 ? rtx_renumbered_equal_p (XEXP (n1
, 0), XEXP (n2
, 0))
1147 : rtx_equal_p (XEXP (n1
, 0), XEXP (n2
, 0))))
1152 /* Examine I1 and I2 and return:
1153 - dir_forward if I1 can be replaced by I2, or
1154 - dir_backward if I2 can be replaced by I1, or
1155 - dir_both if both are the case. */
1157 static enum replace_direction
1158 old_insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx_insn
*i1
, rtx_insn
*i2
)
1162 /* Verify that I1 and I2 are equivalent. */
1163 if (GET_CODE (i1
) != GET_CODE (i2
))
1166 /* __builtin_unreachable() may lead to empty blocks (ending with
1167 NOTE_INSN_BASIC_BLOCK). They may be crossjumped. */
1168 if (NOTE_INSN_BASIC_BLOCK_P (i1
) && NOTE_INSN_BASIC_BLOCK_P (i2
))
1171 /* ??? Do not allow cross-jumping between different stack levels. */
1172 p1
= find_reg_note (i1
, REG_ARGS_SIZE
, NULL
);
1173 p2
= find_reg_note (i2
, REG_ARGS_SIZE
, NULL
);
1178 if (!rtx_equal_p (p1
, p2
))
1181 /* ??? Worse, this adjustment had better be constant lest we
1182 have differing incoming stack levels. */
1183 if (!frame_pointer_needed
1184 && find_args_size_adjust (i1
) == HOST_WIDE_INT_MIN
)
1190 /* Do not allow cross-jumping between frame related insns and other
1192 if (RTX_FRAME_RELATED_P (i1
) != RTX_FRAME_RELATED_P (i2
))
1198 if (GET_CODE (p1
) != GET_CODE (p2
))
1201 /* If this is a CALL_INSN, compare register usage information.
1202 If we don't check this on stack register machines, the two
1203 CALL_INSNs might be merged leaving reg-stack.c with mismatching
1204 numbers of stack registers in the same basic block.
1205 If we don't check this on machines with delay slots, a delay slot may
1206 be filled that clobbers a parameter expected by the subroutine.
1208 ??? We take the simple route for now and assume that if they're
1209 equal, they were constructed identically.
1211 Also check for identical exception regions. */
1215 /* Ensure the same EH region. */
1216 rtx n1
= find_reg_note (i1
, REG_EH_REGION
, 0);
1217 rtx n2
= find_reg_note (i2
, REG_EH_REGION
, 0);
1222 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1225 if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
1226 CALL_INSN_FUNCTION_USAGE (i2
))
1227 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
))
1230 /* For address sanitizer, never crossjump __asan_report_* builtins,
1231 otherwise errors might be reported on incorrect lines. */
1232 if (flag_sanitize
& SANITIZE_ADDRESS
)
1234 rtx call
= get_call_rtx_from (i1
);
1235 if (call
&& GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
1237 rtx symbol
= XEXP (XEXP (call
, 0), 0);
1238 if (SYMBOL_REF_DECL (symbol
)
1239 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
1241 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
1243 && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
))
1244 >= BUILT_IN_ASAN_REPORT_LOAD1
1245 && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
))
1246 <= BUILT_IN_ASAN_STOREN
)
1253 /* If both i1 and i2 are frame related, verify all the CFA notes
1254 in the same order and with the same content. */
1255 if (RTX_FRAME_RELATED_P (i1
) && !insns_have_identical_cfa_notes (i1
, i2
))
1259 /* If cross_jump_death_matters is not 0, the insn's mode
1260 indicates whether or not the insn contains any stack-like
1263 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
1265 /* If register stack conversion has already been done, then
1266 death notes must also be compared before it is certain that
1267 the two instruction streams match. */
1270 HARD_REG_SET i1_regset
, i2_regset
;
1272 CLEAR_HARD_REG_SET (i1_regset
);
1273 CLEAR_HARD_REG_SET (i2_regset
);
1275 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
1276 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1277 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
1279 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
1280 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1281 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
1283 if (!hard_reg_set_equal_p (i1_regset
, i2_regset
))
1288 if (reload_completed
1289 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
1292 return can_replace_by (i1
, i2
);
1295 /* When comparing insns I1 and I2 in flow_find_cross_jump or
1296 flow_find_head_matching_sequence, ensure the notes match. */
1299 merge_notes (rtx_insn
*i1
, rtx_insn
*i2
)
1301 /* If the merged insns have different REG_EQUAL notes, then
1303 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1304 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1306 if (equiv1
&& !equiv2
)
1307 remove_note (i1
, equiv1
);
1308 else if (!equiv1
&& equiv2
)
1309 remove_note (i2
, equiv2
);
1310 else if (equiv1
&& equiv2
1311 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1313 remove_note (i1
, equiv1
);
1314 remove_note (i2
, equiv2
);
1318 /* Walks from I1 in BB1 backward till the next non-debug insn, and returns the
1319 resulting insn in I1, and the corresponding bb in BB1. At the head of a
1320 bb, if there is a predecessor bb that reaches this bb via fallthru, and
1321 FOLLOW_FALLTHRU, walks further in the predecessor bb and registers this in
1322 DID_FALLTHRU. Otherwise, stops at the head of the bb. */
1325 walk_to_nondebug_insn (rtx_insn
**i1
, basic_block
*bb1
, bool follow_fallthru
,
1330 *did_fallthru
= false;
1333 while (!NONDEBUG_INSN_P (*i1
))
1335 if (*i1
!= BB_HEAD (*bb1
))
1337 *i1
= PREV_INSN (*i1
);
1341 if (!follow_fallthru
)
1344 fallthru
= find_fallthru_edge ((*bb1
)->preds
);
1345 if (!fallthru
|| fallthru
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1346 || !single_succ_p (fallthru
->src
))
1349 *bb1
= fallthru
->src
;
1350 *i1
= BB_END (*bb1
);
1351 *did_fallthru
= true;
1355 /* Look through the insns at the end of BB1 and BB2 and find the longest
1356 sequence that are either equivalent, or allow forward or backward
1357 replacement. Store the first insns for that sequence in *F1 and *F2 and
1358 return the sequence length.
1360 DIR_P indicates the allowed replacement direction on function entry, and
1361 the actual replacement direction on function exit. If NULL, only equivalent
1362 sequences are allowed.
1364 To simplify callers of this function, if the blocks match exactly,
1365 store the head of the blocks in *F1 and *F2. */
1368 flow_find_cross_jump (basic_block bb1
, basic_block bb2
, rtx_insn
**f1
,
1369 rtx_insn
**f2
, enum replace_direction
*dir_p
)
1371 rtx_insn
*i1
, *i2
, *last1
, *last2
, *afterlast1
, *afterlast2
;
1373 enum replace_direction dir
, last_dir
, afterlast_dir
;
1374 bool follow_fallthru
, did_fallthru
;
1380 afterlast_dir
= dir
;
1381 last_dir
= afterlast_dir
;
1383 /* Skip simple jumps at the end of the blocks. Complex jumps still
1384 need to be compared for equivalence, which we'll do below. */
1387 last1
= afterlast1
= last2
= afterlast2
= NULL
;
1389 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1392 i1
= PREV_INSN (i1
);
1397 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1400 /* Count everything except for unconditional jump as insn.
1401 Don't count any jumps if dir_p is NULL. */
1402 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
&& dir_p
)
1404 i2
= PREV_INSN (i2
);
1409 /* In the following example, we can replace all jumps to C by jumps to A.
1411 This removes 4 duplicate insns.
1412 [bb A] insn1 [bb C] insn1
1418 We could also replace all jumps to A by jumps to C, but that leaves B
1419 alive, and removes only 2 duplicate insns. In a subsequent crossjump
1420 step, all jumps to B would be replaced with jumps to the middle of C,
1421 achieving the same result with more effort.
1422 So we allow only the first possibility, which means that we don't allow
1423 fallthru in the block that's being replaced. */
1425 follow_fallthru
= dir_p
&& dir
!= dir_forward
;
1426 walk_to_nondebug_insn (&i1
, &bb1
, follow_fallthru
, &did_fallthru
);
1430 follow_fallthru
= dir_p
&& dir
!= dir_backward
;
1431 walk_to_nondebug_insn (&i2
, &bb2
, follow_fallthru
, &did_fallthru
);
1435 if (i1
== BB_HEAD (bb1
) || i2
== BB_HEAD (bb2
))
1438 dir
= merge_dir (dir
, old_insns_match_p (0, i1
, i2
));
1439 if (dir
== dir_none
|| (!dir_p
&& dir
!= dir_both
))
1442 merge_memattrs (i1
, i2
);
1444 /* Don't begin a cross-jump with a NOTE insn. */
1447 merge_notes (i1
, i2
);
1449 afterlast1
= last1
, afterlast2
= last2
;
1450 last1
= i1
, last2
= i2
;
1451 afterlast_dir
= last_dir
;
1453 if (active_insn_p (i1
))
1457 i1
= PREV_INSN (i1
);
1458 i2
= PREV_INSN (i2
);
1461 /* Don't allow the insn after a compare to be shared by
1462 cross-jumping unless the compare is also shared. */
1463 if (HAVE_cc0
&& ninsns
&& reg_mentioned_p (cc0_rtx
, last1
)
1464 && ! sets_cc0_p (last1
))
1465 last1
= afterlast1
, last2
= afterlast2
, last_dir
= afterlast_dir
, ninsns
--;
1467 /* Include preceding notes and labels in the cross-jump. One,
1468 this may bring us to the head of the blocks as requested above.
1469 Two, it keeps line number notes as matched as may be. */
1472 bb1
= BLOCK_FOR_INSN (last1
);
1473 while (last1
!= BB_HEAD (bb1
) && !NONDEBUG_INSN_P (PREV_INSN (last1
)))
1474 last1
= PREV_INSN (last1
);
1476 if (last1
!= BB_HEAD (bb1
) && LABEL_P (PREV_INSN (last1
)))
1477 last1
= PREV_INSN (last1
);
1479 bb2
= BLOCK_FOR_INSN (last2
);
1480 while (last2
!= BB_HEAD (bb2
) && !NONDEBUG_INSN_P (PREV_INSN (last2
)))
1481 last2
= PREV_INSN (last2
);
1483 if (last2
!= BB_HEAD (bb2
) && LABEL_P (PREV_INSN (last2
)))
1484 last2
= PREV_INSN (last2
);
1495 /* Like flow_find_cross_jump, except start looking for a matching sequence from
1496 the head of the two blocks. Do not include jumps at the end.
1497 If STOP_AFTER is nonzero, stop after finding that many matching
1498 instructions. If STOP_AFTER is zero, count all INSN_P insns, if it is
1499 non-zero, only count active insns. */
1502 flow_find_head_matching_sequence (basic_block bb1
, basic_block bb2
, rtx_insn
**f1
,
1503 rtx_insn
**f2
, int stop_after
)
1505 rtx_insn
*i1
, *i2
, *last1
, *last2
, *beforelast1
, *beforelast2
;
1509 int nehedges1
= 0, nehedges2
= 0;
1511 FOR_EACH_EDGE (e
, ei
, bb1
->succs
)
1512 if (e
->flags
& EDGE_EH
)
1514 FOR_EACH_EDGE (e
, ei
, bb2
->succs
)
1515 if (e
->flags
& EDGE_EH
)
1520 last1
= beforelast1
= last2
= beforelast2
= NULL
;
1524 /* Ignore notes, except NOTE_INSN_EPILOGUE_BEG. */
1525 while (!NONDEBUG_INSN_P (i1
) && i1
!= BB_END (bb1
))
1527 if (NOTE_P (i1
) && NOTE_KIND (i1
) == NOTE_INSN_EPILOGUE_BEG
)
1529 i1
= NEXT_INSN (i1
);
1532 while (!NONDEBUG_INSN_P (i2
) && i2
!= BB_END (bb2
))
1534 if (NOTE_P (i2
) && NOTE_KIND (i2
) == NOTE_INSN_EPILOGUE_BEG
)
1536 i2
= NEXT_INSN (i2
);
1539 if ((i1
== BB_END (bb1
) && !NONDEBUG_INSN_P (i1
))
1540 || (i2
== BB_END (bb2
) && !NONDEBUG_INSN_P (i2
)))
1543 if (NOTE_P (i1
) || NOTE_P (i2
)
1544 || JUMP_P (i1
) || JUMP_P (i2
))
1547 /* A sanity check to make sure we're not merging insns with different
1548 effects on EH. If only one of them ends a basic block, it shouldn't
1549 have an EH edge; if both end a basic block, there should be the same
1550 number of EH edges. */
1551 if ((i1
== BB_END (bb1
) && i2
!= BB_END (bb2
)
1553 || (i2
== BB_END (bb2
) && i1
!= BB_END (bb1
)
1555 || (i1
== BB_END (bb1
) && i2
== BB_END (bb2
)
1556 && nehedges1
!= nehedges2
))
1559 if (old_insns_match_p (0, i1
, i2
) != dir_both
)
1562 merge_memattrs (i1
, i2
);
1564 /* Don't begin a cross-jump with a NOTE insn. */
1567 merge_notes (i1
, i2
);
1569 beforelast1
= last1
, beforelast2
= last2
;
1570 last1
= i1
, last2
= i2
;
1571 if (!stop_after
|| active_insn_p (i1
))
1575 if (i1
== BB_END (bb1
) || i2
== BB_END (bb2
)
1576 || (stop_after
> 0 && ninsns
== stop_after
))
1579 i1
= NEXT_INSN (i1
);
1580 i2
= NEXT_INSN (i2
);
1583 /* Don't allow a compare to be shared by cross-jumping unless the insn
1584 after the compare is also shared. */
1585 if (HAVE_cc0
&& ninsns
&& reg_mentioned_p (cc0_rtx
, last1
)
1586 && sets_cc0_p (last1
))
1587 last1
= beforelast1
, last2
= beforelast2
, ninsns
--;
1598 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1599 the branch instruction. This means that if we commonize the control
1600 flow before end of the basic block, the semantic remains unchanged.
1602 We may assume that there exists one edge with a common destination. */
1605 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1607 int nehedges1
= 0, nehedges2
= 0;
1608 edge fallthru1
= 0, fallthru2
= 0;
1612 /* If we performed shrink-wrapping, edges to the exit block can
1613 only be distinguished for JUMP_INSNs. The two paths may differ in
1614 whether they went through the prologue. Sibcalls are fine, we know
1615 that we either didn't need or inserted an epilogue before them. */
1616 if (crtl
->shrink_wrapped
1617 && single_succ_p (bb1
)
1618 && single_succ (bb1
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
1619 && !JUMP_P (BB_END (bb1
))
1620 && !(CALL_P (BB_END (bb1
)) && SIBLING_CALL_P (BB_END (bb1
))))
1623 /* If BB1 has only one successor, we may be looking at either an
1624 unconditional jump, or a fake edge to exit. */
1625 if (single_succ_p (bb1
)
1626 && (single_succ_edge (bb1
)->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1627 && (!JUMP_P (BB_END (bb1
)) || simplejump_p (BB_END (bb1
))))
1628 return (single_succ_p (bb2
)
1629 && (single_succ_edge (bb2
)->flags
1630 & (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1631 && (!JUMP_P (BB_END (bb2
)) || simplejump_p (BB_END (bb2
))));
1633 /* Match conditional jumps - this may get tricky when fallthru and branch
1634 edges are crossed. */
1635 if (EDGE_COUNT (bb1
->succs
) == 2
1636 && any_condjump_p (BB_END (bb1
))
1637 && onlyjump_p (BB_END (bb1
)))
1639 edge b1
, f1
, b2
, f2
;
1640 bool reverse
, match
;
1641 rtx set1
, set2
, cond1
, cond2
;
1642 enum rtx_code code1
, code2
;
1644 if (EDGE_COUNT (bb2
->succs
) != 2
1645 || !any_condjump_p (BB_END (bb2
))
1646 || !onlyjump_p (BB_END (bb2
)))
1649 b1
= BRANCH_EDGE (bb1
);
1650 b2
= BRANCH_EDGE (bb2
);
1651 f1
= FALLTHRU_EDGE (bb1
);
1652 f2
= FALLTHRU_EDGE (bb2
);
1654 /* Get around possible forwarders on fallthru edges. Other cases
1655 should be optimized out already. */
1656 if (FORWARDER_BLOCK_P (f1
->dest
))
1657 f1
= single_succ_edge (f1
->dest
);
1659 if (FORWARDER_BLOCK_P (f2
->dest
))
1660 f2
= single_succ_edge (f2
->dest
);
1662 /* To simplify use of this function, return false if there are
1663 unneeded forwarder blocks. These will get eliminated later
1664 during cleanup_cfg. */
1665 if (FORWARDER_BLOCK_P (f1
->dest
)
1666 || FORWARDER_BLOCK_P (f2
->dest
)
1667 || FORWARDER_BLOCK_P (b1
->dest
)
1668 || FORWARDER_BLOCK_P (b2
->dest
))
1671 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1673 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1678 set1
= pc_set (BB_END (bb1
));
1679 set2
= pc_set (BB_END (bb2
));
1680 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1681 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1684 cond1
= XEXP (SET_SRC (set1
), 0);
1685 cond2
= XEXP (SET_SRC (set2
), 0);
1686 code1
= GET_CODE (cond1
);
1688 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
1690 code2
= GET_CODE (cond2
);
1692 if (code2
== UNKNOWN
)
1695 /* Verify codes and operands match. */
1696 match
= ((code1
== code2
1697 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1698 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1699 || (code1
== swap_condition (code2
)
1700 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1702 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1705 /* If we return true, we will join the blocks. Which means that
1706 we will only have one branch prediction bit to work with. Thus
1707 we require the existing branches to have probabilities that are
1710 && optimize_bb_for_speed_p (bb1
)
1711 && optimize_bb_for_speed_p (bb2
))
1713 profile_probability prob2
;
1715 if (b1
->dest
== b2
->dest
)
1716 prob2
= b2
->probability
;
1718 /* Do not use f2 probability as f2 may be forwarded. */
1719 prob2
= b2
->probability
.invert ();
1721 /* Fail if the difference in probabilities is greater than 50%.
1722 This rules out two well-predicted branches with opposite
1724 if (b1
->probability
.differs_lot_from_p (prob2
))
1729 "Outcomes of branch in bb %i and %i differ too"
1730 " much (", bb1
->index
, bb2
->index
);
1731 b1
->probability
.dump (dump_file
);
1732 prob2
.dump (dump_file
);
1733 fprintf (dump_file
, ")\n");
1739 if (dump_file
&& match
)
1740 fprintf (dump_file
, "Conditionals in bb %i and %i match.\n",
1741 bb1
->index
, bb2
->index
);
1746 /* Generic case - we are seeing a computed jump, table jump or trapping
1749 /* Check whether there are tablejumps in the end of BB1 and BB2.
1750 Return true if they are identical. */
1752 rtx_insn
*label1
, *label2
;
1753 rtx_jump_table_data
*table1
, *table2
;
1755 if (tablejump_p (BB_END (bb1
), &label1
, &table1
)
1756 && tablejump_p (BB_END (bb2
), &label2
, &table2
)
1757 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1759 /* The labels should never be the same rtx. If they really are same
1760 the jump tables are same too. So disable crossjumping of blocks BB1
1761 and BB2 because when deleting the common insns in the end of BB1
1762 by delete_basic_block () the jump table would be deleted too. */
1763 /* If LABEL2 is referenced in BB1->END do not do anything
1764 because we would loose information when replacing
1765 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1766 if (label1
!= label2
&& !rtx_referenced_p (label2
, BB_END (bb1
)))
1768 /* Set IDENTICAL to true when the tables are identical. */
1769 bool identical
= false;
1772 p1
= PATTERN (table1
);
1773 p2
= PATTERN (table2
);
1774 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1778 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1779 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1780 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1781 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1786 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1787 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1795 /* Temporarily replace references to LABEL1 with LABEL2
1796 in BB1->END so that we could compare the instructions. */
1797 replace_label_in_insn (BB_END (bb1
), label1
, label2
, false);
1799 match
= (old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
))
1801 if (dump_file
&& match
)
1803 "Tablejumps in bb %i and %i match.\n",
1804 bb1
->index
, bb2
->index
);
1806 /* Set the original label in BB1->END because when deleting
1807 a block whose end is a tablejump, the tablejump referenced
1808 from the instruction is deleted too. */
1809 replace_label_in_insn (BB_END (bb1
), label2
, label1
, false);
1818 /* Find the last non-debug non-note instruction in each bb, except
1819 stop when we see the NOTE_INSN_BASIC_BLOCK, as old_insns_match_p
1820 handles that case specially. old_insns_match_p does not handle
1821 other types of instruction notes. */
1822 rtx_insn
*last1
= BB_END (bb1
);
1823 rtx_insn
*last2
= BB_END (bb2
);
1824 while (!NOTE_INSN_BASIC_BLOCK_P (last1
) &&
1825 (DEBUG_INSN_P (last1
) || NOTE_P (last1
)))
1826 last1
= PREV_INSN (last1
);
1827 while (!NOTE_INSN_BASIC_BLOCK_P (last2
) &&
1828 (DEBUG_INSN_P (last2
) || NOTE_P (last2
)))
1829 last2
= PREV_INSN (last2
);
1830 gcc_assert (last1
&& last2
);
1832 /* First ensure that the instructions match. There may be many outgoing
1833 edges so this test is generally cheaper. */
1834 if (old_insns_match_p (mode
, last1
, last2
) != dir_both
)
1837 /* Search the outgoing edges, ensure that the counts do match, find possible
1838 fallthru and exception handling edges since these needs more
1840 if (EDGE_COUNT (bb1
->succs
) != EDGE_COUNT (bb2
->succs
))
1843 bool nonfakeedges
= false;
1844 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1846 e2
= EDGE_SUCC (bb2
, ei
.index
);
1848 if ((e1
->flags
& EDGE_FAKE
) == 0)
1849 nonfakeedges
= true;
1851 if (e1
->flags
& EDGE_EH
)
1854 if (e2
->flags
& EDGE_EH
)
1857 if (e1
->flags
& EDGE_FALLTHRU
)
1859 if (e2
->flags
& EDGE_FALLTHRU
)
1863 /* If number of edges of various types does not match, fail. */
1864 if (nehedges1
!= nehedges2
1865 || (fallthru1
!= 0) != (fallthru2
!= 0))
1868 /* If !ACCUMULATE_OUTGOING_ARGS, bb1 (and bb2) have no successors
1869 and the last real insn doesn't have REG_ARGS_SIZE note, don't
1870 attempt to optimize, as the two basic blocks might have different
1871 REG_ARGS_SIZE depths. For noreturn calls and unconditional
1872 traps there should be REG_ARG_SIZE notes, they could be missing
1873 for __builtin_unreachable () uses though. */
1875 && !ACCUMULATE_OUTGOING_ARGS
1877 || !find_reg_note (last1
, REG_ARGS_SIZE
, NULL
)))
1880 /* fallthru edges must be forwarded to the same destination. */
1883 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1884 ? single_succ (fallthru1
->dest
): fallthru1
->dest
);
1885 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1886 ? single_succ (fallthru2
->dest
): fallthru2
->dest
);
1892 /* Ensure the same EH region. */
1894 rtx n1
= find_reg_note (BB_END (bb1
), REG_EH_REGION
, 0);
1895 rtx n2
= find_reg_note (BB_END (bb2
), REG_EH_REGION
, 0);
1900 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1904 /* The same checks as in try_crossjump_to_edge. It is required for RTL
1905 version of sequence abstraction. */
1906 FOR_EACH_EDGE (e1
, ei
, bb2
->succs
)
1910 basic_block d1
= e1
->dest
;
1912 if (FORWARDER_BLOCK_P (d1
))
1913 d1
= EDGE_SUCC (d1
, 0)->dest
;
1915 FOR_EACH_EDGE (e2
, ei
, bb1
->succs
)
1917 basic_block d2
= e2
->dest
;
1918 if (FORWARDER_BLOCK_P (d2
))
1919 d2
= EDGE_SUCC (d2
, 0)->dest
;
1931 /* Returns true if BB basic block has a preserve label. */
1934 block_has_preserve_label (basic_block bb
)
1938 && LABEL_PRESERVE_P (block_label (bb
)));
1941 /* E1 and E2 are edges with the same destination block. Search their
1942 predecessors for common code. If found, redirect control flow from
1943 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC (dir_forward),
1944 or the other way around (dir_backward). DIR specifies the allowed
1945 replacement direction. */
1948 try_crossjump_to_edge (int mode
, edge e1
, edge e2
,
1949 enum replace_direction dir
)
1952 basic_block src1
= e1
->src
, src2
= e2
->src
;
1953 basic_block redirect_to
, redirect_from
, to_remove
;
1954 basic_block osrc1
, osrc2
, redirect_edges_to
, tmp
;
1955 rtx_insn
*newpos1
, *newpos2
;
1959 newpos1
= newpos2
= NULL
;
1961 /* If we have partitioned hot/cold basic blocks, it is a bad idea
1962 to try this optimization.
1964 Basic block partitioning may result in some jumps that appear to
1965 be optimizable (or blocks that appear to be mergeable), but which really
1966 must be left untouched (they are required to make it safely across
1967 partition boundaries). See the comments at the top of
1968 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1970 if (crtl
->has_bb_partition
&& reload_completed
)
1973 /* Search backward through forwarder blocks. We don't need to worry
1974 about multiple entry or chained forwarders, as they will be optimized
1975 away. We do this to look past the unconditional jump following a
1976 conditional jump that is required due to the current CFG shape. */
1977 if (single_pred_p (src1
)
1978 && FORWARDER_BLOCK_P (src1
))
1979 e1
= single_pred_edge (src1
), src1
= e1
->src
;
1981 if (single_pred_p (src2
)
1982 && FORWARDER_BLOCK_P (src2
))
1983 e2
= single_pred_edge (src2
), src2
= e2
->src
;
1985 /* Nothing to do if we reach ENTRY, or a common source block. */
1986 if (src1
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || src2
1987 == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1992 /* Seeing more than 1 forwarder blocks would confuse us later... */
1993 if (FORWARDER_BLOCK_P (e1
->dest
)
1994 && FORWARDER_BLOCK_P (single_succ (e1
->dest
)))
1997 if (FORWARDER_BLOCK_P (e2
->dest
)
1998 && FORWARDER_BLOCK_P (single_succ (e2
->dest
)))
2001 /* Likewise with dead code (possibly newly created by the other optimizations
2003 if (EDGE_COUNT (src1
->preds
) == 0 || EDGE_COUNT (src2
->preds
) == 0)
2006 /* Look for the common insn sequence, part the first ... */
2007 if (!outgoing_edges_match (mode
, src1
, src2
))
2010 /* ... and part the second. */
2011 nmatch
= flow_find_cross_jump (src1
, src2
, &newpos1
, &newpos2
, &dir
);
2015 if (newpos1
!= NULL_RTX
)
2016 src1
= BLOCK_FOR_INSN (newpos1
);
2017 if (newpos2
!= NULL_RTX
)
2018 src2
= BLOCK_FOR_INSN (newpos2
);
2020 /* Check that SRC1 and SRC2 have preds again. They may have changed
2021 above due to the call to flow_find_cross_jump. */
2022 if (EDGE_COUNT (src1
->preds
) == 0 || EDGE_COUNT (src2
->preds
) == 0)
2025 if (dir
== dir_backward
)
2027 #define SWAP(T, X, Y) do { T tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
2028 SWAP (basic_block
, osrc1
, osrc2
);
2029 SWAP (basic_block
, src1
, src2
);
2030 SWAP (edge
, e1
, e2
);
2031 SWAP (rtx_insn
*, newpos1
, newpos2
);
2035 /* Don't proceed with the crossjump unless we found a sufficient number
2036 of matching instructions or the 'from' block was totally matched
2037 (such that its predecessors will hopefully be redirected and the
2039 if ((nmatch
< PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS
))
2040 && (newpos1
!= BB_HEAD (src1
)))
2043 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */
2044 if (block_has_preserve_label (e1
->dest
)
2045 && (e1
->flags
& EDGE_ABNORMAL
))
2048 /* Here we know that the insns in the end of SRC1 which are common with SRC2
2050 If we have tablejumps in the end of SRC1 and SRC2
2051 they have been already compared for equivalence in outgoing_edges_match ()
2052 so replace the references to TABLE1 by references to TABLE2. */
2054 rtx_insn
*label1
, *label2
;
2055 rtx_jump_table_data
*table1
, *table2
;
2057 if (tablejump_p (BB_END (osrc1
), &label1
, &table1
)
2058 && tablejump_p (BB_END (osrc2
), &label2
, &table2
)
2059 && label1
!= label2
)
2063 /* Replace references to LABEL1 with LABEL2. */
2064 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
2066 /* Do not replace the label in SRC1->END because when deleting
2067 a block whose end is a tablejump, the tablejump referenced
2068 from the instruction is deleted too. */
2069 if (insn
!= BB_END (osrc1
))
2070 replace_label_in_insn (insn
, label1
, label2
, true);
2075 /* Avoid splitting if possible. We must always split when SRC2 has
2076 EH predecessor edges, or we may end up with basic blocks with both
2077 normal and EH predecessor edges. */
2078 if (newpos2
== BB_HEAD (src2
)
2079 && !(EDGE_PRED (src2
, 0)->flags
& EDGE_EH
))
2083 if (newpos2
== BB_HEAD (src2
))
2085 /* Skip possible basic block header. */
2086 if (LABEL_P (newpos2
))
2087 newpos2
= NEXT_INSN (newpos2
);
2088 while (DEBUG_INSN_P (newpos2
))
2089 newpos2
= NEXT_INSN (newpos2
);
2090 if (NOTE_P (newpos2
))
2091 newpos2
= NEXT_INSN (newpos2
);
2092 while (DEBUG_INSN_P (newpos2
))
2093 newpos2
= NEXT_INSN (newpos2
);
2097 fprintf (dump_file
, "Splitting bb %i before %i insns\n",
2098 src2
->index
, nmatch
);
2099 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
2104 "Cross jumping from bb %i to bb %i; %i common insns\n",
2105 src1
->index
, src2
->index
, nmatch
);
2107 /* We may have some registers visible through the block. */
2108 df_set_bb_dirty (redirect_to
);
2111 redirect_edges_to
= redirect_to
;
2113 redirect_edges_to
= osrc2
;
2115 /* Recompute the frequencies and counts of outgoing edges. */
2116 FOR_EACH_EDGE (s
, ei
, redirect_edges_to
->succs
)
2120 basic_block d
= s
->dest
;
2122 if (FORWARDER_BLOCK_P (d
))
2123 d
= single_succ (d
);
2125 FOR_EACH_EDGE (s2
, ei
, src1
->succs
)
2127 basic_block d2
= s2
->dest
;
2128 if (FORWARDER_BLOCK_P (d2
))
2129 d2
= single_succ (d2
);
2134 s
->count
+= s2
->count
;
2136 /* Take care to update possible forwarder blocks. We verified
2137 that there is no more than one in the chain, so we can't run
2138 into infinite loop. */
2139 if (FORWARDER_BLOCK_P (s
->dest
))
2141 single_succ_edge (s
->dest
)->count
+= s2
->count
;
2142 s
->dest
->count
+= s2
->count
;
2143 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
2146 if (FORWARDER_BLOCK_P (s2
->dest
))
2148 single_succ_edge (s2
->dest
)->count
-= s2
->count
;
2149 s2
->dest
->count
-= s2
->count
;
2150 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
2151 if (s2
->dest
->frequency
< 0)
2152 s2
->dest
->frequency
= 0;
2155 if (!redirect_edges_to
->frequency
&& !src1
->frequency
)
2156 s
->probability
= s
->probability
.combine_with_freq
2157 (redirect_edges_to
->frequency
,
2158 s2
->probability
, src1
->frequency
);
2161 /* Adjust count and frequency for the block. An earlier jump
2162 threading pass may have left the profile in an inconsistent
2163 state (see update_bb_profile_for_threading) so we must be
2164 prepared for overflows. */
2168 tmp
->count
+= src1
->count
;
2169 tmp
->frequency
+= src1
->frequency
;
2170 if (tmp
->frequency
> BB_FREQ_MAX
)
2171 tmp
->frequency
= BB_FREQ_MAX
;
2172 if (tmp
== redirect_edges_to
)
2174 tmp
= find_fallthru_edge (tmp
->succs
)->dest
;
2177 update_br_prob_note (redirect_edges_to
);
2179 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
2181 /* Skip possible basic block header. */
2182 if (LABEL_P (newpos1
))
2183 newpos1
= NEXT_INSN (newpos1
);
2185 while (DEBUG_INSN_P (newpos1
))
2186 newpos1
= NEXT_INSN (newpos1
);
2188 if (NOTE_INSN_BASIC_BLOCK_P (newpos1
))
2189 newpos1
= NEXT_INSN (newpos1
);
2191 while (DEBUG_INSN_P (newpos1
))
2192 newpos1
= NEXT_INSN (newpos1
);
2194 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
2195 to_remove
= single_succ (redirect_from
);
2197 redirect_edge_and_branch_force (single_succ_edge (redirect_from
), redirect_to
);
2198 delete_basic_block (to_remove
);
2200 update_forwarder_flag (redirect_from
);
2201 if (redirect_to
!= src2
)
2202 update_forwarder_flag (src2
);
2207 /* Search the predecessors of BB for common insn sequences. When found,
2208 share code between them by redirecting control flow. Return true if
2209 any changes made. */
2212 try_crossjump_bb (int mode
, basic_block bb
)
2214 edge e
, e2
, fallthru
;
2216 unsigned max
, ix
, ix2
;
2218 /* Nothing to do if there is not at least two incoming edges. */
2219 if (EDGE_COUNT (bb
->preds
) < 2)
2222 /* Don't crossjump if this block ends in a computed jump,
2223 unless we are optimizing for size. */
2224 if (optimize_bb_for_size_p (bb
)
2225 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2226 && computed_jump_p (BB_END (bb
)))
2229 /* If we are partitioning hot/cold basic blocks, we don't want to
2230 mess up unconditional or indirect jumps that cross between hot
2233 Basic block partitioning may result in some jumps that appear to
2234 be optimizable (or blocks that appear to be mergeable), but which really
2235 must be left untouched (they are required to make it safely across
2236 partition boundaries). See the comments at the top of
2237 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
2239 if (BB_PARTITION (EDGE_PRED (bb
, 0)->src
) !=
2240 BB_PARTITION (EDGE_PRED (bb
, 1)->src
)
2241 || (EDGE_PRED (bb
, 0)->flags
& EDGE_CROSSING
))
2244 /* It is always cheapest to redirect a block that ends in a branch to
2245 a block that falls through into BB, as that adds no branches to the
2246 program. We'll try that combination first. */
2248 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
2250 if (EDGE_COUNT (bb
->preds
) > max
)
2253 fallthru
= find_fallthru_edge (bb
->preds
);
2256 for (ix
= 0; ix
< EDGE_COUNT (bb
->preds
);)
2258 e
= EDGE_PRED (bb
, ix
);
2261 /* As noted above, first try with the fallthru predecessor (or, a
2262 fallthru predecessor if we are in cfglayout mode). */
2265 /* Don't combine the fallthru edge into anything else.
2266 If there is a match, we'll do it the other way around. */
2269 /* If nothing changed since the last attempt, there is nothing
2272 && !((e
->src
->flags
& BB_MODIFIED
)
2273 || (fallthru
->src
->flags
& BB_MODIFIED
)))
2276 if (try_crossjump_to_edge (mode
, e
, fallthru
, dir_forward
))
2284 /* Non-obvious work limiting check: Recognize that we're going
2285 to call try_crossjump_bb on every basic block. So if we have
2286 two blocks with lots of outgoing edges (a switch) and they
2287 share lots of common destinations, then we would do the
2288 cross-jump check once for each common destination.
2290 Now, if the blocks actually are cross-jump candidates, then
2291 all of their destinations will be shared. Which means that
2292 we only need check them for cross-jump candidacy once. We
2293 can eliminate redundant checks of crossjump(A,B) by arbitrarily
2294 choosing to do the check from the block for which the edge
2295 in question is the first successor of A. */
2296 if (EDGE_SUCC (e
->src
, 0) != e
)
2299 for (ix2
= 0; ix2
< EDGE_COUNT (bb
->preds
); ix2
++)
2301 e2
= EDGE_PRED (bb
, ix2
);
2306 /* We've already checked the fallthru edge above. */
2310 /* The "first successor" check above only prevents multiple
2311 checks of crossjump(A,B). In order to prevent redundant
2312 checks of crossjump(B,A), require that A be the block
2313 with the lowest index. */
2314 if (e
->src
->index
> e2
->src
->index
)
2317 /* If nothing changed since the last attempt, there is nothing
2320 && !((e
->src
->flags
& BB_MODIFIED
)
2321 || (e2
->src
->flags
& BB_MODIFIED
)))
2324 /* Both e and e2 are not fallthru edges, so we can crossjump in either
2326 if (try_crossjump_to_edge (mode
, e
, e2
, dir_both
))
2336 crossjumps_occurred
= true;
2341 /* Search the successors of BB for common insn sequences. When found,
2342 share code between them by moving it across the basic block
2343 boundary. Return true if any changes made. */
2346 try_head_merge_bb (basic_block bb
)
2348 basic_block final_dest_bb
= NULL
;
2349 int max_match
= INT_MAX
;
2351 rtx_insn
**headptr
, **currptr
, **nextptr
;
2352 bool changed
, moveall
;
2354 rtx_insn
*e0_last_head
;
2356 rtx_insn
*move_before
;
2357 unsigned nedges
= EDGE_COUNT (bb
->succs
);
2358 rtx_insn
*jump
= BB_END (bb
);
2359 regset live
, live_union
;
2361 /* Nothing to do if there is not at least two outgoing edges. */
2365 /* Don't crossjump if this block ends in a computed jump,
2366 unless we are optimizing for size. */
2367 if (optimize_bb_for_size_p (bb
)
2368 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2369 && computed_jump_p (BB_END (bb
)))
2372 cond
= get_condition (jump
, &move_before
, true, false);
2373 if (cond
== NULL_RTX
)
2375 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, jump
))
2376 move_before
= prev_nonnote_nondebug_insn (jump
);
2381 for (ix
= 0; ix
< nedges
; ix
++)
2382 if (EDGE_SUCC (bb
, ix
)->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
2385 for (ix
= 0; ix
< nedges
; ix
++)
2387 edge e
= EDGE_SUCC (bb
, ix
);
2388 basic_block other_bb
= e
->dest
;
2390 if (df_get_bb_dirty (other_bb
))
2392 block_was_dirty
= true;
2396 if (e
->flags
& EDGE_ABNORMAL
)
2399 /* Normally, all destination blocks must only be reachable from this
2400 block, i.e. they must have one incoming edge.
2402 There is one special case we can handle, that of multiple consecutive
2403 jumps where the first jumps to one of the targets of the second jump.
2404 This happens frequently in switch statements for default labels.
2405 The structure is as follows:
2411 jump with targets A, B, C, D...
2413 has two incoming edges, from FINAL_DEST_BB and BB
2415 In this case, we can try to move the insns through BB and into
2417 if (EDGE_COUNT (other_bb
->preds
) != 1)
2419 edge incoming_edge
, incoming_bb_other_edge
;
2422 if (final_dest_bb
!= NULL
2423 || EDGE_COUNT (other_bb
->preds
) != 2)
2426 /* We must be able to move the insns across the whole block. */
2427 move_before
= BB_HEAD (bb
);
2428 while (!NONDEBUG_INSN_P (move_before
))
2429 move_before
= NEXT_INSN (move_before
);
2431 if (EDGE_COUNT (bb
->preds
) != 1)
2433 incoming_edge
= EDGE_PRED (bb
, 0);
2434 final_dest_bb
= incoming_edge
->src
;
2435 if (EDGE_COUNT (final_dest_bb
->succs
) != 2)
2437 FOR_EACH_EDGE (incoming_bb_other_edge
, ei
, final_dest_bb
->succs
)
2438 if (incoming_bb_other_edge
!= incoming_edge
)
2440 if (incoming_bb_other_edge
->dest
!= other_bb
)
2445 e0
= EDGE_SUCC (bb
, 0);
2446 e0_last_head
= NULL
;
2449 for (ix
= 1; ix
< nedges
; ix
++)
2451 edge e
= EDGE_SUCC (bb
, ix
);
2452 rtx_insn
*e0_last
, *e_last
;
2455 nmatch
= flow_find_head_matching_sequence (e0
->dest
, e
->dest
,
2456 &e0_last
, &e_last
, 0);
2460 if (nmatch
< max_match
)
2463 e0_last_head
= e0_last
;
2467 /* If we matched an entire block, we probably have to avoid moving the
2470 && e0_last_head
== BB_END (e0
->dest
)
2471 && (find_reg_note (e0_last_head
, REG_EH_REGION
, 0)
2472 || control_flow_insn_p (e0_last_head
)))
2478 e0_last_head
= prev_real_insn (e0_last_head
);
2479 while (DEBUG_INSN_P (e0_last_head
));
2485 /* We must find a union of the live registers at each of the end points. */
2486 live
= BITMAP_ALLOC (NULL
);
2487 live_union
= BITMAP_ALLOC (NULL
);
2489 currptr
= XNEWVEC (rtx_insn
*, nedges
);
2490 headptr
= XNEWVEC (rtx_insn
*, nedges
);
2491 nextptr
= XNEWVEC (rtx_insn
*, nedges
);
2493 for (ix
= 0; ix
< nedges
; ix
++)
2496 basic_block merge_bb
= EDGE_SUCC (bb
, ix
)->dest
;
2497 rtx_insn
*head
= BB_HEAD (merge_bb
);
2499 while (!NONDEBUG_INSN_P (head
))
2500 head
= NEXT_INSN (head
);
2504 /* Compute the end point and live information */
2505 for (j
= 1; j
< max_match
; j
++)
2507 head
= NEXT_INSN (head
);
2508 while (!NONDEBUG_INSN_P (head
));
2509 simulate_backwards_to_point (merge_bb
, live
, head
);
2510 IOR_REG_SET (live_union
, live
);
2513 /* If we're moving across two blocks, verify the validity of the
2514 first move, then adjust the target and let the loop below deal
2515 with the final move. */
2516 if (final_dest_bb
!= NULL
)
2518 rtx_insn
*move_upto
;
2520 moveall
= can_move_insns_across (currptr
[0], e0_last_head
, move_before
,
2521 jump
, e0
->dest
, live_union
,
2525 if (move_upto
== NULL_RTX
)
2528 while (e0_last_head
!= move_upto
)
2530 df_simulate_one_insn_backwards (e0
->dest
, e0_last_head
,
2532 e0_last_head
= PREV_INSN (e0_last_head
);
2535 if (e0_last_head
== NULL_RTX
)
2538 jump
= BB_END (final_dest_bb
);
2539 cond
= get_condition (jump
, &move_before
, true, false);
2540 if (cond
== NULL_RTX
)
2542 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, jump
))
2543 move_before
= prev_nonnote_nondebug_insn (jump
);
2551 rtx_insn
*move_upto
;
2552 moveall
= can_move_insns_across (currptr
[0], e0_last_head
,
2553 move_before
, jump
, e0
->dest
, live_union
,
2555 if (!moveall
&& move_upto
== NULL_RTX
)
2557 if (jump
== move_before
)
2560 /* Try again, using a different insertion point. */
2563 /* Don't try moving before a cc0 user, as that may invalidate
2565 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, jump
))
2571 if (final_dest_bb
&& !moveall
)
2572 /* We haven't checked whether a partial move would be OK for the first
2573 move, so we have to fail this case. */
2579 if (currptr
[0] == move_upto
)
2581 for (ix
= 0; ix
< nedges
; ix
++)
2583 rtx_insn
*curr
= currptr
[ix
];
2585 curr
= NEXT_INSN (curr
);
2586 while (!NONDEBUG_INSN_P (curr
));
2591 /* If we can't currently move all of the identical insns, remember
2592 each insn after the range that we'll merge. */
2594 for (ix
= 0; ix
< nedges
; ix
++)
2596 rtx_insn
*curr
= currptr
[ix
];
2598 curr
= NEXT_INSN (curr
);
2599 while (!NONDEBUG_INSN_P (curr
));
2603 reorder_insns (headptr
[0], currptr
[0], PREV_INSN (move_before
));
2604 df_set_bb_dirty (EDGE_SUCC (bb
, 0)->dest
);
2605 if (final_dest_bb
!= NULL
)
2606 df_set_bb_dirty (final_dest_bb
);
2607 df_set_bb_dirty (bb
);
2608 for (ix
= 1; ix
< nedges
; ix
++)
2610 df_set_bb_dirty (EDGE_SUCC (bb
, ix
)->dest
);
2611 delete_insn_chain (headptr
[ix
], currptr
[ix
], false);
2615 if (jump
== move_before
)
2618 /* For the unmerged insns, try a different insertion point. */
2621 /* Don't try moving before a cc0 user, as that may invalidate
2623 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, jump
))
2626 for (ix
= 0; ix
< nedges
; ix
++)
2627 currptr
[ix
] = headptr
[ix
] = nextptr
[ix
];
2637 crossjumps_occurred
|= changed
;
2642 /* Return true if BB contains just bb note, or bb note followed
2643 by only DEBUG_INSNs. */
2646 trivially_empty_bb_p (basic_block bb
)
2648 rtx_insn
*insn
= BB_END (bb
);
2652 if (insn
== BB_HEAD (bb
))
2654 if (!DEBUG_INSN_P (insn
))
2656 insn
= PREV_INSN (insn
);
2660 /* Return true if BB contains just a return and possibly a USE of the
2661 return value. Fill in *RET and *USE with the return and use insns
2662 if any found, otherwise NULL. All CLOBBERs are ignored. */
2665 bb_is_just_return (basic_block bb
, rtx_insn
**ret
, rtx_insn
**use
)
2670 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
2673 FOR_BB_INSNS (bb
, insn
)
2674 if (NONDEBUG_INSN_P (insn
))
2676 rtx pat
= PATTERN (insn
);
2678 if (!*ret
&& ANY_RETURN_P (pat
))
2680 else if (!*ret
&& !*use
&& GET_CODE (pat
) == USE
2681 && REG_P (XEXP (pat
, 0))
2682 && REG_FUNCTION_VALUE_P (XEXP (pat
, 0)))
2684 else if (GET_CODE (pat
) != CLOBBER
)
2691 /* Do simple CFG optimizations - basic block merging, simplifying of jump
2692 instructions etc. Return nonzero if changes were made. */
2695 try_optimize_cfg (int mode
)
2697 bool changed_overall
= false;
2700 basic_block bb
, b
, next
;
2702 if (mode
& (CLEANUP_CROSSJUMP
| CLEANUP_THREADING
))
2705 crossjumps_occurred
= false;
2707 FOR_EACH_BB_FN (bb
, cfun
)
2708 update_forwarder_flag (bb
);
2710 if (! targetm
.cannot_modify_jumps_p ())
2713 /* Attempt to merge blocks as made possible by edge removal. If
2714 a block has only one successor, and the successor has only
2715 one predecessor, they may be combined. */
2718 block_was_dirty
= false;
2724 "\n\ntry_optimize_cfg iteration %i\n\n",
2727 for (b
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; b
2728 != EXIT_BLOCK_PTR_FOR_FN (cfun
);)
2732 bool changed_here
= false;
2734 /* Delete trivially dead basic blocks. This is either
2735 blocks with no predecessors, or empty blocks with no
2736 successors. However if the empty block with no
2737 successors is the successor of the ENTRY_BLOCK, it is
2738 kept. This ensures that the ENTRY_BLOCK will have a
2739 successor which is a precondition for many RTL
2740 passes. Empty blocks may result from expanding
2741 __builtin_unreachable (). */
2742 if (EDGE_COUNT (b
->preds
) == 0
2743 || (EDGE_COUNT (b
->succs
) == 0
2744 && trivially_empty_bb_p (b
)
2745 && single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->dest
2749 if (EDGE_COUNT (b
->preds
) > 0)
2754 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2757 && BARRIER_P (BB_FOOTER (b
)))
2758 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2759 if ((e
->flags
& EDGE_FALLTHRU
)
2760 && BB_FOOTER (e
->src
) == NULL
)
2764 BB_FOOTER (e
->src
) = BB_FOOTER (b
);
2765 BB_FOOTER (b
) = NULL
;
2770 BB_FOOTER (e
->src
) = emit_barrier ();
2777 rtx_insn
*last
= get_last_bb_insn (b
);
2778 if (last
&& BARRIER_P (last
))
2779 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2780 if ((e
->flags
& EDGE_FALLTHRU
))
2781 emit_barrier_after (BB_END (e
->src
));
2784 delete_basic_block (b
);
2786 /* Avoid trying to remove the exit block. */
2787 b
= (c
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) ? c
->next_bb
: c
);
2791 /* Remove code labels no longer used. */
2792 if (single_pred_p (b
)
2793 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2794 && !(single_pred_edge (b
)->flags
& EDGE_COMPLEX
)
2795 && LABEL_P (BB_HEAD (b
))
2796 && !LABEL_PRESERVE_P (BB_HEAD (b
))
2797 /* If the previous block ends with a branch to this
2798 block, we can't delete the label. Normally this
2799 is a condjump that is yet to be simplified, but
2800 if CASE_DROPS_THRU, this can be a tablejump with
2801 some element going to the same place as the
2802 default (fallthru). */
2803 && (single_pred (b
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2804 || !JUMP_P (BB_END (single_pred (b
)))
2805 || ! label_is_jump_target_p (BB_HEAD (b
),
2806 BB_END (single_pred (b
)))))
2808 delete_insn (BB_HEAD (b
));
2810 fprintf (dump_file
, "Deleted label in block %i.\n",
2814 /* If we fall through an empty block, we can remove it. */
2815 if (!(mode
& (CLEANUP_CFGLAYOUT
| CLEANUP_NO_INSN_DEL
))
2816 && single_pred_p (b
)
2817 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2818 && !LABEL_P (BB_HEAD (b
))
2819 && FORWARDER_BLOCK_P (b
)
2820 /* Note that forwarder_block_p true ensures that
2821 there is a successor for this block. */
2822 && (single_succ_edge (b
)->flags
& EDGE_FALLTHRU
)
2823 && n_basic_blocks_for_fn (cfun
) > NUM_FIXED_BLOCKS
+ 1)
2827 "Deleting fallthru block %i.\n",
2830 c
= ((b
->prev_bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
2831 ? b
->next_bb
: b
->prev_bb
);
2832 redirect_edge_succ_nodup (single_pred_edge (b
),
2834 delete_basic_block (b
);
2840 /* Merge B with its single successor, if any. */
2841 if (single_succ_p (b
)
2842 && (s
= single_succ_edge (b
))
2843 && !(s
->flags
& EDGE_COMPLEX
)
2844 && (c
= s
->dest
) != EXIT_BLOCK_PTR_FOR_FN (cfun
)
2845 && single_pred_p (c
)
2848 /* When not in cfg_layout mode use code aware of reordering
2849 INSN. This code possibly creates new basic blocks so it
2850 does not fit merge_blocks interface and is kept here in
2851 hope that it will become useless once more of compiler
2852 is transformed to use cfg_layout mode. */
2854 if ((mode
& CLEANUP_CFGLAYOUT
)
2855 && can_merge_blocks_p (b
, c
))
2857 merge_blocks (b
, c
);
2858 update_forwarder_flag (b
);
2859 changed_here
= true;
2861 else if (!(mode
& CLEANUP_CFGLAYOUT
)
2862 /* If the jump insn has side effects,
2863 we can't kill the edge. */
2864 && (!JUMP_P (BB_END (b
))
2865 || (reload_completed
2866 ? simplejump_p (BB_END (b
))
2867 : (onlyjump_p (BB_END (b
))
2868 && !tablejump_p (BB_END (b
),
2870 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
2873 changed_here
= true;
2877 /* Try to change a branch to a return to just that return. */
2878 rtx_insn
*ret
, *use
;
2879 if (single_succ_p (b
)
2880 && onlyjump_p (BB_END (b
))
2881 && bb_is_just_return (single_succ (b
), &ret
, &use
))
2883 if (redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (b
)),
2887 emit_insn_before (copy_insn (PATTERN (use
)),
2890 fprintf (dump_file
, "Changed jump %d->%d to return.\n",
2891 b
->index
, single_succ (b
)->index
);
2892 redirect_edge_succ (single_succ_edge (b
),
2893 EXIT_BLOCK_PTR_FOR_FN (cfun
));
2894 single_succ_edge (b
)->flags
&= ~EDGE_CROSSING
;
2895 changed_here
= true;
2899 /* Try to change a conditional branch to a return to the
2900 respective conditional return. */
2901 if (EDGE_COUNT (b
->succs
) == 2
2902 && any_condjump_p (BB_END (b
))
2903 && bb_is_just_return (BRANCH_EDGE (b
)->dest
, &ret
, &use
))
2905 if (redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (b
)),
2909 emit_insn_before (copy_insn (PATTERN (use
)),
2912 fprintf (dump_file
, "Changed conditional jump %d->%d "
2913 "to conditional return.\n",
2914 b
->index
, BRANCH_EDGE (b
)->dest
->index
);
2915 redirect_edge_succ (BRANCH_EDGE (b
),
2916 EXIT_BLOCK_PTR_FOR_FN (cfun
));
2917 BRANCH_EDGE (b
)->flags
&= ~EDGE_CROSSING
;
2918 changed_here
= true;
2922 /* Try to flip a conditional branch that falls through to
2923 a return so that it becomes a conditional return and a
2924 new jump to the original branch target. */
2925 if (EDGE_COUNT (b
->succs
) == 2
2926 && BRANCH_EDGE (b
)->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2927 && any_condjump_p (BB_END (b
))
2928 && bb_is_just_return (FALLTHRU_EDGE (b
)->dest
, &ret
, &use
))
2930 if (invert_jump (as_a
<rtx_jump_insn
*> (BB_END (b
)),
2931 JUMP_LABEL (BB_END (b
)), 0))
2933 basic_block new_ft
= BRANCH_EDGE (b
)->dest
;
2934 if (redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (b
)),
2938 emit_insn_before (copy_insn (PATTERN (use
)),
2941 fprintf (dump_file
, "Changed conditional jump "
2942 "%d->%d to conditional return, adding "
2943 "fall-through jump.\n",
2944 b
->index
, BRANCH_EDGE (b
)->dest
->index
);
2945 redirect_edge_succ (BRANCH_EDGE (b
),
2946 EXIT_BLOCK_PTR_FOR_FN (cfun
));
2947 BRANCH_EDGE (b
)->flags
&= ~EDGE_CROSSING
;
2948 std::swap (BRANCH_EDGE (b
)->probability
,
2949 FALLTHRU_EDGE (b
)->probability
);
2950 update_br_prob_note (b
);
2951 basic_block jb
= force_nonfallthru (FALLTHRU_EDGE (b
));
2952 notice_new_block (jb
);
2953 if (!redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (jb
)),
2954 block_label (new_ft
), 0))
2956 redirect_edge_succ (single_succ_edge (jb
), new_ft
);
2957 changed_here
= true;
2961 /* Invert the jump back to what it was. This should
2963 if (!invert_jump (as_a
<rtx_jump_insn
*> (BB_END (b
)),
2964 JUMP_LABEL (BB_END (b
)), 0))
2970 /* Simplify branch over branch. */
2971 if ((mode
& CLEANUP_EXPENSIVE
)
2972 && !(mode
& CLEANUP_CFGLAYOUT
)
2973 && try_simplify_condjump (b
))
2974 changed_here
= true;
2976 /* If B has a single outgoing edge, but uses a
2977 non-trivial jump instruction without side-effects, we
2978 can either delete the jump entirely, or replace it
2979 with a simple unconditional jump. */
2980 if (single_succ_p (b
)
2981 && single_succ (b
) != EXIT_BLOCK_PTR_FOR_FN (cfun
)
2982 && onlyjump_p (BB_END (b
))
2983 && !CROSSING_JUMP_P (BB_END (b
))
2984 && try_redirect_by_replacing_jump (single_succ_edge (b
),
2986 (mode
& CLEANUP_CFGLAYOUT
) != 0))
2988 update_forwarder_flag (b
);
2989 changed_here
= true;
2992 /* Simplify branch to branch. */
2993 if (try_forward_edges (mode
, b
))
2995 update_forwarder_flag (b
);
2996 changed_here
= true;
2999 /* Look for shared code between blocks. */
3000 if ((mode
& CLEANUP_CROSSJUMP
)
3001 && try_crossjump_bb (mode
, b
))
3002 changed_here
= true;
3004 if ((mode
& CLEANUP_CROSSJUMP
)
3005 /* This can lengthen register lifetimes. Do it only after
3008 && try_head_merge_bb (b
))
3009 changed_here
= true;
3011 /* Don't get confused by the index shift caused by
3019 if ((mode
& CLEANUP_CROSSJUMP
)
3020 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR_FOR_FN (cfun
)))
3023 if (block_was_dirty
)
3025 /* This should only be set by head-merging. */
3026 gcc_assert (mode
& CLEANUP_CROSSJUMP
);
3032 /* Edge forwarding in particular can cause hot blocks previously
3033 reached by both hot and cold blocks to become dominated only
3034 by cold blocks. This will cause the verification below to fail,
3035 and lead to now cold code in the hot section. This is not easy
3036 to detect and fix during edge forwarding, and in some cases
3037 is only visible after newly unreachable blocks are deleted,
3038 which will be done in fixup_partitions. */
3039 fixup_partitions ();
3040 checking_verify_flow_info ();
3043 changed_overall
|= changed
;
3049 FOR_ALL_BB_FN (b
, cfun
)
3050 b
->flags
&= ~(BB_FORWARDER_BLOCK
| BB_NONTHREADABLE_BLOCK
);
3052 return changed_overall
;
3055 /* Delete all unreachable basic blocks. */
3058 delete_unreachable_blocks (void)
3060 bool changed
= false;
3061 basic_block b
, prev_bb
;
3063 find_unreachable_blocks ();
3065 /* When we're in GIMPLE mode and there may be debug insns, we should
3066 delete blocks in reverse dominator order, so as to get a chance
3067 to substitute all released DEFs into debug stmts. If we don't
3068 have dominators information, walking blocks backward gets us a
3069 better chance of retaining most debug information than
3071 if (MAY_HAVE_DEBUG_INSNS
&& current_ir_type () == IR_GIMPLE
3072 && dom_info_available_p (CDI_DOMINATORS
))
3074 for (b
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
3075 b
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
); b
= prev_bb
)
3077 prev_bb
= b
->prev_bb
;
3079 if (!(b
->flags
& BB_REACHABLE
))
3081 /* Speed up the removal of blocks that don't dominate
3082 others. Walking backwards, this should be the common
3084 if (!first_dom_son (CDI_DOMINATORS
, b
))
3085 delete_basic_block (b
);
3089 = get_all_dominated_blocks (CDI_DOMINATORS
, b
);
3095 prev_bb
= b
->prev_bb
;
3097 gcc_assert (!(b
->flags
& BB_REACHABLE
));
3099 delete_basic_block (b
);
3111 for (b
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
3112 b
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
); b
= prev_bb
)
3114 prev_bb
= b
->prev_bb
;
3116 if (!(b
->flags
& BB_REACHABLE
))
3118 delete_basic_block (b
);
3125 tidy_fallthru_edges ();
3129 /* Delete any jump tables never referenced. We can't delete them at the
3130 time of removing tablejump insn as they are referenced by the preceding
3131 insns computing the destination, so we delay deleting and garbagecollect
3132 them once life information is computed. */
3134 delete_dead_jumptables (void)
3138 /* A dead jump table does not belong to any basic block. Scan insns
3139 between two adjacent basic blocks. */
3140 FOR_EACH_BB_FN (bb
, cfun
)
3142 rtx_insn
*insn
, *next
;
3144 for (insn
= NEXT_INSN (BB_END (bb
));
3145 insn
&& !NOTE_INSN_BASIC_BLOCK_P (insn
);
3148 next
= NEXT_INSN (insn
);
3150 && LABEL_NUSES (insn
) == LABEL_PRESERVE_P (insn
)
3151 && JUMP_TABLE_DATA_P (next
))
3153 rtx_insn
*label
= insn
, *jump
= next
;
3156 fprintf (dump_file
, "Dead jumptable %i removed\n",
3159 next
= NEXT_INSN (next
);
3161 delete_insn (label
);
3168 /* Tidy the CFG by deleting unreachable code and whatnot. */
3171 cleanup_cfg (int mode
)
3173 bool changed
= false;
3175 /* Set the cfglayout mode flag here. We could update all the callers
3176 but that is just inconvenient, especially given that we eventually
3177 want to have cfglayout mode as the default. */
3178 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
3179 mode
|= CLEANUP_CFGLAYOUT
;
3181 timevar_push (TV_CLEANUP_CFG
);
3182 if (delete_unreachable_blocks ())
3185 /* We've possibly created trivially dead code. Cleanup it right
3186 now to introduce more opportunities for try_optimize_cfg. */
3187 if (!(mode
& (CLEANUP_NO_INSN_DEL
))
3188 && !reload_completed
)
3189 delete_trivially_dead_insns (get_insns (), max_reg_num ());
3194 /* To tail-merge blocks ending in the same noreturn function (e.g.
3195 a call to abort) we have to insert fake edges to exit. Do this
3196 here once. The fake edges do not interfere with any other CFG
3198 if (mode
& CLEANUP_CROSSJUMP
)
3199 add_noreturn_fake_exit_edges ();
3201 if (!dbg_cnt (cfg_cleanup
))
3204 while (try_optimize_cfg (mode
))
3206 delete_unreachable_blocks (), changed
= true;
3207 if (!(mode
& CLEANUP_NO_INSN_DEL
))
3209 /* Try to remove some trivially dead insns when doing an expensive
3210 cleanup. But delete_trivially_dead_insns doesn't work after
3211 reload (it only handles pseudos) and run_fast_dce is too costly
3212 to run in every iteration.
3214 For effective cross jumping, we really want to run a fast DCE to
3215 clean up any dead conditions, or they get in the way of performing
3218 Other transformations in cleanup_cfg are not so sensitive to dead
3219 code, so delete_trivially_dead_insns or even doing nothing at all
3221 if ((mode
& CLEANUP_EXPENSIVE
) && !reload_completed
3222 && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
3224 if ((mode
& CLEANUP_CROSSJUMP
) && crossjumps_occurred
)
3231 if (mode
& CLEANUP_CROSSJUMP
)
3232 remove_fake_exit_edges ();
3234 /* Don't call delete_dead_jumptables in cfglayout mode, because
3235 that function assumes that jump tables are in the insns stream.
3236 But we also don't _have_ to delete dead jumptables in cfglayout
3237 mode because we shouldn't even be looking at things that are
3238 not in a basic block. Dead jumptables are cleaned up when
3239 going out of cfglayout mode. */
3240 if (!(mode
& CLEANUP_CFGLAYOUT
))
3241 delete_dead_jumptables ();
3243 /* ??? We probably do this way too often. */
3246 || (mode
& CLEANUP_CFG_CHANGED
)))
3248 timevar_push (TV_REPAIR_LOOPS
);
3249 /* The above doesn't preserve dominance info if available. */
3250 gcc_assert (!dom_info_available_p (CDI_DOMINATORS
));
3251 calculate_dominance_info (CDI_DOMINATORS
);
3252 fix_loop_structure (NULL
);
3253 free_dominance_info (CDI_DOMINATORS
);
3254 timevar_pop (TV_REPAIR_LOOPS
);
3257 timevar_pop (TV_CLEANUP_CFG
);
3264 const pass_data pass_data_jump
=
3266 RTL_PASS
, /* type */
3268 OPTGROUP_NONE
, /* optinfo_flags */
3269 TV_JUMP
, /* tv_id */
3270 0, /* properties_required */
3271 0, /* properties_provided */
3272 0, /* properties_destroyed */
3273 0, /* todo_flags_start */
3274 0, /* todo_flags_finish */
3277 class pass_jump
: public rtl_opt_pass
3280 pass_jump (gcc::context
*ctxt
)
3281 : rtl_opt_pass (pass_data_jump
, ctxt
)
3284 /* opt_pass methods: */
3285 virtual unsigned int execute (function
*);
3287 }; // class pass_jump
3290 pass_jump::execute (function
*)
3292 delete_trivially_dead_insns (get_insns (), max_reg_num ());
3294 dump_flow_info (dump_file
, dump_flags
);
3295 cleanup_cfg ((optimize
? CLEANUP_EXPENSIVE
: 0)
3296 | (flag_thread_jumps
? CLEANUP_THREADING
: 0));
3303 make_pass_jump (gcc::context
*ctxt
)
3305 return new pass_jump (ctxt
);
3310 const pass_data pass_data_jump2
=
3312 RTL_PASS
, /* type */
3314 OPTGROUP_NONE
, /* optinfo_flags */
3315 TV_JUMP
, /* tv_id */
3316 0, /* properties_required */
3317 0, /* properties_provided */
3318 0, /* properties_destroyed */
3319 0, /* todo_flags_start */
3320 0, /* todo_flags_finish */
3323 class pass_jump2
: public rtl_opt_pass
3326 pass_jump2 (gcc::context
*ctxt
)
3327 : rtl_opt_pass (pass_data_jump2
, ctxt
)
3330 /* opt_pass methods: */
3331 virtual unsigned int execute (function
*)
3333 cleanup_cfg (flag_crossjumping
? CLEANUP_CROSSJUMP
: 0);
3337 }; // class pass_jump2
3342 make_pass_jump2 (gcc::context
*ctxt
)
3344 return new pass_jump2 (ctxt
);