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
4 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"
43 #include "insn-config.h"
46 #include "diagnostic-core.h"
52 #include "cfglayout.h"
54 #include "tree-pass.h"
61 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
63 /* Set to true when we are running first pass of try_optimize_cfg loop. */
64 static bool first_pass
;
66 /* Set to true if crossjumps occured in the latest run of try_optimize_cfg. */
67 static bool crossjumps_occured
;
69 /* Set to true if we couldn't run an optimization due to stale liveness
70 information; we should run df_analyze to enable more opportunities. */
71 static bool block_was_dirty
;
73 static bool try_crossjump_to_edge (int, edge
, edge
);
74 static bool try_crossjump_bb (int, basic_block
);
75 static bool outgoing_edges_match (int, basic_block
, basic_block
);
76 static bool old_insns_match_p (int, rtx
, rtx
);
78 static void merge_blocks_move_predecessor_nojumps (basic_block
, basic_block
);
79 static void merge_blocks_move_successor_nojumps (basic_block
, basic_block
);
80 static bool try_optimize_cfg (int);
81 static bool try_simplify_condjump (basic_block
);
82 static bool try_forward_edges (int, basic_block
);
83 static edge
thread_jump (edge
, basic_block
);
84 static bool mark_effect (rtx
, bitmap
);
85 static void notice_new_block (basic_block
);
86 static void update_forwarder_flag (basic_block
);
87 static int mentions_nonequal_regs (rtx
*, void *);
88 static void merge_memattrs (rtx
, rtx
);
90 /* Set flags for newly created block. */
93 notice_new_block (basic_block bb
)
98 if (forwarder_block_p (bb
))
99 bb
->flags
|= BB_FORWARDER_BLOCK
;
102 /* Recompute forwarder flag after block has been modified. */
105 update_forwarder_flag (basic_block bb
)
107 if (forwarder_block_p (bb
))
108 bb
->flags
|= BB_FORWARDER_BLOCK
;
110 bb
->flags
&= ~BB_FORWARDER_BLOCK
;
113 /* Simplify a conditional jump around an unconditional jump.
114 Return true if something changed. */
117 try_simplify_condjump (basic_block cbranch_block
)
119 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
120 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
123 /* Verify that there are exactly two successors. */
124 if (EDGE_COUNT (cbranch_block
->succs
) != 2)
127 /* Verify that we've got a normal conditional branch at the end
129 cbranch_insn
= BB_END (cbranch_block
);
130 if (!any_condjump_p (cbranch_insn
))
133 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
134 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
136 /* The next block must not have multiple predecessors, must not
137 be the last block in the function, and must contain just the
138 unconditional jump. */
139 jump_block
= cbranch_fallthru_edge
->dest
;
140 if (!single_pred_p (jump_block
)
141 || jump_block
->next_bb
== EXIT_BLOCK_PTR
142 || !FORWARDER_BLOCK_P (jump_block
))
144 jump_dest_block
= single_succ (jump_block
);
146 /* If we are partitioning hot/cold basic blocks, we don't want to
147 mess up unconditional or indirect jumps that cross between hot
150 Basic block partitioning may result in some jumps that appear to
151 be optimizable (or blocks that appear to be mergeable), but which really
152 must be left untouched (they are required to make it safely across
153 partition boundaries). See the comments at the top of
154 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
156 if (BB_PARTITION (jump_block
) != BB_PARTITION (jump_dest_block
)
157 || (cbranch_jump_edge
->flags
& EDGE_CROSSING
))
160 /* The conditional branch must target the block after the
161 unconditional branch. */
162 cbranch_dest_block
= cbranch_jump_edge
->dest
;
164 if (cbranch_dest_block
== EXIT_BLOCK_PTR
165 || !can_fallthru (jump_block
, cbranch_dest_block
))
168 /* Invert the conditional branch. */
169 if (!invert_jump (cbranch_insn
, block_label (jump_dest_block
), 0))
173 fprintf (dump_file
, "Simplifying condjump %i around jump %i\n",
174 INSN_UID (cbranch_insn
), INSN_UID (BB_END (jump_block
)));
176 /* Success. Update the CFG to match. Note that after this point
177 the edge variable names appear backwards; the redirection is done
178 this way to preserve edge profile data. */
179 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
181 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
183 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
184 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
185 update_br_prob_note (cbranch_block
);
187 /* Delete the block with the unconditional jump, and clean up the mess. */
188 delete_basic_block (jump_block
);
189 tidy_fallthru_edge (cbranch_jump_edge
);
190 update_forwarder_flag (cbranch_block
);
195 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
196 on register. Used by jump threading. */
199 mark_effect (rtx exp
, regset nonequal
)
203 switch (GET_CODE (exp
))
205 /* In case we do clobber the register, mark it as equal, as we know the
206 value is dead so it don't have to match. */
208 if (REG_P (XEXP (exp
, 0)))
210 dest
= XEXP (exp
, 0);
211 regno
= REGNO (dest
);
212 CLEAR_REGNO_REG_SET (nonequal
, regno
);
213 if (regno
< FIRST_PSEUDO_REGISTER
)
215 int n
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
217 CLEAR_REGNO_REG_SET (nonequal
, regno
+ n
);
223 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
225 dest
= SET_DEST (exp
);
230 regno
= REGNO (dest
);
231 SET_REGNO_REG_SET (nonequal
, regno
);
232 if (regno
< FIRST_PSEUDO_REGISTER
)
234 int n
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
236 SET_REGNO_REG_SET (nonequal
, regno
+ n
);
245 /* Return nonzero if X is a register set in regset DATA.
246 Called via for_each_rtx. */
248 mentions_nonequal_regs (rtx
*x
, void *data
)
250 regset nonequal
= (regset
) data
;
256 if (REGNO_REG_SET_P (nonequal
, regno
))
258 if (regno
< FIRST_PSEUDO_REGISTER
)
260 int n
= hard_regno_nregs
[regno
][GET_MODE (*x
)];
262 if (REGNO_REG_SET_P (nonequal
, regno
+ n
))
268 /* Attempt to prove that the basic block B will have no side effects and
269 always continues in the same edge if reached via E. Return the edge
270 if exist, NULL otherwise. */
273 thread_jump (edge e
, basic_block b
)
275 rtx set1
, set2
, cond1
, cond2
, insn
;
276 enum rtx_code code1
, code2
, reversed_code2
;
277 bool reverse1
= false;
281 reg_set_iterator rsi
;
283 if (b
->flags
& BB_NONTHREADABLE_BLOCK
)
286 /* At the moment, we do handle only conditional jumps, but later we may
287 want to extend this code to tablejumps and others. */
288 if (EDGE_COUNT (e
->src
->succs
) != 2)
290 if (EDGE_COUNT (b
->succs
) != 2)
292 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
296 /* Second branch must end with onlyjump, as we will eliminate the jump. */
297 if (!any_condjump_p (BB_END (e
->src
)))
300 if (!any_condjump_p (BB_END (b
)) || !onlyjump_p (BB_END (b
)))
302 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
306 set1
= pc_set (BB_END (e
->src
));
307 set2
= pc_set (BB_END (b
));
308 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
309 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
312 cond1
= XEXP (SET_SRC (set1
), 0);
313 cond2
= XEXP (SET_SRC (set2
), 0);
315 code1
= reversed_comparison_code (cond1
, BB_END (e
->src
));
317 code1
= GET_CODE (cond1
);
319 code2
= GET_CODE (cond2
);
320 reversed_code2
= reversed_comparison_code (cond2
, BB_END (b
));
322 if (!comparison_dominates_p (code1
, code2
)
323 && !comparison_dominates_p (code1
, reversed_code2
))
326 /* Ensure that the comparison operators are equivalent.
327 ??? This is far too pessimistic. We should allow swapped operands,
328 different CCmodes, or for example comparisons for interval, that
329 dominate even when operands are not equivalent. */
330 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
331 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
334 /* Short circuit cases where block B contains some side effects, as we can't
336 for (insn
= NEXT_INSN (BB_HEAD (b
)); insn
!= NEXT_INSN (BB_END (b
));
337 insn
= NEXT_INSN (insn
))
338 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
340 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
346 /* First process all values computed in the source basic block. */
347 for (insn
= NEXT_INSN (BB_HEAD (e
->src
));
348 insn
!= NEXT_INSN (BB_END (e
->src
));
349 insn
= NEXT_INSN (insn
))
351 cselib_process_insn (insn
);
353 nonequal
= BITMAP_ALLOC (NULL
);
354 CLEAR_REG_SET (nonequal
);
356 /* Now assume that we've continued by the edge E to B and continue
357 processing as if it were same basic block.
358 Our goal is to prove that whole block is an NOOP. */
360 for (insn
= NEXT_INSN (BB_HEAD (b
));
361 insn
!= NEXT_INSN (BB_END (b
)) && !failed
;
362 insn
= NEXT_INSN (insn
))
366 rtx pat
= PATTERN (insn
);
368 if (GET_CODE (pat
) == PARALLEL
)
370 for (i
= 0; i
< (unsigned)XVECLEN (pat
, 0); i
++)
371 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
374 failed
|= mark_effect (pat
, nonequal
);
377 cselib_process_insn (insn
);
380 /* Later we should clear nonequal of dead registers. So far we don't
381 have life information in cfg_cleanup. */
384 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
388 /* cond2 must not mention any register that is not equal to the
390 if (for_each_rtx (&cond2
, mentions_nonequal_regs
, nonequal
))
393 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, rsi
)
396 BITMAP_FREE (nonequal
);
398 if ((comparison_dominates_p (code1
, code2
) != 0)
399 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
400 return BRANCH_EDGE (b
);
402 return FALLTHRU_EDGE (b
);
405 BITMAP_FREE (nonequal
);
410 /* Attempt to forward edges leaving basic block B.
411 Return true if successful. */
414 try_forward_edges (int mode
, basic_block b
)
416 bool changed
= false;
418 edge e
, *threaded_edges
= NULL
;
420 /* If we are partitioning hot/cold basic blocks, we don't want to
421 mess up unconditional or indirect jumps that cross between hot
424 Basic block partitioning may result in some jumps that appear to
425 be optimizable (or blocks that appear to be mergeable), but which really
426 must be left untouched (they are required to make it safely across
427 partition boundaries). See the comments at the top of
428 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
430 if (find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
433 for (ei
= ei_start (b
->succs
); (e
= ei_safe_edge (ei
)); )
435 basic_block target
, first
;
436 int counter
, goto_locus
;
437 bool threaded
= false;
438 int nthreaded_edges
= 0;
439 bool may_thread
= first_pass
|| (b
->flags
& BB_MODIFIED
) != 0;
441 /* Skip complex edges because we don't know how to update them.
443 Still handle fallthru edges, as we can succeed to forward fallthru
444 edge to the same place as the branch edge of conditional branch
445 and turn conditional branch to an unconditional branch. */
446 if (e
->flags
& EDGE_COMPLEX
)
452 target
= first
= e
->dest
;
453 counter
= NUM_FIXED_BLOCKS
;
454 goto_locus
= e
->goto_locus
;
456 /* If we are partitioning hot/cold basic_blocks, we don't want to mess
457 up jumps that cross between hot/cold sections.
459 Basic block partitioning may result in some jumps that appear
460 to be optimizable (or blocks that appear to be mergeable), but which
461 really must be left untouched (they are required to make it safely
462 across partition boundaries). See the comments at the top of
463 bb-reorder.c:partition_hot_cold_basic_blocks for complete
466 if (first
!= EXIT_BLOCK_PTR
467 && find_reg_note (BB_END (first
), REG_CROSSING_JUMP
, NULL_RTX
))
470 while (counter
< n_basic_blocks
)
472 basic_block new_target
= NULL
;
473 bool new_target_threaded
= false;
474 may_thread
|= (target
->flags
& BB_MODIFIED
) != 0;
476 if (FORWARDER_BLOCK_P (target
)
477 && !(single_succ_edge (target
)->flags
& EDGE_CROSSING
)
478 && single_succ (target
) != EXIT_BLOCK_PTR
)
480 /* Bypass trivial infinite loops. */
481 new_target
= single_succ (target
);
482 if (target
== new_target
)
483 counter
= n_basic_blocks
;
486 /* When not optimizing, ensure that edges or forwarder
487 blocks with different locus are not optimized out. */
488 int locus
= single_succ_edge (target
)->goto_locus
;
490 if (locus
&& goto_locus
&& !locator_eq (locus
, goto_locus
))
491 counter
= n_basic_blocks
;
495 if (INSN_P (BB_END (target
)))
497 locus
= INSN_LOCATOR (BB_END (target
));
499 if (locus
&& goto_locus
500 && !locator_eq (locus
, goto_locus
))
501 counter
= n_basic_blocks
;
508 /* Allow to thread only over one edge at time to simplify updating
510 else if ((mode
& CLEANUP_THREADING
) && may_thread
)
512 edge t
= thread_jump (e
, target
);
516 threaded_edges
= XNEWVEC (edge
, n_basic_blocks
);
521 /* Detect an infinite loop across blocks not
522 including the start block. */
523 for (i
= 0; i
< nthreaded_edges
; ++i
)
524 if (threaded_edges
[i
] == t
)
526 if (i
< nthreaded_edges
)
528 counter
= n_basic_blocks
;
533 /* Detect an infinite loop across the start block. */
537 gcc_assert (nthreaded_edges
< n_basic_blocks
- NUM_FIXED_BLOCKS
);
538 threaded_edges
[nthreaded_edges
++] = t
;
540 new_target
= t
->dest
;
541 new_target_threaded
= true;
550 threaded
|= new_target_threaded
;
553 if (counter
>= n_basic_blocks
)
556 fprintf (dump_file
, "Infinite loop in BB %i.\n",
559 else if (target
== first
)
560 ; /* We didn't do anything. */
563 /* Save the values now, as the edge may get removed. */
564 gcov_type edge_count
= e
->count
;
565 int edge_probability
= e
->probability
;
569 e
->goto_locus
= goto_locus
;
571 /* Don't force if target is exit block. */
572 if (threaded
&& target
!= EXIT_BLOCK_PTR
)
574 notice_new_block (redirect_edge_and_branch_force (e
, target
));
576 fprintf (dump_file
, "Conditionals threaded.\n");
578 else if (!redirect_edge_and_branch (e
, target
))
582 "Forwarding edge %i->%i to %i failed.\n",
583 b
->index
, e
->dest
->index
, target
->index
);
588 /* We successfully forwarded the edge. Now update profile
589 data: for each edge we traversed in the chain, remove
590 the original edge's execution count. */
591 edge_frequency
= ((edge_probability
* b
->frequency
592 + REG_BR_PROB_BASE
/ 2)
595 if (!FORWARDER_BLOCK_P (b
) && forwarder_block_p (b
))
596 b
->flags
|= BB_FORWARDER_BLOCK
;
602 if (!single_succ_p (first
))
604 gcc_assert (n
< nthreaded_edges
);
605 t
= threaded_edges
[n
++];
606 gcc_assert (t
->src
== first
);
607 update_bb_profile_for_threading (first
, edge_frequency
,
609 update_br_prob_note (first
);
613 first
->count
-= edge_count
;
614 if (first
->count
< 0)
616 first
->frequency
-= edge_frequency
;
617 if (first
->frequency
< 0)
618 first
->frequency
= 0;
619 /* It is possible that as the result of
620 threading we've removed edge as it is
621 threaded to the fallthru edge. Avoid
622 getting out of sync. */
623 if (n
< nthreaded_edges
624 && first
== threaded_edges
[n
]->src
)
626 t
= single_succ_edge (first
);
629 t
->count
-= edge_count
;
634 while (first
!= target
);
643 free (threaded_edges
);
648 /* Blocks A and B are to be merged into a single block. A has no incoming
649 fallthru edge, so it can be moved before B without adding or modifying
650 any jumps (aside from the jump from A to B). */
653 merge_blocks_move_predecessor_nojumps (basic_block a
, basic_block b
)
657 /* If we are partitioning hot/cold basic blocks, we don't want to
658 mess up unconditional or indirect jumps that cross between hot
661 Basic block partitioning may result in some jumps that appear to
662 be optimizable (or blocks that appear to be mergeable), but which really
663 must be left untouched (they are required to make it safely across
664 partition boundaries). See the comments at the top of
665 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
667 if (BB_PARTITION (a
) != BB_PARTITION (b
))
670 barrier
= next_nonnote_insn (BB_END (a
));
671 gcc_assert (BARRIER_P (barrier
));
672 delete_insn (barrier
);
674 /* Scramble the insn chain. */
675 if (BB_END (a
) != PREV_INSN (BB_HEAD (b
)))
676 reorder_insns_nobb (BB_HEAD (a
), BB_END (a
), PREV_INSN (BB_HEAD (b
)));
680 fprintf (dump_file
, "Moved block %d before %d and merged.\n",
683 /* Swap the records for the two blocks around. */
686 link_block (a
, b
->prev_bb
);
688 /* Now blocks A and B are contiguous. Merge them. */
692 /* Blocks A and B are to be merged into a single block. B has no outgoing
693 fallthru edge, so it can be moved after A without adding or modifying
694 any jumps (aside from the jump from A to B). */
697 merge_blocks_move_successor_nojumps (basic_block a
, basic_block b
)
699 rtx barrier
, real_b_end
;
702 /* If we are partitioning hot/cold basic blocks, we don't want to
703 mess up unconditional or indirect jumps that cross between hot
706 Basic block partitioning may result in some jumps that appear to
707 be optimizable (or blocks that appear to be mergeable), but which really
708 must be left untouched (they are required to make it safely across
709 partition boundaries). See the comments at the top of
710 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
712 if (BB_PARTITION (a
) != BB_PARTITION (b
))
715 real_b_end
= BB_END (b
);
717 /* If there is a jump table following block B temporarily add the jump table
718 to block B so that it will also be moved to the correct location. */
719 if (tablejump_p (BB_END (b
), &label
, &table
)
720 && prev_active_insn (label
) == BB_END (b
))
725 /* There had better have been a barrier there. Delete it. */
726 barrier
= NEXT_INSN (BB_END (b
));
727 if (barrier
&& BARRIER_P (barrier
))
728 delete_insn (barrier
);
731 /* Scramble the insn chain. */
732 reorder_insns_nobb (BB_HEAD (b
), BB_END (b
), BB_END (a
));
734 /* Restore the real end of b. */
735 BB_END (b
) = real_b_end
;
738 fprintf (dump_file
, "Moved block %d after %d and merged.\n",
741 /* Now blocks A and B are contiguous. Merge them. */
745 /* Attempt to merge basic blocks that are potentially non-adjacent.
746 Return NULL iff the attempt failed, otherwise return basic block
747 where cleanup_cfg should continue. Because the merging commonly
748 moves basic block away or introduces another optimization
749 possibility, return basic block just before B so cleanup_cfg don't
752 It may be good idea to return basic block before C in the case
753 C has been moved after B and originally appeared earlier in the
754 insn sequence, but we have no information available about the
755 relative ordering of these two. Hopefully it is not too common. */
758 merge_blocks_move (edge e
, basic_block b
, basic_block c
, int mode
)
762 /* If we are partitioning hot/cold basic blocks, we don't want to
763 mess up unconditional or indirect jumps that cross between hot
766 Basic block partitioning may result in some jumps that appear to
767 be optimizable (or blocks that appear to be mergeable), but which really
768 must be left untouched (they are required to make it safely across
769 partition boundaries). See the comments at the top of
770 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
772 if (BB_PARTITION (b
) != BB_PARTITION (c
))
775 /* If B has a fallthru edge to C, no need to move anything. */
776 if (e
->flags
& EDGE_FALLTHRU
)
778 int b_index
= b
->index
, c_index
= c
->index
;
780 update_forwarder_flag (b
);
783 fprintf (dump_file
, "Merged %d and %d without moving.\n",
786 return b
->prev_bb
== ENTRY_BLOCK_PTR
? b
: b
->prev_bb
;
789 /* Otherwise we will need to move code around. Do that only if expensive
790 transformations are allowed. */
791 else if (mode
& CLEANUP_EXPENSIVE
)
793 edge tmp_edge
, b_fallthru_edge
;
794 bool c_has_outgoing_fallthru
;
795 bool b_has_incoming_fallthru
;
798 /* Avoid overactive code motion, as the forwarder blocks should be
799 eliminated by edge redirection instead. One exception might have
800 been if B is a forwarder block and C has no fallthru edge, but
801 that should be cleaned up by bb-reorder instead. */
802 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
805 /* We must make sure to not munge nesting of lexical blocks,
806 and loop notes. This is done by squeezing out all the notes
807 and leaving them there to lie. Not ideal, but functional. */
809 FOR_EACH_EDGE (tmp_edge
, ei
, c
->succs
)
810 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
813 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
815 FOR_EACH_EDGE (tmp_edge
, ei
, b
->preds
)
816 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
819 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
820 b_fallthru_edge
= tmp_edge
;
823 next
= next
->prev_bb
;
825 /* Otherwise, we're going to try to move C after B. If C does
826 not have an outgoing fallthru, then it can be moved
827 immediately after B without introducing or modifying jumps. */
828 if (! c_has_outgoing_fallthru
)
830 merge_blocks_move_successor_nojumps (b
, c
);
831 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
834 /* If B does not have an incoming fallthru, then it can be moved
835 immediately before C without introducing or modifying jumps.
836 C cannot be the first block, so we do not have to worry about
837 accessing a non-existent block. */
839 if (b_has_incoming_fallthru
)
843 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
845 bb
= force_nonfallthru (b_fallthru_edge
);
847 notice_new_block (bb
);
850 merge_blocks_move_predecessor_nojumps (b
, c
);
851 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
858 /* Removes the memory attributes of MEM expression
859 if they are not equal. */
862 merge_memattrs (rtx x
, rtx y
)
871 if (x
== 0 || y
== 0)
876 if (code
!= GET_CODE (y
))
879 if (GET_MODE (x
) != GET_MODE (y
))
882 if (code
== MEM
&& MEM_ATTRS (x
) != MEM_ATTRS (y
))
886 else if (! MEM_ATTRS (y
))
892 if (MEM_ALIAS_SET (x
) != MEM_ALIAS_SET (y
))
894 set_mem_alias_set (x
, 0);
895 set_mem_alias_set (y
, 0);
898 if (! mem_expr_equal_p (MEM_EXPR (x
), MEM_EXPR (y
)))
902 set_mem_offset (x
, 0);
903 set_mem_offset (y
, 0);
905 else if (MEM_OFFSET (x
) != MEM_OFFSET (y
))
907 set_mem_offset (x
, 0);
908 set_mem_offset (y
, 0);
913 else if (!MEM_SIZE (y
))
916 mem_size
= GEN_INT (MAX (INTVAL (MEM_SIZE (x
)),
917 INTVAL (MEM_SIZE (y
))));
918 set_mem_size (x
, mem_size
);
919 set_mem_size (y
, mem_size
);
921 set_mem_align (x
, MIN (MEM_ALIGN (x
), MEM_ALIGN (y
)));
922 set_mem_align (y
, MEM_ALIGN (x
));
926 fmt
= GET_RTX_FORMAT (code
);
927 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
932 /* Two vectors must have the same length. */
933 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
936 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
937 merge_memattrs (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
));
942 merge_memattrs (XEXP (x
, i
), XEXP (y
, i
));
949 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
952 old_insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx i1
, rtx i2
)
956 /* Verify that I1 and I2 are equivalent. */
957 if (GET_CODE (i1
) != GET_CODE (i2
))
960 /* __builtin_unreachable() may lead to empty blocks (ending with
961 NOTE_INSN_BASIC_BLOCK). They may be crossjumped. */
962 if (NOTE_INSN_BASIC_BLOCK_P (i1
) && NOTE_INSN_BASIC_BLOCK_P (i2
))
968 if (GET_CODE (p1
) != GET_CODE (p2
))
971 /* If this is a CALL_INSN, compare register usage information.
972 If we don't check this on stack register machines, the two
973 CALL_INSNs might be merged leaving reg-stack.c with mismatching
974 numbers of stack registers in the same basic block.
975 If we don't check this on machines with delay slots, a delay slot may
976 be filled that clobbers a parameter expected by the subroutine.
978 ??? We take the simple route for now and assume that if they're
979 equal, they were constructed identically.
981 Also check for identical exception regions. */
985 /* Ensure the same EH region. */
986 rtx n1
= find_reg_note (i1
, REG_EH_REGION
, 0);
987 rtx n2
= find_reg_note (i2
, REG_EH_REGION
, 0);
992 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
995 if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
996 CALL_INSN_FUNCTION_USAGE (i2
))
997 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
))
1002 /* If cross_jump_death_matters is not 0, the insn's mode
1003 indicates whether or not the insn contains any stack-like
1006 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
1008 /* If register stack conversion has already been done, then
1009 death notes must also be compared before it is certain that
1010 the two instruction streams match. */
1013 HARD_REG_SET i1_regset
, i2_regset
;
1015 CLEAR_HARD_REG_SET (i1_regset
);
1016 CLEAR_HARD_REG_SET (i2_regset
);
1018 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
1019 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1020 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
1022 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
1023 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
1024 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
1026 if (!hard_reg_set_equal_p (i1_regset
, i2_regset
))
1031 if (reload_completed
1032 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
1038 /* When comparing insns I1 and I2 in flow_find_cross_jump or
1039 flow_find_head_matching_sequence, ensure the notes match. */
1042 merge_notes (rtx i1
, rtx i2
)
1044 /* If the merged insns have different REG_EQUAL notes, then
1046 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1047 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1049 if (equiv1
&& !equiv2
)
1050 remove_note (i1
, equiv1
);
1051 else if (!equiv1
&& equiv2
)
1052 remove_note (i2
, equiv2
);
1053 else if (equiv1
&& equiv2
1054 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1056 remove_note (i1
, equiv1
);
1057 remove_note (i2
, equiv2
);
1061 /* Look through the insns at the end of BB1 and BB2 and find the longest
1062 sequence that are equivalent. Store the first insns for that sequence
1063 in *F1 and *F2 and return the sequence length.
1065 To simplify callers of this function, if the blocks match exactly,
1066 store the head of the blocks in *F1 and *F2. */
1069 flow_find_cross_jump (basic_block bb1
, basic_block bb2
, rtx
*f1
, rtx
*f2
)
1071 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
1074 /* Skip simple jumps at the end of the blocks. Complex jumps still
1075 need to be compared for equivalence, which we'll do below. */
1078 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
1080 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1083 i1
= PREV_INSN (i1
);
1088 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1091 /* Count everything except for unconditional jump as insn. */
1092 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1094 i2
= PREV_INSN (i2
);
1100 while (!NONDEBUG_INSN_P (i1
) && i1
!= BB_HEAD (bb1
))
1101 i1
= PREV_INSN (i1
);
1103 while (!NONDEBUG_INSN_P (i2
) && i2
!= BB_HEAD (bb2
))
1104 i2
= PREV_INSN (i2
);
1106 if (i1
== BB_HEAD (bb1
) || i2
== BB_HEAD (bb2
))
1109 if (!old_insns_match_p (0, i1
, i2
))
1112 merge_memattrs (i1
, i2
);
1114 /* Don't begin a cross-jump with a NOTE insn. */
1117 merge_notes (i1
, i2
);
1119 afterlast1
= last1
, afterlast2
= last2
;
1120 last1
= i1
, last2
= i2
;
1124 i1
= PREV_INSN (i1
);
1125 i2
= PREV_INSN (i2
);
1129 /* Don't allow the insn after a compare to be shared by
1130 cross-jumping unless the compare is also shared. */
1131 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1132 last1
= afterlast1
, last2
= afterlast2
, ninsns
--;
1135 /* Include preceding notes and labels in the cross-jump. One,
1136 this may bring us to the head of the blocks as requested above.
1137 Two, it keeps line number notes as matched as may be. */
1140 while (last1
!= BB_HEAD (bb1
) && !NONDEBUG_INSN_P (PREV_INSN (last1
)))
1141 last1
= PREV_INSN (last1
);
1143 if (last1
!= BB_HEAD (bb1
) && LABEL_P (PREV_INSN (last1
)))
1144 last1
= PREV_INSN (last1
);
1146 while (last2
!= BB_HEAD (bb2
) && !NONDEBUG_INSN_P (PREV_INSN (last2
)))
1147 last2
= PREV_INSN (last2
);
1149 if (last2
!= BB_HEAD (bb2
) && LABEL_P (PREV_INSN (last2
)))
1150 last2
= PREV_INSN (last2
);
1159 /* Like flow_find_cross_jump, except start looking for a matching sequence from
1160 the head of the two blocks. Do not include jumps at the end.
1161 If STOP_AFTER is nonzero, stop after finding that many matching
1165 flow_find_head_matching_sequence (basic_block bb1
, basic_block bb2
, rtx
*f1
,
1166 rtx
*f2
, int stop_after
)
1168 rtx i1
, i2
, last1
, last2
, beforelast1
, beforelast2
;
1172 int nehedges1
= 0, nehedges2
= 0;
1174 FOR_EACH_EDGE (e
, ei
, bb1
->succs
)
1175 if (e
->flags
& EDGE_EH
)
1177 FOR_EACH_EDGE (e
, ei
, bb2
->succs
)
1178 if (e
->flags
& EDGE_EH
)
1183 last1
= beforelast1
= last2
= beforelast2
= NULL_RTX
;
1188 while (!NONDEBUG_INSN_P (i1
) && i1
!= BB_END (bb1
))
1189 i1
= NEXT_INSN (i1
);
1191 while (!NONDEBUG_INSN_P (i2
) && i2
!= BB_END (bb2
))
1192 i2
= NEXT_INSN (i2
);
1194 if ((i1
== BB_END (bb1
) && !NONDEBUG_INSN_P (i1
))
1195 || (i2
== BB_END (bb2
) && !NONDEBUG_INSN_P (i2
)))
1198 if (NOTE_P (i1
) || NOTE_P (i2
)
1199 || JUMP_P (i1
) || JUMP_P (i2
))
1202 /* A sanity check to make sure we're not merging insns with different
1203 effects on EH. If only one of them ends a basic block, it shouldn't
1204 have an EH edge; if both end a basic block, there should be the same
1205 number of EH edges. */
1206 if ((i1
== BB_END (bb1
) && i2
!= BB_END (bb2
)
1208 || (i2
== BB_END (bb2
) && i1
!= BB_END (bb1
)
1210 || (i1
== BB_END (bb1
) && i2
== BB_END (bb2
)
1211 && nehedges1
!= nehedges2
))
1214 if (!old_insns_match_p (0, i1
, i2
))
1217 merge_memattrs (i1
, i2
);
1219 /* Don't begin a cross-jump with a NOTE insn. */
1222 merge_notes (i1
, i2
);
1224 beforelast1
= last1
, beforelast2
= last2
;
1225 last1
= i1
, last2
= i2
;
1229 if (i1
== BB_END (bb1
) || i2
== BB_END (bb2
)
1230 || (stop_after
> 0 && ninsns
== stop_after
))
1233 i1
= NEXT_INSN (i1
);
1234 i2
= NEXT_INSN (i2
);
1238 /* Don't allow a compare to be shared by cross-jumping unless the insn
1239 after the compare is also shared. */
1240 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && sets_cc0_p (last1
))
1241 last1
= beforelast1
, last2
= beforelast2
, ninsns
--;
1253 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1254 the branch instruction. This means that if we commonize the control
1255 flow before end of the basic block, the semantic remains unchanged.
1257 We may assume that there exists one edge with a common destination. */
1260 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1262 int nehedges1
= 0, nehedges2
= 0;
1263 edge fallthru1
= 0, fallthru2
= 0;
1267 /* If BB1 has only one successor, we may be looking at either an
1268 unconditional jump, or a fake edge to exit. */
1269 if (single_succ_p (bb1
)
1270 && (single_succ_edge (bb1
)->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1271 && (!JUMP_P (BB_END (bb1
)) || simplejump_p (BB_END (bb1
))))
1272 return (single_succ_p (bb2
)
1273 && (single_succ_edge (bb2
)->flags
1274 & (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1275 && (!JUMP_P (BB_END (bb2
)) || simplejump_p (BB_END (bb2
))));
1277 /* Match conditional jumps - this may get tricky when fallthru and branch
1278 edges are crossed. */
1279 if (EDGE_COUNT (bb1
->succs
) == 2
1280 && any_condjump_p (BB_END (bb1
))
1281 && onlyjump_p (BB_END (bb1
)))
1283 edge b1
, f1
, b2
, f2
;
1284 bool reverse
, match
;
1285 rtx set1
, set2
, cond1
, cond2
;
1286 enum rtx_code code1
, code2
;
1288 if (EDGE_COUNT (bb2
->succs
) != 2
1289 || !any_condjump_p (BB_END (bb2
))
1290 || !onlyjump_p (BB_END (bb2
)))
1293 b1
= BRANCH_EDGE (bb1
);
1294 b2
= BRANCH_EDGE (bb2
);
1295 f1
= FALLTHRU_EDGE (bb1
);
1296 f2
= FALLTHRU_EDGE (bb2
);
1298 /* Get around possible forwarders on fallthru edges. Other cases
1299 should be optimized out already. */
1300 if (FORWARDER_BLOCK_P (f1
->dest
))
1301 f1
= single_succ_edge (f1
->dest
);
1303 if (FORWARDER_BLOCK_P (f2
->dest
))
1304 f2
= single_succ_edge (f2
->dest
);
1306 /* To simplify use of this function, return false if there are
1307 unneeded forwarder blocks. These will get eliminated later
1308 during cleanup_cfg. */
1309 if (FORWARDER_BLOCK_P (f1
->dest
)
1310 || FORWARDER_BLOCK_P (f2
->dest
)
1311 || FORWARDER_BLOCK_P (b1
->dest
)
1312 || FORWARDER_BLOCK_P (b2
->dest
))
1315 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1317 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1322 set1
= pc_set (BB_END (bb1
));
1323 set2
= pc_set (BB_END (bb2
));
1324 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1325 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1328 cond1
= XEXP (SET_SRC (set1
), 0);
1329 cond2
= XEXP (SET_SRC (set2
), 0);
1330 code1
= GET_CODE (cond1
);
1332 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
1334 code2
= GET_CODE (cond2
);
1336 if (code2
== UNKNOWN
)
1339 /* Verify codes and operands match. */
1340 match
= ((code1
== code2
1341 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1342 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1343 || (code1
== swap_condition (code2
)
1344 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1346 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1349 /* If we return true, we will join the blocks. Which means that
1350 we will only have one branch prediction bit to work with. Thus
1351 we require the existing branches to have probabilities that are
1354 && optimize_bb_for_speed_p (bb1
)
1355 && optimize_bb_for_speed_p (bb2
))
1359 if (b1
->dest
== b2
->dest
)
1360 prob2
= b2
->probability
;
1362 /* Do not use f2 probability as f2 may be forwarded. */
1363 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1365 /* Fail if the difference in probabilities is greater than 50%.
1366 This rules out two well-predicted branches with opposite
1368 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1372 "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
1373 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1379 if (dump_file
&& match
)
1380 fprintf (dump_file
, "Conditionals in bb %i and %i match.\n",
1381 bb1
->index
, bb2
->index
);
1386 /* Generic case - we are seeing a computed jump, table jump or trapping
1389 /* Check whether there are tablejumps in the end of BB1 and BB2.
1390 Return true if they are identical. */
1395 if (tablejump_p (BB_END (bb1
), &label1
, &table1
)
1396 && tablejump_p (BB_END (bb2
), &label2
, &table2
)
1397 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1399 /* The labels should never be the same rtx. If they really are same
1400 the jump tables are same too. So disable crossjumping of blocks BB1
1401 and BB2 because when deleting the common insns in the end of BB1
1402 by delete_basic_block () the jump table would be deleted too. */
1403 /* If LABEL2 is referenced in BB1->END do not do anything
1404 because we would loose information when replacing
1405 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1406 if (label1
!= label2
&& !rtx_referenced_p (label2
, BB_END (bb1
)))
1408 /* Set IDENTICAL to true when the tables are identical. */
1409 bool identical
= false;
1412 p1
= PATTERN (table1
);
1413 p2
= PATTERN (table2
);
1414 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1418 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1419 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1420 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1421 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1426 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1427 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1433 replace_label_data rr
;
1436 /* Temporarily replace references to LABEL1 with LABEL2
1437 in BB1->END so that we could compare the instructions. */
1440 rr
.update_label_nuses
= false;
1441 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1443 match
= old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
));
1444 if (dump_file
&& match
)
1446 "Tablejumps in bb %i and %i match.\n",
1447 bb1
->index
, bb2
->index
);
1449 /* Set the original label in BB1->END because when deleting
1450 a block whose end is a tablejump, the tablejump referenced
1451 from the instruction is deleted too. */
1454 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1463 /* First ensure that the instructions match. There may be many outgoing
1464 edges so this test is generally cheaper. */
1465 if (!old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
)))
1468 /* Search the outgoing edges, ensure that the counts do match, find possible
1469 fallthru and exception handling edges since these needs more
1471 if (EDGE_COUNT (bb1
->succs
) != EDGE_COUNT (bb2
->succs
))
1474 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1476 e2
= EDGE_SUCC (bb2
, ei
.index
);
1478 if (e1
->flags
& EDGE_EH
)
1481 if (e2
->flags
& EDGE_EH
)
1484 if (e1
->flags
& EDGE_FALLTHRU
)
1486 if (e2
->flags
& EDGE_FALLTHRU
)
1490 /* If number of edges of various types does not match, fail. */
1491 if (nehedges1
!= nehedges2
1492 || (fallthru1
!= 0) != (fallthru2
!= 0))
1495 /* fallthru edges must be forwarded to the same destination. */
1498 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1499 ? single_succ (fallthru1
->dest
): fallthru1
->dest
);
1500 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1501 ? single_succ (fallthru2
->dest
): fallthru2
->dest
);
1507 /* Ensure the same EH region. */
1509 rtx n1
= find_reg_note (BB_END (bb1
), REG_EH_REGION
, 0);
1510 rtx n2
= find_reg_note (BB_END (bb2
), REG_EH_REGION
, 0);
1515 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1519 /* The same checks as in try_crossjump_to_edge. It is required for RTL
1520 version of sequence abstraction. */
1521 FOR_EACH_EDGE (e1
, ei
, bb2
->succs
)
1525 basic_block d1
= e1
->dest
;
1527 if (FORWARDER_BLOCK_P (d1
))
1528 d1
= EDGE_SUCC (d1
, 0)->dest
;
1530 FOR_EACH_EDGE (e2
, ei
, bb1
->succs
)
1532 basic_block d2
= e2
->dest
;
1533 if (FORWARDER_BLOCK_P (d2
))
1534 d2
= EDGE_SUCC (d2
, 0)->dest
;
1546 /* Returns true if BB basic block has a preserve label. */
1549 block_has_preserve_label (basic_block bb
)
1553 && LABEL_PRESERVE_P (block_label (bb
)));
1556 /* E1 and E2 are edges with the same destination block. Search their
1557 predecessors for common code. If found, redirect control flow from
1558 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1561 try_crossjump_to_edge (int mode
, edge e1
, edge e2
)
1564 basic_block src1
= e1
->src
, src2
= e2
->src
;
1565 basic_block redirect_to
, redirect_from
, to_remove
;
1566 rtx newpos1
, newpos2
;
1570 newpos1
= newpos2
= NULL_RTX
;
1572 /* If we have partitioned hot/cold basic blocks, it is a bad idea
1573 to try this optimization.
1575 Basic block partitioning may result in some jumps that appear to
1576 be optimizable (or blocks that appear to be mergeable), but which really
1577 must be left untouched (they are required to make it safely across
1578 partition boundaries). See the comments at the top of
1579 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1581 if (flag_reorder_blocks_and_partition
&& reload_completed
)
1584 /* Search backward through forwarder blocks. We don't need to worry
1585 about multiple entry or chained forwarders, as they will be optimized
1586 away. We do this to look past the unconditional jump following a
1587 conditional jump that is required due to the current CFG shape. */
1588 if (single_pred_p (src1
)
1589 && FORWARDER_BLOCK_P (src1
))
1590 e1
= single_pred_edge (src1
), src1
= e1
->src
;
1592 if (single_pred_p (src2
)
1593 && FORWARDER_BLOCK_P (src2
))
1594 e2
= single_pred_edge (src2
), src2
= e2
->src
;
1596 /* Nothing to do if we reach ENTRY, or a common source block. */
1597 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1602 /* Seeing more than 1 forwarder blocks would confuse us later... */
1603 if (FORWARDER_BLOCK_P (e1
->dest
)
1604 && FORWARDER_BLOCK_P (single_succ (e1
->dest
)))
1607 if (FORWARDER_BLOCK_P (e2
->dest
)
1608 && FORWARDER_BLOCK_P (single_succ (e2
->dest
)))
1611 /* Likewise with dead code (possibly newly created by the other optimizations
1613 if (EDGE_COUNT (src1
->preds
) == 0 || EDGE_COUNT (src2
->preds
) == 0)
1616 /* Look for the common insn sequence, part the first ... */
1617 if (!outgoing_edges_match (mode
, src1
, src2
))
1620 /* ... and part the second. */
1621 nmatch
= flow_find_cross_jump (src1
, src2
, &newpos1
, &newpos2
);
1623 /* Don't proceed with the crossjump unless we found a sufficient number
1624 of matching instructions or the 'from' block was totally matched
1625 (such that its predecessors will hopefully be redirected and the
1627 if ((nmatch
< PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS
))
1628 && (newpos1
!= BB_HEAD (src1
)))
1631 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */
1632 if (block_has_preserve_label (e1
->dest
)
1633 && (e1
->flags
& EDGE_ABNORMAL
))
1636 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1638 If we have tablejumps in the end of SRC1 and SRC2
1639 they have been already compared for equivalence in outgoing_edges_match ()
1640 so replace the references to TABLE1 by references to TABLE2. */
1645 if (tablejump_p (BB_END (src1
), &label1
, &table1
)
1646 && tablejump_p (BB_END (src2
), &label2
, &table2
)
1647 && label1
!= label2
)
1649 replace_label_data rr
;
1652 /* Replace references to LABEL1 with LABEL2. */
1655 rr
.update_label_nuses
= true;
1656 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1658 /* Do not replace the label in SRC1->END because when deleting
1659 a block whose end is a tablejump, the tablejump referenced
1660 from the instruction is deleted too. */
1661 if (insn
!= BB_END (src1
))
1662 for_each_rtx (&insn
, replace_label
, &rr
);
1667 /* Avoid splitting if possible. We must always split when SRC2 has
1668 EH predecessor edges, or we may end up with basic blocks with both
1669 normal and EH predecessor edges. */
1670 if (newpos2
== BB_HEAD (src2
)
1671 && !(EDGE_PRED (src2
, 0)->flags
& EDGE_EH
))
1675 if (newpos2
== BB_HEAD (src2
))
1677 /* Skip possible basic block header. */
1678 if (LABEL_P (newpos2
))
1679 newpos2
= NEXT_INSN (newpos2
);
1680 while (DEBUG_INSN_P (newpos2
))
1681 newpos2
= NEXT_INSN (newpos2
);
1682 if (NOTE_P (newpos2
))
1683 newpos2
= NEXT_INSN (newpos2
);
1684 while (DEBUG_INSN_P (newpos2
))
1685 newpos2
= NEXT_INSN (newpos2
);
1689 fprintf (dump_file
, "Splitting bb %i before %i insns\n",
1690 src2
->index
, nmatch
);
1691 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
1696 "Cross jumping from bb %i to bb %i; %i common insns\n",
1697 src1
->index
, src2
->index
, nmatch
);
1699 /* We may have some registers visible through the block. */
1700 df_set_bb_dirty (redirect_to
);
1702 /* Recompute the frequencies and counts of outgoing edges. */
1703 FOR_EACH_EDGE (s
, ei
, redirect_to
->succs
)
1707 basic_block d
= s
->dest
;
1709 if (FORWARDER_BLOCK_P (d
))
1710 d
= single_succ (d
);
1712 FOR_EACH_EDGE (s2
, ei
, src1
->succs
)
1714 basic_block d2
= s2
->dest
;
1715 if (FORWARDER_BLOCK_P (d2
))
1716 d2
= single_succ (d2
);
1721 s
->count
+= s2
->count
;
1723 /* Take care to update possible forwarder blocks. We verified
1724 that there is no more than one in the chain, so we can't run
1725 into infinite loop. */
1726 if (FORWARDER_BLOCK_P (s
->dest
))
1728 single_succ_edge (s
->dest
)->count
+= s2
->count
;
1729 s
->dest
->count
+= s2
->count
;
1730 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
1733 if (FORWARDER_BLOCK_P (s2
->dest
))
1735 single_succ_edge (s2
->dest
)->count
-= s2
->count
;
1736 if (single_succ_edge (s2
->dest
)->count
< 0)
1737 single_succ_edge (s2
->dest
)->count
= 0;
1738 s2
->dest
->count
-= s2
->count
;
1739 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
1740 if (s2
->dest
->frequency
< 0)
1741 s2
->dest
->frequency
= 0;
1742 if (s2
->dest
->count
< 0)
1743 s2
->dest
->count
= 0;
1746 if (!redirect_to
->frequency
&& !src1
->frequency
)
1747 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
1750 = ((s
->probability
* redirect_to
->frequency
+
1751 s2
->probability
* src1
->frequency
)
1752 / (redirect_to
->frequency
+ src1
->frequency
));
1755 /* Adjust count and frequency for the block. An earlier jump
1756 threading pass may have left the profile in an inconsistent
1757 state (see update_bb_profile_for_threading) so we must be
1758 prepared for overflows. */
1759 redirect_to
->count
+= src1
->count
;
1760 redirect_to
->frequency
+= src1
->frequency
;
1761 if (redirect_to
->frequency
> BB_FREQ_MAX
)
1762 redirect_to
->frequency
= BB_FREQ_MAX
;
1763 update_br_prob_note (redirect_to
);
1765 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1767 /* Skip possible basic block header. */
1768 if (LABEL_P (newpos1
))
1769 newpos1
= NEXT_INSN (newpos1
);
1771 while (DEBUG_INSN_P (newpos1
))
1772 newpos1
= NEXT_INSN (newpos1
);
1774 if (NOTE_INSN_BASIC_BLOCK_P (newpos1
))
1775 newpos1
= NEXT_INSN (newpos1
);
1777 while (DEBUG_INSN_P (newpos1
))
1778 newpos1
= NEXT_INSN (newpos1
);
1780 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
1781 to_remove
= single_succ (redirect_from
);
1783 redirect_edge_and_branch_force (single_succ_edge (redirect_from
), redirect_to
);
1784 delete_basic_block (to_remove
);
1786 update_forwarder_flag (redirect_from
);
1787 if (redirect_to
!= src2
)
1788 update_forwarder_flag (src2
);
1793 /* Search the predecessors of BB for common insn sequences. When found,
1794 share code between them by redirecting control flow. Return true if
1795 any changes made. */
1798 try_crossjump_bb (int mode
, basic_block bb
)
1800 edge e
, e2
, fallthru
;
1802 unsigned max
, ix
, ix2
;
1803 basic_block ev
, ev2
;
1806 /* Nothing to do if there is not at least two incoming edges. */
1807 if (EDGE_COUNT (bb
->preds
) < 2)
1810 /* Don't crossjump if this block ends in a computed jump,
1811 unless we are optimizing for size. */
1812 if (optimize_bb_for_size_p (bb
)
1813 && bb
!= EXIT_BLOCK_PTR
1814 && computed_jump_p (BB_END (bb
)))
1817 /* If we are partitioning hot/cold basic blocks, we don't want to
1818 mess up unconditional or indirect jumps that cross between hot
1821 Basic block partitioning may result in some jumps that appear to
1822 be optimizable (or blocks that appear to be mergeable), but which really
1823 must be left untouched (they are required to make it safely across
1824 partition boundaries). See the comments at the top of
1825 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1827 if (BB_PARTITION (EDGE_PRED (bb
, 0)->src
) !=
1828 BB_PARTITION (EDGE_PRED (bb
, 1)->src
)
1829 || (EDGE_PRED (bb
, 0)->flags
& EDGE_CROSSING
))
1832 /* It is always cheapest to redirect a block that ends in a branch to
1833 a block that falls through into BB, as that adds no branches to the
1834 program. We'll try that combination first. */
1836 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
1838 if (EDGE_COUNT (bb
->preds
) > max
)
1841 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1843 if (e
->flags
& EDGE_FALLTHRU
)
1851 for (ix
= 0, ev
= bb
; ix
< EDGE_COUNT (ev
->preds
); )
1853 e
= EDGE_PRED (ev
, ix
);
1856 /* As noted above, first try with the fallthru predecessor (or, a
1857 fallthru predecessor if we are in cfglayout mode). */
1860 /* Don't combine the fallthru edge into anything else.
1861 If there is a match, we'll do it the other way around. */
1864 /* If nothing changed since the last attempt, there is nothing
1867 && !((e
->src
->flags
& BB_MODIFIED
)
1868 || (fallthru
->src
->flags
& BB_MODIFIED
)))
1871 if (try_crossjump_to_edge (mode
, e
, fallthru
))
1880 /* Non-obvious work limiting check: Recognize that we're going
1881 to call try_crossjump_bb on every basic block. So if we have
1882 two blocks with lots of outgoing edges (a switch) and they
1883 share lots of common destinations, then we would do the
1884 cross-jump check once for each common destination.
1886 Now, if the blocks actually are cross-jump candidates, then
1887 all of their destinations will be shared. Which means that
1888 we only need check them for cross-jump candidacy once. We
1889 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1890 choosing to do the check from the block for which the edge
1891 in question is the first successor of A. */
1892 if (EDGE_SUCC (e
->src
, 0) != e
)
1895 for (ix2
= 0, ev2
= bb
; ix2
< EDGE_COUNT (ev2
->preds
); )
1897 e2
= EDGE_PRED (ev2
, ix2
);
1903 /* We've already checked the fallthru edge above. */
1907 /* The "first successor" check above only prevents multiple
1908 checks of crossjump(A,B). In order to prevent redundant
1909 checks of crossjump(B,A), require that A be the block
1910 with the lowest index. */
1911 if (e
->src
->index
> e2
->src
->index
)
1914 /* If nothing changed since the last attempt, there is nothing
1917 && !((e
->src
->flags
& BB_MODIFIED
)
1918 || (e2
->src
->flags
& BB_MODIFIED
)))
1921 if (try_crossjump_to_edge (mode
, e
, e2
))
1932 crossjumps_occured
= true;
1937 /* Search the successors of BB for common insn sequences. When found,
1938 share code between them by moving it across the basic block
1939 boundary. Return true if any changes made. */
1942 try_head_merge_bb (basic_block bb
)
1944 basic_block final_dest_bb
= NULL
;
1945 int max_match
= INT_MAX
;
1947 rtx
*headptr
, *currptr
, *nextptr
;
1948 bool changed
, moveall
;
1950 rtx e0_last_head
, cond
, move_before
;
1951 unsigned nedges
= EDGE_COUNT (bb
->succs
);
1952 rtx jump
= BB_END (bb
);
1953 regset live
, live_union
;
1955 /* Nothing to do if there is not at least two outgoing edges. */
1959 /* Don't crossjump if this block ends in a computed jump,
1960 unless we are optimizing for size. */
1961 if (optimize_bb_for_size_p (bb
)
1962 && bb
!= EXIT_BLOCK_PTR
1963 && computed_jump_p (BB_END (bb
)))
1966 cond
= get_condition (jump
, &move_before
, true, false);
1967 if (cond
== NULL_RTX
)
1970 for (ix
= 0; ix
< nedges
; ix
++)
1971 if (EDGE_SUCC (bb
, ix
)->dest
== EXIT_BLOCK_PTR
)
1974 for (ix
= 0; ix
< nedges
; ix
++)
1976 edge e
= EDGE_SUCC (bb
, ix
);
1977 basic_block other_bb
= e
->dest
;
1979 if (df_get_bb_dirty (other_bb
))
1981 block_was_dirty
= true;
1985 if (e
->flags
& EDGE_ABNORMAL
)
1988 /* Normally, all destination blocks must only be reachable from this
1989 block, i.e. they must have one incoming edge.
1991 There is one special case we can handle, that of multiple consecutive
1992 jumps where the first jumps to one of the targets of the second jump.
1993 This happens frequently in switch statements for default labels.
1994 The structure is as follows:
2000 jump with targets A, B, C, D...
2002 has two incoming edges, from FINAL_DEST_BB and BB
2004 In this case, we can try to move the insns through BB and into
2006 if (EDGE_COUNT (other_bb
->preds
) != 1)
2008 edge incoming_edge
, incoming_bb_other_edge
;
2011 if (final_dest_bb
!= NULL
2012 || EDGE_COUNT (other_bb
->preds
) != 2)
2015 /* We must be able to move the insns across the whole block. */
2016 move_before
= BB_HEAD (bb
);
2017 while (!NONDEBUG_INSN_P (move_before
))
2018 move_before
= NEXT_INSN (move_before
);
2020 if (EDGE_COUNT (bb
->preds
) != 1)
2022 incoming_edge
= EDGE_PRED (bb
, 0);
2023 final_dest_bb
= incoming_edge
->src
;
2024 if (EDGE_COUNT (final_dest_bb
->succs
) != 2)
2026 FOR_EACH_EDGE (incoming_bb_other_edge
, ei
, final_dest_bb
->succs
)
2027 if (incoming_bb_other_edge
!= incoming_edge
)
2029 if (incoming_bb_other_edge
->dest
!= other_bb
)
2034 e0
= EDGE_SUCC (bb
, 0);
2035 e0_last_head
= NULL_RTX
;
2038 for (ix
= 1; ix
< nedges
; ix
++)
2040 edge e
= EDGE_SUCC (bb
, ix
);
2041 rtx e0_last
, e_last
;
2044 nmatch
= flow_find_head_matching_sequence (e0
->dest
, e
->dest
,
2045 &e0_last
, &e_last
, 0);
2049 if (nmatch
< max_match
)
2052 e0_last_head
= e0_last
;
2056 /* If we matched an entire block, we probably have to avoid moving the
2059 && e0_last_head
== BB_END (e0
->dest
)
2060 && (find_reg_note (e0_last_head
, REG_EH_REGION
, 0)
2061 || control_flow_insn_p (e0_last_head
)))
2067 e0_last_head
= prev_real_insn (e0_last_head
);
2068 while (DEBUG_INSN_P (e0_last_head
));
2074 /* We must find a union of the live registers at each of the end points. */
2075 live
= BITMAP_ALLOC (NULL
);
2076 live_union
= BITMAP_ALLOC (NULL
);
2078 currptr
= XNEWVEC (rtx
, nedges
);
2079 headptr
= XNEWVEC (rtx
, nedges
);
2080 nextptr
= XNEWVEC (rtx
, nedges
);
2082 for (ix
= 0; ix
< nedges
; ix
++)
2085 basic_block merge_bb
= EDGE_SUCC (bb
, ix
)->dest
;
2086 rtx head
= BB_HEAD (merge_bb
);
2088 while (!NONDEBUG_INSN_P (head
))
2089 head
= NEXT_INSN (head
);
2093 /* Compute the end point and live information */
2094 for (j
= 1; j
< max_match
; j
++)
2096 head
= NEXT_INSN (head
);
2097 while (!NONDEBUG_INSN_P (head
));
2098 simulate_backwards_to_point (merge_bb
, live
, head
);
2099 IOR_REG_SET (live_union
, live
);
2102 /* If we're moving across two blocks, verify the validity of the
2103 first move, then adjust the target and let the loop below deal
2104 with the final move. */
2105 if (final_dest_bb
!= NULL
)
2109 moveall
= can_move_insns_across (currptr
[0], e0_last_head
, move_before
,
2110 jump
, e0
->dest
, live_union
,
2113 e0_last_head
= move_upto
;
2114 if (e0_last_head
== NULL_RTX
)
2117 jump
= BB_END (final_dest_bb
);
2118 cond
= get_condition (jump
, &move_before
, true, false);
2119 if (cond
== NULL_RTX
)
2126 moveall
= can_move_insns_across (currptr
[0], e0_last_head
,
2127 move_before
, jump
, e0
->dest
, live_union
,
2129 if (!moveall
&& move_upto
== NULL_RTX
)
2131 if (jump
== move_before
)
2134 /* Try again, using a different insertion point. */
2138 /* Don't try moving before a cc0 user, as that may invalidate
2140 if (reg_mentioned_p (cc0_rtx
, jump
))
2147 if (final_dest_bb
&& !moveall
)
2148 /* We haven't checked whether a partial move would be OK for the first
2149 move, so we have to fail this case. */
2155 if (currptr
[0] == move_upto
)
2157 for (ix
= 0; ix
< nedges
; ix
++)
2159 rtx curr
= currptr
[ix
];
2161 curr
= NEXT_INSN (curr
);
2162 while (!NONDEBUG_INSN_P (curr
));
2167 /* If we can't currently move all of the identical insns, remember
2168 each insn after the range that we'll merge. */
2170 for (ix
= 0; ix
< nedges
; ix
++)
2172 rtx curr
= currptr
[ix
];
2174 curr
= NEXT_INSN (curr
);
2175 while (!NONDEBUG_INSN_P (curr
));
2179 reorder_insns (headptr
[0], currptr
[0], PREV_INSN (move_before
));
2180 df_set_bb_dirty (EDGE_SUCC (bb
, 0)->dest
);
2181 if (final_dest_bb
!= NULL
)
2182 df_set_bb_dirty (final_dest_bb
);
2183 df_set_bb_dirty (bb
);
2184 for (ix
= 1; ix
< nedges
; ix
++)
2186 df_set_bb_dirty (EDGE_SUCC (bb
, ix
)->dest
);
2187 delete_insn_chain (headptr
[ix
], currptr
[ix
], false);
2191 if (jump
== move_before
)
2194 /* For the unmerged insns, try a different insertion point. */
2198 /* Don't try moving before a cc0 user, as that may invalidate
2200 if (reg_mentioned_p (cc0_rtx
, jump
))
2204 for (ix
= 0; ix
< nedges
; ix
++)
2205 currptr
[ix
] = headptr
[ix
] = nextptr
[ix
];
2215 crossjumps_occured
|= changed
;
2220 /* Return true if BB contains just bb note, or bb note followed
2221 by only DEBUG_INSNs. */
2224 trivially_empty_bb_p (basic_block bb
)
2226 rtx insn
= BB_END (bb
);
2230 if (insn
== BB_HEAD (bb
))
2232 if (!DEBUG_INSN_P (insn
))
2234 insn
= PREV_INSN (insn
);
2238 /* Do simple CFG optimizations - basic block merging, simplifying of jump
2239 instructions etc. Return nonzero if changes were made. */
2242 try_optimize_cfg (int mode
)
2244 bool changed_overall
= false;
2247 basic_block bb
, b
, next
;
2249 if (mode
& (CLEANUP_CROSSJUMP
| CLEANUP_THREADING
))
2252 crossjumps_occured
= false;
2255 update_forwarder_flag (bb
);
2257 if (! targetm
.cannot_modify_jumps_p ())
2260 /* Attempt to merge blocks as made possible by edge removal. If
2261 a block has only one successor, and the successor has only
2262 one predecessor, they may be combined. */
2265 block_was_dirty
= false;
2271 "\n\ntry_optimize_cfg iteration %i\n\n",
2274 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
;)
2278 bool changed_here
= false;
2280 /* Delete trivially dead basic blocks. This is either
2281 blocks with no predecessors, or empty blocks with no
2282 successors. However if the empty block with no
2283 successors is the successor of the ENTRY_BLOCK, it is
2284 kept. This ensures that the ENTRY_BLOCK will have a
2285 successor which is a precondition for many RTL
2286 passes. Empty blocks may result from expanding
2287 __builtin_unreachable (). */
2288 if (EDGE_COUNT (b
->preds
) == 0
2289 || (EDGE_COUNT (b
->succs
) == 0
2290 && trivially_empty_bb_p (b
)
2291 && single_succ_edge (ENTRY_BLOCK_PTR
)->dest
!= b
))
2294 if (EDGE_COUNT (b
->preds
) > 0)
2299 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2301 if (b
->il
.rtl
->footer
2302 && BARRIER_P (b
->il
.rtl
->footer
))
2303 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2304 if ((e
->flags
& EDGE_FALLTHRU
)
2305 && e
->src
->il
.rtl
->footer
== NULL
)
2307 if (b
->il
.rtl
->footer
)
2309 e
->src
->il
.rtl
->footer
= b
->il
.rtl
->footer
;
2310 b
->il
.rtl
->footer
= NULL
;
2315 e
->src
->il
.rtl
->footer
= emit_barrier ();
2322 rtx last
= get_last_bb_insn (b
);
2323 if (last
&& BARRIER_P (last
))
2324 FOR_EACH_EDGE (e
, ei
, b
->preds
)
2325 if ((e
->flags
& EDGE_FALLTHRU
))
2326 emit_barrier_after (BB_END (e
->src
));
2329 delete_basic_block (b
);
2330 if (!(mode
& CLEANUP_CFGLAYOUT
))
2332 /* Avoid trying to remove ENTRY_BLOCK_PTR. */
2333 b
= (c
== ENTRY_BLOCK_PTR
? c
->next_bb
: c
);
2337 /* Remove code labels no longer used. */
2338 if (single_pred_p (b
)
2339 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2340 && !(single_pred_edge (b
)->flags
& EDGE_COMPLEX
)
2341 && LABEL_P (BB_HEAD (b
))
2342 /* If the previous block ends with a branch to this
2343 block, we can't delete the label. Normally this
2344 is a condjump that is yet to be simplified, but
2345 if CASE_DROPS_THRU, this can be a tablejump with
2346 some element going to the same place as the
2347 default (fallthru). */
2348 && (single_pred (b
) == ENTRY_BLOCK_PTR
2349 || !JUMP_P (BB_END (single_pred (b
)))
2350 || ! label_is_jump_target_p (BB_HEAD (b
),
2351 BB_END (single_pred (b
)))))
2353 rtx label
= BB_HEAD (b
);
2355 delete_insn_chain (label
, label
, false);
2356 /* If the case label is undeletable, move it after the
2357 BASIC_BLOCK note. */
2358 if (NOTE_KIND (BB_HEAD (b
)) == NOTE_INSN_DELETED_LABEL
)
2360 rtx bb_note
= NEXT_INSN (BB_HEAD (b
));
2362 reorder_insns_nobb (label
, label
, bb_note
);
2363 BB_HEAD (b
) = bb_note
;
2364 if (BB_END (b
) == bb_note
)
2368 fprintf (dump_file
, "Deleted label in block %i.\n",
2372 /* If we fall through an empty block, we can remove it. */
2373 if (!(mode
& CLEANUP_CFGLAYOUT
)
2374 && single_pred_p (b
)
2375 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
2376 && !LABEL_P (BB_HEAD (b
))
2377 && FORWARDER_BLOCK_P (b
)
2378 /* Note that forwarder_block_p true ensures that
2379 there is a successor for this block. */
2380 && (single_succ_edge (b
)->flags
& EDGE_FALLTHRU
)
2381 && n_basic_blocks
> NUM_FIXED_BLOCKS
+ 1)
2385 "Deleting fallthru block %i.\n",
2388 c
= b
->prev_bb
== ENTRY_BLOCK_PTR
? b
->next_bb
: b
->prev_bb
;
2389 redirect_edge_succ_nodup (single_pred_edge (b
),
2391 delete_basic_block (b
);
2397 if (single_succ_p (b
)
2398 && (s
= single_succ_edge (b
))
2399 && !(s
->flags
& EDGE_COMPLEX
)
2400 && (c
= s
->dest
) != EXIT_BLOCK_PTR
2401 && single_pred_p (c
)
2404 /* When not in cfg_layout mode use code aware of reordering
2405 INSN. This code possibly creates new basic blocks so it
2406 does not fit merge_blocks interface and is kept here in
2407 hope that it will become useless once more of compiler
2408 is transformed to use cfg_layout mode. */
2410 if ((mode
& CLEANUP_CFGLAYOUT
)
2411 && can_merge_blocks_p (b
, c
))
2413 merge_blocks (b
, c
);
2414 update_forwarder_flag (b
);
2415 changed_here
= true;
2417 else if (!(mode
& CLEANUP_CFGLAYOUT
)
2418 /* If the jump insn has side effects,
2419 we can't kill the edge. */
2420 && (!JUMP_P (BB_END (b
))
2421 || (reload_completed
2422 ? simplejump_p (BB_END (b
))
2423 : (onlyjump_p (BB_END (b
))
2424 && !tablejump_p (BB_END (b
),
2426 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
2429 changed_here
= true;
2433 /* Simplify branch over branch. */
2434 if ((mode
& CLEANUP_EXPENSIVE
)
2435 && !(mode
& CLEANUP_CFGLAYOUT
)
2436 && try_simplify_condjump (b
))
2437 changed_here
= true;
2439 /* If B has a single outgoing edge, but uses a
2440 non-trivial jump instruction without side-effects, we
2441 can either delete the jump entirely, or replace it
2442 with a simple unconditional jump. */
2443 if (single_succ_p (b
)
2444 && single_succ (b
) != EXIT_BLOCK_PTR
2445 && onlyjump_p (BB_END (b
))
2446 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
)
2447 && try_redirect_by_replacing_jump (single_succ_edge (b
),
2449 (mode
& CLEANUP_CFGLAYOUT
) != 0))
2451 update_forwarder_flag (b
);
2452 changed_here
= true;
2455 /* Simplify branch to branch. */
2456 if (try_forward_edges (mode
, b
))
2457 changed_here
= true;
2459 /* Look for shared code between blocks. */
2460 if ((mode
& CLEANUP_CROSSJUMP
)
2461 && try_crossjump_bb (mode
, b
))
2462 changed_here
= true;
2464 if ((mode
& CLEANUP_CROSSJUMP
)
2465 /* This can lengthen register lifetimes. Do it only after
2468 && try_head_merge_bb (b
))
2469 changed_here
= true;
2471 /* Don't get confused by the index shift caused by
2479 if ((mode
& CLEANUP_CROSSJUMP
)
2480 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
2483 if (block_was_dirty
)
2485 /* This should only be set by head-merging. */
2486 gcc_assert (mode
& CLEANUP_CROSSJUMP
);
2490 #ifdef ENABLE_CHECKING
2492 verify_flow_info ();
2495 changed_overall
|= changed
;
2502 b
->flags
&= ~(BB_FORWARDER_BLOCK
| BB_NONTHREADABLE_BLOCK
);
2504 return changed_overall
;
2507 /* Delete all unreachable basic blocks. */
2510 delete_unreachable_blocks (void)
2512 bool changed
= false;
2513 basic_block b
, prev_bb
;
2515 find_unreachable_blocks ();
2517 /* When we're in GIMPLE mode and there may be debug insns, we should
2518 delete blocks in reverse dominator order, so as to get a chance
2519 to substitute all released DEFs into debug stmts. If we don't
2520 have dominators information, walking blocks backward gets us a
2521 better chance of retaining most debug information than
2523 if (MAY_HAVE_DEBUG_STMTS
&& current_ir_type () == IR_GIMPLE
2524 && dom_info_available_p (CDI_DOMINATORS
))
2526 for (b
= EXIT_BLOCK_PTR
->prev_bb
; b
!= ENTRY_BLOCK_PTR
; b
= prev_bb
)
2528 prev_bb
= b
->prev_bb
;
2530 if (!(b
->flags
& BB_REACHABLE
))
2532 /* Speed up the removal of blocks that don't dominate
2533 others. Walking backwards, this should be the common
2535 if (!first_dom_son (CDI_DOMINATORS
, b
))
2536 delete_basic_block (b
);
2539 VEC (basic_block
, heap
) *h
2540 = get_all_dominated_blocks (CDI_DOMINATORS
, b
);
2542 while (VEC_length (basic_block
, h
))
2544 b
= VEC_pop (basic_block
, h
);
2546 prev_bb
= b
->prev_bb
;
2548 gcc_assert (!(b
->flags
& BB_REACHABLE
));
2550 delete_basic_block (b
);
2553 VEC_free (basic_block
, heap
, h
);
2562 for (b
= EXIT_BLOCK_PTR
->prev_bb
; b
!= ENTRY_BLOCK_PTR
; b
= prev_bb
)
2564 prev_bb
= b
->prev_bb
;
2566 if (!(b
->flags
& BB_REACHABLE
))
2568 delete_basic_block (b
);
2575 tidy_fallthru_edges ();
2579 /* Delete any jump tables never referenced. We can't delete them at the
2580 time of removing tablejump insn as they are referenced by the preceding
2581 insns computing the destination, so we delay deleting and garbagecollect
2582 them once life information is computed. */
2584 delete_dead_jumptables (void)
2588 /* A dead jump table does not belong to any basic block. Scan insns
2589 between two adjacent basic blocks. */
2594 for (insn
= NEXT_INSN (BB_END (bb
));
2595 insn
&& !NOTE_INSN_BASIC_BLOCK_P (insn
);
2598 next
= NEXT_INSN (insn
);
2600 && LABEL_NUSES (insn
) == LABEL_PRESERVE_P (insn
)
2601 && JUMP_TABLE_DATA_P (next
))
2603 rtx label
= insn
, jump
= next
;
2606 fprintf (dump_file
, "Dead jumptable %i removed\n",
2609 next
= NEXT_INSN (next
);
2611 delete_insn (label
);
2618 /* Tidy the CFG by deleting unreachable code and whatnot. */
2621 cleanup_cfg (int mode
)
2623 bool changed
= false;
2625 /* Set the cfglayout mode flag here. We could update all the callers
2626 but that is just inconvenient, especially given that we eventually
2627 want to have cfglayout mode as the default. */
2628 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2629 mode
|= CLEANUP_CFGLAYOUT
;
2631 timevar_push (TV_CLEANUP_CFG
);
2632 if (delete_unreachable_blocks ())
2635 /* We've possibly created trivially dead code. Cleanup it right
2636 now to introduce more opportunities for try_optimize_cfg. */
2637 if (!(mode
& (CLEANUP_NO_INSN_DEL
))
2638 && !reload_completed
)
2639 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2644 /* To tail-merge blocks ending in the same noreturn function (e.g.
2645 a call to abort) we have to insert fake edges to exit. Do this
2646 here once. The fake edges do not interfere with any other CFG
2648 if (mode
& CLEANUP_CROSSJUMP
)
2649 add_noreturn_fake_exit_edges ();
2651 if (!dbg_cnt (cfg_cleanup
))
2654 while (try_optimize_cfg (mode
))
2656 delete_unreachable_blocks (), changed
= true;
2657 if (!(mode
& CLEANUP_NO_INSN_DEL
))
2659 /* Try to remove some trivially dead insns when doing an expensive
2660 cleanup. But delete_trivially_dead_insns doesn't work after
2661 reload (it only handles pseudos) and run_fast_dce is too costly
2662 to run in every iteration.
2664 For effective cross jumping, we really want to run a fast DCE to
2665 clean up any dead conditions, or they get in the way of performing
2668 Other transformations in cleanup_cfg are not so sensitive to dead
2669 code, so delete_trivially_dead_insns or even doing nothing at all
2671 if ((mode
& CLEANUP_EXPENSIVE
) && !reload_completed
2672 && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
2674 if ((mode
& CLEANUP_CROSSJUMP
) && crossjumps_occured
)
2681 if (mode
& CLEANUP_CROSSJUMP
)
2682 remove_fake_exit_edges ();
2684 /* Don't call delete_dead_jumptables in cfglayout mode, because
2685 that function assumes that jump tables are in the insns stream.
2686 But we also don't _have_ to delete dead jumptables in cfglayout
2687 mode because we shouldn't even be looking at things that are
2688 not in a basic block. Dead jumptables are cleaned up when
2689 going out of cfglayout mode. */
2690 if (!(mode
& CLEANUP_CFGLAYOUT
))
2691 delete_dead_jumptables ();
2693 timevar_pop (TV_CLEANUP_CFG
);
2699 rest_of_handle_jump (void)
2701 if (crtl
->tail_call_emit
)
2702 fixup_tail_calls ();
2706 struct rtl_opt_pass pass_jump
=
2710 "sibling", /* name */
2712 rest_of_handle_jump
, /* execute */
2715 0, /* static_pass_number */
2716 TV_JUMP
, /* tv_id */
2717 0, /* properties_required */
2718 0, /* properties_provided */
2719 0, /* properties_destroyed */
2720 TODO_ggc_collect
, /* todo_flags_start */
2721 TODO_verify_flow
, /* todo_flags_finish */
2727 rest_of_handle_jump2 (void)
2729 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2731 dump_flow_info (dump_file
, dump_flags
);
2732 cleanup_cfg ((optimize
? CLEANUP_EXPENSIVE
: 0)
2733 | (flag_thread_jumps
? CLEANUP_THREADING
: 0));
2738 struct rtl_opt_pass pass_jump2
=
2744 rest_of_handle_jump2
, /* execute */
2747 0, /* static_pass_number */
2748 TV_JUMP
, /* tv_id */
2749 0, /* properties_required */
2750 0, /* properties_provided */
2751 0, /* properties_destroyed */
2752 TODO_ggc_collect
, /* todo_flags_start */
2753 TODO_dump_func
| TODO_verify_rtl_sharing
,/* todo_flags_finish */