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 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
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"
51 #include "cfglayout.h"
53 #include "tree-pass.h"
57 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
59 /* Set to true when we are running first pass of try_optimize_cfg loop. */
60 static bool first_pass
;
61 static bool try_crossjump_to_edge (int, edge
, edge
);
62 static bool try_crossjump_bb (int, basic_block
);
63 static bool outgoing_edges_match (int *, struct equiv_info
*);
65 static void merge_blocks_move_predecessor_nojumps (basic_block
, basic_block
);
66 static void merge_blocks_move_successor_nojumps (basic_block
, basic_block
);
67 static bool try_optimize_cfg (int);
68 static bool try_simplify_condjump (basic_block
);
69 static bool try_forward_edges (int, basic_block
);
70 static edge
thread_jump (int, edge
, basic_block
);
71 static bool mark_effect (rtx
, bitmap
);
72 static void notice_new_block (basic_block
);
73 static void update_forwarder_flag (basic_block
);
74 static int mentions_nonequal_regs (rtx
*, void *);
76 /* Set flags for newly created block. */
79 notice_new_block (basic_block bb
)
84 if (forwarder_block_p (bb
))
85 bb
->flags
|= BB_FORWARDER_BLOCK
;
88 /* Recompute forwarder flag after block has been modified. */
91 update_forwarder_flag (basic_block bb
)
93 if (forwarder_block_p (bb
))
94 bb
->flags
|= BB_FORWARDER_BLOCK
;
96 bb
->flags
&= ~BB_FORWARDER_BLOCK
;
99 /* Simplify a conditional jump around an unconditional jump.
100 Return true if something changed. */
103 try_simplify_condjump (basic_block cbranch_block
)
105 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
106 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
109 /* Verify that there are exactly two successors. */
110 if (EDGE_COUNT (cbranch_block
->succs
) != 2)
113 /* Verify that we've got a normal conditional branch at the end
115 cbranch_insn
= BB_END (cbranch_block
);
116 if (!any_condjump_p (cbranch_insn
))
119 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
120 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
122 /* The next block must not have multiple predecessors, must not
123 be the last block in the function, and must contain just the
124 unconditional jump. */
125 jump_block
= cbranch_fallthru_edge
->dest
;
126 if (!single_pred_p (jump_block
)
127 || jump_block
->next_bb
== EXIT_BLOCK_PTR
128 || !FORWARDER_BLOCK_P (jump_block
))
130 jump_dest_block
= single_succ (jump_block
);
132 /* If we are partitioning hot/cold basic blocks, we don't want to
133 mess up unconditional or indirect jumps that cross between hot
136 Basic block partitioning may result in some jumps that appear to
137 be optimizable (or blocks that appear to be mergeable), but which really
138 must be left untouched (they are required to make it safely across
139 partition boundaries). See the comments at the top of
140 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
142 if (BB_PARTITION (jump_block
) != BB_PARTITION (jump_dest_block
)
143 || (cbranch_jump_edge
->flags
& EDGE_CROSSING
))
146 /* The conditional branch must target the block after the
147 unconditional branch. */
148 cbranch_dest_block
= cbranch_jump_edge
->dest
;
150 if (cbranch_dest_block
== EXIT_BLOCK_PTR
151 || !can_fallthru (jump_block
, cbranch_dest_block
))
154 /* Invert the conditional branch. */
155 if (!invert_jump (cbranch_insn
, block_label (jump_dest_block
), 0))
159 fprintf (dump_file
, "Simplifying condjump %i around jump %i\n",
160 INSN_UID (cbranch_insn
), INSN_UID (BB_END (jump_block
)));
162 /* Success. Update the CFG to match. Note that after this point
163 the edge variable names appear backwards; the redirection is done
164 this way to preserve edge profile data. */
165 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
167 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
169 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
170 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
171 update_br_prob_note (cbranch_block
);
173 /* Delete the block with the unconditional jump, and clean up the mess. */
174 delete_basic_block (jump_block
);
175 tidy_fallthru_edge (cbranch_jump_edge
);
176 update_forwarder_flag (cbranch_block
);
181 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
182 on register. Used by jump threading. */
185 mark_effect (rtx exp
, regset nonequal
)
189 switch (GET_CODE (exp
))
191 /* In case we do clobber the register, mark it as equal, as we know the
192 value is dead so it don't have to match. */
194 if (REG_P (XEXP (exp
, 0)))
196 dest
= XEXP (exp
, 0);
197 regno
= REGNO (dest
);
198 CLEAR_REGNO_REG_SET (nonequal
, regno
);
199 if (regno
< FIRST_PSEUDO_REGISTER
)
201 int n
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
203 CLEAR_REGNO_REG_SET (nonequal
, regno
+ n
);
209 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
211 dest
= SET_DEST (exp
);
216 regno
= REGNO (dest
);
217 SET_REGNO_REG_SET (nonequal
, regno
);
218 if (regno
< FIRST_PSEUDO_REGISTER
)
220 int n
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
222 SET_REGNO_REG_SET (nonequal
, regno
+ n
);
231 /* Return nonzero if X is a register set in regset DATA.
232 Called via for_each_rtx. */
234 mentions_nonequal_regs (rtx
*x
, void *data
)
236 regset nonequal
= (regset
) data
;
242 if (REGNO_REG_SET_P (nonequal
, regno
))
244 if (regno
< FIRST_PSEUDO_REGISTER
)
246 int n
= hard_regno_nregs
[regno
][GET_MODE (*x
)];
248 if (REGNO_REG_SET_P (nonequal
, regno
+ n
))
254 /* Attempt to prove that the basic block B will have no side effects and
255 always continues in the same edge if reached via E. Return the edge
256 if exist, NULL otherwise. */
259 thread_jump (int mode
, edge e
, basic_block b
)
261 rtx set1
, set2
, cond1
, cond2
, insn
;
262 enum rtx_code code1
, code2
, reversed_code2
;
263 bool reverse1
= false;
267 reg_set_iterator rsi
;
269 if (b
->flags
& BB_NONTHREADABLE_BLOCK
)
272 /* At the moment, we do handle only conditional jumps, but later we may
273 want to extend this code to tablejumps and others. */
274 if (EDGE_COUNT (e
->src
->succs
) != 2)
276 if (EDGE_COUNT (b
->succs
) != 2)
278 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
282 /* Second branch must end with onlyjump, as we will eliminate the jump. */
283 if (!any_condjump_p (BB_END (e
->src
)))
286 if (!any_condjump_p (BB_END (b
)) || !onlyjump_p (BB_END (b
)))
288 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
292 set1
= pc_set (BB_END (e
->src
));
293 set2
= pc_set (BB_END (b
));
294 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
295 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
298 cond1
= XEXP (SET_SRC (set1
), 0);
299 cond2
= XEXP (SET_SRC (set2
), 0);
301 code1
= reversed_comparison_code (cond1
, BB_END (e
->src
));
303 code1
= GET_CODE (cond1
);
305 code2
= GET_CODE (cond2
);
306 reversed_code2
= reversed_comparison_code (cond2
, BB_END (b
));
308 if (!comparison_dominates_p (code1
, code2
)
309 && !comparison_dominates_p (code1
, reversed_code2
))
312 /* Ensure that the comparison operators are equivalent.
313 ??? This is far too pessimistic. We should allow swapped operands,
314 different CCmodes, or for example comparisons for interval, that
315 dominate even when operands are not equivalent. */
316 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
317 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
320 /* Short circuit cases where block B contains some side effects, as we can't
322 for (insn
= NEXT_INSN (BB_HEAD (b
)); insn
!= NEXT_INSN (BB_END (b
));
323 insn
= NEXT_INSN (insn
))
324 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
326 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
332 /* First process all values computed in the source basic block. */
333 for (insn
= NEXT_INSN (BB_HEAD (e
->src
));
334 insn
!= NEXT_INSN (BB_END (e
->src
));
335 insn
= NEXT_INSN (insn
))
337 cselib_process_insn (insn
);
339 nonequal
= BITMAP_ALLOC (NULL
);
340 CLEAR_REG_SET (nonequal
);
342 /* Now assume that we've continued by the edge E to B and continue
343 processing as if it were same basic block.
344 Our goal is to prove that whole block is an NOOP. */
346 for (insn
= NEXT_INSN (BB_HEAD (b
));
347 insn
!= NEXT_INSN (BB_END (b
)) && !failed
;
348 insn
= NEXT_INSN (insn
))
352 rtx pat
= PATTERN (insn
);
354 if (GET_CODE (pat
) == PARALLEL
)
356 for (i
= 0; i
< (unsigned)XVECLEN (pat
, 0); i
++)
357 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
360 failed
|= mark_effect (pat
, nonequal
);
363 cselib_process_insn (insn
);
366 /* Later we should clear nonequal of dead registers. So far we don't
367 have life information in cfg_cleanup. */
370 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
374 /* cond2 must not mention any register that is not equal to the
376 if (for_each_rtx (&cond2
, mentions_nonequal_regs
, nonequal
))
379 /* In case liveness information is available, we need to prove equivalence
380 only of the live values. */
381 if (mode
& CLEANUP_UPDATE_LIFE
)
382 AND_REG_SET (nonequal
, b
->il
.rtl
->global_live_at_end
);
384 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, rsi
)
387 BITMAP_FREE (nonequal
);
389 if ((comparison_dominates_p (code1
, code2
) != 0)
390 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
391 return BRANCH_EDGE (b
);
393 return FALLTHRU_EDGE (b
);
396 BITMAP_FREE (nonequal
);
401 /* Attempt to forward edges leaving basic block B.
402 Return true if successful. */
405 try_forward_edges (int mode
, basic_block b
)
407 bool changed
= false;
409 edge e
, *threaded_edges
= NULL
;
411 /* If we are partitioning hot/cold basic blocks, we don't want to
412 mess up unconditional or indirect jumps that cross between hot
415 Basic block partitioning may result in some jumps that appear to
416 be optimizable (or blocks that appear to be mergeable), but which really m
417 ust be left untouched (they are required to make it safely across
418 partition boundaries). See the comments at the top of
419 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
421 if (find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
424 for (ei
= ei_start (b
->succs
); (e
= ei_safe_edge (ei
)); )
426 basic_block target
, first
;
428 bool threaded
= false;
429 int nthreaded_edges
= 0;
430 bool may_thread
= first_pass
| (b
->flags
& BB_DIRTY
);
432 /* Skip complex edges because we don't know how to update them.
434 Still handle fallthru edges, as we can succeed to forward fallthru
435 edge to the same place as the branch edge of conditional branch
436 and turn conditional branch to an unconditional branch. */
437 if (e
->flags
& EDGE_COMPLEX
)
443 target
= first
= e
->dest
;
444 counter
= NUM_FIXED_BLOCKS
;
446 /* If we are partitioning hot/cold basic_blocks, we don't want to mess
447 up jumps that cross between hot/cold sections.
449 Basic block partitioning may result in some jumps that appear
450 to be optimizable (or blocks that appear to be mergeable), but which
451 really must be left untouched (they are required to make it safely
452 across partition boundaries). See the comments at the top of
453 bb-reorder.c:partition_hot_cold_basic_blocks for complete
456 if (first
!= EXIT_BLOCK_PTR
457 && find_reg_note (BB_END (first
), REG_CROSSING_JUMP
, NULL_RTX
))
460 while (counter
< n_basic_blocks
)
462 basic_block new_target
= NULL
;
463 bool new_target_threaded
= false;
464 may_thread
|= target
->flags
& BB_DIRTY
;
466 if (FORWARDER_BLOCK_P (target
)
467 && !(single_succ_edge (target
)->flags
& EDGE_CROSSING
)
468 && single_succ (target
) != EXIT_BLOCK_PTR
)
470 /* Bypass trivial infinite loops. */
471 new_target
= single_succ (target
);
472 if (target
== new_target
)
473 counter
= n_basic_blocks
;
476 /* Allow to thread only over one edge at time to simplify updating
478 else if ((mode
& CLEANUP_THREADING
) && may_thread
)
480 edge t
= thread_jump (mode
, e
, target
);
484 threaded_edges
= xmalloc (sizeof (*threaded_edges
)
490 /* Detect an infinite loop across blocks not
491 including the start block. */
492 for (i
= 0; i
< nthreaded_edges
; ++i
)
493 if (threaded_edges
[i
] == t
)
495 if (i
< nthreaded_edges
)
497 counter
= n_basic_blocks
;
502 /* Detect an infinite loop across the start block. */
506 gcc_assert (nthreaded_edges
< n_basic_blocks
- NUM_FIXED_BLOCKS
);
507 threaded_edges
[nthreaded_edges
++] = t
;
509 new_target
= t
->dest
;
510 new_target_threaded
= true;
517 /* Avoid killing of loop pre-headers, as it is the place loop
518 optimizer wants to hoist code to.
520 For fallthru forwarders, the LOOP_BEG note must appear between
521 the header of block and CODE_LABEL of the loop, for non forwarders
522 it must appear before the JUMP_INSN. */
523 if ((mode
& CLEANUP_PRE_LOOP
) && optimize
&& flag_loop_optimize
)
525 rtx insn
= (EDGE_SUCC (target
, 0)->flags
& EDGE_FALLTHRU
526 ? BB_HEAD (target
) : prev_nonnote_insn (BB_END (target
)));
529 insn
= NEXT_INSN (insn
);
531 for (; insn
&& !LABEL_P (insn
) && !INSN_P (insn
);
532 insn
= NEXT_INSN (insn
))
534 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
537 if (insn
&& NOTE_P (insn
))
540 /* Do not clean up branches to just past the end of a loop
541 at this time; it can mess up the loop optimizer's
542 recognition of some patterns. */
544 insn
= PREV_INSN (BB_HEAD (target
));
545 if (insn
&& NOTE_P (insn
)
546 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
552 threaded
|= new_target_threaded
;
555 if (counter
>= n_basic_blocks
)
558 fprintf (dump_file
, "Infinite loop in BB %i.\n",
561 else if (target
== first
)
562 ; /* We didn't do anything. */
565 /* Save the values now, as the edge may get removed. */
566 gcov_type edge_count
= e
->count
;
567 int edge_probability
= e
->probability
;
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
)
658 /* If we are partitioning hot/cold basic blocks, we don't want to
659 mess up unconditional or indirect jumps that cross between hot
662 Basic block partitioning may result in some jumps that appear to
663 be optimizable (or blocks that appear to be mergeable), but which really
664 must be left untouched (they are required to make it safely across
665 partition boundaries). See the comments at the top of
666 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
668 if (BB_PARTITION (a
) != BB_PARTITION (b
))
671 barrier
= next_nonnote_insn (BB_END (a
));
672 gcc_assert (BARRIER_P (barrier
));
673 delete_insn (barrier
);
675 /* Move block and loop notes out of the chain so that we do not
678 ??? A better solution would be to squeeze out all the non-nested notes
679 and adjust the block trees appropriately. Even better would be to have
680 a tighter connection between block trees and rtl so that this is not
682 only_notes
= squeeze_notes (&BB_HEAD (a
), &BB_END (a
));
683 gcc_assert (!only_notes
);
685 /* Scramble the insn chain. */
686 if (BB_END (a
) != PREV_INSN (BB_HEAD (b
)))
687 reorder_insns_nobb (BB_HEAD (a
), BB_END (a
), PREV_INSN (BB_HEAD (b
)));
688 a
->flags
|= BB_DIRTY
;
691 fprintf (dump_file
, "Moved block %d before %d and merged.\n",
694 /* Swap the records for the two blocks around. */
697 link_block (a
, b
->prev_bb
);
699 /* Now blocks A and B are contiguous. Merge them. */
703 /* Blocks A and B are to be merged into a single block. B has no outgoing
704 fallthru edge, so it can be moved after A without adding or modifying
705 any jumps (aside from the jump from A to B). */
708 merge_blocks_move_successor_nojumps (basic_block a
, basic_block b
)
710 rtx barrier
, real_b_end
;
714 /* If we are partitioning hot/cold basic blocks, we don't want to
715 mess up unconditional or indirect jumps that cross between hot
718 Basic block partitioning may result in some jumps that appear to
719 be optimizable (or blocks that appear to be mergeable), but which really
720 must be left untouched (they are required to make it safely across
721 partition boundaries). See the comments at the top of
722 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
724 if (BB_PARTITION (a
) != BB_PARTITION (b
))
727 real_b_end
= BB_END (b
);
729 /* If there is a jump table following block B temporarily add the jump table
730 to block B so that it will also be moved to the correct location. */
731 if (tablejump_p (BB_END (b
), &label
, &table
)
732 && prev_active_insn (label
) == BB_END (b
))
737 /* There had better have been a barrier there. Delete it. */
738 barrier
= NEXT_INSN (BB_END (b
));
739 if (barrier
&& BARRIER_P (barrier
))
740 delete_insn (barrier
);
742 /* Move block and loop notes out of the chain so that we do not
745 ??? A better solution would be to squeeze out all the non-nested notes
746 and adjust the block trees appropriately. Even better would be to have
747 a tighter connection between block trees and rtl so that this is not
749 only_notes
= squeeze_notes (&BB_HEAD (b
), &BB_END (b
));
750 gcc_assert (!only_notes
);
753 /* Scramble the insn chain. */
754 reorder_insns_nobb (BB_HEAD (b
), BB_END (b
), BB_END (a
));
756 /* Restore the real end of b. */
757 BB_END (b
) = real_b_end
;
760 fprintf (dump_file
, "Moved block %d after %d and merged.\n",
763 /* Now blocks A and B are contiguous. Merge them. */
767 /* Attempt to merge basic blocks that are potentially non-adjacent.
768 Return NULL iff the attempt failed, otherwise return basic block
769 where cleanup_cfg should continue. Because the merging commonly
770 moves basic block away or introduces another optimization
771 possibility, return basic block just before B so cleanup_cfg don't
774 It may be good idea to return basic block before C in the case
775 C has been moved after B and originally appeared earlier in the
776 insn sequence, but we have no information available about the
777 relative ordering of these two. Hopefully it is not too common. */
780 merge_blocks_move (edge e
, basic_block b
, basic_block c
, int mode
)
784 /* If we are partitioning hot/cold basic blocks, we don't want to
785 mess up unconditional or indirect jumps that cross between hot
788 Basic block partitioning may result in some jumps that appear to
789 be optimizable (or blocks that appear to be mergeable), but which really
790 must be left untouched (they are required to make it safely across
791 partition boundaries). See the comments at the top of
792 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
794 if (BB_PARTITION (b
) != BB_PARTITION (c
))
799 /* If B has a fallthru edge to C, no need to move anything. */
800 if (e
->flags
& EDGE_FALLTHRU
)
802 int b_index
= b
->index
, c_index
= c
->index
;
804 update_forwarder_flag (b
);
807 fprintf (dump_file
, "Merged %d and %d without moving.\n",
810 return b
->prev_bb
== ENTRY_BLOCK_PTR
? b
: b
->prev_bb
;
813 /* Otherwise we will need to move code around. Do that only if expensive
814 transformations are allowed. */
815 else if (mode
& CLEANUP_EXPENSIVE
)
817 edge tmp_edge
, b_fallthru_edge
;
818 bool c_has_outgoing_fallthru
;
819 bool b_has_incoming_fallthru
;
822 /* Avoid overactive code motion, as the forwarder blocks should be
823 eliminated by edge redirection instead. One exception might have
824 been if B is a forwarder block and C has no fallthru edge, but
825 that should be cleaned up by bb-reorder instead. */
826 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
829 /* We must make sure to not munge nesting of lexical blocks,
830 and loop notes. This is done by squeezing out all the notes
831 and leaving them there to lie. Not ideal, but functional. */
833 FOR_EACH_EDGE (tmp_edge
, ei
, c
->succs
)
834 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
837 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
839 FOR_EACH_EDGE (tmp_edge
, ei
, b
->preds
)
840 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
843 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
844 b_fallthru_edge
= tmp_edge
;
847 next
= next
->prev_bb
;
849 /* Otherwise, we're going to try to move C after B. If C does
850 not have an outgoing fallthru, then it can be moved
851 immediately after B without introducing or modifying jumps. */
852 if (! c_has_outgoing_fallthru
)
854 merge_blocks_move_successor_nojumps (b
, c
);
855 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
858 /* If B does not have an incoming fallthru, then it can be moved
859 immediately before C without introducing or modifying jumps.
860 C cannot be the first block, so we do not have to worry about
861 accessing a non-existent block. */
863 if (b_has_incoming_fallthru
)
867 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
869 bb
= force_nonfallthru (b_fallthru_edge
);
871 notice_new_block (bb
);
874 merge_blocks_move_predecessor_nojumps (b
, c
);
875 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
881 /* Return true iff the condbranches at the end of BB1 and BB2 match. */
883 condjump_equiv_p (struct equiv_info
*info
, bool call_init
)
885 basic_block bb1
= info
->x_block
;
886 basic_block bb2
= info
->y_block
;
887 edge b1
= BRANCH_EDGE (bb1
);
888 edge b2
= BRANCH_EDGE (bb2
);
889 edge f1
= FALLTHRU_EDGE (bb1
);
890 edge f2
= FALLTHRU_EDGE (bb2
);
892 rtx set1
, set2
, cond1
, cond2
;
894 enum rtx_code code1
, code2
;
896 /* Get around possible forwarders on fallthru edges. Other cases
897 should be optimized out already. */
898 if (FORWARDER_BLOCK_P (f1
->dest
))
899 f1
= single_succ_edge (f1
->dest
);
901 if (FORWARDER_BLOCK_P (f2
->dest
))
902 f2
= single_succ_edge (f2
->dest
);
904 /* To simplify use of this function, return false if there are
905 unneeded forwarder blocks. These will get eliminated later
906 during cleanup_cfg. */
907 if (FORWARDER_BLOCK_P (f1
->dest
)
908 || FORWARDER_BLOCK_P (f2
->dest
)
909 || FORWARDER_BLOCK_P (b1
->dest
)
910 || FORWARDER_BLOCK_P (b2
->dest
))
913 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
915 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
920 set1
= pc_set (BB_END (bb1
));
921 set2
= pc_set (BB_END (bb2
));
922 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
923 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
926 src1
= SET_SRC (set1
);
927 src2
= SET_SRC (set2
);
928 cond1
= XEXP (src1
, 0);
929 cond2
= XEXP (src2
, 0);
930 code1
= GET_CODE (cond1
);
932 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
934 code2
= GET_CODE (cond2
);
936 if (code2
== UNKNOWN
)
939 if (call_init
&& !struct_equiv_init (STRUCT_EQUIV_START
| info
->mode
, info
))
941 /* Make the sources of the pc sets unreadable so that when we call
942 insns_match_p it won't process them.
943 The death_notes_match_p from insns_match_p won't see the local registers
944 used for the pc set, but that could only cause missed optimizations when
945 there are actually condjumps that use stack registers. */
946 SET_SRC (set1
) = pc_rtx
;
947 SET_SRC (set2
) = pc_rtx
;
948 /* Verify codes and operands match. */
951 match
= (insns_match_p (BB_END (bb1
), BB_END (bb2
), info
)
952 && rtx_equiv_p (&XEXP (cond1
, 0), XEXP (cond2
, 0), 1, info
)
953 && rtx_equiv_p (&XEXP (cond1
, 1), XEXP (cond2
, 1), 1, info
));
956 else if (code1
== swap_condition (code2
))
958 match
= (insns_match_p (BB_END (bb1
), BB_END (bb2
), info
)
959 && rtx_equiv_p (&XEXP (cond1
, 1), XEXP (cond2
, 0), 1, info
)
960 && rtx_equiv_p (&XEXP (cond1
, 0), XEXP (cond2
, 1), 1, info
));
965 SET_SRC (set1
) = src1
;
966 SET_SRC (set2
) = src2
;
967 match
&= verify_changes (0);
969 /* If we return true, we will join the blocks. Which means that
970 we will only have one branch prediction bit to work with. Thus
971 we require the existing branches to have probabilities that are
975 && maybe_hot_bb_p (bb1
)
976 && maybe_hot_bb_p (bb2
))
980 if (b1
->dest
== b2
->dest
)
981 prob2
= b2
->probability
;
983 /* Do not use f2 probability as f2 may be forwarded. */
984 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
986 /* Fail if the difference in probabilities is greater than 50%.
987 This rules out two well-predicted branches with opposite
989 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
993 "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
994 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1000 if (dump_file
&& match
)
1001 fprintf (dump_file
, "Conditionals in bb %i and %i match.\n",
1002 bb1
->index
, bb2
->index
);
1009 /* Return true iff outgoing edges of INFO->y_block and INFO->x_block match,
1010 together with the branch instruction. This means that if we commonize the
1011 control flow before end of the basic block, the semantic remains unchanged.
1012 If we need to compare jumps, we set STRUCT_EQUIV_MATCH_JUMPS in *MODE,
1013 and pass *MODE to struct_equiv_init or assign it to INFO->mode, as
1016 We may assume that there exists one edge with a common destination. */
1019 outgoing_edges_match (int *mode
, struct equiv_info
*info
)
1021 basic_block bb1
= info
->y_block
;
1022 basic_block bb2
= info
->x_block
;
1023 int nehedges1
= 0, nehedges2
= 0;
1024 edge fallthru1
= 0, fallthru2
= 0;
1028 /* If BB1 has only one successor, we may be looking at either an
1029 unconditional jump, or a fake edge to exit. */
1030 if (single_succ_p (bb1
)
1031 && (single_succ_edge (bb1
)->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1032 && (!JUMP_P (BB_END (bb1
)) || simplejump_p (BB_END (bb1
))))
1033 return (single_succ_p (bb2
)
1034 && (single_succ_edge (bb2
)->flags
1035 & (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1036 && (!JUMP_P (BB_END (bb2
)) || simplejump_p (BB_END (bb2
))));
1038 *mode
|= STRUCT_EQUIV_MATCH_JUMPS
;
1039 /* Match conditional jumps - this may get tricky when fallthru and branch
1040 edges are crossed. */
1041 if (EDGE_COUNT (bb1
->succs
) == 2
1042 && any_condjump_p (BB_END (bb1
))
1043 && onlyjump_p (BB_END (bb1
)))
1045 if (EDGE_COUNT (bb2
->succs
) != 2
1046 || !any_condjump_p (BB_END (bb2
))
1047 || !onlyjump_p (BB_END (bb2
)))
1050 return condjump_equiv_p (info
, true);
1053 /* Generic case - we are seeing a computed jump, table jump or trapping
1056 /* Check whether there are tablejumps in the end of BB1 and BB2.
1057 Return true if they are identical. */
1062 if (tablejump_p (BB_END (bb1
), &label1
, &table1
)
1063 && tablejump_p (BB_END (bb2
), &label2
, &table2
)
1064 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1066 /* The labels should never be the same rtx. If they really are same
1067 the jump tables are same too. So disable crossjumping of blocks BB1
1068 and BB2 because when deleting the common insns in the end of BB1
1069 by delete_basic_block () the jump table would be deleted too. */
1070 /* If LABEL2 is referenced in BB1->END do not do anything
1071 because we would loose information when replacing
1072 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1073 if (label1
!= label2
&& !rtx_referenced_p (label2
, BB_END (bb1
)))
1075 /* Set IDENTICAL to true when the tables are identical. */
1076 bool identical
= false;
1079 p1
= PATTERN (table1
);
1080 p2
= PATTERN (table2
);
1081 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1085 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1086 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1087 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1088 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1093 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1094 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1099 && struct_equiv_init (STRUCT_EQUIV_START
| *mode
, info
))
1103 /* Indicate that LABEL1 is to be replaced with LABEL2
1104 in BB1->END so that we could compare the instructions. */
1105 info
->y_label
= label1
;
1106 info
->x_label
= label2
;
1108 match
= insns_match_p (BB_END (bb1
), BB_END (bb2
), info
);
1109 if (dump_file
&& match
)
1111 "Tablejumps in bb %i and %i match.\n",
1112 bb1
->index
, bb2
->index
);
1121 /* First ensure that the instructions match. There may be many outgoing
1122 edges so this test is generally cheaper. */
1123 if (!struct_equiv_init (STRUCT_EQUIV_START
| *mode
, info
)
1124 || !insns_match_p (BB_END (bb1
), BB_END (bb2
), info
))
1127 /* Search the outgoing edges, ensure that the counts do match, find possible
1128 fallthru and exception handling edges since these needs more
1130 if (EDGE_COUNT (bb1
->succs
) != EDGE_COUNT (bb2
->succs
))
1133 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1135 e2
= EDGE_SUCC (bb2
, ei
.index
);
1137 if (e1
->flags
& EDGE_EH
)
1140 if (e2
->flags
& EDGE_EH
)
1143 if (e1
->flags
& EDGE_FALLTHRU
)
1145 if (e2
->flags
& EDGE_FALLTHRU
)
1149 /* If number of edges of various types does not match, fail. */
1150 if (nehedges1
!= nehedges2
1151 || (fallthru1
!= 0) != (fallthru2
!= 0))
1154 /* fallthru edges must be forwarded to the same destination. */
1157 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1158 ? single_succ (fallthru1
->dest
): fallthru1
->dest
);
1159 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1160 ? single_succ (fallthru2
->dest
): fallthru2
->dest
);
1166 /* Ensure the same EH region. */
1168 rtx n1
= find_reg_note (BB_END (bb1
), REG_EH_REGION
, 0);
1169 rtx n2
= find_reg_note (BB_END (bb2
), REG_EH_REGION
, 0);
1174 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1178 /* We don't need to match the rest of edges as above checks should be enough
1179 to ensure that they are equivalent. */
1183 /* E1 and E2 are edges with the same destination block. Search their
1184 predecessors for common code. If found, redirect control flow from
1185 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1188 try_crossjump_to_edge (int mode
, edge e1
, edge e2
)
1191 basic_block src1
= e1
->src
, src2
= e2
->src
;
1192 basic_block redirect_to
, redirect_from
, to_remove
;
1195 struct equiv_info info
;
1196 rtx x_active
, y_active
;
1198 /* If we have partitioned hot/cold basic blocks, it is a bad idea
1199 to try this optimization.
1201 Basic block partitioning may result in some jumps that appear to
1202 be optimizable (or blocks that appear to be mergeable), but which really
1203 must be left untouched (they are required to make it safely across
1204 partition boundaries). See the comments at the top of
1205 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1207 if (flag_reorder_blocks_and_partition
&& no_new_pseudos
)
1210 /* Search backward through forwarder blocks. We don't need to worry
1211 about multiple entry or chained forwarders, as they will be optimized
1212 away. We do this to look past the unconditional jump following a
1213 conditional jump that is required due to the current CFG shape. */
1214 if (single_pred_p (src1
)
1215 && FORWARDER_BLOCK_P (src1
))
1216 e1
= single_pred_edge (src1
), src1
= e1
->src
;
1218 if (single_pred_p (src2
)
1219 && FORWARDER_BLOCK_P (src2
))
1220 e2
= single_pred_edge (src2
), src2
= e2
->src
;
1222 /* Nothing to do if we reach ENTRY, or a common source block. */
1223 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1228 /* Seeing more than 1 forwarder blocks would confuse us later... */
1229 if (FORWARDER_BLOCK_P (e1
->dest
)
1230 && FORWARDER_BLOCK_P (single_succ (e1
->dest
)))
1233 if (FORWARDER_BLOCK_P (e2
->dest
)
1234 && FORWARDER_BLOCK_P (single_succ (e2
->dest
)))
1237 /* Likewise with dead code (possibly newly created by the other optimizations
1239 if (EDGE_COUNT (src1
->preds
) == 0 || EDGE_COUNT (src2
->preds
) == 0)
1242 /* Look for the common insn sequence, part the first ... */
1243 info
.x_block
= src2
;
1244 info
.y_block
= src1
;
1245 if (!outgoing_edges_match (&mode
, &info
))
1248 /* ... and part the second. */
1249 info
.input_cost
= optimize_size
? COSTS_N_INSNS (1) : -1;
1250 nmatch
= struct_equiv_block_eq (STRUCT_EQUIV_START
| mode
, &info
);
1252 /* Don't proceed with the crossjump unless we found a sufficient number
1253 of matching instructions or the 'from' block was totally matched
1254 (such that its predecessors will hopefully be redirected and the
1258 if ((nmatch
-info
.cur
.input_count
< PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS
))
1259 && (info
.cur
.y_start
!= BB_HEAD (src1
)))
1261 while (info
.need_rerun
)
1263 nmatch
= struct_equiv_block_eq (STRUCT_EQUIV_RERUN
| mode
, &info
);
1266 if ((nmatch
-info
.cur
.input_count
< PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS
))
1267 && (info
.cur
.y_start
!= BB_HEAD (src1
)))
1270 nmatch
= struct_equiv_block_eq (STRUCT_EQUIV_FINAL
| mode
, &info
);
1271 if ((nmatch
-info
.cur
.input_count
< PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS
))
1272 && (info
.cur
.y_start
!= BB_HEAD (src1
)))
1275 /* Skip possible basic block header. */
1276 x_active
= info
.cur
.x_start
;
1277 if (LABEL_P (x_active
))
1278 x_active
= NEXT_INSN (x_active
);
1279 if (NOTE_P (x_active
))
1280 x_active
= NEXT_INSN (x_active
);
1282 y_active
= info
.cur
.y_start
;
1283 if (LABEL_P (y_active
))
1284 y_active
= NEXT_INSN (y_active
);
1285 if (NOTE_P (y_active
))
1286 y_active
= NEXT_INSN (y_active
);
1288 /* In order for this code to become active, either we have to be called
1289 before reload, or struct_equiv_block_eq needs to add register scavenging
1290 code to allocate input_reg after reload. */
1293 emit_insn_before (gen_move_insn (info
.input_reg
, info
.x_input
),
1295 emit_insn_before (gen_move_insn (info
.input_reg
, info
.y_input
),
1299 for (i
= 0; i
< info
.cur
.local_count
; i
++)
1300 if (info
.local_rvalue
[i
])
1301 emit_insn_before (gen_move_insn (info
.x_local
[i
], info
.y_local
[i
]),
1304 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1306 If we have tablejumps in the end of SRC1 and SRC2
1307 they have been already compared for equivalence in outgoing_edges_match ()
1308 so replace the references to TABLE1 by references to TABLE2. */
1313 if (tablejump_p (BB_END (src1
), &label1
, &table1
)
1314 && tablejump_p (BB_END (src2
), &label2
, &table2
)
1315 && label1
!= label2
)
1317 replace_label_data rr
;
1320 /* Replace references to LABEL1 with LABEL2. */
1323 rr
.update_label_nuses
= true;
1324 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1326 /* Do not replace the label in SRC1->END because when deleting
1327 a block whose end is a tablejump, the tablejump referenced
1328 from the instruction is deleted too. */
1329 if (insn
!= BB_END (src1
))
1330 for_each_rtx (&insn
, replace_label
, &rr
);
1335 /* Avoid splitting if possible. We must always split when SRC2 has
1336 EH predecessor edges, or we may end up with basic blocks with both
1337 normal and EH predecessor edges. */
1338 if (info
.cur
.x_start
== BB_HEAD (src2
)
1339 && !(EDGE_PRED (src2
, 0)->flags
& EDGE_EH
))
1343 if (info
.cur
.x_start
== BB_HEAD (src2
))
1345 /* Skip possible basic block header. */
1346 if (LABEL_P (info
.cur
.x_start
))
1347 info
.cur
.x_start
= NEXT_INSN (info
.cur
.x_start
);
1348 if (NOTE_P (info
.cur
.x_start
))
1349 info
.cur
.x_start
= NEXT_INSN (info
.cur
.x_start
);
1353 fprintf (dump_file
, "Splitting bb %i before %i insns\n",
1354 src2
->index
, nmatch
);
1355 redirect_to
= split_block (src2
, PREV_INSN (info
.cur
.x_start
))->dest
;
1356 COPY_REG_SET (info
.y_block
->il
.rtl
->global_live_at_end
,
1357 info
.x_block
->il
.rtl
->global_live_at_end
);
1362 fprintf (dump_file
, "Cross jumping from bb %i to bb %i; %i common insns",
1363 src1
->index
, src2
->index
, nmatch
);
1364 if (info
.cur
.local_count
)
1365 fprintf (dump_file
, ", %i local registers", info
.cur
.local_count
);
1366 fprintf (dump_file
, "\n");
1369 redirect_to
->count
+= src1
->count
;
1370 redirect_to
->frequency
+= src1
->frequency
;
1371 /* We may have some registers visible trought the block. */
1372 redirect_to
->flags
|= BB_DIRTY
;
1374 /* Recompute the frequencies and counts of outgoing edges. */
1375 FOR_EACH_EDGE (s
, ei
, redirect_to
->succs
)
1379 basic_block d
= s
->dest
;
1381 if (FORWARDER_BLOCK_P (d
))
1382 d
= single_succ (d
);
1384 FOR_EACH_EDGE (s2
, ei
, src1
->succs
)
1386 basic_block d2
= s2
->dest
;
1387 if (FORWARDER_BLOCK_P (d2
))
1388 d2
= single_succ (d2
);
1393 s
->count
+= s2
->count
;
1395 /* Take care to update possible forwarder blocks. We verified
1396 that there is no more than one in the chain, so we can't run
1397 into infinite loop. */
1398 if (FORWARDER_BLOCK_P (s
->dest
))
1400 single_succ_edge (s
->dest
)->count
+= s2
->count
;
1401 s
->dest
->count
+= s2
->count
;
1402 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
1405 if (FORWARDER_BLOCK_P (s2
->dest
))
1407 single_succ_edge (s2
->dest
)->count
-= s2
->count
;
1408 if (single_succ_edge (s2
->dest
)->count
< 0)
1409 single_succ_edge (s2
->dest
)->count
= 0;
1410 s2
->dest
->count
-= s2
->count
;
1411 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
1412 if (s2
->dest
->frequency
< 0)
1413 s2
->dest
->frequency
= 0;
1414 if (s2
->dest
->count
< 0)
1415 s2
->dest
->count
= 0;
1418 if (!redirect_to
->frequency
&& !src1
->frequency
)
1419 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
1422 = ((s
->probability
* redirect_to
->frequency
+
1423 s2
->probability
* src1
->frequency
)
1424 / (redirect_to
->frequency
+ src1
->frequency
));
1427 update_br_prob_note (redirect_to
);
1429 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1431 redirect_from
= split_block (src1
, PREV_INSN (y_active
))->src
;
1432 to_remove
= single_succ (redirect_from
);
1434 redirect_edge_and_branch_force (single_succ_edge (redirect_from
), redirect_to
);
1435 delete_basic_block (to_remove
);
1437 update_forwarder_flag (redirect_from
);
1438 if (redirect_to
!= src2
)
1439 update_forwarder_flag (src2
);
1444 /* Search the predecessors of BB for common insn sequences. When found,
1445 share code between them by redirecting control flow. Return true if
1446 any changes made. */
1449 try_crossjump_bb (int mode
, basic_block bb
)
1451 edge e
, e2
, fallthru
;
1453 unsigned max
, ix
, ix2
;
1454 basic_block ev
, ev2
;
1457 /* Nothing to do if there is not at least two incoming edges. */
1458 if (EDGE_COUNT (bb
->preds
) < 2)
1461 /* Don't crossjump if this block ends in a computed jump,
1462 unless we are optimizing for size. */
1464 && bb
!= EXIT_BLOCK_PTR
1465 && computed_jump_p (BB_END (bb
)))
1468 /* If we are partitioning hot/cold basic blocks, we don't want to
1469 mess up unconditional or indirect jumps that cross between hot
1472 Basic block partitioning may result in some jumps that appear to
1473 be optimizable (or blocks that appear to be mergeable), but which really
1474 must be left untouched (they are required to make it safely across
1475 partition boundaries). See the comments at the top of
1476 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1478 if (BB_PARTITION (EDGE_PRED (bb
, 0)->src
) !=
1479 BB_PARTITION (EDGE_PRED (bb
, 1)->src
)
1480 || (EDGE_PRED (bb
, 0)->flags
& EDGE_CROSSING
))
1483 /* It is always cheapest to redirect a block that ends in a branch to
1484 a block that falls through into BB, as that adds no branches to the
1485 program. We'll try that combination first. */
1487 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
1489 if (EDGE_COUNT (bb
->preds
) > max
)
1492 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1494 if (e
->flags
& EDGE_FALLTHRU
)
1499 for (ix
= 0, ev
= bb
; ix
< EDGE_COUNT (ev
->preds
); )
1501 e
= EDGE_PRED (ev
, ix
);
1504 /* As noted above, first try with the fallthru predecessor. */
1507 /* Don't combine the fallthru edge into anything else.
1508 If there is a match, we'll do it the other way around. */
1511 /* If nothing changed since the last attempt, there is nothing
1514 && (!(e
->src
->flags
& BB_DIRTY
)
1515 && !(fallthru
->src
->flags
& BB_DIRTY
)))
1518 if (try_crossjump_to_edge (mode
, e
, fallthru
))
1527 /* Non-obvious work limiting check: Recognize that we're going
1528 to call try_crossjump_bb on every basic block. So if we have
1529 two blocks with lots of outgoing edges (a switch) and they
1530 share lots of common destinations, then we would do the
1531 cross-jump check once for each common destination.
1533 Now, if the blocks actually are cross-jump candidates, then
1534 all of their destinations will be shared. Which means that
1535 we only need check them for cross-jump candidacy once. We
1536 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1537 choosing to do the check from the block for which the edge
1538 in question is the first successor of A. */
1539 if (EDGE_SUCC (e
->src
, 0) != e
)
1542 for (ix2
= 0, ev2
= bb
; ix2
< EDGE_COUNT (ev2
->preds
); )
1544 e2
= EDGE_PRED (ev2
, ix2
);
1550 /* We've already checked the fallthru edge above. */
1554 /* The "first successor" check above only prevents multiple
1555 checks of crossjump(A,B). In order to prevent redundant
1556 checks of crossjump(B,A), require that A be the block
1557 with the lowest index. */
1558 if (e
->src
->index
> e2
->src
->index
)
1561 /* If nothing changed since the last attempt, there is nothing
1564 && (!(e
->src
->flags
& BB_DIRTY
)
1565 && !(e2
->src
->flags
& BB_DIRTY
)))
1568 if (try_crossjump_to_edge (mode
, e
, e2
))
1581 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1582 instructions etc. Return nonzero if changes were made. */
1585 try_optimize_cfg (int mode
)
1587 bool changed_overall
= false;
1590 basic_block bb
, b
, next
;
1592 if (mode
& CLEANUP_CROSSJUMP
)
1593 add_noreturn_fake_exit_edges ();
1595 if (mode
& (CLEANUP_UPDATE_LIFE
| CLEANUP_CROSSJUMP
| CLEANUP_THREADING
))
1599 update_forwarder_flag (bb
);
1601 if (! targetm
.cannot_modify_jumps_p ())
1604 /* Attempt to merge blocks as made possible by edge removal. If
1605 a block has only one successor, and the successor has only
1606 one predecessor, they may be combined. */
1614 "\n\ntry_optimize_cfg iteration %i\n\n",
1617 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
;)
1621 bool changed_here
= false;
1623 /* Delete trivially dead basic blocks. */
1624 while (EDGE_COUNT (b
->preds
) == 0)
1628 fprintf (dump_file
, "Deleting block %i.\n",
1631 delete_basic_block (b
);
1632 if (!(mode
& CLEANUP_CFGLAYOUT
))
1637 /* Remove code labels no longer used. */
1638 if (single_pred_p (b
)
1639 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
1640 && !(single_pred_edge (b
)->flags
& EDGE_COMPLEX
)
1641 && LABEL_P (BB_HEAD (b
))
1642 /* If the previous block ends with a branch to this
1643 block, we can't delete the label. Normally this
1644 is a condjump that is yet to be simplified, but
1645 if CASE_DROPS_THRU, this can be a tablejump with
1646 some element going to the same place as the
1647 default (fallthru). */
1648 && (single_pred (b
) == ENTRY_BLOCK_PTR
1649 || !JUMP_P (BB_END (single_pred (b
)))
1650 || ! label_is_jump_target_p (BB_HEAD (b
),
1651 BB_END (single_pred (b
)))))
1653 rtx label
= BB_HEAD (b
);
1655 delete_insn_chain (label
, label
);
1656 /* In the case label is undeletable, move it after the
1657 BASIC_BLOCK note. */
1658 if (NOTE_LINE_NUMBER (BB_HEAD (b
)) == NOTE_INSN_DELETED_LABEL
)
1660 rtx bb_note
= NEXT_INSN (BB_HEAD (b
));
1662 reorder_insns_nobb (label
, label
, bb_note
);
1663 BB_HEAD (b
) = bb_note
;
1666 fprintf (dump_file
, "Deleted label in block %i.\n",
1670 /* If we fall through an empty block, we can remove it. */
1671 if (!(mode
& CLEANUP_CFGLAYOUT
)
1672 && single_pred_p (b
)
1673 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
1674 && !LABEL_P (BB_HEAD (b
))
1675 && FORWARDER_BLOCK_P (b
)
1676 /* Note that forwarder_block_p true ensures that
1677 there is a successor for this block. */
1678 && (single_succ_edge (b
)->flags
& EDGE_FALLTHRU
)
1679 && n_basic_blocks
> NUM_FIXED_BLOCKS
+ 1)
1683 "Deleting fallthru block %i.\n",
1686 c
= b
->prev_bb
== ENTRY_BLOCK_PTR
? b
->next_bb
: b
->prev_bb
;
1687 redirect_edge_succ_nodup (single_pred_edge (b
),
1689 delete_basic_block (b
);
1694 if (single_succ_p (b
)
1695 && (s
= single_succ_edge (b
))
1696 && !(s
->flags
& EDGE_COMPLEX
)
1697 && (c
= s
->dest
) != EXIT_BLOCK_PTR
1698 && single_pred_p (c
)
1701 /* When not in cfg_layout mode use code aware of reordering
1702 INSN. This code possibly creates new basic blocks so it
1703 does not fit merge_blocks interface and is kept here in
1704 hope that it will become useless once more of compiler
1705 is transformed to use cfg_layout mode. */
1707 if ((mode
& CLEANUP_CFGLAYOUT
)
1708 && can_merge_blocks_p (b
, c
))
1710 merge_blocks (b
, c
);
1711 update_forwarder_flag (b
);
1712 changed_here
= true;
1714 else if (!(mode
& CLEANUP_CFGLAYOUT
)
1715 /* If the jump insn has side effects,
1716 we can't kill the edge. */
1717 && (!JUMP_P (BB_END (b
))
1718 || (reload_completed
1719 ? simplejump_p (BB_END (b
))
1720 : (onlyjump_p (BB_END (b
))
1721 && !tablejump_p (BB_END (b
),
1723 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
1726 changed_here
= true;
1730 /* Simplify branch over branch. */
1731 if ((mode
& CLEANUP_EXPENSIVE
)
1732 && !(mode
& CLEANUP_CFGLAYOUT
)
1733 && try_simplify_condjump (b
))
1734 changed_here
= true;
1736 /* If B has a single outgoing edge, but uses a
1737 non-trivial jump instruction without side-effects, we
1738 can either delete the jump entirely, or replace it
1739 with a simple unconditional jump. */
1740 if (single_succ_p (b
)
1741 && single_succ (b
) != EXIT_BLOCK_PTR
1742 && onlyjump_p (BB_END (b
))
1743 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
)
1744 && try_redirect_by_replacing_jump (single_succ_edge (b
),
1746 (mode
& CLEANUP_CFGLAYOUT
) != 0))
1748 update_forwarder_flag (b
);
1749 changed_here
= true;
1752 /* Simplify branch to branch. */
1753 if (try_forward_edges (mode
, b
))
1754 changed_here
= true;
1756 /* Look for shared code between blocks. */
1757 if ((mode
& CLEANUP_CROSSJUMP
)
1758 && try_crossjump_bb (mode
, b
))
1759 changed_here
= true;
1761 /* Don't get confused by the index shift caused by
1769 if ((mode
& CLEANUP_CROSSJUMP
)
1770 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
1773 #ifdef ENABLE_CHECKING
1775 verify_flow_info ();
1778 changed_overall
|= changed
;
1784 if (mode
& CLEANUP_CROSSJUMP
)
1785 remove_fake_exit_edges ();
1788 b
->flags
&= ~(BB_FORWARDER_BLOCK
| BB_NONTHREADABLE_BLOCK
);
1790 return changed_overall
;
1793 /* Delete all unreachable basic blocks. */
1796 delete_unreachable_blocks (void)
1798 bool changed
= false;
1799 basic_block b
, next_bb
;
1801 find_unreachable_blocks ();
1803 /* Delete all unreachable basic blocks. */
1805 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
; b
= next_bb
)
1807 next_bb
= b
->next_bb
;
1809 if (!(b
->flags
& BB_REACHABLE
))
1811 delete_basic_block (b
);
1817 tidy_fallthru_edges ();
1821 /* Merges sequential blocks if possible. */
1824 merge_seq_blocks (void)
1827 bool changed
= false;
1829 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
!= EXIT_BLOCK_PTR
; )
1831 if (single_succ_p (bb
)
1832 && can_merge_blocks_p (bb
, single_succ (bb
)))
1834 /* Merge the blocks and retry. */
1835 merge_blocks (bb
, single_succ (bb
));
1846 /* Tidy the CFG by deleting unreachable code and whatnot. */
1849 cleanup_cfg (int mode
)
1851 bool changed
= false;
1853 timevar_push (TV_CLEANUP_CFG
);
1854 if (delete_unreachable_blocks ())
1857 /* We've possibly created trivially dead code. Cleanup it right
1858 now to introduce more opportunities for try_optimize_cfg. */
1859 if (!(mode
& (CLEANUP_NO_INSN_DEL
| CLEANUP_UPDATE_LIFE
))
1860 && !reload_completed
)
1861 delete_trivially_dead_insns (get_insns(), max_reg_num ());
1866 while (try_optimize_cfg (mode
))
1868 delete_unreachable_blocks (), changed
= true;
1869 if (mode
& CLEANUP_UPDATE_LIFE
)
1871 /* Cleaning up CFG introduces more opportunities for dead code
1872 removal that in turn may introduce more opportunities for
1873 cleaning up the CFG. */
1874 if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES
,
1876 | PROP_SCAN_DEAD_CODE
1877 | PROP_KILL_DEAD_CODE
1878 | ((mode
& CLEANUP_LOG_LINKS
)
1879 ? PROP_LOG_LINKS
: 0)))
1882 else if (!(mode
& CLEANUP_NO_INSN_DEL
)
1883 && (mode
& CLEANUP_EXPENSIVE
)
1884 && !reload_completed
)
1886 if (!delete_trivially_dead_insns (get_insns(), max_reg_num ()))
1891 delete_dead_jumptables ();
1894 timevar_pop (TV_CLEANUP_CFG
);
1900 rest_of_handle_jump (void)
1902 delete_unreachable_blocks ();
1904 if (cfun
->tail_call_emit
)
1905 fixup_tail_calls ();
1908 struct tree_opt_pass pass_jump
=
1910 "sibling", /* name */
1912 rest_of_handle_jump
, /* execute */
1915 0, /* static_pass_number */
1916 TV_JUMP
, /* tv_id */
1917 0, /* properties_required */
1918 0, /* properties_provided */
1919 0, /* properties_destroyed */
1920 TODO_ggc_collect
, /* todo_flags_start */
1922 TODO_verify_flow
, /* todo_flags_finish */
1928 rest_of_handle_jump2 (void)
1930 /* Turn NOTE_INSN_EXPECTED_VALUE into REG_BR_PROB. Do this
1931 before jump optimization switches branch directions. */
1932 if (flag_guess_branch_prob
)
1933 expected_value_to_br_prob ();
1935 delete_trivially_dead_insns (get_insns (), max_reg_num ());
1936 reg_scan (get_insns (), max_reg_num ());
1938 dump_flow_info (dump_file
);
1939 cleanup_cfg ((optimize
? CLEANUP_EXPENSIVE
: 0) | CLEANUP_PRE_LOOP
1940 | (flag_thread_jumps
? CLEANUP_THREADING
: 0));
1942 create_loop_notes ();
1944 purge_line_number_notes ();
1947 cleanup_cfg (CLEANUP_EXPENSIVE
| CLEANUP_PRE_LOOP
);
1949 /* Jump optimization, and the removal of NULL pointer checks, may
1950 have reduced the number of instructions substantially. CSE, and
1951 future passes, allocate arrays whose dimensions involve the
1952 maximum instruction UID, so if we can reduce the maximum UID
1953 we'll save big on memory. */
1954 renumber_insns (dump_file
);
1958 struct tree_opt_pass pass_jump2
=
1962 rest_of_handle_jump2
, /* execute */
1965 0, /* static_pass_number */
1966 TV_JUMP
, /* tv_id */
1967 0, /* properties_required */
1968 0, /* properties_provided */
1969 0, /* properties_destroyed */
1970 TODO_ggc_collect
, /* todo_flags_start */
1971 TODO_dump_func
, /* todo_flags_finish */