1 /* Control flow optimization code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010, 2011,
4 2012 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file contains optimizer of the control flow. The main entry point is
23 cleanup_cfg. Following optimizations are performed:
25 - Unreachable blocks removal
26 - Edge forwarding (edge to the forwarder block is forwarded to its
27 successor. Simplification of the branch instruction is performed by
28 underlying infrastructure so branch can be converted to simplejump or
30 - Cross jumping (tail merging)
31 - Conditional jump-around-simplejump simplification
32 - Basic block merging. */
36 #include "coretypes.h"
39 #include "hard-reg-set.h"
41 #include "insn-config.h"
44 #include "diagnostic-core.h"
49 #include "function.h" /* For inline functions in emit-rtl.h they need crtl. */
51 #include "tree-pass.h"
58 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
60 /* Set to true when we are running first pass of try_optimize_cfg loop. */
61 static bool first_pass
;
63 /* Set to true if crossjumps occurred in the latest run of try_optimize_cfg. */
64 static bool crossjumps_occured
;
66 /* Set to true if we couldn't run an optimization due to stale liveness
67 information; we should run df_analyze to enable more opportunities. */
68 static bool block_was_dirty
;
70 static bool try_crossjump_to_edge (int, edge
, edge
, enum replace_direction
);
71 static bool try_crossjump_bb (int, basic_block
);
72 static bool outgoing_edges_match (int, basic_block
, basic_block
);
73 static enum replace_direction
old_insns_match_p (int, rtx
, rtx
);
75 static void merge_blocks_move_predecessor_nojumps (basic_block
, basic_block
);
76 static void merge_blocks_move_successor_nojumps (basic_block
, basic_block
);
77 static bool try_optimize_cfg (int);
78 static bool try_simplify_condjump (basic_block
);
79 static bool try_forward_edges (int, basic_block
);
80 static edge
thread_jump (edge
, basic_block
);
81 static bool mark_effect (rtx
, bitmap
);
82 static void notice_new_block (basic_block
);
83 static void update_forwarder_flag (basic_block
);
84 static int mentions_nonequal_regs (rtx
*, void *);
85 static void merge_memattrs (rtx
, rtx
);
87 /* Set flags for newly created block. */
90 notice_new_block (basic_block bb
)
95 if (forwarder_block_p (bb
))
96 bb
->flags
|= BB_FORWARDER_BLOCK
;
99 /* Recompute forwarder flag after block has been modified. */
102 update_forwarder_flag (basic_block bb
)
104 if (forwarder_block_p (bb
))
105 bb
->flags
|= BB_FORWARDER_BLOCK
;
107 bb
->flags
&= ~BB_FORWARDER_BLOCK
;
110 /* Simplify a conditional jump around an unconditional jump.
111 Return true if something changed. */
114 try_simplify_condjump (basic_block cbranch_block
)
116 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
117 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
120 /* Verify that there are exactly two successors. */
121 if (EDGE_COUNT (cbranch_block
->succs
) != 2)
124 /* Verify that we've got a normal conditional branch at the end
126 cbranch_insn
= BB_END (cbranch_block
);
127 if (!any_condjump_p (cbranch_insn
))
130 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
131 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
133 /* The next block must not have multiple predecessors, must not
134 be the last block in the function, and must contain just the
135 unconditional jump. */
136 jump_block
= cbranch_fallthru_edge
->dest
;
137 if (!single_pred_p (jump_block
)
138 || jump_block
->next_bb
== EXIT_BLOCK_PTR
139 || !FORWARDER_BLOCK_P (jump_block
))
141 jump_dest_block
= single_succ (jump_block
);
143 /* If we are partitioning hot/cold basic blocks, we don't want to
144 mess up unconditional or indirect jumps that cross between hot
147 Basic block partitioning may result in some jumps that appear to
148 be optimizable (or blocks that appear to be mergeable), but which really
149 must be left untouched (they are required to make it safely across
150 partition boundaries). See the comments at the top of
151 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
153 if (BB_PARTITION (jump_block
) != BB_PARTITION (jump_dest_block
)
154 || (cbranch_jump_edge
->flags
& EDGE_CROSSING
))
157 /* The conditional branch must target the block after the
158 unconditional branch. */
159 cbranch_dest_block
= cbranch_jump_edge
->dest
;
161 if (cbranch_dest_block
== EXIT_BLOCK_PTR
162 || !can_fallthru (jump_block
, cbranch_dest_block
))
165 /* Invert the conditional branch. */
166 if (!invert_jump (cbranch_insn
, 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
)
200 switch (GET_CODE (exp
))
202 /* In case we do clobber the register, mark it as equal, as we know the
203 value is dead so it don't have to match. */
205 if (REG_P (XEXP (exp
, 0)))
207 dest
= XEXP (exp
, 0);
208 regno
= REGNO (dest
);
209 if (HARD_REGISTER_NUM_P (regno
))
210 bitmap_clear_range (nonequal
, regno
,
211 hard_regno_nregs
[regno
][GET_MODE (dest
)]);
213 bitmap_clear_bit (nonequal
, regno
);
218 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
220 dest
= SET_DEST (exp
);
225 regno
= REGNO (dest
);
226 if (HARD_REGISTER_NUM_P (regno
))
227 bitmap_set_range (nonequal
, regno
,
228 hard_regno_nregs
[regno
][GET_MODE (dest
)]);
230 bitmap_set_bit (nonequal
, regno
);
238 /* Return nonzero if X is a register set in regset DATA.
239 Called via for_each_rtx. */
241 mentions_nonequal_regs (rtx
*x
, void *data
)
243 regset nonequal
= (regset
) data
;
249 if (REGNO_REG_SET_P (nonequal
, regno
))
251 if (regno
< FIRST_PSEUDO_REGISTER
)
253 int n
= hard_regno_nregs
[regno
][GET_MODE (*x
)];
255 if (REGNO_REG_SET_P (nonequal
, regno
+ n
))
261 /* Attempt to prove that the basic block B will have no side effects and
262 always continues in the same edge if reached via E. Return the edge
263 if exist, NULL otherwise. */
266 thread_jump (edge e
, basic_block b
)
268 rtx set1
, set2
, cond1
, cond2
, insn
;
269 enum rtx_code code1
, code2
, reversed_code2
;
270 bool reverse1
= false;
274 reg_set_iterator rsi
;
276 if (b
->flags
& BB_NONTHREADABLE_BLOCK
)
279 /* At the moment, we do handle only conditional jumps, but later we may
280 want to extend this code to tablejumps and others. */
281 if (EDGE_COUNT (e
->src
->succs
) != 2)
283 if (EDGE_COUNT (b
->succs
) != 2)
285 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
289 /* Second branch must end with onlyjump, as we will eliminate the jump. */
290 if (!any_condjump_p (BB_END (e
->src
)))
293 if (!any_condjump_p (BB_END (b
)) || !onlyjump_p (BB_END (b
)))
295 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
299 set1
= pc_set (BB_END (e
->src
));
300 set2
= pc_set (BB_END (b
));
301 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
302 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
305 cond1
= XEXP (SET_SRC (set1
), 0);
306 cond2
= XEXP (SET_SRC (set2
), 0);
308 code1
= reversed_comparison_code (cond1
, BB_END (e
->src
));
310 code1
= GET_CODE (cond1
);
312 code2
= GET_CODE (cond2
);
313 reversed_code2
= reversed_comparison_code (cond2
, BB_END (b
));
315 if (!comparison_dominates_p (code1
, code2
)
316 && !comparison_dominates_p (code1
, reversed_code2
))
319 /* Ensure that the comparison operators are equivalent.
320 ??? This is far too pessimistic. We should allow swapped operands,
321 different CCmodes, or for example comparisons for interval, that
322 dominate even when operands are not equivalent. */
323 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
324 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
327 /* Short circuit cases where block B contains some side effects, as we can't
329 for (insn
= NEXT_INSN (BB_HEAD (b
)); insn
!= NEXT_INSN (BB_END (b
));
330 insn
= NEXT_INSN (insn
))
331 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
333 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
339 /* First process all values computed in the source basic block. */
340 for (insn
= NEXT_INSN (BB_HEAD (e
->src
));
341 insn
!= NEXT_INSN (BB_END (e
->src
));
342 insn
= NEXT_INSN (insn
))
344 cselib_process_insn (insn
);
346 nonequal
= BITMAP_ALLOC (NULL
);
347 CLEAR_REG_SET (nonequal
);
349 /* Now assume that we've continued by the edge E to B and continue
350 processing as if it were same basic block.
351 Our goal is to prove that whole block is an NOOP. */
353 for (insn
= NEXT_INSN (BB_HEAD (b
));
354 insn
!= NEXT_INSN (BB_END (b
)) && !failed
;
355 insn
= NEXT_INSN (insn
))
359 rtx pat
= PATTERN (insn
);
361 if (GET_CODE (pat
) == PARALLEL
)
363 for (i
= 0; i
< (unsigned)XVECLEN (pat
, 0); i
++)
364 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
367 failed
|= mark_effect (pat
, nonequal
);
370 cselib_process_insn (insn
);
373 /* Later we should clear nonequal of dead registers. So far we don't
374 have life information in cfg_cleanup. */
377 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
381 /* cond2 must not mention any register that is not equal to the
383 if (for_each_rtx (&cond2
, mentions_nonequal_regs
, nonequal
))
386 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, rsi
)
389 BITMAP_FREE (nonequal
);
391 if ((comparison_dominates_p (code1
, code2
) != 0)
392 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
393 return BRANCH_EDGE (b
);
395 return FALLTHRU_EDGE (b
);
398 BITMAP_FREE (nonequal
);
403 /* Attempt to forward edges leaving basic block B.
404 Return true if successful. */
407 try_forward_edges (int mode
, basic_block b
)
409 bool changed
= false;
411 edge e
, *threaded_edges
= NULL
;
413 /* If we are partitioning hot/cold basic blocks, we don't want to
414 mess up unconditional or indirect jumps that cross between hot
417 Basic block partitioning may result in some jumps that appear to
418 be optimizable (or blocks that appear to be mergeable), but which really
419 must be left untouched (they are required to make it safely across
420 partition boundaries). See the comments at the top of
421 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
423 if (find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
426 for (ei
= ei_start (b
->succs
); (e
= ei_safe_edge (ei
)); )
428 basic_block target
, first
;
429 int counter
, goto_locus
;
430 bool threaded
= false;
431 int nthreaded_edges
= 0;
432 bool may_thread
= first_pass
|| (b
->flags
& BB_MODIFIED
) != 0;
434 /* Skip complex edges because we don't know how to update them.
436 Still handle fallthru edges, as we can succeed to forward fallthru
437 edge to the same place as the branch edge of conditional branch
438 and turn conditional branch to an unconditional branch. */
439 if (e
->flags
& EDGE_COMPLEX
)
445 target
= first
= e
->dest
;
446 counter
= NUM_FIXED_BLOCKS
;
447 goto_locus
= e
->goto_locus
;
449 /* If we are partitioning hot/cold basic_blocks, we don't want to mess
450 up jumps that cross between hot/cold sections.
452 Basic block partitioning may result in some jumps that appear
453 to be optimizable (or blocks that appear to be mergeable), but which
454 really must be left untouched (they are required to make it safely
455 across partition boundaries). See the comments at the top of
456 bb-reorder.c:partition_hot_cold_basic_blocks for complete
459 if (first
!= EXIT_BLOCK_PTR
460 && find_reg_note (BB_END (first
), REG_CROSSING_JUMP
, NULL_RTX
))
463 while (counter
< n_basic_blocks
)
465 basic_block new_target
= NULL
;
466 bool new_target_threaded
= false;
467 may_thread
|= (target
->flags
& BB_MODIFIED
) != 0;
469 if (FORWARDER_BLOCK_P (target
)
470 && !(single_succ_edge (target
)->flags
& EDGE_CROSSING
)
471 && single_succ (target
) != EXIT_BLOCK_PTR
)
473 /* Bypass trivial infinite loops. */
474 new_target
= single_succ (target
);
475 if (target
== new_target
)
476 counter
= n_basic_blocks
;
479 /* When not optimizing, ensure that edges or forwarder
480 blocks with different locus are not optimized out. */
481 int new_locus
= single_succ_edge (target
)->goto_locus
;
482 int locus
= goto_locus
;
484 if (new_locus
!= UNKNOWN_LOCATION
485 && locus
!= UNKNOWN_LOCATION
486 && new_locus
!= locus
)
492 if (new_locus
!= UNKNOWN_LOCATION
)
495 last
= BB_END (target
);
496 if (DEBUG_INSN_P (last
))
497 last
= prev_nondebug_insn (last
);
499 new_locus
= last
&& INSN_P (last
)
500 ? INSN_LOCATION (last
) : 0;
502 if (new_locus
!= UNKNOWN_LOCATION
503 && locus
!= UNKNOWN_LOCATION
504 && new_locus
!= locus
)
508 if (new_locus
!= UNKNOWN_LOCATION
)
517 /* Allow to thread only over one edge at time to simplify updating
519 else if ((mode
& CLEANUP_THREADING
) && may_thread
)
521 edge t
= thread_jump (e
, target
);
525 threaded_edges
= XNEWVEC (edge
, n_basic_blocks
);
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
;
542 /* Detect an infinite loop across the start block. */
546 gcc_assert (nthreaded_edges
< n_basic_blocks
- NUM_FIXED_BLOCKS
);
547 threaded_edges
[nthreaded_edges
++] = t
;
549 new_target
= t
->dest
;
550 new_target_threaded
= true;
559 threaded
|= new_target_threaded
;
562 if (counter
>= n_basic_blocks
)
565 fprintf (dump_file
, "Infinite loop in BB %i.\n",
568 else if (target
== first
)
569 ; /* We didn't do anything. */
572 /* Save the values now, as the edge may get removed. */
573 gcov_type edge_count
= e
->count
;
574 int edge_probability
= e
->probability
;
578 e
->goto_locus
= goto_locus
;
580 /* Don't force if target is exit block. */
581 if (threaded
&& target
!= EXIT_BLOCK_PTR
)
583 notice_new_block (redirect_edge_and_branch_force (e
, target
));
585 fprintf (dump_file
, "Conditionals threaded.\n");
587 else if (!redirect_edge_and_branch (e
, target
))
591 "Forwarding edge %i->%i to %i failed.\n",
592 b
->index
, e
->dest
->index
, target
->index
);
597 /* We successfully forwarded the edge. Now update profile
598 data: for each edge we traversed in the chain, remove
599 the original edge's execution count. */
600 edge_frequency
= ((edge_probability
* b
->frequency
601 + REG_BR_PROB_BASE
/ 2)
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
? 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
? 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
)
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
? 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
));
933 fmt
= GET_RTX_FORMAT (code
);
934 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
939 /* Two vectors must have the same length. */
940 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
943 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
944 merge_memattrs (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
));
949 merge_memattrs (XEXP (x
, i
), XEXP (y
, i
));
956 /* Checks if patterns P1 and P2 are equivalent, apart from the possibly
957 different single sets S1 and S2. */
960 equal_different_set_p (rtx p1
, rtx s1
, rtx p2
, rtx s2
)
965 if (p1
== s1
&& p2
== s2
)
968 if (GET_CODE (p1
) != PARALLEL
|| GET_CODE (p2
) != PARALLEL
)
971 if (XVECLEN (p1
, 0) != XVECLEN (p2
, 0))
974 for (i
= 0; i
< XVECLEN (p1
, 0); i
++)
976 e1
= XVECEXP (p1
, 0, i
);
977 e2
= XVECEXP (p2
, 0, i
);
978 if (e1
== s1
&& e2
== s2
)
981 ? rtx_renumbered_equal_p (e1
, e2
) : rtx_equal_p (e1
, e2
))
990 /* Examine register notes on I1 and I2 and return:
991 - dir_forward if I1 can be replaced by I2, or
992 - dir_backward if I2 can be replaced by I1, or
993 - dir_both if both are the case. */
995 static enum replace_direction
996 can_replace_by (rtx i1
, rtx i2
)
998 rtx s1
, s2
, d1
, d2
, src1
, src2
, note1
, note2
;
1001 /* Check for 2 sets. */
1002 s1
= single_set (i1
);
1003 s2
= single_set (i2
);
1004 if (s1
== NULL_RTX
|| s2
== NULL_RTX
)
1007 /* Check that the 2 sets set the same dest. */
1010 if (!(reload_completed
1011 ? rtx_renumbered_equal_p (d1
, d2
) : rtx_equal_p (d1
, d2
)))
1014 /* Find identical req_equiv or reg_equal note, which implies that the 2 sets
1015 set dest to the same value. */
1016 note1
= find_reg_equal_equiv_note (i1
);
1017 note2
= find_reg_equal_equiv_note (i2
);
1018 if (!note1
|| !note2
|| !rtx_equal_p (XEXP (note1
, 0), XEXP (note2
, 0))
1019 || !CONST_INT_P (XEXP (note1
, 0)))
1022 if (!equal_different_set_p (PATTERN (i1
), s1
, PATTERN (i2
), s2
))
1025 /* Although the 2 sets set dest to the same value, we cannot replace
1026 (set (dest) (const_int))
1029 because we don't know if the reg is live and has the same value at the
1030 location of replacement. */
1031 src1
= SET_SRC (s1
);
1032 src2
= SET_SRC (s2
);
1033 c1
= CONST_INT_P (src1
);
1034 c2
= CONST_INT_P (src2
);
1040 return dir_backward
;
1045 /* Merges directions A and B. */
1047 static enum replace_direction
1048 merge_dir (enum replace_direction a
, enum replace_direction b
)
1050 /* Implements the following table:
1069 /* Examine I1 and I2 and return:
1070 - dir_forward if I1 can be replaced by I2, or
1071 - dir_backward if I2 can be replaced by I1, or
1072 - dir_both if both are the case. */
1074 static enum replace_direction
1075 old_insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx i1
, rtx i2
)
1079 /* Verify that I1 and I2 are equivalent. */
1080 if (GET_CODE (i1
) != GET_CODE (i2
))
1083 /* __builtin_unreachable() may lead to empty blocks (ending with
1084 NOTE_INSN_BASIC_BLOCK). They may be crossjumped. */
1085 if (NOTE_INSN_BASIC_BLOCK_P (i1
) && NOTE_INSN_BASIC_BLOCK_P (i2
))
1088 /* ??? Do not allow cross-jumping between different stack levels. */
1089 p1
= find_reg_note (i1
, REG_ARGS_SIZE
, NULL
);
1090 p2
= find_reg_note (i2
, REG_ARGS_SIZE
, NULL
);
1095 if (!rtx_equal_p (p1
, p2
))
1098 /* ??? Worse, this adjustment had better be constant lest we
1099 have differing incoming stack levels. */
1100 if (!frame_pointer_needed
1101 && find_args_size_adjust (i1
) == HOST_WIDE_INT_MIN
)
1110 if (GET_CODE (p1
) != GET_CODE (p2
))
1113 /* If this is a CALL_INSN, compare register usage information.
1114 If we don't check this on stack register machines, the two
1115 CALL_INSNs might be merged leaving reg-stack.c with mismatching
1116 numbers of stack registers in the same basic block.
1117 If we don't check this on machines with delay slots, a delay slot may
1118 be filled that clobbers a parameter expected by the subroutine.
1120 ??? We take the simple route for now and assume that if they're
1121 equal, they were constructed identically.
1123 Also check for identical exception regions. */
1127 /* Ensure the same EH region. */
1128 rtx n1
= find_reg_note (i1
, REG_EH_REGION
, 0);
1129 rtx n2
= find_reg_note (i2
, REG_EH_REGION
, 0);
1134 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1137 if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
1138 CALL_INSN_FUNCTION_USAGE (i2
))
1139 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
))
1142 /* For address sanitizer, never crossjump __asan_report_* builtins,
1143 otherwise errors might be reported on incorrect lines. */
1146 rtx call
= get_call_rtx_from (i1
);
1147 if (call
&& GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
1149 rtx symbol
= XEXP (XEXP (call
, 0), 0);
1150 if (SYMBOL_REF_DECL (symbol
)
1151 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
1153 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
1155 && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
))
1156 >= BUILT_IN_ASAN_REPORT_LOAD1
1157 && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
))
1158 <= BUILT_IN_ASAN_REPORT_STORE16
)
1166 /* If cross_jump_death_matters is not 0, the insn's mode
1167 indicates whether or not the insn contains any stack-like
1170 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
1172 /* If register stack conversion has already been done, then
1173 death notes must also be compared before it is certain that
1174 the two instruction streams match. */
1177 HARD_REG_SET i1_regset
, i2_regset
;
1179 CLEAR_HARD_REG_SET (i1_regset
);
1180 CLEAR_HARD_REG_SET (i2_regset
);
1182 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
1183 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1184 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
1186 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
1187 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1188 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
1190 if (!hard_reg_set_equal_p (i1_regset
, i2_regset
))
1195 if (reload_completed
1196 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
1199 return can_replace_by (i1
, i2
);
1202 /* When comparing insns I1 and I2 in flow_find_cross_jump or
1203 flow_find_head_matching_sequence, ensure the notes match. */
1206 merge_notes (rtx i1
, rtx i2
)
1208 /* If the merged insns have different REG_EQUAL notes, then
1210 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1211 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1213 if (equiv1
&& !equiv2
)
1214 remove_note (i1
, equiv1
);
1215 else if (!equiv1
&& equiv2
)
1216 remove_note (i2
, equiv2
);
1217 else if (equiv1
&& equiv2
1218 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1220 remove_note (i1
, equiv1
);
1221 remove_note (i2
, equiv2
);
1225 /* Walks from I1 in BB1 backward till the next non-debug insn, and returns the
1226 resulting insn in I1, and the corresponding bb in BB1. At the head of a
1227 bb, if there is a predecessor bb that reaches this bb via fallthru, and
1228 FOLLOW_FALLTHRU, walks further in the predecessor bb and registers this in
1229 DID_FALLTHRU. Otherwise, stops at the head of the bb. */
1232 walk_to_nondebug_insn (rtx
*i1
, basic_block
*bb1
, bool follow_fallthru
,
1237 *did_fallthru
= false;
1240 while (!NONDEBUG_INSN_P (*i1
))
1242 if (*i1
!= BB_HEAD (*bb1
))
1244 *i1
= PREV_INSN (*i1
);
1248 if (!follow_fallthru
)
1251 fallthru
= find_fallthru_edge ((*bb1
)->preds
);
1252 if (!fallthru
|| fallthru
->src
== ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
)
1253 || !single_succ_p (fallthru
->src
))
1256 *bb1
= fallthru
->src
;
1257 *i1
= BB_END (*bb1
);
1258 *did_fallthru
= true;
1262 /* Look through the insns at the end of BB1 and BB2 and find the longest
1263 sequence that are either equivalent, or allow forward or backward
1264 replacement. Store the first insns for that sequence in *F1 and *F2 and
1265 return the sequence length.
1267 DIR_P indicates the allowed replacement direction on function entry, and
1268 the actual replacement direction on function exit. If NULL, only equivalent
1269 sequences are allowed.
1271 To simplify callers of this function, if the blocks match exactly,
1272 store the head of the blocks in *F1 and *F2. */
1275 flow_find_cross_jump (basic_block bb1
, basic_block bb2
, rtx
*f1
, rtx
*f2
,
1276 enum replace_direction
*dir_p
)
1278 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
1281 enum replace_direction dir
, last_dir
, afterlast_dir
;
1282 bool follow_fallthru
, did_fallthru
;
1288 afterlast_dir
= dir
;
1289 last_dir
= afterlast_dir
;
1291 /* Skip simple jumps at the end of the blocks. Complex jumps still
1292 need to be compared for equivalence, which we'll do below. */
1295 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
1297 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1300 i1
= PREV_INSN (i1
);
1305 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1308 /* Count everything except for unconditional jump as insn. */
1309 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1311 i2
= PREV_INSN (i2
);
1316 /* In the following example, we can replace all jumps to C by jumps to A.
1318 This removes 4 duplicate insns.
1319 [bb A] insn1 [bb C] insn1
1325 We could also replace all jumps to A by jumps to C, but that leaves B
1326 alive, and removes only 2 duplicate insns. In a subsequent crossjump
1327 step, all jumps to B would be replaced with jumps to the middle of C,
1328 achieving the same result with more effort.
1329 So we allow only the first possibility, which means that we don't allow
1330 fallthru in the block that's being replaced. */
1332 follow_fallthru
= dir_p
&& dir
!= dir_forward
;
1333 walk_to_nondebug_insn (&i1
, &bb1
, follow_fallthru
, &did_fallthru
);
1337 follow_fallthru
= dir_p
&& dir
!= dir_backward
;
1338 walk_to_nondebug_insn (&i2
, &bb2
, follow_fallthru
, &did_fallthru
);
1342 if (i1
== BB_HEAD (bb1
) || i2
== BB_HEAD (bb2
))
1345 dir
= merge_dir (dir
, old_insns_match_p (0, i1
, i2
));
1346 if (dir
== dir_none
|| (!dir_p
&& dir
!= dir_both
))
1349 merge_memattrs (i1
, i2
);
1351 /* Don't begin a cross-jump with a NOTE insn. */
1354 merge_notes (i1
, i2
);
1356 afterlast1
= last1
, afterlast2
= last2
;
1357 last1
= i1
, last2
= i2
;
1358 afterlast_dir
= last_dir
;
1361 if (!(GET_CODE (p1
) == USE
|| GET_CODE (p1
) == CLOBBER
))
1365 i1
= PREV_INSN (i1
);
1366 i2
= PREV_INSN (i2
);
1370 /* Don't allow the insn after a compare to be shared by
1371 cross-jumping unless the compare is also shared. */
1372 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1373 last1
= afterlast1
, last2
= afterlast2
, last_dir
= afterlast_dir
, ninsns
--;
1376 /* Include preceding notes and labels in the cross-jump. One,
1377 this may bring us to the head of the blocks as requested above.
1378 Two, it keeps line number notes as matched as may be. */
1381 bb1
= BLOCK_FOR_INSN (last1
);
1382 while (last1
!= BB_HEAD (bb1
) && !NONDEBUG_INSN_P (PREV_INSN (last1
)))
1383 last1
= PREV_INSN (last1
);
1385 if (last1
!= BB_HEAD (bb1
) && LABEL_P (PREV_INSN (last1
)))
1386 last1
= PREV_INSN (last1
);
1388 bb2
= BLOCK_FOR_INSN (last2
);
1389 while (last2
!= BB_HEAD (bb2
) && !NONDEBUG_INSN_P (PREV_INSN (last2
)))
1390 last2
= PREV_INSN (last2
);
1392 if (last2
!= BB_HEAD (bb2
) && LABEL_P (PREV_INSN (last2
)))
1393 last2
= PREV_INSN (last2
);
1404 /* Like flow_find_cross_jump, except start looking for a matching sequence from
1405 the head of the two blocks. Do not include jumps at the end.
1406 If STOP_AFTER is nonzero, stop after finding that many matching
1410 flow_find_head_matching_sequence (basic_block bb1
, basic_block bb2
, rtx
*f1
,
1411 rtx
*f2
, int stop_after
)
1413 rtx i1
, i2
, last1
, last2
, beforelast1
, beforelast2
;
1417 int nehedges1
= 0, nehedges2
= 0;
1419 FOR_EACH_EDGE (e
, ei
, bb1
->succs
)
1420 if (e
->flags
& EDGE_EH
)
1422 FOR_EACH_EDGE (e
, ei
, bb2
->succs
)
1423 if (e
->flags
& EDGE_EH
)
1428 last1
= beforelast1
= last2
= beforelast2
= NULL_RTX
;
1432 /* Ignore notes, except NOTE_INSN_EPILOGUE_BEG. */
1433 while (!NONDEBUG_INSN_P (i1
) && i1
!= BB_END (bb1
))
1435 if (NOTE_P (i1
) && NOTE_KIND (i1
) == NOTE_INSN_EPILOGUE_BEG
)
1437 i1
= NEXT_INSN (i1
);
1440 while (!NONDEBUG_INSN_P (i2
) && i2
!= BB_END (bb2
))
1442 if (NOTE_P (i2
) && NOTE_KIND (i2
) == NOTE_INSN_EPILOGUE_BEG
)
1444 i2
= NEXT_INSN (i2
);
1447 if ((i1
== BB_END (bb1
) && !NONDEBUG_INSN_P (i1
))
1448 || (i2
== BB_END (bb2
) && !NONDEBUG_INSN_P (i2
)))
1451 if (NOTE_P (i1
) || NOTE_P (i2
)
1452 || JUMP_P (i1
) || JUMP_P (i2
))
1455 /* A sanity check to make sure we're not merging insns with different
1456 effects on EH. If only one of them ends a basic block, it shouldn't
1457 have an EH edge; if both end a basic block, there should be the same
1458 number of EH edges. */
1459 if ((i1
== BB_END (bb1
) && i2
!= BB_END (bb2
)
1461 || (i2
== BB_END (bb2
) && i1
!= BB_END (bb1
)
1463 || (i1
== BB_END (bb1
) && i2
== BB_END (bb2
)
1464 && nehedges1
!= nehedges2
))
1467 if (old_insns_match_p (0, i1
, i2
) != dir_both
)
1470 merge_memattrs (i1
, i2
);
1472 /* Don't begin a cross-jump with a NOTE insn. */
1475 merge_notes (i1
, i2
);
1477 beforelast1
= last1
, beforelast2
= last2
;
1478 last1
= i1
, last2
= i2
;
1482 if (i1
== BB_END (bb1
) || i2
== BB_END (bb2
)
1483 || (stop_after
> 0 && ninsns
== stop_after
))
1486 i1
= NEXT_INSN (i1
);
1487 i2
= NEXT_INSN (i2
);
1491 /* Don't allow a compare to be shared by cross-jumping unless the insn
1492 after the compare is also shared. */
1493 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && sets_cc0_p (last1
))
1494 last1
= beforelast1
, last2
= beforelast2
, ninsns
--;
1506 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1507 the branch instruction. This means that if we commonize the control
1508 flow before end of the basic block, the semantic remains unchanged.
1510 We may assume that there exists one edge with a common destination. */
1513 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1515 int nehedges1
= 0, nehedges2
= 0;
1516 edge fallthru1
= 0, fallthru2
= 0;
1520 /* If we performed shrink-wrapping, edges to the EXIT_BLOCK_PTR can
1521 only be distinguished for JUMP_INSNs. The two paths may differ in
1522 whether they went through the prologue. Sibcalls are fine, we know
1523 that we either didn't need or inserted an epilogue before them. */
1524 if (crtl
->shrink_wrapped
1525 && single_succ_p (bb1
) && single_succ (bb1
) == EXIT_BLOCK_PTR
1526 && !JUMP_P (BB_END (bb1
))
1527 && !(CALL_P (BB_END (bb1
)) && SIBLING_CALL_P (BB_END (bb1
))))
1530 /* If BB1 has only one successor, we may be looking at either an
1531 unconditional jump, or a fake edge to exit. */
1532 if (single_succ_p (bb1
)
1533 && (single_succ_edge (bb1
)->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1534 && (!JUMP_P (BB_END (bb1
)) || simplejump_p (BB_END (bb1
))))
1535 return (single_succ_p (bb2
)
1536 && (single_succ_edge (bb2
)->flags
1537 & (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1538 && (!JUMP_P (BB_END (bb2
)) || simplejump_p (BB_END (bb2
))));
1540 /* Match conditional jumps - this may get tricky when fallthru and branch
1541 edges are crossed. */
1542 if (EDGE_COUNT (bb1
->succs
) == 2
1543 && any_condjump_p (BB_END (bb1
))
1544 && onlyjump_p (BB_END (bb1
)))
1546 edge b1
, f1
, b2
, f2
;
1547 bool reverse
, match
;
1548 rtx set1
, set2
, cond1
, cond2
;
1549 enum rtx_code code1
, code2
;
1551 if (EDGE_COUNT (bb2
->succs
) != 2
1552 || !any_condjump_p (BB_END (bb2
))
1553 || !onlyjump_p (BB_END (bb2
)))
1556 b1
= BRANCH_EDGE (bb1
);
1557 b2
= BRANCH_EDGE (bb2
);
1558 f1
= FALLTHRU_EDGE (bb1
);
1559 f2
= FALLTHRU_EDGE (bb2
);
1561 /* Get around possible forwarders on fallthru edges. Other cases
1562 should be optimized out already. */
1563 if (FORWARDER_BLOCK_P (f1
->dest
))
1564 f1
= single_succ_edge (f1
->dest
);
1566 if (FORWARDER_BLOCK_P (f2
->dest
))
1567 f2
= single_succ_edge (f2
->dest
);
1569 /* To simplify use of this function, return false if there are
1570 unneeded forwarder blocks. These will get eliminated later
1571 during cleanup_cfg. */
1572 if (FORWARDER_BLOCK_P (f1
->dest
)
1573 || FORWARDER_BLOCK_P (f2
->dest
)
1574 || FORWARDER_BLOCK_P (b1
->dest
)
1575 || FORWARDER_BLOCK_P (b2
->dest
))
1578 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1580 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1585 set1
= pc_set (BB_END (bb1
));
1586 set2
= pc_set (BB_END (bb2
));
1587 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1588 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1591 cond1
= XEXP (SET_SRC (set1
), 0);
1592 cond2
= XEXP (SET_SRC (set2
), 0);
1593 code1
= GET_CODE (cond1
);
1595 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
1597 code2
= GET_CODE (cond2
);
1599 if (code2
== UNKNOWN
)
1602 /* Verify codes and operands match. */
1603 match
= ((code1
== code2
1604 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1605 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1606 || (code1
== swap_condition (code2
)
1607 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1609 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1612 /* If we return true, we will join the blocks. Which means that
1613 we will only have one branch prediction bit to work with. Thus
1614 we require the existing branches to have probabilities that are
1617 && optimize_bb_for_speed_p (bb1
)
1618 && optimize_bb_for_speed_p (bb2
))
1622 if (b1
->dest
== b2
->dest
)
1623 prob2
= b2
->probability
;
1625 /* Do not use f2 probability as f2 may be forwarded. */
1626 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1628 /* Fail if the difference in probabilities is greater than 50%.
1629 This rules out two well-predicted branches with opposite
1631 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1635 "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
1636 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1642 if (dump_file
&& match
)
1643 fprintf (dump_file
, "Conditionals in bb %i and %i match.\n",
1644 bb1
->index
, bb2
->index
);
1649 /* Generic case - we are seeing a computed jump, table jump or trapping
1652 /* Check whether there are tablejumps in the end of BB1 and BB2.
1653 Return true if they are identical. */
1658 if (tablejump_p (BB_END (bb1
), &label1
, &table1
)
1659 && tablejump_p (BB_END (bb2
), &label2
, &table2
)
1660 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1662 /* The labels should never be the same rtx. If they really are same
1663 the jump tables are same too. So disable crossjumping of blocks BB1
1664 and BB2 because when deleting the common insns in the end of BB1
1665 by delete_basic_block () the jump table would be deleted too. */
1666 /* If LABEL2 is referenced in BB1->END do not do anything
1667 because we would loose information when replacing
1668 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1669 if (label1
!= label2
&& !rtx_referenced_p (label2
, BB_END (bb1
)))
1671 /* Set IDENTICAL to true when the tables are identical. */
1672 bool identical
= false;
1675 p1
= PATTERN (table1
);
1676 p2
= PATTERN (table2
);
1677 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1681 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1682 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1683 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1684 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1689 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1690 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1696 replace_label_data rr
;
1699 /* Temporarily replace references to LABEL1 with LABEL2
1700 in BB1->END so that we could compare the instructions. */
1703 rr
.update_label_nuses
= false;
1704 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1706 match
= (old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
))
1708 if (dump_file
&& match
)
1710 "Tablejumps in bb %i and %i match.\n",
1711 bb1
->index
, bb2
->index
);
1713 /* Set the original label in BB1->END because when deleting
1714 a block whose end is a tablejump, the tablejump referenced
1715 from the instruction is deleted too. */
1718 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1727 rtx last1
= BB_END (bb1
);
1728 rtx last2
= BB_END (bb2
);
1729 if (DEBUG_INSN_P (last1
))
1730 last1
= prev_nondebug_insn (last1
);
1731 if (DEBUG_INSN_P (last2
))
1732 last2
= prev_nondebug_insn (last2
);
1733 /* First ensure that the instructions match. There may be many outgoing
1734 edges so this test is generally cheaper. */
1735 if (old_insns_match_p (mode
, last1
, last2
) != dir_both
)
1738 /* Search the outgoing edges, ensure that the counts do match, find possible
1739 fallthru and exception handling edges since these needs more
1741 if (EDGE_COUNT (bb1
->succs
) != EDGE_COUNT (bb2
->succs
))
1744 bool nonfakeedges
= false;
1745 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1747 e2
= EDGE_SUCC (bb2
, ei
.index
);
1749 if ((e1
->flags
& EDGE_FAKE
) == 0)
1750 nonfakeedges
= true;
1752 if (e1
->flags
& EDGE_EH
)
1755 if (e2
->flags
& EDGE_EH
)
1758 if (e1
->flags
& EDGE_FALLTHRU
)
1760 if (e2
->flags
& EDGE_FALLTHRU
)
1764 /* If number of edges of various types does not match, fail. */
1765 if (nehedges1
!= nehedges2
1766 || (fallthru1
!= 0) != (fallthru2
!= 0))
1769 /* If !ACCUMULATE_OUTGOING_ARGS, bb1 (and bb2) have no successors
1770 and the last real insn doesn't have REG_ARGS_SIZE note, don't
1771 attempt to optimize, as the two basic blocks might have different
1772 REG_ARGS_SIZE depths. For noreturn calls and unconditional
1773 traps there should be REG_ARG_SIZE notes, they could be missing
1774 for __builtin_unreachable () uses though. */
1776 && !ACCUMULATE_OUTGOING_ARGS
1778 || !find_reg_note (last1
, REG_ARGS_SIZE
, NULL
)))
1781 /* fallthru edges must be forwarded to the same destination. */
1784 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1785 ? single_succ (fallthru1
->dest
): fallthru1
->dest
);
1786 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1787 ? single_succ (fallthru2
->dest
): fallthru2
->dest
);
1793 /* Ensure the same EH region. */
1795 rtx n1
= find_reg_note (BB_END (bb1
), REG_EH_REGION
, 0);
1796 rtx n2
= find_reg_note (BB_END (bb2
), REG_EH_REGION
, 0);
1801 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1805 /* The same checks as in try_crossjump_to_edge. It is required for RTL
1806 version of sequence abstraction. */
1807 FOR_EACH_EDGE (e1
, ei
, bb2
->succs
)
1811 basic_block d1
= e1
->dest
;
1813 if (FORWARDER_BLOCK_P (d1
))
1814 d1
= EDGE_SUCC (d1
, 0)->dest
;
1816 FOR_EACH_EDGE (e2
, ei
, bb1
->succs
)
1818 basic_block d2
= e2
->dest
;
1819 if (FORWARDER_BLOCK_P (d2
))
1820 d2
= EDGE_SUCC (d2
, 0)->dest
;
1832 /* Returns true if BB basic block has a preserve label. */
1835 block_has_preserve_label (basic_block bb
)
1839 && LABEL_PRESERVE_P (block_label (bb
)));
1842 /* E1 and E2 are edges with the same destination block. Search their
1843 predecessors for common code. If found, redirect control flow from
1844 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC (dir_forward),
1845 or the other way around (dir_backward). DIR specifies the allowed
1846 replacement direction. */
1849 try_crossjump_to_edge (int mode
, edge e1
, edge e2
,
1850 enum replace_direction dir
)
1853 basic_block src1
= e1
->src
, src2
= e2
->src
;
1854 basic_block redirect_to
, redirect_from
, to_remove
;
1855 basic_block osrc1
, osrc2
, redirect_edges_to
, tmp
;
1856 rtx newpos1
, newpos2
;
1860 newpos1
= newpos2
= NULL_RTX
;
1862 /* If we have partitioned hot/cold basic blocks, it is a bad idea
1863 to try this optimization.
1865 Basic block partitioning may result in some jumps that appear to
1866 be optimizable (or blocks that appear to be mergeable), but which really
1867 must be left untouched (they are required to make it safely across
1868 partition boundaries). See the comments at the top of
1869 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1871 if (flag_reorder_blocks_and_partition
&& reload_completed
)
1874 /* Search backward through forwarder blocks. We don't need to worry
1875 about multiple entry or chained forwarders, as they will be optimized
1876 away. We do this to look past the unconditional jump following a
1877 conditional jump that is required due to the current CFG shape. */
1878 if (single_pred_p (src1
)
1879 && FORWARDER_BLOCK_P (src1
))
1880 e1
= single_pred_edge (src1
), src1
= e1
->src
;
1882 if (single_pred_p (src2
)
1883 && FORWARDER_BLOCK_P (src2
))
1884 e2
= single_pred_edge (src2
), src2
= e2
->src
;
1886 /* Nothing to do if we reach ENTRY, or a common source block. */
1887 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1892 /* Seeing more than 1 forwarder blocks would confuse us later... */
1893 if (FORWARDER_BLOCK_P (e1
->dest
)
1894 && FORWARDER_BLOCK_P (single_succ (e1
->dest
)))
1897 if (FORWARDER_BLOCK_P (e2
->dest
)
1898 && FORWARDER_BLOCK_P (single_succ (e2
->dest
)))
1901 /* Likewise with dead code (possibly newly created by the other optimizations
1903 if (EDGE_COUNT (src1
->preds
) == 0 || EDGE_COUNT (src2
->preds
) == 0)
1906 /* Look for the common insn sequence, part the first ... */
1907 if (!outgoing_edges_match (mode
, src1
, src2
))
1910 /* ... and part the second. */
1911 nmatch
= flow_find_cross_jump (src1
, src2
, &newpos1
, &newpos2
, &dir
);
1915 if (newpos1
!= NULL_RTX
)
1916 src1
= BLOCK_FOR_INSN (newpos1
);
1917 if (newpos2
!= NULL_RTX
)
1918 src2
= BLOCK_FOR_INSN (newpos2
);
1920 if (dir
== dir_backward
)
1922 #define SWAP(T, X, Y) do { T tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
1923 SWAP (basic_block
, osrc1
, osrc2
);
1924 SWAP (basic_block
, src1
, src2
);
1925 SWAP (edge
, e1
, e2
);
1926 SWAP (rtx
, newpos1
, newpos2
);
1930 /* Don't proceed with the crossjump unless we found a sufficient number
1931 of matching instructions or the 'from' block was totally matched
1932 (such that its predecessors will hopefully be redirected and the
1934 if ((nmatch
< PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS
))
1935 && (newpos1
!= BB_HEAD (src1
)))
1938 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */
1939 if (block_has_preserve_label (e1
->dest
)
1940 && (e1
->flags
& EDGE_ABNORMAL
))
1943 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1945 If we have tablejumps in the end of SRC1 and SRC2
1946 they have been already compared for equivalence in outgoing_edges_match ()
1947 so replace the references to TABLE1 by references to TABLE2. */
1952 if (tablejump_p (BB_END (osrc1
), &label1
, &table1
)
1953 && tablejump_p (BB_END (osrc2
), &label2
, &table2
)
1954 && label1
!= label2
)
1956 replace_label_data rr
;
1959 /* Replace references to LABEL1 with LABEL2. */
1962 rr
.update_label_nuses
= true;
1963 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1965 /* Do not replace the label in SRC1->END because when deleting
1966 a block whose end is a tablejump, the tablejump referenced
1967 from the instruction is deleted too. */
1968 if (insn
!= BB_END (osrc1
))
1969 for_each_rtx (&insn
, replace_label
, &rr
);
1974 /* Avoid splitting if possible. We must always split when SRC2 has
1975 EH predecessor edges, or we may end up with basic blocks with both
1976 normal and EH predecessor edges. */
1977 if (newpos2
== BB_HEAD (src2
)
1978 && !(EDGE_PRED (src2
, 0)->flags
& EDGE_EH
))
1982 if (newpos2
== BB_HEAD (src2
))
1984 /* Skip possible basic block header. */
1985 if (LABEL_P (newpos2
))
1986 newpos2
= NEXT_INSN (newpos2
);
1987 while (DEBUG_INSN_P (newpos2
))
1988 newpos2
= NEXT_INSN (newpos2
);
1989 if (NOTE_P (newpos2
))
1990 newpos2
= NEXT_INSN (newpos2
);
1991 while (DEBUG_INSN_P (newpos2
))
1992 newpos2
= NEXT_INSN (newpos2
);
1996 fprintf (dump_file
, "Splitting bb %i before %i insns\n",
1997 src2
->index
, nmatch
);
1998 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
2003 "Cross jumping from bb %i to bb %i; %i common insns\n",
2004 src1
->index
, src2
->index
, nmatch
);
2006 /* We may have some registers visible through the block. */
2007 df_set_bb_dirty (redirect_to
);
2010 redirect_edges_to
= redirect_to
;
2012 redirect_edges_to
= osrc2
;
2014 /* Recompute the frequencies and counts of outgoing edges. */
2015 FOR_EACH_EDGE (s
, ei
, redirect_edges_to
->succs
)
2019 basic_block d
= s
->dest
;
2021 if (FORWARDER_BLOCK_P (d
))
2022 d
= single_succ (d
);
2024 FOR_EACH_EDGE (s2
, ei
, src1
->succs
)
2026 basic_block d2
= s2
->dest
;
2027 if (FORWARDER_BLOCK_P (d2
))
2028 d2
= single_succ (d2
);
2033 s
->count
+= s2
->count
;
2035 /* Take care to update possible forwarder blocks. We verified
2036 that there is no more than one in the chain, so we can't run
2037 into infinite loop. */
2038 if (FORWARDER_BLOCK_P (s
->dest
))
2040 single_succ_edge (s
->dest
)->count
+= s2
->count
;
2041 s
->dest
->count
+= s2
->count
;
2042 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
2045 if (FORWARDER_BLOCK_P (s2
->dest
))
2047 single_succ_edge (s2
->dest
)->count
-= s2
->count
;
2048 if (single_succ_edge (s2
->dest
)->count
< 0)
2049 single_succ_edge (s2
->dest
)->count
= 0;
2050 s2
->dest
->count
-= s2
->count
;
2051 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
2052 if (s2
->dest
->frequency
< 0)
2053 s2
->dest
->frequency
= 0;
2054 if (s2
->dest
->count
< 0)
2055 s2
->dest
->count
= 0;
2058 if (!redirect_edges_to
->frequency
&& !src1
->frequency
)
2059 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
2062 = ((s
->probability
* redirect_edges_to
->frequency
+
2063 s2
->probability
* src1
->frequency
)
2064 / (redirect_edges_to
->frequency
+ src1
->frequency
));
2067 /* Adjust count and frequency for the block. An earlier jump
2068 threading pass may have left the profile in an inconsistent
2069 state (see update_bb_profile_for_threading) so we must be
2070 prepared for overflows. */
2074 tmp
->count
+= src1
->count
;
2075 tmp
->frequency
+= src1
->frequency
;
2076 if (tmp
->frequency
> BB_FREQ_MAX
)
2077 tmp
->frequency
= BB_FREQ_MAX
;
2078 if (tmp
== redirect_edges_to
)
2080 tmp
= find_fallthru_edge (tmp
->succs
)->dest
;
2083 update_br_prob_note (redirect_edges_to
);
2085 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
2087 /* Skip possible basic block header. */
2088 if (LABEL_P (newpos1
))
2089 newpos1
= NEXT_INSN (newpos1
);
2091 while (DEBUG_INSN_P (newpos1
))
2092 newpos1
= NEXT_INSN (newpos1
);
2094 if (NOTE_INSN_BASIC_BLOCK_P (newpos1
))
2095 newpos1
= NEXT_INSN (newpos1
);
2097 while (DEBUG_INSN_P (newpos1
))
2098 newpos1
= NEXT_INSN (newpos1
);
2100 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
2101 to_remove
= single_succ (redirect_from
);
2103 redirect_edge_and_branch_force (single_succ_edge (redirect_from
), redirect_to
);
2104 delete_basic_block (to_remove
);
2106 update_forwarder_flag (redirect_from
);
2107 if (redirect_to
!= src2
)
2108 update_forwarder_flag (src2
);
2113 /* Search the predecessors of BB for common insn sequences. When found,
2114 share code between them by redirecting control flow. Return true if
2115 any changes made. */
2118 try_crossjump_bb (int mode
, basic_block bb
)
2120 edge e
, e2
, fallthru
;
2122 unsigned max
, ix
, ix2
;
2124 /* Nothing to do if there is not at least two incoming edges. */
2125 if (EDGE_COUNT (bb
->preds
) < 2)
2128 /* Don't crossjump if this block ends in a computed jump,
2129 unless we are optimizing for size. */
2130 if (optimize_bb_for_size_p (bb
)
2131 && bb
!= EXIT_BLOCK_PTR
2132 && computed_jump_p (BB_END (bb
)))
2135 /* If we are partitioning hot/cold basic blocks, we don't want to
2136 mess up unconditional or indirect jumps that cross between hot
2139 Basic block partitioning may result in some jumps that appear to
2140 be optimizable (or blocks that appear to be mergeable), but which really
2141 must be left untouched (they are required to make it safely across
2142 partition boundaries). See the comments at the top of
2143 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
2145 if (BB_PARTITION (EDGE_PRED (bb
, 0)->src
) !=
2146 BB_PARTITION (EDGE_PRED (bb
, 1)->src
)
2147 || (EDGE_PRED (bb
, 0)->flags
& EDGE_CROSSING
))
2150 /* It is always cheapest to redirect a block that ends in a branch to
2151 a block that falls through into BB, as that adds no branches to the
2152 program. We'll try that combination first. */
2154 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
2156 if (EDGE_COUNT (bb
->preds
) > max
)
2159 fallthru
= find_fallthru_edge (bb
->preds
);
2162 for (ix
= 0; ix
< EDGE_COUNT (bb
->preds
);)
2164 e
= EDGE_PRED (bb
, ix
);
2167 /* As noted above, first try with the fallthru predecessor (or, a
2168 fallthru predecessor if we are in cfglayout mode). */
2171 /* Don't combine the fallthru edge into anything else.
2172 If there is a match, we'll do it the other way around. */
2175 /* If nothing changed since the last attempt, there is nothing
2178 && !((e
->src
->flags
& BB_MODIFIED
)
2179 || (fallthru
->src
->flags
& BB_MODIFIED
)))
2182 if (try_crossjump_to_edge (mode
, e
, fallthru
, dir_forward
))
2190 /* Non-obvious work limiting check: Recognize that we're going
2191 to call try_crossjump_bb on every basic block. So if we have
2192 two blocks with lots of outgoing edges (a switch) and they
2193 share lots of common destinations, then we would do the
2194 cross-jump check once for each common destination.
2196 Now, if the blocks actually are cross-jump candidates, then
2197 all of their destinations will be shared. Which means that
2198 we only need check them for cross-jump candidacy once. We
2199 can eliminate redundant checks of crossjump(A,B) by arbitrarily
2200 choosing to do the check from the block for which the edge
2201 in question is the first successor of A. */
2202 if (EDGE_SUCC (e
->src
, 0) != e
)
2205 for (ix2
= 0; ix2
< EDGE_COUNT (bb
->preds
); ix2
++)
2207 e2
= EDGE_PRED (bb
, ix2
);
2212 /* We've already checked the fallthru edge above. */
2216 /* The "first successor" check above only prevents multiple
2217 checks of crossjump(A,B). In order to prevent redundant
2218 checks of crossjump(B,A), require that A be the block
2219 with the lowest index. */
2220 if (e
->src
->index
> e2
->src
->index
)
2223 /* If nothing changed since the last attempt, there is nothing
2226 && !((e
->src
->flags
& BB_MODIFIED
)
2227 || (e2
->src
->flags
& BB_MODIFIED
)))
2230 /* Both e and e2 are not fallthru edges, so we can crossjump in either
2232 if (try_crossjump_to_edge (mode
, e
, e2
, dir_both
))
2242 crossjumps_occured
= true;
2247 /* Search the successors of BB for common insn sequences. When found,
2248 share code between them by moving it across the basic block
2249 boundary. Return true if any changes made. */
2252 try_head_merge_bb (basic_block bb
)
2254 basic_block final_dest_bb
= NULL
;
2255 int max_match
= INT_MAX
;
2257 rtx
*headptr
, *currptr
, *nextptr
;
2258 bool changed
, moveall
;
2260 rtx e0_last_head
, cond
, move_before
;
2261 unsigned nedges
= EDGE_COUNT (bb
->succs
);
2262 rtx jump
= BB_END (bb
);
2263 regset live
, live_union
;
2265 /* Nothing to do if there is not at least two outgoing edges. */
2269 /* Don't crossjump if this block ends in a computed jump,
2270 unless we are optimizing for size. */
2271 if (optimize_bb_for_size_p (bb
)
2272 && bb
!= EXIT_BLOCK_PTR
2273 && computed_jump_p (BB_END (bb
)))
2276 cond
= get_condition (jump
, &move_before
, true, false);
2277 if (cond
== NULL_RTX
)
2280 if (reg_mentioned_p (cc0_rtx
, jump
))
2281 move_before
= prev_nonnote_nondebug_insn (jump
);
2287 for (ix
= 0; ix
< nedges
; ix
++)
2288 if (EDGE_SUCC (bb
, ix
)->dest
== EXIT_BLOCK_PTR
)
2291 for (ix
= 0; ix
< nedges
; ix
++)
2293 edge e
= EDGE_SUCC (bb
, ix
);
2294 basic_block other_bb
= e
->dest
;
2296 if (df_get_bb_dirty (other_bb
))
2298 block_was_dirty
= true;
2302 if (e
->flags
& EDGE_ABNORMAL
)
2305 /* Normally, all destination blocks must only be reachable from this
2306 block, i.e. they must have one incoming edge.
2308 There is one special case we can handle, that of multiple consecutive
2309 jumps where the first jumps to one of the targets of the second jump.
2310 This happens frequently in switch statements for default labels.
2311 The structure is as follows:
2317 jump with targets A, B, C, D...
2319 has two incoming edges, from FINAL_DEST_BB and BB
2321 In this case, we can try to move the insns through BB and into
2323 if (EDGE_COUNT (other_bb
->preds
) != 1)
2325 edge incoming_edge
, incoming_bb_other_edge
;
2328 if (final_dest_bb
!= NULL
2329 || EDGE_COUNT (other_bb
->preds
) != 2)
2332 /* We must be able to move the insns across the whole block. */
2333 move_before
= BB_HEAD (bb
);
2334 while (!NONDEBUG_INSN_P (move_before
))
2335 move_before
= NEXT_INSN (move_before
);
2337 if (EDGE_COUNT (bb
->preds
) != 1)
2339 incoming_edge
= EDGE_PRED (bb
, 0);
2340 final_dest_bb
= incoming_edge
->src
;
2341 if (EDGE_COUNT (final_dest_bb
->succs
) != 2)
2343 FOR_EACH_EDGE (incoming_bb_other_edge
, ei
, final_dest_bb
->succs
)
2344 if (incoming_bb_other_edge
!= incoming_edge
)
2346 if (incoming_bb_other_edge
->dest
!= other_bb
)
2351 e0
= EDGE_SUCC (bb
, 0);
2352 e0_last_head
= NULL_RTX
;
2355 for (ix
= 1; ix
< nedges
; ix
++)
2357 edge e
= EDGE_SUCC (bb
, ix
);
2358 rtx e0_last
, e_last
;
2361 nmatch
= flow_find_head_matching_sequence (e0
->dest
, e
->dest
,
2362 &e0_last
, &e_last
, 0);
2366 if (nmatch
< max_match
)
2369 e0_last_head
= e0_last
;
2373 /* If we matched an entire block, we probably have to avoid moving the
2376 && e0_last_head
== BB_END (e0
->dest
)
2377 && (find_reg_note (e0_last_head
, REG_EH_REGION
, 0)
2378 || control_flow_insn_p (e0_last_head
)))
2384 e0_last_head
= prev_real_insn (e0_last_head
);
2385 while (DEBUG_INSN_P (e0_last_head
));
2391 /* We must find a union of the live registers at each of the end points. */
2392 live
= BITMAP_ALLOC (NULL
);
2393 live_union
= BITMAP_ALLOC (NULL
);
2395 currptr
= XNEWVEC (rtx
, nedges
);
2396 headptr
= XNEWVEC (rtx
, nedges
);
2397 nextptr
= XNEWVEC (rtx
, nedges
);
2399 for (ix
= 0; ix
< nedges
; ix
++)
2402 basic_block merge_bb
= EDGE_SUCC (bb
, ix
)->dest
;
2403 rtx head
= BB_HEAD (merge_bb
);
2405 while (!NONDEBUG_INSN_P (head
))
2406 head
= NEXT_INSN (head
);
2410 /* Compute the end point and live information */
2411 for (j
= 1; j
< max_match
; j
++)
2413 head
= NEXT_INSN (head
);
2414 while (!NONDEBUG_INSN_P (head
));
2415 simulate_backwards_to_point (merge_bb
, live
, head
);
2416 IOR_REG_SET (live_union
, live
);
2419 /* If we're moving across two blocks, verify the validity of the
2420 first move, then adjust the target and let the loop below deal
2421 with the final move. */
2422 if (final_dest_bb
!= NULL
)
2426 moveall
= can_move_insns_across (currptr
[0], e0_last_head
, move_before
,
2427 jump
, e0
->dest
, live_union
,
2431 if (move_upto
== NULL_RTX
)
2434 while (e0_last_head
!= move_upto
)
2436 df_simulate_one_insn_backwards (e0
->dest
, e0_last_head
,
2438 e0_last_head
= PREV_INSN (e0_last_head
);
2441 if (e0_last_head
== NULL_RTX
)
2444 jump
= BB_END (final_dest_bb
);
2445 cond
= get_condition (jump
, &move_before
, true, false);
2446 if (cond
== NULL_RTX
)
2449 if (reg_mentioned_p (cc0_rtx
, jump
))
2450 move_before
= prev_nonnote_nondebug_insn (jump
);
2460 moveall
= can_move_insns_across (currptr
[0], e0_last_head
,
2461 move_before
, jump
, e0
->dest
, live_union
,
2463 if (!moveall
&& move_upto
== NULL_RTX
)
2465 if (jump
== move_before
)
2468 /* Try again, using a different insertion point. */
2472 /* Don't try moving before a cc0 user, as that may invalidate
2474 if (reg_mentioned_p (cc0_rtx
, jump
))
2481 if (final_dest_bb
&& !moveall
)
2482 /* We haven't checked whether a partial move would be OK for the first
2483 move, so we have to fail this case. */
2489 if (currptr
[0] == move_upto
)
2491 for (ix
= 0; ix
< nedges
; ix
++)
2493 rtx curr
= currptr
[ix
];
2495 curr
= NEXT_INSN (curr
);
2496 while (!NONDEBUG_INSN_P (curr
));
2501 /* If we can't currently move all of the identical insns, remember
2502 each insn after the range that we'll merge. */
2504 for (ix
= 0; ix
< nedges
; ix
++)
2506 rtx curr
= currptr
[ix
];
2508 curr
= NEXT_INSN (curr
);
2509 while (!NONDEBUG_INSN_P (curr
));
2513 reorder_insns (headptr
[0], currptr
[0], PREV_INSN (move_before
));
2514 df_set_bb_dirty (EDGE_SUCC (bb
, 0)->dest
);
2515 if (final_dest_bb
!= NULL
)
2516 df_set_bb_dirty (final_dest_bb
);
2517 df_set_bb_dirty (bb
);
2518 for (ix
= 1; ix
< nedges
; ix
++)
2520 df_set_bb_dirty (EDGE_SUCC (bb
, ix
)->dest
);
2521 delete_insn_chain (headptr
[ix
], currptr
[ix
], false);
2525 if (jump
== move_before
)
2528 /* For the unmerged insns, try a different insertion point. */
2532 /* Don't try moving before a cc0 user, as that may invalidate
2534 if (reg_mentioned_p (cc0_rtx
, jump
))
2538 for (ix
= 0; ix
< nedges
; ix
++)
2539 currptr
[ix
] = headptr
[ix
] = nextptr
[ix
];
2549 crossjumps_occured
|= changed
;
2554 /* Return true if BB contains just bb note, or bb note followed
2555 by only DEBUG_INSNs. */
2558 trivially_empty_bb_p (basic_block bb
)
2560 rtx insn
= BB_END (bb
);
2564 if (insn
== BB_HEAD (bb
))
2566 if (!DEBUG_INSN_P (insn
))
2568 insn
= PREV_INSN (insn
);
2572 /* Do simple CFG optimizations - basic block merging, simplifying of jump
2573 instructions etc. Return nonzero if changes were made. */
2576 try_optimize_cfg (int mode
)
2578 bool changed_overall
= false;
2581 basic_block bb
, b
, next
;
2583 if (mode
& (CLEANUP_CROSSJUMP
| CLEANUP_THREADING
))
2586 crossjumps_occured
= false;
2589 update_forwarder_flag (bb
);
2591 if (! targetm
.cannot_modify_jumps_p ())
2594 /* Attempt to merge blocks as made possible by edge removal. If
2595 a block has only one successor, and the successor has only
2596 one predecessor, they may be combined. */
2599 block_was_dirty
= false;
2605 "\n\ntry_optimize_cfg iteration %i\n\n",
2608 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
;)
2612 bool changed_here
= false;
2614 /* Delete trivially dead basic blocks. This is either
2615 blocks with no predecessors, or empty blocks with no
2616 successors. However if the empty block with no
2617 successors is the successor of the ENTRY_BLOCK, it is
2618 kept. This ensures that the ENTRY_BLOCK will have a
2619 successor which is a precondition for many RTL
2620 passes. Empty blocks may result from expanding
2621 __builtin_unreachable (). */
2622 if (EDGE_COUNT (b
->preds
) == 0
2623 || (EDGE_COUNT (b
->succs
) == 0
2624 && trivially_empty_bb_p (b
)
2625 && single_succ_edge (ENTRY_BLOCK_PTR
)->dest
!= b
))
2628 if (EDGE_COUNT (b
->preds
) > 0)
2633 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2636 && BARRIER_P (BB_FOOTER (b
)))
2637 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2638 if ((e
->flags
& EDGE_FALLTHRU
)
2639 && BB_FOOTER (e
->src
) == NULL
)
2643 BB_FOOTER (e
->src
) = BB_FOOTER (b
);
2644 BB_FOOTER (b
) = NULL
;
2649 BB_FOOTER (e
->src
) = emit_barrier ();
2656 rtx last
= get_last_bb_insn (b
);
2657 if (last
&& BARRIER_P (last
))
2658 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2659 if ((e
->flags
& EDGE_FALLTHRU
))
2660 emit_barrier_after (BB_END (e
->src
));
2663 delete_basic_block (b
);
2665 /* Avoid trying to remove ENTRY_BLOCK_PTR. */
2666 b
= (c
== ENTRY_BLOCK_PTR
? c
->next_bb
: c
);
2670 /* Remove code labels no longer used. */
2671 if (single_pred_p (b
)
2672 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2673 && !(single_pred_edge (b
)->flags
& EDGE_COMPLEX
)
2674 && LABEL_P (BB_HEAD (b
))
2675 /* If the previous block ends with a branch to this
2676 block, we can't delete the label. Normally this
2677 is a condjump that is yet to be simplified, but
2678 if CASE_DROPS_THRU, this can be a tablejump with
2679 some element going to the same place as the
2680 default (fallthru). */
2681 && (single_pred (b
) == ENTRY_BLOCK_PTR
2682 || !JUMP_P (BB_END (single_pred (b
)))
2683 || ! label_is_jump_target_p (BB_HEAD (b
),
2684 BB_END (single_pred (b
)))))
2686 delete_insn (BB_HEAD (b
));
2688 fprintf (dump_file
, "Deleted label in block %i.\n",
2692 /* If we fall through an empty block, we can remove it. */
2693 if (!(mode
& (CLEANUP_CFGLAYOUT
| CLEANUP_NO_INSN_DEL
))
2694 && single_pred_p (b
)
2695 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2696 && !LABEL_P (BB_HEAD (b
))
2697 && FORWARDER_BLOCK_P (b
)
2698 /* Note that forwarder_block_p true ensures that
2699 there is a successor for this block. */
2700 && (single_succ_edge (b
)->flags
& EDGE_FALLTHRU
)
2701 && n_basic_blocks
> NUM_FIXED_BLOCKS
+ 1)
2705 "Deleting fallthru block %i.\n",
2708 c
= b
->prev_bb
== ENTRY_BLOCK_PTR
? b
->next_bb
: b
->prev_bb
;
2709 redirect_edge_succ_nodup (single_pred_edge (b
),
2711 delete_basic_block (b
);
2717 /* Merge B with its single successor, if any. */
2718 if (single_succ_p (b
)
2719 && (s
= single_succ_edge (b
))
2720 && !(s
->flags
& EDGE_COMPLEX
)
2721 && (c
= s
->dest
) != EXIT_BLOCK_PTR
2722 && single_pred_p (c
)
2725 /* When not in cfg_layout mode use code aware of reordering
2726 INSN. This code possibly creates new basic blocks so it
2727 does not fit merge_blocks interface and is kept here in
2728 hope that it will become useless once more of compiler
2729 is transformed to use cfg_layout mode. */
2731 if ((mode
& CLEANUP_CFGLAYOUT
)
2732 && can_merge_blocks_p (b
, c
))
2734 merge_blocks (b
, c
);
2735 update_forwarder_flag (b
);
2736 changed_here
= true;
2738 else if (!(mode
& CLEANUP_CFGLAYOUT
)
2739 /* If the jump insn has side effects,
2740 we can't kill the edge. */
2741 && (!JUMP_P (BB_END (b
))
2742 || (reload_completed
2743 ? simplejump_p (BB_END (b
))
2744 : (onlyjump_p (BB_END (b
))
2745 && !tablejump_p (BB_END (b
),
2747 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
2750 changed_here
= true;
2754 /* Simplify branch over branch. */
2755 if ((mode
& CLEANUP_EXPENSIVE
)
2756 && !(mode
& CLEANUP_CFGLAYOUT
)
2757 && try_simplify_condjump (b
))
2758 changed_here
= true;
2760 /* If B has a single outgoing edge, but uses a
2761 non-trivial jump instruction without side-effects, we
2762 can either delete the jump entirely, or replace it
2763 with a simple unconditional jump. */
2764 if (single_succ_p (b
)
2765 && single_succ (b
) != EXIT_BLOCK_PTR
2766 && onlyjump_p (BB_END (b
))
2767 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
)
2768 && try_redirect_by_replacing_jump (single_succ_edge (b
),
2770 (mode
& CLEANUP_CFGLAYOUT
) != 0))
2772 update_forwarder_flag (b
);
2773 changed_here
= true;
2776 /* Simplify branch to branch. */
2777 if (try_forward_edges (mode
, b
))
2779 update_forwarder_flag (b
);
2780 changed_here
= true;
2783 /* Look for shared code between blocks. */
2784 if ((mode
& CLEANUP_CROSSJUMP
)
2785 && try_crossjump_bb (mode
, b
))
2786 changed_here
= true;
2788 if ((mode
& CLEANUP_CROSSJUMP
)
2789 /* This can lengthen register lifetimes. Do it only after
2792 && try_head_merge_bb (b
))
2793 changed_here
= true;
2795 /* Don't get confused by the index shift caused by
2803 if ((mode
& CLEANUP_CROSSJUMP
)
2804 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
2807 if (block_was_dirty
)
2809 /* This should only be set by head-merging. */
2810 gcc_assert (mode
& CLEANUP_CROSSJUMP
);
2814 #ifdef ENABLE_CHECKING
2816 verify_flow_info ();
2819 changed_overall
|= changed
;
2826 b
->flags
&= ~(BB_FORWARDER_BLOCK
| BB_NONTHREADABLE_BLOCK
);
2828 return changed_overall
;
2831 /* Delete all unreachable basic blocks. */
2834 delete_unreachable_blocks (void)
2836 bool changed
= false;
2837 basic_block b
, prev_bb
;
2839 find_unreachable_blocks ();
2841 /* When we're in GIMPLE mode and there may be debug insns, we should
2842 delete blocks in reverse dominator order, so as to get a chance
2843 to substitute all released DEFs into debug stmts. If we don't
2844 have dominators information, walking blocks backward gets us a
2845 better chance of retaining most debug information than
2847 if (MAY_HAVE_DEBUG_INSNS
&& current_ir_type () == IR_GIMPLE
2848 && dom_info_available_p (CDI_DOMINATORS
))
2850 for (b
= EXIT_BLOCK_PTR
->prev_bb
; b
!= ENTRY_BLOCK_PTR
; b
= prev_bb
)
2852 prev_bb
= b
->prev_bb
;
2854 if (!(b
->flags
& BB_REACHABLE
))
2856 /* Speed up the removal of blocks that don't dominate
2857 others. Walking backwards, this should be the common
2859 if (!first_dom_son (CDI_DOMINATORS
, b
))
2860 delete_basic_block (b
);
2864 = get_all_dominated_blocks (CDI_DOMINATORS
, b
);
2870 prev_bb
= b
->prev_bb
;
2872 gcc_assert (!(b
->flags
& BB_REACHABLE
));
2874 delete_basic_block (b
);
2886 for (b
= EXIT_BLOCK_PTR
->prev_bb
; b
!= ENTRY_BLOCK_PTR
; b
= prev_bb
)
2888 prev_bb
= b
->prev_bb
;
2890 if (!(b
->flags
& BB_REACHABLE
))
2892 delete_basic_block (b
);
2899 tidy_fallthru_edges ();
2903 /* Delete any jump tables never referenced. We can't delete them at the
2904 time of removing tablejump insn as they are referenced by the preceding
2905 insns computing the destination, so we delay deleting and garbagecollect
2906 them once life information is computed. */
2908 delete_dead_jumptables (void)
2912 /* A dead jump table does not belong to any basic block. Scan insns
2913 between two adjacent basic blocks. */
2918 for (insn
= NEXT_INSN (BB_END (bb
));
2919 insn
&& !NOTE_INSN_BASIC_BLOCK_P (insn
);
2922 next
= NEXT_INSN (insn
);
2924 && LABEL_NUSES (insn
) == LABEL_PRESERVE_P (insn
)
2925 && JUMP_TABLE_DATA_P (next
))
2927 rtx label
= insn
, jump
= next
;
2930 fprintf (dump_file
, "Dead jumptable %i removed\n",
2933 next
= NEXT_INSN (next
);
2935 delete_insn (label
);
2942 /* Tidy the CFG by deleting unreachable code and whatnot. */
2945 cleanup_cfg (int mode
)
2947 bool changed
= false;
2949 /* Set the cfglayout mode flag here. We could update all the callers
2950 but that is just inconvenient, especially given that we eventually
2951 want to have cfglayout mode as the default. */
2952 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2953 mode
|= CLEANUP_CFGLAYOUT
;
2955 timevar_push (TV_CLEANUP_CFG
);
2956 if (delete_unreachable_blocks ())
2959 /* We've possibly created trivially dead code. Cleanup it right
2960 now to introduce more opportunities for try_optimize_cfg. */
2961 if (!(mode
& (CLEANUP_NO_INSN_DEL
))
2962 && !reload_completed
)
2963 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2968 /* To tail-merge blocks ending in the same noreturn function (e.g.
2969 a call to abort) we have to insert fake edges to exit. Do this
2970 here once. The fake edges do not interfere with any other CFG
2972 if (mode
& CLEANUP_CROSSJUMP
)
2973 add_noreturn_fake_exit_edges ();
2975 if (!dbg_cnt (cfg_cleanup
))
2978 while (try_optimize_cfg (mode
))
2980 delete_unreachable_blocks (), changed
= true;
2981 if (!(mode
& CLEANUP_NO_INSN_DEL
))
2983 /* Try to remove some trivially dead insns when doing an expensive
2984 cleanup. But delete_trivially_dead_insns doesn't work after
2985 reload (it only handles pseudos) and run_fast_dce is too costly
2986 to run in every iteration.
2988 For effective cross jumping, we really want to run a fast DCE to
2989 clean up any dead conditions, or they get in the way of performing
2992 Other transformations in cleanup_cfg are not so sensitive to dead
2993 code, so delete_trivially_dead_insns or even doing nothing at all
2995 if ((mode
& CLEANUP_EXPENSIVE
) && !reload_completed
2996 && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
2998 if ((mode
& CLEANUP_CROSSJUMP
) && crossjumps_occured
)
3005 if (mode
& CLEANUP_CROSSJUMP
)
3006 remove_fake_exit_edges ();
3008 /* Don't call delete_dead_jumptables in cfglayout mode, because
3009 that function assumes that jump tables are in the insns stream.
3010 But we also don't _have_ to delete dead jumptables in cfglayout
3011 mode because we shouldn't even be looking at things that are
3012 not in a basic block. Dead jumptables are cleaned up when
3013 going out of cfglayout mode. */
3014 if (!(mode
& CLEANUP_CFGLAYOUT
))
3015 delete_dead_jumptables ();
3017 /* ??? We probably do this way too often. */
3020 || (mode
& CLEANUP_CFG_CHANGED
)))
3023 timevar_push (TV_REPAIR_LOOPS
);
3024 /* The above doesn't preserve dominance info if available. */
3025 gcc_assert (!dom_info_available_p (CDI_DOMINATORS
));
3026 calculate_dominance_info (CDI_DOMINATORS
);
3027 changed_bbs
= BITMAP_ALLOC (NULL
);
3028 fix_loop_structure (changed_bbs
);
3029 BITMAP_FREE (changed_bbs
);
3030 free_dominance_info (CDI_DOMINATORS
);
3031 timevar_pop (TV_REPAIR_LOOPS
);
3034 timevar_pop (TV_CLEANUP_CFG
);
3042 delete_trivially_dead_insns (get_insns (), max_reg_num ());
3044 dump_flow_info (dump_file
, dump_flags
);
3045 cleanup_cfg ((optimize
? CLEANUP_EXPENSIVE
: 0)
3046 | (flag_thread_jumps
? CLEANUP_THREADING
: 0));
3050 struct rtl_opt_pass pass_jump
=
3055 OPTGROUP_NONE
, /* optinfo_flags */
3057 execute_jump
, /* execute */
3060 0, /* static_pass_number */
3061 TV_JUMP
, /* tv_id */
3062 0, /* properties_required */
3063 0, /* properties_provided */
3064 0, /* properties_destroyed */
3065 TODO_ggc_collect
, /* todo_flags_start */
3066 TODO_verify_rtl_sharing
, /* todo_flags_finish */
3071 execute_jump2 (void)
3073 cleanup_cfg (flag_crossjumping
? CLEANUP_CROSSJUMP
: 0);
3077 struct rtl_opt_pass pass_jump2
=
3082 OPTGROUP_NONE
, /* optinfo_flags */
3084 execute_jump2
, /* execute */
3087 0, /* static_pass_number */
3088 TV_JUMP
, /* tv_id */
3089 0, /* properties_required */
3090 0, /* properties_provided */
3091 0, /* properties_destroyed */
3092 TODO_ggc_collect
, /* todo_flags_start */
3093 TODO_verify_rtl_sharing
, /* todo_flags_finish */