1 /* Control flow optimization code for GNU compiler.
2 Copyright (C) 1987-2019 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 for (ei
= ei_start (b
->succs
); (e
= ei_safe_edge (ei
)); )
399 basic_block target
, first
;
400 location_t goto_locus
;
402 bool threaded
= false;
403 int nthreaded_edges
= 0;
404 bool may_thread
= first_pass
|| (b
->flags
& BB_MODIFIED
) != 0;
405 bool new_target_threaded
= false;
407 /* Skip complex edges because we don't know how to update them.
409 Still handle fallthru edges, as we can succeed to forward fallthru
410 edge to the same place as the branch edge of conditional branch
411 and turn conditional branch to an unconditional branch. */
412 if (e
->flags
& EDGE_COMPLEX
)
418 target
= first
= e
->dest
;
419 counter
= NUM_FIXED_BLOCKS
;
420 goto_locus
= e
->goto_locus
;
422 while (counter
< n_basic_blocks_for_fn (cfun
))
424 basic_block new_target
= NULL
;
425 may_thread
|= (target
->flags
& BB_MODIFIED
) != 0;
427 if (FORWARDER_BLOCK_P (target
)
428 && single_succ (target
) != EXIT_BLOCK_PTR_FOR_FN (cfun
))
430 /* Bypass trivial infinite loops. */
431 new_target
= single_succ (target
);
432 if (target
== new_target
)
433 counter
= n_basic_blocks_for_fn (cfun
);
436 /* When not optimizing, ensure that edges or forwarder
437 blocks with different locus are not optimized out. */
438 location_t new_locus
= single_succ_edge (target
)->goto_locus
;
439 location_t locus
= goto_locus
;
441 if (LOCATION_LOCUS (new_locus
) != UNKNOWN_LOCATION
442 && LOCATION_LOCUS (locus
) != UNKNOWN_LOCATION
443 && new_locus
!= locus
)
447 if (LOCATION_LOCUS (new_locus
) != UNKNOWN_LOCATION
)
450 rtx_insn
*last
= BB_END (target
);
451 if (DEBUG_INSN_P (last
))
452 last
= prev_nondebug_insn (last
);
453 if (last
&& INSN_P (last
))
454 new_locus
= INSN_LOCATION (last
);
456 new_locus
= UNKNOWN_LOCATION
;
458 if (LOCATION_LOCUS (new_locus
) != UNKNOWN_LOCATION
459 && LOCATION_LOCUS (locus
) != UNKNOWN_LOCATION
460 && new_locus
!= locus
)
464 if (LOCATION_LOCUS (new_locus
) != UNKNOWN_LOCATION
)
473 /* Allow to thread only over one edge at time to simplify updating
475 else if ((mode
& CLEANUP_THREADING
) && may_thread
)
477 edge t
= thread_jump (e
, target
);
481 threaded_edges
= XNEWVEC (edge
,
482 n_basic_blocks_for_fn (cfun
));
487 /* Detect an infinite loop across blocks not
488 including the start block. */
489 for (i
= 0; i
< nthreaded_edges
; ++i
)
490 if (threaded_edges
[i
] == t
)
492 if (i
< nthreaded_edges
)
494 counter
= n_basic_blocks_for_fn (cfun
);
499 /* Detect an infinite loop across the start block. */
503 gcc_assert (nthreaded_edges
504 < (n_basic_blocks_for_fn (cfun
)
505 - NUM_FIXED_BLOCKS
));
506 threaded_edges
[nthreaded_edges
++] = t
;
508 new_target
= t
->dest
;
509 new_target_threaded
= true;
517 /* Do not turn non-crossing jump to crossing. Depending on target
518 it may require different instruction pattern. */
519 if ((e
->flags
& EDGE_CROSSING
)
520 || BB_PARTITION (first
) == BB_PARTITION (new_target
))
523 threaded
|= new_target_threaded
;
527 if (counter
>= n_basic_blocks_for_fn (cfun
))
530 fprintf (dump_file
, "Infinite loop in BB %i.\n",
533 else if (target
== first
)
534 ; /* We didn't do anything. */
537 /* Save the values now, as the edge may get removed. */
538 profile_count edge_count
= e
->count ();
541 e
->goto_locus
= goto_locus
;
543 /* Don't force if target is exit block. */
544 if (threaded
&& target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
546 notice_new_block (redirect_edge_and_branch_force (e
, target
));
548 fprintf (dump_file
, "Conditionals threaded.\n");
550 else if (!redirect_edge_and_branch (e
, target
))
554 "Forwarding edge %i->%i to %i failed.\n",
555 b
->index
, e
->dest
->index
, target
->index
);
560 /* We successfully forwarded the edge. Now update profile
561 data: for each edge we traversed in the chain, remove
562 the original edge's execution count. */
567 if (!single_succ_p (first
))
569 gcc_assert (n
< nthreaded_edges
);
570 t
= threaded_edges
[n
++];
571 gcc_assert (t
->src
== first
);
572 update_bb_profile_for_threading (first
, edge_count
, t
);
573 update_br_prob_note (first
);
577 first
->count
-= edge_count
;
578 /* It is possible that as the result of
579 threading we've removed edge as it is
580 threaded to the fallthru edge. Avoid
581 getting out of sync. */
582 if (n
< nthreaded_edges
583 && first
== threaded_edges
[n
]->src
)
585 t
= single_succ_edge (first
);
590 while (first
!= target
);
598 free (threaded_edges
);
603 /* Blocks A and B are to be merged into a single block. A has no incoming
604 fallthru edge, so it can be moved before B without adding or modifying
605 any jumps (aside from the jump from A to B). */
608 merge_blocks_move_predecessor_nojumps (basic_block a
, basic_block b
)
612 /* If we are partitioning hot/cold basic blocks, we don't want to
613 mess up unconditional or indirect jumps that cross between hot
616 Basic block partitioning may result in some jumps that appear to
617 be optimizable (or blocks that appear to be mergeable), but which really
618 must be left untouched (they are required to make it safely across
619 partition boundaries). See the comments at the top of
620 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
622 if (BB_PARTITION (a
) != BB_PARTITION (b
))
625 barrier
= next_nonnote_insn (BB_END (a
));
626 gcc_assert (BARRIER_P (barrier
));
627 delete_insn (barrier
);
629 /* Scramble the insn chain. */
630 if (BB_END (a
) != PREV_INSN (BB_HEAD (b
)))
631 reorder_insns_nobb (BB_HEAD (a
), BB_END (a
), PREV_INSN (BB_HEAD (b
)));
635 fprintf (dump_file
, "Moved block %d before %d and merged.\n",
638 /* Swap the records for the two blocks around. */
641 link_block (a
, b
->prev_bb
);
643 /* Now blocks A and B are contiguous. Merge them. */
647 /* Blocks A and B are to be merged into a single block. B has no outgoing
648 fallthru edge, so it can be moved after A without adding or modifying
649 any jumps (aside from the jump from A to B). */
652 merge_blocks_move_successor_nojumps (basic_block a
, basic_block b
)
654 rtx_insn
*barrier
, *real_b_end
;
656 rtx_jump_table_data
*table
;
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 real_b_end
= BB_END (b
);
673 /* If there is a jump table following block B temporarily add the jump table
674 to block B so that it will also be moved to the correct location. */
675 if (tablejump_p (BB_END (b
), &label
, &table
)
676 && prev_active_insn (label
) == BB_END (b
))
681 /* There had better have been a barrier there. Delete it. */
682 barrier
= NEXT_INSN (BB_END (b
));
683 if (barrier
&& BARRIER_P (barrier
))
684 delete_insn (barrier
);
687 /* Scramble the insn chain. */
688 reorder_insns_nobb (BB_HEAD (b
), BB_END (b
), BB_END (a
));
690 /* Restore the real end of b. */
691 BB_END (b
) = real_b_end
;
694 fprintf (dump_file
, "Moved block %d after %d and merged.\n",
697 /* Now blocks A and B are contiguous. Merge them. */
701 /* Attempt to merge basic blocks that are potentially non-adjacent.
702 Return NULL iff the attempt failed, otherwise return basic block
703 where cleanup_cfg should continue. Because the merging commonly
704 moves basic block away or introduces another optimization
705 possibility, return basic block just before B so cleanup_cfg don't
708 It may be good idea to return basic block before C in the case
709 C has been moved after B and originally appeared earlier in the
710 insn sequence, but we have no information available about the
711 relative ordering of these two. Hopefully it is not too common. */
714 merge_blocks_move (edge e
, basic_block b
, basic_block c
, int mode
)
718 /* If we are partitioning hot/cold basic blocks, we don't want to
719 mess up unconditional or indirect jumps that cross between hot
722 Basic block partitioning may result in some jumps that appear to
723 be optimizable (or blocks that appear to be mergeable), but which really
724 must be left untouched (they are required to make it safely across
725 partition boundaries). See the comments at the top of
726 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
728 if (BB_PARTITION (b
) != BB_PARTITION (c
))
731 /* If B has a fallthru edge to C, no need to move anything. */
732 if (e
->flags
& EDGE_FALLTHRU
)
734 int b_index
= b
->index
, c_index
= c
->index
;
736 /* Protect the loop latches. */
737 if (current_loops
&& c
->loop_father
->latch
== c
)
741 update_forwarder_flag (b
);
744 fprintf (dump_file
, "Merged %d and %d without moving.\n",
747 return b
->prev_bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) ? b
: b
->prev_bb
;
750 /* Otherwise we will need to move code around. Do that only if expensive
751 transformations are allowed. */
752 else if (mode
& CLEANUP_EXPENSIVE
)
754 edge tmp_edge
, b_fallthru_edge
;
755 bool c_has_outgoing_fallthru
;
756 bool b_has_incoming_fallthru
;
758 /* Avoid overactive code motion, as the forwarder blocks should be
759 eliminated by edge redirection instead. One exception might have
760 been if B is a forwarder block and C has no fallthru edge, but
761 that should be cleaned up by bb-reorder instead. */
762 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
765 /* We must make sure to not munge nesting of lexical blocks,
766 and loop notes. This is done by squeezing out all the notes
767 and leaving them there to lie. Not ideal, but functional. */
769 tmp_edge
= find_fallthru_edge (c
->succs
);
770 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
772 tmp_edge
= find_fallthru_edge (b
->preds
);
773 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
774 b_fallthru_edge
= tmp_edge
;
777 next
= next
->prev_bb
;
779 /* Otherwise, we're going to try to move C after B. If C does
780 not have an outgoing fallthru, then it can be moved
781 immediately after B without introducing or modifying jumps. */
782 if (! c_has_outgoing_fallthru
)
784 merge_blocks_move_successor_nojumps (b
, c
);
785 return next
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) ? next
->next_bb
: next
;
788 /* If B does not have an incoming fallthru, then it can be moved
789 immediately before C without introducing or modifying jumps.
790 C cannot be the first block, so we do not have to worry about
791 accessing a non-existent block. */
793 if (b_has_incoming_fallthru
)
797 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
799 bb
= force_nonfallthru (b_fallthru_edge
);
801 notice_new_block (bb
);
804 merge_blocks_move_predecessor_nojumps (b
, c
);
805 return next
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) ? next
->next_bb
: next
;
812 /* Removes the memory attributes of MEM expression
813 if they are not equal. */
816 merge_memattrs (rtx x
, rtx y
)
825 if (x
== 0 || y
== 0)
830 if (code
!= GET_CODE (y
))
833 if (GET_MODE (x
) != GET_MODE (y
))
836 if (code
== MEM
&& !mem_attrs_eq_p (MEM_ATTRS (x
), MEM_ATTRS (y
)))
840 else if (! MEM_ATTRS (y
))
844 if (MEM_ALIAS_SET (x
) != MEM_ALIAS_SET (y
))
846 set_mem_alias_set (x
, 0);
847 set_mem_alias_set (y
, 0);
850 if (! mem_expr_equal_p (MEM_EXPR (x
), MEM_EXPR (y
)))
854 clear_mem_offset (x
);
855 clear_mem_offset (y
);
857 else if (MEM_OFFSET_KNOWN_P (x
) != MEM_OFFSET_KNOWN_P (y
)
858 || (MEM_OFFSET_KNOWN_P (x
)
859 && maybe_ne (MEM_OFFSET (x
), MEM_OFFSET (y
))))
861 clear_mem_offset (x
);
862 clear_mem_offset (y
);
865 if (!MEM_SIZE_KNOWN_P (x
))
867 else if (!MEM_SIZE_KNOWN_P (y
))
869 else if (known_le (MEM_SIZE (x
), MEM_SIZE (y
)))
870 set_mem_size (x
, MEM_SIZE (y
));
871 else if (known_le (MEM_SIZE (y
), MEM_SIZE (x
)))
872 set_mem_size (y
, MEM_SIZE (x
));
875 /* The sizes aren't ordered, so we can't merge them. */
880 set_mem_align (x
, MIN (MEM_ALIGN (x
), MEM_ALIGN (y
)));
881 set_mem_align (y
, MEM_ALIGN (x
));
886 if (MEM_READONLY_P (x
) != MEM_READONLY_P (y
))
888 MEM_READONLY_P (x
) = 0;
889 MEM_READONLY_P (y
) = 0;
891 if (MEM_NOTRAP_P (x
) != MEM_NOTRAP_P (y
))
893 MEM_NOTRAP_P (x
) = 0;
894 MEM_NOTRAP_P (y
) = 0;
896 if (MEM_VOLATILE_P (x
) != MEM_VOLATILE_P (y
))
898 MEM_VOLATILE_P (x
) = 1;
899 MEM_VOLATILE_P (y
) = 1;
903 fmt
= GET_RTX_FORMAT (code
);
904 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
909 /* Two vectors must have the same length. */
910 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
913 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
914 merge_memattrs (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
));
919 merge_memattrs (XEXP (x
, i
), XEXP (y
, i
));
926 /* Checks if patterns P1 and P2 are equivalent, apart from the possibly
927 different single sets S1 and S2. */
930 equal_different_set_p (rtx p1
, rtx s1
, rtx p2
, rtx s2
)
935 if (p1
== s1
&& p2
== s2
)
938 if (GET_CODE (p1
) != PARALLEL
|| GET_CODE (p2
) != PARALLEL
)
941 if (XVECLEN (p1
, 0) != XVECLEN (p2
, 0))
944 for (i
= 0; i
< XVECLEN (p1
, 0); i
++)
946 e1
= XVECEXP (p1
, 0, i
);
947 e2
= XVECEXP (p2
, 0, i
);
948 if (e1
== s1
&& e2
== s2
)
951 ? rtx_renumbered_equal_p (e1
, e2
) : rtx_equal_p (e1
, e2
))
961 /* NOTE1 is the REG_EQUAL note, if any, attached to an insn
962 that is a single_set with a SET_SRC of SRC1. Similarly
965 So effectively NOTE1/NOTE2 are an alternate form of
966 SRC1/SRC2 respectively.
968 Return nonzero if SRC1 or NOTE1 has the same constant
969 integer value as SRC2 or NOTE2. Else return zero. */
971 values_equal_p (rtx note1
, rtx note2
, rtx src1
, rtx src2
)
975 && CONST_INT_P (XEXP (note1
, 0))
976 && rtx_equal_p (XEXP (note1
, 0), XEXP (note2
, 0)))
981 && CONST_INT_P (src1
)
982 && CONST_INT_P (src2
)
983 && rtx_equal_p (src1
, src2
))
987 && CONST_INT_P (src2
)
988 && rtx_equal_p (XEXP (note1
, 0), src2
))
992 && CONST_INT_P (src1
)
993 && rtx_equal_p (XEXP (note2
, 0), src1
))
999 /* Examine register notes on I1 and I2 and return:
1000 - dir_forward if I1 can be replaced by I2, or
1001 - dir_backward if I2 can be replaced by I1, or
1002 - dir_both if both are the case. */
1004 static enum replace_direction
1005 can_replace_by (rtx_insn
*i1
, rtx_insn
*i2
)
1007 rtx s1
, s2
, d1
, d2
, src1
, src2
, note1
, note2
;
1010 /* Check for 2 sets. */
1011 s1
= single_set (i1
);
1012 s2
= single_set (i2
);
1013 if (s1
== NULL_RTX
|| s2
== NULL_RTX
)
1016 /* Check that the 2 sets set the same dest. */
1019 if (!(reload_completed
1020 ? rtx_renumbered_equal_p (d1
, d2
) : rtx_equal_p (d1
, d2
)))
1023 /* Find identical req_equiv or reg_equal note, which implies that the 2 sets
1024 set dest to the same value. */
1025 note1
= find_reg_equal_equiv_note (i1
);
1026 note2
= find_reg_equal_equiv_note (i2
);
1028 src1
= SET_SRC (s1
);
1029 src2
= SET_SRC (s2
);
1031 if (!values_equal_p (note1
, note2
, src1
, src2
))
1034 if (!equal_different_set_p (PATTERN (i1
), s1
, PATTERN (i2
), s2
))
1037 /* Although the 2 sets set dest to the same value, we cannot replace
1038 (set (dest) (const_int))
1041 because we don't know if the reg is live and has the same value at the
1042 location of replacement. */
1043 c1
= CONST_INT_P (src1
);
1044 c2
= CONST_INT_P (src2
);
1050 return dir_backward
;
1055 /* Merges directions A and B. */
1057 static enum replace_direction
1058 merge_dir (enum replace_direction a
, enum replace_direction b
)
1060 /* Implements the following table:
1079 /* Array of flags indexed by reg note kind, true if the given
1080 reg note is CFA related. */
1081 static const bool reg_note_cfa_p
[] = {
1083 #define DEF_REG_NOTE(NAME) false,
1084 #define REG_CFA_NOTE(NAME) true,
1085 #include "reg-notes.def"
1091 /* Return true if I1 and I2 have identical CFA notes (the same order
1092 and equivalent content). */
1095 insns_have_identical_cfa_notes (rtx_insn
*i1
, rtx_insn
*i2
)
1098 for (n1
= REG_NOTES (i1
), n2
= REG_NOTES (i2
); ;
1099 n1
= XEXP (n1
, 1), n2
= XEXP (n2
, 1))
1101 /* Skip over reg notes not related to CFI information. */
1102 while (n1
&& !reg_note_cfa_p
[REG_NOTE_KIND (n1
)])
1104 while (n2
&& !reg_note_cfa_p
[REG_NOTE_KIND (n2
)])
1106 if (n1
== NULL_RTX
&& n2
== NULL_RTX
)
1108 if (n1
== NULL_RTX
|| n2
== NULL_RTX
)
1110 if (XEXP (n1
, 0) == XEXP (n2
, 0))
1112 else if (XEXP (n1
, 0) == NULL_RTX
|| XEXP (n2
, 0) == NULL_RTX
)
1114 else if (!(reload_completed
1115 ? rtx_renumbered_equal_p (XEXP (n1
, 0), XEXP (n2
, 0))
1116 : rtx_equal_p (XEXP (n1
, 0), XEXP (n2
, 0))))
1121 /* Examine I1 and I2 and return:
1122 - dir_forward if I1 can be replaced by I2, or
1123 - dir_backward if I2 can be replaced by I1, or
1124 - dir_both if both are the case. */
1126 static enum replace_direction
1127 old_insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx_insn
*i1
, rtx_insn
*i2
)
1131 /* Verify that I1 and I2 are equivalent. */
1132 if (GET_CODE (i1
) != GET_CODE (i2
))
1135 /* __builtin_unreachable() may lead to empty blocks (ending with
1136 NOTE_INSN_BASIC_BLOCK). They may be crossjumped. */
1137 if (NOTE_INSN_BASIC_BLOCK_P (i1
) && NOTE_INSN_BASIC_BLOCK_P (i2
))
1140 /* ??? Do not allow cross-jumping between different stack levels. */
1141 p1
= find_reg_note (i1
, REG_ARGS_SIZE
, NULL
);
1142 p2
= find_reg_note (i2
, REG_ARGS_SIZE
, NULL
);
1147 if (!rtx_equal_p (p1
, p2
))
1150 /* ??? Worse, this adjustment had better be constant lest we
1151 have differing incoming stack levels. */
1152 if (!frame_pointer_needed
1153 && known_eq (find_args_size_adjust (i1
), HOST_WIDE_INT_MIN
))
1159 /* Do not allow cross-jumping between frame related insns and other
1161 if (RTX_FRAME_RELATED_P (i1
) != RTX_FRAME_RELATED_P (i2
))
1167 if (GET_CODE (p1
) != GET_CODE (p2
))
1170 /* If this is a CALL_INSN, compare register usage information.
1171 If we don't check this on stack register machines, the two
1172 CALL_INSNs might be merged leaving reg-stack.c with mismatching
1173 numbers of stack registers in the same basic block.
1174 If we don't check this on machines with delay slots, a delay slot may
1175 be filled that clobbers a parameter expected by the subroutine.
1177 ??? We take the simple route for now and assume that if they're
1178 equal, they were constructed identically.
1180 Also check for identical exception regions. */
1184 /* Ensure the same EH region. */
1185 rtx n1
= find_reg_note (i1
, REG_EH_REGION
, 0);
1186 rtx n2
= find_reg_note (i2
, REG_EH_REGION
, 0);
1191 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1194 if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
1195 CALL_INSN_FUNCTION_USAGE (i2
))
1196 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
))
1199 /* For address sanitizer, never crossjump __asan_report_* builtins,
1200 otherwise errors might be reported on incorrect lines. */
1201 if (flag_sanitize
& SANITIZE_ADDRESS
)
1203 rtx call
= get_call_rtx_from (i1
);
1204 if (call
&& GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
1206 rtx symbol
= XEXP (XEXP (call
, 0), 0);
1207 if (SYMBOL_REF_DECL (symbol
)
1208 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
1210 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
1212 && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
))
1213 >= BUILT_IN_ASAN_REPORT_LOAD1
1214 && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
))
1215 <= BUILT_IN_ASAN_STOREN
)
1222 /* If both i1 and i2 are frame related, verify all the CFA notes
1223 in the same order and with the same content. */
1224 if (RTX_FRAME_RELATED_P (i1
) && !insns_have_identical_cfa_notes (i1
, i2
))
1228 /* If cross_jump_death_matters is not 0, the insn's mode
1229 indicates whether or not the insn contains any stack-like
1232 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
1234 /* If register stack conversion has already been done, then
1235 death notes must also be compared before it is certain that
1236 the two instruction streams match. */
1239 HARD_REG_SET i1_regset
, i2_regset
;
1241 CLEAR_HARD_REG_SET (i1_regset
);
1242 CLEAR_HARD_REG_SET (i2_regset
);
1244 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
1245 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1246 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
1248 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
1249 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1250 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
1252 if (!hard_reg_set_equal_p (i1_regset
, i2_regset
))
1257 if (reload_completed
1258 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
1261 return can_replace_by (i1
, i2
);
1264 /* When comparing insns I1 and I2 in flow_find_cross_jump or
1265 flow_find_head_matching_sequence, ensure the notes match. */
1268 merge_notes (rtx_insn
*i1
, rtx_insn
*i2
)
1270 /* If the merged insns have different REG_EQUAL notes, then
1272 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1273 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1275 if (equiv1
&& !equiv2
)
1276 remove_note (i1
, equiv1
);
1277 else if (!equiv1
&& equiv2
)
1278 remove_note (i2
, equiv2
);
1279 else if (equiv1
&& equiv2
1280 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1282 remove_note (i1
, equiv1
);
1283 remove_note (i2
, equiv2
);
1287 /* Walks from I1 in BB1 backward till the next non-debug insn, and returns the
1288 resulting insn in I1, and the corresponding bb in BB1. At the head of a
1289 bb, if there is a predecessor bb that reaches this bb via fallthru, and
1290 FOLLOW_FALLTHRU, walks further in the predecessor bb and registers this in
1291 DID_FALLTHRU. Otherwise, stops at the head of the bb. */
1294 walk_to_nondebug_insn (rtx_insn
**i1
, basic_block
*bb1
, bool follow_fallthru
,
1299 *did_fallthru
= false;
1302 while (!NONDEBUG_INSN_P (*i1
))
1304 if (*i1
!= BB_HEAD (*bb1
))
1306 *i1
= PREV_INSN (*i1
);
1310 if (!follow_fallthru
)
1313 fallthru
= find_fallthru_edge ((*bb1
)->preds
);
1314 if (!fallthru
|| fallthru
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1315 || !single_succ_p (fallthru
->src
))
1318 *bb1
= fallthru
->src
;
1319 *i1
= BB_END (*bb1
);
1320 *did_fallthru
= true;
1324 /* Look through the insns at the end of BB1 and BB2 and find the longest
1325 sequence that are either equivalent, or allow forward or backward
1326 replacement. Store the first insns for that sequence in *F1 and *F2 and
1327 return the sequence length.
1329 DIR_P indicates the allowed replacement direction on function entry, and
1330 the actual replacement direction on function exit. If NULL, only equivalent
1331 sequences are allowed.
1333 To simplify callers of this function, if the blocks match exactly,
1334 store the head of the blocks in *F1 and *F2. */
1337 flow_find_cross_jump (basic_block bb1
, basic_block bb2
, rtx_insn
**f1
,
1338 rtx_insn
**f2
, enum replace_direction
*dir_p
)
1340 rtx_insn
*i1
, *i2
, *last1
, *last2
, *afterlast1
, *afterlast2
;
1342 enum replace_direction dir
, last_dir
, afterlast_dir
;
1343 bool follow_fallthru
, did_fallthru
;
1349 afterlast_dir
= dir
;
1350 last_dir
= afterlast_dir
;
1352 /* Skip simple jumps at the end of the blocks. Complex jumps still
1353 need to be compared for equivalence, which we'll do below. */
1356 last1
= afterlast1
= last2
= afterlast2
= NULL
;
1358 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1361 i1
= PREV_INSN (i1
);
1366 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1369 /* Count everything except for unconditional jump as insn.
1370 Don't count any jumps if dir_p is NULL. */
1371 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
&& dir_p
)
1373 i2
= PREV_INSN (i2
);
1378 /* In the following example, we can replace all jumps to C by jumps to A.
1380 This removes 4 duplicate insns.
1381 [bb A] insn1 [bb C] insn1
1387 We could also replace all jumps to A by jumps to C, but that leaves B
1388 alive, and removes only 2 duplicate insns. In a subsequent crossjump
1389 step, all jumps to B would be replaced with jumps to the middle of C,
1390 achieving the same result with more effort.
1391 So we allow only the first possibility, which means that we don't allow
1392 fallthru in the block that's being replaced. */
1394 follow_fallthru
= dir_p
&& dir
!= dir_forward
;
1395 walk_to_nondebug_insn (&i1
, &bb1
, follow_fallthru
, &did_fallthru
);
1399 follow_fallthru
= dir_p
&& dir
!= dir_backward
;
1400 walk_to_nondebug_insn (&i2
, &bb2
, follow_fallthru
, &did_fallthru
);
1404 if (i1
== BB_HEAD (bb1
) || i2
== BB_HEAD (bb2
))
1407 /* Do not turn corssing edge to non-crossing or vice versa after
1409 if (BB_PARTITION (BLOCK_FOR_INSN (i1
))
1410 != BB_PARTITION (BLOCK_FOR_INSN (i2
))
1411 && reload_completed
)
1414 dir
= merge_dir (dir
, old_insns_match_p (0, i1
, i2
));
1415 if (dir
== dir_none
|| (!dir_p
&& dir
!= dir_both
))
1418 merge_memattrs (i1
, i2
);
1420 /* Don't begin a cross-jump with a NOTE insn. */
1423 merge_notes (i1
, i2
);
1425 afterlast1
= last1
, afterlast2
= last2
;
1426 last1
= i1
, last2
= i2
;
1427 afterlast_dir
= last_dir
;
1429 if (active_insn_p (i1
))
1433 i1
= PREV_INSN (i1
);
1434 i2
= PREV_INSN (i2
);
1437 /* Don't allow the insn after a compare to be shared by
1438 cross-jumping unless the compare is also shared. */
1439 if (HAVE_cc0
&& ninsns
&& reg_mentioned_p (cc0_rtx
, last1
)
1440 && ! sets_cc0_p (last1
))
1441 last1
= afterlast1
, last2
= afterlast2
, last_dir
= afterlast_dir
, ninsns
--;
1443 /* Include preceding notes and labels in the cross-jump. One,
1444 this may bring us to the head of the blocks as requested above.
1445 Two, it keeps line number notes as matched as may be. */
1448 bb1
= BLOCK_FOR_INSN (last1
);
1449 while (last1
!= BB_HEAD (bb1
) && !NONDEBUG_INSN_P (PREV_INSN (last1
)))
1450 last1
= PREV_INSN (last1
);
1452 if (last1
!= BB_HEAD (bb1
) && LABEL_P (PREV_INSN (last1
)))
1453 last1
= PREV_INSN (last1
);
1455 bb2
= BLOCK_FOR_INSN (last2
);
1456 while (last2
!= BB_HEAD (bb2
) && !NONDEBUG_INSN_P (PREV_INSN (last2
)))
1457 last2
= PREV_INSN (last2
);
1459 if (last2
!= BB_HEAD (bb2
) && LABEL_P (PREV_INSN (last2
)))
1460 last2
= PREV_INSN (last2
);
1471 /* Like flow_find_cross_jump, except start looking for a matching sequence from
1472 the head of the two blocks. Do not include jumps at the end.
1473 If STOP_AFTER is nonzero, stop after finding that many matching
1474 instructions. If STOP_AFTER is zero, count all INSN_P insns, if it is
1475 non-zero, only count active insns. */
1478 flow_find_head_matching_sequence (basic_block bb1
, basic_block bb2
, rtx_insn
**f1
,
1479 rtx_insn
**f2
, int stop_after
)
1481 rtx_insn
*i1
, *i2
, *last1
, *last2
, *beforelast1
, *beforelast2
;
1485 int nehedges1
= 0, nehedges2
= 0;
1487 FOR_EACH_EDGE (e
, ei
, bb1
->succs
)
1488 if (e
->flags
& EDGE_EH
)
1490 FOR_EACH_EDGE (e
, ei
, bb2
->succs
)
1491 if (e
->flags
& EDGE_EH
)
1496 last1
= beforelast1
= last2
= beforelast2
= NULL
;
1500 /* Ignore notes, except NOTE_INSN_EPILOGUE_BEG. */
1501 while (!NONDEBUG_INSN_P (i1
) && i1
!= BB_END (bb1
))
1503 if (NOTE_P (i1
) && NOTE_KIND (i1
) == NOTE_INSN_EPILOGUE_BEG
)
1505 i1
= NEXT_INSN (i1
);
1508 while (!NONDEBUG_INSN_P (i2
) && i2
!= BB_END (bb2
))
1510 if (NOTE_P (i2
) && NOTE_KIND (i2
) == NOTE_INSN_EPILOGUE_BEG
)
1512 i2
= NEXT_INSN (i2
);
1515 if ((i1
== BB_END (bb1
) && !NONDEBUG_INSN_P (i1
))
1516 || (i2
== BB_END (bb2
) && !NONDEBUG_INSN_P (i2
)))
1519 if (NOTE_P (i1
) || NOTE_P (i2
)
1520 || JUMP_P (i1
) || JUMP_P (i2
))
1523 /* A sanity check to make sure we're not merging insns with different
1524 effects on EH. If only one of them ends a basic block, it shouldn't
1525 have an EH edge; if both end a basic block, there should be the same
1526 number of EH edges. */
1527 if ((i1
== BB_END (bb1
) && i2
!= BB_END (bb2
)
1529 || (i2
== BB_END (bb2
) && i1
!= BB_END (bb1
)
1531 || (i1
== BB_END (bb1
) && i2
== BB_END (bb2
)
1532 && nehedges1
!= nehedges2
))
1535 if (old_insns_match_p (0, i1
, i2
) != dir_both
)
1538 merge_memattrs (i1
, i2
);
1540 /* Don't begin a cross-jump with a NOTE insn. */
1543 merge_notes (i1
, i2
);
1545 beforelast1
= last1
, beforelast2
= last2
;
1546 last1
= i1
, last2
= i2
;
1547 if (!stop_after
|| active_insn_p (i1
))
1551 if (i1
== BB_END (bb1
) || i2
== BB_END (bb2
)
1552 || (stop_after
> 0 && ninsns
== stop_after
))
1555 i1
= NEXT_INSN (i1
);
1556 i2
= NEXT_INSN (i2
);
1559 /* Don't allow a compare to be shared by cross-jumping unless the insn
1560 after the compare is also shared. */
1561 if (HAVE_cc0
&& ninsns
&& reg_mentioned_p (cc0_rtx
, last1
)
1562 && sets_cc0_p (last1
))
1563 last1
= beforelast1
, last2
= beforelast2
, ninsns
--;
1574 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1575 the branch instruction. This means that if we commonize the control
1576 flow before end of the basic block, the semantic remains unchanged.
1578 We may assume that there exists one edge with a common destination. */
1581 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1583 int nehedges1
= 0, nehedges2
= 0;
1584 edge fallthru1
= 0, fallthru2
= 0;
1588 /* If we performed shrink-wrapping, edges to the exit block can
1589 only be distinguished for JUMP_INSNs. The two paths may differ in
1590 whether they went through the prologue. Sibcalls are fine, we know
1591 that we either didn't need or inserted an epilogue before them. */
1592 if (crtl
->shrink_wrapped
1593 && single_succ_p (bb1
)
1594 && single_succ (bb1
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
1595 && (!JUMP_P (BB_END (bb1
))
1596 /* Punt if the only successor is a fake edge to exit, the jump
1597 must be some weird one. */
1598 || (single_succ_edge (bb1
)->flags
& EDGE_FAKE
) != 0)
1599 && !(CALL_P (BB_END (bb1
)) && SIBLING_CALL_P (BB_END (bb1
))))
1602 /* If BB1 has only one successor, we may be looking at either an
1603 unconditional jump, or a fake edge to exit. */
1604 if (single_succ_p (bb1
)
1605 && (single_succ_edge (bb1
)->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1606 && (!JUMP_P (BB_END (bb1
)) || simplejump_p (BB_END (bb1
))))
1607 return (single_succ_p (bb2
)
1608 && (single_succ_edge (bb2
)->flags
1609 & (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1610 && (!JUMP_P (BB_END (bb2
)) || simplejump_p (BB_END (bb2
))));
1612 /* Match conditional jumps - this may get tricky when fallthru and branch
1613 edges are crossed. */
1614 if (EDGE_COUNT (bb1
->succs
) == 2
1615 && any_condjump_p (BB_END (bb1
))
1616 && onlyjump_p (BB_END (bb1
)))
1618 edge b1
, f1
, b2
, f2
;
1619 bool reverse
, match
;
1620 rtx set1
, set2
, cond1
, cond2
;
1621 enum rtx_code code1
, code2
;
1623 if (EDGE_COUNT (bb2
->succs
) != 2
1624 || !any_condjump_p (BB_END (bb2
))
1625 || !onlyjump_p (BB_END (bb2
)))
1628 b1
= BRANCH_EDGE (bb1
);
1629 b2
= BRANCH_EDGE (bb2
);
1630 f1
= FALLTHRU_EDGE (bb1
);
1631 f2
= FALLTHRU_EDGE (bb2
);
1633 /* Get around possible forwarders on fallthru edges. Other cases
1634 should be optimized out already. */
1635 if (FORWARDER_BLOCK_P (f1
->dest
))
1636 f1
= single_succ_edge (f1
->dest
);
1638 if (FORWARDER_BLOCK_P (f2
->dest
))
1639 f2
= single_succ_edge (f2
->dest
);
1641 /* To simplify use of this function, return false if there are
1642 unneeded forwarder blocks. These will get eliminated later
1643 during cleanup_cfg. */
1644 if (FORWARDER_BLOCK_P (f1
->dest
)
1645 || FORWARDER_BLOCK_P (f2
->dest
)
1646 || FORWARDER_BLOCK_P (b1
->dest
)
1647 || FORWARDER_BLOCK_P (b2
->dest
))
1650 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1652 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1657 set1
= pc_set (BB_END (bb1
));
1658 set2
= pc_set (BB_END (bb2
));
1659 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1660 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1663 cond1
= XEXP (SET_SRC (set1
), 0);
1664 cond2
= XEXP (SET_SRC (set2
), 0);
1665 code1
= GET_CODE (cond1
);
1667 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
1669 code2
= GET_CODE (cond2
);
1671 if (code2
== UNKNOWN
)
1674 /* Verify codes and operands match. */
1675 match
= ((code1
== code2
1676 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1677 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1678 || (code1
== swap_condition (code2
)
1679 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1681 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1684 /* If we return true, we will join the blocks. Which means that
1685 we will only have one branch prediction bit to work with. Thus
1686 we require the existing branches to have probabilities that are
1689 && optimize_bb_for_speed_p (bb1
)
1690 && optimize_bb_for_speed_p (bb2
))
1692 profile_probability prob2
;
1694 if (b1
->dest
== b2
->dest
)
1695 prob2
= b2
->probability
;
1697 /* Do not use f2 probability as f2 may be forwarded. */
1698 prob2
= b2
->probability
.invert ();
1700 /* Fail if the difference in probabilities is greater than 50%.
1701 This rules out two well-predicted branches with opposite
1703 if (b1
->probability
.differs_lot_from_p (prob2
))
1708 "Outcomes of branch in bb %i and %i differ too"
1709 " much (", bb1
->index
, bb2
->index
);
1710 b1
->probability
.dump (dump_file
);
1711 prob2
.dump (dump_file
);
1712 fprintf (dump_file
, ")\n");
1718 if (dump_file
&& match
)
1719 fprintf (dump_file
, "Conditionals in bb %i and %i match.\n",
1720 bb1
->index
, bb2
->index
);
1725 /* Generic case - we are seeing a computed jump, table jump or trapping
1728 /* Check whether there are tablejumps in the end of BB1 and BB2.
1729 Return true if they are identical. */
1731 rtx_insn
*label1
, *label2
;
1732 rtx_jump_table_data
*table1
, *table2
;
1734 if (tablejump_p (BB_END (bb1
), &label1
, &table1
)
1735 && tablejump_p (BB_END (bb2
), &label2
, &table2
)
1736 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1738 /* The labels should never be the same rtx. If they really are same
1739 the jump tables are same too. So disable crossjumping of blocks BB1
1740 and BB2 because when deleting the common insns in the end of BB1
1741 by delete_basic_block () the jump table would be deleted too. */
1742 /* If LABEL2 is referenced in BB1->END do not do anything
1743 because we would loose information when replacing
1744 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1745 if (label1
!= label2
&& !rtx_referenced_p (label2
, BB_END (bb1
)))
1747 /* Set IDENTICAL to true when the tables are identical. */
1748 bool identical
= false;
1751 p1
= PATTERN (table1
);
1752 p2
= PATTERN (table2
);
1753 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1757 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1758 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1759 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1760 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1765 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1766 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1774 /* Temporarily replace references to LABEL1 with LABEL2
1775 in BB1->END so that we could compare the instructions. */
1776 replace_label_in_insn (BB_END (bb1
), label1
, label2
, false);
1778 match
= (old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
))
1780 if (dump_file
&& match
)
1782 "Tablejumps in bb %i and %i match.\n",
1783 bb1
->index
, bb2
->index
);
1785 /* Set the original label in BB1->END because when deleting
1786 a block whose end is a tablejump, the tablejump referenced
1787 from the instruction is deleted too. */
1788 replace_label_in_insn (BB_END (bb1
), label2
, label1
, false);
1797 /* Find the last non-debug non-note instruction in each bb, except
1798 stop when we see the NOTE_INSN_BASIC_BLOCK, as old_insns_match_p
1799 handles that case specially. old_insns_match_p does not handle
1800 other types of instruction notes. */
1801 rtx_insn
*last1
= BB_END (bb1
);
1802 rtx_insn
*last2
= BB_END (bb2
);
1803 while (!NOTE_INSN_BASIC_BLOCK_P (last1
) &&
1804 (DEBUG_INSN_P (last1
) || NOTE_P (last1
)))
1805 last1
= PREV_INSN (last1
);
1806 while (!NOTE_INSN_BASIC_BLOCK_P (last2
) &&
1807 (DEBUG_INSN_P (last2
) || NOTE_P (last2
)))
1808 last2
= PREV_INSN (last2
);
1809 gcc_assert (last1
&& last2
);
1811 /* First ensure that the instructions match. There may be many outgoing
1812 edges so this test is generally cheaper. */
1813 if (old_insns_match_p (mode
, last1
, last2
) != dir_both
)
1816 /* Search the outgoing edges, ensure that the counts do match, find possible
1817 fallthru and exception handling edges since these needs more
1819 if (EDGE_COUNT (bb1
->succs
) != EDGE_COUNT (bb2
->succs
))
1822 bool nonfakeedges
= false;
1823 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1825 e2
= EDGE_SUCC (bb2
, ei
.index
);
1827 if ((e1
->flags
& EDGE_FAKE
) == 0)
1828 nonfakeedges
= true;
1830 if (e1
->flags
& EDGE_EH
)
1833 if (e2
->flags
& EDGE_EH
)
1836 if (e1
->flags
& EDGE_FALLTHRU
)
1838 if (e2
->flags
& EDGE_FALLTHRU
)
1842 /* If number of edges of various types does not match, fail. */
1843 if (nehedges1
!= nehedges2
1844 || (fallthru1
!= 0) != (fallthru2
!= 0))
1847 /* If !ACCUMULATE_OUTGOING_ARGS, bb1 (and bb2) have no successors
1848 and the last real insn doesn't have REG_ARGS_SIZE note, don't
1849 attempt to optimize, as the two basic blocks might have different
1850 REG_ARGS_SIZE depths. For noreturn calls and unconditional
1851 traps there should be REG_ARG_SIZE notes, they could be missing
1852 for __builtin_unreachable () uses though. */
1854 && !ACCUMULATE_OUTGOING_ARGS
1856 || !find_reg_note (last1
, REG_ARGS_SIZE
, NULL
)))
1859 /* fallthru edges must be forwarded to the same destination. */
1862 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1863 ? single_succ (fallthru1
->dest
): fallthru1
->dest
);
1864 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1865 ? single_succ (fallthru2
->dest
): fallthru2
->dest
);
1871 /* Ensure the same EH region. */
1873 rtx n1
= find_reg_note (BB_END (bb1
), REG_EH_REGION
, 0);
1874 rtx n2
= find_reg_note (BB_END (bb2
), REG_EH_REGION
, 0);
1879 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1883 /* The same checks as in try_crossjump_to_edge. It is required for RTL
1884 version of sequence abstraction. */
1885 FOR_EACH_EDGE (e1
, ei
, bb2
->succs
)
1889 basic_block d1
= e1
->dest
;
1891 if (FORWARDER_BLOCK_P (d1
))
1892 d1
= EDGE_SUCC (d1
, 0)->dest
;
1894 FOR_EACH_EDGE (e2
, ei
, bb1
->succs
)
1896 basic_block d2
= e2
->dest
;
1897 if (FORWARDER_BLOCK_P (d2
))
1898 d2
= EDGE_SUCC (d2
, 0)->dest
;
1910 /* Returns true if BB basic block has a preserve label. */
1913 block_has_preserve_label (basic_block bb
)
1917 && LABEL_PRESERVE_P (block_label (bb
)));
1920 /* E1 and E2 are edges with the same destination block. Search their
1921 predecessors for common code. If found, redirect control flow from
1922 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC (dir_forward),
1923 or the other way around (dir_backward). DIR specifies the allowed
1924 replacement direction. */
1927 try_crossjump_to_edge (int mode
, edge e1
, edge e2
,
1928 enum replace_direction dir
)
1931 basic_block src1
= e1
->src
, src2
= e2
->src
;
1932 basic_block redirect_to
, redirect_from
, to_remove
;
1933 basic_block osrc1
, osrc2
, redirect_edges_to
, tmp
;
1934 rtx_insn
*newpos1
, *newpos2
;
1938 newpos1
= newpos2
= NULL
;
1940 /* Search backward through forwarder blocks. We don't need to worry
1941 about multiple entry or chained forwarders, as they will be optimized
1942 away. We do this to look past the unconditional jump following a
1943 conditional jump that is required due to the current CFG shape. */
1944 if (single_pred_p (src1
)
1945 && FORWARDER_BLOCK_P (src1
))
1946 e1
= single_pred_edge (src1
), src1
= e1
->src
;
1948 if (single_pred_p (src2
)
1949 && FORWARDER_BLOCK_P (src2
))
1950 e2
= single_pred_edge (src2
), src2
= e2
->src
;
1952 /* Nothing to do if we reach ENTRY, or a common source block. */
1953 if (src1
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || src2
1954 == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1959 /* Seeing more than 1 forwarder blocks would confuse us later... */
1960 if (FORWARDER_BLOCK_P (e1
->dest
)
1961 && FORWARDER_BLOCK_P (single_succ (e1
->dest
)))
1964 if (FORWARDER_BLOCK_P (e2
->dest
)
1965 && FORWARDER_BLOCK_P (single_succ (e2
->dest
)))
1968 /* Likewise with dead code (possibly newly created by the other optimizations
1970 if (EDGE_COUNT (src1
->preds
) == 0 || EDGE_COUNT (src2
->preds
) == 0)
1973 /* Do not turn corssing edge to non-crossing or vice versa after reload. */
1974 if (BB_PARTITION (src1
) != BB_PARTITION (src2
)
1975 && reload_completed
)
1978 /* Look for the common insn sequence, part the first ... */
1979 if (!outgoing_edges_match (mode
, src1
, src2
))
1982 /* ... and part the second. */
1983 nmatch
= flow_find_cross_jump (src1
, src2
, &newpos1
, &newpos2
, &dir
);
1987 if (newpos1
!= NULL_RTX
)
1988 src1
= BLOCK_FOR_INSN (newpos1
);
1989 if (newpos2
!= NULL_RTX
)
1990 src2
= BLOCK_FOR_INSN (newpos2
);
1992 /* Check that SRC1 and SRC2 have preds again. They may have changed
1993 above due to the call to flow_find_cross_jump. */
1994 if (EDGE_COUNT (src1
->preds
) == 0 || EDGE_COUNT (src2
->preds
) == 0)
1997 if (dir
== dir_backward
)
1999 std::swap (osrc1
, osrc2
);
2000 std::swap (src1
, src2
);
2002 std::swap (newpos1
, newpos2
);
2005 /* Don't proceed with the crossjump unless we found a sufficient number
2006 of matching instructions or the 'from' block was totally matched
2007 (such that its predecessors will hopefully be redirected and the
2009 if ((nmatch
< PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS
))
2010 && (newpos1
!= BB_HEAD (src1
)))
2013 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */
2014 if (block_has_preserve_label (e1
->dest
)
2015 && (e1
->flags
& EDGE_ABNORMAL
))
2018 /* Here we know that the insns in the end of SRC1 which are common with SRC2
2020 If we have tablejumps in the end of SRC1 and SRC2
2021 they have been already compared for equivalence in outgoing_edges_match ()
2022 so replace the references to TABLE1 by references to TABLE2. */
2024 rtx_insn
*label1
, *label2
;
2025 rtx_jump_table_data
*table1
, *table2
;
2027 if (tablejump_p (BB_END (osrc1
), &label1
, &table1
)
2028 && tablejump_p (BB_END (osrc2
), &label2
, &table2
)
2029 && label1
!= label2
)
2033 /* Replace references to LABEL1 with LABEL2. */
2034 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
2036 /* Do not replace the label in SRC1->END because when deleting
2037 a block whose end is a tablejump, the tablejump referenced
2038 from the instruction is deleted too. */
2039 if (insn
!= BB_END (osrc1
))
2040 replace_label_in_insn (insn
, label1
, label2
, true);
2045 /* Avoid splitting if possible. We must always split when SRC2 has
2046 EH predecessor edges, or we may end up with basic blocks with both
2047 normal and EH predecessor edges. */
2048 if (newpos2
== BB_HEAD (src2
)
2049 && !(EDGE_PRED (src2
, 0)->flags
& EDGE_EH
))
2053 if (newpos2
== BB_HEAD (src2
))
2055 /* Skip possible basic block header. */
2056 if (LABEL_P (newpos2
))
2057 newpos2
= NEXT_INSN (newpos2
);
2058 while (DEBUG_INSN_P (newpos2
))
2059 newpos2
= NEXT_INSN (newpos2
);
2060 if (NOTE_P (newpos2
))
2061 newpos2
= NEXT_INSN (newpos2
);
2062 while (DEBUG_INSN_P (newpos2
))
2063 newpos2
= NEXT_INSN (newpos2
);
2067 fprintf (dump_file
, "Splitting bb %i before %i insns\n",
2068 src2
->index
, nmatch
);
2069 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
2074 "Cross jumping from bb %i to bb %i; %i common insns\n",
2075 src1
->index
, src2
->index
, nmatch
);
2077 /* We may have some registers visible through the block. */
2078 df_set_bb_dirty (redirect_to
);
2081 redirect_edges_to
= redirect_to
;
2083 redirect_edges_to
= osrc2
;
2085 /* Recompute the counts of destinations of outgoing edges. */
2086 FOR_EACH_EDGE (s
, ei
, redirect_edges_to
->succs
)
2090 basic_block d
= s
->dest
;
2092 if (FORWARDER_BLOCK_P (d
))
2093 d
= single_succ (d
);
2095 FOR_EACH_EDGE (s2
, ei
, src1
->succs
)
2097 basic_block d2
= s2
->dest
;
2098 if (FORWARDER_BLOCK_P (d2
))
2099 d2
= single_succ (d2
);
2104 /* Take care to update possible forwarder blocks. We verified
2105 that there is no more than one in the chain, so we can't run
2106 into infinite loop. */
2107 if (FORWARDER_BLOCK_P (s
->dest
))
2108 s
->dest
->count
+= s
->count ();
2110 if (FORWARDER_BLOCK_P (s2
->dest
))
2111 s2
->dest
->count
-= s
->count ();
2113 s
->probability
= s
->probability
.combine_with_count
2114 (redirect_edges_to
->count
,
2115 s2
->probability
, src1
->count
);
2118 /* Adjust count for the block. An earlier jump
2119 threading pass may have left the profile in an inconsistent
2120 state (see update_bb_profile_for_threading) so we must be
2121 prepared for overflows. */
2125 tmp
->count
+= src1
->count
;
2126 if (tmp
== redirect_edges_to
)
2128 tmp
= find_fallthru_edge (tmp
->succs
)->dest
;
2131 update_br_prob_note (redirect_edges_to
);
2133 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
2135 /* Skip possible basic block header. */
2136 if (LABEL_P (newpos1
))
2137 newpos1
= NEXT_INSN (newpos1
);
2139 while (DEBUG_INSN_P (newpos1
))
2140 newpos1
= NEXT_INSN (newpos1
);
2142 if (NOTE_INSN_BASIC_BLOCK_P (newpos1
))
2143 newpos1
= NEXT_INSN (newpos1
);
2145 while (DEBUG_INSN_P (newpos1
))
2146 newpos1
= NEXT_INSN (newpos1
);
2148 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
2149 to_remove
= single_succ (redirect_from
);
2151 redirect_edge_and_branch_force (single_succ_edge (redirect_from
), redirect_to
);
2152 delete_basic_block (to_remove
);
2154 update_forwarder_flag (redirect_from
);
2155 if (redirect_to
!= src2
)
2156 update_forwarder_flag (src2
);
2161 /* Search the predecessors of BB for common insn sequences. When found,
2162 share code between them by redirecting control flow. Return true if
2163 any changes made. */
2166 try_crossjump_bb (int mode
, basic_block bb
)
2168 edge e
, e2
, fallthru
;
2170 unsigned max
, ix
, ix2
;
2172 /* Nothing to do if there is not at least two incoming edges. */
2173 if (EDGE_COUNT (bb
->preds
) < 2)
2176 /* Don't crossjump if this block ends in a computed jump,
2177 unless we are optimizing for size. */
2178 if (optimize_bb_for_size_p (bb
)
2179 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2180 && computed_jump_p (BB_END (bb
)))
2183 /* If we are partitioning hot/cold basic blocks, we don't want to
2184 mess up unconditional or indirect jumps that cross between hot
2187 Basic block partitioning may result in some jumps that appear to
2188 be optimizable (or blocks that appear to be mergeable), but which really
2189 must be left untouched (they are required to make it safely across
2190 partition boundaries). See the comments at the top of
2191 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
2193 if (BB_PARTITION (EDGE_PRED (bb
, 0)->src
) !=
2194 BB_PARTITION (EDGE_PRED (bb
, 1)->src
)
2195 || (EDGE_PRED (bb
, 0)->flags
& EDGE_CROSSING
))
2198 /* It is always cheapest to redirect a block that ends in a branch to
2199 a block that falls through into BB, as that adds no branches to the
2200 program. We'll try that combination first. */
2202 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
2204 if (EDGE_COUNT (bb
->preds
) > max
)
2207 fallthru
= find_fallthru_edge (bb
->preds
);
2210 for (ix
= 0; ix
< EDGE_COUNT (bb
->preds
);)
2212 e
= EDGE_PRED (bb
, ix
);
2215 /* As noted above, first try with the fallthru predecessor (or, a
2216 fallthru predecessor if we are in cfglayout mode). */
2219 /* Don't combine the fallthru edge into anything else.
2220 If there is a match, we'll do it the other way around. */
2223 /* If nothing changed since the last attempt, there is nothing
2226 && !((e
->src
->flags
& BB_MODIFIED
)
2227 || (fallthru
->src
->flags
& BB_MODIFIED
)))
2230 if (try_crossjump_to_edge (mode
, e
, fallthru
, dir_forward
))
2238 /* Non-obvious work limiting check: Recognize that we're going
2239 to call try_crossjump_bb on every basic block. So if we have
2240 two blocks with lots of outgoing edges (a switch) and they
2241 share lots of common destinations, then we would do the
2242 cross-jump check once for each common destination.
2244 Now, if the blocks actually are cross-jump candidates, then
2245 all of their destinations will be shared. Which means that
2246 we only need check them for cross-jump candidacy once. We
2247 can eliminate redundant checks of crossjump(A,B) by arbitrarily
2248 choosing to do the check from the block for which the edge
2249 in question is the first successor of A. */
2250 if (EDGE_SUCC (e
->src
, 0) != e
)
2253 for (ix2
= 0; ix2
< EDGE_COUNT (bb
->preds
); ix2
++)
2255 e2
= EDGE_PRED (bb
, ix2
);
2260 /* We've already checked the fallthru edge above. */
2264 /* The "first successor" check above only prevents multiple
2265 checks of crossjump(A,B). In order to prevent redundant
2266 checks of crossjump(B,A), require that A be the block
2267 with the lowest index. */
2268 if (e
->src
->index
> e2
->src
->index
)
2271 /* If nothing changed since the last attempt, there is nothing
2274 && !((e
->src
->flags
& BB_MODIFIED
)
2275 || (e2
->src
->flags
& BB_MODIFIED
)))
2278 /* Both e and e2 are not fallthru edges, so we can crossjump in either
2280 if (try_crossjump_to_edge (mode
, e
, e2
, dir_both
))
2290 crossjumps_occurred
= true;
2295 /* Search the successors of BB for common insn sequences. When found,
2296 share code between them by moving it across the basic block
2297 boundary. Return true if any changes made. */
2300 try_head_merge_bb (basic_block bb
)
2302 basic_block final_dest_bb
= NULL
;
2303 int max_match
= INT_MAX
;
2305 rtx_insn
**headptr
, **currptr
, **nextptr
;
2306 bool changed
, moveall
;
2308 rtx_insn
*e0_last_head
;
2310 rtx_insn
*move_before
;
2311 unsigned nedges
= EDGE_COUNT (bb
->succs
);
2312 rtx_insn
*jump
= BB_END (bb
);
2313 regset live
, live_union
;
2315 /* Nothing to do if there is not at least two outgoing edges. */
2319 /* Don't crossjump if this block ends in a computed jump,
2320 unless we are optimizing for size. */
2321 if (optimize_bb_for_size_p (bb
)
2322 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2323 && computed_jump_p (BB_END (bb
)))
2326 cond
= get_condition (jump
, &move_before
, true, false);
2327 if (cond
== NULL_RTX
)
2329 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, jump
))
2330 move_before
= prev_nonnote_nondebug_insn (jump
);
2335 for (ix
= 0; ix
< nedges
; ix
++)
2336 if (EDGE_SUCC (bb
, ix
)->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
2339 for (ix
= 0; ix
< nedges
; ix
++)
2341 edge e
= EDGE_SUCC (bb
, ix
);
2342 basic_block other_bb
= e
->dest
;
2344 if (df_get_bb_dirty (other_bb
))
2346 block_was_dirty
= true;
2350 if (e
->flags
& EDGE_ABNORMAL
)
2353 /* Normally, all destination blocks must only be reachable from this
2354 block, i.e. they must have one incoming edge.
2356 There is one special case we can handle, that of multiple consecutive
2357 jumps where the first jumps to one of the targets of the second jump.
2358 This happens frequently in switch statements for default labels.
2359 The structure is as follows:
2365 jump with targets A, B, C, D...
2367 has two incoming edges, from FINAL_DEST_BB and BB
2369 In this case, we can try to move the insns through BB and into
2371 if (EDGE_COUNT (other_bb
->preds
) != 1)
2373 edge incoming_edge
, incoming_bb_other_edge
;
2376 if (final_dest_bb
!= NULL
2377 || EDGE_COUNT (other_bb
->preds
) != 2)
2380 /* We must be able to move the insns across the whole block. */
2381 move_before
= BB_HEAD (bb
);
2382 while (!NONDEBUG_INSN_P (move_before
))
2383 move_before
= NEXT_INSN (move_before
);
2385 if (EDGE_COUNT (bb
->preds
) != 1)
2387 incoming_edge
= EDGE_PRED (bb
, 0);
2388 final_dest_bb
= incoming_edge
->src
;
2389 if (EDGE_COUNT (final_dest_bb
->succs
) != 2)
2391 FOR_EACH_EDGE (incoming_bb_other_edge
, ei
, final_dest_bb
->succs
)
2392 if (incoming_bb_other_edge
!= incoming_edge
)
2394 if (incoming_bb_other_edge
->dest
!= other_bb
)
2399 e0
= EDGE_SUCC (bb
, 0);
2400 e0_last_head
= NULL
;
2403 for (ix
= 1; ix
< nedges
; ix
++)
2405 edge e
= EDGE_SUCC (bb
, ix
);
2406 rtx_insn
*e0_last
, *e_last
;
2409 nmatch
= flow_find_head_matching_sequence (e0
->dest
, e
->dest
,
2410 &e0_last
, &e_last
, 0);
2414 if (nmatch
< max_match
)
2417 e0_last_head
= e0_last
;
2421 /* If we matched an entire block, we probably have to avoid moving the
2424 && e0_last_head
== BB_END (e0
->dest
)
2425 && (find_reg_note (e0_last_head
, REG_EH_REGION
, 0)
2426 || control_flow_insn_p (e0_last_head
)))
2431 e0_last_head
= prev_real_nondebug_insn (e0_last_head
);
2437 /* We must find a union of the live registers at each of the end points. */
2438 live
= BITMAP_ALLOC (NULL
);
2439 live_union
= BITMAP_ALLOC (NULL
);
2441 currptr
= XNEWVEC (rtx_insn
*, nedges
);
2442 headptr
= XNEWVEC (rtx_insn
*, nedges
);
2443 nextptr
= XNEWVEC (rtx_insn
*, nedges
);
2445 for (ix
= 0; ix
< nedges
; ix
++)
2448 basic_block merge_bb
= EDGE_SUCC (bb
, ix
)->dest
;
2449 rtx_insn
*head
= BB_HEAD (merge_bb
);
2451 while (!NONDEBUG_INSN_P (head
))
2452 head
= NEXT_INSN (head
);
2456 /* Compute the end point and live information */
2457 for (j
= 1; j
< max_match
; j
++)
2459 head
= NEXT_INSN (head
);
2460 while (!NONDEBUG_INSN_P (head
));
2461 simulate_backwards_to_point (merge_bb
, live
, head
);
2462 IOR_REG_SET (live_union
, live
);
2465 /* If we're moving across two blocks, verify the validity of the
2466 first move, then adjust the target and let the loop below deal
2467 with the final move. */
2468 if (final_dest_bb
!= NULL
)
2470 rtx_insn
*move_upto
;
2472 moveall
= can_move_insns_across (currptr
[0], e0_last_head
, move_before
,
2473 jump
, e0
->dest
, live_union
,
2477 if (move_upto
== NULL_RTX
)
2480 while (e0_last_head
!= move_upto
)
2482 df_simulate_one_insn_backwards (e0
->dest
, e0_last_head
,
2484 e0_last_head
= PREV_INSN (e0_last_head
);
2487 if (e0_last_head
== NULL_RTX
)
2490 jump
= BB_END (final_dest_bb
);
2491 cond
= get_condition (jump
, &move_before
, true, false);
2492 if (cond
== NULL_RTX
)
2494 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, jump
))
2495 move_before
= prev_nonnote_nondebug_insn (jump
);
2503 rtx_insn
*move_upto
;
2504 moveall
= can_move_insns_across (currptr
[0], e0_last_head
,
2505 move_before
, jump
, e0
->dest
, live_union
,
2507 if (!moveall
&& move_upto
== NULL_RTX
)
2509 if (jump
== move_before
)
2512 /* Try again, using a different insertion point. */
2515 /* Don't try moving before a cc0 user, as that may invalidate
2517 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, jump
))
2523 if (final_dest_bb
&& !moveall
)
2524 /* We haven't checked whether a partial move would be OK for the first
2525 move, so we have to fail this case. */
2531 if (currptr
[0] == move_upto
)
2533 for (ix
= 0; ix
< nedges
; ix
++)
2535 rtx_insn
*curr
= currptr
[ix
];
2537 curr
= NEXT_INSN (curr
);
2538 while (!NONDEBUG_INSN_P (curr
));
2543 /* If we can't currently move all of the identical insns, remember
2544 each insn after the range that we'll merge. */
2546 for (ix
= 0; ix
< nedges
; ix
++)
2548 rtx_insn
*curr
= currptr
[ix
];
2550 curr
= NEXT_INSN (curr
);
2551 while (!NONDEBUG_INSN_P (curr
));
2555 reorder_insns (headptr
[0], currptr
[0], PREV_INSN (move_before
));
2556 df_set_bb_dirty (EDGE_SUCC (bb
, 0)->dest
);
2557 if (final_dest_bb
!= NULL
)
2558 df_set_bb_dirty (final_dest_bb
);
2559 df_set_bb_dirty (bb
);
2560 for (ix
= 1; ix
< nedges
; ix
++)
2562 df_set_bb_dirty (EDGE_SUCC (bb
, ix
)->dest
);
2563 delete_insn_chain (headptr
[ix
], currptr
[ix
], false);
2567 if (jump
== move_before
)
2570 /* For the unmerged insns, try a different insertion point. */
2573 /* Don't try moving before a cc0 user, as that may invalidate
2575 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, jump
))
2578 for (ix
= 0; ix
< nedges
; ix
++)
2579 currptr
[ix
] = headptr
[ix
] = nextptr
[ix
];
2589 crossjumps_occurred
|= changed
;
2594 /* Return true if BB contains just bb note, or bb note followed
2595 by only DEBUG_INSNs. */
2598 trivially_empty_bb_p (basic_block bb
)
2600 rtx_insn
*insn
= BB_END (bb
);
2604 if (insn
== BB_HEAD (bb
))
2606 if (!DEBUG_INSN_P (insn
))
2608 insn
= PREV_INSN (insn
);
2612 /* Return true if BB contains just a return and possibly a USE of the
2613 return value. Fill in *RET and *USE with the return and use insns
2614 if any found, otherwise NULL. All CLOBBERs are ignored. */
2617 bb_is_just_return (basic_block bb
, rtx_insn
**ret
, rtx_insn
**use
)
2622 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
2625 FOR_BB_INSNS (bb
, insn
)
2626 if (NONDEBUG_INSN_P (insn
))
2628 rtx pat
= PATTERN (insn
);
2630 if (!*ret
&& ANY_RETURN_P (pat
))
2632 else if (!*ret
&& !*use
&& GET_CODE (pat
) == USE
2633 && REG_P (XEXP (pat
, 0))
2634 && REG_FUNCTION_VALUE_P (XEXP (pat
, 0)))
2636 else if (GET_CODE (pat
) != CLOBBER
)
2643 /* Do simple CFG optimizations - basic block merging, simplifying of jump
2644 instructions etc. Return nonzero if changes were made. */
2647 try_optimize_cfg (int mode
)
2649 bool changed_overall
= false;
2652 basic_block bb
, b
, next
;
2654 if (mode
& (CLEANUP_CROSSJUMP
| CLEANUP_THREADING
))
2657 crossjumps_occurred
= false;
2659 FOR_EACH_BB_FN (bb
, cfun
)
2660 update_forwarder_flag (bb
);
2662 if (! targetm
.cannot_modify_jumps_p ())
2665 /* Attempt to merge blocks as made possible by edge removal. If
2666 a block has only one successor, and the successor has only
2667 one predecessor, they may be combined. */
2670 block_was_dirty
= false;
2676 "\n\ntry_optimize_cfg iteration %i\n\n",
2679 for (b
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; b
2680 != EXIT_BLOCK_PTR_FOR_FN (cfun
);)
2684 bool changed_here
= false;
2686 /* Delete trivially dead basic blocks. This is either
2687 blocks with no predecessors, or empty blocks with no
2688 successors. However if the empty block with no
2689 successors is the successor of the ENTRY_BLOCK, it is
2690 kept. This ensures that the ENTRY_BLOCK will have a
2691 successor which is a precondition for many RTL
2692 passes. Empty blocks may result from expanding
2693 __builtin_unreachable (). */
2694 if (EDGE_COUNT (b
->preds
) == 0
2695 || (EDGE_COUNT (b
->succs
) == 0
2696 && trivially_empty_bb_p (b
)
2697 && single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->dest
2701 if (EDGE_COUNT (b
->preds
) > 0)
2706 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2709 && BARRIER_P (BB_FOOTER (b
)))
2710 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2711 if ((e
->flags
& EDGE_FALLTHRU
)
2712 && BB_FOOTER (e
->src
) == NULL
)
2716 BB_FOOTER (e
->src
) = BB_FOOTER (b
);
2717 BB_FOOTER (b
) = NULL
;
2722 BB_FOOTER (e
->src
) = emit_barrier ();
2729 rtx_insn
*last
= get_last_bb_insn (b
);
2730 if (last
&& BARRIER_P (last
))
2731 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2732 if ((e
->flags
& EDGE_FALLTHRU
))
2733 emit_barrier_after (BB_END (e
->src
));
2736 delete_basic_block (b
);
2738 /* Avoid trying to remove the exit block. */
2739 b
= (c
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) ? c
->next_bb
: c
);
2743 /* Remove code labels no longer used. */
2744 if (single_pred_p (b
)
2745 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2746 && !(single_pred_edge (b
)->flags
& EDGE_COMPLEX
)
2747 && LABEL_P (BB_HEAD (b
))
2748 && !LABEL_PRESERVE_P (BB_HEAD (b
))
2749 /* If the previous block ends with a branch to this
2750 block, we can't delete the label. Normally this
2751 is a condjump that is yet to be simplified, but
2752 if CASE_DROPS_THRU, this can be a tablejump with
2753 some element going to the same place as the
2754 default (fallthru). */
2755 && (single_pred (b
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2756 || !JUMP_P (BB_END (single_pred (b
)))
2757 || ! label_is_jump_target_p (BB_HEAD (b
),
2758 BB_END (single_pred (b
)))))
2760 delete_insn (BB_HEAD (b
));
2762 fprintf (dump_file
, "Deleted label in block %i.\n",
2766 /* If we fall through an empty block, we can remove it. */
2767 if (!(mode
& (CLEANUP_CFGLAYOUT
| CLEANUP_NO_INSN_DEL
))
2768 && single_pred_p (b
)
2769 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2770 && !LABEL_P (BB_HEAD (b
))
2771 && FORWARDER_BLOCK_P (b
)
2772 /* Note that forwarder_block_p true ensures that
2773 there is a successor for this block. */
2774 && (single_succ_edge (b
)->flags
& EDGE_FALLTHRU
)
2775 && n_basic_blocks_for_fn (cfun
) > NUM_FIXED_BLOCKS
+ 1)
2779 "Deleting fallthru block %i.\n",
2782 c
= ((b
->prev_bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
2783 ? b
->next_bb
: b
->prev_bb
);
2784 redirect_edge_succ_nodup (single_pred_edge (b
),
2786 delete_basic_block (b
);
2792 /* Merge B with its single successor, if any. */
2793 if (single_succ_p (b
)
2794 && (s
= single_succ_edge (b
))
2795 && !(s
->flags
& EDGE_COMPLEX
)
2796 && (c
= s
->dest
) != EXIT_BLOCK_PTR_FOR_FN (cfun
)
2797 && single_pred_p (c
)
2800 /* When not in cfg_layout mode use code aware of reordering
2801 INSN. This code possibly creates new basic blocks so it
2802 does not fit merge_blocks interface and is kept here in
2803 hope that it will become useless once more of compiler
2804 is transformed to use cfg_layout mode. */
2806 if ((mode
& CLEANUP_CFGLAYOUT
)
2807 && can_merge_blocks_p (b
, c
))
2809 merge_blocks (b
, c
);
2810 update_forwarder_flag (b
);
2811 changed_here
= true;
2813 else if (!(mode
& CLEANUP_CFGLAYOUT
)
2814 /* If the jump insn has side effects,
2815 we can't kill the edge. */
2816 && (!JUMP_P (BB_END (b
))
2817 || (reload_completed
2818 ? simplejump_p (BB_END (b
))
2819 : (onlyjump_p (BB_END (b
))
2820 && !tablejump_p (BB_END (b
),
2822 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
2825 changed_here
= true;
2829 /* Try to change a branch to a return to just that return. */
2830 rtx_insn
*ret
, *use
;
2831 if (single_succ_p (b
)
2832 && onlyjump_p (BB_END (b
))
2833 && bb_is_just_return (single_succ (b
), &ret
, &use
))
2835 if (redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (b
)),
2839 emit_insn_before (copy_insn (PATTERN (use
)),
2842 fprintf (dump_file
, "Changed jump %d->%d to return.\n",
2843 b
->index
, single_succ (b
)->index
);
2844 redirect_edge_succ (single_succ_edge (b
),
2845 EXIT_BLOCK_PTR_FOR_FN (cfun
));
2846 single_succ_edge (b
)->flags
&= ~EDGE_CROSSING
;
2847 changed_here
= true;
2851 /* Try to change a conditional branch to a return to the
2852 respective conditional return. */
2853 if (EDGE_COUNT (b
->succs
) == 2
2854 && any_condjump_p (BB_END (b
))
2855 && bb_is_just_return (BRANCH_EDGE (b
)->dest
, &ret
, &use
))
2857 if (redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (b
)),
2861 emit_insn_before (copy_insn (PATTERN (use
)),
2864 fprintf (dump_file
, "Changed conditional jump %d->%d "
2865 "to conditional return.\n",
2866 b
->index
, BRANCH_EDGE (b
)->dest
->index
);
2867 redirect_edge_succ (BRANCH_EDGE (b
),
2868 EXIT_BLOCK_PTR_FOR_FN (cfun
));
2869 BRANCH_EDGE (b
)->flags
&= ~EDGE_CROSSING
;
2870 changed_here
= true;
2874 /* Try to flip a conditional branch that falls through to
2875 a return so that it becomes a conditional return and a
2876 new jump to the original branch target. */
2877 if (EDGE_COUNT (b
->succs
) == 2
2878 && BRANCH_EDGE (b
)->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2879 && any_condjump_p (BB_END (b
))
2880 && bb_is_just_return (FALLTHRU_EDGE (b
)->dest
, &ret
, &use
))
2882 if (invert_jump (as_a
<rtx_jump_insn
*> (BB_END (b
)),
2883 JUMP_LABEL (BB_END (b
)), 0))
2885 basic_block new_ft
= BRANCH_EDGE (b
)->dest
;
2886 if (redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (b
)),
2890 emit_insn_before (copy_insn (PATTERN (use
)),
2893 fprintf (dump_file
, "Changed conditional jump "
2894 "%d->%d to conditional return, adding "
2895 "fall-through jump.\n",
2896 b
->index
, BRANCH_EDGE (b
)->dest
->index
);
2897 redirect_edge_succ (BRANCH_EDGE (b
),
2898 EXIT_BLOCK_PTR_FOR_FN (cfun
));
2899 BRANCH_EDGE (b
)->flags
&= ~EDGE_CROSSING
;
2900 std::swap (BRANCH_EDGE (b
)->probability
,
2901 FALLTHRU_EDGE (b
)->probability
);
2902 update_br_prob_note (b
);
2903 basic_block jb
= force_nonfallthru (FALLTHRU_EDGE (b
));
2904 notice_new_block (jb
);
2905 if (!redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (jb
)),
2906 block_label (new_ft
), 0))
2908 redirect_edge_succ (single_succ_edge (jb
), new_ft
);
2909 changed_here
= true;
2913 /* Invert the jump back to what it was. This should
2915 if (!invert_jump (as_a
<rtx_jump_insn
*> (BB_END (b
)),
2916 JUMP_LABEL (BB_END (b
)), 0))
2922 /* Simplify branch over branch. */
2923 if ((mode
& CLEANUP_EXPENSIVE
)
2924 && !(mode
& CLEANUP_CFGLAYOUT
)
2925 && try_simplify_condjump (b
))
2926 changed_here
= true;
2928 /* If B has a single outgoing edge, but uses a
2929 non-trivial jump instruction without side-effects, we
2930 can either delete the jump entirely, or replace it
2931 with a simple unconditional jump. */
2932 if (single_succ_p (b
)
2933 && single_succ (b
) != EXIT_BLOCK_PTR_FOR_FN (cfun
)
2934 && onlyjump_p (BB_END (b
))
2935 && !CROSSING_JUMP_P (BB_END (b
))
2936 && try_redirect_by_replacing_jump (single_succ_edge (b
),
2938 (mode
& CLEANUP_CFGLAYOUT
) != 0))
2940 update_forwarder_flag (b
);
2941 changed_here
= true;
2944 /* Simplify branch to branch. */
2945 if (try_forward_edges (mode
, b
))
2947 update_forwarder_flag (b
);
2948 changed_here
= true;
2951 /* Look for shared code between blocks. */
2952 if ((mode
& CLEANUP_CROSSJUMP
)
2953 && try_crossjump_bb (mode
, b
))
2954 changed_here
= true;
2956 if ((mode
& CLEANUP_CROSSJUMP
)
2957 /* This can lengthen register lifetimes. Do it only after
2960 && try_head_merge_bb (b
))
2961 changed_here
= true;
2963 /* Don't get confused by the index shift caused by
2971 if ((mode
& CLEANUP_CROSSJUMP
)
2972 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR_FOR_FN (cfun
)))
2975 if (block_was_dirty
)
2977 /* This should only be set by head-merging. */
2978 gcc_assert (mode
& CLEANUP_CROSSJUMP
);
2984 /* Edge forwarding in particular can cause hot blocks previously
2985 reached by both hot and cold blocks to become dominated only
2986 by cold blocks. This will cause the verification below to fail,
2987 and lead to now cold code in the hot section. This is not easy
2988 to detect and fix during edge forwarding, and in some cases
2989 is only visible after newly unreachable blocks are deleted,
2990 which will be done in fixup_partitions. */
2991 if ((mode
& CLEANUP_NO_PARTITIONING
) == 0)
2993 fixup_partitions ();
2994 checking_verify_flow_info ();
2998 changed_overall
|= changed
;
3004 FOR_ALL_BB_FN (b
, cfun
)
3005 b
->flags
&= ~(BB_FORWARDER_BLOCK
| BB_NONTHREADABLE_BLOCK
);
3007 return changed_overall
;
3010 /* Delete all unreachable basic blocks. */
3013 delete_unreachable_blocks (void)
3015 bool changed
= false;
3016 basic_block b
, prev_bb
;
3018 find_unreachable_blocks ();
3020 /* When we're in GIMPLE mode and there may be debug bind insns, we
3021 should delete blocks in reverse dominator order, so as to get a
3022 chance to substitute all released DEFs into debug bind stmts. If
3023 we don't have dominators information, walking blocks backward
3024 gets us a better chance of retaining most debug information than
3026 if (MAY_HAVE_DEBUG_BIND_INSNS
&& current_ir_type () == IR_GIMPLE
3027 && dom_info_available_p (CDI_DOMINATORS
))
3029 for (b
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
3030 b
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
); b
= prev_bb
)
3032 prev_bb
= b
->prev_bb
;
3034 if (!(b
->flags
& BB_REACHABLE
))
3036 /* Speed up the removal of blocks that don't dominate
3037 others. Walking backwards, this should be the common
3039 if (!first_dom_son (CDI_DOMINATORS
, b
))
3040 delete_basic_block (b
);
3044 = get_all_dominated_blocks (CDI_DOMINATORS
, b
);
3050 prev_bb
= b
->prev_bb
;
3052 gcc_assert (!(b
->flags
& BB_REACHABLE
));
3054 delete_basic_block (b
);
3066 for (b
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
3067 b
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
); b
= prev_bb
)
3069 prev_bb
= b
->prev_bb
;
3071 if (!(b
->flags
& BB_REACHABLE
))
3073 delete_basic_block (b
);
3080 tidy_fallthru_edges ();
3084 /* Delete any jump tables never referenced. We can't delete them at the
3085 time of removing tablejump insn as they are referenced by the preceding
3086 insns computing the destination, so we delay deleting and garbagecollect
3087 them once life information is computed. */
3089 delete_dead_jumptables (void)
3093 /* A dead jump table does not belong to any basic block. Scan insns
3094 between two adjacent basic blocks. */
3095 FOR_EACH_BB_FN (bb
, cfun
)
3097 rtx_insn
*insn
, *next
;
3099 for (insn
= NEXT_INSN (BB_END (bb
));
3100 insn
&& !NOTE_INSN_BASIC_BLOCK_P (insn
);
3103 next
= NEXT_INSN (insn
);
3105 && LABEL_NUSES (insn
) == LABEL_PRESERVE_P (insn
)
3106 && JUMP_TABLE_DATA_P (next
))
3108 rtx_insn
*label
= insn
, *jump
= next
;
3111 fprintf (dump_file
, "Dead jumptable %i removed\n",
3114 next
= NEXT_INSN (next
);
3116 delete_insn (label
);
3123 /* Tidy the CFG by deleting unreachable code and whatnot. */
3126 cleanup_cfg (int mode
)
3128 bool changed
= false;
3130 /* Set the cfglayout mode flag here. We could update all the callers
3131 but that is just inconvenient, especially given that we eventually
3132 want to have cfglayout mode as the default. */
3133 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
3134 mode
|= CLEANUP_CFGLAYOUT
;
3136 timevar_push (TV_CLEANUP_CFG
);
3137 if (delete_unreachable_blocks ())
3140 /* We've possibly created trivially dead code. Cleanup it right
3141 now to introduce more opportunities for try_optimize_cfg. */
3142 if (!(mode
& (CLEANUP_NO_INSN_DEL
))
3143 && !reload_completed
)
3144 delete_trivially_dead_insns (get_insns (), max_reg_num ());
3149 /* To tail-merge blocks ending in the same noreturn function (e.g.
3150 a call to abort) we have to insert fake edges to exit. Do this
3151 here once. The fake edges do not interfere with any other CFG
3153 if (mode
& CLEANUP_CROSSJUMP
)
3154 add_noreturn_fake_exit_edges ();
3156 if (!dbg_cnt (cfg_cleanup
))
3159 while (try_optimize_cfg (mode
))
3161 delete_unreachable_blocks (), changed
= true;
3162 if (!(mode
& CLEANUP_NO_INSN_DEL
))
3164 /* Try to remove some trivially dead insns when doing an expensive
3165 cleanup. But delete_trivially_dead_insns doesn't work after
3166 reload (it only handles pseudos) and run_fast_dce is too costly
3167 to run in every iteration.
3169 For effective cross jumping, we really want to run a fast DCE to
3170 clean up any dead conditions, or they get in the way of performing
3173 Other transformations in cleanup_cfg are not so sensitive to dead
3174 code, so delete_trivially_dead_insns or even doing nothing at all
3176 if ((mode
& CLEANUP_EXPENSIVE
) && !reload_completed
3177 && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
3179 if ((mode
& CLEANUP_CROSSJUMP
) && crossjumps_occurred
)
3186 if (mode
& CLEANUP_CROSSJUMP
)
3187 remove_fake_exit_edges ();
3189 /* Don't call delete_dead_jumptables in cfglayout mode, because
3190 that function assumes that jump tables are in the insns stream.
3191 But we also don't _have_ to delete dead jumptables in cfglayout
3192 mode because we shouldn't even be looking at things that are
3193 not in a basic block. Dead jumptables are cleaned up when
3194 going out of cfglayout mode. */
3195 if (!(mode
& CLEANUP_CFGLAYOUT
))
3196 delete_dead_jumptables ();
3198 /* ??? We probably do this way too often. */
3201 || (mode
& CLEANUP_CFG_CHANGED
)))
3203 timevar_push (TV_REPAIR_LOOPS
);
3204 /* The above doesn't preserve dominance info if available. */
3205 gcc_assert (!dom_info_available_p (CDI_DOMINATORS
));
3206 calculate_dominance_info (CDI_DOMINATORS
);
3207 fix_loop_structure (NULL
);
3208 free_dominance_info (CDI_DOMINATORS
);
3209 timevar_pop (TV_REPAIR_LOOPS
);
3212 timevar_pop (TV_CLEANUP_CFG
);
3219 const pass_data pass_data_jump
=
3221 RTL_PASS
, /* type */
3223 OPTGROUP_NONE
, /* optinfo_flags */
3224 TV_JUMP
, /* tv_id */
3225 0, /* properties_required */
3226 0, /* properties_provided */
3227 0, /* properties_destroyed */
3228 0, /* todo_flags_start */
3229 0, /* todo_flags_finish */
3232 class pass_jump
: public rtl_opt_pass
3235 pass_jump (gcc::context
*ctxt
)
3236 : rtl_opt_pass (pass_data_jump
, ctxt
)
3239 /* opt_pass methods: */
3240 virtual unsigned int execute (function
*);
3242 }; // class pass_jump
3245 pass_jump::execute (function
*)
3247 delete_trivially_dead_insns (get_insns (), max_reg_num ());
3249 dump_flow_info (dump_file
, dump_flags
);
3250 cleanup_cfg ((optimize
? CLEANUP_EXPENSIVE
: 0)
3251 | (flag_thread_jumps
? CLEANUP_THREADING
: 0));
3258 make_pass_jump (gcc::context
*ctxt
)
3260 return new pass_jump (ctxt
);
3265 const pass_data pass_data_postreload_jump
=
3267 RTL_PASS
, /* type */
3268 "postreload_jump", /* name */
3269 OPTGROUP_NONE
, /* optinfo_flags */
3270 TV_JUMP
, /* tv_id */
3271 0, /* properties_required */
3272 0, /* properties_provided */
3273 0, /* properties_destroyed */
3274 0, /* todo_flags_start */
3275 0, /* todo_flags_finish */
3278 class pass_postreload_jump
: public rtl_opt_pass
3281 pass_postreload_jump (gcc::context
*ctxt
)
3282 : rtl_opt_pass (pass_data_postreload_jump
, ctxt
)
3285 /* opt_pass methods: */
3286 virtual unsigned int execute (function
*);
3288 }; // class pass_postreload_jump
3291 pass_postreload_jump::execute (function
*)
3293 cleanup_cfg (flag_thread_jumps
? CLEANUP_THREADING
: 0);
3300 make_pass_postreload_jump (gcc::context
*ctxt
)
3302 return new pass_postreload_jump (ctxt
);
3307 const pass_data pass_data_jump2
=
3309 RTL_PASS
, /* type */
3311 OPTGROUP_NONE
, /* optinfo_flags */
3312 TV_JUMP
, /* tv_id */
3313 0, /* properties_required */
3314 0, /* properties_provided */
3315 0, /* properties_destroyed */
3316 0, /* todo_flags_start */
3317 0, /* todo_flags_finish */
3320 class pass_jump2
: public rtl_opt_pass
3323 pass_jump2 (gcc::context
*ctxt
)
3324 : rtl_opt_pass (pass_data_jump2
, ctxt
)
3327 /* opt_pass methods: */
3328 virtual unsigned int execute (function
*)
3330 cleanup_cfg (flag_crossjumping
? CLEANUP_CROSSJUMP
: 0);
3334 }; // class pass_jump2
3339 make_pass_jump2 (gcc::context
*ctxt
)
3341 return new pass_jump2 (ctxt
);