1 /* Control flow optimization code for GNU compiler.
2 Copyright (C) 1987-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file contains optimizer of the control flow. The main entry point is
21 cleanup_cfg. Following optimizations are performed:
23 - Unreachable blocks removal
24 - Edge forwarding (edge to the forwarder block is forwarded to its
25 successor. Simplification of the branch instruction is performed by
26 underlying infrastructure so branch can be converted to simplejump or
28 - Cross jumping (tail merging)
29 - Conditional jump-around-simplejump simplification
30 - Basic block merging. */
34 #include "coretypes.h"
38 #include "hard-reg-set.h"
40 #include "insn-config.h"
43 #include "diagnostic-core.h"
48 #include "function.h" /* For inline functions in emit-rtl.h they need crtl. */
50 #include "tree-pass.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_occured
;
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
, rtx
);
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 int mentions_nonequal_regs (rtx
*, void *);
84 static void merge_memattrs (rtx
, rtx
);
86 /* Set flags for newly created block. */
89 notice_new_block (basic_block bb
)
94 if (forwarder_block_p (bb
))
95 bb
->flags
|= BB_FORWARDER_BLOCK
;
98 /* Recompute forwarder flag after block has been modified. */
101 update_forwarder_flag (basic_block bb
)
103 if (forwarder_block_p (bb
))
104 bb
->flags
|= BB_FORWARDER_BLOCK
;
106 bb
->flags
&= ~BB_FORWARDER_BLOCK
;
109 /* Simplify a conditional jump around an unconditional jump.
110 Return true if something changed. */
113 try_simplify_condjump (basic_block cbranch_block
)
115 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
116 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
119 /* Verify that there are exactly two successors. */
120 if (EDGE_COUNT (cbranch_block
->succs
) != 2)
123 /* Verify that we've got a normal conditional branch at the end
125 cbranch_insn
= BB_END (cbranch_block
);
126 if (!any_condjump_p (cbranch_insn
))
129 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
130 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
132 /* The next block must not have multiple predecessors, must not
133 be the last block in the function, and must contain just the
134 unconditional jump. */
135 jump_block
= cbranch_fallthru_edge
->dest
;
136 if (!single_pred_p (jump_block
)
137 || jump_block
->next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
138 || !FORWARDER_BLOCK_P (jump_block
))
140 jump_dest_block
= single_succ (jump_block
);
142 /* If we are partitioning hot/cold basic blocks, we don't want to
143 mess up unconditional or indirect jumps that cross between hot
146 Basic block partitioning may result in some jumps that appear to
147 be optimizable (or blocks that appear to be mergeable), but which really
148 must be left untouched (they are required to make it safely across
149 partition boundaries). See the comments at the top of
150 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
152 if (BB_PARTITION (jump_block
) != BB_PARTITION (jump_dest_block
)
153 || (cbranch_jump_edge
->flags
& EDGE_CROSSING
))
156 /* The conditional branch must target the block after the
157 unconditional branch. */
158 cbranch_dest_block
= cbranch_jump_edge
->dest
;
160 if (cbranch_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 (cbranch_insn
, block_label (jump_dest_block
), 0))
169 fprintf (dump_file
, "Simplifying condjump %i around jump %i\n",
170 INSN_UID (cbranch_insn
), INSN_UID (BB_END (jump_block
)));
172 /* Success. Update the CFG to match. Note that after this point
173 the edge variable names appear backwards; the redirection is done
174 this way to preserve edge profile data. */
175 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
177 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
179 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
180 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
181 update_br_prob_note (cbranch_block
);
183 /* Delete the block with the unconditional jump, and clean up the mess. */
184 delete_basic_block (jump_block
);
185 tidy_fallthru_edge (cbranch_jump_edge
);
186 update_forwarder_flag (cbranch_block
);
191 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
192 on register. Used by jump threading. */
195 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 if (REG_P (XEXP (exp
, 0)))
206 dest
= XEXP (exp
, 0);
207 regno
= REGNO (dest
);
208 if (HARD_REGISTER_NUM_P (regno
))
209 bitmap_clear_range (nonequal
, regno
,
210 hard_regno_nregs
[regno
][GET_MODE (dest
)]);
212 bitmap_clear_bit (nonequal
, regno
);
217 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
219 dest
= SET_DEST (exp
);
224 regno
= REGNO (dest
);
225 if (HARD_REGISTER_NUM_P (regno
))
226 bitmap_set_range (nonequal
, regno
,
227 hard_regno_nregs
[regno
][GET_MODE (dest
)]);
229 bitmap_set_bit (nonequal
, regno
);
237 /* Return nonzero if X is a register set in regset DATA.
238 Called via for_each_rtx. */
240 mentions_nonequal_regs (rtx
*x
, void *data
)
242 regset nonequal
= (regset
) data
;
248 if (REGNO_REG_SET_P (nonequal
, regno
))
250 if (regno
< FIRST_PSEUDO_REGISTER
)
252 int n
= hard_regno_nregs
[regno
][GET_MODE (*x
)];
254 if (REGNO_REG_SET_P (nonequal
, regno
+ n
))
260 /* Attempt to prove that the basic block B will have no side effects and
261 always continues in the same edge if reached via E. Return the edge
262 if exist, NULL otherwise. */
265 thread_jump (edge e
, basic_block b
)
267 rtx set1
, set2
, cond1
, cond2
, insn
;
268 enum rtx_code code1
, code2
, reversed_code2
;
269 bool reverse1
= false;
273 reg_set_iterator rsi
;
275 if (b
->flags
& BB_NONTHREADABLE_BLOCK
)
278 /* At the moment, we do handle only conditional jumps, but later we may
279 want to extend this code to tablejumps and others. */
280 if (EDGE_COUNT (e
->src
->succs
) != 2)
282 if (EDGE_COUNT (b
->succs
) != 2)
284 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
288 /* Second branch must end with onlyjump, as we will eliminate the jump. */
289 if (!any_condjump_p (BB_END (e
->src
)))
292 if (!any_condjump_p (BB_END (b
)) || !onlyjump_p (BB_END (b
)))
294 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
298 set1
= pc_set (BB_END (e
->src
));
299 set2
= pc_set (BB_END (b
));
300 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
301 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
304 cond1
= XEXP (SET_SRC (set1
), 0);
305 cond2
= XEXP (SET_SRC (set2
), 0);
307 code1
= reversed_comparison_code (cond1
, BB_END (e
->src
));
309 code1
= GET_CODE (cond1
);
311 code2
= GET_CODE (cond2
);
312 reversed_code2
= reversed_comparison_code (cond2
, BB_END (b
));
314 if (!comparison_dominates_p (code1
, code2
)
315 && !comparison_dominates_p (code1
, reversed_code2
))
318 /* Ensure that the comparison operators are equivalent.
319 ??? This is far too pessimistic. We should allow swapped operands,
320 different CCmodes, or for example comparisons for interval, that
321 dominate even when operands are not equivalent. */
322 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
323 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
326 /* Short circuit cases where block B contains some side effects, as we can't
328 for (insn
= NEXT_INSN (BB_HEAD (b
)); insn
!= NEXT_INSN (BB_END (b
));
329 insn
= NEXT_INSN (insn
))
330 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
332 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
338 /* First process all values computed in the source basic block. */
339 for (insn
= NEXT_INSN (BB_HEAD (e
->src
));
340 insn
!= NEXT_INSN (BB_END (e
->src
));
341 insn
= NEXT_INSN (insn
))
343 cselib_process_insn (insn
);
345 nonequal
= BITMAP_ALLOC (NULL
);
346 CLEAR_REG_SET (nonequal
);
348 /* Now assume that we've continued by the edge E to B and continue
349 processing as if it were same basic block.
350 Our goal is to prove that whole block is an NOOP. */
352 for (insn
= NEXT_INSN (BB_HEAD (b
));
353 insn
!= NEXT_INSN (BB_END (b
)) && !failed
;
354 insn
= NEXT_INSN (insn
))
358 rtx pat
= PATTERN (insn
);
360 if (GET_CODE (pat
) == PARALLEL
)
362 for (i
= 0; i
< (unsigned)XVECLEN (pat
, 0); i
++)
363 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
366 failed
|= mark_effect (pat
, nonequal
);
369 cselib_process_insn (insn
);
372 /* Later we should clear nonequal of dead registers. So far we don't
373 have life information in cfg_cleanup. */
376 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
380 /* cond2 must not mention any register that is not equal to the
382 if (for_each_rtx (&cond2
, mentions_nonequal_regs
, nonequal
))
385 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, rsi
)
388 BITMAP_FREE (nonequal
);
390 if ((comparison_dominates_p (code1
, code2
) != 0)
391 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
392 return BRANCH_EDGE (b
);
394 return FALLTHRU_EDGE (b
);
397 BITMAP_FREE (nonequal
);
402 /* Attempt to forward edges leaving basic block B.
403 Return true if successful. */
406 try_forward_edges (int mode
, basic_block b
)
408 bool changed
= false;
410 edge e
, *threaded_edges
= NULL
;
412 /* If we are partitioning hot/cold basic blocks, we don't want to
413 mess up unconditional or indirect jumps that cross between hot
416 Basic block partitioning may result in some jumps that appear to
417 be optimizable (or blocks that appear to be mergeable), but which really
418 must be left untouched (they are required to make it safely across
419 partition boundaries). See the comments at the top of
420 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
422 if (find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
425 for (ei
= ei_start (b
->succs
); (e
= ei_safe_edge (ei
)); )
427 basic_block target
, first
;
428 int counter
, goto_locus
;
429 bool threaded
= false;
430 int nthreaded_edges
= 0;
431 bool may_thread
= first_pass
|| (b
->flags
& BB_MODIFIED
) != 0;
433 /* Skip complex edges because we don't know how to update them.
435 Still handle fallthru edges, as we can succeed to forward fallthru
436 edge to the same place as the branch edge of conditional branch
437 and turn conditional branch to an unconditional branch. */
438 if (e
->flags
& EDGE_COMPLEX
)
444 target
= first
= e
->dest
;
445 counter
= NUM_FIXED_BLOCKS
;
446 goto_locus
= e
->goto_locus
;
448 /* If we are partitioning hot/cold basic_blocks, we don't want to mess
449 up jumps that cross between hot/cold sections.
451 Basic block partitioning may result in some jumps that appear
452 to be optimizable (or blocks that appear to be mergeable), but which
453 really must be left untouched (they are required to make it safely
454 across partition boundaries). See the comments at the top of
455 bb-reorder.c:partition_hot_cold_basic_blocks for complete
458 if (first
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
459 && find_reg_note (BB_END (first
), REG_CROSSING_JUMP
, NULL_RTX
))
462 while (counter
< n_basic_blocks_for_fn (cfun
))
464 basic_block new_target
= NULL
;
465 bool new_target_threaded
= false;
466 may_thread
|= (target
->flags
& BB_MODIFIED
) != 0;
468 if (FORWARDER_BLOCK_P (target
)
469 && !(single_succ_edge (target
)->flags
& EDGE_CROSSING
)
470 && single_succ (target
) != EXIT_BLOCK_PTR_FOR_FN (cfun
))
472 /* Bypass trivial infinite loops. */
473 new_target
= single_succ (target
);
474 if (target
== new_target
)
475 counter
= n_basic_blocks_for_fn (cfun
);
478 /* When not optimizing, ensure that edges or forwarder
479 blocks with different locus are not optimized out. */
480 int new_locus
= single_succ_edge (target
)->goto_locus
;
481 int locus
= goto_locus
;
483 if (new_locus
!= UNKNOWN_LOCATION
484 && locus
!= UNKNOWN_LOCATION
485 && new_locus
!= locus
)
491 if (new_locus
!= UNKNOWN_LOCATION
)
494 last
= BB_END (target
);
495 if (DEBUG_INSN_P (last
))
496 last
= prev_nondebug_insn (last
);
498 new_locus
= last
&& INSN_P (last
)
499 ? INSN_LOCATION (last
) : 0;
501 if (new_locus
!= UNKNOWN_LOCATION
502 && locus
!= UNKNOWN_LOCATION
503 && new_locus
!= locus
)
507 if (new_locus
!= UNKNOWN_LOCATION
)
516 /* Allow to thread only over one edge at time to simplify updating
518 else if ((mode
& CLEANUP_THREADING
) && may_thread
)
520 edge t
= thread_jump (e
, target
);
524 threaded_edges
= XNEWVEC (edge
,
525 n_basic_blocks_for_fn (cfun
));
530 /* Detect an infinite loop across blocks not
531 including the start block. */
532 for (i
= 0; i
< nthreaded_edges
; ++i
)
533 if (threaded_edges
[i
] == t
)
535 if (i
< nthreaded_edges
)
537 counter
= n_basic_blocks_for_fn (cfun
);
542 /* Detect an infinite loop across the start block. */
546 gcc_assert (nthreaded_edges
547 < (n_basic_blocks_for_fn (cfun
)
548 - NUM_FIXED_BLOCKS
));
549 threaded_edges
[nthreaded_edges
++] = t
;
551 new_target
= t
->dest
;
552 new_target_threaded
= true;
561 threaded
|= new_target_threaded
;
564 if (counter
>= n_basic_blocks_for_fn (cfun
))
567 fprintf (dump_file
, "Infinite loop in BB %i.\n",
570 else if (target
== first
)
571 ; /* We didn't do anything. */
574 /* Save the values now, as the edge may get removed. */
575 gcov_type edge_count
= e
->count
;
576 int edge_probability
= e
->probability
;
580 e
->goto_locus
= goto_locus
;
582 /* Don't force if target is exit block. */
583 if (threaded
&& target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
585 notice_new_block (redirect_edge_and_branch_force (e
, target
));
587 fprintf (dump_file
, "Conditionals threaded.\n");
589 else if (!redirect_edge_and_branch (e
, target
))
593 "Forwarding edge %i->%i to %i failed.\n",
594 b
->index
, e
->dest
->index
, target
->index
);
599 /* We successfully forwarded the edge. Now update profile
600 data: for each edge we traversed in the chain, remove
601 the original edge's execution count. */
602 edge_frequency
= apply_probability (b
->frequency
, edge_probability
);
608 if (!single_succ_p (first
))
610 gcc_assert (n
< nthreaded_edges
);
611 t
= threaded_edges
[n
++];
612 gcc_assert (t
->src
== first
);
613 update_bb_profile_for_threading (first
, edge_frequency
,
615 update_br_prob_note (first
);
619 first
->count
-= edge_count
;
620 if (first
->count
< 0)
622 first
->frequency
-= edge_frequency
;
623 if (first
->frequency
< 0)
624 first
->frequency
= 0;
625 /* It is possible that as the result of
626 threading we've removed edge as it is
627 threaded to the fallthru edge. Avoid
628 getting out of sync. */
629 if (n
< nthreaded_edges
630 && first
== threaded_edges
[n
]->src
)
632 t
= single_succ_edge (first
);
635 t
->count
-= edge_count
;
640 while (first
!= target
);
648 free (threaded_edges
);
653 /* Blocks A and B are to be merged into a single block. A has no incoming
654 fallthru edge, so it can be moved before B without adding or modifying
655 any jumps (aside from the jump from A to B). */
658 merge_blocks_move_predecessor_nojumps (basic_block a
, basic_block b
)
662 /* If we are partitioning hot/cold basic blocks, we don't want to
663 mess up unconditional or indirect jumps that cross between hot
666 Basic block partitioning may result in some jumps that appear to
667 be optimizable (or blocks that appear to be mergeable), but which really
668 must be left untouched (they are required to make it safely across
669 partition boundaries). See the comments at the top of
670 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
672 if (BB_PARTITION (a
) != BB_PARTITION (b
))
675 barrier
= next_nonnote_insn (BB_END (a
));
676 gcc_assert (BARRIER_P (barrier
));
677 delete_insn (barrier
);
679 /* Scramble the insn chain. */
680 if (BB_END (a
) != PREV_INSN (BB_HEAD (b
)))
681 reorder_insns_nobb (BB_HEAD (a
), BB_END (a
), PREV_INSN (BB_HEAD (b
)));
685 fprintf (dump_file
, "Moved block %d before %d and merged.\n",
688 /* Swap the records for the two blocks around. */
691 link_block (a
, b
->prev_bb
);
693 /* Now blocks A and B are contiguous. Merge them. */
697 /* Blocks A and B are to be merged into a single block. B has no outgoing
698 fallthru edge, so it can be moved after A without adding or modifying
699 any jumps (aside from the jump from A to B). */
702 merge_blocks_move_successor_nojumps (basic_block a
, basic_block b
)
704 rtx barrier
, real_b_end
;
707 /* If we are partitioning hot/cold basic blocks, we don't want to
708 mess up unconditional or indirect jumps that cross between hot
711 Basic block partitioning may result in some jumps that appear to
712 be optimizable (or blocks that appear to be mergeable), but which really
713 must be left untouched (they are required to make it safely across
714 partition boundaries). See the comments at the top of
715 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
717 if (BB_PARTITION (a
) != BB_PARTITION (b
))
720 real_b_end
= BB_END (b
);
722 /* If there is a jump table following block B temporarily add the jump table
723 to block B so that it will also be moved to the correct location. */
724 if (tablejump_p (BB_END (b
), &label
, &table
)
725 && prev_active_insn (label
) == BB_END (b
))
730 /* There had better have been a barrier there. Delete it. */
731 barrier
= NEXT_INSN (BB_END (b
));
732 if (barrier
&& BARRIER_P (barrier
))
733 delete_insn (barrier
);
736 /* Scramble the insn chain. */
737 reorder_insns_nobb (BB_HEAD (b
), BB_END (b
), BB_END (a
));
739 /* Restore the real end of b. */
740 BB_END (b
) = real_b_end
;
743 fprintf (dump_file
, "Moved block %d after %d and merged.\n",
746 /* Now blocks A and B are contiguous. Merge them. */
750 /* Attempt to merge basic blocks that are potentially non-adjacent.
751 Return NULL iff the attempt failed, otherwise return basic block
752 where cleanup_cfg should continue. Because the merging commonly
753 moves basic block away or introduces another optimization
754 possibility, return basic block just before B so cleanup_cfg don't
757 It may be good idea to return basic block before C in the case
758 C has been moved after B and originally appeared earlier in the
759 insn sequence, but we have no information available about the
760 relative ordering of these two. Hopefully it is not too common. */
763 merge_blocks_move (edge e
, basic_block b
, basic_block c
, int mode
)
767 /* If we are partitioning hot/cold basic blocks, we don't want to
768 mess up unconditional or indirect jumps that cross between hot
771 Basic block partitioning may result in some jumps that appear to
772 be optimizable (or blocks that appear to be mergeable), but which really
773 must be left untouched (they are required to make it safely across
774 partition boundaries). See the comments at the top of
775 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
777 if (BB_PARTITION (b
) != BB_PARTITION (c
))
780 /* If B has a fallthru edge to C, no need to move anything. */
781 if (e
->flags
& EDGE_FALLTHRU
)
783 int b_index
= b
->index
, c_index
= c
->index
;
785 /* Protect the loop latches. */
786 if (current_loops
&& c
->loop_father
->latch
== c
)
790 update_forwarder_flag (b
);
793 fprintf (dump_file
, "Merged %d and %d without moving.\n",
796 return b
->prev_bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) ? b
: b
->prev_bb
;
799 /* Otherwise we will need to move code around. Do that only if expensive
800 transformations are allowed. */
801 else if (mode
& CLEANUP_EXPENSIVE
)
803 edge tmp_edge
, b_fallthru_edge
;
804 bool c_has_outgoing_fallthru
;
805 bool b_has_incoming_fallthru
;
807 /* Avoid overactive code motion, as the forwarder blocks should be
808 eliminated by edge redirection instead. One exception might have
809 been if B is a forwarder block and C has no fallthru edge, but
810 that should be cleaned up by bb-reorder instead. */
811 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
814 /* We must make sure to not munge nesting of lexical blocks,
815 and loop notes. This is done by squeezing out all the notes
816 and leaving them there to lie. Not ideal, but functional. */
818 tmp_edge
= find_fallthru_edge (c
->succs
);
819 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
821 tmp_edge
= find_fallthru_edge (b
->preds
);
822 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
823 b_fallthru_edge
= tmp_edge
;
826 next
= next
->prev_bb
;
828 /* Otherwise, we're going to try to move C after B. If C does
829 not have an outgoing fallthru, then it can be moved
830 immediately after B without introducing or modifying jumps. */
831 if (! c_has_outgoing_fallthru
)
833 merge_blocks_move_successor_nojumps (b
, c
);
834 return next
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) ? next
->next_bb
: next
;
837 /* If B does not have an incoming fallthru, then it can be moved
838 immediately before C without introducing or modifying jumps.
839 C cannot be the first block, so we do not have to worry about
840 accessing a non-existent block. */
842 if (b_has_incoming_fallthru
)
846 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
848 bb
= force_nonfallthru (b_fallthru_edge
);
850 notice_new_block (bb
);
853 merge_blocks_move_predecessor_nojumps (b
, c
);
854 return next
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) ? next
->next_bb
: next
;
861 /* Removes the memory attributes of MEM expression
862 if they are not equal. */
865 merge_memattrs (rtx x
, rtx y
)
874 if (x
== 0 || y
== 0)
879 if (code
!= GET_CODE (y
))
882 if (GET_MODE (x
) != GET_MODE (y
))
885 if (code
== MEM
&& MEM_ATTRS (x
) != MEM_ATTRS (y
))
889 else if (! MEM_ATTRS (y
))
893 HOST_WIDE_INT mem_size
;
895 if (MEM_ALIAS_SET (x
) != MEM_ALIAS_SET (y
))
897 set_mem_alias_set (x
, 0);
898 set_mem_alias_set (y
, 0);
901 if (! mem_expr_equal_p (MEM_EXPR (x
), MEM_EXPR (y
)))
905 clear_mem_offset (x
);
906 clear_mem_offset (y
);
908 else if (MEM_OFFSET_KNOWN_P (x
) != MEM_OFFSET_KNOWN_P (y
)
909 || (MEM_OFFSET_KNOWN_P (x
)
910 && MEM_OFFSET (x
) != MEM_OFFSET (y
)))
912 clear_mem_offset (x
);
913 clear_mem_offset (y
);
916 if (MEM_SIZE_KNOWN_P (x
) && MEM_SIZE_KNOWN_P (y
))
918 mem_size
= MAX (MEM_SIZE (x
), MEM_SIZE (y
));
919 set_mem_size (x
, mem_size
);
920 set_mem_size (y
, mem_size
);
928 set_mem_align (x
, MIN (MEM_ALIGN (x
), MEM_ALIGN (y
)));
929 set_mem_align (y
, MEM_ALIGN (x
));
934 if (MEM_READONLY_P (x
) != MEM_READONLY_P (y
))
936 MEM_READONLY_P (x
) = 0;
937 MEM_READONLY_P (y
) = 0;
939 if (MEM_NOTRAP_P (x
) != MEM_NOTRAP_P (y
))
941 MEM_NOTRAP_P (x
) = 0;
942 MEM_NOTRAP_P (y
) = 0;
944 if (MEM_VOLATILE_P (x
) != MEM_VOLATILE_P (y
))
946 MEM_VOLATILE_P (x
) = 1;
947 MEM_VOLATILE_P (y
) = 1;
951 fmt
= GET_RTX_FORMAT (code
);
952 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
957 /* Two vectors must have the same length. */
958 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
961 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
962 merge_memattrs (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
));
967 merge_memattrs (XEXP (x
, i
), XEXP (y
, i
));
974 /* Checks if patterns P1 and P2 are equivalent, apart from the possibly
975 different single sets S1 and S2. */
978 equal_different_set_p (rtx p1
, rtx s1
, rtx p2
, rtx s2
)
983 if (p1
== s1
&& p2
== s2
)
986 if (GET_CODE (p1
) != PARALLEL
|| GET_CODE (p2
) != PARALLEL
)
989 if (XVECLEN (p1
, 0) != XVECLEN (p2
, 0))
992 for (i
= 0; i
< XVECLEN (p1
, 0); i
++)
994 e1
= XVECEXP (p1
, 0, i
);
995 e2
= XVECEXP (p2
, 0, i
);
996 if (e1
== s1
&& e2
== s2
)
999 ? rtx_renumbered_equal_p (e1
, e2
) : rtx_equal_p (e1
, e2
))
1008 /* Examine register notes on I1 and I2 and return:
1009 - dir_forward if I1 can be replaced by I2, or
1010 - dir_backward if I2 can be replaced by I1, or
1011 - dir_both if both are the case. */
1013 static enum replace_direction
1014 can_replace_by (rtx i1
, rtx i2
)
1016 rtx s1
, s2
, d1
, d2
, src1
, src2
, note1
, note2
;
1019 /* Check for 2 sets. */
1020 s1
= single_set (i1
);
1021 s2
= single_set (i2
);
1022 if (s1
== NULL_RTX
|| s2
== NULL_RTX
)
1025 /* Check that the 2 sets set the same dest. */
1028 if (!(reload_completed
1029 ? rtx_renumbered_equal_p (d1
, d2
) : rtx_equal_p (d1
, d2
)))
1032 /* Find identical req_equiv or reg_equal note, which implies that the 2 sets
1033 set dest to the same value. */
1034 note1
= find_reg_equal_equiv_note (i1
);
1035 note2
= find_reg_equal_equiv_note (i2
);
1036 if (!note1
|| !note2
|| !rtx_equal_p (XEXP (note1
, 0), XEXP (note2
, 0))
1037 || !CONST_INT_P (XEXP (note1
, 0)))
1040 if (!equal_different_set_p (PATTERN (i1
), s1
, PATTERN (i2
), s2
))
1043 /* Although the 2 sets set dest to the same value, we cannot replace
1044 (set (dest) (const_int))
1047 because we don't know if the reg is live and has the same value at the
1048 location of replacement. */
1049 src1
= SET_SRC (s1
);
1050 src2
= SET_SRC (s2
);
1051 c1
= CONST_INT_P (src1
);
1052 c2
= CONST_INT_P (src2
);
1058 return dir_backward
;
1063 /* Merges directions A and B. */
1065 static enum replace_direction
1066 merge_dir (enum replace_direction a
, enum replace_direction b
)
1068 /* Implements the following table:
1087 /* Examine I1 and I2 and return:
1088 - dir_forward if I1 can be replaced by I2, or
1089 - dir_backward if I2 can be replaced by I1, or
1090 - dir_both if both are the case. */
1092 static enum replace_direction
1093 old_insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx i1
, rtx i2
)
1097 /* Verify that I1 and I2 are equivalent. */
1098 if (GET_CODE (i1
) != GET_CODE (i2
))
1101 /* __builtin_unreachable() may lead to empty blocks (ending with
1102 NOTE_INSN_BASIC_BLOCK). They may be crossjumped. */
1103 if (NOTE_INSN_BASIC_BLOCK_P (i1
) && NOTE_INSN_BASIC_BLOCK_P (i2
))
1106 /* ??? Do not allow cross-jumping between different stack levels. */
1107 p1
= find_reg_note (i1
, REG_ARGS_SIZE
, NULL
);
1108 p2
= find_reg_note (i2
, REG_ARGS_SIZE
, NULL
);
1113 if (!rtx_equal_p (p1
, p2
))
1116 /* ??? Worse, this adjustment had better be constant lest we
1117 have differing incoming stack levels. */
1118 if (!frame_pointer_needed
1119 && find_args_size_adjust (i1
) == HOST_WIDE_INT_MIN
)
1128 if (GET_CODE (p1
) != GET_CODE (p2
))
1131 /* If this is a CALL_INSN, compare register usage information.
1132 If we don't check this on stack register machines, the two
1133 CALL_INSNs might be merged leaving reg-stack.c with mismatching
1134 numbers of stack registers in the same basic block.
1135 If we don't check this on machines with delay slots, a delay slot may
1136 be filled that clobbers a parameter expected by the subroutine.
1138 ??? We take the simple route for now and assume that if they're
1139 equal, they were constructed identically.
1141 Also check for identical exception regions. */
1145 /* Ensure the same EH region. */
1146 rtx n1
= find_reg_note (i1
, REG_EH_REGION
, 0);
1147 rtx n2
= find_reg_note (i2
, REG_EH_REGION
, 0);
1152 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1155 if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
1156 CALL_INSN_FUNCTION_USAGE (i2
))
1157 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
))
1160 /* For address sanitizer, never crossjump __asan_report_* builtins,
1161 otherwise errors might be reported on incorrect lines. */
1162 if (flag_sanitize
& SANITIZE_ADDRESS
)
1164 rtx call
= get_call_rtx_from (i1
);
1165 if (call
&& GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
1167 rtx symbol
= XEXP (XEXP (call
, 0), 0);
1168 if (SYMBOL_REF_DECL (symbol
)
1169 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
1171 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
1173 && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
))
1174 >= BUILT_IN_ASAN_REPORT_LOAD1
1175 && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
))
1176 <= BUILT_IN_ASAN_REPORT_STORE16
)
1184 /* If cross_jump_death_matters is not 0, the insn's mode
1185 indicates whether or not the insn contains any stack-like
1188 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
1190 /* If register stack conversion has already been done, then
1191 death notes must also be compared before it is certain that
1192 the two instruction streams match. */
1195 HARD_REG_SET i1_regset
, i2_regset
;
1197 CLEAR_HARD_REG_SET (i1_regset
);
1198 CLEAR_HARD_REG_SET (i2_regset
);
1200 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
1201 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1202 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
1204 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
1205 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1206 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
1208 if (!hard_reg_set_equal_p (i1_regset
, i2_regset
))
1213 if (reload_completed
1214 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
1217 return can_replace_by (i1
, i2
);
1220 /* When comparing insns I1 and I2 in flow_find_cross_jump or
1221 flow_find_head_matching_sequence, ensure the notes match. */
1224 merge_notes (rtx i1
, rtx i2
)
1226 /* If the merged insns have different REG_EQUAL notes, then
1228 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1229 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1231 if (equiv1
&& !equiv2
)
1232 remove_note (i1
, equiv1
);
1233 else if (!equiv1
&& equiv2
)
1234 remove_note (i2
, equiv2
);
1235 else if (equiv1
&& equiv2
1236 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1238 remove_note (i1
, equiv1
);
1239 remove_note (i2
, equiv2
);
1243 /* Walks from I1 in BB1 backward till the next non-debug insn, and returns the
1244 resulting insn in I1, and the corresponding bb in BB1. At the head of a
1245 bb, if there is a predecessor bb that reaches this bb via fallthru, and
1246 FOLLOW_FALLTHRU, walks further in the predecessor bb and registers this in
1247 DID_FALLTHRU. Otherwise, stops at the head of the bb. */
1250 walk_to_nondebug_insn (rtx
*i1
, basic_block
*bb1
, bool follow_fallthru
,
1255 *did_fallthru
= false;
1258 while (!NONDEBUG_INSN_P (*i1
))
1260 if (*i1
!= BB_HEAD (*bb1
))
1262 *i1
= PREV_INSN (*i1
);
1266 if (!follow_fallthru
)
1269 fallthru
= find_fallthru_edge ((*bb1
)->preds
);
1270 if (!fallthru
|| fallthru
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1271 || !single_succ_p (fallthru
->src
))
1274 *bb1
= fallthru
->src
;
1275 *i1
= BB_END (*bb1
);
1276 *did_fallthru
= true;
1280 /* Look through the insns at the end of BB1 and BB2 and find the longest
1281 sequence that are either equivalent, or allow forward or backward
1282 replacement. Store the first insns for that sequence in *F1 and *F2 and
1283 return the sequence length.
1285 DIR_P indicates the allowed replacement direction on function entry, and
1286 the actual replacement direction on function exit. If NULL, only equivalent
1287 sequences are allowed.
1289 To simplify callers of this function, if the blocks match exactly,
1290 store the head of the blocks in *F1 and *F2. */
1293 flow_find_cross_jump (basic_block bb1
, basic_block bb2
, rtx
*f1
, rtx
*f2
,
1294 enum replace_direction
*dir_p
)
1296 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
1299 enum replace_direction dir
, last_dir
, afterlast_dir
;
1300 bool follow_fallthru
, did_fallthru
;
1306 afterlast_dir
= dir
;
1307 last_dir
= afterlast_dir
;
1309 /* Skip simple jumps at the end of the blocks. Complex jumps still
1310 need to be compared for equivalence, which we'll do below. */
1313 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
1315 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1318 i1
= PREV_INSN (i1
);
1323 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1326 /* Count everything except for unconditional jump as insn. */
1327 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1329 i2
= PREV_INSN (i2
);
1334 /* In the following example, we can replace all jumps to C by jumps to A.
1336 This removes 4 duplicate insns.
1337 [bb A] insn1 [bb C] insn1
1343 We could also replace all jumps to A by jumps to C, but that leaves B
1344 alive, and removes only 2 duplicate insns. In a subsequent crossjump
1345 step, all jumps to B would be replaced with jumps to the middle of C,
1346 achieving the same result with more effort.
1347 So we allow only the first possibility, which means that we don't allow
1348 fallthru in the block that's being replaced. */
1350 follow_fallthru
= dir_p
&& dir
!= dir_forward
;
1351 walk_to_nondebug_insn (&i1
, &bb1
, follow_fallthru
, &did_fallthru
);
1355 follow_fallthru
= dir_p
&& dir
!= dir_backward
;
1356 walk_to_nondebug_insn (&i2
, &bb2
, follow_fallthru
, &did_fallthru
);
1360 if (i1
== BB_HEAD (bb1
) || i2
== BB_HEAD (bb2
))
1363 dir
= merge_dir (dir
, old_insns_match_p (0, i1
, i2
));
1364 if (dir
== dir_none
|| (!dir_p
&& dir
!= dir_both
))
1367 merge_memattrs (i1
, i2
);
1369 /* Don't begin a cross-jump with a NOTE insn. */
1372 merge_notes (i1
, i2
);
1374 afterlast1
= last1
, afterlast2
= last2
;
1375 last1
= i1
, last2
= i2
;
1376 afterlast_dir
= last_dir
;
1379 if (!(GET_CODE (p1
) == USE
|| GET_CODE (p1
) == CLOBBER
))
1383 i1
= PREV_INSN (i1
);
1384 i2
= PREV_INSN (i2
);
1388 /* Don't allow the insn after a compare to be shared by
1389 cross-jumping unless the compare is also shared. */
1390 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1391 last1
= afterlast1
, last2
= afterlast2
, last_dir
= afterlast_dir
, ninsns
--;
1394 /* Include preceding notes and labels in the cross-jump. One,
1395 this may bring us to the head of the blocks as requested above.
1396 Two, it keeps line number notes as matched as may be. */
1399 bb1
= BLOCK_FOR_INSN (last1
);
1400 while (last1
!= BB_HEAD (bb1
) && !NONDEBUG_INSN_P (PREV_INSN (last1
)))
1401 last1
= PREV_INSN (last1
);
1403 if (last1
!= BB_HEAD (bb1
) && LABEL_P (PREV_INSN (last1
)))
1404 last1
= PREV_INSN (last1
);
1406 bb2
= BLOCK_FOR_INSN (last2
);
1407 while (last2
!= BB_HEAD (bb2
) && !NONDEBUG_INSN_P (PREV_INSN (last2
)))
1408 last2
= PREV_INSN (last2
);
1410 if (last2
!= BB_HEAD (bb2
) && LABEL_P (PREV_INSN (last2
)))
1411 last2
= PREV_INSN (last2
);
1422 /* Like flow_find_cross_jump, except start looking for a matching sequence from
1423 the head of the two blocks. Do not include jumps at the end.
1424 If STOP_AFTER is nonzero, stop after finding that many matching
1428 flow_find_head_matching_sequence (basic_block bb1
, basic_block bb2
, rtx
*f1
,
1429 rtx
*f2
, int stop_after
)
1431 rtx i1
, i2
, last1
, last2
, beforelast1
, beforelast2
;
1435 int nehedges1
= 0, nehedges2
= 0;
1437 FOR_EACH_EDGE (e
, ei
, bb1
->succs
)
1438 if (e
->flags
& EDGE_EH
)
1440 FOR_EACH_EDGE (e
, ei
, bb2
->succs
)
1441 if (e
->flags
& EDGE_EH
)
1446 last1
= beforelast1
= last2
= beforelast2
= NULL_RTX
;
1450 /* Ignore notes, except NOTE_INSN_EPILOGUE_BEG. */
1451 while (!NONDEBUG_INSN_P (i1
) && i1
!= BB_END (bb1
))
1453 if (NOTE_P (i1
) && NOTE_KIND (i1
) == NOTE_INSN_EPILOGUE_BEG
)
1455 i1
= NEXT_INSN (i1
);
1458 while (!NONDEBUG_INSN_P (i2
) && i2
!= BB_END (bb2
))
1460 if (NOTE_P (i2
) && NOTE_KIND (i2
) == NOTE_INSN_EPILOGUE_BEG
)
1462 i2
= NEXT_INSN (i2
);
1465 if ((i1
== BB_END (bb1
) && !NONDEBUG_INSN_P (i1
))
1466 || (i2
== BB_END (bb2
) && !NONDEBUG_INSN_P (i2
)))
1469 if (NOTE_P (i1
) || NOTE_P (i2
)
1470 || JUMP_P (i1
) || JUMP_P (i2
))
1473 /* A sanity check to make sure we're not merging insns with different
1474 effects on EH. If only one of them ends a basic block, it shouldn't
1475 have an EH edge; if both end a basic block, there should be the same
1476 number of EH edges. */
1477 if ((i1
== BB_END (bb1
) && i2
!= BB_END (bb2
)
1479 || (i2
== BB_END (bb2
) && i1
!= BB_END (bb1
)
1481 || (i1
== BB_END (bb1
) && i2
== BB_END (bb2
)
1482 && nehedges1
!= nehedges2
))
1485 if (old_insns_match_p (0, i1
, i2
) != dir_both
)
1488 merge_memattrs (i1
, i2
);
1490 /* Don't begin a cross-jump with a NOTE insn. */
1493 merge_notes (i1
, i2
);
1495 beforelast1
= last1
, beforelast2
= last2
;
1496 last1
= i1
, last2
= i2
;
1500 if (i1
== BB_END (bb1
) || i2
== BB_END (bb2
)
1501 || (stop_after
> 0 && ninsns
== stop_after
))
1504 i1
= NEXT_INSN (i1
);
1505 i2
= NEXT_INSN (i2
);
1509 /* Don't allow a compare to be shared by cross-jumping unless the insn
1510 after the compare is also shared. */
1511 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && sets_cc0_p (last1
))
1512 last1
= beforelast1
, last2
= beforelast2
, ninsns
--;
1524 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1525 the branch instruction. This means that if we commonize the control
1526 flow before end of the basic block, the semantic remains unchanged.
1528 We may assume that there exists one edge with a common destination. */
1531 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1533 int nehedges1
= 0, nehedges2
= 0;
1534 edge fallthru1
= 0, fallthru2
= 0;
1538 /* If we performed shrink-wrapping, edges to the exit block can
1539 only be distinguished for JUMP_INSNs. The two paths may differ in
1540 whether they went through the prologue. Sibcalls are fine, we know
1541 that we either didn't need or inserted an epilogue before them. */
1542 if (crtl
->shrink_wrapped
1543 && single_succ_p (bb1
)
1544 && single_succ (bb1
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
1545 && !JUMP_P (BB_END (bb1
))
1546 && !(CALL_P (BB_END (bb1
)) && SIBLING_CALL_P (BB_END (bb1
))))
1549 /* If BB1 has only one successor, we may be looking at either an
1550 unconditional jump, or a fake edge to exit. */
1551 if (single_succ_p (bb1
)
1552 && (single_succ_edge (bb1
)->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1553 && (!JUMP_P (BB_END (bb1
)) || simplejump_p (BB_END (bb1
))))
1554 return (single_succ_p (bb2
)
1555 && (single_succ_edge (bb2
)->flags
1556 & (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1557 && (!JUMP_P (BB_END (bb2
)) || simplejump_p (BB_END (bb2
))));
1559 /* Match conditional jumps - this may get tricky when fallthru and branch
1560 edges are crossed. */
1561 if (EDGE_COUNT (bb1
->succs
) == 2
1562 && any_condjump_p (BB_END (bb1
))
1563 && onlyjump_p (BB_END (bb1
)))
1565 edge b1
, f1
, b2
, f2
;
1566 bool reverse
, match
;
1567 rtx set1
, set2
, cond1
, cond2
;
1568 enum rtx_code code1
, code2
;
1570 if (EDGE_COUNT (bb2
->succs
) != 2
1571 || !any_condjump_p (BB_END (bb2
))
1572 || !onlyjump_p (BB_END (bb2
)))
1575 b1
= BRANCH_EDGE (bb1
);
1576 b2
= BRANCH_EDGE (bb2
);
1577 f1
= FALLTHRU_EDGE (bb1
);
1578 f2
= FALLTHRU_EDGE (bb2
);
1580 /* Get around possible forwarders on fallthru edges. Other cases
1581 should be optimized out already. */
1582 if (FORWARDER_BLOCK_P (f1
->dest
))
1583 f1
= single_succ_edge (f1
->dest
);
1585 if (FORWARDER_BLOCK_P (f2
->dest
))
1586 f2
= single_succ_edge (f2
->dest
);
1588 /* To simplify use of this function, return false if there are
1589 unneeded forwarder blocks. These will get eliminated later
1590 during cleanup_cfg. */
1591 if (FORWARDER_BLOCK_P (f1
->dest
)
1592 || FORWARDER_BLOCK_P (f2
->dest
)
1593 || FORWARDER_BLOCK_P (b1
->dest
)
1594 || FORWARDER_BLOCK_P (b2
->dest
))
1597 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1599 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1604 set1
= pc_set (BB_END (bb1
));
1605 set2
= pc_set (BB_END (bb2
));
1606 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1607 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1610 cond1
= XEXP (SET_SRC (set1
), 0);
1611 cond2
= XEXP (SET_SRC (set2
), 0);
1612 code1
= GET_CODE (cond1
);
1614 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
1616 code2
= GET_CODE (cond2
);
1618 if (code2
== UNKNOWN
)
1621 /* Verify codes and operands match. */
1622 match
= ((code1
== code2
1623 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1624 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1625 || (code1
== swap_condition (code2
)
1626 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1628 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1631 /* If we return true, we will join the blocks. Which means that
1632 we will only have one branch prediction bit to work with. Thus
1633 we require the existing branches to have probabilities that are
1636 && optimize_bb_for_speed_p (bb1
)
1637 && optimize_bb_for_speed_p (bb2
))
1641 if (b1
->dest
== b2
->dest
)
1642 prob2
= b2
->probability
;
1644 /* Do not use f2 probability as f2 may be forwarded. */
1645 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1647 /* Fail if the difference in probabilities is greater than 50%.
1648 This rules out two well-predicted branches with opposite
1650 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1654 "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
1655 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1661 if (dump_file
&& match
)
1662 fprintf (dump_file
, "Conditionals in bb %i and %i match.\n",
1663 bb1
->index
, bb2
->index
);
1668 /* Generic case - we are seeing a computed jump, table jump or trapping
1671 /* Check whether there are tablejumps in the end of BB1 and BB2.
1672 Return true if they are identical. */
1677 if (tablejump_p (BB_END (bb1
), &label1
, &table1
)
1678 && tablejump_p (BB_END (bb2
), &label2
, &table2
)
1679 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1681 /* The labels should never be the same rtx. If they really are same
1682 the jump tables are same too. So disable crossjumping of blocks BB1
1683 and BB2 because when deleting the common insns in the end of BB1
1684 by delete_basic_block () the jump table would be deleted too. */
1685 /* If LABEL2 is referenced in BB1->END do not do anything
1686 because we would loose information when replacing
1687 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1688 if (label1
!= label2
&& !rtx_referenced_p (label2
, BB_END (bb1
)))
1690 /* Set IDENTICAL to true when the tables are identical. */
1691 bool identical
= false;
1694 p1
= PATTERN (table1
);
1695 p2
= PATTERN (table2
);
1696 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1700 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1701 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1702 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1703 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1708 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1709 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1715 replace_label_data rr
;
1718 /* Temporarily replace references to LABEL1 with LABEL2
1719 in BB1->END so that we could compare the instructions. */
1722 rr
.update_label_nuses
= false;
1723 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1725 match
= (old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
))
1727 if (dump_file
&& match
)
1729 "Tablejumps in bb %i and %i match.\n",
1730 bb1
->index
, bb2
->index
);
1732 /* Set the original label in BB1->END because when deleting
1733 a block whose end is a tablejump, the tablejump referenced
1734 from the instruction is deleted too. */
1737 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1746 /* Find the last non-debug non-note instruction in each bb, except
1747 stop when we see the NOTE_INSN_BASIC_BLOCK, as old_insns_match_p
1748 handles that case specially. old_insns_match_p does not handle
1749 other types of instruction notes. */
1750 rtx last1
= BB_END (bb1
);
1751 rtx last2
= BB_END (bb2
);
1752 while (!NOTE_INSN_BASIC_BLOCK_P (last1
) &&
1753 (DEBUG_INSN_P (last1
) || NOTE_P (last1
)))
1754 last1
= PREV_INSN (last1
);
1755 while (!NOTE_INSN_BASIC_BLOCK_P (last2
) &&
1756 (DEBUG_INSN_P (last2
) || NOTE_P (last2
)))
1757 last2
= PREV_INSN (last2
);
1758 gcc_assert (last1
&& last2
);
1760 /* First ensure that the instructions match. There may be many outgoing
1761 edges so this test is generally cheaper. */
1762 if (old_insns_match_p (mode
, last1
, last2
) != dir_both
)
1765 /* Search the outgoing edges, ensure that the counts do match, find possible
1766 fallthru and exception handling edges since these needs more
1768 if (EDGE_COUNT (bb1
->succs
) != EDGE_COUNT (bb2
->succs
))
1771 bool nonfakeedges
= false;
1772 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1774 e2
= EDGE_SUCC (bb2
, ei
.index
);
1776 if ((e1
->flags
& EDGE_FAKE
) == 0)
1777 nonfakeedges
= true;
1779 if (e1
->flags
& EDGE_EH
)
1782 if (e2
->flags
& EDGE_EH
)
1785 if (e1
->flags
& EDGE_FALLTHRU
)
1787 if (e2
->flags
& EDGE_FALLTHRU
)
1791 /* If number of edges of various types does not match, fail. */
1792 if (nehedges1
!= nehedges2
1793 || (fallthru1
!= 0) != (fallthru2
!= 0))
1796 /* If !ACCUMULATE_OUTGOING_ARGS, bb1 (and bb2) have no successors
1797 and the last real insn doesn't have REG_ARGS_SIZE note, don't
1798 attempt to optimize, as the two basic blocks might have different
1799 REG_ARGS_SIZE depths. For noreturn calls and unconditional
1800 traps there should be REG_ARG_SIZE notes, they could be missing
1801 for __builtin_unreachable () uses though. */
1803 && !ACCUMULATE_OUTGOING_ARGS
1805 || !find_reg_note (last1
, REG_ARGS_SIZE
, NULL
)))
1808 /* fallthru edges must be forwarded to the same destination. */
1811 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1812 ? single_succ (fallthru1
->dest
): fallthru1
->dest
);
1813 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1814 ? single_succ (fallthru2
->dest
): fallthru2
->dest
);
1820 /* Ensure the same EH region. */
1822 rtx n1
= find_reg_note (BB_END (bb1
), REG_EH_REGION
, 0);
1823 rtx n2
= find_reg_note (BB_END (bb2
), REG_EH_REGION
, 0);
1828 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1832 /* The same checks as in try_crossjump_to_edge. It is required for RTL
1833 version of sequence abstraction. */
1834 FOR_EACH_EDGE (e1
, ei
, bb2
->succs
)
1838 basic_block d1
= e1
->dest
;
1840 if (FORWARDER_BLOCK_P (d1
))
1841 d1
= EDGE_SUCC (d1
, 0)->dest
;
1843 FOR_EACH_EDGE (e2
, ei
, bb1
->succs
)
1845 basic_block d2
= e2
->dest
;
1846 if (FORWARDER_BLOCK_P (d2
))
1847 d2
= EDGE_SUCC (d2
, 0)->dest
;
1859 /* Returns true if BB basic block has a preserve label. */
1862 block_has_preserve_label (basic_block bb
)
1866 && LABEL_PRESERVE_P (block_label (bb
)));
1869 /* E1 and E2 are edges with the same destination block. Search their
1870 predecessors for common code. If found, redirect control flow from
1871 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC (dir_forward),
1872 or the other way around (dir_backward). DIR specifies the allowed
1873 replacement direction. */
1876 try_crossjump_to_edge (int mode
, edge e1
, edge e2
,
1877 enum replace_direction dir
)
1880 basic_block src1
= e1
->src
, src2
= e2
->src
;
1881 basic_block redirect_to
, redirect_from
, to_remove
;
1882 basic_block osrc1
, osrc2
, redirect_edges_to
, tmp
;
1883 rtx newpos1
, newpos2
;
1887 newpos1
= newpos2
= NULL_RTX
;
1889 /* If we have partitioned hot/cold basic blocks, it is a bad idea
1890 to try this optimization.
1892 Basic block partitioning may result in some jumps that appear to
1893 be optimizable (or blocks that appear to be mergeable), but which really
1894 must be left untouched (they are required to make it safely across
1895 partition boundaries). See the comments at the top of
1896 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1898 if (crtl
->has_bb_partition
&& reload_completed
)
1901 /* Search backward through forwarder blocks. We don't need to worry
1902 about multiple entry or chained forwarders, as they will be optimized
1903 away. We do this to look past the unconditional jump following a
1904 conditional jump that is required due to the current CFG shape. */
1905 if (single_pred_p (src1
)
1906 && FORWARDER_BLOCK_P (src1
))
1907 e1
= single_pred_edge (src1
), src1
= e1
->src
;
1909 if (single_pred_p (src2
)
1910 && FORWARDER_BLOCK_P (src2
))
1911 e2
= single_pred_edge (src2
), src2
= e2
->src
;
1913 /* Nothing to do if we reach ENTRY, or a common source block. */
1914 if (src1
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || src2
1915 == ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1920 /* Seeing more than 1 forwarder blocks would confuse us later... */
1921 if (FORWARDER_BLOCK_P (e1
->dest
)
1922 && FORWARDER_BLOCK_P (single_succ (e1
->dest
)))
1925 if (FORWARDER_BLOCK_P (e2
->dest
)
1926 && FORWARDER_BLOCK_P (single_succ (e2
->dest
)))
1929 /* Likewise with dead code (possibly newly created by the other optimizations
1931 if (EDGE_COUNT (src1
->preds
) == 0 || EDGE_COUNT (src2
->preds
) == 0)
1934 /* Look for the common insn sequence, part the first ... */
1935 if (!outgoing_edges_match (mode
, src1
, src2
))
1938 /* ... and part the second. */
1939 nmatch
= flow_find_cross_jump (src1
, src2
, &newpos1
, &newpos2
, &dir
);
1943 if (newpos1
!= NULL_RTX
)
1944 src1
= BLOCK_FOR_INSN (newpos1
);
1945 if (newpos2
!= NULL_RTX
)
1946 src2
= BLOCK_FOR_INSN (newpos2
);
1948 if (dir
== dir_backward
)
1950 #define SWAP(T, X, Y) do { T tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
1951 SWAP (basic_block
, osrc1
, osrc2
);
1952 SWAP (basic_block
, src1
, src2
);
1953 SWAP (edge
, e1
, e2
);
1954 SWAP (rtx
, newpos1
, newpos2
);
1958 /* Don't proceed with the crossjump unless we found a sufficient number
1959 of matching instructions or the 'from' block was totally matched
1960 (such that its predecessors will hopefully be redirected and the
1962 if ((nmatch
< PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS
))
1963 && (newpos1
!= BB_HEAD (src1
)))
1966 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */
1967 if (block_has_preserve_label (e1
->dest
)
1968 && (e1
->flags
& EDGE_ABNORMAL
))
1971 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1973 If we have tablejumps in the end of SRC1 and SRC2
1974 they have been already compared for equivalence in outgoing_edges_match ()
1975 so replace the references to TABLE1 by references to TABLE2. */
1980 if (tablejump_p (BB_END (osrc1
), &label1
, &table1
)
1981 && tablejump_p (BB_END (osrc2
), &label2
, &table2
)
1982 && label1
!= label2
)
1984 replace_label_data rr
;
1987 /* Replace references to LABEL1 with LABEL2. */
1990 rr
.update_label_nuses
= true;
1991 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1993 /* Do not replace the label in SRC1->END because when deleting
1994 a block whose end is a tablejump, the tablejump referenced
1995 from the instruction is deleted too. */
1996 if (insn
!= BB_END (osrc1
))
1997 for_each_rtx (&insn
, replace_label
, &rr
);
2002 /* Avoid splitting if possible. We must always split when SRC2 has
2003 EH predecessor edges, or we may end up with basic blocks with both
2004 normal and EH predecessor edges. */
2005 if (newpos2
== BB_HEAD (src2
)
2006 && !(EDGE_PRED (src2
, 0)->flags
& EDGE_EH
))
2010 if (newpos2
== BB_HEAD (src2
))
2012 /* Skip possible basic block header. */
2013 if (LABEL_P (newpos2
))
2014 newpos2
= NEXT_INSN (newpos2
);
2015 while (DEBUG_INSN_P (newpos2
))
2016 newpos2
= NEXT_INSN (newpos2
);
2017 if (NOTE_P (newpos2
))
2018 newpos2
= NEXT_INSN (newpos2
);
2019 while (DEBUG_INSN_P (newpos2
))
2020 newpos2
= NEXT_INSN (newpos2
);
2024 fprintf (dump_file
, "Splitting bb %i before %i insns\n",
2025 src2
->index
, nmatch
);
2026 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
2031 "Cross jumping from bb %i to bb %i; %i common insns\n",
2032 src1
->index
, src2
->index
, nmatch
);
2034 /* We may have some registers visible through the block. */
2035 df_set_bb_dirty (redirect_to
);
2038 redirect_edges_to
= redirect_to
;
2040 redirect_edges_to
= osrc2
;
2042 /* Recompute the frequencies and counts of outgoing edges. */
2043 FOR_EACH_EDGE (s
, ei
, redirect_edges_to
->succs
)
2047 basic_block d
= s
->dest
;
2049 if (FORWARDER_BLOCK_P (d
))
2050 d
= single_succ (d
);
2052 FOR_EACH_EDGE (s2
, ei
, src1
->succs
)
2054 basic_block d2
= s2
->dest
;
2055 if (FORWARDER_BLOCK_P (d2
))
2056 d2
= single_succ (d2
);
2061 s
->count
+= s2
->count
;
2063 /* Take care to update possible forwarder blocks. We verified
2064 that there is no more than one in the chain, so we can't run
2065 into infinite loop. */
2066 if (FORWARDER_BLOCK_P (s
->dest
))
2068 single_succ_edge (s
->dest
)->count
+= s2
->count
;
2069 s
->dest
->count
+= s2
->count
;
2070 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
2073 if (FORWARDER_BLOCK_P (s2
->dest
))
2075 single_succ_edge (s2
->dest
)->count
-= s2
->count
;
2076 if (single_succ_edge (s2
->dest
)->count
< 0)
2077 single_succ_edge (s2
->dest
)->count
= 0;
2078 s2
->dest
->count
-= s2
->count
;
2079 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
2080 if (s2
->dest
->frequency
< 0)
2081 s2
->dest
->frequency
= 0;
2082 if (s2
->dest
->count
< 0)
2083 s2
->dest
->count
= 0;
2086 if (!redirect_edges_to
->frequency
&& !src1
->frequency
)
2087 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
2090 = ((s
->probability
* redirect_edges_to
->frequency
+
2091 s2
->probability
* src1
->frequency
)
2092 / (redirect_edges_to
->frequency
+ src1
->frequency
));
2095 /* Adjust count and frequency for the block. An earlier jump
2096 threading pass may have left the profile in an inconsistent
2097 state (see update_bb_profile_for_threading) so we must be
2098 prepared for overflows. */
2102 tmp
->count
+= src1
->count
;
2103 tmp
->frequency
+= src1
->frequency
;
2104 if (tmp
->frequency
> BB_FREQ_MAX
)
2105 tmp
->frequency
= BB_FREQ_MAX
;
2106 if (tmp
== redirect_edges_to
)
2108 tmp
= find_fallthru_edge (tmp
->succs
)->dest
;
2111 update_br_prob_note (redirect_edges_to
);
2113 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
2115 /* Skip possible basic block header. */
2116 if (LABEL_P (newpos1
))
2117 newpos1
= NEXT_INSN (newpos1
);
2119 while (DEBUG_INSN_P (newpos1
))
2120 newpos1
= NEXT_INSN (newpos1
);
2122 if (NOTE_INSN_BASIC_BLOCK_P (newpos1
))
2123 newpos1
= NEXT_INSN (newpos1
);
2125 while (DEBUG_INSN_P (newpos1
))
2126 newpos1
= NEXT_INSN (newpos1
);
2128 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
2129 to_remove
= single_succ (redirect_from
);
2131 redirect_edge_and_branch_force (single_succ_edge (redirect_from
), redirect_to
);
2132 delete_basic_block (to_remove
);
2134 update_forwarder_flag (redirect_from
);
2135 if (redirect_to
!= src2
)
2136 update_forwarder_flag (src2
);
2141 /* Search the predecessors of BB for common insn sequences. When found,
2142 share code between them by redirecting control flow. Return true if
2143 any changes made. */
2146 try_crossjump_bb (int mode
, basic_block bb
)
2148 edge e
, e2
, fallthru
;
2150 unsigned max
, ix
, ix2
;
2152 /* Nothing to do if there is not at least two incoming edges. */
2153 if (EDGE_COUNT (bb
->preds
) < 2)
2156 /* Don't crossjump if this block ends in a computed jump,
2157 unless we are optimizing for size. */
2158 if (optimize_bb_for_size_p (bb
)
2159 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2160 && computed_jump_p (BB_END (bb
)))
2163 /* If we are partitioning hot/cold basic blocks, we don't want to
2164 mess up unconditional or indirect jumps that cross between hot
2167 Basic block partitioning may result in some jumps that appear to
2168 be optimizable (or blocks that appear to be mergeable), but which really
2169 must be left untouched (they are required to make it safely across
2170 partition boundaries). See the comments at the top of
2171 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
2173 if (BB_PARTITION (EDGE_PRED (bb
, 0)->src
) !=
2174 BB_PARTITION (EDGE_PRED (bb
, 1)->src
)
2175 || (EDGE_PRED (bb
, 0)->flags
& EDGE_CROSSING
))
2178 /* It is always cheapest to redirect a block that ends in a branch to
2179 a block that falls through into BB, as that adds no branches to the
2180 program. We'll try that combination first. */
2182 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
2184 if (EDGE_COUNT (bb
->preds
) > max
)
2187 fallthru
= find_fallthru_edge (bb
->preds
);
2190 for (ix
= 0; ix
< EDGE_COUNT (bb
->preds
);)
2192 e
= EDGE_PRED (bb
, ix
);
2195 /* As noted above, first try with the fallthru predecessor (or, a
2196 fallthru predecessor if we are in cfglayout mode). */
2199 /* Don't combine the fallthru edge into anything else.
2200 If there is a match, we'll do it the other way around. */
2203 /* If nothing changed since the last attempt, there is nothing
2206 && !((e
->src
->flags
& BB_MODIFIED
)
2207 || (fallthru
->src
->flags
& BB_MODIFIED
)))
2210 if (try_crossjump_to_edge (mode
, e
, fallthru
, dir_forward
))
2218 /* Non-obvious work limiting check: Recognize that we're going
2219 to call try_crossjump_bb on every basic block. So if we have
2220 two blocks with lots of outgoing edges (a switch) and they
2221 share lots of common destinations, then we would do the
2222 cross-jump check once for each common destination.
2224 Now, if the blocks actually are cross-jump candidates, then
2225 all of their destinations will be shared. Which means that
2226 we only need check them for cross-jump candidacy once. We
2227 can eliminate redundant checks of crossjump(A,B) by arbitrarily
2228 choosing to do the check from the block for which the edge
2229 in question is the first successor of A. */
2230 if (EDGE_SUCC (e
->src
, 0) != e
)
2233 for (ix2
= 0; ix2
< EDGE_COUNT (bb
->preds
); ix2
++)
2235 e2
= EDGE_PRED (bb
, ix2
);
2240 /* We've already checked the fallthru edge above. */
2244 /* The "first successor" check above only prevents multiple
2245 checks of crossjump(A,B). In order to prevent redundant
2246 checks of crossjump(B,A), require that A be the block
2247 with the lowest index. */
2248 if (e
->src
->index
> e2
->src
->index
)
2251 /* If nothing changed since the last attempt, there is nothing
2254 && !((e
->src
->flags
& BB_MODIFIED
)
2255 || (e2
->src
->flags
& BB_MODIFIED
)))
2258 /* Both e and e2 are not fallthru edges, so we can crossjump in either
2260 if (try_crossjump_to_edge (mode
, e
, e2
, dir_both
))
2270 crossjumps_occured
= true;
2275 /* Search the successors of BB for common insn sequences. When found,
2276 share code between them by moving it across the basic block
2277 boundary. Return true if any changes made. */
2280 try_head_merge_bb (basic_block bb
)
2282 basic_block final_dest_bb
= NULL
;
2283 int max_match
= INT_MAX
;
2285 rtx
*headptr
, *currptr
, *nextptr
;
2286 bool changed
, moveall
;
2288 rtx e0_last_head
, cond
, move_before
;
2289 unsigned nedges
= EDGE_COUNT (bb
->succs
);
2290 rtx jump
= BB_END (bb
);
2291 regset live
, live_union
;
2293 /* Nothing to do if there is not at least two outgoing edges. */
2297 /* Don't crossjump if this block ends in a computed jump,
2298 unless we are optimizing for size. */
2299 if (optimize_bb_for_size_p (bb
)
2300 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2301 && computed_jump_p (BB_END (bb
)))
2304 cond
= get_condition (jump
, &move_before
, true, false);
2305 if (cond
== NULL_RTX
)
2308 if (reg_mentioned_p (cc0_rtx
, jump
))
2309 move_before
= prev_nonnote_nondebug_insn (jump
);
2315 for (ix
= 0; ix
< nedges
; ix
++)
2316 if (EDGE_SUCC (bb
, ix
)->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
2319 for (ix
= 0; ix
< nedges
; ix
++)
2321 edge e
= EDGE_SUCC (bb
, ix
);
2322 basic_block other_bb
= e
->dest
;
2324 if (df_get_bb_dirty (other_bb
))
2326 block_was_dirty
= true;
2330 if (e
->flags
& EDGE_ABNORMAL
)
2333 /* Normally, all destination blocks must only be reachable from this
2334 block, i.e. they must have one incoming edge.
2336 There is one special case we can handle, that of multiple consecutive
2337 jumps where the first jumps to one of the targets of the second jump.
2338 This happens frequently in switch statements for default labels.
2339 The structure is as follows:
2345 jump with targets A, B, C, D...
2347 has two incoming edges, from FINAL_DEST_BB and BB
2349 In this case, we can try to move the insns through BB and into
2351 if (EDGE_COUNT (other_bb
->preds
) != 1)
2353 edge incoming_edge
, incoming_bb_other_edge
;
2356 if (final_dest_bb
!= NULL
2357 || EDGE_COUNT (other_bb
->preds
) != 2)
2360 /* We must be able to move the insns across the whole block. */
2361 move_before
= BB_HEAD (bb
);
2362 while (!NONDEBUG_INSN_P (move_before
))
2363 move_before
= NEXT_INSN (move_before
);
2365 if (EDGE_COUNT (bb
->preds
) != 1)
2367 incoming_edge
= EDGE_PRED (bb
, 0);
2368 final_dest_bb
= incoming_edge
->src
;
2369 if (EDGE_COUNT (final_dest_bb
->succs
) != 2)
2371 FOR_EACH_EDGE (incoming_bb_other_edge
, ei
, final_dest_bb
->succs
)
2372 if (incoming_bb_other_edge
!= incoming_edge
)
2374 if (incoming_bb_other_edge
->dest
!= other_bb
)
2379 e0
= EDGE_SUCC (bb
, 0);
2380 e0_last_head
= NULL_RTX
;
2383 for (ix
= 1; ix
< nedges
; ix
++)
2385 edge e
= EDGE_SUCC (bb
, ix
);
2386 rtx e0_last
, e_last
;
2389 nmatch
= flow_find_head_matching_sequence (e0
->dest
, e
->dest
,
2390 &e0_last
, &e_last
, 0);
2394 if (nmatch
< max_match
)
2397 e0_last_head
= e0_last
;
2401 /* If we matched an entire block, we probably have to avoid moving the
2404 && e0_last_head
== BB_END (e0
->dest
)
2405 && (find_reg_note (e0_last_head
, REG_EH_REGION
, 0)
2406 || control_flow_insn_p (e0_last_head
)))
2412 e0_last_head
= prev_real_insn (e0_last_head
);
2413 while (DEBUG_INSN_P (e0_last_head
));
2419 /* We must find a union of the live registers at each of the end points. */
2420 live
= BITMAP_ALLOC (NULL
);
2421 live_union
= BITMAP_ALLOC (NULL
);
2423 currptr
= XNEWVEC (rtx
, nedges
);
2424 headptr
= XNEWVEC (rtx
, nedges
);
2425 nextptr
= XNEWVEC (rtx
, nedges
);
2427 for (ix
= 0; ix
< nedges
; ix
++)
2430 basic_block merge_bb
= EDGE_SUCC (bb
, ix
)->dest
;
2431 rtx head
= BB_HEAD (merge_bb
);
2433 while (!NONDEBUG_INSN_P (head
))
2434 head
= NEXT_INSN (head
);
2438 /* Compute the end point and live information */
2439 for (j
= 1; j
< max_match
; j
++)
2441 head
= NEXT_INSN (head
);
2442 while (!NONDEBUG_INSN_P (head
));
2443 simulate_backwards_to_point (merge_bb
, live
, head
);
2444 IOR_REG_SET (live_union
, live
);
2447 /* If we're moving across two blocks, verify the validity of the
2448 first move, then adjust the target and let the loop below deal
2449 with the final move. */
2450 if (final_dest_bb
!= NULL
)
2454 moveall
= can_move_insns_across (currptr
[0], e0_last_head
, move_before
,
2455 jump
, e0
->dest
, live_union
,
2459 if (move_upto
== NULL_RTX
)
2462 while (e0_last_head
!= move_upto
)
2464 df_simulate_one_insn_backwards (e0
->dest
, e0_last_head
,
2466 e0_last_head
= PREV_INSN (e0_last_head
);
2469 if (e0_last_head
== NULL_RTX
)
2472 jump
= BB_END (final_dest_bb
);
2473 cond
= get_condition (jump
, &move_before
, true, false);
2474 if (cond
== NULL_RTX
)
2477 if (reg_mentioned_p (cc0_rtx
, jump
))
2478 move_before
= prev_nonnote_nondebug_insn (jump
);
2488 moveall
= can_move_insns_across (currptr
[0], e0_last_head
,
2489 move_before
, jump
, e0
->dest
, live_union
,
2491 if (!moveall
&& move_upto
== NULL_RTX
)
2493 if (jump
== move_before
)
2496 /* Try again, using a different insertion point. */
2500 /* Don't try moving before a cc0 user, as that may invalidate
2502 if (reg_mentioned_p (cc0_rtx
, jump
))
2509 if (final_dest_bb
&& !moveall
)
2510 /* We haven't checked whether a partial move would be OK for the first
2511 move, so we have to fail this case. */
2517 if (currptr
[0] == move_upto
)
2519 for (ix
= 0; ix
< nedges
; ix
++)
2521 rtx curr
= currptr
[ix
];
2523 curr
= NEXT_INSN (curr
);
2524 while (!NONDEBUG_INSN_P (curr
));
2529 /* If we can't currently move all of the identical insns, remember
2530 each insn after the range that we'll merge. */
2532 for (ix
= 0; ix
< nedges
; ix
++)
2534 rtx curr
= currptr
[ix
];
2536 curr
= NEXT_INSN (curr
);
2537 while (!NONDEBUG_INSN_P (curr
));
2541 reorder_insns (headptr
[0], currptr
[0], PREV_INSN (move_before
));
2542 df_set_bb_dirty (EDGE_SUCC (bb
, 0)->dest
);
2543 if (final_dest_bb
!= NULL
)
2544 df_set_bb_dirty (final_dest_bb
);
2545 df_set_bb_dirty (bb
);
2546 for (ix
= 1; ix
< nedges
; ix
++)
2548 df_set_bb_dirty (EDGE_SUCC (bb
, ix
)->dest
);
2549 delete_insn_chain (headptr
[ix
], currptr
[ix
], false);
2553 if (jump
== move_before
)
2556 /* For the unmerged insns, try a different insertion point. */
2560 /* Don't try moving before a cc0 user, as that may invalidate
2562 if (reg_mentioned_p (cc0_rtx
, jump
))
2566 for (ix
= 0; ix
< nedges
; ix
++)
2567 currptr
[ix
] = headptr
[ix
] = nextptr
[ix
];
2577 crossjumps_occured
|= changed
;
2582 /* Return true if BB contains just bb note, or bb note followed
2583 by only DEBUG_INSNs. */
2586 trivially_empty_bb_p (basic_block bb
)
2588 rtx insn
= BB_END (bb
);
2592 if (insn
== BB_HEAD (bb
))
2594 if (!DEBUG_INSN_P (insn
))
2596 insn
= PREV_INSN (insn
);
2600 /* Do simple CFG optimizations - basic block merging, simplifying of jump
2601 instructions etc. Return nonzero if changes were made. */
2604 try_optimize_cfg (int mode
)
2606 bool changed_overall
= false;
2609 basic_block bb
, b
, next
;
2611 if (mode
& (CLEANUP_CROSSJUMP
| CLEANUP_THREADING
))
2614 crossjumps_occured
= false;
2616 FOR_EACH_BB_FN (bb
, cfun
)
2617 update_forwarder_flag (bb
);
2619 if (! targetm
.cannot_modify_jumps_p ())
2622 /* Attempt to merge blocks as made possible by edge removal. If
2623 a block has only one successor, and the successor has only
2624 one predecessor, they may be combined. */
2627 block_was_dirty
= false;
2633 "\n\ntry_optimize_cfg iteration %i\n\n",
2636 for (b
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; b
2637 != EXIT_BLOCK_PTR_FOR_FN (cfun
);)
2641 bool changed_here
= false;
2643 /* Delete trivially dead basic blocks. This is either
2644 blocks with no predecessors, or empty blocks with no
2645 successors. However if the empty block with no
2646 successors is the successor of the ENTRY_BLOCK, it is
2647 kept. This ensures that the ENTRY_BLOCK will have a
2648 successor which is a precondition for many RTL
2649 passes. Empty blocks may result from expanding
2650 __builtin_unreachable (). */
2651 if (EDGE_COUNT (b
->preds
) == 0
2652 || (EDGE_COUNT (b
->succs
) == 0
2653 && trivially_empty_bb_p (b
)
2654 && single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->dest
2658 if (EDGE_COUNT (b
->preds
) > 0)
2663 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2666 && BARRIER_P (BB_FOOTER (b
)))
2667 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2668 if ((e
->flags
& EDGE_FALLTHRU
)
2669 && BB_FOOTER (e
->src
) == NULL
)
2673 BB_FOOTER (e
->src
) = BB_FOOTER (b
);
2674 BB_FOOTER (b
) = NULL
;
2679 BB_FOOTER (e
->src
) = emit_barrier ();
2686 rtx last
= get_last_bb_insn (b
);
2687 if (last
&& BARRIER_P (last
))
2688 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2689 if ((e
->flags
& EDGE_FALLTHRU
))
2690 emit_barrier_after (BB_END (e
->src
));
2693 delete_basic_block (b
);
2695 /* Avoid trying to remove the exit block. */
2696 b
= (c
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) ? c
->next_bb
: c
);
2700 /* Remove code labels no longer used. */
2701 if (single_pred_p (b
)
2702 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2703 && !(single_pred_edge (b
)->flags
& EDGE_COMPLEX
)
2704 && LABEL_P (BB_HEAD (b
))
2705 /* If the previous block ends with a branch to this
2706 block, we can't delete the label. Normally this
2707 is a condjump that is yet to be simplified, but
2708 if CASE_DROPS_THRU, this can be a tablejump with
2709 some element going to the same place as the
2710 default (fallthru). */
2711 && (single_pred (b
) == ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2712 || !JUMP_P (BB_END (single_pred (b
)))
2713 || ! label_is_jump_target_p (BB_HEAD (b
),
2714 BB_END (single_pred (b
)))))
2716 delete_insn (BB_HEAD (b
));
2718 fprintf (dump_file
, "Deleted label in block %i.\n",
2722 /* If we fall through an empty block, we can remove it. */
2723 if (!(mode
& (CLEANUP_CFGLAYOUT
| CLEANUP_NO_INSN_DEL
))
2724 && single_pred_p (b
)
2725 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2726 && !LABEL_P (BB_HEAD (b
))
2727 && FORWARDER_BLOCK_P (b
)
2728 /* Note that forwarder_block_p true ensures that
2729 there is a successor for this block. */
2730 && (single_succ_edge (b
)->flags
& EDGE_FALLTHRU
)
2731 && n_basic_blocks_for_fn (cfun
) > NUM_FIXED_BLOCKS
+ 1)
2735 "Deleting fallthru block %i.\n",
2738 c
= ((b
->prev_bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
2739 ? b
->next_bb
: b
->prev_bb
);
2740 redirect_edge_succ_nodup (single_pred_edge (b
),
2742 delete_basic_block (b
);
2748 /* Merge B with its single successor, if any. */
2749 if (single_succ_p (b
)
2750 && (s
= single_succ_edge (b
))
2751 && !(s
->flags
& EDGE_COMPLEX
)
2752 && (c
= s
->dest
) != EXIT_BLOCK_PTR_FOR_FN (cfun
)
2753 && single_pred_p (c
)
2756 /* When not in cfg_layout mode use code aware of reordering
2757 INSN. This code possibly creates new basic blocks so it
2758 does not fit merge_blocks interface and is kept here in
2759 hope that it will become useless once more of compiler
2760 is transformed to use cfg_layout mode. */
2762 if ((mode
& CLEANUP_CFGLAYOUT
)
2763 && can_merge_blocks_p (b
, c
))
2765 merge_blocks (b
, c
);
2766 update_forwarder_flag (b
);
2767 changed_here
= true;
2769 else if (!(mode
& CLEANUP_CFGLAYOUT
)
2770 /* If the jump insn has side effects,
2771 we can't kill the edge. */
2772 && (!JUMP_P (BB_END (b
))
2773 || (reload_completed
2774 ? simplejump_p (BB_END (b
))
2775 : (onlyjump_p (BB_END (b
))
2776 && !tablejump_p (BB_END (b
),
2778 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
2781 changed_here
= true;
2785 /* Simplify branch over branch. */
2786 if ((mode
& CLEANUP_EXPENSIVE
)
2787 && !(mode
& CLEANUP_CFGLAYOUT
)
2788 && try_simplify_condjump (b
))
2789 changed_here
= true;
2791 /* If B has a single outgoing edge, but uses a
2792 non-trivial jump instruction without side-effects, we
2793 can either delete the jump entirely, or replace it
2794 with a simple unconditional jump. */
2795 if (single_succ_p (b
)
2796 && single_succ (b
) != EXIT_BLOCK_PTR_FOR_FN (cfun
)
2797 && onlyjump_p (BB_END (b
))
2798 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
)
2799 && try_redirect_by_replacing_jump (single_succ_edge (b
),
2801 (mode
& CLEANUP_CFGLAYOUT
) != 0))
2803 update_forwarder_flag (b
);
2804 changed_here
= true;
2807 /* Simplify branch to branch. */
2808 if (try_forward_edges (mode
, b
))
2810 update_forwarder_flag (b
);
2811 changed_here
= true;
2814 /* Look for shared code between blocks. */
2815 if ((mode
& CLEANUP_CROSSJUMP
)
2816 && try_crossjump_bb (mode
, b
))
2817 changed_here
= true;
2819 if ((mode
& CLEANUP_CROSSJUMP
)
2820 /* This can lengthen register lifetimes. Do it only after
2823 && try_head_merge_bb (b
))
2824 changed_here
= true;
2826 /* Don't get confused by the index shift caused by
2834 if ((mode
& CLEANUP_CROSSJUMP
)
2835 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR_FOR_FN (cfun
)))
2838 if (block_was_dirty
)
2840 /* This should only be set by head-merging. */
2841 gcc_assert (mode
& CLEANUP_CROSSJUMP
);
2847 /* Edge forwarding in particular can cause hot blocks previously
2848 reached by both hot and cold blocks to become dominated only
2849 by cold blocks. This will cause the verification below to fail,
2850 and lead to now cold code in the hot section. This is not easy
2851 to detect and fix during edge forwarding, and in some cases
2852 is only visible after newly unreachable blocks are deleted,
2853 which will be done in fixup_partitions. */
2854 fixup_partitions ();
2856 #ifdef ENABLE_CHECKING
2857 verify_flow_info ();
2861 changed_overall
|= changed
;
2867 FOR_ALL_BB_FN (b
, cfun
)
2868 b
->flags
&= ~(BB_FORWARDER_BLOCK
| BB_NONTHREADABLE_BLOCK
);
2870 return changed_overall
;
2873 /* Delete all unreachable basic blocks. */
2876 delete_unreachable_blocks (void)
2878 bool changed
= false;
2879 basic_block b
, prev_bb
;
2881 find_unreachable_blocks ();
2883 /* When we're in GIMPLE mode and there may be debug insns, we should
2884 delete blocks in reverse dominator order, so as to get a chance
2885 to substitute all released DEFs into debug stmts. If we don't
2886 have dominators information, walking blocks backward gets us a
2887 better chance of retaining most debug information than
2889 if (MAY_HAVE_DEBUG_INSNS
&& current_ir_type () == IR_GIMPLE
2890 && dom_info_available_p (CDI_DOMINATORS
))
2892 for (b
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
2893 b
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
); b
= prev_bb
)
2895 prev_bb
= b
->prev_bb
;
2897 if (!(b
->flags
& BB_REACHABLE
))
2899 /* Speed up the removal of blocks that don't dominate
2900 others. Walking backwards, this should be the common
2902 if (!first_dom_son (CDI_DOMINATORS
, b
))
2903 delete_basic_block (b
);
2907 = get_all_dominated_blocks (CDI_DOMINATORS
, b
);
2913 prev_bb
= b
->prev_bb
;
2915 gcc_assert (!(b
->flags
& BB_REACHABLE
));
2917 delete_basic_block (b
);
2929 for (b
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
2930 b
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
); b
= prev_bb
)
2932 prev_bb
= b
->prev_bb
;
2934 if (!(b
->flags
& BB_REACHABLE
))
2936 delete_basic_block (b
);
2943 tidy_fallthru_edges ();
2947 /* Delete any jump tables never referenced. We can't delete them at the
2948 time of removing tablejump insn as they are referenced by the preceding
2949 insns computing the destination, so we delay deleting and garbagecollect
2950 them once life information is computed. */
2952 delete_dead_jumptables (void)
2956 /* A dead jump table does not belong to any basic block. Scan insns
2957 between two adjacent basic blocks. */
2958 FOR_EACH_BB_FN (bb
, cfun
)
2962 for (insn
= NEXT_INSN (BB_END (bb
));
2963 insn
&& !NOTE_INSN_BASIC_BLOCK_P (insn
);
2966 next
= NEXT_INSN (insn
);
2968 && LABEL_NUSES (insn
) == LABEL_PRESERVE_P (insn
)
2969 && JUMP_TABLE_DATA_P (next
))
2971 rtx label
= insn
, jump
= next
;
2974 fprintf (dump_file
, "Dead jumptable %i removed\n",
2977 next
= NEXT_INSN (next
);
2979 delete_insn (label
);
2986 /* Tidy the CFG by deleting unreachable code and whatnot. */
2989 cleanup_cfg (int mode
)
2991 bool changed
= false;
2993 /* Set the cfglayout mode flag here. We could update all the callers
2994 but that is just inconvenient, especially given that we eventually
2995 want to have cfglayout mode as the default. */
2996 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2997 mode
|= CLEANUP_CFGLAYOUT
;
2999 timevar_push (TV_CLEANUP_CFG
);
3000 if (delete_unreachable_blocks ())
3003 /* We've possibly created trivially dead code. Cleanup it right
3004 now to introduce more opportunities for try_optimize_cfg. */
3005 if (!(mode
& (CLEANUP_NO_INSN_DEL
))
3006 && !reload_completed
)
3007 delete_trivially_dead_insns (get_insns (), max_reg_num ());
3012 /* To tail-merge blocks ending in the same noreturn function (e.g.
3013 a call to abort) we have to insert fake edges to exit. Do this
3014 here once. The fake edges do not interfere with any other CFG
3016 if (mode
& CLEANUP_CROSSJUMP
)
3017 add_noreturn_fake_exit_edges ();
3019 if (!dbg_cnt (cfg_cleanup
))
3022 while (try_optimize_cfg (mode
))
3024 delete_unreachable_blocks (), changed
= true;
3025 if (!(mode
& CLEANUP_NO_INSN_DEL
))
3027 /* Try to remove some trivially dead insns when doing an expensive
3028 cleanup. But delete_trivially_dead_insns doesn't work after
3029 reload (it only handles pseudos) and run_fast_dce is too costly
3030 to run in every iteration.
3032 For effective cross jumping, we really want to run a fast DCE to
3033 clean up any dead conditions, or they get in the way of performing
3036 Other transformations in cleanup_cfg are not so sensitive to dead
3037 code, so delete_trivially_dead_insns or even doing nothing at all
3039 if ((mode
& CLEANUP_EXPENSIVE
) && !reload_completed
3040 && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
3042 if ((mode
& CLEANUP_CROSSJUMP
) && crossjumps_occured
)
3049 if (mode
& CLEANUP_CROSSJUMP
)
3050 remove_fake_exit_edges ();
3052 /* Don't call delete_dead_jumptables in cfglayout mode, because
3053 that function assumes that jump tables are in the insns stream.
3054 But we also don't _have_ to delete dead jumptables in cfglayout
3055 mode because we shouldn't even be looking at things that are
3056 not in a basic block. Dead jumptables are cleaned up when
3057 going out of cfglayout mode. */
3058 if (!(mode
& CLEANUP_CFGLAYOUT
))
3059 delete_dead_jumptables ();
3061 /* ??? We probably do this way too often. */
3064 || (mode
& CLEANUP_CFG_CHANGED
)))
3066 timevar_push (TV_REPAIR_LOOPS
);
3067 /* The above doesn't preserve dominance info if available. */
3068 gcc_assert (!dom_info_available_p (CDI_DOMINATORS
));
3069 calculate_dominance_info (CDI_DOMINATORS
);
3070 fix_loop_structure (NULL
);
3071 free_dominance_info (CDI_DOMINATORS
);
3072 timevar_pop (TV_REPAIR_LOOPS
);
3075 timevar_pop (TV_CLEANUP_CFG
);
3083 delete_trivially_dead_insns (get_insns (), max_reg_num ());
3085 dump_flow_info (dump_file
, dump_flags
);
3086 cleanup_cfg ((optimize
? CLEANUP_EXPENSIVE
: 0)
3087 | (flag_thread_jumps
? CLEANUP_THREADING
: 0));
3093 const pass_data pass_data_jump
=
3095 RTL_PASS
, /* type */
3097 OPTGROUP_NONE
, /* optinfo_flags */
3098 false, /* has_gate */
3099 true, /* has_execute */
3100 TV_JUMP
, /* tv_id */
3101 0, /* properties_required */
3102 0, /* properties_provided */
3103 0, /* properties_destroyed */
3104 0, /* todo_flags_start */
3105 TODO_verify_rtl_sharing
, /* todo_flags_finish */
3108 class pass_jump
: public rtl_opt_pass
3111 pass_jump (gcc::context
*ctxt
)
3112 : rtl_opt_pass (pass_data_jump
, ctxt
)
3115 /* opt_pass methods: */
3116 unsigned int execute () { return execute_jump (); }
3118 }; // class pass_jump
3123 make_pass_jump (gcc::context
*ctxt
)
3125 return new pass_jump (ctxt
);
3129 execute_jump2 (void)
3131 cleanup_cfg (flag_crossjumping
? CLEANUP_CROSSJUMP
: 0);
3137 const pass_data pass_data_jump2
=
3139 RTL_PASS
, /* type */
3141 OPTGROUP_NONE
, /* optinfo_flags */
3142 false, /* has_gate */
3143 true, /* has_execute */
3144 TV_JUMP
, /* tv_id */
3145 0, /* properties_required */
3146 0, /* properties_provided */
3147 0, /* properties_destroyed */
3148 0, /* todo_flags_start */
3149 TODO_verify_rtl_sharing
, /* todo_flags_finish */
3152 class pass_jump2
: public rtl_opt_pass
3155 pass_jump2 (gcc::context
*ctxt
)
3156 : rtl_opt_pass (pass_data_jump2
, ctxt
)
3159 /* opt_pass methods: */
3160 unsigned int execute () { return execute_jump2 (); }
3162 }; // class pass_jump2
3167 make_pass_jump2 (gcc::context
*ctxt
)
3169 return new pass_jump2 (ctxt
);