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
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"
51 #include "cfglayout.h"
53 #include "tree-pass.h"
60 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
62 /* Set to true when we are running first pass of try_optimize_cfg loop. */
63 static bool first_pass
;
65 /* Set to true if crossjumps occured in the latest run of try_optimize_cfg. */
66 static bool crossjumps_occured
;
68 static bool try_crossjump_to_edge (int, edge
, edge
);
69 static bool try_crossjump_bb (int, basic_block
);
70 static bool outgoing_edges_match (int, basic_block
, basic_block
);
71 static int flow_find_cross_jump (int, basic_block
, basic_block
, rtx
*, rtx
*);
72 static bool old_insns_match_p (int, rtx
, rtx
);
74 static void merge_blocks_move_predecessor_nojumps (basic_block
, basic_block
);
75 static void merge_blocks_move_successor_nojumps (basic_block
, basic_block
);
76 static bool try_optimize_cfg (int);
77 static bool try_simplify_condjump (basic_block
);
78 static bool try_forward_edges (int, basic_block
);
79 static edge
thread_jump (edge
, basic_block
);
80 static bool mark_effect (rtx
, bitmap
);
81 static void notice_new_block (basic_block
);
82 static void update_forwarder_flag (basic_block
);
83 static int mentions_nonequal_regs (rtx
*, void *);
84 static void merge_memattrs (rtx
, rtx
);
86 /* Set flags for newly created block. */
89 notice_new_block (basic_block bb
)
94 if (forwarder_block_p (bb
))
95 bb
->flags
|= BB_FORWARDER_BLOCK
;
98 /* Recompute forwarder flag after block has been modified. */
101 update_forwarder_flag (basic_block bb
)
103 if (forwarder_block_p (bb
))
104 bb
->flags
|= BB_FORWARDER_BLOCK
;
106 bb
->flags
&= ~BB_FORWARDER_BLOCK
;
109 /* Simplify a conditional jump around an unconditional jump.
110 Return true if something changed. */
113 try_simplify_condjump (basic_block cbranch_block
)
115 basic_block jump_block
, jump_dest_block
, cbranch_dest_block
;
116 edge cbranch_jump_edge
, cbranch_fallthru_edge
;
119 /* Verify that there are exactly two successors. */
120 if (EDGE_COUNT (cbranch_block
->succs
) != 2)
123 /* Verify that we've got a normal conditional branch at the end
125 cbranch_insn
= BB_END (cbranch_block
);
126 if (!any_condjump_p (cbranch_insn
))
129 cbranch_fallthru_edge
= FALLTHRU_EDGE (cbranch_block
);
130 cbranch_jump_edge
= BRANCH_EDGE (cbranch_block
);
132 /* The next block must not have multiple predecessors, must not
133 be the last block in the function, and must contain just the
134 unconditional jump. */
135 jump_block
= cbranch_fallthru_edge
->dest
;
136 if (!single_pred_p (jump_block
)
137 || jump_block
->next_bb
== EXIT_BLOCK_PTR
138 || !FORWARDER_BLOCK_P (jump_block
))
140 jump_dest_block
= single_succ (jump_block
);
142 /* If we are partitioning hot/cold basic blocks, we don't want to
143 mess up unconditional or indirect jumps that cross between hot
146 Basic block partitioning may result in some jumps that appear to
147 be optimizable (or blocks that appear to be mergeable), but which really
148 must be left untouched (they are required to make it safely across
149 partition boundaries). See the comments at the top of
150 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
152 if (BB_PARTITION (jump_block
) != BB_PARTITION (jump_dest_block
)
153 || (cbranch_jump_edge
->flags
& EDGE_CROSSING
))
156 /* The conditional branch must target the block after the
157 unconditional branch. */
158 cbranch_dest_block
= cbranch_jump_edge
->dest
;
160 if (cbranch_dest_block
== EXIT_BLOCK_PTR
161 || !can_fallthru (jump_block
, cbranch_dest_block
))
164 /* Invert the conditional branch. */
165 if (!invert_jump (cbranch_insn
, block_label (jump_dest_block
), 0))
169 fprintf (dump_file
, "Simplifying condjump %i around jump %i\n",
170 INSN_UID (cbranch_insn
), INSN_UID (BB_END (jump_block
)));
172 /* Success. Update the CFG to match. Note that after this point
173 the edge variable names appear backwards; the redirection is done
174 this way to preserve edge profile data. */
175 cbranch_jump_edge
= redirect_edge_succ_nodup (cbranch_jump_edge
,
177 cbranch_fallthru_edge
= redirect_edge_succ_nodup (cbranch_fallthru_edge
,
179 cbranch_jump_edge
->flags
|= EDGE_FALLTHRU
;
180 cbranch_fallthru_edge
->flags
&= ~EDGE_FALLTHRU
;
181 update_br_prob_note (cbranch_block
);
183 /* Delete the block with the unconditional jump, and clean up the mess. */
184 delete_basic_block (jump_block
);
185 tidy_fallthru_edge (cbranch_jump_edge
);
186 update_forwarder_flag (cbranch_block
);
191 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
192 on register. Used by jump threading. */
195 mark_effect (rtx exp
, regset nonequal
)
199 switch (GET_CODE (exp
))
201 /* In case we do clobber the register, mark it as equal, as we know the
202 value is dead so it don't have to match. */
204 if (REG_P (XEXP (exp
, 0)))
206 dest
= XEXP (exp
, 0);
207 regno
= REGNO (dest
);
208 CLEAR_REGNO_REG_SET (nonequal
, regno
);
209 if (regno
< FIRST_PSEUDO_REGISTER
)
211 int n
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
213 CLEAR_REGNO_REG_SET (nonequal
, regno
+ n
);
219 if (rtx_equal_for_cselib_p (SET_DEST (exp
), SET_SRC (exp
)))
221 dest
= SET_DEST (exp
);
226 regno
= REGNO (dest
);
227 SET_REGNO_REG_SET (nonequal
, regno
);
228 if (regno
< FIRST_PSEUDO_REGISTER
)
230 int n
= hard_regno_nregs
[regno
][GET_MODE (dest
)];
232 SET_REGNO_REG_SET (nonequal
, regno
+ n
);
241 /* Return nonzero if X is a register set in regset DATA.
242 Called via for_each_rtx. */
244 mentions_nonequal_regs (rtx
*x
, void *data
)
246 regset nonequal
= (regset
) data
;
252 if (REGNO_REG_SET_P (nonequal
, regno
))
254 if (regno
< FIRST_PSEUDO_REGISTER
)
256 int n
= hard_regno_nregs
[regno
][GET_MODE (*x
)];
258 if (REGNO_REG_SET_P (nonequal
, regno
+ n
))
264 /* Attempt to prove that the basic block B will have no side effects and
265 always continues in the same edge if reached via E. Return the edge
266 if exist, NULL otherwise. */
269 thread_jump (edge e
, basic_block b
)
271 rtx set1
, set2
, cond1
, cond2
, insn
;
272 enum rtx_code code1
, code2
, reversed_code2
;
273 bool reverse1
= false;
277 reg_set_iterator rsi
;
279 if (b
->flags
& BB_NONTHREADABLE_BLOCK
)
282 /* At the moment, we do handle only conditional jumps, but later we may
283 want to extend this code to tablejumps and others. */
284 if (EDGE_COUNT (e
->src
->succs
) != 2)
286 if (EDGE_COUNT (b
->succs
) != 2)
288 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
292 /* Second branch must end with onlyjump, as we will eliminate the jump. */
293 if (!any_condjump_p (BB_END (e
->src
)))
296 if (!any_condjump_p (BB_END (b
)) || !onlyjump_p (BB_END (b
)))
298 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
302 set1
= pc_set (BB_END (e
->src
));
303 set2
= pc_set (BB_END (b
));
304 if (((e
->flags
& EDGE_FALLTHRU
) != 0)
305 != (XEXP (SET_SRC (set1
), 1) == pc_rtx
))
308 cond1
= XEXP (SET_SRC (set1
), 0);
309 cond2
= XEXP (SET_SRC (set2
), 0);
311 code1
= reversed_comparison_code (cond1
, BB_END (e
->src
));
313 code1
= GET_CODE (cond1
);
315 code2
= GET_CODE (cond2
);
316 reversed_code2
= reversed_comparison_code (cond2
, BB_END (b
));
318 if (!comparison_dominates_p (code1
, code2
)
319 && !comparison_dominates_p (code1
, reversed_code2
))
322 /* Ensure that the comparison operators are equivalent.
323 ??? This is far too pessimistic. We should allow swapped operands,
324 different CCmodes, or for example comparisons for interval, that
325 dominate even when operands are not equivalent. */
326 if (!rtx_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
327 || !rtx_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
330 /* Short circuit cases where block B contains some side effects, as we can't
332 for (insn
= NEXT_INSN (BB_HEAD (b
)); insn
!= NEXT_INSN (BB_END (b
));
333 insn
= NEXT_INSN (insn
))
334 if (INSN_P (insn
) && side_effects_p (PATTERN (insn
)))
336 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
342 /* First process all values computed in the source basic block. */
343 for (insn
= NEXT_INSN (BB_HEAD (e
->src
));
344 insn
!= NEXT_INSN (BB_END (e
->src
));
345 insn
= NEXT_INSN (insn
))
347 cselib_process_insn (insn
);
349 nonequal
= BITMAP_ALLOC (NULL
);
350 CLEAR_REG_SET (nonequal
);
352 /* Now assume that we've continued by the edge E to B and continue
353 processing as if it were same basic block.
354 Our goal is to prove that whole block is an NOOP. */
356 for (insn
= NEXT_INSN (BB_HEAD (b
));
357 insn
!= NEXT_INSN (BB_END (b
)) && !failed
;
358 insn
= NEXT_INSN (insn
))
362 rtx pat
= PATTERN (insn
);
364 if (GET_CODE (pat
) == PARALLEL
)
366 for (i
= 0; i
< (unsigned)XVECLEN (pat
, 0); i
++)
367 failed
|= mark_effect (XVECEXP (pat
, 0, i
), nonequal
);
370 failed
|= mark_effect (pat
, nonequal
);
373 cselib_process_insn (insn
);
376 /* Later we should clear nonequal of dead registers. So far we don't
377 have life information in cfg_cleanup. */
380 b
->flags
|= BB_NONTHREADABLE_BLOCK
;
384 /* cond2 must not mention any register that is not equal to the
386 if (for_each_rtx (&cond2
, mentions_nonequal_regs
, nonequal
))
389 EXECUTE_IF_SET_IN_REG_SET (nonequal
, 0, i
, rsi
)
392 BITMAP_FREE (nonequal
);
394 if ((comparison_dominates_p (code1
, code2
) != 0)
395 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
396 return BRANCH_EDGE (b
);
398 return FALLTHRU_EDGE (b
);
401 BITMAP_FREE (nonequal
);
406 /* Attempt to forward edges leaving basic block B.
407 Return true if successful. */
410 try_forward_edges (int mode
, basic_block b
)
412 bool changed
= false;
414 edge e
, *threaded_edges
= NULL
;
416 /* If we are partitioning hot/cold basic blocks, we don't want to
417 mess up unconditional or indirect jumps that cross between hot
420 Basic block partitioning may result in some jumps that appear to
421 be optimizable (or blocks that appear to be mergeable), but which really
422 must be left untouched (they are required to make it safely across
423 partition boundaries). See the comments at the top of
424 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
426 if (find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
))
429 for (ei
= ei_start (b
->succs
); (e
= ei_safe_edge (ei
)); )
431 basic_block target
, first
;
433 bool threaded
= false;
434 int nthreaded_edges
= 0;
435 bool may_thread
= first_pass
| df_get_bb_dirty (b
);
437 /* Skip complex edges because we don't know how to update them.
439 Still handle fallthru edges, as we can succeed to forward fallthru
440 edge to the same place as the branch edge of conditional branch
441 and turn conditional branch to an unconditional branch. */
442 if (e
->flags
& EDGE_COMPLEX
)
448 target
= first
= e
->dest
;
449 counter
= NUM_FIXED_BLOCKS
;
451 /* If we are partitioning hot/cold basic_blocks, we don't want to mess
452 up jumps that cross between hot/cold sections.
454 Basic block partitioning may result in some jumps that appear
455 to be optimizable (or blocks that appear to be mergeable), but which
456 really must be left untouched (they are required to make it safely
457 across partition boundaries). See the comments at the top of
458 bb-reorder.c:partition_hot_cold_basic_blocks for complete
461 if (first
!= EXIT_BLOCK_PTR
462 && find_reg_note (BB_END (first
), REG_CROSSING_JUMP
, NULL_RTX
))
465 while (counter
< n_basic_blocks
)
467 basic_block new_target
= NULL
;
468 bool new_target_threaded
= false;
469 may_thread
|= df_get_bb_dirty (target
);
471 if (FORWARDER_BLOCK_P (target
)
472 && !(single_succ_edge (target
)->flags
& EDGE_CROSSING
)
473 && single_succ (target
) != EXIT_BLOCK_PTR
)
475 /* Bypass trivial infinite loops. */
476 new_target
= single_succ (target
);
477 if (target
== new_target
)
478 counter
= n_basic_blocks
;
481 /* Allow to thread only over one edge at time to simplify updating
483 else if ((mode
& CLEANUP_THREADING
) && may_thread
)
485 edge t
= thread_jump (e
, target
);
489 threaded_edges
= XNEWVEC (edge
, n_basic_blocks
);
494 /* Detect an infinite loop across blocks not
495 including the start block. */
496 for (i
= 0; i
< nthreaded_edges
; ++i
)
497 if (threaded_edges
[i
] == t
)
499 if (i
< nthreaded_edges
)
501 counter
= n_basic_blocks
;
506 /* Detect an infinite loop across the start block. */
510 gcc_assert (nthreaded_edges
< n_basic_blocks
- NUM_FIXED_BLOCKS
);
511 threaded_edges
[nthreaded_edges
++] = t
;
513 new_target
= t
->dest
;
514 new_target_threaded
= true;
523 threaded
|= new_target_threaded
;
526 if (counter
>= n_basic_blocks
)
529 fprintf (dump_file
, "Infinite loop in BB %i.\n",
532 else if (target
== first
)
533 ; /* We didn't do anything. */
536 /* Save the values now, as the edge may get removed. */
537 gcov_type edge_count
= e
->count
;
538 int edge_probability
= e
->probability
;
542 /* Don't force if target is exit block. */
543 if (threaded
&& target
!= EXIT_BLOCK_PTR
)
545 notice_new_block (redirect_edge_and_branch_force (e
, target
));
547 fprintf (dump_file
, "Conditionals threaded.\n");
549 else if (!redirect_edge_and_branch (e
, target
))
553 "Forwarding edge %i->%i to %i failed.\n",
554 b
->index
, e
->dest
->index
, target
->index
);
559 /* We successfully forwarded the edge. Now update profile
560 data: for each edge we traversed in the chain, remove
561 the original edge's execution count. */
562 edge_frequency
= ((edge_probability
* b
->frequency
563 + REG_BR_PROB_BASE
/ 2)
566 if (!FORWARDER_BLOCK_P (b
) && forwarder_block_p (b
))
567 b
->flags
|= BB_FORWARDER_BLOCK
;
573 if (!single_succ_p (first
))
575 gcc_assert (n
< nthreaded_edges
);
576 t
= threaded_edges
[n
++];
577 gcc_assert (t
->src
== first
);
578 update_bb_profile_for_threading (first
, edge_frequency
,
580 update_br_prob_note (first
);
584 first
->count
-= edge_count
;
585 if (first
->count
< 0)
587 first
->frequency
-= edge_frequency
;
588 if (first
->frequency
< 0)
589 first
->frequency
= 0;
590 /* It is possible that as the result of
591 threading we've removed edge as it is
592 threaded to the fallthru edge. Avoid
593 getting out of sync. */
594 if (n
< nthreaded_edges
595 && first
== threaded_edges
[n
]->src
)
597 t
= single_succ_edge (first
);
600 t
->count
-= edge_count
;
605 while (first
!= target
);
614 free (threaded_edges
);
619 /* Blocks A and B are to be merged into a single block. A has no incoming
620 fallthru edge, so it can be moved before B without adding or modifying
621 any jumps (aside from the jump from A to B). */
624 merge_blocks_move_predecessor_nojumps (basic_block a
, basic_block b
)
628 /* If we are partitioning hot/cold basic blocks, we don't want to
629 mess up unconditional or indirect jumps that cross between hot
632 Basic block partitioning may result in some jumps that appear to
633 be optimizable (or blocks that appear to be mergeable), but which really
634 must be left untouched (they are required to make it safely across
635 partition boundaries). See the comments at the top of
636 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
638 if (BB_PARTITION (a
) != BB_PARTITION (b
))
641 barrier
= next_nonnote_insn (BB_END (a
));
642 gcc_assert (BARRIER_P (barrier
));
643 delete_insn (barrier
);
645 /* Scramble the insn chain. */
646 if (BB_END (a
) != PREV_INSN (BB_HEAD (b
)))
647 reorder_insns_nobb (BB_HEAD (a
), BB_END (a
), PREV_INSN (BB_HEAD (b
)));
651 fprintf (dump_file
, "Moved block %d before %d and merged.\n",
654 /* Swap the records for the two blocks around. */
657 link_block (a
, b
->prev_bb
);
659 /* Now blocks A and B are contiguous. Merge them. */
663 /* Blocks A and B are to be merged into a single block. B has no outgoing
664 fallthru edge, so it can be moved after A without adding or modifying
665 any jumps (aside from the jump from A to B). */
668 merge_blocks_move_successor_nojumps (basic_block a
, basic_block b
)
670 rtx barrier
, real_b_end
;
673 /* If we are partitioning hot/cold basic blocks, we don't want to
674 mess up unconditional or indirect jumps that cross between hot
677 Basic block partitioning may result in some jumps that appear to
678 be optimizable (or blocks that appear to be mergeable), but which really
679 must be left untouched (they are required to make it safely across
680 partition boundaries). See the comments at the top of
681 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
683 if (BB_PARTITION (a
) != BB_PARTITION (b
))
686 real_b_end
= BB_END (b
);
688 /* If there is a jump table following block B temporarily add the jump table
689 to block B so that it will also be moved to the correct location. */
690 if (tablejump_p (BB_END (b
), &label
, &table
)
691 && prev_active_insn (label
) == BB_END (b
))
696 /* There had better have been a barrier there. Delete it. */
697 barrier
= NEXT_INSN (BB_END (b
));
698 if (barrier
&& BARRIER_P (barrier
))
699 delete_insn (barrier
);
702 /* Scramble the insn chain. */
703 reorder_insns_nobb (BB_HEAD (b
), BB_END (b
), BB_END (a
));
705 /* Restore the real end of b. */
706 BB_END (b
) = real_b_end
;
709 fprintf (dump_file
, "Moved block %d after %d and merged.\n",
712 /* Now blocks A and B are contiguous. Merge them. */
716 /* Attempt to merge basic blocks that are potentially non-adjacent.
717 Return NULL iff the attempt failed, otherwise return basic block
718 where cleanup_cfg should continue. Because the merging commonly
719 moves basic block away or introduces another optimization
720 possibility, return basic block just before B so cleanup_cfg don't
723 It may be good idea to return basic block before C in the case
724 C has been moved after B and originally appeared earlier in the
725 insn sequence, but we have no information available about the
726 relative ordering of these two. Hopefully it is not too common. */
729 merge_blocks_move (edge e
, basic_block b
, basic_block c
, int mode
)
733 /* If we are partitioning hot/cold basic blocks, we don't want to
734 mess up unconditional or indirect jumps that cross between hot
737 Basic block partitioning may result in some jumps that appear to
738 be optimizable (or blocks that appear to be mergeable), but which really
739 must be left untouched (they are required to make it safely across
740 partition boundaries). See the comments at the top of
741 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
743 if (BB_PARTITION (b
) != BB_PARTITION (c
))
746 /* If B has a fallthru edge to C, no need to move anything. */
747 if (e
->flags
& EDGE_FALLTHRU
)
749 int b_index
= b
->index
, c_index
= c
->index
;
751 update_forwarder_flag (b
);
754 fprintf (dump_file
, "Merged %d and %d without moving.\n",
757 return b
->prev_bb
== ENTRY_BLOCK_PTR
? b
: b
->prev_bb
;
760 /* Otherwise we will need to move code around. Do that only if expensive
761 transformations are allowed. */
762 else if (mode
& CLEANUP_EXPENSIVE
)
764 edge tmp_edge
, b_fallthru_edge
;
765 bool c_has_outgoing_fallthru
;
766 bool b_has_incoming_fallthru
;
769 /* Avoid overactive code motion, as the forwarder blocks should be
770 eliminated by edge redirection instead. One exception might have
771 been if B is a forwarder block and C has no fallthru edge, but
772 that should be cleaned up by bb-reorder instead. */
773 if (FORWARDER_BLOCK_P (b
) || FORWARDER_BLOCK_P (c
))
776 /* We must make sure to not munge nesting of lexical blocks,
777 and loop notes. This is done by squeezing out all the notes
778 and leaving them there to lie. Not ideal, but functional. */
780 FOR_EACH_EDGE (tmp_edge
, ei
, c
->succs
)
781 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
784 c_has_outgoing_fallthru
= (tmp_edge
!= NULL
);
786 FOR_EACH_EDGE (tmp_edge
, ei
, b
->preds
)
787 if (tmp_edge
->flags
& EDGE_FALLTHRU
)
790 b_has_incoming_fallthru
= (tmp_edge
!= NULL
);
791 b_fallthru_edge
= tmp_edge
;
794 next
= next
->prev_bb
;
796 /* Otherwise, we're going to try to move C after B. If C does
797 not have an outgoing fallthru, then it can be moved
798 immediately after B without introducing or modifying jumps. */
799 if (! c_has_outgoing_fallthru
)
801 merge_blocks_move_successor_nojumps (b
, c
);
802 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
805 /* If B does not have an incoming fallthru, then it can be moved
806 immediately before C without introducing or modifying jumps.
807 C cannot be the first block, so we do not have to worry about
808 accessing a non-existent block. */
810 if (b_has_incoming_fallthru
)
814 if (b_fallthru_edge
->src
== ENTRY_BLOCK_PTR
)
816 bb
= force_nonfallthru (b_fallthru_edge
);
818 notice_new_block (bb
);
821 merge_blocks_move_predecessor_nojumps (b
, c
);
822 return next
== ENTRY_BLOCK_PTR
? next
->next_bb
: next
;
829 /* Removes the memory attributes of MEM expression
830 if they are not equal. */
833 merge_memattrs (rtx x
, rtx y
)
842 if (x
== 0 || y
== 0)
847 if (code
!= GET_CODE (y
))
850 if (GET_MODE (x
) != GET_MODE (y
))
853 if (code
== MEM
&& MEM_ATTRS (x
) != MEM_ATTRS (y
))
857 else if (! MEM_ATTRS (y
))
863 if (MEM_ALIAS_SET (x
) != MEM_ALIAS_SET (y
))
865 set_mem_alias_set (x
, 0);
866 set_mem_alias_set (y
, 0);
869 if (! mem_expr_equal_p (MEM_EXPR (x
), MEM_EXPR (y
)))
873 set_mem_offset (x
, 0);
874 set_mem_offset (y
, 0);
876 else if (MEM_OFFSET (x
) != MEM_OFFSET (y
))
878 set_mem_offset (x
, 0);
879 set_mem_offset (y
, 0);
884 else if (!MEM_SIZE (y
))
887 mem_size
= GEN_INT (MAX (INTVAL (MEM_SIZE (x
)),
888 INTVAL (MEM_SIZE (y
))));
889 set_mem_size (x
, mem_size
);
890 set_mem_size (y
, mem_size
);
892 set_mem_align (x
, MIN (MEM_ALIGN (x
), MEM_ALIGN (y
)));
893 set_mem_align (y
, MEM_ALIGN (x
));
897 fmt
= GET_RTX_FORMAT (code
);
898 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
903 /* Two vectors must have the same length. */
904 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
907 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
908 merge_memattrs (XVECEXP (x
, i
, j
), XVECEXP (y
, i
, j
));
913 merge_memattrs (XEXP (x
, i
), XEXP (y
, i
));
920 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
923 old_insns_match_p (int mode ATTRIBUTE_UNUSED
, rtx i1
, rtx i2
)
927 /* Verify that I1 and I2 are equivalent. */
928 if (GET_CODE (i1
) != GET_CODE (i2
))
934 if (GET_CODE (p1
) != GET_CODE (p2
))
937 /* If this is a CALL_INSN, compare register usage information.
938 If we don't check this on stack register machines, the two
939 CALL_INSNs might be merged leaving reg-stack.c with mismatching
940 numbers of stack registers in the same basic block.
941 If we don't check this on machines with delay slots, a delay slot may
942 be filled that clobbers a parameter expected by the subroutine.
944 ??? We take the simple route for now and assume that if they're
945 equal, they were constructed identically. */
948 && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1
),
949 CALL_INSN_FUNCTION_USAGE (i2
))
950 || SIBLING_CALL_P (i1
) != SIBLING_CALL_P (i2
)))
954 /* If cross_jump_death_matters is not 0, the insn's mode
955 indicates whether or not the insn contains any stack-like
958 if ((mode
& CLEANUP_POST_REGSTACK
) && stack_regs_mentioned (i1
))
960 /* If register stack conversion has already been done, then
961 death notes must also be compared before it is certain that
962 the two instruction streams match. */
965 HARD_REG_SET i1_regset
, i2_regset
;
967 CLEAR_HARD_REG_SET (i1_regset
);
968 CLEAR_HARD_REG_SET (i2_regset
);
970 for (note
= REG_NOTES (i1
); note
; note
= XEXP (note
, 1))
971 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
972 SET_HARD_REG_BIT (i1_regset
, REGNO (XEXP (note
, 0)));
974 for (note
= REG_NOTES (i2
); note
; note
= XEXP (note
, 1))
975 if (REG_NOTE_KIND (note
) == REG_DEAD
&& STACK_REG_P (XEXP (note
, 0)))
976 SET_HARD_REG_BIT (i2_regset
, REGNO (XEXP (note
, 0)));
978 if (!hard_reg_set_equal_p (i1_regset
, i2_regset
))
984 ? rtx_renumbered_equal_p (p1
, p2
) : rtx_equal_p (p1
, p2
))
987 /* Do not do EQUIV substitution after reload. First, we're undoing the
988 work of reload_cse. Second, we may be undoing the work of the post-
989 reload splitting pass. */
990 /* ??? Possibly add a new phase switch variable that can be used by
991 targets to disallow the troublesome insns after splitting. */
992 if (!reload_completed
)
994 /* The following code helps take care of G++ cleanups. */
995 rtx equiv1
= find_reg_equal_equiv_note (i1
);
996 rtx equiv2
= find_reg_equal_equiv_note (i2
);
999 /* If the equivalences are not to a constant, they may
1000 reference pseudos that no longer exist, so we can't
1002 && (! reload_completed
1003 || (CONSTANT_P (XEXP (equiv1
, 0))
1004 && rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))))
1006 rtx s1
= single_set (i1
);
1007 rtx s2
= single_set (i2
);
1008 if (s1
!= 0 && s2
!= 0
1009 && rtx_renumbered_equal_p (SET_DEST (s1
), SET_DEST (s2
)))
1011 validate_change (i1
, &SET_SRC (s1
), XEXP (equiv1
, 0), 1);
1012 validate_change (i2
, &SET_SRC (s2
), XEXP (equiv2
, 0), 1);
1013 if (! rtx_renumbered_equal_p (p1
, p2
))
1015 else if (apply_change_group ())
1024 /* Look through the insns at the end of BB1 and BB2 and find the longest
1025 sequence that are equivalent. Store the first insns for that sequence
1026 in *F1 and *F2 and return the sequence length.
1028 To simplify callers of this function, if the blocks match exactly,
1029 store the head of the blocks in *F1 and *F2. */
1032 flow_find_cross_jump (int mode ATTRIBUTE_UNUSED
, basic_block bb1
,
1033 basic_block bb2
, rtx
*f1
, rtx
*f2
)
1035 rtx i1
, i2
, last1
, last2
, afterlast1
, afterlast2
;
1038 /* Skip simple jumps at the end of the blocks. Complex jumps still
1039 need to be compared for equivalence, which we'll do below. */
1042 last1
= afterlast1
= last2
= afterlast2
= NULL_RTX
;
1044 || (returnjump_p (i1
) && !side_effects_p (PATTERN (i1
))))
1047 i1
= PREV_INSN (i1
);
1052 || (returnjump_p (i2
) && !side_effects_p (PATTERN (i2
))))
1055 /* Count everything except for unconditional jump as insn. */
1056 if (!simplejump_p (i2
) && !returnjump_p (i2
) && last1
)
1058 i2
= PREV_INSN (i2
);
1064 while (!INSN_P (i1
) && i1
!= BB_HEAD (bb1
))
1065 i1
= PREV_INSN (i1
);
1067 while (!INSN_P (i2
) && i2
!= BB_HEAD (bb2
))
1068 i2
= PREV_INSN (i2
);
1070 if (i1
== BB_HEAD (bb1
) || i2
== BB_HEAD (bb2
))
1073 if (!old_insns_match_p (mode
, i1
, i2
))
1076 merge_memattrs (i1
, i2
);
1078 /* Don't begin a cross-jump with a NOTE insn. */
1081 /* If the merged insns have different REG_EQUAL notes, then
1083 rtx equiv1
= find_reg_equal_equiv_note (i1
);
1084 rtx equiv2
= find_reg_equal_equiv_note (i2
);
1086 if (equiv1
&& !equiv2
)
1087 remove_note (i1
, equiv1
);
1088 else if (!equiv1
&& equiv2
)
1089 remove_note (i2
, equiv2
);
1090 else if (equiv1
&& equiv2
1091 && !rtx_equal_p (XEXP (equiv1
, 0), XEXP (equiv2
, 0)))
1093 remove_note (i1
, equiv1
);
1094 remove_note (i2
, equiv2
);
1097 afterlast1
= last1
, afterlast2
= last2
;
1098 last1
= i1
, last2
= i2
;
1102 i1
= PREV_INSN (i1
);
1103 i2
= PREV_INSN (i2
);
1107 /* Don't allow the insn after a compare to be shared by
1108 cross-jumping unless the compare is also shared. */
1109 if (ninsns
&& reg_mentioned_p (cc0_rtx
, last1
) && ! sets_cc0_p (last1
))
1110 last1
= afterlast1
, last2
= afterlast2
, ninsns
--;
1113 /* Include preceding notes and labels in the cross-jump. One,
1114 this may bring us to the head of the blocks as requested above.
1115 Two, it keeps line number notes as matched as may be. */
1118 while (last1
!= BB_HEAD (bb1
) && !INSN_P (PREV_INSN (last1
)))
1119 last1
= PREV_INSN (last1
);
1121 if (last1
!= BB_HEAD (bb1
) && LABEL_P (PREV_INSN (last1
)))
1122 last1
= PREV_INSN (last1
);
1124 while (last2
!= BB_HEAD (bb2
) && !INSN_P (PREV_INSN (last2
)))
1125 last2
= PREV_INSN (last2
);
1127 if (last2
!= BB_HEAD (bb2
) && LABEL_P (PREV_INSN (last2
)))
1128 last2
= PREV_INSN (last2
);
1137 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1138 the branch instruction. This means that if we commonize the control
1139 flow before end of the basic block, the semantic remains unchanged.
1141 We may assume that there exists one edge with a common destination. */
1144 outgoing_edges_match (int mode
, basic_block bb1
, basic_block bb2
)
1146 int nehedges1
= 0, nehedges2
= 0;
1147 edge fallthru1
= 0, fallthru2
= 0;
1151 /* If BB1 has only one successor, we may be looking at either an
1152 unconditional jump, or a fake edge to exit. */
1153 if (single_succ_p (bb1
)
1154 && (single_succ_edge (bb1
)->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1155 && (!JUMP_P (BB_END (bb1
)) || simplejump_p (BB_END (bb1
))))
1156 return (single_succ_p (bb2
)
1157 && (single_succ_edge (bb2
)->flags
1158 & (EDGE_COMPLEX
| EDGE_FAKE
)) == 0
1159 && (!JUMP_P (BB_END (bb2
)) || simplejump_p (BB_END (bb2
))));
1161 /* Match conditional jumps - this may get tricky when fallthru and branch
1162 edges are crossed. */
1163 if (EDGE_COUNT (bb1
->succs
) == 2
1164 && any_condjump_p (BB_END (bb1
))
1165 && onlyjump_p (BB_END (bb1
)))
1167 edge b1
, f1
, b2
, f2
;
1168 bool reverse
, match
;
1169 rtx set1
, set2
, cond1
, cond2
;
1170 enum rtx_code code1
, code2
;
1172 if (EDGE_COUNT (bb2
->succs
) != 2
1173 || !any_condjump_p (BB_END (bb2
))
1174 || !onlyjump_p (BB_END (bb2
)))
1177 b1
= BRANCH_EDGE (bb1
);
1178 b2
= BRANCH_EDGE (bb2
);
1179 f1
= FALLTHRU_EDGE (bb1
);
1180 f2
= FALLTHRU_EDGE (bb2
);
1182 /* Get around possible forwarders on fallthru edges. Other cases
1183 should be optimized out already. */
1184 if (FORWARDER_BLOCK_P (f1
->dest
))
1185 f1
= single_succ_edge (f1
->dest
);
1187 if (FORWARDER_BLOCK_P (f2
->dest
))
1188 f2
= single_succ_edge (f2
->dest
);
1190 /* To simplify use of this function, return false if there are
1191 unneeded forwarder blocks. These will get eliminated later
1192 during cleanup_cfg. */
1193 if (FORWARDER_BLOCK_P (f1
->dest
)
1194 || FORWARDER_BLOCK_P (f2
->dest
)
1195 || FORWARDER_BLOCK_P (b1
->dest
)
1196 || FORWARDER_BLOCK_P (b2
->dest
))
1199 if (f1
->dest
== f2
->dest
&& b1
->dest
== b2
->dest
)
1201 else if (f1
->dest
== b2
->dest
&& b1
->dest
== f2
->dest
)
1206 set1
= pc_set (BB_END (bb1
));
1207 set2
= pc_set (BB_END (bb2
));
1208 if ((XEXP (SET_SRC (set1
), 1) == pc_rtx
)
1209 != (XEXP (SET_SRC (set2
), 1) == pc_rtx
))
1212 cond1
= XEXP (SET_SRC (set1
), 0);
1213 cond2
= XEXP (SET_SRC (set2
), 0);
1214 code1
= GET_CODE (cond1
);
1216 code2
= reversed_comparison_code (cond2
, BB_END (bb2
));
1218 code2
= GET_CODE (cond2
);
1220 if (code2
== UNKNOWN
)
1223 /* Verify codes and operands match. */
1224 match
= ((code1
== code2
1225 && rtx_renumbered_equal_p (XEXP (cond1
, 0), XEXP (cond2
, 0))
1226 && rtx_renumbered_equal_p (XEXP (cond1
, 1), XEXP (cond2
, 1)))
1227 || (code1
== swap_condition (code2
)
1228 && rtx_renumbered_equal_p (XEXP (cond1
, 1),
1230 && rtx_renumbered_equal_p (XEXP (cond1
, 0),
1233 /* If we return true, we will join the blocks. Which means that
1234 we will only have one branch prediction bit to work with. Thus
1235 we require the existing branches to have probabilities that are
1238 && optimize_bb_for_speed_p (bb1
)
1239 && optimize_bb_for_speed_p (bb2
))
1243 if (b1
->dest
== b2
->dest
)
1244 prob2
= b2
->probability
;
1246 /* Do not use f2 probability as f2 may be forwarded. */
1247 prob2
= REG_BR_PROB_BASE
- b2
->probability
;
1249 /* Fail if the difference in probabilities is greater than 50%.
1250 This rules out two well-predicted branches with opposite
1252 if (abs (b1
->probability
- prob2
) > REG_BR_PROB_BASE
/ 2)
1256 "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
1257 bb1
->index
, bb2
->index
, b1
->probability
, prob2
);
1263 if (dump_file
&& match
)
1264 fprintf (dump_file
, "Conditionals in bb %i and %i match.\n",
1265 bb1
->index
, bb2
->index
);
1270 /* Generic case - we are seeing a computed jump, table jump or trapping
1273 /* Check whether there are tablejumps in the end of BB1 and BB2.
1274 Return true if they are identical. */
1279 if (tablejump_p (BB_END (bb1
), &label1
, &table1
)
1280 && tablejump_p (BB_END (bb2
), &label2
, &table2
)
1281 && GET_CODE (PATTERN (table1
)) == GET_CODE (PATTERN (table2
)))
1283 /* The labels should never be the same rtx. If they really are same
1284 the jump tables are same too. So disable crossjumping of blocks BB1
1285 and BB2 because when deleting the common insns in the end of BB1
1286 by delete_basic_block () the jump table would be deleted too. */
1287 /* If LABEL2 is referenced in BB1->END do not do anything
1288 because we would loose information when replacing
1289 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1290 if (label1
!= label2
&& !rtx_referenced_p (label2
, BB_END (bb1
)))
1292 /* Set IDENTICAL to true when the tables are identical. */
1293 bool identical
= false;
1296 p1
= PATTERN (table1
);
1297 p2
= PATTERN (table2
);
1298 if (GET_CODE (p1
) == ADDR_VEC
&& rtx_equal_p (p1
, p2
))
1302 else if (GET_CODE (p1
) == ADDR_DIFF_VEC
1303 && (XVECLEN (p1
, 1) == XVECLEN (p2
, 1))
1304 && rtx_equal_p (XEXP (p1
, 2), XEXP (p2
, 2))
1305 && rtx_equal_p (XEXP (p1
, 3), XEXP (p2
, 3)))
1310 for (i
= XVECLEN (p1
, 1) - 1; i
>= 0 && identical
; i
--)
1311 if (!rtx_equal_p (XVECEXP (p1
, 1, i
), XVECEXP (p2
, 1, i
)))
1317 replace_label_data rr
;
1320 /* Temporarily replace references to LABEL1 with LABEL2
1321 in BB1->END so that we could compare the instructions. */
1324 rr
.update_label_nuses
= false;
1325 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1327 match
= old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
));
1328 if (dump_file
&& match
)
1330 "Tablejumps in bb %i and %i match.\n",
1331 bb1
->index
, bb2
->index
);
1333 /* Set the original label in BB1->END because when deleting
1334 a block whose end is a tablejump, the tablejump referenced
1335 from the instruction is deleted too. */
1338 for_each_rtx (&BB_END (bb1
), replace_label
, &rr
);
1347 /* First ensure that the instructions match. There may be many outgoing
1348 edges so this test is generally cheaper. */
1349 if (!old_insns_match_p (mode
, BB_END (bb1
), BB_END (bb2
)))
1352 /* Search the outgoing edges, ensure that the counts do match, find possible
1353 fallthru and exception handling edges since these needs more
1355 if (EDGE_COUNT (bb1
->succs
) != EDGE_COUNT (bb2
->succs
))
1358 FOR_EACH_EDGE (e1
, ei
, bb1
->succs
)
1360 e2
= EDGE_SUCC (bb2
, ei
.index
);
1362 if (e1
->flags
& EDGE_EH
)
1365 if (e2
->flags
& EDGE_EH
)
1368 if (e1
->flags
& EDGE_FALLTHRU
)
1370 if (e2
->flags
& EDGE_FALLTHRU
)
1374 /* If number of edges of various types does not match, fail. */
1375 if (nehedges1
!= nehedges2
1376 || (fallthru1
!= 0) != (fallthru2
!= 0))
1379 /* fallthru edges must be forwarded to the same destination. */
1382 basic_block d1
= (forwarder_block_p (fallthru1
->dest
)
1383 ? single_succ (fallthru1
->dest
): fallthru1
->dest
);
1384 basic_block d2
= (forwarder_block_p (fallthru2
->dest
)
1385 ? single_succ (fallthru2
->dest
): fallthru2
->dest
);
1391 /* Ensure the same EH region. */
1393 rtx n1
= find_reg_note (BB_END (bb1
), REG_EH_REGION
, 0);
1394 rtx n2
= find_reg_note (BB_END (bb2
), REG_EH_REGION
, 0);
1399 if (n1
&& (!n2
|| XEXP (n1
, 0) != XEXP (n2
, 0)))
1403 /* The same checks as in try_crossjump_to_edge. It is required for RTL
1404 version of sequence abstraction. */
1405 FOR_EACH_EDGE (e1
, ei
, bb2
->succs
)
1409 basic_block d1
= e1
->dest
;
1411 if (FORWARDER_BLOCK_P (d1
))
1412 d1
= EDGE_SUCC (d1
, 0)->dest
;
1414 FOR_EACH_EDGE (e2
, ei
, bb1
->succs
)
1416 basic_block d2
= e2
->dest
;
1417 if (FORWARDER_BLOCK_P (d2
))
1418 d2
= EDGE_SUCC (d2
, 0)->dest
;
1430 /* Returns true if BB basic block has a preserve label. */
1433 block_has_preserve_label (basic_block bb
)
1437 && LABEL_PRESERVE_P (block_label (bb
)));
1440 /* E1 and E2 are edges with the same destination block. Search their
1441 predecessors for common code. If found, redirect control flow from
1442 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1445 try_crossjump_to_edge (int mode
, edge e1
, edge e2
)
1448 basic_block src1
= e1
->src
, src2
= e2
->src
;
1449 basic_block redirect_to
, redirect_from
, to_remove
;
1450 rtx newpos1
, newpos2
;
1454 newpos1
= newpos2
= NULL_RTX
;
1456 /* If we have partitioned hot/cold basic blocks, it is a bad idea
1457 to try this optimization.
1459 Basic block partitioning may result in some jumps that appear to
1460 be optimizable (or blocks that appear to be mergeable), but which really
1461 must be left untouched (they are required to make it safely across
1462 partition boundaries). See the comments at the top of
1463 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1465 if (flag_reorder_blocks_and_partition
&& reload_completed
)
1468 /* Search backward through forwarder blocks. We don't need to worry
1469 about multiple entry or chained forwarders, as they will be optimized
1470 away. We do this to look past the unconditional jump following a
1471 conditional jump that is required due to the current CFG shape. */
1472 if (single_pred_p (src1
)
1473 && FORWARDER_BLOCK_P (src1
))
1474 e1
= single_pred_edge (src1
), src1
= e1
->src
;
1476 if (single_pred_p (src2
)
1477 && FORWARDER_BLOCK_P (src2
))
1478 e2
= single_pred_edge (src2
), src2
= e2
->src
;
1480 /* Nothing to do if we reach ENTRY, or a common source block. */
1481 if (src1
== ENTRY_BLOCK_PTR
|| src2
== ENTRY_BLOCK_PTR
)
1486 /* Seeing more than 1 forwarder blocks would confuse us later... */
1487 if (FORWARDER_BLOCK_P (e1
->dest
)
1488 && FORWARDER_BLOCK_P (single_succ (e1
->dest
)))
1491 if (FORWARDER_BLOCK_P (e2
->dest
)
1492 && FORWARDER_BLOCK_P (single_succ (e2
->dest
)))
1495 /* Likewise with dead code (possibly newly created by the other optimizations
1497 if (EDGE_COUNT (src1
->preds
) == 0 || EDGE_COUNT (src2
->preds
) == 0)
1500 /* Look for the common insn sequence, part the first ... */
1501 if (!outgoing_edges_match (mode
, src1
, src2
))
1504 /* ... and part the second. */
1505 nmatch
= flow_find_cross_jump (mode
, src1
, src2
, &newpos1
, &newpos2
);
1507 /* Don't proceed with the crossjump unless we found a sufficient number
1508 of matching instructions or the 'from' block was totally matched
1509 (such that its predecessors will hopefully be redirected and the
1511 if ((nmatch
< PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS
))
1512 && (newpos1
!= BB_HEAD (src1
)))
1515 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */
1516 if (block_has_preserve_label (e1
->dest
)
1517 && (e1
->flags
& EDGE_ABNORMAL
))
1520 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1522 If we have tablejumps in the end of SRC1 and SRC2
1523 they have been already compared for equivalence in outgoing_edges_match ()
1524 so replace the references to TABLE1 by references to TABLE2. */
1529 if (tablejump_p (BB_END (src1
), &label1
, &table1
)
1530 && tablejump_p (BB_END (src2
), &label2
, &table2
)
1531 && label1
!= label2
)
1533 replace_label_data rr
;
1536 /* Replace references to LABEL1 with LABEL2. */
1539 rr
.update_label_nuses
= true;
1540 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1542 /* Do not replace the label in SRC1->END because when deleting
1543 a block whose end is a tablejump, the tablejump referenced
1544 from the instruction is deleted too. */
1545 if (insn
!= BB_END (src1
))
1546 for_each_rtx (&insn
, replace_label
, &rr
);
1551 /* Avoid splitting if possible. We must always split when SRC2 has
1552 EH predecessor edges, or we may end up with basic blocks with both
1553 normal and EH predecessor edges. */
1554 if (newpos2
== BB_HEAD (src2
)
1555 && !(EDGE_PRED (src2
, 0)->flags
& EDGE_EH
))
1559 if (newpos2
== BB_HEAD (src2
))
1561 /* Skip possible basic block header. */
1562 if (LABEL_P (newpos2
))
1563 newpos2
= NEXT_INSN (newpos2
);
1564 if (NOTE_P (newpos2
))
1565 newpos2
= NEXT_INSN (newpos2
);
1569 fprintf (dump_file
, "Splitting bb %i before %i insns\n",
1570 src2
->index
, nmatch
);
1571 redirect_to
= split_block (src2
, PREV_INSN (newpos2
))->dest
;
1576 "Cross jumping from bb %i to bb %i; %i common insns\n",
1577 src1
->index
, src2
->index
, nmatch
);
1579 /* We may have some registers visible through the block. */
1580 df_set_bb_dirty (redirect_to
);
1582 /* Recompute the frequencies and counts of outgoing edges. */
1583 FOR_EACH_EDGE (s
, ei
, redirect_to
->succs
)
1587 basic_block d
= s
->dest
;
1589 if (FORWARDER_BLOCK_P (d
))
1590 d
= single_succ (d
);
1592 FOR_EACH_EDGE (s2
, ei
, src1
->succs
)
1594 basic_block d2
= s2
->dest
;
1595 if (FORWARDER_BLOCK_P (d2
))
1596 d2
= single_succ (d2
);
1601 s
->count
+= s2
->count
;
1603 /* Take care to update possible forwarder blocks. We verified
1604 that there is no more than one in the chain, so we can't run
1605 into infinite loop. */
1606 if (FORWARDER_BLOCK_P (s
->dest
))
1608 single_succ_edge (s
->dest
)->count
+= s2
->count
;
1609 s
->dest
->count
+= s2
->count
;
1610 s
->dest
->frequency
+= EDGE_FREQUENCY (s
);
1613 if (FORWARDER_BLOCK_P (s2
->dest
))
1615 single_succ_edge (s2
->dest
)->count
-= s2
->count
;
1616 if (single_succ_edge (s2
->dest
)->count
< 0)
1617 single_succ_edge (s2
->dest
)->count
= 0;
1618 s2
->dest
->count
-= s2
->count
;
1619 s2
->dest
->frequency
-= EDGE_FREQUENCY (s
);
1620 if (s2
->dest
->frequency
< 0)
1621 s2
->dest
->frequency
= 0;
1622 if (s2
->dest
->count
< 0)
1623 s2
->dest
->count
= 0;
1626 if (!redirect_to
->frequency
&& !src1
->frequency
)
1627 s
->probability
= (s
->probability
+ s2
->probability
) / 2;
1630 = ((s
->probability
* redirect_to
->frequency
+
1631 s2
->probability
* src1
->frequency
)
1632 / (redirect_to
->frequency
+ src1
->frequency
));
1635 /* Adjust count and frequency for the block. An earlier jump
1636 threading pass may have left the profile in an inconsistent
1637 state (see update_bb_profile_for_threading) so we must be
1638 prepared for overflows. */
1639 redirect_to
->count
+= src1
->count
;
1640 redirect_to
->frequency
+= src1
->frequency
;
1641 if (redirect_to
->frequency
> BB_FREQ_MAX
)
1642 redirect_to
->frequency
= BB_FREQ_MAX
;
1643 update_br_prob_note (redirect_to
);
1645 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1647 /* Skip possible basic block header. */
1648 if (LABEL_P (newpos1
))
1649 newpos1
= NEXT_INSN (newpos1
);
1651 if (NOTE_P (newpos1
))
1652 newpos1
= NEXT_INSN (newpos1
);
1654 redirect_from
= split_block (src1
, PREV_INSN (newpos1
))->src
;
1655 to_remove
= single_succ (redirect_from
);
1657 redirect_edge_and_branch_force (single_succ_edge (redirect_from
), redirect_to
);
1658 delete_basic_block (to_remove
);
1660 update_forwarder_flag (redirect_from
);
1661 if (redirect_to
!= src2
)
1662 update_forwarder_flag (src2
);
1667 /* Search the predecessors of BB for common insn sequences. When found,
1668 share code between them by redirecting control flow. Return true if
1669 any changes made. */
1672 try_crossjump_bb (int mode
, basic_block bb
)
1674 edge e
, e2
, fallthru
;
1676 unsigned max
, ix
, ix2
;
1677 basic_block ev
, ev2
;
1680 /* Nothing to do if there is not at least two incoming edges. */
1681 if (EDGE_COUNT (bb
->preds
) < 2)
1684 /* Don't crossjump if this block ends in a computed jump,
1685 unless we are optimizing for size. */
1686 if (optimize_bb_for_size_p (bb
)
1687 && bb
!= EXIT_BLOCK_PTR
1688 && computed_jump_p (BB_END (bb
)))
1691 /* If we are partitioning hot/cold basic blocks, we don't want to
1692 mess up unconditional or indirect jumps that cross between hot
1695 Basic block partitioning may result in some jumps that appear to
1696 be optimizable (or blocks that appear to be mergeable), but which really
1697 must be left untouched (they are required to make it safely across
1698 partition boundaries). See the comments at the top of
1699 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1701 if (BB_PARTITION (EDGE_PRED (bb
, 0)->src
) !=
1702 BB_PARTITION (EDGE_PRED (bb
, 1)->src
)
1703 || (EDGE_PRED (bb
, 0)->flags
& EDGE_CROSSING
))
1706 /* It is always cheapest to redirect a block that ends in a branch to
1707 a block that falls through into BB, as that adds no branches to the
1708 program. We'll try that combination first. */
1710 max
= PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES
);
1712 if (EDGE_COUNT (bb
->preds
) > max
)
1715 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1717 if (e
->flags
& EDGE_FALLTHRU
)
1725 for (ix
= 0, ev
= bb
; ix
< EDGE_COUNT (ev
->preds
); )
1727 e
= EDGE_PRED (ev
, ix
);
1730 /* As noted above, first try with the fallthru predecessor (or, a
1731 fallthru predecessor if we are in cfglayout mode). */
1734 /* Don't combine the fallthru edge into anything else.
1735 If there is a match, we'll do it the other way around. */
1738 /* If nothing changed since the last attempt, there is nothing
1741 && (!(df_get_bb_dirty (e
->src
))
1742 && !(df_get_bb_dirty (fallthru
->src
))))
1745 if (try_crossjump_to_edge (mode
, e
, fallthru
))
1754 /* Non-obvious work limiting check: Recognize that we're going
1755 to call try_crossjump_bb on every basic block. So if we have
1756 two blocks with lots of outgoing edges (a switch) and they
1757 share lots of common destinations, then we would do the
1758 cross-jump check once for each common destination.
1760 Now, if the blocks actually are cross-jump candidates, then
1761 all of their destinations will be shared. Which means that
1762 we only need check them for cross-jump candidacy once. We
1763 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1764 choosing to do the check from the block for which the edge
1765 in question is the first successor of A. */
1766 if (EDGE_SUCC (e
->src
, 0) != e
)
1769 for (ix2
= 0, ev2
= bb
; ix2
< EDGE_COUNT (ev2
->preds
); )
1771 e2
= EDGE_PRED (ev2
, ix2
);
1777 /* We've already checked the fallthru edge above. */
1781 /* The "first successor" check above only prevents multiple
1782 checks of crossjump(A,B). In order to prevent redundant
1783 checks of crossjump(B,A), require that A be the block
1784 with the lowest index. */
1785 if (e
->src
->index
> e2
->src
->index
)
1788 /* If nothing changed since the last attempt, there is nothing
1791 && (!(df_get_bb_dirty (e
->src
))
1792 && !(df_get_bb_dirty (e2
->src
))))
1795 if (try_crossjump_to_edge (mode
, e
, e2
))
1806 crossjumps_occured
= true;
1811 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1812 instructions etc. Return nonzero if changes were made. */
1815 try_optimize_cfg (int mode
)
1817 bool changed_overall
= false;
1820 basic_block bb
, b
, next
;
1822 if (mode
& (CLEANUP_CROSSJUMP
| CLEANUP_THREADING
))
1825 crossjumps_occured
= false;
1828 update_forwarder_flag (bb
);
1830 if (! targetm
.cannot_modify_jumps_p ())
1833 /* Attempt to merge blocks as made possible by edge removal. If
1834 a block has only one successor, and the successor has only
1835 one predecessor, they may be combined. */
1843 "\n\ntry_optimize_cfg iteration %i\n\n",
1846 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
;)
1850 bool changed_here
= false;
1852 /* Delete trivially dead basic blocks. */
1853 if (EDGE_COUNT (b
->preds
) == 0)
1857 fprintf (dump_file
, "Deleting block %i.\n",
1860 delete_basic_block (b
);
1861 if (!(mode
& CLEANUP_CFGLAYOUT
))
1863 /* Avoid trying to remove ENTRY_BLOCK_PTR. */
1864 b
= (c
== ENTRY_BLOCK_PTR
? c
->next_bb
: c
);
1868 /* Remove code labels no longer used. */
1869 if (single_pred_p (b
)
1870 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
1871 && !(single_pred_edge (b
)->flags
& EDGE_COMPLEX
)
1872 && LABEL_P (BB_HEAD (b
))
1873 /* If the previous block ends with a branch to this
1874 block, we can't delete the label. Normally this
1875 is a condjump that is yet to be simplified, but
1876 if CASE_DROPS_THRU, this can be a tablejump with
1877 some element going to the same place as the
1878 default (fallthru). */
1879 && (single_pred (b
) == ENTRY_BLOCK_PTR
1880 || !JUMP_P (BB_END (single_pred (b
)))
1881 || ! label_is_jump_target_p (BB_HEAD (b
),
1882 BB_END (single_pred (b
)))))
1884 rtx label
= BB_HEAD (b
);
1886 delete_insn_chain (label
, label
, false);
1887 /* If the case label is undeletable, move it after the
1888 BASIC_BLOCK note. */
1889 if (NOTE_KIND (BB_HEAD (b
)) == NOTE_INSN_DELETED_LABEL
)
1891 rtx bb_note
= NEXT_INSN (BB_HEAD (b
));
1893 reorder_insns_nobb (label
, label
, bb_note
);
1894 BB_HEAD (b
) = bb_note
;
1895 if (BB_END (b
) == bb_note
)
1899 fprintf (dump_file
, "Deleted label in block %i.\n",
1903 /* If we fall through an empty block, we can remove it. */
1904 if (!(mode
& CLEANUP_CFGLAYOUT
)
1905 && single_pred_p (b
)
1906 && (single_pred_edge (b
)->flags
& EDGE_FALLTHRU
)
1907 && !LABEL_P (BB_HEAD (b
))
1908 && FORWARDER_BLOCK_P (b
)
1909 /* Note that forwarder_block_p true ensures that
1910 there is a successor for this block. */
1911 && (single_succ_edge (b
)->flags
& EDGE_FALLTHRU
)
1912 && n_basic_blocks
> NUM_FIXED_BLOCKS
+ 1)
1916 "Deleting fallthru block %i.\n",
1919 c
= b
->prev_bb
== ENTRY_BLOCK_PTR
? b
->next_bb
: b
->prev_bb
;
1920 redirect_edge_succ_nodup (single_pred_edge (b
),
1922 delete_basic_block (b
);
1927 if (single_succ_p (b
)
1928 && (s
= single_succ_edge (b
))
1929 && !(s
->flags
& EDGE_COMPLEX
)
1930 && (c
= s
->dest
) != EXIT_BLOCK_PTR
1931 && single_pred_p (c
)
1934 /* When not in cfg_layout mode use code aware of reordering
1935 INSN. This code possibly creates new basic blocks so it
1936 does not fit merge_blocks interface and is kept here in
1937 hope that it will become useless once more of compiler
1938 is transformed to use cfg_layout mode. */
1940 if ((mode
& CLEANUP_CFGLAYOUT
)
1941 && can_merge_blocks_p (b
, c
))
1943 merge_blocks (b
, c
);
1944 update_forwarder_flag (b
);
1945 changed_here
= true;
1947 else if (!(mode
& CLEANUP_CFGLAYOUT
)
1948 /* If the jump insn has side effects,
1949 we can't kill the edge. */
1950 && (!JUMP_P (BB_END (b
))
1951 || (reload_completed
1952 ? simplejump_p (BB_END (b
))
1953 : (onlyjump_p (BB_END (b
))
1954 && !tablejump_p (BB_END (b
),
1956 && (next
= merge_blocks_move (s
, b
, c
, mode
)))
1959 changed_here
= true;
1963 /* Simplify branch over branch. */
1964 if ((mode
& CLEANUP_EXPENSIVE
)
1965 && !(mode
& CLEANUP_CFGLAYOUT
)
1966 && try_simplify_condjump (b
))
1967 changed_here
= true;
1969 /* If B has a single outgoing edge, but uses a
1970 non-trivial jump instruction without side-effects, we
1971 can either delete the jump entirely, or replace it
1972 with a simple unconditional jump. */
1973 if (single_succ_p (b
)
1974 && single_succ (b
) != EXIT_BLOCK_PTR
1975 && onlyjump_p (BB_END (b
))
1976 && !find_reg_note (BB_END (b
), REG_CROSSING_JUMP
, NULL_RTX
)
1977 && try_redirect_by_replacing_jump (single_succ_edge (b
),
1979 (mode
& CLEANUP_CFGLAYOUT
) != 0))
1981 update_forwarder_flag (b
);
1982 changed_here
= true;
1985 /* Simplify branch to branch. */
1986 if (try_forward_edges (mode
, b
))
1987 changed_here
= true;
1989 /* Look for shared code between blocks. */
1990 if ((mode
& CLEANUP_CROSSJUMP
)
1991 && try_crossjump_bb (mode
, b
))
1992 changed_here
= true;
1994 /* Don't get confused by the index shift caused by
2002 if ((mode
& CLEANUP_CROSSJUMP
)
2003 && try_crossjump_bb (mode
, EXIT_BLOCK_PTR
))
2006 #ifdef ENABLE_CHECKING
2008 verify_flow_info ();
2011 changed_overall
|= changed
;
2018 b
->flags
&= ~(BB_FORWARDER_BLOCK
| BB_NONTHREADABLE_BLOCK
);
2020 return changed_overall
;
2023 /* Delete all unreachable basic blocks. */
2026 delete_unreachable_blocks (void)
2028 bool changed
= false;
2029 basic_block b
, next_bb
;
2031 find_unreachable_blocks ();
2033 /* Delete all unreachable basic blocks. */
2035 for (b
= ENTRY_BLOCK_PTR
->next_bb
; b
!= EXIT_BLOCK_PTR
; b
= next_bb
)
2037 next_bb
= b
->next_bb
;
2039 if (!(b
->flags
& BB_REACHABLE
))
2041 delete_basic_block (b
);
2047 tidy_fallthru_edges ();
2051 /* Delete any jump tables never referenced. We can't delete them at the
2052 time of removing tablejump insn as they are referenced by the preceding
2053 insns computing the destination, so we delay deleting and garbagecollect
2054 them once life information is computed. */
2056 delete_dead_jumptables (void)
2060 /* A dead jump table does not belong to any basic block. Scan insns
2061 between two adjacent basic blocks. */
2066 for (insn
= NEXT_INSN (BB_END (bb
));
2067 insn
&& !NOTE_INSN_BASIC_BLOCK_P (insn
);
2070 next
= NEXT_INSN (insn
);
2072 && LABEL_NUSES (insn
) == LABEL_PRESERVE_P (insn
)
2074 && (GET_CODE (PATTERN (next
)) == ADDR_VEC
2075 || GET_CODE (PATTERN (next
)) == ADDR_DIFF_VEC
))
2077 rtx label
= insn
, jump
= next
;
2080 fprintf (dump_file
, "Dead jumptable %i removed\n",
2083 next
= NEXT_INSN (next
);
2085 delete_insn (label
);
2092 /* Tidy the CFG by deleting unreachable code and whatnot. */
2095 cleanup_cfg (int mode
)
2097 bool changed
= false;
2099 /* Set the cfglayout mode flag here. We could update all the callers
2100 but that is just inconvenient, especially given that we eventually
2101 want to have cfglayout mode as the default. */
2102 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
2103 mode
|= CLEANUP_CFGLAYOUT
;
2105 timevar_push (TV_CLEANUP_CFG
);
2106 if (delete_unreachable_blocks ())
2109 /* We've possibly created trivially dead code. Cleanup it right
2110 now to introduce more opportunities for try_optimize_cfg. */
2111 if (!(mode
& (CLEANUP_NO_INSN_DEL
))
2112 && !reload_completed
)
2113 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2118 /* To tail-merge blocks ending in the same noreturn function (e.g.
2119 a call to abort) we have to insert fake edges to exit. Do this
2120 here once. The fake edges do not interfere with any other CFG
2122 if (mode
& CLEANUP_CROSSJUMP
)
2123 add_noreturn_fake_exit_edges ();
2125 if (!dbg_cnt (cfg_cleanup
))
2128 while (try_optimize_cfg (mode
))
2130 delete_unreachable_blocks (), changed
= true;
2131 if (!(mode
& CLEANUP_NO_INSN_DEL
))
2133 /* Try to remove some trivially dead insns when doing an expensive
2134 cleanup. But delete_trivially_dead_insns doesn't work after
2135 reload (it only handles pseudos) and run_fast_dce is too costly
2136 to run in every iteration.
2138 For effective cross jumping, we really want to run a fast DCE to
2139 clean up any dead conditions, or they get in the way of performing
2142 Other transformations in cleanup_cfg are not so sensitive to dead
2143 code, so delete_trivially_dead_insns or even doing nothing at all
2145 if ((mode
& CLEANUP_EXPENSIVE
) && !reload_completed
2146 && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
2148 else if ((mode
& CLEANUP_CROSSJUMP
)
2149 && crossjumps_occured
)
2156 if (mode
& CLEANUP_CROSSJUMP
)
2157 remove_fake_exit_edges ();
2159 /* Don't call delete_dead_jumptables in cfglayout mode, because
2160 that function assumes that jump tables are in the insns stream.
2161 But we also don't _have_ to delete dead jumptables in cfglayout
2162 mode because we shouldn't even be looking at things that are
2163 not in a basic block. Dead jumptables are cleaned up when
2164 going out of cfglayout mode. */
2165 if (!(mode
& CLEANUP_CFGLAYOUT
))
2166 delete_dead_jumptables ();
2168 timevar_pop (TV_CLEANUP_CFG
);
2174 rest_of_handle_jump (void)
2176 delete_unreachable_blocks ();
2178 if (crtl
->tail_call_emit
)
2179 fixup_tail_calls ();
2183 struct rtl_opt_pass pass_jump
=
2187 "sibling", /* name */
2189 rest_of_handle_jump
, /* execute */
2192 0, /* static_pass_number */
2193 TV_JUMP
, /* tv_id */
2194 0, /* properties_required */
2195 0, /* properties_provided */
2196 0, /* properties_destroyed */
2197 TODO_ggc_collect
, /* todo_flags_start */
2198 TODO_verify_flow
, /* todo_flags_finish */
2204 rest_of_handle_jump2 (void)
2206 delete_trivially_dead_insns (get_insns (), max_reg_num ());
2208 dump_flow_info (dump_file
, dump_flags
);
2209 cleanup_cfg ((optimize
? CLEANUP_EXPENSIVE
: 0)
2210 | (flag_thread_jumps
? CLEANUP_THREADING
: 0));
2215 struct rtl_opt_pass pass_jump2
=
2221 rest_of_handle_jump2
, /* execute */
2224 0, /* static_pass_number */
2225 TV_JUMP
, /* tv_id */
2226 0, /* properties_required */
2227 0, /* properties_provided */
2228 0, /* properties_destroyed */
2229 TODO_ggc_collect
, /* todo_flags_start */
2230 TODO_dump_func
| TODO_verify_rtl_sharing
,/* todo_flags_finish */